# Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems

arXiv: https://arxiv.org/abs/2309.05337 · HTML: https://mlsanity.com/paper/2309.05337/

## 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 (most cited first, 29 of 29)

- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [A high-bias, low-variance introduction to Machine Learning for physicists](https://mlsanity.com/paper/1803.08823/) (2018)
- [Revisiting Small Batch Training for Deep Neural Networks](https://mlsanity.com/paper/1804.07612/) (2018)
- [On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)](https://mlsanity.com/paper/2102.12470/) (2021)
- [Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classification](https://mlsanity.com/paper/2006.06098/) (2020)
- [Fluctuation-dissipation relations for stochastic gradient descent](https://mlsanity.com/paper/1810.00004/) (2018)
- [Unveiling the structure of wide flat minima in neural networks](https://mlsanity.com/paper/2107.01163/) (2021)
- [The effective noise of Stochastic Gradient Descent](https://mlsanity.com/paper/2112.10852/) (2021)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Learning through atypical "phase transitions" in overparameterized neural networks](https://mlsanity.com/paper/2110.00683/) (2021)
- [Machine learning in spectral domain](https://mlsanity.com/paper/2005.14436/) (2020)
- [The backtracking survey propagation algorithm for solving random K-SAT problems](https://mlsanity.com/paper/1508.05117/) (2015)
- [Deep learning via message passing algorithms based on belief propagation](https://mlsanity.com/paper/2110.14583/) (2021)
- [Correspondence between neuroevolution and gradient descent](https://mlsanity.com/paper/2008.06643/) (2020)
- [Learning from Survey Propagation: a Neural Network for MAX-E-3-SAT](https://mlsanity.com/paper/2012.06344/) (2020)
- [Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemes](https://mlsanity.com/paper/2012.07747/) (2020)
- [Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs](https://mlsanity.com/paper/1904.02231/) (2019)
- [Phase transitions in the mini-batch size for sparse and dense two-layer neural networks](https://mlsanity.com/paper/2305.06435/) (2023)
- [Hard Optimization Problems have Soft Edges](https://mlsanity.com/paper/2209.04824/) (2022)
- [Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization](https://mlsanity.com/paper/2111.13628/) (2021)
- [Parallel Tempering for the planted clique problem](https://mlsanity.com/paper/1802.05903/) (2018)
- [Large independent sets on random d-regular graphs with fixed degree d](https://mlsanity.com/paper/2003.12293/) (2020)
- [Recurrent Spectral Network (RSN): shaping the basin of attraction of a discrete map to reach automated classification](https://mlsanity.com/paper/2202.04497/) (2022)
- [Fluctuation-dissipation Type Theorem in Stochastic Linear Learning](https://mlsanity.com/paper/2106.02220/) (2021)
- [Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape](https://mlsanity.com/paper/2309.04788/) (2023)

## Built on by (most cited first, 3 of 3)

- [Complex Recurrent Spectral Network](https://mlsanity.com/paper/2312.07296/) (2023)
- [Engineered Ordinary Differential Equations as Classification Algorithm (EODECA): thorough characterization and testing](https://mlsanity.com/paper/2312.14681/) (2023)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)

## 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.