Thresholds of descending algorithms in inference problems

Abstract

We review recent works on analyzing the dynamics of gradient-based algorithms in a prototypical statistical inference problem. Using methods and insights from the physics of glassy systems, these works showed how to understand quantitatively and qualitatively the performance of gradient-based algorithms. Here we review the key results and their interpretation in non-technical terms accessible to a wide audience of physicists in the context of related works.

arXiv comment8 pages, 4 figures

References in corpus (21)

• Message Passing Algorithms for Compressed Sensing
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• The structural glass transition and the entropy of the metastable states
• Statistical physics of inference: Thresholds and algorithms
• Data Mining and Machine Learning in Astronomy
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• The spherical $2+p$ spin glass model: an exactly solvable model for glass to spin-glass transition
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Out-of-equilibrium dynamical mean-field equations for the perceptron model
• On the formal equivalence of the TAP and thermodynamic methods in the SK model
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• Complexity of the Sherrington-Kirkpatrick Model in the Annealed Approximation
• Statistical Mechanics of Recurrent Neural Networks II. Dynamics
• Glassy nature of the hard phase in inference problems
• Quenched Computation of the Complexity of the Sherrington-Kirkpatrick Model
• Aging and relaxation near Random Pinning Glass Transitions

Cited by in corpus (2)

• High-dimensional Asymptotics of Langevin Dynamics in Spiked Matrix Models
• Entropic barriers as a reason for hardness in both classical and quantum algorithms