# Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2019.

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

- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method](https://mlsanity.com/paper/2308.14742/) (2023)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexity](https://mlsanity.com/paper/2409.10773/) (2024)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)
- [Aggregation in the Mirror Space (AIMS): Fast, Accurate Distributed Machine Learning in Military Settings](https://mlsanity.com/paper/2210.16181/) (2022)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)

## Abstract (arXiv)

In this paper, we study the iteration complexity of cubic regularization of Newton method for solving composite minimization problems with uniformly convex objective. We introduce the notion of second-order condition number of a certain degree and justify the linear rate of convergence in a nondegenerate case for the method with an adaptive estimate of the regularization parameter. The algorithm automatically achieves the best possible global complexity bound among different problem classes of uniformly convex objective functions with H"older continuous Hessian of the smooth part of the objective. As a byproduct of our developments, we justify an intuitively plausible result that the global iteration complexity of the Newton method is always better than that of the gradient method on the class of strongly convex functions with uniformly bounded second derivative.