Differentially Private Optimization with Sparse Gradients
This work addresses privacy-preserving optimization for large embedding models, offering incremental advances in efficiency and sparsity-based rates.
The paper tackles differentially private optimization for models with sparse gradients, achieving near-optimal bounds for mean estimation and dimension-independent rates for stochastic convex optimization, with improvements in high-dimensional regimes.
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.