Stochastic Gradient Descent-like relaxation is equivalent to Glauber
  dynamics in discrete optimization and inference problems
Maria Chiara Angelini Angelo Giorgio Cavaliere Raffaele Marino Federico Ricci-Tersenghi
Is Stochastic Gradient Descent (SGD) substantially different from Glauber
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.