  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.
