Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
arXiv:2309.05337 · doi:10.1038/s41598-024-62625-8
Abstract
Is Stochastic Gradient Descent (SGD) substantially different from Metropolis Monte Carlo dynamics? This is a fundamental question at the time of understanding the most used training algorithm in the field of Machine Learning, but it received no answer until now. Here we show that in discrete optimization and inference problems, the dynamics of an SGD-like algorithm resemble very closely that of Metropolis Monte Carlo with a properly chosen temperature, which depends on the mini-batch size. This quantitative matching holds both at equilibrium and in the out-of-equilibrium regime, despite the two algorithms having fundamental differences (e.g.\ SGD does not satisfy detailed balance). Such equivalence allows us to use results about performances and limits of Monte Carlo algorithms to optimize the mini-batch size in the SGD-like algorithm and make it efficient at recovering the signal in hard inference problems.
19 pages, 9 figures
References in corpus (23)
- Active Particles in Complex and Crowded Environments
- Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
- A high-bias, low-variance introduction to Machine Learning for physicists
- Energy flow, partial equilibration and effective temperatures in systems with slow dynamics
- Phase Transitions in the Coloring of Random Graphs
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Aging and multiscaling in out of equilibrium dynamical processes in granular media
- Nonequilibrium Brownian motion beyond the effective temperature
- Machine learning in spectral domain
- Unveiling the structure of wide flat minima in neural networks
- Monte Carlo methods in statistical physics: Mathematical foundations and strategies
- Learning through atypical "phase transitions" in overparameterized neural networks
- Spectral pruning of fully connected layers: ranking the nodes based on the eigenvalues
- Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemes
- Hard Optimization Problems have Soft Edges
- Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
- Parallel Tempering for the planted clique problem
- On the training of sparse and dense deep neural networks: less parameters, same performance
- Revisiting the Challenges of MaxClique
- Diffusion of a Brownian ellipsoid in a force field
- Recurrent Spectral Network (RSN): shaping the basin of attraction of a discrete map to reach automated classification
- Fluctuation-dissipation Type Theorem in Stochastic Linear Learning
- Advective-diffusive motion on large scales from small-scale dynamics with an internal symmetry