Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$

Technical Breakdown of the Paper§

Core Problem and Contributions§

The Barzilai-Borwein (BB) method is a gradient-based optimization algorithm that has shown strong empirical performance, but its convergence theory remains incomplete. A key open question was whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. This paper provides a negative answer for dimensions $n \geq 4$ by constructing a nonempty open family of quadratics and initial points where BB converges but only linearly, with explicit rates $\rho_{\min}=10^{-6}$ and $\rho_{\max}=0.61$.

Mathematical Framework§

For a strictly convex quadratic $f(x) = \frac{1}{2}x^\top A x$ with $A \succ 0$, BB1 (long BB) updates: $$x_{k+1} = x_k - \alpha_k \nabla f(x_k), \quad \alpha_k = \frac{\|\nabla f(x_k)\|^2}{\nabla f(x_k)^\top A \nabla f(x_k)}.$$ The dynamics can be projected onto the simplex of eigenvalues of $A$ along the search direction. The paper studies the projectivized BB dynamics in dimension $n=4$ and constructs a nonresonant attracting seven-cycle. This cycle yields geometric bounds on the spectral components of the gradient: for each eigencomponent $i$, $$c_i \rho_{\min}^k \leq |\nabla_i f(x_k)| \leq C_i \rho_{\max}^k,$$ with $0 < \rho_{\min} < \rho_{\max} < 1$. Consequently, the gradient norm $\|\nabla f(x_k)\|$ and energy norm $\|x_k - x^*\|_A$ decay geometrically, ruling out superlinear convergence.

Construction and Proof Methodology§

The proof is computer-assisted. It: 1. Identifies a specific set of quadratics (eigenvalues) and an initialization that leads to a periodic orbit of period 7 in the projectivized dynamics. 2. Verifies that this cycle is attracting (stable) by checking eigenvalues of the Jacobian of the return map. 3. Uses interval arithmetic to rigorously bound the constants $\rho_{\min}, \rho_{\max}$.

The open set is then a small neighborhood of the constructed parameters and initialization.

Implications§

For practitioners, this means that BB1 can converge arbitrarily slowly (linearly) even on simple quadratics, contradicting the belief that it is often superlinear. The result extends to all $n \geq 4$ by embedding the 4D example into higher dimensions.

Code Snippet (Simulating the 7-cycle)§

import numpy as np

def bb1_step(x, A):
    grad = A @ x
    ag = A @ grad
    alpha = np.dot(grad, grad) / np.dot(grad, ag)
    return x - alpha * grad

# Construct A and initial x from paper's parameters
# (specific values omitted for brevity; refer to paper for exact numbers)
eigenvalues = np.array([1.0, 2.0, 3.0, 4.0])  # example
Q = np.eye(4)  # rotation to align with cycle
A = Q @ np.diag(eigenvalues) @ Q.T
x0 = np.array([0.1, 0.2, -0.1, 0.05])
x = x0
for k in range(100):
    x = bb1_step(x, A)
    if k % 7 == 0:
        print(f"Step {k}: ||grad|| = {np.linalg.norm(A @ x):.6e}")

Key Equations§

• Gradient norm bound: $c \rho_{\min}^k \leq \|\nabla f(x_k)\| \leq C \rho_{\max}^k$
• Objective gap: $f(x_k) - f(x^*) \propto \rho_{\min}^{2k}$

Conclusion§

This paper closes a long-standing open problem in optimization by showing that BB1 cannot be superlinear on a positive-measure set. The computer-assisted approach provides rigorous bounds and opens the door to further analysis of BB methods.