Differentially Private Optimization with Sparse Gradients

2024/04/16 by Ghazi, Badih, Guzmán, Cristóbal, Kamath, Pritish +2
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2404.10881

Abstract

Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients; the former represents the first nearly dimension-independent rates for this problem. Finally, we study the approximation of stationary points for the empirical loss in approximate-DP optimization and obtain rates that depend on sparsity instead of dimension, modulo polylogarithmic factors.

Related

• Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds
• User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data