{"id":"e90c0252-5cdb-4666-9a00-f1b53b5544da","arxiv_id":"2412.11341","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A dynamic stepsize scheme for SGD that detects stationarity via the distance between two coupled SGD iterations sharing the same minibatch noise.","lead":"This paper proposes a stationarity detector for constant-stepsize stochastic gradient descent: run two copies of the algorithm with the same random data and watch their distance shrink. When the pair gets close, the learning rate is cut automatically, and the authors test this on logistic regression, least squares, and ResNet-18.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 certifies only the expected coupling ratio; Algorithm 1 triggers on a single realized ratio with no concentration bound, so a rare small D_k can cause premature, irreversible stepsize decay.","rationale":"Read in good faith, the paper's theoretical contribution is a genuine expectation-level bound: Theorem 1's proof, though terse and with typos (e.g., 'f1' in Section 3, and gamma^2 mu vs gamma^2 mu^2 in Lemma 1), does establish W2^2 <= (E-ratio)^(1/tau) * E_{pi_gamma}||theta0 - theta||^2 under strong convexity. The quadratic Proposition 2 is exact when noise is additive and shared between the two chains. What is not established is the paper's operational claim that the coupling ratio 'tracks' saturation in the algorithm: Algorithm 1 consumes a single realization of a ratio whose expectation is bounded, and it does so after restarts that change the coupling. This gap is load-bearing because the whole method is a trigger: a false positive cannot be undone, and the experimental comparisons would be explained by early/late decay luck rather than by the diagnostic. This is a correctness-risk concern, not an ad hominem or a disagreement with consensus. The reader's weakest_assumption pointed at restarts and the unknown threshold factor; my concern sharpens the restart issue into the expectation-versus-realization gap and identifies the missing concentration step, so agreement is partial. A conditional verdict remains appropriate: the empirical evidence is substantial and the expectation theory is plausibly the right first step, but the authors should either prove concentration, average the statistic over independent couplings, or explicitly restrict the theoretical claim to the expectation diagnostic.","tokens_in":15272,"tokens_out":12739,"duration_ms":110875,"concrete_test":"Use a smooth strongly convex logistic-regression instance with known mu and L and d=10; fix theta(1)_0 and theta(2)_0. Compute the exact or high-accuracy Monte Carlo expectation E||D_k||^2/E||D_0||^2, and set beta from Theorem 1 for a target W2^2 <= epsilon * E_{pi_gamma}||theta0 - theta||^2 with tau = 4L/mu. Then run Algorithm 1 on 1000 independent noise realizations and record the first k where S_k < beta. Count false positives: crossings that occur while the expectation ratio is still above beta (so the theorem's certificate has not fired) and before the chain's empirical W2 distance to pi_gamma is below the target. If this rate is materially above zero, the single-realization trigger is not justified by Theorem 1; averaging S over a mini-batch of independent couplings should be added and retested.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central certificate is Theorem 1: W2^2(P^k_gamma(theta0,·), pi_gamma) <= (E||D_k||^2/E||D_0||^2)^(1/tau) * E_{theta~pi_gamma}||theta0 - theta||^2. This is an expectation statement. But Algorithm 1 (lines 4-7) uses one realized value S_k = ||theta(1)_k - theta(2)_k||^2 / ||theta(1)_0 - theta(2)_0||^2 on a single noise realization and decays gamma forever if S_k < beta. Nothing in Assumptions A.1-A.4 or Theorem 1 controls the fluctuations of S_k around its expectation: no variance bound, no concentration inequality, and no repeated sampling. A single rare draw of the shared noise can make S_k small while the expectation ratio is still large; the algorithm then irreversibly reduces the stepsize, reproducing the early-decay failure mode the paper attributes to Pflug's statistic. In addition, even the expectation bound contains the unknown factor E_{theta~pi_gamma}||theta0 - theta||^2 and exponent 1/tau with tau >= 4L/mu, so Theorem 1 provides no computable calibration for beta. After a restart, theta(2) is reinitialized from theta(2)_{k-b}, the denominator is not reset, and the chain parameters change, so the theorem's fixed-initial-pair, fixed-stepsize premise no longer applies.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15603,"tokens_out":6184,"duration_ms":53548,"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":[{"comment":"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":"Section 3, Theorem 1 vs. Algorithm 1, lines 4-7"},{"comment":"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":"Section 3, Theorem 1 and Proposition 3"},{"comment":"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.","section":"Section 3, Algorithm 1 lines 6-7 and Algorithm 2 lines 6-8"}],"minor_comments":[{"comment":"The phrase 'track the transition from transience stationarity' is missing a 'to'; it should read 'from transience to stationarity'.","section":"Abstract and Section 3"},{"comment":"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.","section":"Section 3, Proposition 3"},{"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.","section":"Algorithm 1, line 4 comment"},{"comment":"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.","section":"Figure 2 and Section 4.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for an applied ML venue, and the coupling idea is attractive. My main concern is that the gap between the theorem and the implemented algorithm is not a presentation issue but a correctness issue for the central claim. The authors may be able to fix it by either (a) adding concentration bounds and a multi-stage analysis, or (b) substantially weakening the theoretical claim and presenting the method as a heuristic with strong empirical support. I would also encourage the authors to check whether the claimed robustness to threshold beta is consistent with the uncalibrated factor in Theorem 1; a small experiment varying the condition number L/mu would be informative."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nNone 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.\n\nThis 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.","headline":"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.","tokens_in":16101,"tokens_out":2570,"would_cite":true,"duration_ms":21749,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Two coupled SGD runs give a provable stationarity signal for automatic stepsize control.","keywords":["stochastic gradient descent","constant stepsize","stepsize schedule","Markov chain coupling","stationarity diagnostic","Wasserstein distance","strong convexity","saturation detection"],"falsifier":"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.","tokens_in":15056,"feed_emoji":"📉","tokens_out":13556,"duration_ms":110129,"temperature":0.7,"pith_summary":"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.","feed_headline":"Coupling two SGD runs tells you when to cut the stepsize","feed_subtitle":"Run a second SGD chain on the same data; when the pair's gap collapses, stationarity is reached and the stepsize drops.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Wasserstein convergence bound for constant-stepsize SGD (Proposition 1) and the stationary-bias expansion that Theorem 1 builds on.","marker":"Dieuleveut, Durmus, and Bach 2020"},{"why":"Provides the classical bias-variance decomposition of constant-stepsize SGD that motivates the transience-stationarity picture.","marker":"Needell, Ward, and Srebro 2014"},{"why":"Implements the Pflug-statistic ISGD 1/2 baseline whose premature restarts motivate the new diagnostic.","marker":"Chee and Toulis 2018"},{"why":"Gives a fluctuation-dissipation diagnostic baseline that the paper compares against and whose variance motivates the coupling alternative.","marker":"Yaida 2018"},{"why":"Supplies the distance-to-initialization diagnostic baseline and the uniformly-convex experiments used as comparisons.","marker":"Pesme, Dieuleveut, and Flammarion 2020"},{"why":"Provides the gradient mini-batch saturation test that the paper cites as over-conservative, framing the need for a faster diagnostic.","marker":"Lang, Xiao, and Zhang 2019"}],"fun_headline_variants":["Watch a second SGD chain to know when to shrink stepsize","SGD stepsize: when twin runs meet, cut it down","Stationarity detector for SGD: pair of runs reveals when to adapt","Twin SGD runs show when learning rate should drop"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Watch a second SGD chain to know when to shrink stepsize","SGD stepsize: when twin runs meet, cut it down","Stationarity detector for SGD: pair of runs reveals when to adapt","Twin SGD runs show when learning rate should drop"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000512,"raw_usage":{"total_tokens":2522,"prompt_tokens":1007,"completion_tokens":1515,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":623,"completion_tokens_details":{"reasoning_tokens":1444}},"tokens_in":623,"tokens_out":1515,"duration_ms":9371,"temperature":1.0,"reasoning_tokens":1444,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:03:09.676673+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Wasserstein convergence bound for constant-stepsize SGD (Proposition 1) and the stationary-bias expansion that Theorem 1 builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the classical bias-variance decomposition of constant-stepsize SGD that motivates the transience-stationarity picture."},{"cited_title":"On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descent","cited_arxiv_id":"2007.00534","evidence_quote":"Supplies the distance-to-initialization diagnostic baseline and the uniformly-convex experiments used as comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the gradient mini-batch saturation test that the paper cites as over-conservative, framing the need for a faster diagnostic."}],"review_version":1}