Convergence of Cubic Regularization for Nonconvex Optimization under KL Property

Yi Zhou, Zhe Wang, Yingbin Liang

Introduction

Most modern machine learning models, such as deep neural networks, are highly nonconvex. Their "loss landscapes" are riddled with hills, valleys, and—most problematically—saddle points. While standard Gradient Descent (GD) is effective at finding "stationary points" where the slope is zero, it often gets stuck or slows to a crawl near saddle points, resulting in suboptimal solutions.

Second-order methods like Cubic-regularized Newton’s method (CR) use curvature information (the Hessian) to navigate these landscapes, guaranteeing an escape from "strict" saddle points. However, until this paper, the exact convergence speed of CR for the vast majority of practical functions remained unclear, as previous proofs relied on highly restrictive geometric assumptions.

This paper provides the first comprehensive theoretical analysis of how CR converges on a broad class of nonconvex functions characterized by the ubiquitous Kurdyka-Łojasiewicz (KŁ) property. The authors prove that CR is not only guaranteed to find second-order stationary points but is also "order-wise" faster than standard gradient descent across a wide variety of function geometries.

Methods: Cubic Regularization and the KŁ Property

Unlike standard Newton's method, which uses a quadratic approximation, CR uses a third-order Taylor expansion (a cubic model) to determine its next step.

Comparison of descent bounds between Gradient Descent and Cubic Regularization.

To analyze CR's performance, the authors utilize the KŁ property, a generalized framework that describes almost all functions encountered in real-world engineering (including most semi-algebraic and sub-analytic functions). The KŁ property is parameterized by a value $\theta \in (0, 1]$:

  • Large $\theta$ (near 1): Represents "sharp" or "steep" local geometry.
  • Small $\theta$ (near 0): Represents "flat" local geometry.

By deriving new recursive inequalities, the authors characterize the convergence rates for four different metrics: the function value gap, the distance to the solution, the gradient norm, and the least eigenvalue of the Hessian. They also extend this analysis to Inexact CR, where the gradient and Hessian are only approximations—a common necessity in large-scale computing.

Key Insights and Convergence Results

The speed of CR is a direct reflection of the local geometry. The most significant insight from this work is that under the same KŁ conditions, CR is always order-wise faster than Gradient Descent. In very flat regions where GD is painfully slow, CR’s second-order "vision" allows it to take much more efficient paths. Furthermore, the sequence of iterates generated by CR has a finite length (it is "absolutely summable"), guaranteeing the algorithm won't oscillate forever but will head straight for a stable solution.

The paper categorizes convergence into distinct regimes based on the KŁ parameter $\theta$:

Asymptotic convergence rates of Gradient Descent vs. Cubic Regularization across KŁ parameter regimes.
  1. The "Sharp" Regime ($\theta \in [1/3, 1]$): CR achieves (super)-linear convergence. It reaches the neighborhood of a solution extremely quickly.
  2. The "Flat" Regime ($\theta \in (0, 1/3)$): CR converges sub-linearly. However, its rate of $\mathcal{O}(k^{-\frac{2}{1-3\theta}})$ is still significantly better than Gradient Descent's rate of $\mathcal{O}(k^{-\frac{1}{1-2\theta}})$.
  3. Second-Order Stationarity: CR is proven to meet the second-order stationary condition (where the gradient is zero and the Hessian is positive semi-definite) at these same improved rates.

Limitations and Future Work

While CR requires fewer iterations than GD, each iteration carries a higher computational overhead because it involves solving a cubic subproblem and computing a Hessian. Although efficient solvers exist, the per-iteration cost remains a practical trade-off. Additionally, the analysis is primarily "asymptotic" or local, describing behavior as the algorithm approaches the solution set.

Future research directions suggested by the authors include applying this KŁ framework to more efficient variants, such as stochastic variance-reduced CR. This could potentially combine the rapid convergence of second-order methods with the scalability required for massive stochastic optimization tasks.

Summary updated

Abstract

Cubic-regularized Newton's method (CR) is a popular algorithm that guarantees to produce a second-order stationary solution for solving nonconvex optimization problems. However, existing understandings of convergence rate of CR are conditioned on special types of geometrical properties of the objective function. In this paper, we explore the asymptotic convergence rate of CR by exploiting the ubiquitous Kurdyka-Lojasiewicz (KL) property of the nonconvex objective functions. In specific, we characterize the asymptotic convergence rate of various types of optimality measures for CR including function value gap, variable distance gap, gradient norm and least eigenvalue of the Hessian matrix. Our results fully characterize the diverse convergence behaviors of these optimality measures in the full parameter regime of the KL property. Moreover, we show that the obtained asymptotic convergence rates of CR are order-wise faster than those of first-order gradient descent algorithms under the KL property.
BibTeX
@inproceedings{zhou2018convergence,
  author = {Yi Zhou and Zhe Wang and Yingbin Liang},
  title = {{Convergence of Cubic Regularization for Nonconvex Optimization under KL Property}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJ-cnIbuWB},
}
Figure