# Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 29 Mar 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [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)
- [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)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [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)
- [Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry](https://mlsanity.com/paper/1411.5417/) (2014)
- [Differentially Private Empirical Risk Minimization with Input Perturbation](https://mlsanity.com/paper/1710.07425/) (2017)

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

- [When Does Differentially Private Learning Not Suffer in High Dimensions?](https://mlsanity.com/paper/2207.00160/) (2022)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [Momentum Aggregation for Private Non-convex ERM](https://mlsanity.com/paper/2210.06328/) (2022)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022)
- [Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Losses](https://mlsanity.com/paper/2407.09690/) (2024)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [Differentially Private Online-to-Batch for Smooth Losses](https://mlsanity.com/paper/2210.06593/) (2022)
- [The Power of Sampling: Dimension-free Risk Bounds in Private ERM](https://mlsanity.com/paper/2105.13637/) (2021)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)
- [Nearly Optimal Differentially Private ReLU Regression](https://mlsanity.com/paper/2503.06009/) (2025)
- [An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise](https://mlsanity.com/paper/2508.10879/) (2025)
- [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025)
- [Understanding Private Learning From Feature Perspective](https://mlsanity.com/paper/2511.18006/) (2025)
- [Learning across Data Owners with Joint Differential Privacy](https://mlsanity.com/paper/2305.15723/) (2023)

## Abstract (arXiv)

We study the differentially private Empirical Risk Minimization (ERM) and Stochastic Convex Optimization (SCO) problems for non-smooth convex functions. We get a (nearly) optimal bound on the excess empirical risk and excess population loss with subquadratic gradient complexity. More precisely, our differentially private algorithm requires O(fracN3/2d1/8+ fracN2d) gradient queries for optimal excess empirical risk, which is achieved with the help of subsampling and smoothing the function via convolution. This is the first subquadratic algorithm for the non-smooth case when d is super constant. As a direct application, using the iterative localization approach of Feldman et al. citefkt20, we achieve the optimal excess population loss for stochastic convex optimization problem, with O(minN5/4d1/8,frac N3/2d1/8) gradient queries. Our work makes progress towards resolving a question raised by Bassily et al. citebfgt20, giving first algorithms for private ERM and SCO with subquadratic steps. We note that independently Asi et al. citeafkt21 gave other algorithms for private ERM and SCO with subquadratic steps.