Force balance controls the relaxation time of the gradient descent algorithm in the satisfiable phase

Abstract

We numerically study the relaxation dynamics of the single layer perceptron with the spherical constraint. This is the simplest model of neural networks and serves a prototypical mean-field model of both convex and non-convex optimization problems. The relaxation time of the gradient descent algorithm rapidly increases near the SAT-UNSAT transition point. We numerically confirm that the first non-zero eigenvalue of the Hessian controls the relaxation time. This first eigenvalue vanishes much faster upon approaching the SAT-UNSAT transition point than the prediction of Marchenko-Pastur law in random matrix theory derived under the assumption that the set of unsatisfied constraints are uncorrelated. This leads to a non-trivial critical exponent of the relaxation time in the SAT phase. Using a simple scaling analysis, we show that the isolation of this first eigenvalue from the bulk of spectrum is attributed to the force balance at the SAT-UNSAT transition point. Finally, we show that the estimated critical exponent of the relaxation time in the non-convex region agrees very well with that of frictionless spherical particles, which have been studied in the context of the jamming transition of granular materials.

arXiv comment10 pages, 12 figures

References in corpus (21)

• Fractal free energy landscapes in structural glasses
• Critical Scaling of Shear Viscosity at the Jamming Transition
• Marginal Stability in Structural, Spin and Electron Glasses
• Universal Spectrum of Normal Modes in Low-Temperature Glasses: an Exact Solution
• Introduction to Random Matrices - Theory and Practice
• A unified framework for non-Brownian suspension flows and soft amorphous solids
• Scaling description of generalization with number of parameters in deep learning
• Jamming Criticality Revealed by Removing Localized Buckling Excitations
• The simplest model of jamming
• Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
• The jamming transition as a paradigm to understand the loss landscape of deep neural networks
• Unified Theory of Inertial Granular Flows and Non-Brownian Suspensions
• Universality of jamming of non-spherical particles
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• On Variational Arguments for Vibrational Modes near Jamming
• Toward a microscopic description of flow near the jamming threshold
• The jamming transition in high dimension: an analytical study of the TAP equations and the effective thermodynamic potential
• Universal relaxation dynamics of sphere packings below jamming
• Universal non-mean-field scaling in the density of state of amorphous solids
• Mean field theory of jamming of nonspherical particles
• Infinitesimal asphericity changes the universality of the jamming transition

Cited by in corpus (7)

• The effective noise of Stochastic Gradient Descent
• Relaxation dynamics of non-Brownian spheres below jamming
• Hard-Sphere Jamming through the Lens of Linear Optimization
• Note: Relaxation time below jamming
• Gradient descent dynamics and the jamming transition in infinite dimensions
• Overlaps between eigenvectors of spiked, correlated random matrices: from matrix PCA to random Gaussian landscapes
• Interaction-free ergodicity-breaking driven by temporally hyperuniform noise