Research map / Federated learning and privacy / Differential privacy
Differentially Private Optimization with Sparse Gradients
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies differentially private optimization when individual per-example gradients are sparse, giving near-optimal sparse mean estimation bounds and DP-SCO/ERM rates that are nearly dimension-independent for pure and approximate DP.
Problem
DP stochastic optimization and mean estimation where each individual gradient has at most s nonzero entries (as in large embedding models), whose theoretical limits were previously unclear.
Approach
Exploits individual gradient sparsity via sparse-vector projection mechanisms with convex relaxations (l1 ball), block-diagonal lower-bound bootstrapping, and a randomized-batch bias-reduced gradient oracle combined with randomly-stopped SGD under a privacy-budget stopping time.
Key results
- Pure-DP sparse mean estimation upper bound sqrt(s d)/(eps n) for large datasets, improving on dense d/(eps n), with matching lower bound Omega(s log(d/s)/(n eps)) via block-diagonal bootstrapping.
- Approximate-DP convex SCO excess risk of order (s ln(d) ln(1/delta))^{1/4}/sqrt(eps n), nearly dimension-independent and nearly optimal.
- Pure-DP algorithms have an exponent gap of 1/6 relative to the mean estimation lower bound, but attain the first nearly dimension-independent rates for pure-DP SCO with sparse gradients.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use individual gradient sparsity rather than the non-sparse setting | DP convex ERM · Convex ERM, approximate (ε,δ)-DP | excess risk: ${\cal R}_{\varepsilon,\delta} \to \frac{(s \ln(d)\ln(1/\delta))^{1/4}}{\sqrt{\varepsilon n}}\wedge {\cal R}_{\varepsilo | Helped |
| Use individual gradient sparsity rather than the non-sparse setting | DP stochastic convex optimization · Stochastic convex optimization, approximate (ε,δ)-DP | excess risk: ${\cal R}_{\varepsilon,\delta}+\frac{1}{\sqrt n} \to \frac{(s\ln(d)\ln(1/\delta))^{1/4}}{\sqrt{\varepsilon n}}\wedge{\ca | Helped |
| Use individual gradient sparsity rather than the non-sparse setting | DP convex ERM · Convex ERM, pure ε-DP | excess risk: ${\cal R}_{\varepsilon} \to \Big( \frac{s\ln(d)}{\varepsilon n} \Big)^{1/3}\wedge {\cal R}_{\varepsilon}$ | Helped |
| Use individual gradient sparsity rather than the non-sparse setting | DP stochastic convex optimization · Stochastic convex optimization, pure ε-DP | excess risk: ${\cal R}_{\varepsilon}+\frac{1}{\sqrt n} \to \Big(\frac{s\ln(d)}{\varepsilon n}\Big)^{1/3}\wedge{\cal R}_{\varepsilon}+ | Helped |
| Use individual gradient sparsity | Approximate-DP empirical gradient norm estimation · Empirical gradient norm | gradient norm: ${\cal R}_{\varepsilon,\delta}^{2/3} \to \frac{(s\ln(d/s)\ln^3(1/\delta))^{1/8}}{(\varepsilon n)^{1/4}}\wedge \big({\cal | Helped |
| Use compressed-sensing ℓ1 recovery instead of the projection mechanism | Approximate-DP sparse mean estimation · Sparse mean estimation | ℓ2 error: log(d) -> log(d/s) | Helped |
| Use the bias-reduced estimator with randomly selected batch sizes | Sparse-gradient SGD · Nonconvex empirical risk minimization | squared gradient norm | Helped |
| Use the full batch instead of random batch sizes | Sparse-gradient SGD · DP empirical risk minimization | excess risk | Hurt |
| Use multiple independent SGD runs and private model selection | Bias-reduced sparse SGD · Convex and nonconvex ERM | success probability: from $1/2$ success probability to $1-\beta$ | Helped |
Surprising findings
- Pure-DP algorithms for sparse SCO do not match the mean estimation lower bound exactly (exponent gap of 1/6).
Limitations
- Mean estimation algorithms require prior knowledge of sparsity parameter s.
- Approximate-DP lower bounds have a ln(d/s)^{1/4} gap in the high-dimensional regime.
- Nonconvex stationarity rate optimality is not established.
Experimental setup
Metrics: l2 estimation error excess empirical/population risk expected squared gradient norm sample complexity rates
Baselines: dense DP-SGD / projection mechanism rates Zhou et al. sparse DP-ERM under partitioning sparsity
Builds on: projection mechanism Blanchet-Glynn bias reduction fully adaptive composition of DP compressed sensing approximate Caratheodory theorem
Closest papers by meaning
- Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · similarity 0.91)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.91)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.90)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.90)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.