42 citations · 156 across the 35 of their papers we have counts for
39 papers
Sampling with collective variables: Relative error analysis for umbrella sampling under general conditions
Holden Lee, Matheau Santana-Gijzen, Jonathan Weare
We consider the problem of estimating the expectation of a function (observable) with respect to a high-dimensional probability distribution, under the assumption that a low-dimens…
Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Ewan Davies, Holden Lee, Juspreet Singh Sandhu +1
We develop a new method for proving a weak functional inequality by first proving it for a sufficiently regular sequence of distributions approximating the stochastic localization…
Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
Ewan Davies, Holden Lee, Juspreet Singh Sandhu +1
We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick model with negligible total-variation distance (TVD) error up to inverse tempera…
Sampling from multimodal distributions with warm starts: Non-asymptotic bounds for the Reweighted Annealed Leap-Point Sampler
Holden Lee, Matheau Santana-Gijzen
Sampling from multimodal distributions is a central challenge in Bayesian inference and machine learning. In light of hardness results for sampling -- classical MCMC methods, even…
Mixing of general biased adjacent transposition chains
Reza Gheissari, Holden Lee, Eric Vigoda
We analyze the general biased adjacent transposition shuffle process, which is a well-studied Markov chain on the symmetric group . In each step, an adjacent pair of elements…
Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression
Holden Lee, Kexin Zhang
We propose using a modified conductance-based method to study the mixing time of an important class of two-block Gibbs samplers, the data augmentation (DA) algorithm. %, which is o…
Efficiently learning and sampling multimodal distributions with data-based initialization
Frederic Koehler, Holden Lee, Thuy-Duong Vuong
We consider the problem of sampling a multimodal distribution with a Markov chain given a small number of samples from the stationary measure. Although mixing can be arbitrarily sl…
What does guidance do? A fine-grained analysis in a simple setting
Muthu Chidambaram, Khashayar Gatmiry, Sitan Chen +2
The use of guidance in diffusion models was originally motivated by the premise that the guidance-modified score is that of the data distribution tilted by a conditional likelihood…
Sampling from the Continuous Random Energy Model in Total Variation Distance
Holden Lee, Qiang Wu
The continuous random energy model (CREM) is a toy model of spin glasses on that, in the limit, exhibits an infinitely hierarchical correlation structure. We give two p…
Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition
Holden Lee, Matheau Santana-Gijzen
We prove bounds on the variance of a function under the empirical measure of the samples obtained by the Sequential Monte Carlo (SMC) algorithm, with time complexity depending…
Learning Mixtures of Gaussians Using Diffusion Models
Khashayar Gatmiry, Jonathan Kelner, Holden Lee
We give a new algorithm for learning mixtures of Gaussians (with identity covariance in ) to TV error , with quasi-polynomial ($O(n^{\text{poly\,log}…
Sampling List Packings
Evan Camrud, Ewan Davies, Alex Karduna +1
We study the problem of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted a lot of atte…
How Flawed Is ECE? An Analysis via Logit Smoothing
Muthu Chidambaram, Holden Lee, Colin McSwiggen +1
Informally, a model is calibrated if its predictions are correct with a probability that matches the confidence of the prediction. By far the most common method in the literature f…
Principled Gradient-based Markov Chain Monte Carlo for Text Generation
Li Du, Afra Amini, Lucas Torroba Hennigen +4
Recent papers have demonstrated the possibility of energy-based text generation by adapting gradient-based sampling algorithms, a paradigm of MCMC algorithms that promises fast con…
Parallelising Glauber dynamics
Holden Lee
For distributions over discrete product spaces , Glauber dynamics is a Markov chain that at each step, resamples a random coordinate conditioned on the other co…
Provable benefits of score matching
Chirag Pabbaraju, Dhruv Rohatgi, Anish Sevekari +3
Score matching is an alternative to maximum likelihood (ML) for estimating a probability distribution parametrized up to a constant of proportionality. By fitting the ''score'' of…
The probability flow ODE is provably fast
Sitan Chen, Sinho Chewi, Holden Lee +3
We provide the first polynomial-time convergence guarantees for the probability flow ODE implementation (together with a corrector step) of score-based generative modeling. Our ana…
Improved Bound for Mixing Time of Parallel Tempering
Holden Lee, Zeyu Shen
In the field of sampling algorithms, MCMC (Markov Chain Monte Carlo) methods are widely used when direct sampling is not possible. However, multimodality of target distributions of…
Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions
Hongrui Chen, Holden Lee, Jianfeng Lu
We give an improved theoretical analysis of score-based generative modeling. Under a score estimate with small error (averaged across timesteps), we provide efficient converg…
Fisher information lower bounds for sampling
Sinho Chewi, Patrik Gerber, Holden Lee +1
We prove two lower bounds for the complexity of non-log-concave sampling within the framework of Balasubramanian et al. (2022), who introduced the use of Fisher information (FI) bo…
Convergence of score-based generative modeling for general data distributions
Holden Lee, Jianfeng Lu, Yixin Tan
Score-based generative modeling (SGM) has grown to be a hugely successful method for learning to generate samples from complex data distributions such as that of images and audio.…
Pitfalls of Gaussians as a noise distribution in NCE
Holden Lee, Chirag Pabbaraju, Anish Sevekari +1
Noise Contrastive Estimation (NCE) is a popular approach for learning probability density functions parameterized up to a constant of proportionality. The main idea is to design a…
Convergence for score-based generative modeling with polynomial complexity
Holden Lee, Jianfeng Lu, Yixin Tan
Score-based generative modeling (SGM) is a highly successful approach for learning a probability distribution from data and generating further samples. We prove the first polynomia…
Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods
Frederic Koehler, Holden Lee, Andrej Risteski
We consider Ising models on the hypercube with a general interaction matrix , and give a polynomial time sampling algorithm when all but eigenvalues of lie in an inte…