Research map / Optimization / Nonconvex and smooth optimization
Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates
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 DP convex stochastic optimization with heavy-tailed (p-th moment bounded) gradients and proposes a simple clipping method and an iterative median-style updating method that attains the minimax-optimal risk rate.
Problem
Differentially private stochastic convex optimization when gradients have only bounded p-th order moments; prior methods give suboptimal excess risk because mean estimators have poor high-probability tail behavior, adding a superfluous factor of d in union bounds.
Approach
A clipped-mean estimator whose tail is analyzed carefully (subexponential in all directions) for simple clipping, and an iterative distance/direction-updating mean estimator over k group-wise noisy means whose subgaussian-type tail is amplified by shuffling-based privacy amplification, which together achieve the minimax-optimal DP risk rate.
Key results
- Simple clipping achieves Õ(sqrt(d/n)+sqrt(d)(sqrt(d)/(εn))^{1-1/p}+d^{3/2-1/p}/n^{1-1/p}) excess risk, matching the lower bound only when ε ≤ 1/sqrt(d).
- Iterative updating method achieves Õ(sqrt(d/n)+sqrt(d)(sqrt(d)/(εn))^{1-1/p}) for all ε ≤ 1, matching the minimax lower bound (up to log factors).
- Mean estimator tail improved from subexponential (simple clipping, with ln(6^d/β) factor) to subgaussian-type with d+ln(1/β) dependence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace simple clipping with iterative updating of noisy group-wise means | Stochastic convex optimization under heavy-tailed gradients · Stochastic convex optimization under heavy-tailed gradients | excess risk bound: Simple clipping: +\frac{d^{\frac{3}{2}-\frac{1}{p}}}{n^{1-\frac{1}{p}}}; Iterative updating: no additional term | Helped |
| use simple clipping for privacy-preserving gradient estimation | Stochastic convex optimization under heavy-tailed gradients · Stochastic convex optimization under heavy-tailed gradients | excess risk bound | Helped |
| use iterative updating with permutation-invariant group estimates | Stochastic convex optimization under heavy-tailed gradients · Stochastic convex optimization under heavy-tailed gradients | excess risk bound | Helped |
| use simple clipping when \epsilon\leq 1/\sqrt{d} | Stochastic convex optimization under heavy-tailed gradients · Stochastic convex optimization under heavy-tailed gradients, \epsilon\leq 1/\sqrt{d} | excess risk bound | Helped |
| use simple clipping when \epsilon>1/\sqrt{d} | Stochastic convex optimization under heavy-tailed gradients · Stochastic convex optimization under heavy-tailed gradients, \epsilon>1/\sqrt{d} | excess risk bound: +\frac{d^{\frac{3}{2}-\frac{1}{p}}}{n^{1-\frac{1}{p}}} | Hurt |
Limitations
- Simple clipping method is only minimax optimal for epsilon <= 1/sqrt(d); extra term otherwise.
- Iterative method is more complex to implement and relies on number of groups k and iteration count t_c.
- Analysis is theoretical with no empirical experiments reported.
Experimental setup
Metrics: excess population risk (theoretical bound)
Baselines: Kamath et al. 2022 DP heavy-tailed SCO methods DP-SGD under bounded second moments
Builds on: DP-SGD median-of-means privacy amplification by shuffling concentrated differential privacy
Closest papers by meaning
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.96)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.92)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.91)
- Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · similarity 0.90)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.89)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 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.