Research map / Optimization / Nonconvex and smooth optimization
Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions
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 clipped SGD (and clipped/implicit adaptive SGD variants) with double sampling achieves high-probability optimality-gap rates on convex stochastic (L0,L1)-smooth functions without exponential dependence on L1 R0, and tests the variants empirically on quartic linear regression.
Problem
Convergence of stochastic gradient descent with clipping on convex (L0,L1)-smooth functions with light-tailed noise, where prior analyses covered only the deterministic regime or had exponential dependence on L1 R0.
Approach
Clipped SGD with double sampling (one sample sets the clipping/step size, an independent sample gives the direction) plus a martingale concentration argument and a return rule averaging only unclipped iterates; the L1 dependence enters only as an additive term, and L1 can be replaced by a conservative surrogate T^{1/2}/R0.
Key results
- Clipped SGD achieves optimality gap O(log(T/δ)(L0 R0^2 + σ R0 sqrt(T))/T) w.h.p. for T ≳ log(T/δ) L1^2 R0^2, with L1 entering only as an additive term.
- Stochastic gradient complexity bound Õ(L0 R^2/ε + σ^2 R0^2/ε^2 + (L1 R0)^2), matching fixed-step SGD up to log factors plus an additive L1 term.
- Empirically, double sampling showed no advantage over single sampling in the reported experiments, and averaging over clipped-free iterates T2 gave slightly better sub-optimality than averaging all iterates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use standard, implicit, or adaptive clipping instead of the other clipping methods | Clipped SGD variants · California Housing, Parkinsons Telemonitoring, and synthetic experiments | optimality gap | No clear effect |
| Add standard clipping | SGD · California Housing, Parkinsons Telemonitoring, and synthetic experiments | sub-optimality | Hurt |
| Add adaptive clipping | Adaptive SGD · California Housing, Parkinsons Telemonitoring, and synthetic experiments | sub-optimality | Helped |
| Use single sampling instead of double sampling (ablation) | Standard clipping · California Housing, Parkinsons Telemonitoring, and synthetic experiments | sub-optimality | Helped |
| Average iterates from the unclipped set T2 instead of averaging all iterates (ablation) | Standard clipping · California Housing, Parkinsons Telemonitoring, and synthetic experiments | sub-optimality | Helped |
Surprising findings
- Double sampling, used for the proof, showed no empirical advantage over single sampling; single sampling performed better per iteration.
- Clipped SGD performed slightly worse than unclipped SGD in the experiments, while clipping helped adaptive SGD more substantially.
Limitations
- Analysis requires convexity and light-tailed (sub-Gaussian) noise; the bounded-noise result is lifted by reduction.
- Double sampling is used for proofs but is not supported empirically and doubles gradient queries per iteration.
- Requires a bound R on the distance to the optimum for the adaptive variant.
Experimental setup
Datasets: California Housing Parkinsons Telemonitoring
Benchmarks: California Housing Parkinsons Telemonitoring
Metrics: optimality gap (sub-optimality) vs number of stochastic grad
Baselines: SGD adaptive SGD single-sample clipped SGD average of all iterates
Builds on: (L0,L1)-smoothness adaptive SGD normalized SGD with double sampling sub-Gaussian to bounded noise reduction
Closest papers by meaning
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.93)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.90)
- Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Stochastic Bias and Remedies (ICML 2025 · similarity 0.90)
- On Convergence of Incremental Gradient for Non-convex Smooth Functions (ICML 2024 · similarity 0.89)
- Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization (NeurIPS 2025 · similarity 0.89)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · 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.