# A Novel Fast Exact Subproblem Solver for Stochastic Quasi-Newton Cubic Regularized Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 19 Apr 2022.

## Builds on (most cited first, 22 of 22)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Self-Normalizing Neural Networks](https://mlsanity.com/paper/1706.02515/) (2017)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [Practical Quasi-Newton Methods for Training Deep Neural Networks](https://mlsanity.com/paper/2006.08877/) (2020)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1607.01231/) (2016)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015)
- [Apollo: An Adaptive Parameter-wise Diagonal Quasi-Newton Method for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2009.13586/) (2020)
- [RES: Regularized Stochastic BFGS Algorithm](https://mlsanity.com/paper/1401.7625/) (2014)
- [Quasi-Newton Methods for Machine Learning: Forget the Past, Just Sample](https://mlsanity.com/paper/1901.09997/) (2019)
- [Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods](https://mlsanity.com/paper/1311.2115/) (2013)
- [Trust-Region Algorithms for Training Responses: Machine Learning Methods Using Indefinite Hessian Approximations](https://mlsanity.com/paper/1807.00251/) (2018)
- [On Solving L-SR1 Trust-Region Subproblems](https://mlsanity.com/paper/1506.07222/) (2015)
- [Stochastic quasi-Newton with line-search regularization](https://mlsanity.com/paper/1909.01238/) (2019)
- [Combining Stochastic Adaptive Cubic Regularization with Negative Curvature for Nonconvex Optimization](https://mlsanity.com/paper/1906.11417/) (2019)
- [A Stochastic Quasi-Newton Method for Large-Scale Nonconvex Optimization with Applications](https://mlsanity.com/paper/1912.04456/) (2019)
- [adaQN: An Adaptive Quasi-Newton Algorithm for Training RNNs](https://mlsanity.com/paper/1511.01169/) (2015)

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

- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)

## Abstract (arXiv)

In this work we describe an Adaptive Regularization using Cubics (ARC) method for large-scale nonconvex unconstrained optimization using Limited-memory Quasi-Newton (LQN) matrices. ARC methods are a relatively new family of optimization strategies that utilize a cubic-regularization (CR) term in place of trust-regions and line-searches. LQN methods offer a large-scale alternative to using explicit second-order information by taking identical inputs to those used by popular first-order methods such as stochastic gradient descent (SGD). Solving the CR subproblem exactly requires Newton's method, yet using properties of the internal structure of LQN matrices, we are able to find exact solutions to the CR subproblem in a matrix-free manner, providing large speedups and scaling into modern size requirements. Additionally, we expand upon previous ARC work and explicitly incorporate first-order updates into our algorithm. We provide experimental results when the SR1 update is used, which show substantial speed-ups and competitive performance compared to Adam and other second order optimizers on deep neural networks (DNNs). We find that our new approach, ARCLQN, compares to modern optimizers with minimal tuning, a common pain-point for second order methods.