Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent

Qiaomin Xie; Xiang Li

REVIEW 3 major objections 4 minor 32 references

Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Two coupled SGD runs give a provable stationarity signal for automatic stepsize control.

desk verdict A genuinely new coupling-based stationarity diagnostic with strong empirical support, but the theory certifies expectations while the algorithm acts on a single realized ratio; worth refereeing with a required revision to close that gap. read the letter →

arxiv 2412.11341 v1 pith:X3R4246L submitted 2024-12-15 cs.LG math.OCstat.ML

Xiang Li , Qiaomin Xie This is my paper · ORCID

classification cs.LGmath.OCstat.ML

keywords stochasticgradientdescentconstantstepsizescheduleMarkovchaincouplingstationaritydiagnosticWassersteindistancestrongconvexitysaturationdetection

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a way to tell, while constant-stepsize SGD is running, when the iterates have stopped improving and have begun to oscillate around the optimum. It runs two SGD sequences that use the same stepsize and the same mini-batches but start from different points, and watches the squared distance between them divided by their initial squared distance. The paper's central claim is that this coupled-distance ratio tracks the transition from transient convergence to stationarity: under smooth, strongly convex objectives, a small ratio certifies that the primary sequence is close, in Wasserstein distance, to its stationary distribution. That certificate turns the ratio into an automatic stepsize rule: when the ratio falls below a threshold, shrink the stepsize and repeat. The authors prove the certificate and demonstrate the resulting schedule on convex problems, ResNet on CIFAR-10, lasso, and Markovian linear stochastic approximation.

What carries the argument

The central object is the coupled difference chain $D_k = \theta_k^{(1)} - \theta_k^{(2)}$ produced by running two SGD recursions with the same stepsize and the same data sequence, so that the noise cancels in the difference update. The diagnostic statistic is the normalized squared length $S_k = \|D_k\|^2/\|D_0\|^2$, a cheap observable that plays the role of a stand-in for the Wasserstein distance to $\pi_\gamma$. The proof machinery is a sandwich: Proposition 1 supplies an exponential upper bound on $\mathrm{W}_2^2(P_\gamma^k(\theta_0,\cdot),\pi_\gamma)$, while a contraction lower bound on $\mathbb{E}\|D_k\|^2/\mathbb{E}\|D_0\|^2$ lets the ratio replace that upper bound through the $\tau$-exponent in Lemma 1.

What would settle it

On a strongly convex logistic-regression problem where the strong-convexity constant can be estimated from the data, run Algorithm 1 and compare its first restart epoch with the epoch at which a Monte Carlo estimate of $\mathbb{E}\|\theta_k-\theta^\star\|^2$ first enters a small band around its stationary value; if the restart fires before that epoch for a range of thresholds $\beta$, then the realized coupling ratio is not faithfully tracking stationarity.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is a theoretical bridge between an observable coupling statistic and the unobservable distance to stationarity. For constant-stepsize SGD satisfying smoothness, strong convexity, zero-mean noise, and expected co-coercivity, define $D_k = \theta_k^{(1)} - \theta_k^{(2)}$ for two chains driven by identical mini-batches. Theorem 1 shows that for $\gamma \in (0, \gamma_0]$ and every $\tau \ge 4L/\mu$, $$\mathrm{W}$_2^{2}$(P_\gamma^k(\$theta_0^{{(1)}}$,\cdot),\pi_\gamma) \le \left(\frac{\mathbb{E}\|D_k\|^2}{\mathbb{E}\|D_0\|^2}\right)^{1/\tau}\mathbb{E}_{\$\theta$\sim\pi_\gamma}\|\$theta_0^{{(1)}}$-\$\theta$\|^2.$$ Hence when the expected squared-ratio $\mathbb{E}\|D_k\|^2/\mathbb{E}\|D_0\|^2$ is small, the primary chain is close to stationarity up to a problem-dependent constant. The same reasoning gives an exact quadratic version in Proposition 3, and Algorithm 1 uses the realized ratio $\|D_k\|^2/\|D_0\|^2$ as the trigger for reducing the stepsize, with Algorithm 2 adding a decaying threshold.

Load-bearing premise

The load-bearing premise is that the ratio computed on a single realized run, after every restart and stepsize reduction, still behaves like the expected ratio in Theorem 1, and that a fixed threshold $\beta$ can be chosen small enough to absorb the unknown constant multiplying the ratio; neither is proved for the multi-restart algorithm.

