{"id":"7fda00ce-83af-47ea-ad8e-5d77fe97b230","arxiv_id":"2608.07839","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For either Barzilai-Borwein rule, the worst asymptotic gradient root factor on strongly convex quadratics is exactly (κ(H)-1)/(κ(H)+1), and the same constant governs local nonlinear convergence under strict differentiability.","lead":"Sharp worst-case convergence factors are proven for the Barzilai-Borwein gradient method, matching the classical spectral bound (κ-1)/(κ+1) in finite dimensions, Hilbert spaces, and local nonlinear settings. The result closes a long-standing gap between known upper and lower rates for this widely used optimization algorithm.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof is internally coherent and the strict-Fréchet assumption is explicitly scoped.","rationale":"The reader's weakest assumption correctly identifies strict Fréchet differentiability (12.3) as the least secure premise in the nonlinear result. I agree that this condition is load-bearing for Lemma 11, since the frozen-quadratic comparison requires uniform control of two-point secant quotients near the minimizer, not merely one-sided Fréchet differentiability at a point. However, the paper states this hypothesis explicitly, proves that C^2 with continuous second derivative implies it (Corollary 7), and does not claim the result under weaker regularity. I therefore do not treat it as an objection to correctness. I reviewed the main algebraic steps: the two-step normalized dynamics in Section 4, the periodic-orbit bound (Theorem 2), the invariant-measure reduction (Lemmas 6 and 7), the semi-uniform ergodic principle (Proposition 3 and Lemma 8), and the Hilbert-space spectral-measure analogues. None of these steps revealed an internal inconsistency. The nonlinear block-restart argument in the proof of Theorem 4 is intricate but coherent: the finite-horizon tracking estimate (Lemma 11) controls the nonlinear-quadratic discrepancy by a factor that vanishes with the initial radius, and the tightness construction with the nonquadratic polynomial is valid because the gradient of the perturbation vanishes on the balanced endpoint orbit. Thus the central claim, sharp worst-case rate c_H and its Hilbert-space and nonlinear analogues, appears supported by the manuscript's proof. The only residual risk is the complexity of the ergodic machinery, which is not machine-checked; a targeted re-derivation of the coboundary identity on a nontrivial example would be a reasonable verification step.","tokens_in":35752,"tokens_out":24973,"duration_ms":274017,"concrete_test":"Independently re-derive Lemma 4's coboundary identity (6.6) by symbolic expansion on a three-eigenvalue example, including a boundary state where an endpoint weight tends to zero; if the identity fails for a boundary case, the telescoping upper bound in Theorem 2 would need repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I found no internal gap sufficient to challenge the central claim. The finite-dimensional upper bound rests on the coboundary identity (6.6), the invariant-measure bound Lemma 7, and the semi-uniform principle Proposition 3; the telescoping and recurrence steps are consistent. The Hilbert-space extension mirrors this with endpoint bands and continuity sets, and the nonlinear localization's Lemma 11 genuinely requires the two-point modulus (12.3): without strict differentiability, the comparison of secant quotients would not hold uniformly, but the theorem explicitly assumes this condition and derives it from C^2 continuity in Corollary 7. The sharpness construction via F_{eta,ell} is internally consistent, with the secant quotients agreeing exactly with the quadratic balanced orbit. The weakest point remains the strict-Fréchet regularity, but it is a stated hypothesis rather than a hidden flaw.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript establishes sharp worst-case asymptotic convergence rates for the two Barzilai-Borwein (BB) rules on uniformly positive quadratics, in both finite dimensions and Hilbert space, and derives local nonlinear analogues under a strict differentiability condition on the gradient. In finite dimensions, for either fixed BB rule and an arbitrary positive first step, the gradient root factor is bounded by the initially active spectral interval ratio (b0-a0)/(b0+a0), implying the global worst-case constant c_H=(κ(H)-1)/(κ(H)+1). Under matched initialization, this constant is attained by balanced endpoint trajectories and is also the optimal uniform-envelope threshold. The proof introduces a two-step probability-measure dynamics, a coboundary identity with a nonnegative defect, and passes from periodic-orbit bounds to arbitrary trajectories via ergodic compactification and a semi-uniform ergodic principle. The Hilbert-space extension uses scalar spectral measures and endpoint bands, including purely continuous-spectrum examples. The nonlinear theorem shows that, under the two-point modulus condition (12.3), every γ>c_*=(κ(A_*)-1)/(κ(A_*)+1) is a uniform local envelope rate for either pure BB rule, and every convergent trajectory has error, gradient, and objective-gap root factors at most c_*, c_*, and c_*^2 respectively.","tokens_in":35817,"tokens_out":23534,"duration_ms":244152,"significance":"The paper settles the sharp worst-case asymptotic rate for the BB methods, a question that has been open despite substantial prior work. The finite-dimensional upper bound closes the gap between the known R-linear factor 1-1/κ and the endpoint-supported lower example, identifying the exact norm-level threshold. The uniform-envelope optimality and its extension to Hilbert space, including continuous spectrum, are natural and significant generalizations. The nonlinear localization under strict Fréchet differentiability of the gradient is a genuine improvement over earlier C^3 or locally Lipschitz-Hessian assumptions. The proofs are rigorous and largely self-contained, with explicit constants and a clear transfer of the finite-dimensional architecture to the spectral-measure setting. The use of ergodic optimization and coboundary certificates is elegant and provides new techniques for analyzing delayed gradient methods. The paper also includes an explicit disclosure of AI assistance in drafting, which is appropriate and does not affect the mathematics.","major_comments":[],"minor_comments":[{"comment":"In the statement of Theorem 4, the phrase \"there exist radii 0 < rγ ≤ rγ\" is a typo: the proof in Section 12.5 uses two distinct radii, the smaller one r_γ and the larger one r̄_γ, so the statement should use distinct symbols to avoid confusion.","section":"Theorem 4"},{"comment":"The recurrence following (5.5) is typeset ambiguously; it should read ζ_{k+1} = ζ_k / ζ_{k-1}^2, which is consistent with the logarithmic recurrence ν_{k+1}=ν_k-2ν_{k-1}.","section":"Proposition 2"},{"comment":"The sentence \"Sections A and 11 treat Hilbert spaces\" is awkward because Section A is an appendix and Section 11 is a main-text section; consider rephrasing to \"Section 11 and Appendix A\".","section":"Section 11.1"},{"comment":"The symbol r_γ is overloaded: in the proof it denotes both the smaller initial radius and, in the theorem statement, the larger containment ball. Please introduce distinct symbols, for example r_γ and r̄_γ, throughout.","section":"Section 12.5"},{"comment":"The manuscript contains several minor typographical inconsistencies (e.g., repeated rγ, occasional missing subscripts in exponents such as ζ^2_{k-1}) that should be cleaned up in the final version.","section":"General"}],"recommendation":"minor_revision","confidential_remarks":"I found the mathematical content sound and the contribution significant. The finite-dimensional and Hilbert-space proofs are coherent, and the nonlinear sharpness examples are convincing. The main issues are presentation-level notation problems in Theorem 4 and a few typos, all of which are easily fixable. The AI-use disclosure is complete and does not raise concerns. The paper is well suited to the journal; I recommend acceptance after minor revisions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Yang and Yuan settle the long-open question of the worst-case asymptotic rate for the Barzilai–Borwein method on strongly convex quadratics. The sharp constant is c_H = (κ−1)/(κ+1), the balanced endpoint orbit attains it, and every trajectory's root factor is controlled by its initially active spectral interval. The proof is real new work: the coboundary identity, the periodic-orbit bound, and the passage through invariant measures fit together coherently. The Hilbert-space extension is not a token remark; it handles continuous spectra and gets the same sharp envelope threshold under matched initialization. The nonlinear localization under strict Fréchet differentiability of the gradient is a genuine improvement over the Lipschitz-Hessian assumptions used before, and the sharpness examples, including the C^∞ nonquadratic construction, are explicit and checkable.\n\nThe soft spots are real but not load-bearing. The nonlinear theorem needs strict Fréchet differentiability of the gradient, which is stronger than ordinary Fréchet; the authors state this clearly, but it means the local result does not cover every reasonable C^1 objective. The Hilbert-space appendix is long and intricate, and the ergodic machinery—compactification, semi-uniform principles, measurable support reduction—is not machine-checked. A careful referee will need to verify the measurable-set details, especially in Lemma 14 and Proposition 7. The paper is also very long; the main ideas could have been presented more crisply. None of this threatens the central claim, which I find convincing.\n\nWho gets value: anyone working on gradient methods, Barzilai–Borwein theory, or ergodic optimization applied to numerical algorithms. It deserves a serious referee. I would send it out rather than desk-reject, and I expect a careful referee to confirm the proof after checking the Hilbert-space appendix.","headline":"The sharp BB rate is now known: c_H, attained by endpoint orbits, with a clean proof and an honest nonlinear extension under strict Fréchet differentiability.","tokens_in":36390,"tokens_out":1149,"would_cite":true,"duration_ms":14951,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","65K05","47A10","37A30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The sharp worst-case asymptotic rate of the Barzilai–Borwein method is the condition-number ratio $c_H=(\\kappa(H)-1)/(\\kappa(H)+1)$.","keywords":["Barzilai–Borwein method","sharp asymptotic rate","R-linear convergence","gradient method","spectral measure","Hilbert space","nonlinear localization","ergodic optimization"],"falsifier":"For the quadratic $H=\\mathrm{diag}(1,4)$ with BB1, take $g_0=(1,1)/\\sqrt{2}$ and matched first step $\\alpha_0=2/5$. The theorem predicts $\\|g_k\\|=(3/5)^k\\|g_0\\|$ for every $k$; any exact recurrence or numerical iteration that produces a larger asymptotic root factor would refute the claimed universal upper bound.","tokens_in":35505,"feed_emoji":"📉","tokens_out":9323,"duration_ms":92205,"temperature":0.7,"pith_summary":"This paper pins down the exact worst-case asymptotic slowdown of the two Barzilai–Borwein (BB) step-size rules, a long-standing gap in gradient-method theory. On any strongly convex quadratic with Hessian $H$, the claim is that for either pure BB rule and any positive first step, the asymptotic root factor of the gradient norm is at most $c_H=(\\kappa(H)-1)/(\\kappa(H)+1)$, where $\\kappa(H)$ is the condition number. A balanced initial gradient on the extreme eigenspaces attains this factor exactly under matched initialization, so $c_H$ is also the optimal uniform-envelope threshold. The same constant governs bounded uniformly positive operators in Hilbert space, including operators with purely continuous spectrum, and locally governs strictly differentiable nonlinear problems near a nondegenerate minimizer. This matters because it replaces a cluster of partial and componentwise bounds with one exact, parameter-free answer.","feed_headline":"Barzilai–Borwein's worst-case rate is exactly (κ−1)/(κ+1)","feed_subtitle":"The bound is sharp for both BB rules, in Hilbert space, and near nonlinear minimizers.","key_machinery":"The central object is the delayed Rayleigh quotient and its normalized two-step dynamics. For BB1, the step $\\alpha_k$ is the inverse of the mean eigenvalue $u(w_{k-1})=\\sum_i \\lambda_i w_{k-1,i}$ of the normalized squared spectral energies $w_{k-1}$; the state $\\chi_k=(w_k,w_{k-1})$ evolves by $T(w,z)=(\\phi(z)\\odot w/\\langle\\phi(z),w\\rangle,\\,w)$ with $\\phi_i(z)=(1-\\lambda_i/u(z))^2$, and the per-step norm factor is $r(w,z)=\\langle\\phi(z),w\\rangle^{1/2}$. The proof is carried by the coboundary identity $\\log r(\\chi)=\\log c_J-D(\\chi)+h(T\\chi)-h(\\chi)$, where the nonnegative defect $D$ measures how far the current mean eigenvalue lies from the midpoint of the active spectral interval and the boundary term $h\\circ T-h$ telescopes along an orbit. Poincare recurrence, Birkhoff's theorem, and a semi-uniform ergodic principle convert the invariant-measure bound into a finite-horizon trajectory bound. The Hilbert-space extension replaces coordinate faces by scalar spectral measures and endpoint coordinates by shrinking endpoint bands.","core_discovery":"The paper establishes that the Barzilai–Borwein method has a sharp worst-case asymptotic rate. For either pure BB rule on a uniformly positive quadratic with Hessian $H$, every trajectory with an arbitrary positive first step has gradient root factor at most $(b_0-a_0)/(b_0+a_0)$, where $[a_0,b_0]$ is the spectral interval spanned by the initial gradient's components, and hence at most $c_H=(\\kappa(H)-1)/(\\kappa(H)+1)$. With matched initialization and equal endpoint energies on the extreme eigenspaces, an orbit satisfies $\\|g_k\\|=c_H^k\\|g_0\\|$ exactly, so the constant is attained. Under matched initialization the same constant is the optimal uniform-envelope threshold. In Hilbert space, scalar spectral measures give the same active-support bound and the same threshold $c_A=(M-m)/(M+m)$, even when the spectral endpoints lie in the continuous spectrum. Locally, if the gradient is strictly Frechet differentiable at a stationary point with uniformly positive self-adjoint derivative $A_*$, then every $\\gamma\\in(c_*,1)$ with $c_*=(\\kappa(A_*)-1)/(\\kappa(A_*)+1)$ is a uniform local envelope rate for either pure BB rule, every convergent trajectory has error and gradient root factors at most $c_*$ and objective-gap root factor at most $c_*^2$, and both quadratic and $C^{\\infty}$ genuinely nonquadratic objectives in $\\mathbb{R}^2$ attain the threshold.","pith_inferences":["A direct extension the paper leaves implicit: the same coboundary certificate should give sharp rates for other two-step gradient rules whose step is a monotone function of a Rayleigh quotient, whenever the extremal fixed state is unique.","Because the sharp constant depends only on the spectrum, the results suggest that any practical improvement over BB must alter the extremal dynamics, for example through restarts or adaptive rule switching, rather than the step formula itself.","A testable numerical consequence is that near the sharp threshold the empirical spectral measure of a worst-case trajectory must concentrate on the balanced endpoint state; measuring this concentration would distinguish the sharp regime from generic faster convergence.","The fixed-horizon comparison in the nonlinear theorem could likely be sharpened to track how the envelope constant degrades continuously as the two-point modulus $\\omega(r)$ grows, giving explicit local constants for specific smoothness classes."],"forward_implications":["The sharp root factor for the error norm $\\|x_k-x_*\\|$ is also $c_H$, while the objective gap has root factor $c_H^2$, so a quadratic gap contraction is governed by the square of the condition-number ratio.","Fixed positive weighted delayed rules, including BB2, inherit the same bound through spectral conjugacy; no fixed spectral reweighting can lower the threshold.","In Hilbert space, operators whose spectral endpoints lie only in the continuous spectrum still obey the same optimal uniform-envelope threshold $c_A=(M-m)/(M+m)$, and a fully continuous-spectrum trajectory attains $c_A$.","Under strict Frechet differentiability of the gradient at a nondegenerate minimizer, the pure BB rules converge locally with any envelope rate above $c_*$, independently of the initial secant.","Over the class of objectives with prescribed derivative endpoints $m_*,M_*$, the threshold $c_*$ is sharp, and matched endpoint trajectories for both quadratic and genuinely nonquadratic smooth objectives in $\\mathbb{R}^2$ attain it."],"supporting_citations":[{"why":"Introduces the BB1 and BB2 two-point secant steps whose sharp worst-case asymptotics are the paper's subject.","marker":"[4]"},{"why":"Establishes R-linear convergence of the BB method in finite-dimensional strictly convex quadratics, the qualitative rate the paper makes sharp.","marker":"[8]"},{"why":"Provides the componentwise factor $1-1/\\kappa(H)$ and an endpoint-supported trajectory with exact factor $c_H$ that calibrates the lower bound.","marker":"[17]"},{"why":"Derives the two-dimensional logarithmic recurrence and isolates the equal-energy linear orbit, which the paper's extremal-state analysis extends.","marker":"[5]"},{"why":"Supplies spectrally uniform R-linear convergence for BB steps in Hilbert spaces, the setting the paper sharpens to an exact threshold.","marker":"[2]"},{"why":"Gives the semi-uniform ergodic principle used to pass from invariant-measure averages to finite-horizon trajectory bounds.","marker":"[22]"},{"why":"Provides the coboundary and ergodic-optimization viewpoint behind the endpoint certificate.","marker":"[14]"}],"fun_headline_variants":["BB method's worst-case rate is exactly (κ−1)/(κ+1)","Sharp worst-case rate for Barzilai–Borwein equals (κ−1)/(κ+1)","Barzilai–Borwein hits (κ−1)/(κ+1) as sharp envelope","Worst-case BB rate: (κ−1)/(κ+1), now proven sharp","BB gradient root factor capped at (κ−1)/(κ+1) in Hilbert space"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The nonlinear half of the theorem rests on assumption (12.3): the two-point modulus $\\omega(r)$ of the gradient's deviation from its linearization must vanish as $r\\to 0$, a condition strictly stronger than ordinary Frechet differentiability; without it, the local envelope and root-factor conclusions are unsupported.","fun_headline_variants_meta":{"raw":{"variants":["BB method's worst-case rate is exactly (κ−1)/(κ+1)","Sharp worst-case rate for Barzilai–Borwein equals (κ−1)/(κ+1)","Barzilai–Borwein hits (κ−1)/(κ+1) as sharp envelope","Worst-case BB rate: (κ−1)/(κ+1), now proven sharp","BB gradient root factor capped at (κ−1)/(κ+1) in Hilbert space"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000173,"raw_usage":{"total_tokens":1403,"prompt_tokens":1193,"completion_tokens":210,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":809,"completion_tokens_details":{"reasoning_tokens":91}},"tokens_in":809,"tokens_out":210,"duration_ms":3317,"temperature":1.0,"reasoning_tokens":91,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:49:13.624517+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the quadratic $H=\\mathrm{diag}(1,4)$ with BB1, take $g_0=(1,1)/\\sqrt{2}$ and matched first step $\\alpha_0=2/5$. The theorem predicts $\\|g_k\\|=(3/5)^k\\|g_0\\|$ for every $k$; any exact recurrence or numerical iteration that produces a larger asymptotic root factor would refute the claimed universal upper bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Derives the two-dimensional logarithmic recurrence and isolates the equal-energy linear orbit, which the paper's extremal-state analysis extends."},{"cited_title":"Azmi and K","cited_arxiv_id":null,"evidence_quote":"Supplies spectrally uniform R-linear convergence for BB steps in Hilbert spaces, the setting the paper sharpens to an exact threshold."},{"cited_title":"Sturman and J","cited_arxiv_id":null,"evidence_quote":"Gives the semi-uniform ergodic principle used to pass from invariant-measure averages to finite-horizon trajectory bounds."}],"review_version":1}