Séminaire de Statistique et Optimisation

Concentration of solutions of optimization problems

by Paul Escande (IMT, CNRS)

Salle K. Johnson, 1er étage (1R3)

Salle K. Johnson, 1er étage


Many estimation problems can be cast in the framework of finding the minimizers of the expectation of a loss function, also known as the risk. In practice the underlying distribution is unknown and only i.i.d. samples can be drawn from it. The empirical risk is therefore minimized in place of the true one.
Studying the generalization error (i.e. the error between the risk evaluated at the empirical minimizers and the optimal risk) is an important question started in the seventies and is still an active research field.
Little is however known regarding the actual converence of the minimizers. Some works recently started to address this question. Yet, they do not provide optimal result on some important estimation problems. After reviewing the main results of the literature, we will observe their lack of optimality on some important estimation problems.
We will then provide an alternative view of this problem that allows to settle the assumptions from which optimal convergence rates can be proven. Based on a fine characterization of the behavior of the risk around its minimizers, those results also leverage tools from geometry, optimization, statistics, and probability theory.