mlsanityData to 14 Oct 2026

Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization

arXiv 2204.01585 ↗First posted 4 Apr 2022cs.LG cs.CR math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism, whose privacy analysis does not depend on convexity and which can be stopped at anytime without compromising privacy, and ii) tight uniform stability guarantees for the exponential mechanism. As a direct consequence, we obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP). The framework allows us to design a DP uniform sampler from the Rashomon set. Rashomon sets are widely used in interpretable and robust machine learning, understanding variable importance, and characterizing fairness.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 38 of its 88 references that are in the map. First posted on arXiv 4 Apr 2022.

Builds on

38 of 88 references.

References · 38

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  3. 2018Averaging Weights Leads to Wider Optima and Better Generalizationcited by 1,209
  4. 2017Renyi Differential Privacycited by 650
  5. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  6. 2018All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneouslycited by 373
  7. 2021Interpretable Machine Learning: Fundamental Principles and 10 Grand Challengescited by 367
  8. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
  9. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 227
  10. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  11. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 197
  12. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
26 more
  1. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  2. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  3. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 127
  4. 2018Privacy Amplification by Iterationcited by 100
  5. 2019On the Existence of Simpler Machine Learning Modelscited by 89
  6. 2017Convergence of Langevin MCMC in KL-divergencecited by 88
  7. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  8. 2021Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descentcited by 73
  9. 2018Sharp convergence rates for Langevin dynamics in the nonconvex settingcited by 68
  10. 2021Characterizing Fairness Over the Set of Good Models Under Selective Labelscited by 65
  11. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 62
  12. 2015Between Pure and Approximate Differential Privacycited by 56
  13. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
  14. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  15. 2020Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergencecited by 42
  16. 2017Tight Lower Bounds for Differentially Private Selectioncited by 34
  17. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  18. 2020Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMCcited by 27
  19. 2020Near Instance-Optimality in Differential Privacycited by 23
  20. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 20
  21. 2022Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamicscited by 19
  22. 2014Robust Optimization using Machine Learning for Uncertainty Setscited by 14
  23. 2018A Theory of Statistical Inference for Ensuring the Robustness of Scientific Resultscited by 13
  24. 2021Sampling from Log-Concave Distributions with Infinity-Distance Guaranteescited by 8
  25. 2015Identifying a minimal class of models for high-dimensional datacited by 3
  26. 2019Detecting Underspecification with Local Ensemblescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 0; 2025: 1; 2026: 1.

3 papers.

  1. 2023Optimal Differentially Private Model Training with Public Datacited by 9
  2. 2025Purifying Approximate Differential Privacy with Randomized Post-processingcited by 2
  3. 2026On the Stability of Spherical Hellinger-Kantorovich Flows and Their Implications for Differential Privacycited by 0