Editorial extensions

If this is right

If Theorem 1 is right, a constant-stepsize SGD run can be equipped with a provably meaningful stationarity alarm without estimating the strong-convexity or smoothness constants.
The schedule triggered by the alarm matches or beats hand-tuned diminishing-stepsize baselines on logistic and least-squares problems in the paper's experiments, indicating that the diagnostic preserves transient speed while reducing saturation error.
Because the two coupled chains share the same mini-batches, the extra chain is a parallel computational cost rather than a sequential one, so the diagnostic need not increase wall-clock time.
The same ratio-based trigger transfers to linear stochastic approximation with Markovian data, where the transience-stationarity transition is also known to occur, and the paper reports gains there as well.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extension: the theorem controls expected ratios in a single phase with fixed initialization, while the algorithm restarts the auxiliary chain and changes the stepsize repeatedly on one noise realization; proving a total-iteration guarantee for the full schedule would require a piecewise analysis that the paper does not supply.
Extension: the quadratic bound's denominator is the initial difference component along the slowest eigenvector $q_{\max}$; users may want to check that their initial pair excites all directions, since an unlucky initial difference could make the ratio decay at the wrong speed.
Extension: the threshold $\beta$ and the decay exponent $1/\tau$ are entangled with the unknown constant $\mathbb{E}_{\pi_\gamma}\|\theta_0-\theta\|^2$; a data-dependent calibration of $\beta$ from an estimate of the stationary variance is a natural next step.
Extension: the ResNet experiments lie outside the theorem's convex assumptions; a rigorous extension under dissipativity or a Polyak-Łojasiewicz condition would tell whether the diagnostic's apparent success in deep learning is a consequence of the same mechanism or of favorable initialization.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the coupling diagnostic is a genuinely new and simple idea, and the empirical work is broad and mostly careful. But the theory in Theorem 1 does not support the algorithm as it is actually run. That gap is the main thing a referee should push on.

What's new: tracking the ratio of distances between two SGD chains that share the same minibatch noise, and using that ratio as a stationarity signal, is not in the prior work they cite. It is data-efficient, easy to implement, and parallelizes without extra wall-clock time. The experiments cover a reasonable range: logistic, least squares, ResNet-18, SVM, uniformly convex, Lasso, and LSA with Markovian data. The robustness sweeps over r, beta, b, and eta are more thorough than what I usually see, and the comparisons to Pflug-based ISGD and the distance-based method look fair, with tuned baselines.

The soft spot is the connection between theory and algorithm. Theorem 1 is an expectation bound: it says W2^2(P^k, pi) <= (E||D_k||^2 / E||D_0||^2)^(1/tau) * E_pi||theta0 - theta||^2. Algorithm 1, on the other hand, checks one realized value S_k on a single noise realization and, if it dips below beta, irreversibly cuts the stepsize. Nothing in the assumptions or theorem controls the fluctuations of S_k around its expectation. One rare small draw can trigger an early decay, which is exactly the failure mode the paper attributes to Pflug's statistic. The multiplier E_pi||theta0 - theta||^2 and the exponent 1/tau with tau >= 4L/mu mean the bound does not give a computable calibration for beta either. And after a restart, the auxiliary chain is reinitialized from a b-step backward iterate, so the theorem's fixed-initial-pair, fixed-stepsize premise no longer applies. The paper's own conclusion admits there is no principled rule for choosing beta, so this is not a hidden flaw; it is a stated limitation.

None of this kills the idea. The statistic is still a reasonable heuristic, and the empirical evidence suggests it works well across problems. But the abstract's phrase 'tracks the transition theoretically' overstates what is proved. To make the claim solid, the authors would need a concentration or variance bound on the ratio, or at least a repeated-sampling scheme, plus a way to set beta from problem data.

This paper deserves a serious referee. The idea is useful, the experiments are extensive, and the gap between theorem and algorithm is a clear, addressable revision rather than a dead end. I would send it out, with a request for concentration analysis or an explicit reframing of the contribution as heuristic-with-experiments.

Referee Report

3 major / 4 minor

