# Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation

arXiv: https://arxiv.org/abs/2112.09291 · HTML: https://mlsanity.com/paper/2112.09291/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2021.

## Built on by (most cited first, 2 of 2)

- [Approximate Secular Equations for the Cubic Regularization Subproblem](https://mlsanity.com/paper/2209.13268/) (2022)
- [Cubic-Regularized Newton for Spectral Constrained Matrix Optimization and its Application to Fairness](https://mlsanity.com/paper/2209.01229/) (2022)

## Abstract (arXiv)

The cubic regularization (CR) algorithm has attracted a lot of attentions in the literature in recent years. We propose a new reformulation of the cubic regularization subproblem. The reformulation is an unconstrained convex problem that requires computing the minimum eigenvalue of the Hessian. Then based on this reformulation, we derive a variant of the (non-adaptive) CR provided a known Lipschitz constant for the Hessian and a variant of adaptive regularization with cubics (ARC). We show that the iteration complexity of our variants matches the best known bounds for unconstrained minimization algorithms using first- and second-order information. Moreover, we show that the operation complexity of both of our variants also matches the state-of-the-art bounds in the literature. Numerical experiments on test problems from CUTEst collection show that the ARC based on our new subproblem reformulation is comparable to existing algorithms.