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=(\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_*