SGD-like Algorithm and Metropolis Dynamics Equivalence
Author Information
Author(s): Angelini Maria Chiara, Cavaliere Angelo Giorgio, Marino Raffaele, Ricci-Tersenghi Federico
Primary Institution: Dipartimento di Fisica, Sapienza Università di Roma
Hypothesis
Is Stochastic Gradient Descent (SGD) substantially different from Metropolis Monte Carlo dynamics?
Conclusion
The study shows that the dynamics of an SGD-like algorithm closely resembles that of Metropolis Monte Carlo dynamics in discrete optimization problems.
Supporting Evidence
- The SGD-like algorithm does not satisfy detailed balance but closely follows the MC dynamics.
- Both algorithms show similar energy relaxation and nucleation times.
- The effective temperature for SGD is related to the mini-batch size.
- Numerical simulations indicate that the two algorithms behave similarly in various regimes.
Takeaway
This study compares two algorithms used for solving problems: one is a popular method called SGD, and the other is a method called Metropolis. They found that both methods work similarly in certain situations.
Methodology
The study involved numerical and analytical analyses of the behavior of SGD-like and Metropolis MC algorithms on the q-coloring problem.
Limitations
The study focuses on a specific discrete optimization problem and may not generalize to all types of optimization problems.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website