{"id":"b3aca68b-d198-4dcb-88b5-d34262043b25","arxiv_id":"2608.10418","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Gradient descent with arbitrary predetermined nonnegative step size schedules has worst-case last-iterate convergence rate at least Omega(T^{-p}) for every p > sqrt(2+sqrt(3)) approximately 1.9319.","lead":"This paper proves that plain gradient descent, even with carefully pre-chosen step sizes, cannot converge faster than about T^{-1.93} in the worst case for smooth convex problems. It gives the first lower bound showing that step-size schedule tricks alone cannot reach the optimal T^{-2} speed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No algebraic error found in spot-checks of Sections 4-6; the load-bearing concern is that Theorem 2.1 rests on an intricate GPT-generated proof whose claimed Lean formalization is unauditable, so its correctness cannot yet be independently certified.","rationale":"The Reader's weakest-assumption pick (the projection identity in Theorem 4.1) is, on my line-by-line check, the best-supported link: the variational inequalities are verified for every s in each block rather than only at visited iterates, and the predecessor and successor comparisons reduce exactly to the condition gamma_i^2 <= chi_i in Eq. (7). I nonetheless keep the Reader's verdict, because the genuine soft spot is the one named in the Reader's rationale: the proof is disclosed as LLM-generated with only a high-level strategy supplied by the authors, and the claimed machine-checked formalization is unauditable from the manuscript. I found no internal inconsistency: the checked identities include (26), (34)-(36), (40), (45), (49)-(53), (55)/(65), (66)-(72), and Lemma B.1, and the strict threshold p > p* = sqrt(2+sqrt(3)) follows correctly from 2*theta+2*theta^2 < 1 with theta = 1/(p^2-1). The construction is parameter-free, explicit, and dimension-efficient (m+1 <= T+1), covers zero steps and unselected long steps inside gaps, and the L,R scaling in Lemma 6.6 is clean. The remaining risk is that an intricate, AI-generated proof without an auditable formal artifact cannot be certified from the manuscript alone; hence the conditional verdict stands unchanged pending the pin-and-build check.","tokens_in":27794,"tokens_out":46706,"duration_ms":356141,"concrete_test":"Ask the authors to pin the Lean repository at a public commit with a pinned lakefile and Lean toolchain, run 'lake build', and extract the formalized statements of Proposition 5.1, Lemma 6.3, Proposition 6.1, and Theorem 2.1, comparing them verbatim with the manuscript. If the repository builds and the extracted statements match, the central claim becomes independently checkable and the verification gap closes; if it does not build or those statements are absent, the conditional verdict is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 2.1) holds exactly if the whole chain of Sections 4 to 6 is correct: the geometric realization (Theorem 4.1), the two-matching order-free bound (Proposition 5.1 via Lemmas 5.2 and 5.3), and the rank-cutoff and Lyapunov mass-growth argument (Lemmas 6.2 to 6.5, Proposition 6.1). I re-derived the load-bearing identities - the factor expansions (26), the mass decomposition (24)-(25), the equalization Lemma 5.2, the matching bound (40), the recursions (49)-(53), the drift identity (65), and the bounded-rank prefix bound (B.1) - and found them internally consistent; the threshold p* = sqrt(2+sqrt(3)) follows correctly from 2*theta+2*theta^2 < 1 with theta = 1/(p^2-1). In particular, the projection identity the Reader singled out is proven for every s in [0, U_i-1] on every block, including empty gaps, zero steps, and unselected long steps inside gaps, so it is not a hidden assumption. The load-bearing concern is epistemic: the disclosure (Section 7) states that the authors supplied only the objective and a high-level resisting-oracle strategy, while GPT-5.6 Sol Pro produced the proof over several attempts; the claimed Lean formalization is referenced only by URL, with no commit hash, no toolchain pin, no build instructions, and no list of formalized theorems. A single incorrect inequality in the matching or Lyapunov machinery would invalidate Theorem 2.1, and the manuscript offers no way to settle that independently. This justifies a conditional verdict; it does not support rejection.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a new worst-case lower bound for plain gradient descent with predetermined nonnegative stepsize schedules on smooth convex functions. The main result, Theorem 2.1, states that for every exponent p > p* = sqrt(2+sqrt(3)) ≈ 1.9319, every horizon T, every L,R > 0, and every predetermined nonnegative schedule, there is a smooth convex instance (in dimension at most T+1) whose last-iterate suboptimality is at least c_p L R^2 (T+1)^{-p}. The proof normalizes to L=R=1, decomposes each step into a capped part and an excess, selects long steps, and constructs a hard instance via the Moreau envelope of the support function of a simplex (Theorem 4.1). A key functional C_T(h) is then bounded below by an order-free matching argument (Proposition 5.1 and Lemma 5.3), followed by a rank-cutoff and Lyapunov mass-growth argument (Section 6). The endpoint p = p* is not reached; the result leaves open the gap between the best known upper exponent log_2(1+sqrt(2)) and the new impossibility threshold.","tokens_in":28108,"tokens_out":26609,"duration_ms":218781,"significance":"If correct, this is a substantial contribution: it is the first rigorous evidence that prescribed nonnegative stepsize schedules alone cannot accelerate plain gradient descent to the optimal O(T^{-2}) rate, and it distinguishes the prescribed-horizon setting from both the anytime lower bound of Tsai et al. and the classical oracle lower bound of Drori. The proof is fully written out and parameter-free, with explicit constructions whose dimension is at most T+1; the threshold p* arises cleanly from the competing requirements 2theta+2theta^2<1 and the Lyapunov exponent. I spot-checked the load-bearing identities—the factor expansions (26), the mass decomposition (24)–(25), the equalization Lemma 5.2, the matching bound (40), the recursions (49)–(53), the drift identity (65), and the bounded-rank prefix bound (B.1)—and found them internally consistent. The projection identity at the heart of Theorem 4.1 is proved for every s in [0,U_i-1] on every block, including empty gaps, zero steps, and unselected long steps inside gaps.","major_comments":[{"comment":"The theorem's universal quantifier over every prescribed initial point x0 is not established by the written proof. Corollary 4.3 and the final scaling argument construct a normalized instance with initial point x̄0 = e0 and then only scale it, yielding x0 = R e0 in the basis chosen by the construction. Since the objective is allowed to depend on the prescribed initial point, the missing step is an orthogonal change of variables: choose U in O(d) with U e0 = x0/R and define f(x) = L R^2 F(U^T x/R), x* = 0; then the GD iterates satisfy x_t = R U x̄_t and the same suboptimality bound holds. This is a local repair, but as written the theorem's stated quantifier is not proved.","section":"Theorem 2.1 / proof of Theorem 2.1 in Section 6.4"}],"minor_comments":[{"comment":"The claimed Lean 4 formalization is referenced only by a URL, with no commit hash, toolchain version, build instructions, or list of formalized theorem statements. Without these details the formalization claim cannot be independently checked; please pin the artifact and specify exactly which statements (e.g., Theorem 2.1, Theorem 4.1, Proposition 5.1, Proposition 6.1) are formalized.","section":"Section 7 (Disclosure on the use of generative AI)"},{"comment":"The quantifier order in Theorem 2.1 should be clarified: the objective f and minimizer x* are allowed to depend on the prescribed initial point x0 as well as on T, L, R, and the schedule eta; Remark 2.2 currently mentions only the horizon and the schedule.","section":"Theorem 2.1 and Remark 2.2"},{"comment":"The reciprocal-factor expansion (26) is load-bearing and correct, but the derivation would be more readable if the intermediate identity chi_{i-1}^{-1} = U_{i-1}(H_{i-1}+H_i)/(c_i H_i) were shown explicitly before expanding.","section":"Section 5.1, Eq. (26)"},{"comment":"In the terminal-factor estimate (72), the final inequality 3q D_q <= 3 D_{q0} q0 uses D_q <= D_{q0}(q0+1)/(q+1) together with monotonicity of q(q0+1)/(q+1) in q; a one-sentence justification would prevent reader confusion.","section":"Appendix B.4, Eq. (72)"}],"recommendation":"minor_revision","confidential_remarks":"The proof is disclosed as having been developed by GPT-5.6 Sol Pro, and the claimed Lean formalization is not auditable in its current form. I did not find a mathematical reason to doubt the written proof, and my spot-checks of the central identities were consistent. However, given the intricacy of the argument, I would encourage the editor to require the authors to pin the formalization artifact (commit hash, toolchain, formalized statement list) as part of the revision, so that independent machine-checking is possible. This is a reproducibility concern rather than a mathematical one."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is the first lower bound for predetermined, horizon-dependent, nonnegative stepsize schedules for plain GD on smooth convex functions. The bound is Omega(T^{-p}) for every p > sqrt(2+sqrt(3)) ~ 1.9319, and it is a genuinely new separation between stepsize-based acceleration and the optimal O(T^{-2}) rate. The proof is a clever chain: a Moreau-envelope realization of a piecewise-constant gradient field, an order-free matching bound, and a Lyapunov cutoff argument. I re-derived the load-bearing identities (factor expansions, equalization lemma, matching bound, recursions, drift identity) and found them internally consistent; the threshold p* comes out correctly. The projection identity the reader singled out is actually proven for every s in [0, U_i-1] on every block, including empty gaps and unselected long steps, so that concern does not land. The rotational invariance behind the 'every prescribed initial point' quantifier is implicit rather than stated, but that is minor. The honest soft spot is epistemic. Section 7 discloses that GPT-5.6 Sol Pro produced the proof, with the authors supplying only the objective and a high-level resisting-oracle strategy. The claimed Lean formalization is a URL only: no commit hash, no toolchain pin, no build instructions, no list of formalized theorems. A single incorrect inequality in the matching or Lyapunov machinery would invalidate Theorem 2.1, and right now the manuscript offers no independent way to settle that. The proof is intricate but readable, and my spot-checks found no error. Minor limitations: the theorem does not reach the endpoint p*; the gap between the silver exponent ~1.2715 and ~1.9319 remains open. The self-citation to the authors' anytime acceleration work is appropriate because the settings differ. The bounded-rank constant c_Q depends on Q, but that is harmless. Who is this for? People working on first-order lower bounds, stepsize schedules, and the silver acceleration line. It is a solid subfield result, not a paradigm shift. It deserves a serious referee. My recommendation: send it to review, with the condition that the authors ship a pinned, compilable Lean artifact and ideally a human-written proof sketch of Sections 5 and 6. Without that, the verification burden on any reader is too high.","headline":"First lower bound for horizon-dependent stepsize schedules: the math looks consistent on inspection, but the GPT-generated proof and unauditable Lean artifact put the verification burden on the reader.","tokens_in":758,"tokens_out":980,"would_cite":true,"duration_ms":26138,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that no predetermined nonnegative stepsize schedule lets gradient descent beat a 1/T^1.9319 worst-case last-iterate rate on smooth convex problems.","keywords":["gradient descent","stepsize schedules","lower bound","last-iterate convergence","smooth convex optimization","silver stepsize","Moreau envelope","acceleration"],"falsifier":"Exhibit a single predetermined nonnegative stepsize schedule $\\eta$ and prove that, for every $L$-smooth convex $f$ with $\\|x_0-x^*\\|\\le R$, the last-iterate gap is $O(T^{-q})$ for some $q>p^*$ (say $q=1.95$); Theorem 2.1 asserts an $\\Omega(T^{-p})$ lower bound for every $p>p^*$, so such a schedule would be a direct counterexample. A more surgical check is to evaluate the functional $C_T(h)$ from (20) for that schedule on a sequence of horizons and show $C_T(h)\\ll T^{-p^*}$; since Corollary 4.3 says the worst-case gap equals $C_T(h)/2$, that would falsify the reduction immediately.","tokens_in":27566,"feed_emoji":"📉","tokens_out":14923,"duration_ms":119108,"temperature":0.7,"pith_summary":"This paper proves a structural limitation of stepsize-based acceleration: for every exponent $p > p^* = \\sqrt{2+\\sqrt{3}} \\approx 1.9319$, and for every prescribed nonnegative stepsize schedule $\\eta$, there exists a smooth convex problem on which gradient descent's last iterate is at least $c_p L R^2 (T+1)^{-p}$ from optimality. In plain terms, no schedule chosen in advance—no matter how long the steps or how they are ordered—can force plain gradient descent to converge faster than $T^{-1.9319}$ in the worst case over $L$-smooth convex functions. The consequence is that stepsize schedules alone cannot close the gap to Nesterov's optimal $O(T^{-2})$ rate without momentum. The paper's construction makes the hard instance explicit in dimension at most $T+1$, and it deliberately allows zero steps, arbitrarily large steps, and non-monotone objective values along the trajectory.","feed_headline":"Stepsize-only gradient descent cannot beat a 1/T^1.9319 rate","feed_subtitle":"Predetermined nonnegative step schedules alone cannot accelerate smooth convex optimization to the optimal 1/T^2 rate.","key_machinery":"The carrying object is the Moreau envelope of the support function of a convex hull: for $K=\\operatorname{conv}\\{0,g_0,\\dots,g_m\\}$ the paper sets $F(x)=\\min_z\\{\\sigma_K(z)+\\tfrac12\\|x-z\\|^2\\}$, whose gradient is exactly the Euclidean projection $\\Pi_K(x)$ onto $K$ (Lemma 4.2). The construction chooses orthogonal anchor points and block gradients so that, as long as each squared amplitude obeys $\\gamma_i^2\\le\\chi_i$ from (7), the projection at every visited iterate is the prescribed block gradient; the long-step transitions then move the trajectory from one anchor to the next, and the terminal gap equals $\\tfrac{1}{2H_m}\\prod_{i=0}^{m-1}\\gamma_i^2$ (Theorem 4.1). All schedule-dependence is thereby concentrated in the functional $C_T(h)$ from (20), whose lower bound is derived by ranking excesses, bounding the reciprocal chain value through two matchings (Proposition 5.1), and controlling residual schedule mass with a Lyapunov potential.","core_discovery":"The central claim is Theorem 2.1: for each $p\\in(p^*,2)$ there is a constant $c_p>0$ such that, for every horizon $T$, every $L,R>0$, and every predetermined schedule $\\eta=(\\eta_0,\\dots,\\eta_{T-1})$ of nonnegative stepsizes, there is an $L$-smooth convex $f$ in some dimension $d\\le T+1$ with a minimizer $x^*$ at distance $R$ from the initialization for which the last-iterate gap satisfies $f(x_T)-f(x^*) \\ge c_p L R^2(T+1)^{-p}$. This establishes an $\\Omega(T^{-p})$ lower bound for all $p>p^*$, hence rules out any asymptotic last-iterate rate faster than $T^{-p^*}$ for stepsize-only gradient descent. The endpoint $p=p^*$ itself is left open, as is the gap to the known silver-ratio upper bound $O(T^{-\\log_2(1+\\sqrt2)})$. The paper frames the result as the first rigorous evidence that predetermined stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ rate.","pith_inferences":["The way the threshold $p^*$ emerges from the matching condition $2\\theta+2\\theta^2<1$ suggests that any improvement toward $T^{-2}$ would need a sharper total-weight estimate for matchings, not merely longer schedules; testing whether the matching lemma can be sharpened is a natural next step.","The same Moreau-envelope construction is modular enough to be reused for other deterministic first-order methods whose iterates stay in the span of past gradients, for example extrapolated or averaged iterates; the paper does not claim such bounds, but the block-projection mechanism transfers.","A concrete check of the functional $C_T(h)$ from (20) for small horizons by exhaustive search over schedules would test the sharpness of the matching and Lyapunov estimates; if any schedule achieved $C_T(h)\\ll T^{-1.932}$ along a sequence, the proof's inequalities would be overestimates and the true exponent could be lower.","The bound's invariance to ordering and allowance of arbitrarily large steps suggests that adaptive feedback rules, which observe the function along the way, are the next class to test; the paper explicitly leaves signed and adaptive stepsizes open."],"forward_implications":["Every predetermined nonnegative stepsize schedule has a worst-case last-iterate rate no faster than $\\Omega(T^{-p})$ for every $p>p^*$, so asymptotically the barrier is $T^{-1.9319}$.","Stepsize schedules alone cannot reach the $O(T^{-2})$ rate of Nesterov acceleration; the acceleration seen from silver stepsizes is real but bounded away from optimal.","The lower bound applies even when zero steps, arbitrarily large steps, or non-monotone objective values are allowed, and it uses only $T+1$ dimensions.","The silver-ratio upper bound $O(T^{-\\log_2(1+\\sqrt2)})\\approx O(T^{-1.2715})$ remains compatible with the lower bound, so the true exponent for stepsize-based acceleration lies somewhere between these two values.","Because the schedule may depend on the horizon $T$, the statement is about prescribed-horizon planning, not about single infinite anytime schedules, and it is not a consequence of the anytime lower bound."],"supporting_citations":[{"why":"It supplies the silver-stepsize schedule, the strongest known stepsize-only upper bound ($O(T^{-\\log_2(1+\\sqrt2)})$) against which the lower bound is aimed.","marker":"Altschuler and Parrilo (2025b)"},{"why":"It presents the other concurrent long-step acceleration construction; the lower bound covers exactly this scheduling family.","marker":"Grimmer et al. (2025b)"},{"why":"It gives the classical $\\Omega(T^{-2})$ oracle lower bound for general first-order methods, the benchmark the paper shows stepsize schedules cannot reach.","marker":"Drori (2016)"},{"why":"It defines the optimal $O(T^{-2})$ rate achieved with momentum, the target that the lower bound separates from stepsize-only gradient descent.","marker":"Nesterov (1983)"},{"why":"It establishes the concurrent anytime lower bound the paper contrasts with, clarifying why prescribed-horizon schedules require a separate bound.","marker":"Tsai et al. (2026)"},{"why":"It provides the textbook $O(T^{-1})$ baseline for constant-stepsize gradient descent that silver-type schedules improve on.","marker":"Bubeck (2015)"},{"why":"It extends silver schedules to arbitrary prescribed horizons by concatenation, completing the upper-bound picture the theorem constrains.","marker":"Zhang and Jiang (2024)"},{"why":"It composes optimized step schedules to arbitrary horizons, another ingredient in the upper-bound landscape.","marker":"Grimmer et al. (2025a)"}],"fun_headline_variants":["Stepsize schedules alone can't beat 1/T^1.9319","Stepsize-only GD stuck at T^-1.9319","No stepsize trick reaches T^-2: new bound T^-1.9319","Stepsize schedules capped at 1/T^1.9319, not 1/T^2","Lower bound: stepsize-only GD cannot reach T^-2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's load-bearing premise is the geometric realization theorem: for every selection of long steps with squared amplitudes satisfying $0<\\gamma_i^2\\le\\chi_i$ in (7), the Moreau envelope's Euclidean projection onto $K$ equals the prescribed block gradient at every visited iterate, including the terminal block and all unhandled combinations of stepsize order; if that projection identity failed at any iterate, the constructed trajectory would not realize the chain value in (20) and the lower bound would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Stepsize schedules alone can't beat 1/T^1.9319","Stepsize-only GD stuck at T^-1.9319","No stepsize trick reaches T^-2: new bound T^-1.9319","Stepsize schedules capped at 1/T^1.9319, not 1/T^2","Lower bound: stepsize-only GD cannot reach T^-2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001039,"raw_usage":{"total_tokens":4379,"prompt_tokens":959,"completion_tokens":3420,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":3318}},"tokens_in":575,"tokens_out":3420,"duration_ms":21592,"temperature":1.0,"reasoning_tokens":3318,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:21:15.886319+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a single predetermined nonnegative stepsize schedule $\\eta$ and prove that, for every $L$-smooth convex $f$ with $\\|x_0-x^*\\|\\le R$, the last-iterate gap is $O(T^{-q})$ for some $q>p^*$ (say $q=1.95$); Theorem 2.1 asserts an $\\Omega(T^{-p})$ lower bound for every $p>p^*$, so such a schedule would be a direct counterexample. A more surgical check is to evaluate the functional $C_T(h)$ from (20) for that schedule on a sequence of horizons and show $C_T(h)\\ll T^{-p^*}$; since Corollary 4.3 says the worst-case gap equals $C_T(h)/2$, that would falsify the reduction immediately.","supporting_citations":[],"review_version":1}