# Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2014.

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)
- [DPlis: Boosting Utility of Differentially Private Deep Learning via Randomized Smoothing](https://mlsanity.com/paper/2103.01496/) (2021)
- [Momentum Aggregation for Private Non-convex ERM](https://mlsanity.com/paper/2210.06328/) (2022)
- [Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks](https://mlsanity.com/paper/2310.20579/) (2023)
- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [Private Zeroth-Order Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2406.19579/) (2024)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Stochastic and Private Nonconvex Outlier-Robust PCA](https://mlsanity.com/paper/2203.09276/) (2022)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023)
- [Nearly Optimal Differentially Private ReLU Regression](https://mlsanity.com/paper/2503.06009/) (2025)
- [Differentially Private Optimization with Sparse Gradients](https://mlsanity.com/paper/2404.10881/) (2024)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [Purifying Approximate Differential Privacy with Randomized Post-processing](https://mlsanity.com/paper/2503.21071/) (2025)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Rethinking Benchmarks for Differentially Private Image Classification](https://mlsanity.com/paper/2601.17189/) (2026)

## Abstract (arXiv)

Empirical Risk Minimization (ERM) is a standard technique in machine learning, where a model is selected by minimizing a loss function over constraint set. When the training dataset consists of private information, it is natural to use a differentially private ERM algorithm, and this problem has been the subject of a long line of work started with Chaudhuri and Monteleoni 2008. A private ERM algorithm outputs an approximate minimizer of the loss function and its error can be measured as the difference from the optimal value of the loss function. When the constraint set is arbitrary, the required error bounds are fairly well understood citeBassilyST14. In this work, we show that the geometric properties of the constraint set can be used to derive significantly better results. Specifically, we show that a differentially private version of Mirror Descent leads to error bounds of the form tildeO(GC/n) for a lipschitz loss function, improving on the tildeO(√p/n) bounds in Bassily, Smith and Thakurta 2014. Here p is the dimensionality of the problem, n is the number of data points in the training set, and GC denotes the Gaussian width of the constraint set that we optimize over. We show similar improvements for strongly convex functions, and for smooth functions. In addition, we show that when the loss function is Lipschitz with respect to the ℓ1 norm and C is ℓ1-bounded, a differentially private version of the Frank-Wolfe algorithm gives error bounds of the form tildeO(n-2/3). This captures the important and common case of sparse linear regression (LASSO), when the data xi satisfies |xi|∞ ≤ 1 and we optimize over the ℓ1 ball. We show new lower bounds for this setting, that together with known bounds, imply that all our upper bounds are tight.