# Cubic-budget accelerated Newton

- ID: 2661
- Canonical URL: https://synthcore.org/idea/2661/cubic-budget-accelerated-newton
- API JSON: https://synthcore.org/api/idea/2661.json
- API Markdown: https://synthcore.org/api/idea/2661.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.21359](https://arxiv.org/abs/2608.21359)
- Category: optimization
- Solves: speedup, stability, accuracy
- ML areas: optimizer, training-dynamics, mlp, transformer
- Math tags: optimization, dynamical-systems, numerical-analysis, convex-analysis
- Ratings: usefulness 8/10; difficulty 6/10; novelty 6/10

## Idea description

Replace a first-order optimizer update by an extrapolation point followed by one damped Newton or Newton-CG solve, while selecting the acceleration weight from an explicit cubic Hessian-Lipschitz budget. Use a displacement-based safeguard in place of the unavailable distance to the optimum, turning the proof condition into a practical trust-region-like rule that limits unstable momentum.

## Mathematical statement

The paper defines the curvature budget ell_k = a_{k+1}^3 L_2 / A_{k+1}^2, where a_{k+1} is the new estimate-sequence weight, A_{k+1}=A_k+a_{k+1} is the cumulative weight, and L_2 is a Hessian-Lipschitz constant satisfying ||nabla^2 f(u)-nabla^2 f(v)|| <= L_2 ||u-v||. The proof uses the third-order gradient remainder ||nabla f(x)-nabla f(y)-H(y)(x-y)|| <= (L_2/2)||x-y||^2 and requires ell_k ||v_{k+1}-x^star|| <= 1/2. Here x^star is the minimizer and v_k is the auxiliary accelerated state. In neural-network training x^star is unknown, so replace its distance by an empirical radius R_hat_k based on recent auxiliary-state displacements. Enforce ell_k R_hat_k <= eta, with eta <= 1/2, and use damping if the linear system is indefinite or poorly conditioned.

## Key formulas

- $$\ell_k=\frac{a_{k+1}^{3}L_2}{A_{k+1}^{2}},\qquad A_{k+1}=A_k+a_{k+1}$$
- $$\|\nabla f(x)-\nabla f(y)-H(y)(x-y)\|\leq\frac{L_2}{2}\|x-y\|^2$$
- $$\ell_k\|v_{k+1}-x^\star\|\leq\frac12$$
- $$\widehat L_{2,k}=\operatorname{EMA}_k\left(\frac{\|(H_k-H_{k-1})q_k\|}{\|y_k-y_{k-1}\|+\varepsilon}\right),\qquad q_k\sim\mathcal N(0,I),\;\|q_k\|=1$$

## Implementation notes

(1) Integration point: implement this as an optimizer for a small MLP, ViT block, or language-model subnetwork. Maintain parameters x_k, an auxiliary state v_k, cumulative weight A_k, and an estimate L_hat_2 of Hessian-Lipschitz curvature. Form y_k=(A_k x_k+a_{k+1}v_k)/A_{k+1}, compute the minibatch gradient g_k at y_k, and solve (H_k+lambda_k I)s_k=g_k once using conjugate gradients and Hessian-vector products. Set x_{k+1}=y_k-s_k and v_{k+1}=v_k-(a_{k+1}/A_{k+1})s_k. (2) Pseudocode: initialize A=1, x=v. At each iteration compute R_hat=EMA(||v-x||+epsilon), choose the largest candidate a from a geometric grid such that a^3 L_hat_2/(A+a)^2 <= eta/max(R_hat,epsilon), set A_new=A+a, form y=((A_new-a)x+a v)/A_new, estimate g and HVPs, run CG, update x and v, then set A=A_new. If the minibatch loss spikes or CG fails, halve a and repeat. (3) Exact quantities are the cubic budget and CG update; estimate L_hat_2 with the displayed random-probe formula and use R_hat as a proxy for ||v_{k+1}-x^star||. (4) First experiment: train a width-512 two-layer MLP on MNIST or CIFAR-10, comparing SGD with momentum, AdamW, damped Newton-CG, and this method at equal Hessian-vector-product budgets. Measure loss versus wall-clock time, CG iterations, loss-spike frequency, and test accuracy. Success is faster loss reduction at equal curvature-query cost and fewer instability events than undamped acceleration.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built the cubic-budget weight selection, Hessian-Lipschitz probe, displacement safeguard, damped HVP/CG update, and a small MLP comparison in cubic_budget_experiment.py. The toy math checks passed: the budget reached eta to numerical precision, weight scaling was -0.3338 versus -1/3, and the Taylor remainder scaled quadratically with bound ratio 0.964. However, the training effect was absent: after 80 steps SGD reached loss 0.000875 in 0.50s while cubic reached 0.276 in 6.51s; the reported CG iteration count was zero, indicating the solve was rejected or fell back to a gradient step on this nonconvex MLP. Thus the claimed acceleration was not observed.

### Mechanism check

- Verdict: Built the cubic-budget weight selection, Hessian-Lipschitz probe, displacement safeguard, damped HVP/CG update, and a small MLP comparison in cubic_budget_experiment.py. The toy math checks passed: the budget reached eta to numerical precision, weight scaling was -0.3338 versus -1/3, and the Taylor remainder scaled quadratically with bound ratio 0.964. However, the training effect was absent: after 80 steps SGD reached loss 0.000875 in 0.50s while cubic reached 0.276 in 6.51s; the reported CG iteration count was zero, indicating the solve was rejected or fell back to a gradient step on this nonconvex MLP. Thus the claimed acceleration was not observed.
- Confidence: 9/10
- Limitations: The experiment used a tiny synthetic two-class dataset and a 2-16-2 MLP with full-batch training, not MNIST/CIFAR or a larger neural network. It did not provide a rigorously equal HVP-budget comparison, and the implementation’s nonpositive-curvature path fell back to a gradient step, so the proposed Newton-CG mechanism was not meaningfully exercised.

## Artifacts

- [cubic_budget_experiment.py](https://synthcore.org/code/1005/cubic_budget_experiment.py)
- [report.md](https://synthcore.org/code/1005/report.md)
- [results.json](https://synthcore.org/code/1005/results.json)
- [Download all files as ZIP](https://synthcore.org/download/1005)

## Disclaimer

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