Research map / Optimization / Optimizers
Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
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.
Proposes a coupling-based stationarity diagnostic for constant-stepsize SGD (tracking the distance between two coupled iterates) that triggers stepsize decay, with theory for quadratic and general convex settings.
Problem
Detecting when constant-stepsize SGD iterates reach stationarity so the stepsize can be reduced adaptively, avoiding premature or delayed decay.
Approach
Run two SGD iterates with the same stepsize and mini-batch noise from different initializations; the ratio of their squared distance to the initial distance serves as a stationarity statistic. When it falls below a threshold, decay the stepsize and re-initialize the auxiliary iterate from a b-step backward iterate; optionally shrink the threshold adaptively.
Key results
- On ResNet-18 with CIFAR-10, the coupling-based method reaches about 94% test accuracy, detecting the adjustment point at epoch 145 versus an earlier manual adjustment at epoch 75 that gave trivial gains.
- On logistic and least squares regression (n=1e6), the coupling-based methods match or beat ISGD^{1/2} and distance-based baselines across dimensions 5 to 100, with the ISGD^{1/2} baseline restarting prematurely.
- The coupling-based method is reported to be robust to the stepsize decay factor r, threshold beta, and backward steps b.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use coupling-based stepsize scheduling instead of the tested baselines | SGD on logistic regression · Logistic regression | optimization error | Helped |
| Use coupling-based stepsize scheduling instead of the tested baselines | SGD on least squares regression · Least squares regression | optimization error | Helped |
| Use coupling-based scheduling instead of constant stepsize or manual adjustment | ResNet-18 · CIFAR-10 | test accuracy | Helped |
| Use coupling-based stepsize scheduling instead of the distance-based method and ISGD¹⁄² | SGD on uniformly convex objectives · Uniformly convex objective, d = 200 | optimization error | Helped |
| Use coupling-based stepsize scheduling instead of the distance-based method | Linear stochastic approximation · Markovian data, d=5 | optimization error | Helped |
| Use an adaptive threshold that decreases with the stepsize rather than a static threshold (ablation) | Coupling-based SGD · SGD stationarity detection | stationarity detection accuracy | Helped |
| Vary the stepsize decay factor r (ablation) | Static coupling-based SGD · Logistic regression and least squares regression, d = 100 | optimization error | No clear effect |
| Vary the diagnostic threshold β (ablation) | Static coupling-based SGD · Logistic regression and least squares regression, d = 100 | optimization error | No clear effect |
| Vary the backward-step parameter b for auxiliary-sequence reinitialization (ablation) | Static coupling-based SGD · Logistic regression and least squares regression, d = 100 | optimization error | No clear effect |
| Use a small threshold decay factor η (ablation) | Adaptive coupling-based SGD · Logistic regression and least squares regression, d = 100 | optimization error | Hurt |
| Vary the threshold decay factor η (ablation) | Adaptive coupling-based SGD · Logistic regression and least squares regression, d = 100 | optimization error | Mixed |
Surprising findings
- Pflug's ISGD^{1/2} restarts too early and too often, causing stepsizes to shrink quickly and stall progress.
Limitations
- No principled rule for choosing the threshold beta; results depend on tuning choices.
- Theoretical guarantees for general convex case only; non-convex settings not analyzed.
- Experiments on deep learning are limited to a single ResNet-18 on CIFAR-10.
Experimental setup
Datasets: CIFAR-10 synthetic logistic regression data synthetic least squares data synthetic SVM data synthetic Lasso data synthetic Markovian LSA data
Benchmarks: CIFAR-10
Metrics: test accuracy optimization error robustness to hyperparameters
Baselines: ISGD^{1/2} distance-based restart method averaged SGD with 1/sqrt(k) averaged SGD with C/sqrt(k) SGD with 1/(mu k) ResNet-18 with manual learning rate decay
Builds on: Pflug's diagnostic ISGD Markov chain coupling averaged SGD
Closest papers by meaning
- On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent (ICML 2020 · similarity 0.93)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.89)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.88)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.88)
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.87)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.87)
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.