{"id":"arxiv/2606.28573","url":"https://arxiv.org/abs/2606.28573","tags":["cs.LG","math.ST"],"score":0,"title":"Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model","domain":"cs.LG","source":"arxiv","authors":["Andrea Montanari","Kangjie Zhou"],"reviews":0,"subject":"cs.LG","summary":"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 i\\le n\\}$ with $\\boldsymbol{x}_i\\in \\mathbb{R}^d$ standard Gaussian feature vectors, and $y_i\\in\\mathbb{R}$ response…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-26","reactions":{}}