Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
Abstract
Modern machine learning models are trained by optimizing high-dimensional non-convex empirical risk functions. Such cost functions can have a multitude of local optima and yet, gradient-based optimization appears to converge to near-global optima. Within a simple supervised learning setting, we develop a precise picture of which parts of the empirical risk landscape are accessible by polynomial-time algorithms. We are given i.i.d. pairs {(xi,yi): 1 ≤ i≤ n} with xi∈ ℝd standard Gaussian feature vectors, and yi∈ℝ response variables that depend on xi through their projections on an unknown k-dimensional subspace. We use empirical risk minimization to learn a model that depends on an m-dimensional projection of the data (e.g., an m-neurons neural network). We propose an incremental approximate message passing (IAMP) algorithm and precisely characterize the training error it achieves, as well as the relation between test and training error, in the high dimensional asymptotics n,d→∞, with n/d→α∈ (0, +∞). Based on earlier work in related models, we expect that the performance achieved by our algorithm is optimal among polynomial-time algorithms.
Related
- Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data
- Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry
- Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization
- Dimension-dependent symmetry breaking in a diffusive nonlocal interaction model
- Full replica symmetry breaking in the Sherrington-Kirkpatrick model
BibTeX
@misc{montanari2026replica,
title = {{Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model}},
author = {Andrea Montanari and Kangjie Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.28573},
eprint = {2606.28573},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.28573},
}
RIS
TY - UNPB
TI - Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
AU - Andrea Montanari
AU - Kangjie Zhou
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2606.28573
UR - https://arxiv.org/abs/2606.28573
AB - Modern machine learning models are trained by optimizing high-dimensional non-convex empirical risk functions. Such cost functions can have a multitude of local optima and yet, gradient-based optimization appears to converge to near-global optima. Within a simple supervised learning setting, we develop a precise picture of which parts of the empirical risk landscape are accessible by polynomial-time algorithms. We are given i.i.d. pairs {(x_i,y_i): 1 ≤ i≤ n} with x_i∈ ℝ^d standard Gaussian feature vectors, and y_i∈ℝ response variables that depend on x_i through their projections on an unknown k-dimensional subspace. We use empirical risk minimization to learn a model that depends on an m-dimensional projection of the data (e.g., an m-neurons neural network). We propose an incremental approximate message passing (IAMP) algorithm and precisely characterize the training error it achieves, as well as the relation between test and training error, in the high dimensional asymptotics n,d→∞, with n/d→α∈ (0, +∞). Based on earlier work in related models, we expect that the performance achieved by our algorithm is optimal among polynomial-time algorithms.
ER -