Stochastic approximation and least-squares regression, with applications to machine learning.

Summary Multiple problems in machine learning involve minimizing a smooth function on a Euclidean space. For supervised learning, this includes least squares and logistic regressions. While small-scale problems are efficiently solved with many optimization algorithms, large-scale problems require first-order methods from gradient descent. In this manuscript, we consider the special case of quadratic loss. In a first part, we propose to minimize it with a stochastic oracle. In a second part, we consider two of its applications to machine learning: data partitioning and shape constrained estimation. The first contribution is a unified framework for the optimization of non-strongly convex quadratic functions. It includes accelerated gradient descent and averaged gradient descent. This new framework suggests an alternative algorithm that combines the positive aspects of averaging and accelerating. The second contribution is to obtain the optimal prediction error rate for the least squares regression as a function of the noise dependence of the problem and the forgetting of the initial conditions. Our new algorithm is based on accelerated and averaged gradient descent. The third contribution deals with the minimization of composite functions, sum of the expectation of quadratic functions and a convex regularization. We extend the existing results for least squares to any regularization and to the different geometries induced by a Bregman divergence. In a fourth contribution, we consider the discriminative partitioning problem. We propose its first theoretical analysis, a parsimonious extension, its extension to the multi-label case and a new algorithm with a better complexity than the existing methods. The last contribution of this thesis considers the problem of seriation. We adopt a statistical approach where the matrix is observed with noise and we study the minimax estimation rates. We also propose a computationally efficient estimator.