mlsanityData to 7 Oct 2026

Private Convex Optimization via Exponential Mechanism

arXiv 2203.00263 ↗First posted 1 Mar 2022cs.DS cs.CR cs.LGcited by 47

Not on the map. Why?

Abstract (arXiv)

In this paper, we study private optimization problems for non-smooth convex functions F(x)=mathbbEi fi(x) on ℝd. We show that modifying the exponential mechanism by adding an ℓ22 regularizer to F(x) and sampling from π(x)propto exp(-k(F(x)+μ|x|22/2)) recovers both the known optimal empirical risk and population loss under (ε,δ)-DP. Furthermore, we show how to implement this mechanism using widetildeO(n min(d, n)) queries to fi(x) for the DP-SCO where n is the number of samples/users and d is the ambient dimension. We also give a (nearly) matching lower bound widetildeOmega(n min(d, n)) on the number of evaluation queries. Our results utilize the following tools that are of independent interest: (1) We prove Gaussian Differential Privacy (GDP) of the exponential mechanism if the loss function is strongly convex and the perturbation is Lipschitz. Our privacy bound is optimal as it includes the privacy of Gaussian mechanism as a special case and is proved using the isoperimetric inequality for strongly log-concave measures. (2) We show how to sample from exp(-F(x)-μ |x|22/2) for G-Lipschitz F with η error in total variation (TV) distance using widetildeO((G2/μ) log2(d/η)) unbiased queries to F(x). This is the first sampler whose query complexity has polylogarithmic dependence on both dimension d and accuracy η.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). Builds on 37 of its 90 references that are in the map. First posted on arXiv 1 Mar 2022.

Builds on

37 of 90 references.

References · 37

  1. 2017Renyi Differential Privacycited by 643
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  4. 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 216
  5. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  6. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  7. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  8. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  9. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  10. 2017Collecting Telemetry Data Privatelycited by 147
  11. 2020The Discrete Gaussian for Differential Privacycited by 134
  12. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
25 more
  1. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  2. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  3. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
  4. 2018Private Selection from Private Candidatescited by 75
  5. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
  6. 2017Efficient Private ERM for Smooth Objectivescited by 61
  7. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 60
  8. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
  9. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  10. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  11. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  12. 2019High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithmcited by 36
  13. 2019Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributionscited by 28
  14. 2019Langevin Monte Carlo without smoothnesscited by 27
  15. 2020Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMCcited by 27
  16. 2021A Proximal Algorithm for Sampling from Non-smooth Potentialscited by 23
  17. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  18. 2017Differentially Private Empirical Risk Minimization with Input Perturbationcited by 19
  19. 2019Benefits and Pitfalls of the Exponential Mechanism with Applications to Hilbert Spaces and Functional PCAcited by 10
  20. 2021Differentially Private Coordinate Descent for Composite Empirical Risk Minimizationcited by 10
  21. 2017Differential Privacy on Finite Computerscited by 8
  22. 2021Sampling from Log-Concave Distributions with Infinity-Distance Guaranteescited by 8
  23. 2018Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densitiescited by 7
  24. 2018Differentially Private Hierarchical Count-of-Counts Histogramscited by 4
  25. 2021The Power of Sampling: Dimension-free Risk Bounds in Private ERMcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 14; 2024: 13; 2025: 9; 2026: 3.

47 papers.

Sort:

By area:

  1. 2022Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Losscited by 60
  2. 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
  3. 2022When Does Differentially Private Learning Not Suffer in High Dimensions?cited by 48
  4. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  5. 2023Why Is Public Pretraining Necessary for Private Model Training?cited by 36
  6. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  7. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  8. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  9. 2022Private Convex Optimization in General Normscited by 13
  10. 2023Faster Differentially Private Convex Optimization via Second-Order Methodscited by 13
  11. 2022Fisher information lower bounds for samplingcited by 12
  12. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
35 more
  1. 2023Query lower bounds for log-concave samplingcited by 12
  2. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 11
  3. 2024Shifted Interpolation for Differential Privacycited by 10
  4. 2025InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacycited by 10
  5. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
  6. 2023On User-Level Private Convex Optimizationcited by 8
  7. 2022Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithmscited by 7
  8. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  9. 2022Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with Differential Privacycited by 6
  10. 2023Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximationcited by 6
  11. 2024The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Modelscited by 6
  12. 2025Gaussian DP for Reporting Differential Privacy Guarantees in Machine Learningcited by 6
  13. 2024Public-data Assisted Private Stochastic Optimization: Power and Limitationscited by 5
  14. 2024Proximal Oracles for Optimization and Samplingcited by 5
  15. 2023Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacycited by 4
  16. 2024Improved Sample Complexity for Private Nonsmooth Nonconvex Optimizationcited by 4
  17. 2022Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimizationcited by 3
  18. 2023Improved Differentially Private and Lazy Online Convex Optimizationcited by 3
  19. 2024Private Online Learning via Lazy Algorithmscited by 3
  20. 2024R'enyi-infinity constrained sampling with d3 membership queriescited by 3
  21. 2025Oracle-based Uniform Sampling from Convex Bodiescited by 3
  22. 2024Differentially Private Bilevel Optimizationcited by 2
  23. 2025Purifying Approximate Differential Privacy with Randomized Post-processingcited by 2
  24. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  25. 2026High-accuracy log-concave sampling with stochastic queriescited by 2
  26. 2022Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walkcited by 1
  27. 2024Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batchescited by 1
  28. 2024On Convex Optimization with Semi-Sensitive Featurescited by 1
  29. 2025Private Geometric Median in Nearly-Linear Timecited by 1
  30. 2025Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Ratescited by 1
  31. 2023Are Normalizing Flows the Key to Unlocking the Exponential Mechanism?cited by 0
  32. 2024Almost linear time differentially private release of synthetic graphscited by 0
  33. 2025On the Inherent Privacy of Zeroth Order Projected Gradient Descentcited by 0
  34. 2026Functional Stochastic Localizationcited by 0
  35. 2026The Geometry of Randomized Smoothing on Feasible Setscited by 0