Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval

Antoine Maillard; Tony Bonnaire; Giulio Biroli

stat.MLFeb 19, 2026

Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval

Authors: Antoine Maillard, Tony Bonnaire, Giulio Biroli

Organizations: INRIA Paris & DI ENS, PSL University, Paris, France. · Université Paris-Saclay, CNRS, Institut d’Astrophysique Spatiale, 91405 Orsay, France · Laboratoire de Physique de l’École normale supérieure, ENS, Université PSL, CNRS, Sorbonne Université, Université Paris Cité, F-75005 Paris, France

Abstract

We consider the landscape of empirical risk minimization for high-dimensional Gaussian single-index models (generalized linear models). The objective is to recover an unknown signal $\boldsymbolθ^\star \in \mathbb{R}^d$ (where $d \gg 1$ ) from a loss function $\hat{R}(\boldsymbolθ)$ that depends on pairs of labels $(\mathbf{x}_i \cdot \boldsymbolθ, \mathbf{x}_i \cdot \boldsymbolθ^\star)_{i=1}^n$ , with $\mathbf{x}_i \sim \mathcal{N}(0, I_d)$ , in the proportional asymptotic regime $n \asymp d$ . Using the Kac-Rice formula, we analyze different complexities of the landscape -- defined as the expected number of critical points -- corresponding to various types of critical points, including local minima. We first show that some variational formulas previously established in the literature for these complexities can be drastically simplified, reducing to explicit variational problems over a finite number of scalar parameters that we can efficiently solve numerically. Our framework also provides detailed predictions for properties of the critical points, including the spectral properties of the Hessian and the joint distribution of labels. We apply our analysis to the real phase retrieval problem for which we derive complete topological phase diagrams of the loss landscape, characterizing notably BBP-type transitions where the Hessian at local minima (as predicted by the Kac-Rice formula) becomes unstable in the direction of the signal. We test the predictive power of our analysis to characterize gradient flow dynamics, finding excellent agreement with finite-size simulations of local optimization algorithms, and capturing fine-grained details such as the empirical distribution of labels. Overall, our results open new avenues for the asymptotic study of loss landscapes and topological trivialization phenomena in high-dimensional statistical models.

Figures & tables

Figure 1: In the phase retrieval problem (see eq. ( 3 )), with

a=0.01

q=0.0

, and

\alpha=6.5

, we show the annealed Kac-Rice prediction for the Hessian density of typical-energy minima, see eq. ( 26 ). The predicted complexity is

{\widetilde{\Sigma}}_{0}(q)\simeq 7.10^{-3}>0

(see also Fig. 5 below). The green arrow represents the position of the negative “BBP” outlier in the spectrum predicted by our theory for this Hessian density, see eq. ( 67 ). The red-shaded area delimitates the prediction for the location of the outlier for all minima with positive complexity, from the highest-energy to lowest-energy ones. The histograms correspond to numerical results obtained using finite-size gradient descent simulations, see Section 3.1 for more details.

Figure 2: For $a=0.01$ , $q=0$ , and three values $\alpha=6.0<\alpha_{\mathrm{triv.}}$ , $\alpha=7.5\simeq\alpha_{\mathrm{triv.}}$ and $\alpha=8.0>\alpha_{\mathrm{triv.}}$ , we show: (left) the complexity ${\widetilde{\Sigma}}_{0}(q=0,e)$ for different values of $e$ around the maximal complexity, (middle) the density of the Hessian at local minima of typical energy (at $e_{\star}\coloneqq\argmax{\widetilde{\Sigma}}_{0}(q=0,e)$ ), and (right) the corresponding law $\nu(y,y^{\star})$ . The results are obtained by solving the optimization problem of eq. ( 24 ).

Figure 3: For $a=0.01$ , $q=0.4$ , and three values $\alpha=4.0<\alpha_{\mathrm{triv.}}$ , $\alpha=4.55\simeq\alpha_{\mathrm{triv.}}$ and $\alpha=5.0>\alpha_{\mathrm{triv.}}$ , we show: (left) the complexity $\Sigma_{\mathrm{tot.}}(q,e)$ for different values of $e$ around the maximal complexity, (middle) the density of the Hessian at critical points of typical energy (at $e_{\star}\coloneqq\argmax\Sigma_{\mathrm{tot.}}(q,e)$ ), and (right) the corresponding law $\nu(y,y^{\star})$ . The results are obtained by solving the optimization problem of eq. ( 28 ).

Figure 4: For

a=0.01

q=0.0

, we show (left) the energy of the typical, lowest, and highest-energy minima as a function of

\alpha

. The inset shows the value of the complexity

\tilde{\Sigma}_{0}

(notice that highest and lowest-energy minima are always at zero complexity by definition). In the red region the complexity of local minima is negative. (Right) The spectral density

\rho_{0}(w)

of the Hessian at these minima, for

\alpha=6.0

. We show in dotted red the line

w=0

. In the inset, we show the Lagrange multiplier

\lambda_{\star}

as a function of

\alpha

. The results are obtained by solving the Kac-Rice formula of eq. ( 24 ).

Panel of Figure 5 — Figure 5: Phase diagram predicted by the Kac-Rice method, for $a=0.01$ .

