[OpenReview 2024] AdaCubic: Breaking the Tuning Curse of Second-Order Optimizers

TL;DR

AdaCubic is a breakthrough second-order optimizer that eliminates the need for Learning Rate (LR) fine-tuning. By solving an auxiliary optimization problem with cubic constraints, it dynamically adjusts its own regularization strength. It leverages stochastic Hessian diagonal approximations to remain as scalable as Adam while providing the saddle-point avoidance guarantees of Cubic Newton methods.

Background Positioning

In the landscape of optimization, we find two dominant but flawed clans: the First-Order clan (SGD, Adam), which are fast but sensitive to LR and prone to getting stuck in saddle points, and the Second-Order clan (Newton methods), which are theoretically superior but computationally ruinous for deep learning. AdaCubic bridges this gap, positioning itself as the first practical, scalable cubic regularization optimizer that works "out of the box" across CV, NLP, and Signal Processing tasks.

The Core Motivation: Why "Adaptive" Cubic Matters?

The standard Cubic Regularization (CR) method relies on a parameter $M$ to weight the cubic term. If $M$ is too small, the step is too aggressive (divergence); if $M$ is too large, the progress is glacial. Most researchers treat $M$ as a static hyperparameter. AdaCubic’s researchers asked: Can we let the geometry of the loss function decide M for us?

By treating the cubic term as a "soft constraint" rather than a fixed penalty, they transformed the optimizer into a self-regulating system.

Methodology: The Auxiliary Subproblem

The heart of AdaCubic is its ability to find the model minimizer without expensive matrix inversions or eigenvalue decompositions.

1. The Adaptive Mechanism

Instead of solving the standard cubic model directly, AdaCubic solves: ${\min }_s\hat{m}(s)exts.t.\Vert s{\Vert }_2^3\le \xi$ Where $\xi$ is a trust parameter. The "magic" happens in the dual space—the weight of the cubic term $M$ is actually the Lagrange multiplier $u^{\ast }$ of this constraint.

2. Hutchinson’s Approximation

To keep the memory cost at $O(d)$, AdaCubic uses Hutchinson’s method. It doesn't calculate the full $dimesd$ Hessian matrix. Instead, it computes: $b_k=extdiag(H_k)\approx \frac{1}{\mathcal{S}}{\sum }_{s=1}^{\mathcal{S}}(H_k{v}_s)\odot v_s$ Where $v_s$ are random Rademacher vectors. This trick makes second-order optimization possible on consumer GPUs.

Figure 1: The logical dependency between the auxiliary problem, strong duality, and the final AdaCubic algorithm.

Experimental Battleground: Performance vs. Efficiency

Does this complexity pay off? The results suggest a resounding "Yes" for practitioners who hate hyperparameter tuning.

Computer Vision

On CIFAR-100, AdaCubic matches the accuracy of heavily fine-tuned Adam and SGD. The crucial advantage is the LR schedule. While Adam and AdaHessian require meticulous LR decay schedules to converge, AdaCubic uses a universal parameter set across all datasets.

Language Modeling

In PTB and WikiText-2 benchmarks using RoBERTa and BERT, AdaCubic frequently outperformed or matched SGD, despite SGD having the benefit of fine-tuned learning rates.

Figure 2: AdaCubic reaches the target loss threshold faster than SGD and AdaHessian in terms of epoch count, highlighting superior convergence efficiency.

Critical Analysis: The Complexity Trade-off

AdaCubic isn't a free lunch. Here is the technical cost-benefit breakdown:

• Memory Footprint: At $2d$ (Gradient + Diagonal Hessian), it is heavier than SGD ($d$) but lighter than Adam ($3d$) and AdaHessian ($4d$).
• Time Cost: Like all Hessian-based methods, it requires an extra backward pass to compute the Hessian-vector product. However, as shown in Figure 2, it often converges in significantly fewer epochs, potentially saving total wall-clock time in complex training runs.

Takeaways & Future Work

AdaCubic proves that the "Theoretical Beauty" of Cubic Regularization can survive the "Practical Chaos" of Deep Learning. Its biggest value is for Automatic ML (AutoML) and settings where tuning is impossible.

Future Outlook: The researchers suggest that while the diagonal approximation is efficient, it misses "off-diagonal" interactions (cross-parameter curvature). Future iterations might explore block-diagonal approximations to further improve results on massive Transformer models.

Senior Editor's Note: AdaCubic is currently available on GitHub. It represents a significant step toward "Parameter-free" deep learning optimization.