Universality of empirical risk minimization

Understand

We study a general class of optimization problems with decision variable $\boldsymbol{\Theta} \in \mathbb{R}^{p \times k}$ and cost function which is the sum of $n$ terms, each dependent on $\boldsymbol{\Theta}$ through the $k$-dimensional projection $\boldsymbol{\Theta}^\top \boldsymbol{x}_i$, where $\boldsymbol{x}_i$, $i \leq n$ are i.i.d.

• random vectors.
• This setting is general enough to include examples of current interest in statistical physics, high-dimensional statistics, and statistical learning theory.
• We consider the proportional asymptotics $n, p \to \infty$, with $n/p = \Theta(1)$, and prove that, whenever there exists a minimizer satisfying a suitable generalization of a "delocalization" condition, the minimum value is universal.