Master Internship proposal 2 – April to september 2018

Project:	Fast large-scale supervised learning with theoretical guarantees
	
	Nowadays machine learning applications deal with extremely large scale datasets (examples ~10^9, dimensions ~10^6). Classical non-parametric learning algorithms are computationally demanding and do not scale up with modern large-scale datasets. However they achieve state of the art results on medium scale datasets and are optimal from a statistical viewpoint (they achieve best possible accuracy) [1]. So the question arises if it is possible to have reduced computational complexity and optimal statistical guarantees.  

In the last few years part of the community started exploring different algorithms (like deep learning approaches) which have reduced computational complexity, but no theoretical guarantees.  Recently a new trend of works [2,3,4] investigate how to build fast approximations of non-parametric algorithms which achieve optimal statistical guarantees and low computational requirements in the context of regression.

The goal of this internship is to extend the results in [4] in the context of classification and/or  gaussian processes, possibly analyzing different loss functions beyond the squared loss. The work is at the intersection of algorithms, statistics and optimization, and may focus primarily on any these three aspects depending on the candidate.

Students interested in this project should contact Alessandro Rudi or Francis Bach to discuss further.

Pre-requisites:	Machine learning classes (theory, kernel methods)
Convex optimization

Length:	4-6 months

Compensation:	Approximately 1200 per month

Laboratory:	INRIA - Département d’Informatique de l’ENS
	2, rue Simone Iff, 75012 Paris

Contact:	Alessandro Rudi (alessandro.rudi@inria.fr), Francis Bach (francis.bach@inria.fr)

[1] Shalev-Shwartz, S. and Ben-David, S., 2014. Understanding machine learning: From theory to algorithms. Cambridge university press.
[2] Bach, F., 2013. Sharp analysis of low-rank kernel matrix approximations. In Conference on Learning Theory (pp. 185-209).
[3] Rudi, A., Camoriano, R. and Rosasco, L., 2015. Less is more: Nyström computational regularization. In Advances in Neural Information Processing Systems (pp. 1657-1665).
[4] Rudi, A., Carratino, L. and Rosasco, L., 2017. FALKON: An Optimal Large Scale Kernel Method. arXiv preprint arXiv:1705.10958.