# Private Convex Optimization via Exponential Mechanism

arXiv: https://arxiv.org/abs/2203.00263 · HTML: https://mlsanity.com/paper/2203.00263/

## Key facts

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

## Builds on (most cited first, 30 of 37)

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm](https://mlsanity.com/paper/1908.10859/) (2019)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [Langevin Monte Carlo without smoothness](https://mlsanity.com/paper/1905.13285/) (2019)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [Differentially Private Empirical Risk Minimization with Input Perturbation](https://mlsanity.com/paper/1710.07425/) (2017)

## Built on by (most cited first, 30 of 49)

- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [When Does Differentially Private Learning Not Suffer in High Dimensions?](https://mlsanity.com/paper/2207.00160/) (2022)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Shifted Interpolation for Differential Privacy](https://mlsanity.com/paper/2403.00278/) (2024)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)
- [InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy](https://mlsanity.com/paper/2507.02974/) (2025)
- [On User-Level Private Convex Optimization](https://mlsanity.com/paper/2305.04912/) (2023)
- [Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms](https://mlsanity.com/paper/2206.03792/) (2022)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with Differential Privacy](https://mlsanity.com/paper/2301.00301/) (2022)
- [Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation](https://mlsanity.com/paper/2305.17558/) (2023)
- [Public-data Assisted Private Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2403.03856/) (2024)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models](https://mlsanity.com/paper/2405.17068/) (2024)
- [Gaussian DP for Reporting Differential Privacy Guarantees in Machine Learning](https://mlsanity.com/paper/2503.10945/) (2025)
- [Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy](https://mlsanity.com/paper/2310.14661/) (2023)
- [Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2410.05880/) (2024)
- [Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization](https://mlsanity.com/paper/2204.01585/) (2022)
- [Improved Differentially Private and Lazy Online Convex Optimization](https://mlsanity.com/paper/2312.11534/) (2023)

## 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 η.