[Submitted on 26 Jun 2026 (v1), last revised 15 Oct 2026 (this version, v2)]
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 ${(boldsymbol{x}_i,y_i):; 1 le ile n}$ with $boldsymbol{x}_iin mathbb{R}^d$ standard Gaussian feature vectors, and $y_iinmathbb{R}$ response variables that depend on $boldsymbol{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,dtoinfty$, with $n/dtoalpha in (0, +infty)$. Based on earlier work in related models, we expect that the performance achieved by our algorithm is optimal among polynomial-time algorithms.
Submission history
From: Kangjie Zhou [view email]
[v1] Fri, 26 Jun 2026 19:57:08 UTC (176 KB)
[v2] Thu, 15 Oct 2026 17:27:20 UTC (273 KB)
