From Zero to Hero: How local curvature at artless initial conditions leads away from bad minima

• URL: http://arxiv.org/abs/2403.02418v2
• Date: Mon, 23 Sep 2024 09:00:09 GMT
• Title: From Zero to Hero: How local curvature at artless initial conditions leads away from bad minima
• Abstract summary: We focus on the phase retrieval problem as a case study for complex loss landscapes. We show that a transition in the spectrum takes place: the direction is lost and the system gets trapped in bad minima. Our analysis sheds light on this new mechanism that facilitates gradient descent dynamics in finite dimensions.
• Score: 9.50832466973301
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide an analytical study of the evolution of the Hessian during gradient descent dynamics, and relate a transition in its spectral properties to the ability of finding good minima. We focus on the phase retrieval problem as a case study for complex loss landscapes. We first characterize the high-dimensional limit where both the number $M$ and the dimension $N$ of the data are going to infinity at fixed signal-to-noise ratio $\alpha = M/N$. For small $\alpha$, the Hessian is uninformative with respect to the signal. For $\alpha$ larger than a critical value, the Hessian displays at short-times a downward direction pointing towards good minima. While descending, a transition in the spectrum takes place: the direction is lost and the system gets trapped in bad minima. Hence, the local landscape is benign and informative at first, before gradient descent brings the system into a uninformative maze. Through both theoretical analysis and numerical experiments, we show that this dynamical transition plays a crucial role for finite (even very large) $N$: it allows the system to recover the signal well before the algorithmic threshold corresponding to the $N\rightarrow\infty$ limit. Our analysis sheds light on this new mechanism that facilitates gradient descent dynamics in finite dimensions, and highlights the importance of a good initialization based on spectral properties for optimization in complex high-dimensional landscapes.

Related papers

• Across the Loss Landscape with Progressive Growth [51.366966420881646]
  We show how grow-and-optimize strategies to train toward flatter regions by viewing growth as progressive relaxation.<n>We empirically validate these predictions in controlled toy basins and in a realistic ResNet/CI-100 setting.<n>Although progressive subspace growth reliably produces flatter solutions, curvature reductions do not universally translate into improved test performance, highlighting subtleties in the flatness-generalization connection.
  arXiv  Detail & Related papers  (2026-08-25T13:50:48Z)
• Non-Singularity of the Gradient Descent map for Neural Networks with Piecewise Analytic Activations [53.348574336527854]
  We investigate the neural network map as a function on the space of weights and biases.<n>We prove, for the first time, the non-singularity of the gradient descent (GD) map on the loss landscape of realistic neural network architectures.
  arXiv  Detail & Related papers  (2025-10-28T14:34:33Z)
• Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks [0.11666234644810891]
  High-dimensional non-student loss play a central role in the theory of Machine Learning.<n>We analyze the spectrum of the Hessian at inception and identify a Baik-Ben Arous-param'ech'e (BBP) transition in the amount of data that separates regimes.
  arXiv  Detail & Related papers  (2025-10-21T09:08:58Z)
• Learning single index model with gradient descent: spectral initialization and precise asymptotics [6.142981584296888]
  We show that for learning problems with large enough sample size, there exists a region around the true signal with benign data.<n>Motivated by many variables, a widely used strategy is a two-stage algorithm, where first apply a spectral gradient descent.<n>We demonstrate our general theory in the example of regularized Wirtinger flow for retrieval.
  arXiv  Detail & Related papers  (2025-09-27T23:27:24Z)
• The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations [29.642830843568525]
  We study the time it takes for the gradient of descent to reach the global minimum of a general, non- loss function.<n>Motivated by applications to neural networks, we provide a series of refinements and extensions of our analysis for loss functions with local minima.
  arXiv  Detail & Related papers  (2025-03-20T17:54:04Z)
• On the Saturation Effects of Spectral Algorithms in Large Dimensions [14.63552944833659]
  Main focus of this paper is to explore the saturation effects for a large class of spectral algorithms in large dimensional settings. We show that the saturation effect occurs in large dimensional setting as long as the source condition $s>tau$ while it occurs in fixed dimensional setting as long as $s>2tau$
  arXiv  Detail & Related papers  (2025-03-01T14:21:38Z)
