{"id":"c6c64c4e-2a9c-4f90-aea0-00ebdc9868a7","arxiv_id":"1908.07861","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A coupled ODE system, discretized with a decreasing learning rate, yields accelerated SGD algorithms with proven optimal last-iterate rates and improved constants.","lead":"This paper derives accelerated stochastic gradient descent algorithms from a coupled system of differential equations that also produces Nesterov's acceleration method. It proves last-iterate convergence rates of order 1/k for strongly convex problems and log(k)/sqrt(k) for convex ones, with constants better than earlier bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Convex-case theorem (Prop 5.4) is false as stated: no initial condition links v0 to x0, and at k=0 the proof's weight 1-2h0/t0 is negative.","rationale":"The most load-bearing concern is that the convex-case theorem is false as stated, because the initial condition is under-specified and the base case k=0 of the proof is invalid. This is more severe than the constant errors the reader flagged: it means the claimed O(1/sqrt(k)) bound does not follow from the proof and is contradicted by an explicit first-step computation. The strongly convex case avoids this by taking v0=x0; the convex case never states this, and the definition of E^C_0 only controls v0. The failure is not an artifact of the noise model; it occurs with sigma=0 and a deterministic smooth convex quadratic. The fix is to require v0=x0 (so E0 bounds the initial distance) and to prove the dissipation separately at k=0, where t_0=h_0 makes the weight 1-2h_0/t_0 negative. Since the flaw is localized and fixable, the manuscript should be accepted only conditionally on these corrections. The reader's weakest_assumption (noise bias/step-size restriction) is not the same concern; agreement is therefore 'disagree'.","tokens_in":18407,"tokens_out":45574,"duration_ms":356229,"concrete_test":"Run the first step of (Per-FE-C) for f(x)=||x||^2/2, L=1, c=1/2, sigma=0, x_0=10, v_0=0=x*. Then h_0=1/2, t_0=1/2, w_0=2, y_0=-10, x_1=-5, v_1=1.25, so E_1^C=t_0^2 f(x_1)+2|v_1|^2=6.25, but the bound in Prop 5.4 gives 0. This confirms the missing v_0=x_0 assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the convex case (Section 5), the initial Lyapunov value is E^C_0 = 2|v_0-x*|^2 (Definition 5.1), and no condition separates v_0 from x_0. At k=0, t_0=h_0, so w_0=2h_0/t_0=2, giving y_0=(1-w_0)x_0+w_0 v_0=-x_0+2v_0. The claimed dissipation (38) fails for v_0=x*, x_0 far. Example: f(x)=x^2/2, L=1, c=1/2 (so h_0=1/2<=1/sqrt(L)), sigma=0, x_0=10, v_0=0=x*. Then E_0^C=0. The update yields x_1=-5, v_1=1.25, so E_1^C=t_0^2 f(x_1)+2|v_1|^2=0.25*12.5+2*1.5625=6.25, while the RHS of (38) is E_0^C+h_0^2 t_0^2 sigma^2=0. Thus Proposition 5.2's dissipation is false at k=0, and Proposition 5.4's bound E[f(x_1)-f*]<=c^2 sigma^2/sqrt(1)=0 is contradicted. The root cause is that Lemma 5.3's weighted sum uses the weight 1-2h_k/t_k, which is -1 at k=0, so the convex combination is invalid. The strongly convex section explicitly sets v_0=x_0; the convex section must do the same and handle the base case separately.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a coupled first-order ODE system whose forward-Euler discretization with a constant learning rate recovers Nesterov's accelerated gradient method in both the strongly convex and convex cases. The same system, discretized with decreasing learning rates, yields two new stochastic gradient descent algorithms: one for strongly convex objectives with an O(1/k) last-iterate rate and one for convex objectives with an O(log k / sqrt(k)) last-iterate rate. The proofs are based on Lyapunov functions: for the strongly convex case the dissipation inequality gives E[E_{k+1}] <= (1 - h_k sqrt(mu)) E[E_k] + h_k^2 sigma^2, and for the convex case the dissipation gives E[E_{k+1}] <= E[E_k] + h_k^2 t_k^2 sigma^2. The paper claims improved constants over prior SGD last-iterate bounds, with the smoothness constant L removed from the rate and the noise measured by variance sigma^2 rather than second-moment bound G^2.","tokens_in":18806,"tokens_out":7364,"duration_ms":169133,"significance":"If correct, the paper would provide a rigorous acceleration guarantee for momentum-style SGD and a clean Lyapunov-based derivation of new algorithms with better constants than existing last-iterate SGD bounds. The strongly convex section is a coherent extension of the deterministic Lyapunov approach, and the explicit coefficient formulas make the algorithms easy to implement and test. The paper also gives a useful perspective connecting Nesterov acceleration, high-resolution ODEs, and stochastic discretizations. However, the convex-case result is not established as stated: the key dissipation step fails at k=0 because the weighted combination in Lemma 5.3 is not a convex combination, and the rate proof in Proposition 5.4 uses a false numerical inequality. The strongly convex contribution is therefore sound in its main lines, but the convex contribution needs a substantial repair before the advertised claims can be accepted.","major_comments":[{"comment":"The dissipation inequality (38) is false as stated because the proof at k=0 uses a negative weight. In Lemma 5.3, inequalities (41) and (42) are combined with weights 1 - 2h_k/t_k and 2h_k/t_k, respectively. Since t_0 = h_0 by the definition t_k = sum_{i=0}^k h_i, the first weight is -1 at k=0, so the combination is not a convex combination and the resulting inequality is not justified. Moreover, Definition 5.1 sets E_0^C = 2|v_0 - x*|^2 without any condition relating v_0 to x_0. A concrete counterexample is f(x) = x^2/2, L=1, c=1/2 (so h_0=1/2), sigma=0, x_0=10, v_0=0=x*. Then E_0^C=0, while the update in (Per-FE-C) gives x_1=-5 and v_1=1.25, so E_1^C = t_0^2 f(x_1) + 2|v_1|^2 = 6.25, violating the claimed inequality E[E_1^C] <= E[E_0^C] + h_0^2 t_0^2 sigma^2 = 0. Consequently Proposition 5.2 and the rate bound in Proposition 5.4 are not proven, and Proposition 5.4 is false as stated for the k=1 case of this example.","section":"Section 5.1, Proposition 5.2 and Lemma 5.3"},{"comment":"The proof contains the false inequality (k+1)^{1/4} - 1 >= k^{1/4}, used to conclude t_{k-1} >= 4c k^{1/4}. For k>0 the left-hand side is strictly smaller than k^{1/4}, e.g. for k=1 it is 2^{1/4}-1 approx 0.189 < 1. Thus the lower bound on t_{k-1} and the final uniform constant in Proposition 5.4 are not established. A correct estimate would need a different lower bound, such as t_{k-1} >= 4c(k^{1/4}-1), which would weaken the stated result or require a modified argument.","section":"Section 5.2, Proposition 5.4 proof"},{"comment":"The stated formula for gamma_k is inconsistent with the derivation in the same proposition. Proposition 2.2 gives gamma_k = k/(2 sqrt(C_f) + 4 + k), but the proof obtains gamma_k = w_{k+1} * k/2 with w_{k+1} = 1/(sqrt(C_f) + 1 + (k+1)/2), which simplifies to gamma_k = k/(2 sqrt(C_f) + k + 3). The form in the Introduction and the matching derivation both give the denominator 2 sqrt(C_f) + k + 3. As written, the algorithm in Proposition 2.2 does not match the system (11)-(13) from which it is derived, so a reader implementing the stated gamma_k would not obtain the algorithm analyzed in Section 3.","section":"Section 2.2, Proposition 2.2"}],"minor_comments":[{"comment":"The manuscript refers to a final numerical simulations section with the placeholder 'Section ??', but the paper ends with the references and contains no numerical experiments. Either add the promised section or remove the reference to it.","section":"General"},{"comment":"The algebraic line in the induction writes (k+k0-1)(k+k0-1) <= (k+k0)^2, but the intended inequality is (k+k0-1)(k+k0+1) <= (k+k0)^2, which is true and needed to pass from the numerator k+k0-1 to the denominator k+k0+1. This appears to be a typographical error.","section":"Section 3.2, Proposition 3.7 proof"},{"comment":"There are several typographical issues in the comparison-series steps ('obrain', 'series-intergal') and in the summation index 'sum_{i=1}^k 1/x'; these should be corrected for clarity.","section":"Section 5.2, Proposition 5.4 proof"},{"comment":"The convex-case initialization is under-specified: unlike the strongly convex case, where Definition 3.1 explicitly sets v_0 = x_0, the convex section does not impose any relation between v_0 and x_0. If the published result requires an extra assumption, it should be stated and used in the proof.","section":"Section 5.1, Definition 5.1"}],"recommendation":"major_revision","confidential_remarks":"The convex-case failure is serious because it directly invalidates Proposition 5.2 and Proposition 5.4 as stated. The issue at k=0 is not a cosmetic gap: the proof machinery breaks at the first step, and the counterexample shows the claimed dissipation does not hold without additional assumptions. I would encourage the authors to repair this by adding a proper initialization condition, handling the base case separately, and proving the required inequalities for all k. If the convex-case result cannot be repaired, the paper should be revised to present only the strongly convex contribution, or to clearly separate the two cases and state which theorems are established. The strongly convex part appears sound and is a useful contribution in itself."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper is a real contribution to last-iterate SGD analysis, but the convex-case theorem is false as written. The strongly convex half holds up; the convex half needs repair, and I think the repair is doable.\n\nThe genuinely new piece is the stochastic extension: a coupled first-order ODE system, the k^{3/4} learning rate, and Lyapunov dissipations that give optimal last-iterate rates under the standard stochastic approximation model (unbiased gradients, bounded variance). The continuous-time part is a reformulation of the high-resolution ODE family from Shi et al. 2018, as the authors themselves note, but the stochastic analysis and the improved constants are not in that prior work. In the strongly convex case the proof is coherent: they set v0=x0, the dissipation (24) and the constant- and decreasing-rate results in Props 3.5 and 3.7 check out, and the 4σ²/(μ(k+k0)) bound with no L dependence is a genuine improvement over the G²-based bounds in Table 1.\n\nThe convex section is another story. Definition 5.1 does not connect v0 to x0, and at k=0 the weight in Lemma 5.3 is 2h0/t0=2, so the claimed convex combination actually has a negative coefficient on the f(xk)-f* term. The counterexample is simple: f(x)=x²/2, L=1, c=1/2, σ=0, x0=10, v0=x*=0. Then E^C_0=0, but one step of the algorithm gives E^C_1=6.25, directly contradicting the monotonicity (38) and the bound in Prop 5.4. That is a real flaw, not a technicality. The fix is plausible: impose v0=x0 and handle k=0 as a separate base case, exactly as the strongly convex section already does. There is also a false inequality in Prop 5.4: (k+1)^{1/4}-1 ≥ k^{1/4} fails for every k≥1, so the stated constant 1/(16c²) is not proven. A slightly worse constant should rescue the O(1/√k) rate.\n\nTwo smaller issues: the γ_k formula in Prop 2.2 has the wrong denominator (it should be 2√Cf+k+3, not 4+k), a typo but in an algorithm specification; and the outline promises numerical simulations in a section that never appears. The constant comparison in Table 1 is apples-to-oranges—G²-based bounds versus σ²-based bounds—so the 'better constants' claim should be nuanced, though the removal of the L dependence is still meaningful.\n\nWho this is for: stochastic optimization researchers working on accelerated momentum schemes and Lyapunov arguments. It deserves a serious referee. The core idea is good, the strongly convex part is likely correct, and the convex part is probably salvageable. I would accept it for peer review with the clear expectation that the convex case be rewritten.\n\nRecommendation: engage with this paper, but do not trust Prop 5.2 or Prop 5.4 in their current form. Ask the authors for the base-case fix and for a correct lower bound on t_{k-1}.","headline":"Strongly convex part looks solid; convex part is false as stated but likely repairable.","tokens_in":19329,"tokens_out":5644,"would_cite":true,"duration_ms":79128,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","65K10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper derives accelerated SGD from a coupled ODE system and proves optimal last-iterate convergence rates in the convex and strongly convex cases.","keywords":["accelerated stochastic gradient descent","Nesterov's accelerated gradient","Lyapunov function","last-iterate convergence","convex optimization","strongly convex optimization","decreasing learning rate","stochastic approximation"],"falsifier":"Run the strongly convex algorithm on a one-dimensional quadratic $f(x)=\\mu x^2/2$ with added zero-mean noise of known variance $\\sigma^2$, estimating $\\mathbb{E}[f(x_k)-f_*]$ over many independent trials. If the empirical average exceeds $\\frac{4\\sigma^2}{\\mu(k+k_0)}$ at any $k$ by more than Monte-Carlo error, the central bound is false. The convex bound can be tested the same way against the $O((1+\\log k)/\\sqrt{k})$ inequality.","tokens_in":18210,"feed_emoji":"⚡","tokens_out":7056,"duration_ms":232344,"temperature":0.7,"pith_summary":"This paper tries to turn the connection between Nesterov's accelerated gradient method and differential equations into new stochastic gradient descent algorithms with proven acceleration. The authors write Nesterov's method as a coupled pair of gradient-descent-like evolutions; with a constant time step the system reproduces Nesterov's method, and with a decreasing learning rate the same system becomes an accelerated SGD algorithm. They prove that the last iterate converges at the optimal rates in both settings, with constants that improve on previously available bounds. If correct, this gives rigorous justification for the common heuristic that momentum helps stochastic gradient descent, and supplies explicit coefficient schedules that realize the improvement.","feed_headline":"Decreasing learning rate turns Nesterov's ODE into fast SGD","feed_subtitle":"Rigorous last-iterate bounds beat earlier constants; the schedule even includes a novel k^{3/4} step size.","key_machinery":"The load-bearing object is the coupled first-order system in the variables $(y_k,x_k,v_k)$: $y_k = (1-w_k)x_k + w_k v_k$, $x_{k+1}-x_k = w_k(v_k-x_k) - \\frac{h_k}{\\sqrt{L}}(\\nabla f(y_k)+e_k)$, and $v_{k+1}-v_k = w_k(x_k-v_k) - \\frac{\\sqrt{C_f}h_k}{\\sqrt{L}}(\\nabla f(y_k)+e_k)$ in the strongly convex case, with $w_k = \\frac{h_k\\sqrt{\\mu}}{1+h_k\\sqrt{\\mu}}$. Alongside it sits a rate-generating Lyapunov function $E^{SC}(x,v) = f(x)-f_* + \\frac{\\mu}{2}\\|v-x_*\\|^2$, and a time-weighted analogue in the convex case. The Lyapunov function is what carries the argument: its one-step dissipation contains a stochastic error term of order $h_k^2\\sigma^2$, and the learning-rate schedule is chosen so that summing these errors produces the target rate.","core_discovery":"The central claim is that a single coupled ODE system supports both regimes. The system couples an ordinary gradient descent variable $x$ with an auxiliary variable $v$ that runs at a faster, unstable rate, joined through a convex combination $y$. Discretized with a constant step $h \\leq 1/\\sqrt{L}$, it is Nesterov's accelerated gradient method; discretized with the decreasing schedule $h_k = \\frac{2}{\\sqrt{\\mu}(k+k_0)}$ in the strongly convex case, it yields $\\mathbb{E}[f(x_k)-f_*] \\leq \\frac{4\\sigma^2}{\\mu(k+k_0)}$, and with the novel schedule $h_k = \\frac{c}{(k+1)^{3/4}}$ in the convex case, it yields $\\mathbb{E}[f(x_k)]-f_* \\leq \\frac{1}{\\sqrt{k}}\\left(\\frac{E_0^C}{16c^2} + c^2\\sigma^2(1+\\log k)\\right)$. In the two-step form the algorithm is $x_{k+1} = y_k - \\alpha_k \\nabla f(y_k)/L$, $y_{k+1} = x_{k+1} + \\beta_k(x_{k+1}-x_k) + \\gamma_k(y_k-x_k)$, where the extra $\\gamma_k$ term is not present in standard momentum SGD heuristics. The proof works by showing a Lyapunov function dissipates with an error term proportional to $h_k^2\\sigma^2$, then choosing $h_k$ so that the accumulated error matches the optimal last-iterate rate.","pith_inferences":["One testable extension: replacing the stochastic-gradient noise model with variance-reduced gradients, the finite-sum case the paper explicitly defers, may preserve the same Lyapunov argument and yield accelerated rates with finite-sum constants.","The $\\gamma_k$ term's role could be isolated empirically: running heuristic momentum SGD with and without this term on a smooth convex problem with controlled noise would show whether the proven acceleration appears in practice or only in the bound.","The ODE-discretization route suggests a recipe: any Lyapunov function with known dissipation can be coupled with a decreasing step schedule to generate new SGD variants, although the paper does not claim this generality.","The convex schedule $h_k \\propto k^{-3/4}$ is unusual; if the bound is tight, it implies the optimal choice of $c$ balances initialization error and noise, which could guide step-size tuning in practice."],"forward_implications":["In the strongly convex case, a stochastic gradient method can reach error $O(\\sigma^2/(\\mu k))$ on the last iterate without averaging, with a constant independent of both the smoothness constant $L$ and the gradient bound $G^2$.","In the convex case, the last iterate reaches $O((1+\\log k)/\\sqrt{k})$ using the $k^{3/4}$ learning-rate schedule, with no need to fix the iteration horizon in advance.","The extra coupling term $\\gamma_k(y_k-x_k)$ is part of the algorithm that makes the Lyapunov proof close; omitting it, as common momentum SGD does, forfeits the proven guarantee.","A short constant-learning-rate warm start puts the Lyapunov function below the critical value $E_{crit}$, so the algorithm can be initialized in a state where the decreasing schedule's rate applies.","The constant-learning-rate phase converges exponentially at rate $1-h\\sqrt{\\mu}$ to a noise-dominated neighborhood, improving on the standard $1-h\\mu$ contraction of SGD."],"supporting_citations":[{"why":"Supplies the ODE representation of Nesterov's method that the paper starts from.","marker":"Su et al. [2014]"},{"why":"Provides the stochastic noise model (1)-(2) and the classical SGD inequality (3) that the accelerated bound is compared with.","marker":"Bottou et al. [2018]"},{"why":"Establishes the information-theoretic lower bounds that identify the optimal last-iterate rates.","marker":"Agarwal et al. [2009]"},{"why":"Gives the baseline last-iterate rates and constants used in Table 1.","marker":"Shamir and Zhang [2013]"},{"why":"The Lyapunov analysis of momentum methods that Proposition 3.2 generalizes and shortens.","marker":"Wilson et al. [2016]"},{"why":"Introduces high-resolution ODEs; the paper's first-order system matches the high-resolution equation with parameter $1/\\sqrt{L}$.","marker":"Shi et al. [2018]"},{"why":"The decreasing-learning-rate Lyapunov induction used in the proof of Proposition 3.7.","marker":"Oberman and Prazeres [2019]"}],"fun_headline_variants":["Decreasing LR turns Nesterov's ODE into faster SGD","Novel k^{3/4} schedule accelerates last-iterate SGD","Nesterov with decreasing step size beats prior SGD rates","Tuned decreasing learning rate yields accelerated SGD bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proofs assume every gradient estimate is unbiased with uniformly bounded variance and every learning rate satisfies $h_k \\leq 1/\\sqrt{L}$; if either fails, the Lyapunov error term is no longer controlled by $h_k^2\\sigma^2$ and the stated rates do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Decreasing LR turns Nesterov's ODE into faster SGD","Novel k^{3/4} schedule accelerates last-iterate SGD","Nesterov with decreasing step size beats prior SGD rates","Tuned decreasing learning rate yields accelerated SGD bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000231,"raw_usage":{"total_tokens":1529,"prompt_tokens":1031,"completion_tokens":498,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":647,"completion_tokens_details":{"reasoning_tokens":428}},"tokens_in":647,"tokens_out":498,"duration_ms":5284,"temperature":1.0,"reasoning_tokens":428,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:55:44.967175+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the strongly convex algorithm on a one-dimensional quadratic $f(x)=\\mu x^2/2$ with added zero-mean noise of known variance $\\sigma^2$, estimating $\\mathbb{E}[f(x_k)-f_*]$ over many independent trials. If the empirical average exceeds $\\frac{4\\sigma^2}{\\mu(k+k_0)}$ at any $k$ by more than Monte-Carlo error, the central bound is false. The convex bound can be tested the same way against the $O((1+\\log k)/\\sqrt{k})$ inequality.","supporting_citations":[],"review_version":1}