{"id":"92576fc3-8eb7-4f3d-93ba-84dd38942190","arxiv_id":"2411.17668","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Gradient descent with a recursively repeated silver stepsize schedule achieves an anytime convergence rate of O(T^{-1.119}) for smooth convex functions, and exp(-Omega(T/kappa^{0.893})) for strongly convex functions.","lead":"This paper finds a fixed stepsize schedule that makes gradient descent converge at rate 1/T^1.119 for every time T, beating the classic 1/T bound. It answers a 2024 COLT open question and extends the improvement to strongly convex problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 10's m=0 subcase divides by zero in (29)–(31); the anytime guarantee needs a separate length-one block argument, though elementary inequalities likely repair it.","rationale":"The central claim of the paper—an anytime stepsize schedule achieving f(x_T)−f* ≤ O(||x_1−x*||²/T^{1.119})—depends on bounding the objective gap at every integer time T, not just at exponentially spaced join steps. Lemma 10 is the precise mechanism that converts fast convergence at join steps into a guarantee for all intermediate iterations. The reader's weakest-assumption analysis correctly identifies the m=0 subcase as the soft spot: the proof's equations divide by bA_0 = 0, and the subsequent case analysis does not provide a separate argument for a block of length one. I checked the surrounding structure and found no independent fatal flaw: the primitive-schedule concatenation, Lemma 7's scaling of aggregate stepsizes, and the extension to strongly convex objectives are coherent, and the proof of Theorem 1 uses Lemma 10 in a way that is consistent with its statement once the block boundaries are indexed correctly. The m=0 gap is localized and likely fixable using only (8f) and gradient Lipschitzness, since the one-step bound and the gradient-growth bound for a √2 step fit within the generous factor 432. For this reason I do not recommend changing the reader's CONDITIONAL verdict; the paper should be accepted only after the m=0 subcase is either repaired with a direct argument or shown to be absorbed by the existing constants.","tokens_in":16952,"tokens_out":34100,"duration_ms":266560,"concrete_test":"Independently re-derive Lemma 10 for m_{j+1}=0 without invoking (29)–(31): verify directly that the one-step block satisfies (i) f_{τ_{j+1}}−f_{τ_j} ≤ (1+√2)||g_{τ_j}||² and (ii) ||g_{τ_{j+1}}||² ≤ (3+2√2)||g_{τ_j}||², and check that substituting these bounds into the final sum (36) still yields the constant 432. If the constant must be enlarged, recompute the O-constants in Theorem 1's display (40) accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 rests on Lemma 10, which controls every intermediate function gap inside a silver block. The displayed derivation of (29)–(31) applies Lemma 9 to the subblock with aggregate bA_{m_{j+1}}. When m_{j+1}=0 this subblock is empty, bA_0 = ρ^0 − 1 = 0, and the denominators bA_{m_{j+1}}(bA_{m_{j+1}}+1) and bA_{m_{j+1}} in (29), (30), and (31) vanish. The proof's Case 2 ('m_{j+1}<2') still starts from (31), so the one-step block is not actually handled. Since the binary expansion of an arbitrary intermediate ℓ can end with 2^0, every invocation of Lemma 10 can hit this case, and (36)—which converts weighted-gradient decay into the anytime bound—has no valid estimate for that term. The gap appears repairable: for m=0 the block is a single step of size √2, and the elementary bounds f(x−√2g)−f(x) ≤ (1+√2)||g||² and ||g(x−√2g)|| ≤ (1+√2)||g|| give constants that fit inside the slack of 432 in (35)–(36). But as written, Lemma 10 is incomplete, and without it Theorem 1 is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a predetermined infinite stepsize schedule for gradient descent on smooth convex functions and proves an anytime bound f(x_T)-f* = O(||x1-x*||^2 / T^theta) with theta = 2 log_2 rho / (1+log_2 rho) = 1.119..., valid for every stopping time T. The schedule is built by concatenating silver stepsize schedules, using the Zhang-Jiang primitive-schedule framework, with each silver order repeated an exponentially growing number of times. The main technical novelty is a lemma controlling the gradient norms at all intermediate iterations inside a silver block; this is what upgrades fast convergence at join steps into an anytime guarantee. The paper also gives a strong-convexity extension by periodically restarting this schedule, obtaining exp(-Omega(T/kappa^{0.893})).","tokens_in":109,"tokens_out":30544,"duration_ms":444775,"significance":"If the proof is made fully rigorous, the result is significant: it affirmatively answers the COLT 2024 open problem of Kornowski and Shamir and is the first provable anytime acceleration of gradient descent beyond the O(1/T) baseline. The paper is largely self-contained; it reproduces the Zhang-Jiang concatenation lemmas in the appendices, and the construction has no fitted parameters, with the final exponent obtained by balancing two proven rates rather than by numerical fitting. The main risk is a technical one in the intermediate-gradient control, which is exactly where the proof currently has gaps.","major_comments":[{"comment":"Case 2 of Lemma 10 is not proved for m_{j+1}=0. In that case the subblock has length one, bA_{m_{j+1}} = bA_0 = 0, and the displayed inequalities (29), (30), and (31) all divide by bA_{m_{j+1}} or by bA_{m_{j+1}}(bA_{m_{j+1}}+1), so Lemma 9 cannot be invoked. This is not a marginal subcase: the binary expansion of an arbitrary intermediate index ell can end with 2^0, so the current proof of Lemma 10 does not cover odd ell. The gap appears repairable by a direct one-step argument: for the single step alpha = sqrt(2), use (8f) together with ||g(x - sqrt(2) g)|| <= (1+sqrt(2))||g|| to show alpha^2_{tau_{j+1}} ||g_{tau_{j+1}}||^2 <= 12 alpha^2_{tau_j} ||g_{tau_j}||^2. This should be written out explicitly, since Lemma 10 is load-bearing for the anytime claim.","section":"Section 3.3, Lemma 10 (displayed inequalities (29)-(31))"},{"comment":"The formula t_{i+1} = t_i + 2^{o_{t_i}+1} is inconsistent with the stated construction. With t_i defined as the length of bs_i after i concatenations in (12), the next concatenation adds one join step plus a silver schedule of order o_{t_i}, so the increment is 2^{o_{t_i}}, not 2^{o_{t_i}+1}; for example, if k_1 is the first repetition count, then t_1=2 and t_2=t_1+2, while the displayed formula would give t_2=6. If instead t_i is intended to be the cumulative length after an entire silver-order group, then the later claim that the union of intervals equals [3,infty) fails because t_1 = 2k_1 is about 10. Either way, the indexing must be repaired. The proof likely goes through with the corrected exponent and adjusted constants, since Lemma 7 bounds 2^{o_{t_i}} as needed, but as written this part of the proof of Theorem 1 is not verifiable.","section":"Section 3.4, around equations (37)-(39)"},{"comment":"The proof of Theorem 11 needs a lower bound tau^theta >= c kappa in order to conclude f_{tau+1} - f* <= ||x1-x*||^2 / (144 kappa), but the displayed argument only yields tau <= 144 C0 kappa^{1/theta}, i.e., tau^theta <= (144 C0)^theta kappa. The missing ingredient is the opposite control: either a lower bound on the hitting time tau, equivalently an upper bound A_t(bs) <= C t^theta on the aggregate stepsizes, or a direct bound showing that the first time A_{tau+1} reaches 4 C0 kappa indeed occurs when tau^theta = Theta(kappa). This upper bound on A_t is plausible from the block construction (each order-j block contributes aggregate rho^j - 1 and length about 2^{(c+1)j}), but it is not stated or proven in the manuscript. Please add this argument before the contraction step.","section":"Section 4, equations (42)-(44)"}],"minor_comments":[{"comment":"The line for (31) contains a duplicated inequality sign ('<= <='); this should be cleaned up.","section":"Section 3.3, equation (31)"},{"comment":"The constant 432 is introduced abruptly. The summation in (36) shows the intended use, but the text should explicitly say that (35) is a coarse uniform bound obtained by combining the geometric decay in Case 1 with the large but finite constant in Case 2.","section":"Section 3.3, equation (35)"},{"comment":"The claim that the union of intervals (t_i,t_{i+1}] equals [3,infty) requires treating the endpoints ell = t_i + 1, which are covered by the primitive bound (38a) rather than by Lemma 10; this should be stated explicitly to avoid an apparent off-by-one gap.","section":"Section 3.4, paragraph after (39)"},{"comment":"The notation A_k in the statement of Lemma 10 and bA_j in its proof should be aligned; the condition alpha >= (sqrt(2)-1)A_k + sqrt(2) uses A_k = 1^T s_i, and the proof would be easier to read if the same symbol were used throughout.","section":"Section 3.3, Lemma 10"}],"recommendation":"major_revision","confidential_remarks":"I recommend major revision. The central result is significant and the identified gaps appear repairable within the paper's scope, but as written the proof of Lemma 10 contains a division-by-zero subcase, the indexing in Section 3.4 is inconsistent, and the strong-convexity contraction argument needs a missing two-sided bound on the aggregate stepsizes. None of these issues looks fatal, but they are load-bearing and should be fixed before the paper is published. The related-work discussion and the self-contained appendices are adequate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zihan and colleagues answer the Kornowski-Shamir open problem: a fixed stepsize schedule, chosen without knowing T, gives f(x_T)-f* = O(||x1-x*||^2/T^{1.119}) for every T. That is a genuine advance. Prior silver-schedule bounds only held at T=2^k-1, and the known concatenation tricks needed T in advance. The construction—repeating silver blocks with exponentially growing multiplicities—is simple and effective, and the analysis is mostly careful. They even reproduce the Zhang-Jiang concatenation lemmas in the appendix, which I appreciate.\n\nThe main theorem hinges on Lemma 10, which controls every intermediate gradient gap inside a silver block. There is a real hole in that lemma as written. In Case 2 (m_{j+1}<2), the displayed (29)-(31) divide by bA_{m_{j+1}}(bA_{m_{j+1}}+1). When m_{j+1}=0, that denominator is zero, and the block is just a single step of size √2. The text still invokes (31) and then asserts a bound that doesn't follow. Since every binary expansion can end at 2^0, this subcase is hit constantly; the anytime bound has no valid estimate there. The gap looks repairable: for a one-step block, the elementary inequalities f(x-√2g)-f(x) ≤ (1+√2)||g||^2 and ||g(x-√2g)|| ≤ (1+√2)||g|| fit inside the slack of the 432 constant. But as written, Lemma 10 is incomplete, and Theorem 1 is not fully proved.\n\nI want to be clear about the proportion: this is a single, localized gap in an otherwise coherent proof. The construction, the exponent calculation, and the extension to strongly convex problems all check out. I don't see any sign of curve-fitting or circularity. The paper is worth serious referee time—someone should ask the authors to fix Lemma 10, and I expect they can.\n\nFor a reader in optimization theory or ML theory, this is a paper to know. I'd put it on a reading group agenda, since the gap and its repair are instructive. My recommendation: send to peer review, but be explicit that the m=0 subcase needs a clean argument before acceptance.","headline":"Resolves the COLT anytime-GD open problem with a clever schedule; the proof has a real, likely patchable gap in Lemma 10's length-one case.","tokens_in":17799,"tokens_out":2988,"would_cite":true,"duration_ms":25862,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper constructs a fixed stepsize schedule under which gradient descent reaches error O(T^{-1.119}) at every stopping time T, the first provable anytime acceleration beyond the classic 1/T rate.","keywords":["anytime convergence","gradient descent","stepsize schedule","silver ratio","smooth convex optimization","strongly convex optimization","acceleration","concatenation"],"falsifier":"Check whether Lemma 10's subcase for a block of length one can be proved without the displayed division by $\\rho^0-1=0$; if no separate argument exists, the lemma's proof is incomplete. Empirically, run the constructed schedule on a family of smooth convex quadratics and record $f(x_T)-f^*$ at all $T$; if $T^{1.119}(f(x_T)-f^*)/\\|x_1-x^*\\|^2$ is unbounded at any time $T$, the $O(T^{-1.119})$ anytime claim is false.","tokens_in":16770,"feed_emoji":"📉","tokens_out":11106,"duration_ms":89392,"temperature":0.7,"pith_summary":"The paper asks whether plain gradient descent can be accelerated by a step-size schedule alone, without knowing in advance when the algorithm will be stopped. It answers yes: the authors construct a predetermined infinite schedule, built by repeating silver-ratio blocks joined by specially chosen step sizes, under which the objective gap at any stopping time $T$ is $O(\\|x_1-x^*\\|^2/T^{1.119})$, improving on the classical $O(1/T)$ rate. The same construction gives an anytime rate $\\exp(-\\Omega(T/\\kappa^{0.893}))$ for smooth strongly convex problems. This settles a 2024 open problem and shows that step-size design, not momentum or memory, can make gradient descent faster at every iteration.","feed_headline":"Gradient descent now beats 1/T at every stopping time","feed_subtitle":"A fixed, precomputed step-size schedule reaches error O(T^-1.119) for smooth convex problems, no matter when you stop.","key_machinery":"The machinery is the primitive stepsize schedule and its concatenation rule. A schedule $s=\\alpha_{1:k-1}$ is primitive if it satisfies a descent-potential inequality that yields $f_k-f^*\\le O(1/A_k)$ at its final point, where $A_k$ is the sum of its step sizes. Two primitive schedules $s$ and $r$ can be joined by inserting the step $\\varphi(1^\\top s,1^\\top r)$, where $\\varphi$ is the unique positive value keeping the combined schedule primitive. The paper's schedule repeats the $j$-th order silver schedule $s_j$ (total step sum $\\rho^j-1$) for $k_j\\approx 2^{c j}$ repetitions with $c=\\log_2\\rho$, producing many join steps while keeping the total step sum large. The new ingredient is Lemma 10: inside a silver block, if the incoming step size $\\alpha$ is at least $(\\sqrt2-1)A_k+\\sqrt2$, every intermediate gap $f_\\ell-f_0$ is bounded by $432\\alpha^2\\|g_0\\|^2$, which prevents intermediate iterates from overshooting.","core_discovery":"The central claim is Theorem 1: there exists a stepsize schedule $\\{\\alpha_t\\}$, fixed in advance and independent of the stopping time, such that gradient descent on a 1-smooth convex function obeys $f(x_T)-f^* \\le O(\\|x_1-x^*\\|^2 / T^\\theta)$ for every $T\\ge 1$, where $\\theta = 2\\log_2\\rho/(1+\\log_2\\rho) \\approx 1.119$ and $\\rho=1+\\sqrt2$ is the silver ratio. Previously, acceleration by step-size design was known only at exponentially spaced checkpoints or when the stopping time was fixed in advance; the paper's contribution is to close the gap at every integer time and to extend the same schedule to strongly convex objectives with an anytime rate $\\exp(-\\Omega(T/\\kappa^{0.893}))$.","pith_inferences":["Editorial extension: the construction leaves the repetition exponent $c$ free and only fixes $c=\\log_2\\rho$ at the end; if a sharper version of Lemma 10 existed, a different $c$ could push the anytime exponent closer to $\\log_2\\rho \\approx 1.272$.","Editorial extension: because the objective value is non-monotone between join steps, a practical stopping rule that trusts the last observed gap could be misled; a natural test is whether stopping at scheduled checkpoints recovers the anytime guarantee in practice.","Editorial extension: the concatenation framework is not tied to the silver schedule, so the same proof strategy could be tried with other primitive blocks, for example blocks tailored to composite objectives or to linear convergence, potentially transferring the anytime property to proximal or coordinate-descent methods."],"forward_implications":["A fixed step-size schedule gives worst-case anytime error $O(T^{-1.119})$ for smooth convex gradient descent, beating the $O(1/T)$ barrier at every stopping time.","The guarantee holds without knowing $T$ in advance, so the schedule is usable when the iteration count is chosen online or by a random stopping rule.","For smooth strongly convex objectives, the concatenation idea gives an anytime rate $\\exp(-\\Omega(T/\\kappa^{0.893}))$, improving the exponent's dependence on the condition number relative to the standard $\\exp(-\\Omega(T/\\kappa))$.","The result affirmatively answers a 2024 open problem asking whether stepsize-based acceleration can achieve an anytime rate of $o(1/T)$."],"supporting_citations":[{"why":"Provides the silver stepsize schedule and its $O(T^{-\\log_2\\rho})$ rate at $T=2^k-1$, the fast block that the new schedule reuses.","marker":"Altschuler and Parrilo, 2023b"},{"why":"Supplies the definition of primitive stepsize schedules and the concatenation lemma (Lemma 3) that the construction repeatedly invokes.","marker":"Zhang and Jiang, 2024"},{"why":"Poses the anytime open problem and shows the unmodified silver schedule fails at intermediate times, defining the target and the baseline.","marker":"Kornowski and Shamir, 2024"},{"why":"Shows how to compose optimized step-size schedules for a prescribed stopping time, the approach the paper adapts to the anytime setting.","marker":"Grimmer et al., 2024b"},{"why":"Gives the textbook constant-stepsize $O(1/T)$ guarantee that the anytime result improves upon.","marker":"Nesterov, 2018"}],"fun_headline_variants":["Anytime step-size acceleration beats 1/T","Gradient descent with silver ratio stepsizes accelerates anytime","Fixed schedule gives super-1/T convergence at every stop","Anytime gradient descent: O(T^-1.119) without knowing T","Step-size design accelerates gradient descent at all times"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The anytime guarantee rests on Lemma 10, the claim that inside a silver block with a large-enough incoming step, every intermediate function gap stays below $432\\alpha^2\\|g_0\\|^2$; if that intermediate control fails, the schedule's fast rate at join steps does not transfer to arbitrary stopping times.","fun_headline_variants_meta":{"raw":{"variants":["Anytime step-size acceleration beats 1/T","Gradient descent with silver ratio stepsizes accelerates anytime","Fixed schedule gives super-1/T convergence at every stop","Anytime gradient descent: O(T^-1.119) without knowing T","Step-size design accelerates gradient descent at all times"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000281,"raw_usage":{"total_tokens":1617,"prompt_tokens":851,"completion_tokens":766,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":467,"completion_tokens_details":{"reasoning_tokens":684}},"tokens_in":467,"tokens_out":766,"duration_ms":7697,"temperature":1.0,"reasoning_tokens":684,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:51:51.830652+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check whether Lemma 10's subcase for a block of length one can be proved without the displayed division by $\\rho^0-1=0$; if no separate argument exists, the lemma's proof is incomplete. Empirically, run the constructed schedule on a family of smooth convex quadratics and record $f(x_T)-f^*$ at all $T$; if $T^{1.119}(f(x_T)-f^*)/\\|x_1-x^*\\|^2$ is unbounded at any time $T$, the $O(T^{-1.119})$ anytime claim is false.","supporting_citations":[{"cited_title":"and Shamir, O","cited_arxiv_id":null,"evidence_quote":"Poses the anytime open problem and shows the unmodified silver schedule fails at intermediate times, defining the target and the baseline."}],"review_version":1}