# Private Convex Optimization in General Norms

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 74 references that are in the map.
- First posted on arXiv 18 Jul 2022.

## Builds on (most cited first, 26 of 26)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [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)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [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)
- [Mirrored Langevin Dynamics](https://mlsanity.com/paper/1802.10174/) (2018)
- [Wasserstein Control of Mirror Langevin Monte Carlo](https://mlsanity.com/paper/2002.04363/) (2020)
- [Efficient constrained sampling via the mirror-Langevin algorithm](https://mlsanity.com/paper/2010.16212/) (2020)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [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)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [The Mirror Langevin Algorithm Converges with Vanishing Bias](https://mlsanity.com/paper/2109.12077/) (2021)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations](https://mlsanity.com/paper/1304.2338/) (2013)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing](https://mlsanity.com/paper/1804.01076/) (2018)
- [Iterative Refinement for ℓp-norm Regression](https://mlsanity.com/paper/1901.06764/) (2019)
- [Flows in Almost Linear Time via Adaptive Preconditioning](https://mlsanity.com/paper/1906.10340/) (2019)
- [The Power of Sampling: Dimension-free Risk Bounds in Private ERM](https://mlsanity.com/paper/2105.13637/) (2021)

## Built on by (most cited first, 13 of 13)

- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Adaptive Batch Size for Privately Finding Second-Order Stationary Points](https://mlsanity.com/paper/2410.07502/) (2024)
- [Learning across Data Owners with Joint Differential Privacy](https://mlsanity.com/paper/2305.15723/) (2023)
- [Private Geometric Median in Nearly-Linear Time](https://mlsanity.com/paper/2505.20189/) (2025)
- [On the Inherent Privacy of Zeroth Order Projected Gradient Descent](https://mlsanity.com/paper/2507.05610/) (2025)
- [Functional Stochastic Localization](https://mlsanity.com/paper/2602.03999/) (2026)

## Abstract (arXiv)

We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm |·|. Our algorithms are based on a regularized exponential mechanism which samples from the density propto exp(-k(F+μ r)) where F is the empirical loss and r is a regularizer which is strongly convex with respect to |·|, generalizing a recent work of [Gopi, Lee, Liu '22] to non-Euclidean settings. We show that this mechanism satisfies Gaussian differential privacy and solves both DP-ERM (empirical risk minimization) and DP-SCO (stochastic convex optimization) by using localization tools from convex geometry. Our framework is the first to apply to private convex optimization in general normed spaces and directly recovers non-private SCO rates achieved by mirror descent as the privacy parameter ε → ∞. As applications, for Lipschitz optimization in ℓp norms for all p ∈ (1, 2), we obtain the first optimal privacy-utility tradeoffs; for p = 1, we improve tradeoffs obtained by the recent works [Asi, Feldman, Koren, Talwar '21, Bassily, Guzman, Nandi '21] by at least a logarithmic factor. Our ℓp norm and Schatten-p norm optimization frameworks are complemented with polynomial-time samplers whose query complexity we explicitly bound.