mlsanityData to 14 Oct 2026

Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity

arXiv 2501.04134 ↗First posted 7 Jan 2025stat.ML cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the mixing time of the projected Langevin algorithm (LA) and the privacy curve of noisy Stochastic Gradient Descent (SGD), beyond nonexpansive iterations. Specifically, we derive new mixing time bounds for the projected LA which are, in some important cases, dimension-free and poly-logarithmic on the accuracy, closely matching the existing results in the smooth convex case. Additionally, we establish new upper bounds for the privacy curve of the subsampled noisy SGD algorithm. These bounds show a crucial dependency on the regularity of gradients, and are useful for a wide range of convex losses beyond the smooth case. Our analysis relies on a suitable extension of the Privacy Amplification by Iteration (PABI) framework (Feldman et al., 2018; Altschuler and Talwar, 2022, 2023) to noisy iterations whose gradient map is not necessarily nonexpansive. This extension is achieved by designing an optimization problem which accounts for the best possible R'enyi divergence bound obtained by an application of PABI, where the tractability of the problem is crucially related to the modulus of continuity of the associated gradient mapping. We show that, in several interesting cases -- namely the nonsmooth convex, weakly smooth and (strongly) dissipative -- such optimization problem can be solved exactly and explicitly, yielding the tightest possible PABI-based bounds.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 21 of its 33 references that are in the map. First posted on arXiv 7 Jan 2025.

Builds on

21 of 33 references.

References · 21

  1. 2020Denoising Diffusion Probabilistic Modelscited by 21,076
  2. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  3. 2019R'enyi Differential Privacy of the Sampled Gaussian Mechanismcited by 204
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  5. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 146
  6. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  7. 2018Privacy Amplification by Iterationcited by 100
  8. 2016Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreaucited by 84
  9. 2021Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descentcited by 73
  10. 2022Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Losscited by 61
  11. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
  12. 2022Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)cited by 48
9 more
  1. 2013Proximal Markov chain Monte Carlo algorithmscited by 46
  2. 2019Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetrycited by 34
  3. 2019Langevin Monte Carlo without smoothnesscited by 28
  4. 2021The Langevin Monte Carlo algorithm in the non-smooth log-concave casecited by 26
  5. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 22
  6. 2024Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Samplercited by 11
  7. 2023Privacy Loss of Noisy Stochastic Gradient Descent Might Converge Even for Non-Convex Lossescited by 10
  8. 2024Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothnesscited by 8
  9. 2024Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite lossescited by 6

Built on by

Not cited yet.