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

SGD-like Algorithm and Metropolis Dynamics Equivalence

Sample size: 280 publication Evidence: high

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)

10.1038/s41598-024-62625-8

Want to read the original?

Access the complete publication on the publisher's website

View Original Publication