In this talk, we introduce a generalized metric subregularity condition, which serves as an extension of the well-studied metric subregularity, and is weaker than the uniform version (called error bound condition) that was recently employed in the quadratic convergence analysis of the cubic regularized Newton method.
We then establish an abstract extended convergence framework that enables one to derive superlinear convergence towards a specific target set (such as the second-order stationary points), under the introduced generalized metric subregularity condition or KL property. We also provide easily verifiable sufficient conditions for generalized metric subregularity with respect to the second-order stationary set under the strict saddle point property, and demonstrate that several important applications satisfy this condition. This, for example, includes the functions that arise in the over-parameterized compressed sensing model, best rank-one matrix approximation, and generalized phase retrieval problems.
As an application, we establish convergence analysis for high-order regularized Newton's method with momentum steps. Specifically, when applying this method to solve the over-parameterized compressed sensing model, we obtain global convergence with a quadratic convergence rate to a local minimizer, under the strict complementarity condition. In the absence of the strict complementarity condition, we obtain a sublinear convergence rate of $O(\frac{1}{k^2})$ to a local minimizer.