Research map / Federated learning and privacy / Differential privacy
Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed CDP-SCO bound for convex losses instead of the prior heavy-tailed SCO method | Heavy-tailed SCO · Convex losses | excess population risk: \tilde O((\frac{d^3}{\varepsilon^2 n})^{1/3}) -> O( \frac{Md}{\sqrt{n}}+\frac{Md^2}{n\sqrt{\rho}}\cdot (\frac{\sqrt{\rho | Helped |
| Use the proposed CDP-SCO bound for strongly convex losses instead of the prior heavy-tailed SCO method | Heavy-tailed SCO · Strongly convex losses | excess population risk: \tilde O(\frac{d^3}{\varepsilon^2 n}) -> \frac{(M+1)^2 (\sc+\sm)^2}{\sc^2\sm} \cdot \tilde O(\frac{d}{ n} + d\cdot (\fra | Helped |
| Set q=1 and take ρ and M as constants | CDP-SCO with CDPNSME · Heavy-tailed SCO, convex | excess population risk: O(\frac{d}{ n^{\frac13}}) -> O(\frac{d} {\sqrt{n}}) | Helped |
| Use the proposed truncation choice instead of the naive per-iteration bias-variance choice (ablation) | CDP-SCO, convex · Heavy-tailed SCO, convex | excess population risk: O((\frac{1}{\sqrt{\rho}n})^{\frac{k-1}{2k-1}}) -> O((\frac{1}{\sqrt{\rho}n})^{\frac{k-1}{k}}) | Helped |
| Use the pure-DP mean-estimation adaptation instead of the concentrated-DP adaptation | Heavy-tailed mean estimation · Heavy-tailed distributions with coordinate-wise bounded k-th moments | ℓ2 estimation error: \tilde O(\sqrt{\frac{d}{n}}+\sqrt{d} (\frac{\sqrt{d}}{\varepsilon n})^{\frac{k-1}{k}}) -> \tilde O(\sqrt{\frac{d}{n}}+\s | Hurt |
Closest papers by meaning
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.96)
- 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.91)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.90)
- Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · similarity 0.89)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (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.