Convergence of Cubic Regularization for Nonconvex Optimization under KŁ Property
Yi Zhou Department of ECE The Ohio State University、Zhe Wang Department of ECE The Ohio State University \ANDYingbin Liang Department of ECE The Ohio State University
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-Łojasiewicz (KŁ ) 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 KŁ 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 KŁ property.
中文速览
三阶正则化牛顿法（Cubic-Regularized Newton's method，CR）是一种能够跳出鞍点、收敛到二阶稳定点的优化算法，但此前对其收敛速度的分析仅限于少数特殊的几何条件，难以覆盖实际应用中的复杂非凸目标函数。这篇论文借助Kurdyka-Łojasiewicz（KŁ）性质——一种被多项式、对数、指数等绝大多数实用函数普遍满足的局部几何刻画工具——系统地分析了CR在非凸优化中的渐近收敛速度。研究对函数值差、变量距离、梯度范数和Hessian矩阵最小特征值四类最优性度量逐一给出了精确的收敛率刻画，覆盖KŁ参数θ的全部取值范围，结果从次线性到超线性不等，并统一推广了此前只在特殊参数情形成立的已有结论。更重要的是，论文从量级上证明了CR在KŁ性质下的收敛速度比一阶梯度下降算法快得多，从理论上确立了二阶算法在非凸优化中的明确优势。
原文 arXiv:1808.07382;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1808.07382v1