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.

arXiv comment39 pages, 12 figures

References in corpus (45)

• Denoising Diffusion Probabilistic Models
• Message Passing Algorithms for Compressed Sensing
• Theoretical perspective on the glass transition and amorphous materials
• Deep Unsupervised Learning using Nonequilibrium Thermodynamics
• Score-Based Generative Modeling through Stochastic Differential Equations
• Generative Modeling by Estimating Gradients of the Data Distribution
• Analytical Solution of the Off-Equilibrium Dynamics of a Long Range Spin-Glass Model
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Thermodynamic signature of growing amorphous order in glass-forming liquids
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Equivariant flow-based sampling for lattice gauge theory
• GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The Nishimori line and Bayesian Statistics
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Efficient generative modeling of protein sequences using simple autoregressive models
• Thin shell implies spectral gap up to polylog via a stochastic localization scheme
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• 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
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Survey-propagation decimation through distributed local computations
• Statistical and computational phase transitions in spiked tensor estimation
• Random Pinning Glass Transition: Hallmarks, Mean-Field Theory and Renormalization Group Analysis
• A note on classical ground state energies
• The condensation transition in random hypergraph 2-coloring
• Phase Transitions in Sparse PCA
• Typology of phase transitions in Bayesian inference 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
• Phase transitions in the $q$-coloring of random hypergraphs
• Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval
• Bicoloring Random Hypergraphs
• On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
• 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