# The Power of Sampling: Dimension-free Risk Bounds in Private ERM

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 28 May 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [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)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces](https://mlsanity.com/paper/2008.06570/) (2020)

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

- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Differentially Private Optimization with Sparse Gradients](https://mlsanity.com/paper/2404.10881/) (2024)

## Abstract (arXiv)

Differentially private empirical risk minimization (DP-ERM) is a fundamental problem in private optimization. While the theory of DP-ERM is well-studied, as large-scale models become prevalent, traditional DP-ERM methods face new challenges, including (1) the prohibitive dependence on the ambient dimension, (2) the highly non-smooth objective functions, (3) costly first-order gradient oracles. Such challenges demand rethinking existing DP-ERM methodologies. In this work, we show that the regularized exponential mechanism combined with existing samplers can address these challenges altogether: under the standard unconstrained domain and low-rank gradients assumptions, our algorithm can achieve rank-dependent risk bounds for non-smooth convex objectives using only zeroth order oracles, which was not accomplished by prior methods. This highlights the power of sampling in differential privacy. We further construct lower bounds, demonstrating that when gradients are full-rank, there is no separation between the constrained and unconstrained settings. Our lower bound is derived from a general black-box reduction from unconstrained to the constrained domain and an improved lower bound in the constrained setting, which might be of independent interest.