△ Mechanism confirmed, baseline not beaten 2026

Overshoot Budget Controller

Implementation & benchmark of arXiv:2607.02053 — Lower Bounds for Anytime Acceleration of Gradient Descent

Usefulness6/10

Difficulty4/10

Novelty7/10

Optimization Stability Speedup Optimizer Scheduler Training dynamics Optimization Dynamical systems Stability theory

Source paper: Lower Bounds for Anytime Acceleration of Gradient Descent arXiv:2607.02053 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Use the paper's non-permutation-invariant overshoot bound as a runtime guard for large learning rates. A proposed step is accepted only if its predicted overshoot contribution is compatible with the observed gradient residual; otherwise the optimizer clips or shrinks the step, preventing isolated very large updates from causing delayed divergence.

Formulas

$$R_n(\boldsymbol{\eta})\geq\frac{(\eta_m-1)^2}{(1+\eta_{1:m-1})^2(1+2\eta_{m+1:n})},\qquad G_n(\boldsymbol{\eta})\geq\frac{(\eta_m-1)^2}{(1+2\eta_{1:m-1})(1+\eta_{m+1:n})^2}$$

$$\eta_n\leq 1+(1+\eta_{1:n-1})\sqrt{R_n},\qquad \eta_n\leq 1+\sqrt{1+2\eta_{1:n-1}}\sqrt{G_n}$$

$$\widehat{G}_t=\frac{\lVert g_t\rVert_2^2}{\lVert g_{t-1}\rVert_2^2+\varepsilon},\qquad \eta_t^{\mathrm{cap}}=1+\sqrt{1+2S_{t-1}}\sqrt{\rho\widehat{G}_t+\varepsilon},\qquad S_{t-1}=\sum_{k<t}\eta_k$$

$$\eta_t=\min\left\{\eta_t^{\mathrm{proposal}},\eta_t^{\mathrm{cap}}\right\},\qquad \eta_t^{\mathrm{proposal}}=\eta_t^{\mathrm{base}}\exp\left(\gamma\,\operatorname{clip}\left(\log\frac{\widehat{G}_t}{\tau},-1,1\right)\right)$$

Mathematical statement

For any positive schedule eta, horizon n, and index m with eta_m > 1, Lemma 3.1 gives R_n(eta) >= (eta_m - 1)^2 divided by ((1 + eta_{1:m-1})^2 (1 + 2 eta_{m+1:n})) and G_n(eta) >= (eta_m - 1)^2 divided by ((1 + 2 eta_{1:m-1})(1 + eta_{m+1:n})^2). Here R_n and G_n are the paper's worst-case function-value and squared-gradient criteria, eta_{a:b} means the sum of eta_k from k = a through b, and eta_m > 1 means that the normalized step overshoots the minimizer on a unit-curvature quadratic. The resulting pointwise bounds are eta_n <= 1 + (1 + eta_{1:n-1}) sqrt(R_n) and eta_n <= 1 + sqrt(1 + 2 eta_{1:n-1}) sqrt(G_n). The adaptation treats a smoothed observed gradient residual as an estimate of G_n and uses the inequality as a conservative learning-rate ceiling. Ordering matters: a large step late in training is treated differently from a large early step because prior cumulative steps enter asymmetrically.

Implementation notes

