mlsanityData to 14 Oct 2026

Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping

arXiv 2206.13011 ↗First posted 27 Jun 2022cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider stochastic convex optimization for heavy-tailed data with the guarantee of being differentially private (DP). Most prior works on differentially private stochastic convex optimization for heavy-tailed data are either restricted to gradient descent (GD) or performed multi-times clipping on stochastic gradient descent (SGD), which is inefficient for large-scale problems. In this paper, we consider a one-time clipping strategy and provide principled analyses of its bias and private mean estimation. We establish new convergence results and improved complexity bounds for the proposed algorithm called AClipped-dpSGD for constrained and unconstrained convex problems. We also extend our convergent analysis to the strongly convex case and non-smooth case (which works for generalized smooth objectives with Hddotolder-continuous gradients). All the above results are guaranteed with a high probability for heavy-tailed data. Numerical experiments are conducted to justify the theoretical improvement.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 22 of its 45 references that are in the map. First posted on arXiv 27 Jun 2022.

Builds on

22 of 45 references.

References · 22

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  3. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  4. 2017Collecting Telemetry Data Privatelycited by 149
  5. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  6. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  7. 2020Tempered Sigmoid Activations for Deep Learning with Differential Privacycited by 122
  8. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  9. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  10. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  11. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  12. 2017Efficient Private ERM for Smooth Objectivescited by 61
10 more
  1. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 52
  2. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  3. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  4. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  5. 2017Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12cited by 43
  6. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  7. 2014Empirical risk minimization for heavy-tailed lossescited by 37
  8. 2018Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Casecited by 19
  9. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  10. 2018Robust descent using smoothed multiplicative noisecited by 6

Built on by

Not cited yet.