Thresholds of descending algorithms in inference problems

ITS Seminar with Stefano Sarao Minelli (Saclay/Courant)

In problems characterized by numerous degrees of freedom many relevant observables require the evaluation of prohibitive high-dimensional integrals. In general, we rely on two strategies to perform such computations: we consider dynamics that asymptotically characterize the integral; or we approximate the integral reducing the degrees of freedom. In particular I will consider the Langevin algorithm and a variation of cavity method. I will discuss a prototypical model from statistical inference where both the approaches can be analyzed. Using tools from the statistical physics of disordered systems I will draw a phase diagram of the algorithms and explain why and when they fail. Finally, I will extend the analysis to gradient descent algorithm and highlight aspects of interest in machine learning problems.