Timezone: »

 
Spotlight
Convergence of Cubic Regularization for Nonconvex Optimization under KL Property
Yi Zhou · Zhe Wang · Yingbin Liang

Thu Dec 06 01:55 PM -- 02:00 PM (PST) @ Room 517 CD
in Thu Track 3 -- Session 2 »

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.

Author Information

Yi Zhou (The Ohio State University)
Zhe Wang (Ohio State University)
Yingbin Liang (The Ohio State University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors