Pith. sign in

REVIEW 5 minor 23 references

The Sharp Worst-Case Asymptotic Rate of the Barzilai--Borwein Method in $\mathbb R^d$ and Hilbert Spaces

T0 review · 0 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The sharp worst-case asymptotic rate of the Barzilai–Borwein method is the condition-number ratio $c_H=(\kappa(H)-1)/(\kappa(H)+1)$.

desk verdict 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. read the letter →

arxiv 2608.07839 v1 pith:HH6GOVR4 submitted 2026-08-08 math.NA cs.NAmath.OC

Shutai Yang , Ya-Xiang Yuan This is my paper · ORCID
classification math.NAcs.NAmath.OC MSC 90C2565K0547A1037A30
keywords Barzilai–BorweinmethodsharpasymptoticrateR-linearconvergencegradientspectralmeasureHilbertspacenonlinearlocalizationergodicoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

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.

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.

minor comments (5)
  1. [Theorem 4] 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.
  2. [Proposition 2] 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}.
  3. [Section 11.1] 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".
  4. [Section 12.5] 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.
  5. [General] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sharp bounds are derived from the BB dynamics and independently constructed extremal orbits, with prior endpoint-orbit facts re-proved in the paper.

full rationale

The paper's central claims pass the circularity screen. The finite-dimensional upper bound ρH(g0, α0) ≤ c(g0) ≤ cH is derived from the normalized two-step dynamics (Section 4), the coboundary identity (6.6), the invariant-measure bound (Lemma 7), and the semi-uniform ergodic principle (Proposition 3); none of these ingredients assumes the target inequality. The matching lower bound is constructed explicitly in Proposition 1 via a balanced two-endpoint orbit and verified by exact computation, so the supremum assertion (2.9) is not a fitted input renamed as a prediction. The Hilbert-space extension (Theorem 3) uses scalar spectral measures and endpoint bands in place of coordinates, with the invariant-average bound proved in Proposition 6 rather than imported. The nonlinear localization (Theorem 4) explicitly assumes strict Fréchet differentiability through the two-point modulus condition (12.3) and derives the local envelope by a frozen-quadratic finite-horizon comparison (Lemma 11) followed by a block-restart argument; the sharpness examples F_{η,ℓ} are constructed so that their secant quotients agree exactly with the quadratic endpoint orbit, which is a genuine counterexample, not a restatement of the theorem. Prior work by Li and Sun on endpoint-supported trajectories is cited but also re-proved as Proposition 1, so no load-bearing conclusion depends on an unverified self-citation. The passages disclosing AI-assisted drafting are transparency statements and do not function as mathematical premises. No step was found in which a defined quantity secretly contains the claimed conclusion or in which a fitted parameter is presented as a prediction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities. The sharp constant is derived, not fitted; the balanced endpoint orbit is constructed in both quadratic and nonquadratic examples. The proof relies on standard spectral and ergodic facts plus the explicitly stated uniform-positivity and strict-differentiability assumptions.

assumptions (5)
  • standard math Spectral theorem and functional calculus for bounded self-adjoint operators
    Used throughout Sections 11 and A to reduce BB dynamics on Hilbert space to scalar spectral measures.
  • standard math Ergodic decomposition, Poincaré recurrence, and Birkhoff's pointwise ergodic theorem
    Used in Sections 8 and A to pass from exact periodic orbits to arbitrary trajectories via invariant measures.
  • standard math Semi-uniform ergodic principle of Sturman and Stark
    Imported from reference [22]; provides the finite-horizon additive bound used in Lemma 8 and in the Hilbert-space proof.
  • domain assumption Uniform positivity of the Hessian or operator: 0 < mI <= H <= MI
    Central setting in (1.1) and (11.1); the sharp constants are defined through the eigenvalue or spectral interval endpoints.
  • domain assumption Strict differentiability of the gradient at the stationary point via the vanishing two-point modulus (12.3)
    Stronger than ordinary Fréchet differentiability; needed for the nonlinear comparison Lemma 11 and the local envelope theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Sharp Worst-Case Asymptotic Rate of the Barzilai--Borwein Method in $\mathbb R^d$ and Hilbert Spaces." pith.science (2026). https://pith.science/paper/HH6GOVR4

