Cycle-breaking BB optimizer
Implementation & benchmark of arXiv:2607.21579 — Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$
Source paper: Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$ arXiv:2607.21579 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use BB1 for inexpensive curvature adaptation, but monitor the projective gradient state for the periodic behavior identified in the paper. When the normalized gradient and scalar step size approximately repeat after seven iterations, temporarily switch to BB2 or a damped gradient step to destroy the attracting cycle, then return to BB1.
Formulas
Mathematical statement
For f(x)=1/2 x^T A x with positive-definite A, let g_k=
abla f(x_k), s_{k-1}=x_k-x_{k-1}, and y_{k-1}=g_k-g_{k-1}. The BB1 step is alpha_k^BB1=(s_{k-1}^T s_{k-1})/(s_{k-1}^T y_{k-1}); BB2 is alpha_k^BB2=(s_{k-1}^T y_{k-1})/(y_{k-1}^T y_{k-1}). If d_k^i is the gradient component along eigenvector i of A with eigenvalue lambda_i, then alpha_k^BB1=(sum_j (d_k^j)^2)/(sum_j lambda_j(d_k^j)^2), and d_{k+1}^i=d_k^i[sum_j(lambda_j-lambda_i)(d_k^j)^2]/[sum_j lambda_j(d_k^j)^2]. The paper constructs an attracting seven-cycle in the normalized, or projectivized, state in dimension four. Its component magnitudes obey geometric lower and upper rates with explicit constants rho_lower=10^-6 and rho_upper=0.61, so a repeating normalized state need not yield superlinear convergence. For neural networks, eigenvectors are unavailable; use the normalized-gradient projector proxy P_k=g_k g_k^T/(g_k^T g_k), or the scalar cosine D_k=1-(g_k^T g_{k-7})^2/[(g_k^T g_k)(g_{k-7}^T g_{k-7})].
Implementation notes
1. Integration point: replace the scalar learning-rate calculation in a full-batch or low-noise optimizer for a flattened parameter vector theta. For large models, apply the rule independently to parameter blocks or layers. Store theta_{t-1}, g_{t-1}, the last seven normalized gradients, and the last seven scalar step sizes. 2. Pseudocode: compute g_t. If t>0, set s=theta_t-theta_{t-1}, y=g_t-g_{t-1}, a1=(s dot s)/(s dot y+delta), and a2=(s dot y)/(y dot y+delta); clip both to [alpha_min,alpha_max]. Set q_t=g_t/(||g_t||+delta). If t>=7, compute D=1-(q_t dot q_{t-7})^2 and c=abs(log(a1/(a_{t-7}+delta))). If D<epsilon_q and c<epsilon_alpha for m consecutive checks, enter fallback mode for r updates and choose a2 or 0.5*a2; otherwise choose a1. Update theta_{t+1}=theta_t-alpha_t g_t, then append q_t and alpha_t. 3. The BB formulas and projective-dynamics interpretation come from the paper. The implementation estimates recurrence empirically from normalized gradients, rather than estimating the Hessian eigenvalues. Use delta=1e-12, epsilon_q=1e-3, epsilon_alpha=0.05, m=2, r=7, and set alpha_min and alpha_max from a warmup, such as [1e-6,10 times the median warmup step]. 4. First experiment: optimize a 4D diagonal quadratic with eigenvalues [1,3,10,30] from many random initializations, comparing BB1, BB2, clipped BB1, and the cycle-breaking rule. Then train a 2-layer MLP on MNIST with full batches or batch size 4096. Record objective gap, gradient norm, trigger frequency, loss oscillation, time to a fixed loss, and final accuracy. Success means fewer long plateaus or lower loss at equal gradient evaluations specifically on runs where BB1 exhibits seven-step recurrence, with no substantial degradation on non-triggered runs.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.