• Can Stability be Detrimental? Better Generalization through Gradient Descent Instabilities [14.741581246137404]
  We show that instabilities induced by large learning rates move model parameters toward flatter regions of the loss landscape.<n>We find these lead to excellent generalization performance on modern benchmark datasets.
  arXiv  Detail & Related papers  (2024-12-23T14:32:53Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
  We introduce the unhinged loss, a concise loss function, that offers more mathematical opportunities to analyze closed-form dynamics. The unhinged loss allows for considering more practical techniques, such as time-vary learning rates and feature normalization.
  arXiv  Detail & Related papers  (2023-12-13T02:11:07Z)
• Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction [49.66486092259376]
  The mean-field Langevin dynamics (MFLD) is a nonlinear generalization of the Langevin dynamics that incorporates a distribution-dependent drift. Recent works have shown that MFLD globally minimizes an entropy-regularized convex functional in the space of measures. We provide a framework to prove a uniform-in-time propagation of chaos for MFLD that takes into account the errors due to finite-particle approximation, time-discretization, and gradient approximation.
  arXiv  Detail & Related papers  (2023-06-12T16:28:11Z)
• Machine learning in and out of equilibrium [58.88325379746631]
  Our study uses a Fokker-Planck approach, adapted from statistical physics, to explore these parallels. We focus in particular on the stationary state of the system in the long-time limit, which in conventional SGD is out of equilibrium. We propose a new variation of Langevin dynamics (SGLD) that harnesses without replacement minibatching.
  arXiv  Detail & Related papers  (2023-06-06T09:12:49Z)
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability [69.01076284478151]
  In machine learning optimization, gradient descent (GD) often operates at the edge of stability (EoS) This paper studies the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime.
  arXiv  Detail & Related papers  (2023-05-19T16:24:47Z)
• Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data [63.34506218832164]
  In this work, we investigate the implicit bias of gradient flow and gradient descent in two-layer fully-connected neural networks with ReLU activations. For gradient flow, we leverage recent work on the implicit bias for homogeneous neural networks to show that leakyally, gradient flow produces a neural network with rank at most two. For gradient descent, provided the random variance is small enough, we show that a single step of gradient descent suffices to drastically reduce the rank of the network, and that the rank remains small throughout training.
  arXiv  Detail & Related papers  (2022-10-13T15:09:54Z)
• Magnitude and Angle Dynamics in Training Single ReLU Neurons [45.886537625951256]
  We decompose gradient flow $w(t)$ to magnitude $w(t)$ and angle $phi(t):= pi - theta(t) $ components. We find that small scale initialization induces slow convergence speed for deep single ReLU neurons.
  arXiv  Detail & Related papers  (2022-09-27T13:58:46Z)
• Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks [15.711517003382484]
  We show that the Hessian spectrum concentrates near positives, with the exception of $Theta(d)$ eigenvalues which growly with$d$. This makes possible the creation and the annihilation of minima using powerful tools from bifurcation theory.
  arXiv  Detail & Related papers  (2021-07-21T22:05:48Z)
• Vanishing Curvature and the Power of Adaptive Methods in Randomly Initialized Deep Networks [30.467121747150816]
  This paper revisits the so-called vanishing gradient phenomenon, which commonly occurs in deep randomly neural networks. We first show that vanishing gradients cannot be circumvented when the network width scales with less than O(depth)
  arXiv  Detail & Related papers  (2021-06-07T16:29:59Z)
• Implicit bias of deep linear networks in the large learning rate phase [15.846533303963229]
  We characterize the implicit bias effect of deep linear networks for binary classification using the logistic loss in a large learning rate regime. We claim that depending on the separation conditions of data, the gradient descent iterates will converge to a flatter minimum in the catapult phase.
  arXiv  Detail & Related papers  (2020-11-25T06:50:30Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  This paper attempts to characterize the particular regularization effect of SGD in the moderate learning rate regime. We show that SGD converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions.
  arXiv  Detail & Related papers  (2020-11-04T21:07:52Z)
• Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry [9.695960412426672]
  We analytically characterize the Hessian at various families of spurious minima. In particular, we prove that for $dge k$ standard Gaussian inputs: (a) of the $dk$ eigenvalues of the Hessian, $dk - O(d)$ concentrate near zero, (b) $Omega(d)$ of the eigenvalues grow linearly with $k$.
  arXiv  Detail & Related papers  (2020-08-04T20:08:35Z)
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy [71.25689267025244]
  We show how the transition is controlled by the relationship between the scale and how accurately we minimize the training loss. Our results indicate that some limit behaviors of gradient descent only kick in at ridiculous training accuracies.
  arXiv  Detail & Related papers  (2020-07-13T23:49:53Z)
• Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval [31.993312235435916]
  We show that gradient-based algorithms can find good minima instead of being trapped in spurious ones. By numerical experiments we show that in this regime the gradient flow algorithm is not trapped; it drifts away from the critical points along the unstable direction and succeeds in finding the global minimum.
  arXiv  Detail & Related papers  (2020-06-12T08:21:12Z)
• Analytic Signal Phase in $N-D$ by Linear Symmetry Tensor--fingerprint modeling [69.35569554213679]
  We show that the Analytic Signal phase, and its gradient have a hitherto unstudied discontinuity in $2-D $ and higher dimensions. This shortcoming can result in severe artifacts whereas the problem does not exist in $1-D $ signals. We suggest the use of Linear Symmetry phase, relying on more than one set of Gabor filters, but with a negligible computational add-on.
  arXiv  Detail & Related papers  (2020-05-16T21:17:26Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
  arXiv  Detail & Related papers  (2020-05-13T14:53:36Z)
• The Break-Even Point on Optimization Trajectories of Deep Neural Networks [64.7563588124004]
  We argue for the existence of the "break-even" point on this trajectory. We show that using a large learning rate in the initial phase of training reduces the variance of the gradient. We also show that using a low learning rate results in bad conditioning of the loss surface even for a neural network with batch normalization layers.
  arXiv  Detail & Related papers  (2020-02-21T22:55:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.