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.

39 pages, 12 figures

References in corpus (17)

• Theoretical perspective on the glass transition and amorphous materials
• Score-Based Generative Modeling through Stochastic Differential Equations
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Disordered Systems Insights on Computational Hardness
• Generative diffusion in very large dimensions
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Glassy aspects of melting dynamics (On melting dynamics and the glass transition, Part I)
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• The estimation error of general first order methods
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics

Cited by in corpus (10)

• Dynamical Regimes of Diffusion Models
• Roadmap on machine learning glassy dynamics
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Normalizing flows as an enhanced sampling method for atomistic supercooled liquids
• Anomalous distribution of magnetization in an Ising spin glass with correlated disorder
• Stochastic Resetting Mitigates Latent Gradient Bias of SGD from Label Noise
• A Very Effective and Simple Diffusion Reconstruction for the Diluted Ising Model
• Large time effective kinetics $\beta$-functions for quantum (2+p)-spin glass
• Geometric Regularity in Deterministic Sampling Dynamics of Diffusion-based Generative Models
• Phase diagram and eigenvalue dynamics of stochastic gradient descent in multilayer neural networks