mlsanityData to 14 Oct 2026

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

arXiv 2103.15352 ↗First posted 29 Mar 2021cs.LG cs.CR cs.DScited by 21

Not on the map. Why?

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.

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

14 of 35 references.

References · 14

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2017Renyi Differential Privacycited by 650
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  5. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  6. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  7. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  8. 2018Privacy Amplification by Iterationcited by 100
  9. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  10. 2017Efficient Private ERM for Smooth Objectivescited by 61
  11. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  12. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
2 more
  1. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
  2. 2017Differentially Private Empirical Risk Minimization with Input Perturbationcited by 19

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 7; 2023: 3; 2024: 2; 2025: 4.

21 papers.

Sort:

  1. 2022When Does Differentially Private Learning Not Suffer in High Dimensions?cited by 48
  2. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  3. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  4. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  5. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  6. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  7. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  8. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  9. 2022Momentum Aggregation for Private Non-convex ERMcited by 10
  10. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  11. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  12. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
9 more
  1. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  2. 2022Differentially Private Online-to-Batch for Smooth Lossescited by 5
  3. 2021The Power of Sampling: Dimension-free Risk Bounds in Private ERMcited by 3
  4. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  5. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  6. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  7. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  8. 2025Understanding Private Learning From Feature Perspectivecited by 3
  9. 2023Learning across Data Owners with Joint Differential Privacycited by 1