Research map / Optimization / Nonconvex and smooth optimization
Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD
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.
Shows that clipped SGD with batch size 1 attains near sub-Gaussian high-probability rates for heavy-tailed stochastic convex optimization, using an iterative refinement of vector martingale concentration built on PAC-Bayes/Donsker-Varadhan and Freedman's inequality.
Problem
Heavy-tailed statistical estimation in the streaming setting (O(d) memory, one sample per step) where prior high-probability guarantees for clipped SGD scale as Tr(Sigma) log(1/delta) rather than near sub-Gaussian rates.
Approach
Iteratively refines a Freedman-type martingale concentration bound using a PAC-Bayes / Donsker-Varadhan argument, sharpening the quadratic variation control so that Clipped-SGD's error scales as Tr(Sigma) + sqrt(Tr(Sigma)||Sigma||) ln(ln T/delta) and extends to smooth convex and Lipschitz convex objectives.
Key results
- For smooth strongly convex objectives, clipped SGD achieves error sqrt((Tr(Sigma)+sqrt(Tr(Sigma)||Sigma||) ln(ln T/delta))/T) with probability 1-delta, improving the prior Tr(Sigma) ln(1/delta) dependence.
- The same near sub-Gaussian guarantees extend to smooth convex and Lipschitz convex objectives, which the authors claim is the first such streaming result.
- Corollaries for streaming heavy-tailed mean estimation, linear regression, logistic regression and LAD regression achieve near sub-Gaussian rates under bounded second (or fourth for covariates) moments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the refined martingale concentration analysis for Clipped SGD | Clipped SGD · Smooth strongly convex SCO with finite gradient-noise second moment | error rate: \sqrt{\frac{\mathsf{Tr}(\Sigma)\ln(\nicefrac{1}{\delta})}{T}} -> \sqrt{\frac{\mathsf{Tr}(\Sigma)+\sqrt{\mathsf{Tr}(\Sigm | Helped |
| Apply Clipped SGD to smooth convex objectives without strong convexity | Clipped SGD · Smooth convex SCO | error rate: \sqrt{\nicefrac{D^2_1(G^2 + \mathsf{Tr}(\Sigma)\log(\tfrac{1}{\delta}))}{T}} | Helped |
| Use the streaming Clipped-SGD estimator | Heavy-tailed mean estimation · Heavy-tailed mean estimation | error rate: \sqrt{\nicefrac{\mathsf{Tr}(\Sigma)\log(\tfrac{1}{\delta})}{N}} -> \sqrt{\frac{\mathsf{Tr}(\Sigma) + \sqrt{\|\Sigma\|_2\ | Helped |
| Use the streaming Clipped-SGD estimator | Heavy-tailed linear regression · Heavy-tailed linear regression | parameter error: \tfrac{\sigma}{\lambda_{\min_{}}(\Sigma)}\sqrt{\tfrac{\|\Sigma\|_2 d \ln(\nicefrac{1}{\delta})}{N + \zeta}} | Helped |
| Use Clipped SGD for heavy-tailed covariates | Streaming logistic regression · Heavy-tailed logistic regression | population risk suboptimality | Helped |
| Use Clipped SGD for heavy-tailed covariates | Streaming LAD regression · Heavy-tailed LAD regression | population risk suboptimality | Helped |
Limitations
- Bounds have sqrt(d) log(1/delta) type dependence rather than the optimal sub-Gaussian d + log(1/delta), with a ln ln T factor in the confidence term.
- Analysis is limited to convex objectives; nonconvex settings such as neural network training are out of scope.
- Step sizes and clipping level depend on problem parameters such as ||Sigma|| and delta, so the method is not parameter-free.
Experimental setup
Metrics: high-probability error bound sample complexity
Baselines: Clipped SGD (prior high-probability analysis) R-Clipped SGD R-Clipped SSTM RobustGD proxBoost restarted-RSMD trimmed mean estimator
Builds on: Clipped SGD Freedman's inequality PAC-Bayes Donsker-Varadhan variational principle
Closest papers by meaning
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.89)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.89)
- Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · similarity 0.89)
- To Clip or not to Clip: the Dynamics of SGD with Gradient Clipping in High-Dimensions (ICLR 2025 · similarity 0.88)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping (ICLR 2025 · similarity 0.88)
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.