Summary. The paper proposes a coupling-based convergence diagnostic for constant-stepsize SGD. Two SGD iterates share the same stepsize and noise but start from different initializations; the algorithm tracks the ratio of their squared distance to its initial value, and when this ratio falls below a threshold, it decays the stepsize and reinitializes the auxiliary iterate from a b-step backward iterate (Algorithms 1 and 2). The theoretical centerpiece is Theorem 1 (Section 3), which states under smoothness, strong convexity, zero-mean noise, and co-coercivity that the squared Wasserstein-2 distance between the SGD distribution and its stationary distribution is bounded by (E||D_k||^2 / E||D_0||^2)^(1/tau) times an unknown factor E_{theta~pi_gamma}||theta_0 - theta||^2, with tau >= 4L/mu. A quadratic specialization is given in Proposition 3. The paper reports extensive experiments on logistic regression, least squares, ResNet-18 on CIFAR-10, SVM, uniformly convex objectives, Lasso, and linear stochastic approximation with Markovian data, comparing favorably with Pflug-based and distance-based diagnostics.

Significance. If the theoretical guarantee could be connected to the algorithm as run, the coupling statistic would be a simple, data-efficient, parallelizable stationarity diagnostic with a provable relationship to Wasserstein convergence, improving on the distance-based heuristic of Pesme et al. (2020). The empirical study is broad, includes nonconvex deep learning, and is accompanied by released code, which is a strength. However, the central claim that the diagnostic 'tracks the transition from transience to stationarity theoretically' is currently supported only in a much narrower sense than the algorithm uses: the theorem is an expectation statement for a fixed stepsize, fixed initial pair, and one phase, while the algorithms trigger on a single realized ratio and restart both the auxiliary chain and the stepsize. The unknown multiplicative factor and the 1/tau exponent also make the threshold beta uncalibrated. These gaps are load-bearing for the paper's main contribution, so the manuscript needs a substantive revision rather than minor polishing.

major comments (3)

[Section 3, Theorem 1 vs. Algorithm 1, lines 4-7] The theorem bounds the expected ratio E||D_k||^2 / E||D_0||^2, but Algorithm 1 triggers the irreversible step-size reduction on a single realized value S = ||theta(1)_k - theta(2)_k||^2 / ||theta(1)_0 - theta(2)_0||^2. No variance bound, concentration inequality, or repeated-sampling procedure is provided, so a single rare draw of the shared noise can make S small while the expectation ratio is still large. This is precisely the early-decay failure mode the paper attributes to Pflug's statistic, and the present manuscript does not rule it out for the coupling statistic.
[Section 3, Theorem 1 and Proposition 3] Even the expectation bound is not calibrated for threshold selection: the right-hand side contains the unknown factor E_{theta~pi_gamma}||theta_0 - theta||^2 and the exponent 1/tau with tau >= 4L/mu. For ill-conditioned strongly convex problems, tau is large, so a threshold such as beta = 0.95 gives (0.95)^(1/tau) close to 1 and the theorem provides no nontrivial stationarity certificate. Proposition 3 has an additional degeneracy: its denominator is E[(D_0^T q_max)^2], and if the initial difference is orthogonal or near-orthogonal to the slowest eigenvector q_max, the ratio can be small even when the chain is far from stationarity; the algorithm does not check this condition.
[Section 3, Algorithm 1 lines 6-7 and Algorithm 2 lines 6-8] After each trigger the algorithm changes gamma, resets theta(2) to theta(2)_{k-b}, and in Algorithm 2 also decreases beta, while the denominator in S is not reset. Theorem 1 and Proposition 3 are proved for a fixed stepsize, a fixed initial pair, and a single phase. The correctness of the full multi-stage procedure therefore rests on an unstated premise that the realized ratio remains a valid stationarity certificate after every restart. No argument or experiment specifically validates this premise against adversarial or unlucky initializations, and the stated theoretical results do not cover it.

minor comments (4)

[Abstract and Section 3] The phrase 'track the transition from transience stationarity' is missing a 'to'; it should read 'from transience to stationarity'.
[Section 3, Proposition 3] The expectation in the denominator is typeset as E[D_0^T q_max]^2, which is ambiguous; it should be E[(D_0^T q_max)^2] if D_0 is random, and the deterministic case should be discussed separately.
[Algorithm 1, line 4 comment] The inline comment says the distance ratio is approximately rho^k, where rho is the Wasserstein contraction factor from Proposition 1; that approximation is not derived for the ratio of realized norms and should be reworded or justified.
[Figure 2 and Section 4.3] The vertical lines are called 'restarts' in the caption, but the algorithm does not restart the primary sequence; it only reduces the stepsize and reinitializes the auxiliary sequence. The terminology should be consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is an externally based bound relating coupling distance to stationarity, not a fitted or renamed input.

