Safeguarded delayed-Rayleigh BB optimizer
Implementation & benchmark of arXiv:2608.07839 — The Sharp Worst-Case Asymptotic Rate of the Barzilai--Borwein Method in $\mathbb R^d$ and Hilbert Spaces
Source paper: The Sharp Worst-Case Asymptotic Rate of the Barzilai--Borwein Method in $\mathbb R^d$ and Hilbert Spaces arXiv:2608.07839 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace the scalar learning rate of SGD or Adam's outer update by a blockwise Barzilai--Borwein estimate computed from consecutive parameters and gradients. Use gradient smoothing, denominator checks, and clipping so that the curvature estimate remains usable with stochastic neural-network gradients.
Formulas
Mathematical statement
For the quadratic q(x) = (1/2)x^T H x - b^T x, H = H^T is positive definite, the minimizer is x_* = H^(-1)b and the gradient is g_k = H(x_k - x_*). The BB1 iteration is x_(k+1) = x_k - alpha_k g_k, with alpha_k = (g_(k-1)^T g_(k-1))/(g_(k-1)^T H g_(k-1)). Since g_k - g_(k-1) = -alpha_(k-1) H g_(k-1), the Hessian-vector product can be inferred from successive gradients. Therefore the implementable delayed estimate is alpha_hat_k = alpha_(k-1) ||g_(k-1)||^2 / (g_(k-1)^T (g_(k-1) - g_k)). If the active eigenvalues of H lie in [a_0,b_0], the paper proves the sharp worst-case gradient root factor c_H = (b_0-a_0)/(b_0+a_0) = (kappa(H)-1)/(kappa(H)+1), where kappa(H) = b_0/a_0; the objective-gap root factor is at most c_H^2. In the nonlinear local result, H is replaced by the self-adjoint uniformly positive derivative of the gradient at a stationary point. The neural-network adaptation uses the same finite-difference Rayleigh estimate, while treating the spectral interval and noise level as empirically estimated rather than known.
Implementation notes
Integrate the method at the learning-rate operation of SGD, initially using one scalar step size per parameter block, such as each Transformer layer, attention projection, or MLP block. For every block, store the previous smoothed gradient g_prev, the previous accepted step alpha_prev, and the current parameter tensor. At iteration k, compute the current gradient g on a fixed or accumulated minibatch, optionally form an exponential moving average g_smooth = rho times g_prev_smooth plus (1-rho) times g, and set d = g_prev_smooth - g_smooth. Compute r = inner_product(g_prev_smooth, d). If r is positive and larger than epsilon times the norms of the two vectors, propose alpha_prop = alpha_prev times squared_norm(g_prev_smooth) divided by r; otherwise retain alpha_prev. Smooth the proposal with alpha = beta times alpha_prop plus (1-beta) times alpha_prev, then clip alpha to [alpha_min, alpha_max], for example [10^(-6), 10] times the baseline learning rate. Apply x_new = x - alpha times g_smooth. Apply decoupled weight decay separately so the BB estimate measures the loss gradient rather than regularization. With minibatches, accumulate gradients over 4 to 16 batches or use a large validation batch before updating alpha, because independent noise can make r negative. The paper determines the quadratic spectral mechanism and target factor c_H; the code estimates curvature from gradient differences and can estimate an effective condition number by tracking recent accepted alpha values. First test ResNet-18 on CIFAR-10 against SGD with momentum and AdamW, then test a small decoder Transformer on WikiText-2. Compare loss versus optimizer steps and wall-clock time at equal model FLOPs, final accuracy or perplexity, gradient-norm ratios, clipping frequency, and failed-denominator frequency. A positive result is faster loss descent or equal quality in fewer updates without increased divergence or excessive learning-rate clipping.
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.