{"id":"1ef75393-9b18-4fbc-a595-22c670334775","arxiv_id":"2509.14969","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new adaptive step-size for SGD, built on the AdaGD Lyapunov function, provably converges in several convex settings without tuned hyper-parameters.","lead":"This paper introduces a learning-rate rule for stochastic gradient descent that adapts to the local shape of the objective using two gradient evaluations per step, with no tuned learning rate. On six convex test problems it matches or beats tuned baselines while staying insensitive to its starting value.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The square-summability proof for Cases 2 and 3 covers only single-sample mini-batches; the 'without loss of generality' reduction fails for mini-batch averages, so the convergence guarantee does not cover Algorithm 1 as run in the experiments.","rationale":"The central construction is a genuine parameter-free step-size rule, and the Lyapunov analysis in Section 2 is coherent: conditions (12) and (14) yield the stochastic analogue (15), and the strongly convex rate proof in Appendix B.2 is internally consistent apart from the λ₁ formula typo flagged by the reader. The load-bearing point is the bridge from the Lyapunov inequality to almost-sure convergence: Theorem 3.2 requires ∑λ_k² < ∞, and the only proof of that for Cases 2 and 3 is in Appendix A.2-A.3, where the mini-batch is reduced to a single sample by a 'without loss of generality' claim. That claim is not a routine extension: for a mini-batch S the curvature ratio is bounded by the inverse of the smallest eigenvalue of the averaged Gram matrix A_S, which is not the single-sample constant and may be arbitrarily large for nearly collinear data. Since the algorithm and experiments use mini-batches of size 32/309, the theorem as written does not cover the implemented method in these cases. This does not make the method wrong: for Case-1 the strong-convexity argument is batch-size agnostic, and for Cases 2-3 a modified bound with min_S λ_min(A_S) would likely restore the result. But the missing proof is a real correctness gap in the stated claims. The reader's weakest_assumption identifies this same issue, so I agree. The verdict should remain CONDITIONAL, with the mini-batch square-summability proof as the primary condition.","tokens_in":21637,"tokens_out":27194,"duration_ms":227569,"concrete_test":"Compute the Case-2 curvature ratio for a mini-batch S of size m>1: for ∇f_S(x) = A_S x - b_S with A_S = (1/m)∑_{i∈S} w_i w_i^T, the quantity ||x_k - x_{k-1}|| / ||∇f_S(x_k) - ∇f_S(x_{k-1})|| equals ||r|| / ||A_S r|| with r = ∇f_S(x_{k-1}). For the two-point dataset w_1 = (1,0), w_2 = (1,ε), this ratio is O(1/ε²) as ε→0, whereas the single-sample bound is 1/||w_i||² = O(1). If the authors cannot supply a mini-batch analogue of equation (20) with a uniform bound, the 'without loss of generality' claim is unsupported and the proof does not cover Algorithm 1 as run.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix A.2-A.3 proves ∑λ_k² < ∞ for Cases 2 and 3 only under the claim that, 'without loss of generality', mini-batches are single-valued. That reduction is not valid. For a mini-batch S, ∇f_S(x) = A_S x - b_S with A_S = (1/|S|)∑_{i∈S} w_i w_i^T, and the curvature ratio controlling λ_k becomes ||r|| / ||A_S r||, where r = ∇f_S(x_{k-1}). Since r lies in range(A_S), the best uniform bound is 1/λ_min(A_S), not the rank-one constant 1/||w_ξ||² used in the single-sample proof. For nearly collinear batch vectors, λ_min(A_S) can be arbitrarily small, so the ratio can be much larger than the single-sample bound. The step-size recurrence alone does not force square-summability when the curvature cap is weak. Because Algorithm 1 and the experiments use mini-batches of size 32 and 309, the almost-sure convergence of Theorem 3.2 and Corollary 3.3 is not established for the method as implemented. A repair would require a uniform lower bound on λ_min(A_S) over all mini-batches, but this is neither stated nor proved.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes AdaSGD, an adaptive step-size rule for stochastic convex optimization. The step size at iteration k is based on the ratio of the displacement to the difference of gradients of the previous mini-batch, combined with a recursive upper bound. Three variants are introduced; Variants II and III include a polynomial decay factor. The authors derive a Lyapunov inequality, then apply the Robbins-Siegmund theorem to obtain almost-sure convergence whenever the step sizes are square-summable, and provide polynomial convergence rates in the strongly convex case. They also claim square-summability for strongly convex objectives and for finite-sum least-squares and ridge regressions. Experiments compare sensitivity to the initial step size and performance against tuned SGD baselines.","tokens_in":21930,"tokens_out":15507,"duration_ms":122797,"significance":"The central construction is original and useful: the step-size derivation is self-contained, the Lyapunov analysis is coherent, and the parameter-free claim is credibly supported by the experiments. The main convergence theorem follows from a standard Robbins-Siegmund argument, and the paper is honest about which experimental settings lie outside the proven cases. However, the proof of square-summability for the non-strongly-convex cases does not cover the algorithm as implemented with mini-batches; this is a load-bearing gap that must be fixed before the central claim is fully established.","major_comments":[{"comment":"The assertion that restricting to single-valued mini-batches is 'without loss of generality' is not justified and is false for the algorithm as stated. For a mini-batch S in linear regression, ∇f_S(x) = A_S x - b_S with A_S = (1/|S|)∑_{i∈S} w_i w_i^T, and the curvature ratio controlling λ_k is ∥r∥/∥A_S r∥ where r = ∇f_S(x_{k-1}). This ratio can be as large as 1/λ_min(A_S) and can be unbounded when A_S is nearly singular or r lies in its kernel. The rank-one identity used in the single-sample proof does not extend to mini-batch averages, so ∑λ_k² < ∞ is not established for mini-batches. Since Algorithm 1 and the experiments use batch sizes 32 and 309, Theorem 3.2 and Corollary 3.3 do not currently imply convergence of the method as run. A repair would need either a uniform lower bound on λ_min(A_S) over all possible batches, a different argument exploiting the random sampling, or a restriction to single-sample updates.","section":"Appendix A.2-A.3 and Corollary 3.3"},{"comment":"The proof defines μhat = max_ℓ ∥w_ℓ∥² and claims the bound ∥Δ∥ / ∥∇f_ξ(x_k)-∇f_ξ(x_{k-1})∥ ≤ 1/μhat. But the computation immediately before gives this ratio equal to 1/∥w_ℓ∥². To obtain the claimed upper bound one needs μhat ≤ ∥w_ℓ∥² for every ℓ, i.e., μhat = min_ℓ ∥w_ℓ∥². As written, the inequality has the wrong direction, so the single-sample Case-2 square-summability proof is also invalid as printed.","section":"Appendix A.2"},{"comment":"Corollary 3.3 is stated for Case-3 (ridge functions) under Assumption 2. However, Assumption 2(2-i) requires each ∇f_ℓ to be globally L-Lipschitz. For f_ℓ(x) = g_ℓ(⟨w_ℓ,x⟩) with g_ℓ merely μ-strongly convex, this need not hold; the paper's own ridge example g(t) = t^4/(1+t^2) + 0.01t² has a derivative that is not globally Lipschitz. Option (2-iii) requires boundedness of the iterates, which is not proved. Thus the convergence guarantee for Case-3 needs an additional smoothness or boundedness assumption, or a separate argument.","section":"Section 3, Case-3 and Assumption 2"}],"minor_comments":[{"comment":"The displayed bound for E_{k-1}∥Δ_k∥² omits the factor 4 in front of λ_k² E_{k-1}[∥∇f_ξk(x_k)-∇f_ξ(k-1)(x_k)∥²]; Proposition 2.1 has the correct factor, so this appears to be a typographical slip.","section":"Section 2.3, displayed inequality after (13)"},{"comment":"The term 32Lλ_k²∥x_k-x_*∥ should read 32L²λ_k²∥x_k-x_*∥² (or be absorbed into T_{k-1}), and the corresponding constant 32L/(8μ²) should be 32L²/(8μ²).","section":"Proof of Theorem 3.4"},{"comment":"The inner expectation denoted E_k should be E_{k-1}, since the quantity is measurable with respect to the filtration at iteration k-1 once x_k is known.","section":"Appendix C, Eq. (28)"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the mini-batch square-summability gap: if the authors can close it, or restrict the theory to single-sample updates and clearly separate the experiments, the paper would be a solid contribution. No concerns about novelty or citation practices beyond those already stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis is a genuinely novel stochastic variant of AdaGD, and the central trick—re-evaluating the previous mini-batch's gradient at the current iterate to cancel the tuning constant α—is clever and worth understanding. The Lyapunov analysis in Section 2 is coherent, and the deterministic-to-stochastic extension is natural. The paper does a good job of presenting three step-size variants, proving almost-sure convergence under several assumptions, and giving a rate in the strongly convex case without knowing μ or L. The experiments convincingly show robustness to λ0 and competitiveness with tuned baselines, though they do not compare to other parameter-free methods like DoG or D-Adaptation, which would be a useful addition.\n\nThe main soft spot is the square-summability proof for Cases 2 and 3 (linear and ridge regression). Appendix A.2–A.3 claim 'without loss of generality' that mini-batches are single-valued, but that reduction does not hold. For a batch S, the curvature ratio becomes ∥Δ∥/∥A_S Δ∥, which is bounded by 1/λ_min(A_S), not by the rank-one constant 1/∥w∥². Since λ_min(A_S) can be arbitrarily small for nearly collinear batch vectors, the proof does not establish square-summability for the algorithm as run in the experiments (batch sizes 32 and 309). This is a real gap in Theorem 3.2 and Corollary 3.3 for those cases. It is not fatal to the central idea—Case-1 (strong convexity) is unaffected, and one can always run with batch size 1—but the paper should either prove a uniform lower bound on λ_min(A_S), or clearly state that the convergence guarantees for Cases 2 and 3 currently apply only to single-sample updates.\n\nMinor issues: δ is technically a user-set parameter, though any small value works; and the relationship between Algorithm 1's λ1 and the appendices should be cleaned up. None of these undermine the main message.\n\nOverall, the paper deserves serious refereeing. The algorithmic idea is new and the analysis is mostly careful, but the mini-batch gap needs to be addressed before the results fully support the claims. I'd send this to a good optimization venue and let the authors fix it.\n\nBest,\n[Your name]","headline":"Clever new stochastic AdaGD variant, but the square-summability proof for the non-strongly-convex cases only covers single-sample batches, so the convergence guarantee doesn't yet match the mini-batch experiments.","tokens_in":22448,"tokens_out":3982,"would_cite":false,"duration_ms":31382,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces an adaptive step-size rule for stochastic gradient descent that needs no hyper-parameter tuning, and proves convergence and explicit rates under strong convexity without knowing the smoothness or strong-convexity…","keywords":["adaptive step size","stochastic gradient descent","parameter-free","Lyapunov analysis","convex optimization","strong convexity","ridge regression","Robbins-Siegmund"],"falsifier":"Run Variants II and III on the finite-sum linear-regression problem with mini-batch size 32 and check empirically whether $\\sum_k \\lambda_k^2$ diverges or whether the bound $\\|\\Delta_k\\|/\\|\\nabla f_\\xi(x_k)-\\nabla f_\\xi(x_{k-1})\\| \\le 1/(\\mu_\\xi\\|w_\\xi\\|^2)$ holds for the averaged gradient; either failure would show the summability guarantee does not cover the algorithm as run.","tokens_in":21310,"feed_emoji":"📉","tokens_out":4687,"duration_ms":36750,"temperature":0.7,"pith_summary":"This paper proposes an adaptive step-size scheme for stochastic gradient descent that requires no hyper-parameter tuning. The step size is formed from two stochastic gradient evaluations per iteration, using the difference of gradients of the same random component function evaluated at consecutive iterates to estimate local curvature. The paper proves almost-sure convergence of the iterates whenever the squared step sizes are summable, and shows summability holds in three settings: strongly convex objectives, linear regression, and sums of ridge functions. For strongly convex objectives, the third variant achieves $\\mathbb{E}[\\|x_{k+1}-x^\\star\\|^2] \\le C/k^{1/2+\\delta}$ without knowing the strong-convexity or smoothness constants. The practical claim is that this matches tuned baselines while removing the step-size search.","feed_headline":"Step-size with no tuning provably converges for stochastic gradient","feed_subtitle":"Two gradient evaluations per step estimate local curvature; matches tuned baselines on six problems.","key_machinery":"The Lyapunov sequence $T_k = \\|x_{k+1}-x^\\star\\|^2 + 2\\lambda_k(1+\\lambda_k/\\lambda_{k-1})(f(x_k)-f^\\star) + \\|x_{k+1}-x_k\\|^2/2$ is the central object. The argument decomposes the sampled-gradient difference into sampling noise and a curvature term, and the curvature term is controlled by the step-size condition $\\lambda_k \\le \\|x_k-x_{k-1}\\|/(2\\sqrt{2}\\|\\nabla f_{\\xi_{k-1}}(x_k)-\\nabla f_{\\xi_{k-1}}(x_{k-1})\\|)$, while the recursion $\\lambda_k \\le \\lambda_{k-1}\\sqrt{1+\\theta_{k-1}}$ maintains the Lyapunov inequality in expectation. Together these two conditions let the analysis reduce convergence to square-summability of the step sizes. The strong-convexity variant adds bounded-above and bounded-below estimates of $\\lambda_k$ that produce the explicit rate.","core_discovery":"The central discovery is that the deterministic 'adaptive gradient descent without descent' Lyapunov analysis can be transferred to stochastic gradients by one pivoting choice: evaluate the two gradients in the curvature estimate on the same previously drawn random component $f_{\\xi_{k-1}}$. The step-size $\\lambda_k$ is the minimum of an inverse-local-Lipschitz term and a multiplicative recursion, and the paper shows the resulting Lyapunov sequence has expected decrease up to a variance term. Under conditions that bound this term, the Lyapunov sequence converges almost surely whenever $\\sum_k \\lambda_k^2 < \\infty$. For $\\mu$-strongly convex $f_\\xi$ with $L$-Lipschitz gradients, Variant III concentrates the step size between explicit constant-free bounds, giving a polynomial convergence rate in expectation without knowledge of $\\mu$ or $L$.","pith_inferences":["The proofs of square-summability in the linear- and ridge-regression cases assume single-element mini-batches and state this is without loss of generality; the step of extending the bound to averaged gradients is not shown. If that inequality degrades for mini-batch averages, the almost-sure guarantee does not cover the batch sizes used in the experiments (32 and 309).","The rate $O(1/k^{1/2+\\delta})$ is slower than the $O(1/k)$ of well-tuned SGD on strongly convex problems; a natural test is whether the no-tuning robustness is worth the constant-factor slowdown at large $k$.","The analysis hinges on convexity for the key inequalities, but the variance term structure suggests a possible extension via the paper's convex-case results to objectives that are only locally Lipschitz smooth."],"forward_implications":["For strongly convex $f_\\xi$, Variant III yields $\\mathbb{E}[\\|x_{k+1}-x^\\star\\|^2] \\le C/k^{1/2+\\delta}$ for all $k \\ge k_0$, with $k_0$ independent of $\\lambda_0$, and without knowing $\\mu$ or $L$.","For finite-sum linear regression and sums of ridge functions, the squared step sizes are summable, so the iterates converge almost surely even though the component functions are not strongly convex.","The deterministic full-batch recursion is recovered up to a $\\sqrt{2}$ factor, so the stochastic method inherits the no-descent property of the deterministic one.","The method uses one extra gradient evaluation per iteration but eliminates the tuning grid, so total oracle cost can be favorable when tuning is expensive."],"supporting_citations":[{"why":"Supplies the deterministic adaptive step-size and Lyapunov function that the paper adapts to the stochastic setting.","marker":"[35]"},{"why":"Provides the almost-sure convergence theorem for nonnegative supermartingales used to prove the convergence results.","marker":"[52]"},{"why":"Provides the asymptotic lemma used in the rate proof to control the tail of the Lyapunov recursion.","marker":"[5]"}],"fun_headline_variants":["No-tuning adaptive step-size provably converges for SGD","Two gradient evaluations make SGD step-size self-tuning","Adaptive SGD without descent: tuning-free convergence proof","Self-tuning step-size for stochastic gradient with proof","Provable convergence for tuning-free stochastic gradient step-size"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the squared step sizes sum to a finite value; in the linear- and ridge-regression cases this is proven for single-sample mini-batches, but the proof that it carries over to the mini-batches used in the experiments is not given.","fun_headline_variants_meta":{"raw":{"variants":["No-tuning adaptive step-size provably converges for SGD","Two gradient evaluations make SGD step-size self-tuning","Adaptive SGD without descent: tuning-free convergence proof","Self-tuning step-size for stochastic gradient with proof","Provable convergence for tuning-free stochastic gradient step-size"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000324,"raw_usage":{"total_tokens":1733,"prompt_tokens":772,"completion_tokens":961,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":388,"completion_tokens_details":{"reasoning_tokens":887}},"tokens_in":388,"tokens_out":961,"duration_ms":8333,"temperature":1.0,"reasoning_tokens":887,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:51:08.304829+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Variants II and III on the finite-sum linear-regression problem with mini-batch size 32 and check empirically whether $\\sum_k \\lambda_k^2$ diverges or whether the bound $\\|\\Delta_k\\|/\\|\\nabla f_\\xi(x_k)-\\nabla f_\\xi(x_{k-1})\\| \\le 1/(\\mu_\\xi\\|w_\\xi\\|^2)$ holds for the averaged gradient; either failure would show the summability guarantee does not cover the algorithm as run.","supporting_citations":[{"cited_title":"Adaptive gradient descent without descent","cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic adaptive step-size and Lyapunov function that the paper adapts to the stochastic setting."},{"cited_title":"Robbins and D","cited_arxiv_id":null,"evidence_quote":"Provides the almost-sure convergence theorem for nonnegative supermartingales used to prove the convergence results."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the asymptotic lemma used in the rate proof to control the tail of the Lyapunov recursion."}],"review_version":2}