Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence

arXiv:2608.22129v1 Announce Type: new Abstract: Cubic-regularized Newton methods have the optimal O(arepsilon^{-3/2}) global rate and an automatic saddle-escape mechanism, but their subproblem is most often solved by a full eigendecomposition, limiting feasible model size. We introduce a blockwise optimizer that partitions parameters by tensor, minimizes an independent cubic model with an adaptive cubic constant M_b per block, and accepts or rejects each block step against a monotone guard on the full loss. The subproblem solver is chosen by block size: small blocks use lazy exact cubic steps from explicitly formed per-block Hessians; arbitrarily large tensors use a matrix-free Chebyshev-bounded Krylov subspace built by the Lanczos process. The cubic shift bounds the required polynomial degree whenever the gradient-driven shift dominates negative curvature, renders the shifted operator positive semidefinite before any polynomial is applied, and preserves the O(arepsilon^{-3/2}) rate under inexact subproblem solves. We prove these claims, and the blockwise scheme carries a monotone per-block descent guarantee. Experiments cover FINER INRs (about 199k parameters) and a 91.4M-parameter ViSIR INR, where the blockwise cubic step remains exact in the cubic-model sense on every block, including the 88.5M-parameter decoder tensor (97% of the model). Run to full convergence on FINER, the ARC-arphi_1 optimizer reaches 133.5 dB PSNR while tuned Adam plateaus at 78.2 dB at the same extended budget; in the roughly 70 minutes Adam takes to reach its peak, ARC-arphi_1 reaches 95.6 dB. A companion report isolates the loss-landscape features responsible for Adam's behavior.

Source: arXiv cs.LG | 2026-08-25