# Overshoot Budget Controller

- ID: 353
- Canonical URL: https://synthcore.org/idea/353/overshoot-budget-controller
- API JSON: https://synthcore.org/api/idea/353.json
- API Markdown: https://synthcore.org/api/idea/353.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.02053](https://arxiv.org/abs/2607.02053)
- Category: optimization
- Solves: stability, speedup
- ML areas: optimizer, scheduler, training-dynamics
- Math tags: optimization, dynamical-systems, stability-theory
- Ratings: usefulness 6/10; difficulty 4/10; novelty 7/10

## 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.

## 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.

## Key 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)$$

## 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

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.82275
- Paired wins: 3/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/1273/bench_report.json)
- [bench_stage2.py](https://synthcore.org/code/1273/bench_stage2.py)
- [overshoot_controller.py](https://synthcore.org/code/1273/overshoot_controller.py)
- [report.md](https://synthcore.org/code/1273/report.md)
- [report_bench_2026-09-04T001905.md](https://synthcore.org/code/1273/report_bench_2026-09-04T001905.md)
- [Download all files as ZIP](https://synthcore.org/download/1273)

## Disclaimer

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