Research map / Optimization / Nonconvex and smooth optimization
High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails
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.
Extends the online-to-non-convex framework with gradient clipping and a sampling-based validation step to find (δ,ϵ)-stationary points of non-smooth non-convex objectives with heavy-tailed stochastic gradients, with high-probability guarantees.
Problem
Finding (δ,ϵ)-stationary points of non-smooth non-convex stochastic objectives when gradients have only finite p-th moments (heavy tails, p in (1,2]), with high-probability rather than in-expectation guarantees.
Approach
Incorporates gradient clipping into the online-to-non-convex framework so OGD updates use clipped stochastic gradients, giving high-probability control of shifting regret, and adds a clipped-gradient validation procedure to select an actual (δ,ϵ)-stationary candidate.
Key results
- Algorithm complexity Õ(ϵ^{-(2p-1)/(p-1)} δ^{-1}) gradient queries for (δ,ϵ)-stationary point with high probability; reduces to Õ(ϵ^{-3}δ^{-1}) when p=2, improving the prior Õ(ϵ^{-4}δ^{-1}) high-probability bound.
- For smooth objectives, finds ϵ-stationary point with Õ(ϵ^{-(3p-2)/(p-1)}) queries, matching the Ω(ϵ^{-(3p-2)/(p-1)}) lower bound up to log factors.
- On CIFAR-10 with injected heavy-tailed gradient noise, CGA outperforms SINGD and ONCCA in training and testing accuracy while SGD fails to converge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply gradient clipping to stochastic gradients in candidate generation | CGA · CIFAR10 training set | accuracy | Helped |
| apply gradient clipping to stochastic gradients in candidate generation | CGA · CIFAR10 testing set | accuracy | Helped |
| use SGD with momentum instead of SINGD, ONCCA, or CGA | ResNet18 on CIFAR10 with manually added heavy-tailed gradient noise · CIFAR10 | accuracy | Hurt |
Limitations
- Algorithm requires knowledge of problem parameters σ_p and G to set the clipping parameter.
- Preliminary experiment is small-scale and uses synthetic heavy-tailed noise added to gradients.
- Guarantees hold only for differentiable objectives (non-differentiable case via randomized smoothing).
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: training accuracy testing accuracy query complexity (theoretical)
Baselines: SGD with momentum SINGD ONCCA Zhang et al. 2020c high-probability method Tian et al. 2022 method
Builds on: online-to-non-convex conversion clipped SGD SINGD Zhang et al. (2020) heavy-tailed smooth non-convex analysis
Closest papers by meaning
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.90)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.90)
- Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping (ICLR 2025 · similarity 0.89)
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise (ICML 2024 · similarity 0.89)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.89)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · 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.