@misc{pith2026260807839,
  author       = {Pith},
  title        = {Pith review of: The Sharp Worst-Case Asymptotic Rate of the Barzilai--Borwein Method in $\mathbb R^d$ and Hilbert Spaces},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HH6GOVR4}},
  note         = {Machine review of arXiv:2608.07839}
}
abstract

We establish sharp asymptotic rates for the two Barzilai--Borwein (BB) rules on uniformly positive quadratics and local nonlinear problems. In finite dimensions, for either fixed rule and an arbitrary positive first step, the gradient root factor is bounded by $(b_0-a_0)/(b_0+a_0)$, where $[a_0,b_0]$ is the initially active spectral interval. Hence the worst trajectory factor is $c_H=(\kappa(H)-1)/(\kappa(H)+1)$. When $H$ has at least two distinct eigenvalues, matched initialization and a balanced endpoint trajectory attain this value. Under matched initialization, the same constant is the optimal uniform-envelope threshold. For bounded, self-adjoint, uniformly positive operators on Hilbert space, scalar spectral measures yield the corresponding active-support bound and optimal matched uniform-envelope threshold, including continuous endpoint spectrum. Finally, if the gradient is strictly Fr\'echet differentiable at a stationary point and its derivative is self-adjoint and uniformly positive, every $\gamma\in(c_*,1)$, where $c_*=(\kappa(A_*)-1)/(\kappa(A_*)+1)$, is a uniform local envelope rate for either pure BB rule. Every well-defined trajectory converging to the stationary point has error and gradient root factors at most $c_*$ and objective-gap root factor at most $c_*^2$. Over the class of objectives with prescribed distinct derivative endpoints $m_*<M_*$, matched endpoint trajectories for quadratic and $C^\infty$ genuinely nonquadratic examples in $\mathbb R^2$ attain these factors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 15 canonical work pages

  1. [1]

    H. Akaike. On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method.Annals of the Institute of Statistical Mathematics, 11(1):1–16, 1959.https://doi.org/10.1007/BF01831719

    work page doi:10.1007/bf01831719 1959

  2. [2]

    Azmi and K

    B. Azmi and K. Kunisch. Analysis of the Barzilai–Borwein step-sizes for problems in Hilbert spaces.Journal of Optimization Theory and Applications, 185(3):819–844, 2020. https://doi.org/10.1007/s10957-020-01677-y

    work page doi:10.1007/s10957-020-01677-y 2020

  3. [3]

    Azmi and K

    B. Azmi and K. Kunisch. On the convergence and mesh-independent property of the Barzilai–Borwein method for PDE-constrained optimization.IMA Journal of Numerical Analysis, 42(4):2984–3021, 2022.https://doi.org/10.1093/imanum/drab056

    work page doi:10.1093/imanum/drab056 2022

  4. [4]

    Barzilai and J

    J. Barzilai and J. M. Borwein. Two-point step size gradient methods.IMA Journal of Numerical Analysis, 8(1):141–148, 1988.https://doi.org/10.1093/imanum/8.1.141

    doi:10.1093/imanum/8.1.141 1988

  5. [5]

    Y.-H. Dai. A new analysis on the Barzilai–Borwein gradient method.Journal of the Operations Research Society of China, 1(2):187–198, 2013. https://doi.org/10.1007/ s40305-013-0007-x

    work page 2013

  6. [6]

    Dai and R

    Y.-H. Dai and R. Fletcher. On the asymptotic behaviour of some new gradient methods.Mathematical Programming, 103(3):541–559, 2005. https://doi.org/10.1007/ s10107-004-0516-9

    work page 2005

  7. [7]

    Y.-H. Dai, W. W. Hager, K. Schittkowski, and H. Zhang. The cyclic Barzilai–Borwein method for unconstrained optimization.IMA Journal of Numerical Analysis, 26(3):604–627, 2006.https://doi.org/10.1093/imanum/drl006

    work page doi:10.1093/imanum/drl006 2006

  8. [9]

    Fletcher

    R. Fletcher. On the Barzilai–Borwein method. In L. Qi, K. L. Teo, and X. Yang, editors, Optimization and Control with Applications, volume 96 ofApplied Optimization, pages 235–256. Springer, Boston, 2005.https://doi.org/10.1007/0-387-24255-4_10

    work page doi:10.1007/0-387-24255-4_10 2005

