Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence

Abstract

Cubic regularized Newton methods have the optimal $\mathcal{O}(\epsilon^{-3/2})$ global rate, but a dense subproblem solve limits the feasible block size. Scalable Cubic Newton variants replace the true block curvature with a diagonal, low-rank, Kronecker-factored, or sketched surrogate and, most often, give up the exact cubic step. We introduce a blockwise optimizer that minimizes an independent cubic model per parameter tensor over the true block Hessian, under a per-block adaptive cubic constant and a monotone guard on the full loss. Arbitrarily large tensors are handled matrix-free in a Lanczos-built Krylov subspace, where we prove that the step minimizes the cubic model. The theory also supplies the $\mathcal{O}(\epsilon^{-3/2})$ iteration complexity bound, a second-order guarantee, and monotone per-block descent. Four variants of this outer scheme are evaluated against the original adaptive regularization with cubics (ARC) optimizer, some other recent cubic Newton variants, Adam, SOAP, and L-BFGS. On a 91.4M-parameter implicit neural representation (INR), the variants introduced in this work are the only evaluated here cubic Newton methods whose steps stay exact on every block. Run to full convergence on FINER 2D image fitting, one of the ARC variants introduced here, ARC-$\varphi_1$, reaches 133.5 dB peak signal-to-noise ratio, while tuned Adam plateaus at 78.2 dB after about 70 minutes. In that time ARC-$\varphi_1$ reaches 95.6 dB.