Reachability Gradient Extrapolation
Implementation & benchmark of arXiv:2608.13915 — First-Order Optimization as Minimum-Time Control
Source paper: First-Order Optimization as Minimum-Time Control arXiv:2608.13915 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Augment SGD or AdamW with periodic control steps that search the affine span of recently observed gradients for a parameter point predicted to have a smaller gradient norm. Apply the extrapolation only when a secant curvature model predicts improvement and a trust-region and actual-gradient acceptance test pass; otherwise use the ordinary optimizer update.
Formulas
Mathematical statement
The paper defines the full first-order control class by $z_{k+1}=z_0-\sum_{j=0}^{k}c_{k,j}\nabla f(z_j)$, where $z_0$ is the initial parameter vector, $z_j$ are queried iterates, and $c_{k,j}$ are real control coefficients. With $g_j=\nabla f(z_j)$ and $G_k=[g_0,\ldots,g_k]$, every reachable candidate is $z(c)=z_0-G_kc$. The target set is $\mathcal{T}_{\varepsilon}=\{z:\|\nabla f(z)\|_2\leq\varepsilon\}$. For a quadratic objective $f(z)=\tfrac12(z-z^\star)^\top H(z-z^\star)+f^\star$ with symmetric positive-definite $H$, the gradient at a reachable point is exactly $\nabla f(z(c))=g_0-HG_kc$. Replace the unknown Hessian $H$ by a regularized secant model $B_k$ fitted from displacements $s_i=z_i-z_{i-1}$ and gradient differences $y_i=g_i-g_{i-1}$. The adapted control solves $\min_c\|g_0-B_kG_kc\|_2^2+\lambda\|c\|_2^2$ subject to $\|G_kc\|_2\leq r$. The predicted residual $R_k=\min_c\|g_0-B_kG_kc\|_2$ estimates whether the small-gradient target is reachable in the current local gradient span. Here $\lambda>0$ is coefficient regularization and $r>0$ is a trust-region radius limiting extrapolation.
Implementation notes
Integrate this into the optimizer rather than the forward network. Maintain a rolling window of m parameter-gradient pairs from AdamW or SGD, preferably with gradients flattened separately per parameter block so the memory cost is bounded. Every q ordinary optimizer steps, form G=[g_{t-m+1},...,g_t]. Do not construct a dense Hessian. Fit a low-rank or block-diagonal secant operator B from s_i=theta_i-theta_{i-1} and y_i=g_i-g_{i-1}; a first MVP can use diagonal curvature b_l=(sum_i s_{i,l}y_{i,l})/(sum_i s_{i,l}^2+rho), with b_l clipped to a positive interval. Compute BG by applying this diagonal operator to every stored gradient. Solve the small ridge problem for c, minimizing ||g_t-BG c|| squared plus lambda times ||c|| squared. Enforce ||G c|| no greater than r by shrinking c if necessary. Construct theta_candidate=theta_t-Gc and evaluate its true loss and gradient. Accept the candidate only if its true gradient norm decreases by at least threshold tau relative to the AdamW proposal and its loss is not worse than the current loss by tolerance delta. If rejected, perform the baseline AdamW update and shrink r; after several accepted steps, increase r slowly. Pseudocode: collect theta and g; if step modulo q is nonzero, execute AdamW; otherwise build G, s_i, and y_i, fit B, solve the displayed constrained control problem, evaluate the candidate, and either accept theta-Gc or use AdamW. The paper-derived objects are the gradient-span control form, the predicted residual, and the reachability interpretation. B, r, lambda, q, tau, and delta are empirical settings. First test a two-layer MLP on MNIST or CIFAR-10 against AdamW using equal numbers of true gradient evaluations. Start with m=4 to 8 and q=4. Record loss versus oracle calls, true gradient norm, acceptance rate, wall-clock time, and memory. Success is faster loss reduction at equal gradient evaluations without instability, such as 10 percent fewer steps to reach a fixed training loss; failure is a high rejection rate or no improvement after candidate-evaluation overhead.
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.