# Prefix-Minimax Anytime Step Schedule

- ID: 352
- Canonical URL: https://synthcore.org/idea/352/prefix-minimax-anytime-step-schedule
- API JSON: https://synthcore.org/api/idea/352.json
- API Markdown: https://synthcore.org/api/idea/352.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.02053](https://arxiv.org/abs/2607.02053)
- Category: optimization
- Solves: speedup, stability, generalization
- ML areas: optimizer, scheduler, training-dynamics
- Math tags: optimization, approximation-theory, spectral-theory
- Ratings: usefulness 7/10; difficulty 5/10; novelty 6/10

## Idea description

Construct a positive learning-rate schedule offline by minimizing the worst residual of every prefix on a normalized curvature interval, rather than optimizing only the final training horizon. The schedule is evaluated through the exact quadratic residual polynomial p_n(lambda) = product_{k=1}^n (1 - eta_k lambda), so every prefix is constrained to make progress across multiple curvatures.

## Mathematical statement

For the one-dimensional 1-smooth convex quadratic f(x) = lambda x^2 / 2, with curvature lambda in [0, 1], gradient descent gives x_{n+1} = product_{k=1}^n (1 - eta_k lambda) x_1. With x_1 = 1, the paper defines Q_n(eta) = max_{lambda in [0,1]} lambda product_{k=1}^n (1 - eta_k lambda)^2. The paper states that both worst-case function-value and squared-gradient criteria satisfy R_n(eta) >= Q_n(eta) and G_n(eta) >= Q_n(eta). Here eta_k > 0 is the step size at iteration k, n is a prefix length, and lambda is normalized curvature. The adaptation minimizes J(eta) = max over prefixes and curvature values of w_n lambda product_{k=1}^n (1 - eta_k lambda)^2. The transferable asset is horizon-independent control: the residual of each prefix is explicitly evaluated without knowing future gradients or the eventual training horizon.

## Key formulas

- $$x_{n+1}=\prod_{k=1}^{n}(1-\eta_k\lambda)$$
- $$Q_n(\boldsymbol{\eta})=\max_{\lambda\in[0,1]}\lambda\prod_{k=1}^{n}(1-\eta_k\lambda)^2$$
- $$R_n(\boldsymbol{\eta})\geq Q_n(\boldsymbol{\eta}),\qquad G_n(\boldsymbol{\eta})\geq Q_n(\boldsymbol{\eta})$$
- $$J(\boldsymbol{\eta})=\max_{1\leq n\leq N,\,\lambda\in[\lambda_{\min},1]}w_n\lambda\exp\left(2\sum_{k=1}^{n}\log\left|1-\eta_k\lambda\right|\right)$$

## Implementation notes

1. Integration point: replace the scalar learning-rate schedule in SGD, AdamW, or a momentum-free preconditioned optimizer. Normalize each parameter group by an estimated curvature scale L_t and use alpha_t = eta_t / L_t, where eta_t is supplied by the learned positive schedule. For AdamW, apply this schedule to the bias-corrected update before weight decay. 2. Schedule construction: choose a maximum prefix N, a logarithmic curvature grid lambda_j in [lambda_min, 1], and prefix weights w_n such as 1/n. Parameterize eta_k = softplus(u_k), compute s_{n,j} = sum over k <= n of log(abs(1 - eta_k lambda_j) + 1e-8), and minimize the smooth maximum of log(lambda_j) + 2 s_{n,j} + log(w_n) with Adam. Add a mild penalty on the total step sum and constrain eta_k to a practical range such as [1e-4, 4]. 3. At training time, expose the schedule sequentially and do not restart it when evaluating intermediate checkpoints. Estimate L_t using one or two power iterations on Hessian-vector products every 100 to 500 steps, or use a fixed warmup estimate initially. 4. The product objective and prefix minimax design come from the quadratic analysis; the curvature interval, normalization, and weights are empirical choices. 5. First experiment: train ViT-Tiny on CIFAR-100 and a 6-layer Transformer on WikiText-2, comparing cosine decay, a tuned constant learning rate, and the prefix-minimax schedule at equal optimizer updates. Record loss at every prefix, final validation quality, and divergence rate over five seeds. Success means lower early-prefix loss and equal or better final quality without knowing the total training horizon.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Implemented the exact prefix residual polynomial and a bounded smooth-minimax positive schedule optimizer. The mechanism was numerically confirmed: the amplification boundary was predicted and observed at eta*lambda=2, the sign transition at 1, 1,008 geometric-ratio checks matched to 2.2e-16, and one-step annihilation across 25 curvatures had residual below 1.1e-32. The learned schedule reduced the worst unweighted prefix residual to 0.1154 versus 0.1481 for constant eta=1.0 and 0.1852 for constant eta=0.8, but it did not improve late-prefix residual versus those baselines; therefore this is a toy quadratic signal, not evidence of a general training win.

### Mechanism check

- Verdict: Implemented the exact prefix residual polynomial and a bounded smooth-minimax positive schedule optimizer. The mechanism was numerically confirmed: the amplification boundary was predicted and observed at eta*lambda=2, the sign transition at 1, 1,008 geometric-ratio checks matched to 2.2e-16, and one-step annihilation across 25 curvatures had residual below 1.1e-32. The learned schedule reduced the worst unweighted prefix residual to 0.1154 versus 0.1481 for constant eta=1.0 and 0.1852 for constant eta=0.8, but it did not improve late-prefix residual versus those baselines; therefore this is a toy quadratic signal, not evidence of a general training win.
- Confidence: 8/10
- Limitations: No CIFAR, language-model, neural-network, multi-seed, wall-clock, or Hessian-normalization experiment was run. The optimizer used a finite curvature grid and smooth surrogate; the resulting schedule collapses most later steps to the lower bound, and the weighted objective is dominated by the first prefix because w_1=1.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.1089
- Paired wins: 2/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_report.json](https://synthcore.org/code/141/bench_report.json)
- [prefix_minimax.py](https://synthcore.org/code/141/prefix_minimax.py)
- [report.md](https://synthcore.org/code/141/report.md)
- [report_bench_2026-08-30T161440.md](https://synthcore.org/code/141/report_bench_2026-08-30T161440.md)
- [results.json](https://synthcore.org/code/141/results.json)
- [run_bench.py](https://synthcore.org/code/141/run_bench.py)
- [run_experiment.py](https://synthcore.org/code/141/run_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/141)

## Disclaimer

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