# Krylov Block-Cubic Optimizer

- ID: 47
- Canonical URL: https://synthcore.org/idea/47/krylov-block-cubic-optimizer
- API JSON: https://synthcore.org/api/idea/47.json
- API Markdown: https://synthcore.org/api/idea/47.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.22129](https://arxiv.org/abs/2608.22129)
- Category: optimization
- Solves: stability, accuracy, speedup
- ML areas: optimizer, training-dynamics, mlp
- Math tags: optimization, linear-algebra, numerical-analysis
- Ratings: usefulness 8/10; difficulty 6/10; novelty 6/10

## Idea description

Replace Adam or damped Newton updates with independent cubic-regularized Newton steps for parameter blocks, using Hessian-vector products and a small Lanczos subspace instead of explicitly forming Hessians. Adapt the cubic coefficient per block and accept only steps that produce monotone decrease in the measured training loss.

## Mathematical statement

Under the paper's Lipschitz-Hessian assumption, there is an L_H >= 0 such that ||nabla^2 f(x)-nabla^2 f(y)|| <= L_H ||x-y||. Consequently, the cubic model upper-bounds the objective locally: f(theta+s) <= f(theta)+g^T s+(1/2)s^T Hs+(L_H/6)||s||^3, where theta is the current parameter vector, g=nabla f(theta), H=nabla^2 f(theta), and s is an update. For parameter block b, use g_b, Hessian operator H_b, and an adaptive coefficient sigma_b>0 to define m_b(s)=g_b^T s+(1/2)s^T H_b s+(sigma_b/6)||s||^3. Approximate the minimizer in the Lanczos Krylov space K_k(H_b,g_b)=span{g_b,H_bg_b,...,H_b^{k-1}g_b}. If Q_k has orthonormal Lanczos columns and T_k=Q_k^T H_b Q_k is the resulting tridiagonal matrix, solve the k-dimensional problem in z and return s_b=Q_k z. The cubic term regularizes both positive and negative curvature. A monotone actual-loss guard rejects steps for which f(theta+s_b)>f(theta). The model-to-objective ratio rho_b=[f(theta)-f(theta+s_b)]/[-m_b(s_b)] can control sigma_b, increasing it after poor agreement and decreasing it after reliable descent.

## Key formulas

- $$\|\nabla^{2}f(x)-\nabla^{2}f(y)\|\leq L_H\|x-y\|,$$
- $$f(x+s)\leq f(x)+\langle g,s\rangle+\tfrac{1}{2}\langle \mathbf{H}s,s\rangle+\tfrac{L_H}{6}\|s\|^{3},$$
- $$m_b(s)=\langle g_b,s\rangle+\tfrac{1}{2}s^{\mathsf T}H_b s+\tfrac{\sigma_b}{6}\|s\|^3,\qquad s_b=\arg\min_s m_b(s),$$
- $$T_k=Q_k^{\mathsf T}H_bQ_k,\quad z^*=\arg\min_z\left\{g_b^{\mathsf T}Q_kz+\tfrac{1}{2}z^{\mathsf T}T_kz+\tfrac{\sigma_b}{6}\|z\|^3\right\},\quad s_b=Q_kz^*.$$

## Implementation notes

Integrate this at the optimizer-update point, operating on one parameter tensor or a small group of tensors at a time. For each block b, compute its gradient g_b and provide an automatic-differentiation Hessian-vector-product routine v -> H_b v; never materialize H_b. Build a k-step Lanczos basis with q_1=g_b/(||g_b||+epsilon). At iteration j, compute w=H_b q_j, set alpha_j=q_j^T w, subtract alpha_j q_j and the previous beta_j q_{j-1}, reorthogonalize if necessary, and set beta_{j+1}=||w||. Stop after k iterations or when beta_{j+1} is negligible. Store Q_k and the tridiagonal T_k. Solve the small cubic problem using the stationarity parameter lambda: for a trial lambda >= 0, solve (T_k+lambda I)z=-Q_k^T g_b and seek lambda=(sigma_b/2)||z|| by safeguarded bisection or Newton iteration. Form s_b=Q_k z and reshape it to the block tensor. Evaluate the actual loss after the proposed update. Accept only if the loss decreases; compute rho_b=[f(theta)-f(theta+s_b)]/[-m_b(s_b)], multiply sigma_b by 2 after rejection or rho_b<0.1, and halve sigma_b after rho_b>0.75, with fixed minimum and maximum bounds. For stochastic training, use a fixed validation mini-batch for the guard or periodically use full-batch checks to avoid noise-driven rejection. The paper supplies the cubic model and Krylov construction; k, block size, sigma bounds, and guard frequency are empirical choices. First test a small full-batch 2-4 layer MLP on synthetic or MNIST regression against AdamW and L-BFGS at matched wall-clock and HVP budgets. Measure loss versus time, number of HVPs, accepted-step ratio, and final error. A successful result is faster descent to a fixed loss, monotone guarded training, or better final accuracy when the Hessian contains substantial negative or anisotropic curvature.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a CPU MVP of the Krylov block-cubic optimizer using Hessian-vector products, reorthogonalized Lanczos bases, reduced cubic subproblem solves, adaptive sigma, and an actual-loss monotonicity guard. The exact quadratic sanity check succeeded with stationarity residual 1.796e-10 and Lanczos orthogonality error 1.906e-15. On the fixed synthetic MLP regression task, cubic optimization reached loss 0.024539 versus Adam's 0.009479 in similar wall time, with only 18/35 steps accepted, so the promised optimization win was not observed.

### Mechanism check

- Verdict: Built a CPU MVP of the Krylov block-cubic optimizer using Hessian-vector products, reorthogonalized Lanczos bases, reduced cubic subproblem solves, adaptive sigma, and an actual-loss monotonicity guard. The exact quadratic sanity check succeeded with stationarity residual 1.796e-10 and Lanczos orthogonality error 1.906e-15. On the fixed synthetic MLP regression task, cubic optimization reached loss 0.024539 versus Adam's 0.009479 in similar wall time, with only 18/35 steps accepted, so the promised optimization win was not observed.
- Confidence: 9/10
- Limitations: Only one small synthetic full-batch regression task, one fixed seed, one full parameter block, and k=6 Lanczos were tested. No MNIST, stochastic training, block partitioning, wall-clock/FLOP-normalized sweeps, or comparison with L-BFGS/Newton-CG was performed.

## Artifacts

- [experiment.py](https://synthcore.org/code/7/experiment.py)
- [report.md](https://synthcore.org/code/7/report.md)
- [Download all files as ZIP](https://synthcore.org/download/7)

## Disclaimer

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