full rationale

Section 3's Theorem 1 is derived, not assumed. The paper imports Proposition 1 from Dieuleveut, Durmus, and Bach (2020), an external W2 contraction bound for constant-stepsize SGD, and combines it with an elementary lower bound on the coupled difference E||D_k||^2 (Equations (6)-(7) and Lemma 1). The diagnostic statistic S = ||theta(1)_k - theta(2)_k||^2 / ||theta(1)_0 - theta(2)_0||^2 is defined independently of the stationarity certificate W2^2(P^k_gamma(theta0, .), pi_gamma); Theorem 1 only asserts an inequality between the two quantities. No parameter is fitted to the target stationarity measure and then renamed a prediction. The main gap — Algorithm 1 triggers on a single realized S_k while Theorem 1 controls only E||D_k||^2, with no concentration bound — is a missing variance/concentration argument, i.e., a correctness or robustness risk, not circularity, since the realized statistic is not defined in terms of the stationarity certificate. The self-citations (Huo et al. 2024; Huo, Chen, and Xie 2023) appear only as background on Markovian LSA transience-stationarity and in the LSA experiment, not as the load-bearing justification for the coupling diagnostic; the central theorem rests on the external Dieuleveut et al. result. Hyperparameters such as beta, r, b, and eta are empirically chosen and tested for robustness, but this post-hoc tuning does not make the theoretical claim definitionally circular. No exhibited equation reduces the conclusion to its input by construction.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the standard convex SGD axioms plus two unstated assumptions: that a single realized ratio behaves like its expectation, and that the restarted multi-stage procedure continues to be governed by the single-phase theorem. These are the main gaps. The method introduces no new physical or mathematical entities; the auxiliary chain is an algorithmic construct.

free parameters (5)

Initial stepsize gamma0 = Problem specific: 1/(2R^2) for least squares, 4/R^2 for logistic regression, 0.01 for ResNet-18
The initial stepsize sets the transient speed and stationary error; the paper tunes it per problem and does not derive it from the diagnostic.
Threshold beta = Varies in robustness scans; 0.95 used for ResNet-18
The threshold determines when a stepsize reduction is triggered. The theory does not specify how to choose beta, and the ResNet value is far from any value that would make the W2 bound tight for ill-conditioned problems.
Stepsize decay factor r = 0.1 for ResNet-18; varied in robustness scans
Controls the new stepsize after each restart; the paper shows robustness but gives no optimal selection rule.
Backward steps b = Varied in robustness scans
The auxiliary chain is reinitialized from the b-step backward iterate; the choice of b affects the reinitialization distance and is chosen by hand.
Threshold decay factor eta = 0.75 recommended in Section B.2
For the adaptive variant, eta reduces the threshold after each restart; smaller eta gives more conservative detection, and the paper recommends a range empirically.

assumptions (6)

domain assumption Assumptions A.1-A.4: L-smoothness, strong convexity with mu > 0, zero-mean i.i.d. noise, and co-coercivity in expectation
Invoked in Theorem 1 and Proposition 1 to guarantee the Markov chain contraction and the lower bound on the coupled distance. These are standard for constant-stepsize SGD analysis.
domain assumption Assumption A.5: quadratic semi-stochastic setting with deterministic noise independent of theta
Used in Proposition 2 and Proposition 3 to obtain the closed-form contraction of the coupled difference.
standard math Proposition 1 (Proposition 2 of Dieuleveut, Durmus, and Bach 2020)
The paper relies on the external result that constant-stepsize SGD converges to a stationary distribution with a Wasserstein contraction rate; this is accepted as prior literature.
standard math Lemma 1 exponential inequality
Elementary inequality used in the proof of Theorem 1 to convert the lower bound on the coupled distance into the W2 bound.
ad hoc to paper Single-trajectory use of the expectation-based ratio
The algorithm thresholds one realized ratio ||D_k||^2/||D_0||^2, while Theorem 1 bounds expectations. No concentration inequality is provided to justify treating the realized value as the expected value.
ad hoc to paper Multi-stage restarts preserve diagnostic validity
The analysis covers one phase with fixed gamma; the actual algorithm repeatedly reduces gamma, changes beta, and reinitializes theta^2, and the paper does not analyze the effect of these restarts on the diagnostic.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent." pith.science (2026). https://pith.science/paper/X3R4246L

