# Regret-trained diagonal preconditioner

- ID: 1078
- Canonical URL: https://synthcore.org/idea/1078/regret-trained-diagonal-preconditioner
- API JSON: https://synthcore.org/api/idea/1078.json
- API Markdown: https://synthcore.org/api/idea/1078.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.17607](https://arxiv.org/abs/2607.17607)
- Category: optimization
- Solves: speedup, stability, accuracy
- ML areas: optimizer, training-dynamics
- Math tags: optimization, convex-analysis, dynamical-systems, stochastic-processes
- Ratings: usefulness 8/10; difficulty 4/10; novelty 6/10

## Idea description

Replace a fixed optimizer preconditioner with a diagonal matrix selected by an online convex optimizer. A gradient predictor supplies the direction, while a linear-loss regret update learns coordinate-wise gains that favor transformations aligned with the realized stochastic gradient. The method retains the identity preconditioner as an explicit comparator, so it can be tested for negative regret and improvement over ordinary SGD.

## Mathematical statement

The paper studies unconstrained minimization of a beta-smooth nonconvex function f: R^d -> R, with stochastic gradient g_t satisfying E[g_t | x_t] = nabla f(x_t) and E[||g_t - nabla f(x_t)||^2 | x_t] <= sigma^2. Its central smooth-objective guarantee is (1/T) sum_{t=1}^T E[||nabla f(x_t)||_2^2] <= C[ sigma sqrt(M beta)/sqrt(T) + sqrt(M beta) R_T(A,I_d)/T + M beta/T ], where M bounds the objective range, beta is the smoothness constant, A is the admissible preconditioner set, I_d is the identity comparator, R_T(A,I_d) is the static regret of the online preconditioner learner against I_d, and C hides universal constants. The online learner receives one ordinary static-regret game with linear convex losses. Use a diagonal positive preconditioner A_t = diag(a_t), with a_t in [a_min,a_max]^d and 1 in this interval. Let m_t be a predictable gradient tracker, for example m_t = rho m_{t-1} + (1-rho)g_{t-1}. The adapted linear loss is ell_t(a) = -sum_i g_{t,i}m_{t,i}a_i, whose gradient is q_t,i = -g_{t,i}m_{t,i}; minimizing this loss rewards coordinates where the predicted direction and realized gradient agree. The diagonal OGD regret guarantee is sum_t ell_t(a_t)-ell_t(1) <= ||1-a_1||_2^2/(2 alpha) + alpha/2 sum_t ||q_t||_2^2 for constant online learning rate alpha, provided the losses are convex and the domain is the box [a_min,a_max]^d. Negative realized regret means the learned preconditioner has lower cumulative linear loss than the identity baseline. The network update is x_{t+1}=x_t-eta A_t m_t, with eta chosen small enough for beta-smooth descent and with gradient clipping or bounded gains to control ||A_t m_t||.

## Key formulas

- $$\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\|\nabla f(x_t)\|_2^2\right]\lesssim\frac{\sigma\sqrt{M\beta}}{\sqrt{T}}+\frac{\sqrt{M\beta}\,\mathscr{R}_{T}(\mathcal{A},I_d)}{T}+\frac{M\beta}{T}.$$
- $$\ell_t(a)=-\langle g_t,\operatorname{diag}(a)m_t\rangle=-\sum_{i=1}^{d}g_{t,i}m_{t,i}a_i,\qquad a\in[a_{\min},a_{\max}]^d,$$
- $$q_{t,i}=\frac{\partial\ell_t}{\partial a_i}=-g_{t,i}m_{t,i},\qquad a_{t+1}=\Pi_{[a_{\min},a_{\max}]^d}\left(a_t-\alpha q_t\right)=\Pi_{[a_{\min},a_{\max}]^d}\left(a_t+\alpha(g_t\odot m_t)\right),$$
- $$\sum_{t=1}^{T}\ell_t(a_t)-\ell_t(\mathbf{1})\leq\frac{\|a_1-\mathbf{1}\|_2^2}{2\alpha}+\frac{\alpha}{2}\sum_{t=1}^{T}\|q_t\|_2^2,\qquad x_{t+1}=x_t-\eta\operatorname{diag}(a_t)m_t.$$

