Title: Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
Abstract : Recent years witnessed the development of powerful
generative models based on flows, diffusion or autoregressive neural
networks, achieving remarkable success in generating data from
examples with applications in a broad range of areas. A theoretical
analysis of the performance and understanding of the limitations of
these methods remain, however, challenging. In this paper, we
undertake a step in this direction by analysing the efficiency of
sampling by these methods on a class of problems with a known
probability distribution and comparing it with the sampling
performance of more traditional methods such as the Monte Carlo Markov
chain and Langevin dynamics. We focus on a class of probability
distribution widely studied in the statistical physics of disordered
systems that relate to spin glasses, statistical inference and
constraint satisfaction problems. We leverage the fact that sampling
via flow-based, diffusion-based or autoregressive networks methods can
be equivalently mapped to the analysis of a Bayes optimal denoising of
a modified probability measure. Our findings demonstrate that these
methods encounter difficulties in sampling stemming from the presence
of a first-order phase transition along the algorithm's denoising
path. Our conclusions go both ways: we identify regions of parameters
where these methods are unable to sample efficiently, while that is
possible using standard Monte Carlo or Langevin approaches. We also
identify regions where the opposite happens: standard approaches are
inefficient while the discussed generative methods work well.
Bio
Florent Krzakala is a French physicist and applied mathematician,
currently a professor at EPFL. His research focuses on using
mathematical tools inspired by statistical physics to solve
theoretical problems in physics, computer science, machine learning,
statistics, and signal processing. He received his PhD in statistical
physics jointly from Pierre and Marie Curie University and Paris-Sud
University in 2002. After a postdoc with Giorgio Parisi in Rome, he
was a lecturer at ESPCI in Paris and then a professor at Sorbonne
University and the Ecole Normale Supérieure in Paris, where he also
co-held the data science chair. He has held various visiting positions
at universities in the United States and was named a junior fellow of
the Institut Universitaire de France in 2015. Krzakala leads the
Idephics laboratory at EPFL and is known in particular for his work on
community detection, quantum annealing, and phase transitions in
satisfiability and coloring problems, as well as high-dimensional
statistics, machine learning and algorithms.