# Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2018.

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

- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function](https://mlsanity.com/paper/2310.11866/) (2023)
- [Two trust region type algorithms for solving nonconvex-strongly concave minimax problems](https://mlsanity.com/paper/2402.09807/) (2024)

## Abstract (arXiv)

In this paper, we consider an unconstrained optimization model where the objective is a sum of a large number of possibly nonconvex functions, though overall the objective is assumed to be smooth and convex. Our bid to solving such model uses the framework of cubic regularization of Newton's method. As well known, the crux in cubic regularization is its utilization of the Hessian information, which may be computationally expensive for large-scale problems. To tackle this, we resort to approximating the Hessian matrix via sub-sampling. In particular, we propose to compute an approximated Hessian matrix by either textituniformly/ or textitnon-uniformly/ sub-sampling the components of the objective. Based upon such sampling strategy, we develop accelerated adaptive cubic regularization approaches and provide theoretical guarantees on global iteration complexity of O(ε-1/3) with high probability, which matches that of the original accelerated cubic regularization methods citeJiang-2017-Unified using the textitfull/ Hessian information. Interestingly, we show that in the worst case scenario our algorithm still achieves an Oleft(log(ε-1)ε-5/6right) iteration complexity bound. The performances of the proposed methods on the regularized logistic regression problems show a clear effect of acceleration in terms of the epoch counts on several real data sets.