@misc{pith2026241211341,
  author       = {Pith},
  title        = {Pith review of: Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X3R4246L}},
  note         = {Machine review of arXiv:2412.11341}
}

read the original abstract

The convergence behavior of Stochastic Gradient Descent (SGD) crucially depends on the stepsize configuration. When using a constant stepsize, the SGD iterates form a Markov chain, enjoying fast convergence during the initial transient phase. However, when reaching stationarity, the iterates oscillate around the optimum without making further progress. In this paper, we study the convergence diagnostics for SGD with constant stepsize, aiming to develop an effective dynamic stepsize scheme. We propose a novel coupling-based convergence diagnostic procedure, which monitors the distance of two coupled SGD iterates for stationarity detection. Our diagnostic statistic is simple and is shown to track the transition from transience stationarity theoretically. We conduct extensive numerical experiments and compare our method against various existing approaches. Our proposed coupling-based stepsize scheme is observed to achieve superior performance across a diverse set of convex and non-convex problems. Moreover, our results demonstrate the robustness of our approach to a wide range of hyperparameters.

Figures

Figures reproduced from arXiv: 2412.11341 by the authors.

**Figure 1.** Evolution of ∥θ (1) k − θ ⋆∥ 2 and ∥θ (2) k − θ ⋆∥ 2 and ∥θ (1) k − θ (2) k ∥ 2 under least squares regression with two different constant stepsizes. Quadratic Setting To answer the above question for our coupling approach, we first consider the case of a quadratic objective function, as stated in the following assumption. Assumption A.5 (Quadratic semi-stochastic setting). There exists a symmetric positive definit… view at source ↗

