Convergence of Cubic Regularization for Nonconvex Optimization under KL Property

Yi Zhou, Zhe Wang, Yingbin Liang

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 the 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 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.

Introduction

In the landscape of modern machine learning, nonconvex optimization is the norm rather than the exception. Training deep neural networks involves navigating complex terrains filled with saddle points—regions where the gradient is zero but the point is not a local minimum. While first-order methods like Gradient Descent (GD) often struggle or stall in these regions, second-order methods, specifically Cubic Regularization (CR), leverage Hessian information to identify descent directions and escape saddle points more efficiently.

This work provides a comprehensive analysis of CR convergence under the Kurdyka-Łojasiewicz (KL) property. The KL property is a powerful mathematical framework that describes the local geometry of nearly all functions encountered in practical optimization, from polynomials to log-exponentials. By utilizing this property, the authors establish that CR is order-wise faster than GD across a wide range of objective function geometries.

Analysis of Descent Properties

The researchers analyzed the standard CR update rule, which minimizes a third-order Taylor approximation of the objective function at each step. To compare CR with GD, they established fundamental inequalities for several optimality measures, including the function value gap, gradient norm, and the least eigenvalue of the Hessian matrix.

Comparison of descent properties between gradient descent and cubic regularization (M=L).

As illustrated in the table above, CR provides stronger descent guarantees. For instance, the function value decrease in CR is proportional to the cube of the step size ($\Vert \mathbf{x}_k - \mathbf{x}_{k-1} \Vert^3$), whereas in GD it is proportional to the square. Furthermore, CR provides a bound on the least eigenvalue of the Hessian, which is critical for escaping saddle points—a capability GD lacks in its basic form.

Convergence Rates and the KL Parameter

The convergence speed of these algorithms is fundamentally tied to the KL parameter ($\theta$), which measures the "sharpness" of the function near a stationary point. A larger $\theta$ corresponds to a sharper landscape, while a smaller $\theta$ indicates a flatter region where optimization is more difficult.

The study identifies a critical geometry threshold at $\theta = 1/3$. When the landscape is sharp ($\theta > 1/3$), CR achieves super-linear convergence. At the threshold $\theta = 1/3$, it achieves linear convergence. Even in extremely flat regions ($\theta < 1/3$), CR maintains a superior sub-linear rate compared to GD.

Asymptotic convergence rates for gradient descent and cubic regularization across different KL parameter regimes.

In the moderately sharp regime ($\theta \in [1/2, 1)$), GD converges linearly while CR achieves super-linear convergence. In the flattest regime ($\theta < 1/3$), the sub-linear rate of CR, $O(k^{-\frac{2}{1-3\theta}})$, is significantly faster than GD's $O(k^{-\frac{1}{1-2\theta}})$. This theoretical "speed limit" demonstrates that second-order information consistently provides an order-wise advantage.

Discussion and Future Directions

While this analysis focuses on asymptotic behavior—describing the algorithm's performance as it nears a solution—it provides a rigorous theoretical foundation for the efficiency of second-order methods in nonconvex settings. One practical limitation is the computational cost of each CR iteration, which requires processing the Hessian. However, the authors point toward "Inexact CR" as a viable path for large-scale applications.

Future work may involve applying this KL-based framework to other variants, such as Stochastic Variance-Reduced CR. Such methods could potentially combine the rapid convergence of second-order information with the scalability of stochastic optimization, offering a powerful tool for training massive machine learning models.

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 the 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 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