Faster high-accuracy log-concave sampling via algorithmic warm starts

JM Altschuler, S Chewi - Journal of the ACM, 2024 - dl.acm.org
It is a fundamental problem to understand the complexity of high-accuracy sampling from a
strongly log-concave density π on ℝ d. Indeed, in practice, high-accuracy samplers such as …

Shifted composition II: shift Harnack inequalities and curvature upper bounds

JM Altschuler, S Chewi - arXiv preprint arXiv:2401.00071, 2023 - arxiv.org
We apply the shifted composition rule--an information-theoretic principle introduced in our
earlier work [AC23]--to establish shift Harnack inequalities for the Langevin diffusion. We …

Shifted Interpolation for Differential Privacy

J Bok, W Su, JM Altschuler - arXiv preprint arXiv:2403.00278, 2024 - arxiv.org
Noisy gradient descent and its variants are the predominant algorithms for differentially
private machine learning. It is a fundamental question to quantify their privacy leakage, yet …

Shifted Composition III: Local Error Framework for KL Divergence

JM Altschuler, S Chewi - arXiv preprint arXiv:2412.17997, 2024 - arxiv.org
Coupling arguments are a central tool for bounding the deviation between two stochastic
processes, but traditionally have been limited to Wasserstein metrics. In this paper, we apply …

On Independent Samples Along the Langevin Diffusion and the Unadjusted Langevin Algorithm

J Liang, S Mitra, A Wibisono - arXiv preprint arXiv:2402.17067, 2024 - arxiv.org
We study the rate at which the initial and current random variables become independent
along a Markov chain, focusing on the Langevin diffusion in continuous time and the …

HWI inequalities in discrete spaces via couplings

TA Courtade, M Fathi - Electronic Communications in Probability, 2024 - projecteuclid.org
HWI inequalities are interpolation inequalities relating entropy, Fisher information and
optimal transport distances. We adapt an argument of Y. Wu for proving the Gaussian HWI …

[PDF][PDF] The shifted composition rule

JM Altschuler, S Chewi - International Zurich Seminar …, 2024 - research-collection.ethz.ch
KL (µY∥ νY)≤ KL (µX′∥ νX)+ EKL (µY| X= x∥ νY| X= x′) where µ is a joint distribution
on X, X′, Y; ν is a joint distribution on X, Y; and the expectation is over any coupling (x, x′) …