**Figure 2.** Effectiveness of our coupling-based statistic for stationarity diagnostic. Left: Algorithm 1 with static threshold; Right: [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Logistic regression (left) and Least squares regression (right). The initial stepsize of coupling/distance-based and [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: Robustness results under logistic regression and least squares regression (LSR) with [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

**Figure 5.** Figure 5: ResNet-18 Test Accuracy on CIFAR-10 dataset. [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 6.** Figure 6: Logistic regression (left) and Least squares regression (right) with different dimensions [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]

**Figure 7.** Figure 7: Robustness results under logistic regression and least squares regression (LSR) with [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]

**Figure 8.** Figure 8: Robustness results under least squares regression (LSR) and logistic regression with [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]

**Figure 9.** Figure 9: SVM with dimension d = 20. The initial stepsize of coupling/distance-based and ISGD1/2 is γ0 = 4/R2 . The errors are averaged over 10 replications. Linear stochastic approximation with Markovian data. Our last set of experiments consider the linear stochastic approxima…

**Figure 11.** Figure 11: Lasso regression with dimension d = 100. The initial stepsizes are γ0 = 1/2R2 [PITH_FULL_IMAGE:figures/full_fig_p013_11.png]

**Figure 12.** Figure 12: LSA with Markovian data stream [PITH_FULL_IMAGE:figures/full_fig_p013_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 21 canonical work pages

[1]

, " * write output.state after.block = add.period write newline

ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
[2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
[3]

Bach, F. 2014. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. arXiv:1303.6149

work page Pith review arXiv 2014
[4]

Bach, F.; and Moulines, E. 2013. Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n). Advances in neural information processing systems, 26

work page 2013
[5]

Bottou, L. 2010. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, 177--186. Springer

work page 2010
[6]

Bottou, L. 2012. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade: Second Edition, 421--436. Springer

work page 2012
[7]

Chee, J.; and Toulis, P. 2018. Convergence diagnostics for stochastic gradient descent with constant step size. arXiv:1710.06382

arXiv 2018
[8]

Dieuleveut, A.; Durmus, A.; and Bach, F. 2020. Bridging the gap between constant step size stochastic gradient descent and Markov chains . The Annals of Statistics, 48(3): 1348 -- 1382

work page 2020

Show all 32 references

[9]

G.; and Tweedie, R

Foss, S. G.; and Tweedie, R. L. 1998. Perfect simulation and backward coupling. Communications in Statistics. Stochastic Models, 14(1-2): 187--203

1998
[10]

Hazan, E.; and Kale, S. 2014. Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex Optimization. Journal of Machine Learning Research, 15(71): 2489--2512

2014
[11]

He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 770--778

2016
[12]

Huo, D.; Chen, Y.; and Xie, Q. 2023. Bias and extrapolation in Markovian linear stochastic approximation with constant stepsizes. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 81--82

2023
[13]

Huo, D.; Zhang, Y.; Chen, Y.; and Xie, Q. 2024. The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize. arXiv preprint arXiv:2405.16732

2024 arXiv
[14]

Krizhevsky, A. 2009. Learning Multiple Layers of Features from Tiny Images. Master's thesis, University of Tront

2009
[15]

Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25

2012
[16]

Lacoste-Julien, S.; Schmidt, M.; and Bach, F. 2012. A simpler approach to obtaining an O (1/t) convergence rate for the projected stochastic subgradient method. arXiv preprint arXiv:1212.2002

2012 arXiv
[17]

Lang, H.; Xiao, L.; and Zhang, P. 2019. Using statistics to automate stochastic optimization. Advances in neural information processing systems, 32

2019
[18]

K.; and Meyn, S

Lauand, C. K.; and Meyn, S. 2023. The curse of memory in stochastic approximation. In 2023 62nd IEEE Conference on Decision and Control (CDC), 7803--7809. IEEE

2023
[19]

Merad, I.; and Ga \" ffas, S. 2023. Convergence and concentration properties of constant step-size SGD through Markov chains. arXiv preprint arXiv:2306.11497

2023
[20]

Moulines, E.; and Bach, F. 2011. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24

2011
[21]

Needell, D.; Ward, R.; and Srebro, N. 2014. Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Advances in neural information processing systems, 27

2014
[22]

Pasupathy, R.; Honnappa, H.; and Hunter, S. R. 2019. Open Problem—Adaptive Constant-Step Stochastic Approximation. Stochastic Systems, 9(3): 307--310

2019
[23]

Pesme, S.; Dieuleveut, A.; and Flammarion, N. 2020. On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent. CoRR, abs/2007.00534

2020 arXiv
[24]

Pflug, G. C. 1983. On the determination of the step size in stochastic quasigradient methods

1983
[25]

Rakhlin, A.; Shamir, O.; and Sridharan, K. 2011. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv:1109.5647

2011 arXiv
[26]

Robbins, H.; and Monro, S. 1951. A stochastic approximation method. The annals of mathematical statistics, 400--407

1951
[27]

Shamir, O.; and Zhang, T. 2013. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, 71--79. PMLR

2013
[28]

Sordello, M.; He, H.; and Su, W. 2020. Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic. arXiv:1910.08597

2020 arXiv
[29]

Villani, C. 2009. Optimal transport: old and new, volume 338. Springer

2009
[30]

Wang, X.; Magnússon, S.; and Johansson, M. 2021. On the Convergence of Step Decay Step-Size for Stochastic Optimization. arXiv:2102.09393

2021 arXiv
[31]

Yaida, S. 2018. Fluctuation-dissipation relations for stochastic gradient descent. arXiv:1810.00004

2018 arXiv
[32]

Yu, L.; Balasubramanian, K.; Volgushev, S.; and Erdogdu, M. A. 2021. An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias. Advances in Neural Information Processing Systems, 34: 4234--4248

2021

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

, " * write output.state after.block = add.period write newline

ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

[2] [2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

[3] [3]

Bach, F. 2014. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. arXiv:1303.6149

work page Pith review arXiv 2014

[4] [4]

Bach, F.; and Moulines, E. 2013. Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n). Advances in neural information processing systems, 26

work page 2013

[5] [5]

Bottou, L. 2010. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, 177--186. Springer

work page 2010

[6] [6]

Bottou, L. 2012. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade: Second Edition, 421--436. Springer

work page 2012

[7] [7]

Chee, J.; and Toulis, P. 2018. Convergence diagnostics for stochastic gradient descent with constant step size. arXiv:1710.06382

arXiv 2018

[8] [8]

Dieuleveut, A.; Durmus, A.; and Bach, F. 2020. Bridging the gap between constant step size stochastic gradient descent and Markov chains . The Annals of Statistics, 48(3): 1348 -- 1382

work page 2020