## Implementation notes

1. Integration point: modify the parameter-update line of SGD, Adam without its usual second-moment preconditioner, or a Transformer optimizer. Maintain one scalar gain a_i per parameter tensor element, or one gain per channel, attention head, or parameter block to reduce overhead. The gains form A_t=diag(a_t); use a_min=0.1 and a_max=10 initially, so the identity comparator a=1 is feasible. 2. Pseudocode: initialize parameters x, tracker m=0, and gains a=ones_like(x). For each minibatch, compute stochastic gradient g_t. Form the predictable tracker m_t=rho*m+(1-rho)*g_prev; use m_t for the parameter update x <- x-eta*(a*m_t). After observing g_t, compute q=-g_t*m_t elementwise, then update a <- clip(a-alpha*q, a_min, a_max), equivalently a <- clip(a+alpha*g_t*m_t, a_min, a_max). Store g_t as g_prev and continue. Apply global norm clipping to g_t and m_t before forming q. 3. Computed directly from the mathematics: the online linear loss, projected OGD update, identity-comparator regret, and preconditioned descent step. Estimated empirically: beta can be approximated with a short Hessian-vector power iteration or omitted initially; sigma is estimated from minibatch gradient variance; M is the observed train-loss range. Log cumulative regret R_hat_T=sum_t[ell_t(a_t)-ell_t(ones)], average gradient norm, gain statistics, and the fraction of gains at the bounds. Choose alpha by a small sweep or alpha=c/(sqrt(T)G), where G is a running upper bound on ||q_t||. 4. First cheap experiment: train a 2-layer MLP and a small ViT on MNIST or CIFAR-10 using identical minibatches and matched optimizer FLOPs. Compare SGD, AdamW, and SGD with the regret-trained diagonal or blockwise preconditioner under matched learning-rate sweeps. The primary falsifiable signals are faster training-loss decrease at equal steps, lower validation loss at a fixed budget, and negative cumulative identity-comparator regret. Add ablations using g_t squared instead of g_t times m_t and using a non-predictive tracker; the proposed separation should outperform these if predictable preconditioning is useful. Also compare elementwise, per-channel, per-head, and per-layer gains to measure the memory-performance tradeoff.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built a regret-trained diagonal preconditioner with predictable exponential gradient tracking, projected OGD gain updates, and identity-comparator regret logging. All three mechanism checks passed: OGD regret was 2.436 versus a 4.928 bound, aligned-gradient gain slope was 0.007680 versus 0.007680 predicted, and alternating-gradient gain slope was -0.001600 versus -0.001600 predicted. The optimizer showed slightly higher validation accuracy than SGD (0.9244 vs 0.9222) but slightly worse validation loss (0.3674 vs 0.3662), so the mechanism is verified but a broad optimization win is not established.

### Mechanism check

- Verdict: Built a regret-trained diagonal preconditioner with predictable exponential gradient tracking, projected OGD gain updates, and identity-comparator regret logging. All three mechanism checks passed: OGD regret was 2.436 versus a 4.928 bound, aligned-gradient gain slope was 0.007680 versus 0.007680 predicted, and alternating-gradient gain slope was -0.001600 versus -0.001600 predicted. The optimizer showed slightly higher validation accuracy than SGD (0.9244 vs 0.9222) but slightly worse validation loss (0.3674 vs 0.3662), so the mechanism is verified but a broad optimization win is not established.
- Confidence: 9/10
- Limitations: Only one small digits MLP, one fixed hyperparameter setting, and 350 minibatch steps were tested; no AdamW, CNN/ViT, learning-rate sweep, multiple seeds, wall-clock or FLOP accounting, or formal nonconvex convergence evaluation was performed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.04595
- Paired wins: 2/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/193/bench_report.json)
- [experiment.py](https://synthcore.org/code/193/experiment.py)
- [report.md](https://synthcore.org/code/193/report.md)
- [report_bench_2026-08-30T195404.md](https://synthcore.org/code/193/report_bench_2026-08-30T195404.md)
- [results.json](https://synthcore.org/code/193/results.json)
- [stage2_bench.py](https://synthcore.org/code/193/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/193)

## Disclaimer

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