Figure 6: Evolution of the average energy

\langle e\rangle

of the minima for

a=0.01

with

\alpha

at fixed (left)

q=0.0

, (middle)

q=0.1

, and (right)

q=0.2

obtained from the experiments (in black) and the band of energy predicted by the annealed Kac-Rice (in shaded red).

Panel of Figure 7 — Figure 7: Comparisons of the predicted Kac-Rice properties for the minima at $q=0.0$ and typical energy $e_{\star}$ and the empirical minima found by the gradient descent dynamics at $d=512$ and $a=0.01$ . We compare: (left) the eigenvalue distribution of the Hessian $\rho(\lambda)$ , (middle) the distribution of the Hessian weights $F(\mathbf{u})=\partial^{2}_{1}\ell(y,y^{\star})$ , and (right) the joint label distributions $\nu(y,y^{\star})$ . In red are the Kac-Rice predictions described in Section 2 .

Panel of Figure 8 — Figure 8: Minima phase diagram predicted by the Kac-Rice method for $a=0.01$ along with the experimental results.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

		$\displaystyle\alpha(\lambda_{A}A^{(k)}+\lambda_{e}e)\frac{\lambda_{t}}{g^{(k)}}+\lambda_{h}$
		$\displaystyle+\alpha\log\int\mu_{q}(\mathrm{d}\mathbf{u})\,e^{-\lambda_{c}c_{q}(\mathbf{u})-\lambda_{A}A(\mathbf{u})-\lambda_{e}\ell(\mathbf{u})+\log(\alpha+F(\mathbf{u})g^{(k)})-\frac{g^{(k)}+\lambda_{t}}{\alpha}t(\mathbf{u})+\lambda_{t}\frac{F(\mathbf{u})}{\alpha+F(\mathbf{u})g^{(k)}}}$
		$\displaystyle\hskip 100.0pt\times e^{-\lambda_{h}\left(\frac{F(\mathbf{u})g^{(k)}}{\alpha+F(\mathbf{u})g^{(k)}}\right)^{2}+\frac{\lambda_{\star}}{\alpha}K_{q}(\mathbf{u})}$

Appendix

Algorithm 1 An algorithm to compute

{\widetilde{\Sigma}}_{0}(q,e)

Panel of Figure 9 — Figure 9: Phase diagram predicted by the Kac-Rice method, for $a\in\{0.1,1.0\}$ . The conventions and colors are the same as in Fig. 5 in the main text.

Figure 10: For

a=1.0

and

\alpha=3.0

, the annealed complexity

{\widetilde{\Sigma}}_{0}(q,e)

as a function of

q

, for

e=e_{\star}(q=0)/2\simeq 0.048

, half of the loss value of typical minima. In red we show the overlap band of positive complexity.

Figure 11: Evolution of (left) the total complexity

\Sigma_{\mathrm{tot.}}

, (middle) the energy, and (right) total number of steps as functions of

\alpha

for two starting points:

\alpha\in\{3.0,3.5\}

Figure 12: For

a=1.0

and

q=0.0

, we show the computation of the BBP transition point for typical-energy, lowest-energy and highest-energy minima.

Figure 13: Evolution of the average energy

\langle e\rangle

of the minima for

a=1

with

\alpha

at fixed (left)

q=0.0

, (middle)

q=0.1

, and (right)

q=0.2

obtained from the experiments (in black) and the band of energy predicted by the annealed Kac-Rice (in shaded red).

Panel of Figure 14 — Figure 14: Comparisons of the predicted Kac-Rice properties for the minima at $q=0.0$ and typical energy $e_{\star}$ and the empirical minima found by the gradient descent dynamics at $d=512$ and $a=1$ . We compare: (left) the eigenvalue distribution of the Hessian $\rho(\lambda)$ , (middle) the distribution of the Hessian weights $F(\mathbf{u})=\partial^{2}_{1}\ell(y,y^{\star})$ , and (right) the joint label distributions $\nu(y,y^{\star})$ . In red are the Kac-Rice predictions described in Section 2 .

Loss Landscape

See all 22 papers

Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
Jun 26, 2026Andrea Montanari, Kangjie ZhouApproximate Message Passing Statistical Learning Theory
Department of Mathematics and Department of Statistics, Stanford University · Department of Statistics, Columbia University
Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks
Apr 10, 2026Jie Huang, Bruno Loureiro, Stefano Sarao MannelliOverparameterization Loss Landscape
Physics, Chalmers University of Technology and University of Gothenburg · Ecole Normale Superieure, PSL & CNRS · Data Science and AI, Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg +1
Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging
Mar 6, 2026Stanley Wei, Alex Damian, Jason D. LeeLangevin Dynamics Single-Index Models
Princeton University · Harvard University · University of California, Berkeley

Jun 26, 2026J/K move · Enter open · S save

Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model

Andrea Montanari, Kangjie Zhou

Department of Mathematics and Department of Statistics, Stanford University · Department of Statistics, Columbia University

Approximate Message Passing Statistical Learning Theory Multi-Index Models Empirical Risk Minimization

Open paper AskPDF arXiv

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 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,d\to\infty

, with

n/d\toα\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.

Abstract

Loss Landscape

Explore similar work

Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model

Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks

Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging