Cubic-budget accelerated Newton
Implementation & benchmark of arXiv:2608.21359 — Primal Acceleration of Newton's Method
Source paper: Primal Acceleration of Newton's Method arXiv:2608.21359 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
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.
Formulas
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.
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
Stage 1 · Toy mechanism gate: Failed ✗
Stage 2 · Mechanism transferred to benchmark: Not tested
Stage 2 · Practical benchmark result: Not run
Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works
Stage 1 — Mechanism check agent confidence 9/10
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.
- Agent confidence
- 9/10
- Baseline
- SGD momentum: final loss 0.0008754, accuracy 1.0, 0 spikes, 0 CG iterations, 0.496s
- Idea
- Cubic-budget method: final loss 0.2758, accuracy 1.0, 0 spikes, 0 accepted CG iterations, 6.515s; toy math mechanism_pass=true
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.
How to run: python3 cubic_budget_experiment.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Artifacts
- cubic_budget_experiment.py 7.2 KB View Raw
- report.md 1.6 KB View
- results.json 5.7 KB View Raw