Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 29 of its 67 references that are in the map. First posted on arXiv 11 Sep 2023.
Builds on
29 of 67 references.
References · 29
- 2016An overview of gradient descent optimization algorithmscited by 1,033
- 2017Three Factors Influencing Minima in SGDcited by 273
- 2015Coordinate Descent Algorithmscited by 219
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
- 2018Don't Use Large Mini-Batches, Use Local SGDcited by 202
- 2018A high-bias, low-variance introduction to Machine Learning for physicistscited by 108
- 2018Revisiting Small Batch Training for Deep Neural Networkscited by 102
- 2021On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)cited by 73
- 2020Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classificationcited by 60
- 2018Fluctuation-dissipation relations for stochastic gradient descentcited by 48
- 2021Unveiling the structure of wide flat minima in neural networkscited by 28
- 2021The effective noise of Stochastic Gradient Descentcited by 25
17 more
- 2021Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problemcited by 23
- 2021Learning through atypical "phase transitions" in overparameterized neural networkscited by 21
- 2020Machine learning in spectral domaincited by 20
- 2015The backtracking survey propagation algorithm for solving random K-SAT problemscited by 14
- 2021Deep learning via message passing algorithms based on belief propagationcited by 12
- 2020Correspondence between neuroevolution and gradient descentcited by 11
- 2020Learning from Survey Propagation: a Neural Network for MAX-E-3-SATcited by 11
- 2020Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemescited by 11
- 2019Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphscited by 9
- 2023Phase transitions in the mini-batch size for sparse and dense two-layer neural networkscited by 9
- 2022Hard Optimization Problems have Soft Edgescited by 8
- 2021Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimizationcited by 6
- 2018Parallel Tempering for the planted clique problemcited by 5
- 2020Large independent sets on random d-regular graphs with fixed degree dcited by 4
- 2022Recurrent Spectral Network (RSN): shaping the basin of attraction of a discrete map to reach automated classificationcited by 4
- 2021Fluctuation-dissipation Type Theorem in Stochastic Linear Learningcited by 3
- 2023Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscapecited by 3
Built on by
Citing papers per year: 2023: 2; 2024: 1.
3 papers.