Show all 23 references
  1. [10]

    G. E. Forsythe. On the asymptotic directions of thes-dimensional optimum gradient method. Numerische Mathematik, 11(1):57–76, 1968.https://doi.org/10.1007/BF02165472

    1968 doi

  2. [11]

    Friedlander, J

    A. Friedlander, J. M. Mart ´ ınez, B. Molina, and M. Raydan. Gradient method with retards and generalizations.SIAM Journal on Numerical Analysis, 36(1):275–289, 1999. https: //doi.org/10.1137/S003614299427315X

    1999 doi

  3. [12]

    Huang, Y.-H

    Y. Huang, Y.-H. Dai, X.-W. Liu, and H. Zhang. On the acceleration of the Barzilai– Borwein method.Computational Optimization and Applications, 81(3):717–740, 2022. https://doi.org/10.1007/s10589-022-00349-z

    2022 doi

  4. [13]

    Huang, Y.-H

    Y. Huang, Y.-H. Dai, X.-W. Liu, and H. Zhang. On the asymptotic convergence and acceleration of gradient methods.Journal of Scientific Computing, 90:7, 2022. https: //doi.org/10.1007/s10915-021-01685-8

    2022 doi

  5. [14]

    Jenkinson

    O. Jenkinson. Ergodic optimization in dynamical systems.Ergodic Theory and Dynamical Systems, 39(10):2593–2618, 2019.https://doi.org/10.1017/etds.2017.142

    2019 doi

  6. [15]

    Li and Y.-K

    X.-R. Li and Y.-K. Huang. A note on R-linear convergence of nonmonotone gradient methods.Journal of the Operations Research Society of China, 13(1):313–325, 2025. https://doi.org/10.1007/s40305-023-00468-2. Sharp Worst-Case Asymptotic Rate of BB 51

    2025 doi

  7. [16]

    D. Li, X. Jiang, and M. Hong. Barzilai–Borwein fails superlinear convergence on an open set of quadratics for every dimension n≥ 4. Preprint, arXiv:2607.21579v1, 2026. https://doi.org/10.48550/arXiv.2607.21579

    2026 doi arXiv

  8. [17]

    Li and R

    D. Li and R. Sun. On a faster R-linear convergence rate of the Barzilai–Borwein method. Preprint, arXiv:2101.00205v2, 2021.https://doi.org/10.48550/arXiv.2101.00205

    2021 doi arXiv

  9. [18]

    Liu and Y.-H

    W. Liu and Y.-H. Dai. Minimization algorithms based on supervisor and searcher cooperation.Journal of Optimization Theory and Applications, 111(2):359–379, 2001. https://doi.org/10.1023/A:1011986402461

    2001 doi

  10. [19]

    Nocedal, A

    J. Nocedal, A. Sartenaer, and C. Zhu. On the behavior of the gradient norm in the steepest descent method.Computational Optimization and Applications, 22(1):5–35, 2002. https://doi.org/10.1023/A:1014897230089

    2002 doi

  11. [20]

    Pronzato, H

    L. Pronzato, H. P. Wynn, and A. A. Zhigljavsky. Asymptotic behaviour of a family of gradient algorithms in Rd and Hilbert spaces.Mathematical Programming, 107(3):409–438, 2006.https://doi.org/10.1007/s10107-005-0602-7

    2006 doi

  12. [21]

    M. Raydan. On the Barzilai and Borwein choice of steplength for the gradient method.IMA Journal of Numerical Analysis, 13(3):321–326, 1993. https://doi.org/10.1093/imanum/ 13.3.321

    1993 doi

  13. [22]

    Sturman and J

    R. Sturman and J. Stark. Semi-uniform ergodic theorems and applications to forced systems. Nonlinearity, 13(1):113–143, 2000.https://doi.org/10.1088/0951-7715/13/1/306

    doi

  14. [23]

    Walters.An Introduction to Ergodic Theory

    P. Walters.An Introduction to Ergodic Theory. Graduate Texts in Mathematics, vol. 79. Springer, New York, 1982.https://doi.org/10.1007/978-1-4612-5775-2

    1982 doi

  15. [24]

    Zou and F

    Q. Zou and F. Magoul` es. Delayed gradient methods for symmetric and positive definite linear systems.SIAM Review, 64(3):517–553, 2022. https://doi.org/10.1137/20M1321140

    2022 doi

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.