Research map / Optimization / Nonconvex and smooth optimization
Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
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.
Gives reduction-based differentially private SCO algorithms for heavy-tailed (k-th moment bounded) gradients that achieve near-optimal excess loss via population-level localization, plus optimal known-Lipschitz and linear-time smooth variants.
Problem
Differentially private stochastic convex optimization when per-sample gradient Lipschitz constants are heavy-tailed (only k-th moments bounded) rather than uniformly bounded.
Approach
A population-level localization framework using clipped DP-SGD subroutines that only need constant-success bias bounds (via Markov), boosted by geometric aggregation; plus a reduction that truncates samples with large Lipschitz overestimates to dummy functions to reuse optimal uniform-Lipschitz DP-SCO algorithms.
Key results
- Achieves excess loss G_2 D/sqrt(n) + G_k D (sqrt(d) log(1/delta)/(n sqrt(rho)))^{1-1/k} under rho-CDP with high probability, matching the lower bound up to polylog(1/delta) factors.
- Known-Lipschitz reduction attains the optimal heavy-tailed rate without extra log factors by replacing samples with large Lipschitz overestimates by dummy functions.
- Smooth and GLM variants give linear-time algorithms with near-optimal rates under moderate smoothness conditions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use population-level localization with geometric aggregation of clipped-DP-SGD subproblem outputs | Heavy-tailed DP-SCO · Heavy-tailed DP-SCO | excess population loss: G_2 D \cdot \sqrt{\frac{\log(\frac{1}{\delta})}{n}} + G_k D\cdot\Par{\frac{\sqrt{d}\log(\frac{1}{\delta})}{n\sqrt \rho}} | Helped |
| Assume each sample function is strongly convex and use localization | Heavy-tailed DP-SCO · Strongly convex heavy-tailed DP-SCO | excess population loss: \Csco\Par{\frac{G_k^2}{\mu}\cdot\Par{\frac{d\log^{3}\Par{\frac{1}{\delta}}}{n^2\rho}}^{1 - \frac 1 k} + \frac{G_2^2}{\mu | Helped |
| Use known per-sample Lipschitz overestimates to truncate samples and reduce to uniformly Lipschitz DP-SCO | Known-Lipschitz heavy-tailed DP-SCO · Known-Lipschitz heavy-tailed DP-SCO | expected excess population loss: \Err(\alg) + \frac{G_k^k D}{(k - 1)C^{k - 1}} | Helped |
Surprising findings
- Clipping can make a contractive smooth gradient step non-contractive in general, so an SVT-based clipping count is needed for privacy in the smooth case.
Limitations
- Main result has polylog(1/delta) overhead and holds only with high probability via sample splitting and aggregation.
- Smooth-case results require conditions on smoothness beta relative to n, d, and epsilon.
Experimental setup
Metrics: excess population loss gradient query complexity
Baselines: Lipschitz DP-SCO algorithms (uniform Lipschitz) clipped DP-SGD heavy-tailed DP-SCO (suboptimal rate with 2k-th moment)
Builds on: clipped DP-SGD localization for DP-SCO geometric aggregation sparse vector technique
Closest papers by meaning
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.96)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.91)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.90)
- Safe Online Convex Optimization with Heavy-Tailed Observation Noises (AAAI 2025 · similarity 0.90)
- Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.90)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.90)
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.