Efficient private SCO for heavy-tailed data via averaged clipping
Open Access
- 30 September 2024
- journal article
- research article
- Published by Springer Nature in Machine Learning
- Vol. 113 (11-12) , 8487-8532
Abstract
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 H $$\ddot{\text {o}}$$ lder-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.
Keywords
All Related Versions
Funding Information
- Innovation and Technology Commission - Hong Kong (ITS/173/22FP)
- CUHK Direct Grant for Research
- Research Grants Council, University Grants Committee (N_CUHK 415/19, 14300219, 14302920, 14301121)
This publication has 25 references indexed in Scilit:
- Heavy-tailed distributions, correlations, kurtosis and Taylor’s Law of fluctuation scalingProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2020
- Mean Estimation and Regression Under Heavy-Tailed Distributions: A SurveyFoundations of Computational Mathematics, 2019
- Lectures on Convex Optimization2018
- Stochastic Intermediate Gradient Method for Convex Problems with Stochastic Inexact OracleJournal of Optimization Theory and Applications, 2016
- Heavy-Tailed Distributions and Robustness in Economics and Finance2015
- Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds2014
- A variational formulation for frame-based inverse problemsInverse Problems, 2007
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- On Bernstein-type inequalities for martingalesStochastic Processes and their Applications, 2001
- The Nature of Statistical Learning Theory1995