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

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=(κ(H)-1)/(κ(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échet differentiable at a stationary point and its derivative is self-adjoint and uniformly positive, every $γ\in(c_*,1)$, where $c_*=(κ(A_*)-1)/(κ(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.

Disclosure

“e strict gap between the quadratic threshold and the prescribed envelope rate then permits restarts in uniformly bounded blocks. The nonlinear frozen-model strategy and the block-restart framework were formulated by Shutai Yang; OpenAI language models assisted him in reorganizing parts of the proof and proposing candidate derivations for selected technical estimates. 12.1 Strict linearization and the local BB iterations Let H be a real Hilbert space, let U ⊂ H be open, and let F : U”

PDF page 25

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:00:40.327209Z

Structural counts