1. Integration point: insert the controller immediately before the parameter update in SGD or AdamW, after computing the preconditioned update direction. Define the normalized scalar step eta_t = alpha_t L_t, where L_t is a per-group curvature estimate or fixed reference scale; clip the actual learning rate so that this normalized step obeys the controller. 2. Maintain S = 0, the previous gradient norm q_old, and an exponential moving average v. At step t, compute the baseline proposal eta_proposal. Compute the residual proxy G_hat_t = (q_t + epsilon) / (q_old + epsilon), where q_t is the squared norm of the current raw or preconditioned gradient. Smooth it with v_t = beta v_{t-1} + (1 - beta) G_hat_t. Compute eta_cap = 1 + sqrt(1 + 2 S) sqrt(rho v_t + epsilon), directly mirroring the paper's G_n inequality. Set eta_t = min(eta_proposal, eta_cap), apply the optimizer update, and then set S to S + eta_t. Reset S at a checkpoint or when the estimated curvature scale changes by more than a factor of two. 3. Estimate L_t with one or two Hessian-vector power iterations, or omit curvature normalization in the first experiment and test the controller on a fixed normalized quadratic. The theorem is exact for smooth convex worst cases; rho, beta, and the gradient-ratio proxy are empirical design parameters. 4. First cheap experiment: compare AdamW, global gradient-clipped AdamW, and this controller on a 2-layer MLP and a 6-layer Transformer using CIFAR-10 and WikiText-2. Deliberately test learning rates from 2 to 10 times the stable baseline. Track gradient spikes, loss recovery after spikes, fraction of clipped steps, divergence frequency, and final validation quality. Success means fewer divergence runs and faster loss descent than global clipping at equal clipping frequency, ideally allowing at least a 2x larger stable base learning rate with no worse final loss.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built an Overshoot Budget Controller for scalar SGD, plus an exact asymmetric-Huber construction check for Lemma 3.1. Across 2,000 random schedules there were zero bound violations, with minimum observed R/G ratios of 0.9999999999997 and 0.9999999999964; ordering-dependent bounds differed for permutations of the same steps. In the deliberate four-spike quadratic stress test, the controller reduced every 20x proposal to approximately 1.25–1.66, capped maximum loss at 0.32 and reached final loss 1.38e-15, while unclipped SGD reached maximum loss 7.94 and global gradient clipping reached 175.0. This is a clear toy stability signal, not evidence of a general training win.

Agent confidence: 8/10

Baseline: Unclipped SGD: final loss 0.01994, max loss 7.938, max |x| 3.985, 0/4 spike steps clipped. Gradient-clipped control: final loss 146.33, max loss 174.98, max |x| 18.707, 0/4 proposal steps reduced.
Idea: Controller: final loss 1.378e-15, max loss 0.320, max |x| 0.8, 4/4 spikes clipped; accepted spike steps [1.248, 1.403, 1.517, 1.662] versus proposal 20.0. Math check: 2,000 trials, zero failures.

Limitations: Only a scalar quadratic/asymmetric-Huber toy experiment was tested; no MLP, Transformer, CIFAR-10, WikiText-2, AdamW integration, wall-clock comparison, hyperparameter sweep, or repeated random training runs were performed. The gradient-clipping baseline uses fixed gradient clipping rather than a separately tuned learning-rate/clipping pair, so the comparison is illustrative rather than a definitive optimizer benchmark.

How to run: python3 overshoot_controller.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.02053) Sep 4, 2026

Ahead of the baseline (−6.8%) but not statistically significant (p=0.8227, wins 3 / 8 paired seeds).

Benchmark: Dynamics forecasting
Model: rnn_small
Paired seeds: 8
Baseline mean: 0.0002
Idea mean: 0.0002
Effect (Δ): -0 (−6.8%; negative = idea better)
Wins: 3 / 8 paired seeds
p-value: 0.8227 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 3 configs

Limitations:

Only the built-in dynamics track was tested. The controller used fixed L_REF=100 rather than Hessian-vector curvature estimation, and the benchmark covered one model, one optimizer family, three learning rates, and 12 epochs.

How to run: python3 bench_stage2.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 4, 2026 latest Failed ✗

Agent confidence: 9/10

The Overshoot Budget Controller was implemented as a local Adam training intervention and evaluated on the structurally matched dynamics pendulum track with paired rnn_small systems. Its mechanism signature was confirmed, but the best task metric was not significantly better than baseline: delta_mean=-1.1293e-05, p=0.82275, with 3 of 8 paired wins.

Baseline: Adam, best lr=0.03; 8-seed dynamics MSE mean=0.0001668608, std=0.0001211998.
Idea: Overshoot-controlled Adam, best lr=0.03; 8-seed dynamics MSE mean=0.0001555682, std=0.0000718532; paired delta=-0.0000112926, p=0.82275, 3/8 wins.
Mechanism signature: Predicted cap mean=3.52561, observed accepted normalized step mean=2.74843, proposal cap fraction=0.30804, trained updates=672, confirmed=true.

Benchmark result