#  Generalized Metric Subregularity with Applications to
High-Order Regularized Newton Methods

Guoyin Li111University of New South Wales, Sydney 2052, Australia
(g.li@unsw.edu.au). Research of this author was partly supported by the
Australian Research Council under Discovery Project DP190100555. Boris
Mordukhovich222Wayne State University, Detroit, MI 48202, USA
(aa1086@wayne.edu). Research of this author was partly supported by the US
National Science Foundation under grant DMS-2204519, by the Australian
Research Council under Discovery Project DP190100555, and by Project 111 of
China under grant D21024. Jiangxing Zhu333Yunnan University, Kunming 650091,
China (jxzhu@ynu.edu.cn). The research of this author was partly supported by
the Basic Research Program of Yunnan Province (Grant No. 202201AT070066), the
Project for Young-notch Talents in the Ten Thousand Talent Program of Yunnan
Province (Grant No. YNWR-QNBJ-2020-080), and the National Natural Science
Foundation of People’s Republic of China (Grant Nos. 12171419 and 12261109).

###### Abstract

This paper pursues a twofold goal. First, we introduce and study in detail a
new notion of variational analysis called generalized metric subregularity,
which is a far-going extension of the conventional metric subregularity
conditions. Our primary focus is on examining this concept concerning first-
order and second-order stationary points. We develop an extended convergence
framework that enables us to derive superlinear and quadratic convergence
under the generalized metric subregularity condition, broadening the widely
used KL convergence analysis framework. We present verifiable sufficient
conditions to ensure the proposed generalized metric subregularity condition
and provide examples demonstrating that the derived convergence rates are
sharp. Second, we design a new high-order regularized Newton method with
momentum steps, and apply the generalized metric subregularity to establish
its superlinear convergence. Quadratic convergence is obtained under
additional assumptions. Specifically, when applying the proposed method to
solve the (nonconvex) over-parameterized compressed sensing model, we achieve
global convergence with a quadratic local convergence rate towards a global
minimizer under a strict complementarity condition.
Keywords: Variational analysis and optimization, generalized metric
subregularity, error bounds, high-order regularized Newton methods, Kurdyka-
Łojasiewicz property, superlinear and quadratic convergence
Mathematics Subject Classification (2020) 49J53, 49M15, 90C26

##  1 Introduction

It has been well recognized, especially during the recent years, that concepts
and tools of modern variational analysis play a crucial role in the design and
justification of numerical algorithms in optimization and related areas. We
mention, in particular, generalized Newton methods for which, in addition to
the fundamental developments summarized in [12, 17, 19], new approaches and
results have been recently proposed in [1, 14, 18, 22, 27] among other
publications. A common feature of these developments is the usage of metric
regularity/subregularity assumptions in a certain form. Another common feature
of the aforementioned publications is justifying superlinear convergence rates
under some nondegeneracy condition. For example, [32] develops the cubic
regularization (CR) method for minimizing a twice continuously differentiable
function, which is now widely recognized as a globally convergent variant of
Newton’s method with superior iteration complexity [10, 32]. The local
quadratic convergence of CR method was derived under a nondegeneracy condition
in [32]. In [40], the authors propose an error bound condition related to the
second-order stationary set and examined the quadratic local convergence for
the cubic regularized Newton method under this condition, extending the
results in [32]. Interestingly, it was shown in [40] that this error bound
condition can be applied to nonconvex and degenerate cases being satisfied
with overwhelming probability for some concrete nonconvex optimization
problems that arise in phase retrieval and low-rank matrix recovery.

On the other hand, it is known that the metric subregularity of the
subdifferential mapping has a close relationship with the Kurdyka-Łojasiewicz
$(KL)$ property. The KL property is satisfied for various important classes of
functions arising in diverse applications, and it has emerged as one of the
most widely used tools for analyzing the convergence of important numerical
algorithms [4, 5]. In particular, if the potential function of the algorithm
satisfies the KL property and the associated desingularization function
$\vartheta$ involved in the KL property takes the form that
$\vartheta(t)=c\,t^{1-\theta}$ with $c>0$ and $\theta\in[0,1)$, then the
corresponding exponent $\theta$ determines the linear or sublinear convergence
rate of the underlying algorithms [4, 5, 21, 39]. Although the KL property and
its associated analysis framework are well-adopted in the literature, this
framework, in general, cannot obtain or detect superlinear or quadratic
convergence rate, which is typical for many second-order numerical methods
including Newton-type methods.

In this paper, we introduce and thoroughly investigate novel generalized
metric subregularity conditions, significantly extending conventional metric
subregularity and error bound conditions from [40]. We develop an abstract
extended convergence framework that enables us to derive superlinear and
quadratic convergence towards specific target sets, such as first-order and
second-order stationary points, under the introduced generalized metric
subregularity condition. This new framework extends the widely used KL
convergence analysis framework. We provide examples demonstrating that the
derived quadratic convergence rates are sharp, meaning they can be attained.
We also present verifiable sufficient conditions that ensure the proposed
generalized metric subregularity condition and showcase that the sufficient
conditions are satisfied for functions that arise in practical models
including the over-parameterized compressed sensing, best rank-one matrix
approximation, and generalized phase retrieval problems. Finally, we use the
generalized metric subregularity condition to establish superlinear (and in
some cases quadratic) convergence of the newly proposed high-order regularized
Newton methods with momentum. Specifically, when applying the proposed method
to solve the (nonconvex) over-parameterized compressed sensing model, we
achieve global convergence with a quadratic local convergence rate towards a
global minimizer under a strict complementarity condition.

Organization. The main achievements of the current research are summarized in
the concluding Section 8. The rest of the paper is structured as follows.

Section 2 presents basic definitions and preliminaries from variational
analysis and generalized differentiation broadly used in what follows. In
Section 3, we define two versions of generalized metric subregularity for
subgradient mappings with respect to first-order and second-order stationary
points and then discuss their relationships with known in the literature and
with growth conditions.

Section 4 develops a new framework for abstract convergence analysis to
establish superlinear and quadratic convergence rates of numerical algorithms
under generalized metric subregularity. Being of their independent interest,
the obtained results are instrumental to justify such fast convergent rates
for our main high-order regularized Newtonian algorithm in the subsequent
parts of the paper. In Section 5, we provide some abstract convergence
analysis under the Kurdyka-Łojasiewicz property.

Section 6 revisits generalized metric subregularity while now concentrating on
this property with respect to second-order stationarity points. Our special
attention is paid to the strict saddle point and weak separation properties,
which provide verifiable sufficient conditions for the fulfillment of
generalized metric subregularity. Here we present several examples of
practical modeling, where these properties are satisfied.

In Section 7, we design the family of high-order regularized Newton methods
with momentum steps for problems of ${\cal C}^{2}$ optimization, where the
order of the method is determined by the Hölder exponent $q\in(0,1]$ of the
Hessian matrix associated with the objective function. Using the machinery of
generalized metric subregularity with respect to second-order stationary
points leads us to establishing superlinear convergence of iterates with
explicit convergence rates and also quadratic convergence in certain
particular settings.

Section 8 provides an overview of the major results obtained in the paper with
discussing some directions of the future research. Section 9 is an appendix,
which contains the proofs of some technical lemmas.

##  2 Preliminaries from Variational Analysis

Let $\mathbb{R}^{m}$ be the $m$-dimensional Euclidean space with the inner
product denoted by $\langle x,y\rangle=x^{T}y$ for all $x,y\in\mathbb{R}^{m}$
and the norm $\|\cdot\|$. The symbols $B_{\mathbb{R}^{m}}(x,\gamma)$ and
$B_{\mathbb{R}^{m}}[x,\gamma]$ stand for the open and closed ball centered at
$x$ with radius $\gamma$, respectively. Given a symmetric matrix
$M\in\mathbb{R}^{m\times m}$, the notation $M\succeq 0$ signifies that $M$ is
positive-semidefinite. We use $\mathbb{N}$ to denote the set of nonnegative
integrals $\\{0,1,\ldots\\}$.

An extended-real-valued function
$f\colon\mathbb{R}^{m}\to\overline{\mathbb{R}}:=(-\infty,\infty]$ is proper if
${\rm dom}\,f:=\\{x\in\mathbb{R}^{m}\;|\;f(x)<\infty\\}\neq\emptyset$ for its
effective domain. The (limiting, Mordukhovich) subdifferential for such
functions $f$ at $\bar{x}\in\mbox{\rm dom}\,f$ is

$\begin{array}[]{ll}\partial
f(\bar{x}):=\Big{\\{}v\in\mathbb{R}^{m}\;\Big{|}&\exists\,x_{k}\to\bar{x}\;\mbox{
with }\;f(x_{k})\to f(\bar{x})\;\mbox{ as }\;k\to\infty\;\mbox{ with}\\\
&\displaystyle\liminf_{x\to x_{k}}\frac{f(x)-f(x_{k})-\langle
v,x-x_{k}\rangle}{\|x-x_{k}\|}\geq 0\;\mbox{ for all
}\;k\in\mathbb{N}\Big{\\}}.\end{array}$ (2.1)

The subdifferential (2.1) reduces to the subdifferential of convex analysis
when $f$ is convex and to the gradient $\nabla f(\bar{x})$ when $f$ is
continuously differentiable (${\cal C}^{1}$-smooth) around $\bar{x}$. For the
general class of lower semicontinuous (l.s.c.) functions, $\partial f$ enjoys
comprehensive calculus rules and is used in numerous applications of
variational analysis and optimization; see, e.g., the books [26, 27, 37] and
the references therein.

Having (2.1), consider the set of first-order stationary points of an l.s.c.
function $f\colon\mathbb{R}^{m}\to\overline{\mathbb{R}}$ defined by

$\Gamma:=\big{\\{}x\in\mathbb{R}^{m}\;\big{|}\;0\in\partial f(x)\big{\\}}.$
(2.2)

Suppose that $f$ is a twice continuously differentiable (${\cal
C}^{2}$-smooth) function and denote the collection of second-order stationary
points of $f$ at $x\in\mathbb{R}^{m}$ by

$\Theta:=\big{\\{}x\in\mathbb{R}^{m}\;\big{|}\;\nabla
f(x)=0,\;\nabla^{2}f(x)\succeq 0\big{\\}}.$ (2.3)

As in [42], we say that $\varphi:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$,
where $\mathbb{R}_{+}:=\\{t\;|\;t\geq 0\\}$, is an admissible function if
$\varphi(0)=0$ and $\varphi(t)\rightarrow 0\Rightarrow t\rightarrow 0$. It is
well known that for convex admissible functions, the directional derivative

$\varphi_{+}^{\prime}(t):=\lim\limits_{s\rightarrow
0^{+}}\frac{\varphi(t+s)-\varphi(t)}{s}$

always exists being nondecreasing on $\mathbb{R}_{+}$. Furthermore (see, e.g.,
[43, Theorem 2.1.5]), $\varphi_{+}^{\prime}$ is increasing on $\mathbb{R}_{+}$
if and only if $\varphi$ is strictly convex, i.e.,

$\varphi(\lambda
t_{1}+(1-\lambda)t_{2})<\lambda\varphi(t_{1})+(1-\lambda)\varphi(t_{2})$

for any $\lambda\in(0,1)$ and $t_{1},t_{2}\in\mathbb{R}_{+}$ with $t_{1}\neq
t_{2}$. It is also known that a convex function $\varphi$ is differentiable on
$\mathbb{R}_{+}$ if and only if $\varphi_{+}^{\prime}$ is continuous on
$\mathbb{R}_{+}$. The following lemma from [43, Theorem 2.1.5] is used below.

######  Lemma 2.1 (properties of convex admissible functions).

Let $\varphi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be a convex admissible function.
Then we have the relationships:
(i)
$0<\frac{\varphi(t_{1})}{t_{1}}\leq\varphi_{+}^{\prime}(t_{1})\leq\varphi_{+}^{\prime}(t_{2})\;\;{\rm
for\;all}\;t_{1},t_{2}\in(0,\;\infty)\;{\rm with}\;t_{1}\leq t_{2}.$
(ii)
$\varphi(t)\geq\varphi_{+}^{\prime}\left(\frac{t}{2}\right)\frac{t}{2}\;\mbox{
for all }\;\in(0,\infty).$

Finally in this section, we recall the celebrated property often used in
convergence analysis.

######  Definition 2.2 (Kurdyka-Łojasiewicz property).

Let $f:\mathbb{R}^{m}\to\overline{\mathbb{R}}$ be a proper lower l.s.c.
function, and let $\vartheta:[0,\eta)\to\mathbb{R}_{+}$ be a continuous
concave function. We say that $f$ has the Kurdyka-Łojasiewicz $(KL)$ property
at $\overline{x}$ with respect to $\vartheta$ if the following conditions
hold:
(i) $\vartheta(0)=0$ and $\vartheta$ is continuously differentiable on
$(0,\eta)$.
(ii) $\vartheta^{\prime}(s)>0$ for all $s\in(0,\eta)$.
(iii) There exists $\varepsilon>0$ such that

$\vartheta^{\prime}(f(x)-f(\overline{x}))d(0,\partial f(x))\geq 1$

for all $x\in
B_{\mathbb{R}^{m}}(\overline{x},\varepsilon)\cap[f(\overline{x})<f<f(\overline{x})+\eta]$,
where $d(\cdot,S)$ stands for the distance function associated with the set
$S$. If in addition $\vartheta$ takes the form of
$\vartheta(t)=c\,t^{1-\theta}$ for some $c>0$ and $\theta\in[0,1)$, then we
say $f$ satisfies the KL property at $\bar{x}$ with the KL exponent $\theta$.

A widely used class of functions satisfying the KL property consists of
subanalytic functions. It is known that the maximum and minimum of finitely
many analytic functions and also semialgebraic functions (such as
$\|x\|_{p}=[\sum_{i=1}^{m}|x_{i}|^{p}]^{\frac{1}{p}}$ with $p$ being a
nonnegative rational number) are subanalytic. We refer the reader to [4, 5, 6,
21] for more details on the KL property and its exponent version, as well as
on subanalytic functions.

##  3 Generalized Metric Subregularity

The main variational concept for the subdifferential (2.1) of an extended-
real-valued function used in this paper is introduced below, where we consider
its two versions.

######  Definition 3.1 (generalized metric subregularity).

Let $f:\mathbb{R}^{m}\to\overline{\mathbb{R}}$ be a proper l.s.c. function,
let $\Gamma$ be taken from (2.2), and let
$\psi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be an admissible function. Given a
target set $\Xi\subset\Gamma$ and a point $\overline{x}\in\Xi$, we say that:
(i) The subdifferential $\partial f$ satisfies the (pointwise) generalized
metric subregularity property with respect to $(\psi,\Xi)$ at $\overline{x}$
if there exist $\kappa,\delta\in(0,\infty)$ such that

$\psi\big{(}d(x,\Xi)\big{)}\leq\kappa\,d\big{(}0,\partial f(x)\big{)}\;\mbox{
for all }\;x\in B_{\mathbb{R}^{m}}(\overline{x},\delta).$ (3.1)

(ii) The subdifferential $\partial f$ satisfies the uniform generalized metric
subregularity property with respect to $(\psi,\Xi)$ if there exist
$\kappa,\rho\in(0,\infty)$ such that

$\psi\big{(}d(x,\Xi)\big{)}\leq\kappa\,d\big{(}0,\partial f(x)\big{)}\;\mbox{
for all
}\;x\in\mathcal{N}(\Xi,\rho):=\big{\\{}x\in\mathbb{R}^{m}\;\big{|}\;\;d(x,\Xi)\leq\rho\big{\\}}.$
(3.2)

(iii) If $\psi(t)=t$ in (i) and (ii), then we simply say that $\partial f$
satisfies the metric subregularity (resp. uniform metric subregularity)
property with respect to $\Xi$.

######  Remark 3.2 (connections with related notions).

Let us briefly discuss connections of the generalized metric subregularity
notions from Definition 3.1 with some related notions.

$\bullet$ Consider the case where the target set $\Xi:=\Gamma$ is the set of
first-order stationary points (2.2). If $\psi(t)=t$, then (3.1) reduces to the
conventional notion of metric subregularity applied to subgradient mappings.
If $\psi(t)=t^{p}$ for $p>0$, which we referred to as exponent metric
subregularity, this notion has also received a lot of attention due to the
important applications in numerical optimization. It is called the Hölder
metric subregularity if $p>1$, and the high-order metric subregularity if
$p\in(0,1)$. Other cases of convex and smooth admissible functions are
considered in [42]. The refer the reader to [3, 13, 20, 28, 30, 41, 42] and
the bibliographies therein for more details.

$\bullet$ In the case where $f$ is a ${\cal C}^{2}$-smooth function,
$\psi(t)=t$, and the target set $\Xi=\Theta$ consists of second-order
stationary points (2.3), Definition 3.1(ii) takes the form: there exist
$\kappa,\rho\in(0,\infty)$ such that

$d(x,\Theta)\leq\kappa\|\nabla f(x)\|\;\mbox{ for all
}\;x\in\mathcal{N}(\Theta,\rho):=\big{\\{}x\in\mathbb{R}^{m}\;\big{|}\;\;d(x,\Theta)\leq\rho\big{\\}},$
(3.3)

i.e., it falls into the framework of the uniform generalized metric
subregularity (3.2) for smooth functions. In this case, it was referred to as
the error bound (EB) condition [40, Assumption 2]. This condition plays a key
role in [40] to justify the quadratic convergence of the cubic regularized
Newton method.

Now we present three examples illustrating several remarkable features of the
introduced notions. The first example shows that the generalized metric
subregularity from (3.1) can go beyond the exponent cases. Note that the usage
of metric subregularity in the nonexponent setting has been recently
identified in [23] for the case of exponential cone programming.

######  Example 3.3 (nonexponent generalized metric subregularity).

Let $\varphi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be given by

$\varphi(t):=\left\\{\begin{array}[]{ll}\int_{0}^{t}e^{-\frac{1}{s}}ds,&\hbox{$t>0$,}\\\
0,&\hbox{$t=0$}.\end{array}\right.$

Define $f:\mathbb{R}\to\mathbb{R}$ by $f(x):=\varphi(|x|)$ for all
$x\in\mathbb{R}$. It is easy to see that $\varphi$ is a differentiable convex
function on $\mathbb{R}_{+}$, and that we have

$\partial
f(x)=\left\\{\begin{array}[]{ll}\varphi^{\prime}(|x|)\frac{x}{|x|},&\hbox{$x\neq
0$,}\\\
0,&\hbox{$x$}=0\end{array}\right.\quad\mbox{and}\quad\mathop{\arg\min}_{x\in\mathbb{R}}f(x)=\Gamma=\\{0\\}.$

This tells us that
$\varphi^{\prime}(d(x,\Gamma))=\varphi^{\prime}(|x|)=d(0,\partial f(x))$ for
all $x\in\mathbb{R}$, and so $\partial f$ has the generalized metric
subregularity property with respect to $(\varphi^{\prime},\Gamma)$. On the
other hand, for any $q\in(0,\infty)$ we get

$\lim_{x\to 0}\frac{d(x,\Gamma)^{q}}{d(0,\partial f(x))}=\lim_{x\to
0}\frac{|x|^{q}}{e^{-\frac{1}{|x|}}}=\lim_{t\to
0^{+}}e^{\frac{1}{t}}t^{q}=\infty,$

which shows that $\partial f$ does not enjoy any exponent-type metric
subregularity.

The next example illustrates the fulfillment of the generalized metric
subregularity (3.2) with respect of $(\psi,\Theta))$ for some admissible
function $\psi$, while the error bound condition (3.3) from [40] fails.

######  Example 3.4 (generalized metric subregularity vs. error bound
condition).

Given $p>2$, define a ${\cal C}^{2}$-smooth function
$f:\mathbb{R}\to\mathbb{R}$ by

$f(x):=\left\\{\begin{array}[]{ll}x^{p},&\hbox{$x\geq 0$,}\\\
0,&\hbox{$x<0$}\end{array}\right.$

for which we get by the direct calculations that

$\nabla f(x)=\left\\{\begin{array}[]{ll}px^{p-1},&\hbox{$x\geq 0$,}\\\
0,&\hbox{$x<0$,}\end{array}\right.\;\nabla^{2}f(x)=\left\\{\begin{array}[]{ll}p(p-1)x^{p-2},&\hbox{$x\geq
0$,}\\\
0,&\hbox{$x<0$},\end{array}\right.\;\mbox{and}\;\;\Theta=\Gamma=(-\infty,0].$

It is easy to see that $d(x,\Theta)=x$ and $d(0,\nabla f(x))=px^{p-1}$ for
$x>0$, while for $x\leq 0$ we have $d(x,\Theta)=d(0,\nabla f(x))=0$. This
implies therefore that

$\limsup_{x\to 0^{+}}\frac{d(x,\Theta)}{d(0,\nabla
f(x))}=\infty\quad\mbox{and}\quad d(x,\Theta)^{p-1}\leq\frac{1}{p}d(0,\nabla
f(x))\quad\mbox{whenever }\;x\in\mathbb{R}.$

Consequently, the EB condition (3.3) fails, while $\nabla f$ enjoys the
generalized metric subregularity property with respect to $(\psi,\Theta)$ at
$0$, where $\psi(t):=t^{p-1}$.

For a fixed admissible function $\psi$ and a given set $\Xi\subset\Gamma$, we
observe directly from the definitions that uniform generalized metric
subregularity with respect to $(\psi,\Xi)$ yields the generalized metric
subregularity at each point $\overline{x}$ of $\Xi$. The following simple one-
dimensional example shows that the reverse implication fails.

######  Example 3.5 (pointwise version is strictly weaker than uniform version
for generalized metric subregularity).

Consider $f(x):=(x-a)^{2}(x-b)^{2p}$ for $p>1$ with $a,b\in\mathbb{R}$ and
$0\leq a<b$. We get $\nabla
f(x)=f^{\prime}(x)=2(x-a)(x-b)^{2p}+2p(x-a)^{2}(x-b)^{2p-1}$ and
$f^{\prime\prime}(x)=2(x-b)^{2p}+8p(x-a)(x-b)^{2p-1}+2p(2p-1)(x-a)^{2}(x-b)^{2p-2}$.
Furthermore, $\Gamma=\\{a,b,\frac{b+pa}{1+p}\\}$ and $\Theta=\\{a,b\\}$. Thus
there exists $M>0$ such that $d(x,\Theta)=|x-a|\leq Md(0,\nabla f(x))$ for all
$x\in B_{\mathbb{R}}(a,\epsilon)$ with $\epsilon<\frac{b-a}{4}$. This tells us
that $\nabla f$ satisfies the generalized metric subregularity property with
respect to $(\psi,\Xi)$ at $\overline{x}=a$ with $\psi(t)=t$ and $\Xi=\Theta$.

On the other hand, $\nabla f$ does not satisfy the uniform generalized metric
subregularity with respect to $(\psi,\Xi)$. Indeed, for any $\epsilon_{k}>0$
with $\epsilon_{k}\rightarrow 0$, we get
$x_{k}=b+\epsilon_{k}\in\mathcal{N}(\Theta,\epsilon_{k})$ and
$\frac{d(x_{k},\Theta)}{\|\nabla
f(x_{k})\|}=O(\frac{\epsilon_{k}}{\epsilon_{k}^{2p-1}})\rightarrow\infty$.

It has been well recognized in variational analysis that there exist close
relationships between metric subregularity of subgradient mappings and second-
order growth conditions for the functions in question; see [3, 11, 27] with
more details. We now extend such relationships to the case of generalized
metric subregularity. The following useful lemma is of its own interest.

######  Lemma 3.6 (first-order stationary points of compositions).

Let $f(x)=(\varphi\circ g)(x)$, where
$\varphi:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ is a proper l.s.c. convex
function, and where $g:\mathbb{R}^{m}\to\mathbb{R}^{n}$ is a ${\cal
C}^{1}$-smooth mapping with the surjective derivative $\nabla g(\overline{x})$
at some first-order stationary point $\overline{x}\in\Gamma$ associated with
the composition $f$ in (2.2). Then there exists $\delta>0$ such that we have
the inclusion

$\Gamma\cap
B_{\mathbb{R}^{m}}(\overline{x},\delta)\subseteq\mathop{\arg\min}_{x\in\mathbb{R}^{m}}f(x).$
(3.4)

###### Proof.

The surjectivity of $\nabla g(\overline{x})$ for smooth $g$ allows us to
deduce from the Lyusternik–Graves theorem (see, e.g., [26, Theorem 1.57]) the
existence of $\delta,L>0$ such that $\nabla g(x)$ is surjective on
$B_{\mathbb{R}^{m}}(\overline{x},\delta)$ and

$\|\nabla g(x)^{T}v\|\geq L\|v\|\quad\mbox{whenever }\;(x,v)\in
B_{\mathbb{R}^{m}}(\overline{x},\delta)\times\mathbb{R}^{n}.$ (3.5)

Consequently, it follows from [26, Proposition 1.112] that

$\partial f(x)=\nabla g(x)^{T}\partial\varphi(g(x))\quad\mbox{for all }\;x\in
B_{\mathbb{R}^{m}}(\overline{x},\delta).$ (3.6)

Picking any $u\in\Gamma\cap B_{\mathbb{R}^{m}}(\overline{x},\delta)$, we
deduce from (3.6) that

$0\in\partial f(u)=\nabla g(u)^{T}\partial\varphi(g(u)).$

Combining this with (3.5) yields $0\in\partial\varphi(g(u))$. Hence $g(u)$ is
a minimizer of the convex function $\varphi$, and

$f(u)=\varphi(g(u))\leq\varphi(g(x))=f(x)\;\mbox{ for
all}\;x\in\mathbb{R}^{m},$

which gives us (3.4) and thus completes the proof. ∎

Now we are ready to establish relationships between the generalized metric
subregularity and corresponding growth conditions extending the known ones [3,
11] when $\psi(t):=t^{2}$, $\overline{\psi}(t):=t$ and $\Xi=\Gamma$.

######  Theorem 3.7 (generalized metric subregularity via growth conditions).

Let $f(x)=(\varphi\circ g)(x)$ in the setting of Lemma 3.6. Consider the
following statements:
(i)  There exists an an admissible function
$\psi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ and constants
$\gamma_{1},\kappa_{1}\in(0,\infty)$ such that

$f(x)\geq f(\overline{x})+\kappa_{1}{\psi}(d(x,\Xi))\quad\mbox{for all }\;x\in
B_{\mathbb{R}^{m}}(\overline{x},\gamma_{1}).$ (3.7)

(ii) There exists an an admissible function
$\overline{\psi}:\mathbb{R}_{+}\to\mathbb{R}_{+}$ and constants
$\gamma_{2},\kappa_{2}\in(0,\infty)$ such that

$\overline{\psi}(d(x,\Xi))\leq\kappa_{2}d(0,\partial f(x))\quad\mbox{for all
x}\;\in B_{\mathbb{R}^{m}}(\overline{x},\gamma_{2}).$

Then implication ${\rm(i)}\Rightarrow{\rm(ii)}$ holds with
$\overline{\psi}(t):={\psi}_{+}^{\prime}(\frac{t}{2})$ if $\psi$ is convex and
$\lim_{t\to 0^{+}}\psi_{+}^{\prime}(t)=\psi_{+}^{\prime}(0)=0$, while the
reverse one ${\rm(ii)}\Rightarrow{\rm(i)}$ is always satisfied with
$\psi(t):=\int_{0}^{t}\,\overline{\psi}(s)ds$.

###### Proof.

To verify ${\rm(i)}\Rightarrow{\rm(ii)}$, we proceed as in the proof of Lemma
3.6 and find $\delta,L>0$ such that (3.4), (3.5), and (3.6) hold. Letting
$\widetilde{\delta}:=\min\\{\gamma_{1},\frac{\delta}{2}\\}$ and then picking
any $x\in B_{\mathbb{R}^{m}}(\overline{x},\widetilde{\delta})$ and
$u\in\partial f(x)$, take a sequence $\\{x_{k}\\}\subset\Xi$ such that
$\|x-x_{k}\|\to d(x,\Xi)$ as $k\to\infty$. Noting that $\overline{x}\in\Xi$
and $\|x-\overline{x}\|<\widetilde{\delta}\leq\frac{\delta}{2}$, assume
without loss of generality that $\\{x_{k}\\}$ entirely lies in $\Xi\cap
B_{\mathbb{R}^{m}}(\overline{x},2\widetilde{\delta})$. Select further
$L_{0}>0$ with $\|g(x_{2})-g(x_{1})\|\leq L_{0}\|x_{1}-x_{2}\|$ for all
$x_{1},x_{2}\in B_{\mathbb{R}^{m}}(\overline{x},\delta)$ and show that

$f(x_{k})\geq f(x)-\frac{L_{0}}{L}\|u\|\cdot\|x_{k}-x\|\;\mbox{ for all
}\;k\in\mathbb{N}$ (3.8)

whenever $u\in\partial f(x)$. Indeed, it follows from (3.5) and (3.6) that for
any $u\in\partial f(x)$ there is $v\in\partial\varphi(g(x))$ with

$u=\nabla g(x)^{T}v\quad\mbox{and}\quad L\|v\|\leq\|u\|.$

Combining the latter with the convexity of $\varphi$ gives us

$\displaystyle f(x)-f(x_{k})=\varphi(g(x))-\varphi(g(x_{k}))\leq\langle
v,g(x)-g(x_{k})\rangle$ $\displaystyle\leq\|v\|\cdot\|g(x)-g(x_{k})\|\leq
L_{0}\|v\|\cdot\|x-x_{k}\|\leq\frac{L_{0}}{L}\|u\|\cdot\|x-x_{k}\|$

for all $k\in\mathbb{N}$, and thus brings us to (3.8). Note further that (3.4)
ensures that $f(x_{k})=f(\overline{x})$ for all $k\in\mathbb{N}$. Letting
there $k\to\infty$ and denoting $\ell:=\frac{L_{0}}{L}$, we get
$f(x)-f(\overline{x})\leq\ell\|u\|d(x,\Xi)$, which yields in turn

$f(x)-f(\overline{x})\leq\ell d\left(0,\partial f(x)\right)d(x,\Xi)\;\mbox{
whenever }\;x\in B_{\mathbb{R}^{m}}(\overline{x},\widetilde{\delta}).$

This allows us to derive from (3.7) that

$0<\frac{\kappa_{1}}{\ell}\frac{\psi\left(d(x,\Xi)\right)}{d(x,\Xi)}\leq
d\left(0,\partial f(x)\right)\;\mbox{ for all }\;x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\widetilde{\delta}\right)\setminus{\rm
cl}(\Xi),$

where ${\rm cl}(\Xi)$ stands the closure of $\Xi$. Employing Lemma 2.1(ii)
tells us that

$\frac{\kappa_{1}}{2\ell}\psi_{+}^{\prime}\left(\frac{d(x,\Xi)}{2}\right)\leq
d\left(0,\partial f(x)\right)$

for any $x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\widetilde{\delta}\right)\setminus{\rm
cl}(\Xi)$, and thus it follows from $\psi_{+}^{\prime}(0)=0$ that (ii) is
satisfied. The reverse implication (ii)$\Rightarrow$(i) is a consequence of
Lemma 3.6 and [38, Theorem 4.2]. ∎

##  4 Abstract Framework for Convergence Analysis

In this section, we develop a general framework for convergence analysis of an
abstract minimization algorithm to ensure its superlinear and quadratic
convergence. This means finding appropriate conditions on an abstract
algorithm structure and the given objective function under which the generated
iterates exhibit the desired fast convergence. We’ll see that the generalized
metric subregularity is an important condition to establish fast convergence.
The obtained abstract results are implemented in Section 7 to derive specific
convergence conditions for the newly proposed high-order regularized Newton
method with momentum.

Our study in this section focuses on a coupled sequence
$\\{(x_{k},e_{k})\\}\subset\mathbb{R}^{m}\times\mathbb{R}_{+}$, where
$\\{x_{k}\\}$ is the main sequence generated by the algorithm, and where
$\\{e_{k}\\}$ is an auxiliary numerical sequence that serves as a surrogate
for $\|x_{k+1}-x_{k}\|$ (the magnitude of the successive change sequence).
Throughout this section, we assume that these two sequences satisfy the
following set of basic assumptions (BA):

  * (i)

Descent condition:

$f(x_{k+1})\leq f(x_{k})\quad\mbox{ for all }\;k\in\mathbb{N}.$ (${\rm H0}$)

  * (ii)

Surrogate condition: there exists $c>0$ such that

$\|x_{k+1}-x_{k}\|\leq c\,e_{k}\;\mbox{ for all }\;k\in\mathbb{N}\;\mbox{ with
}\;\lim_{k\to\infty}e_{k}=0.$ (${\rm H1}$)

  * (iii)

Relative error condition:

$\mbox{there exists }\;w_{k+1}\in\partial f(x_{k+1})\;\mbox{ such that
}\;\|w_{k+1}\|\leq b\,\beta(e_{k}),$ (${\rm H2}$)

where $b$ is a fixed positive constant, and where
$\beta:\mathbb{R}_{+}\to\mathbb{R}_{+}$ is an admissible function.

  * (iv)

Continuity condition: For each subsequence $\\{x_{k_{j}}\\}$ with
$\lim_{j\to\infty}x_{k_{j}}=\widetilde{x}$, we have

$\limsup_{j\to\infty}f(x_{k_{j}})\leq f(\widetilde{x}).$ (${\rm H3}$)

Note that the above descent condition (H0) and surrogate condition (H1) can be
enforced by the following stronger property: there exist constants $a,c>0$
such that

$f(x_{k+1})+a\,\varphi(e_{k})\leq f(x_{k})\;\mbox{ and
}\;\|x_{k+1}-x_{k}\|\leq c\,e_{k}\;\mbox{ for all }\;k\in\mathbb{N},$ (${\rm
H1^{\prime}}$)

where $\varphi$ is an admissible function. When $\varphi(t)=t^{2}$ and
$e_{k}=\|x_{k+1}-x_{k}\|$, condition (${\rm H1^{\prime}}$) is often referred
to as the sufficient descent condition. Both conditions (${\rm H1^{\prime}}$)
and (${\rm H2}$) are automatically satisfied for various commonly used
algorithms. For example, for proximal-type methods [5], these conditions
always hold with $\varphi(t)=t^{2}$, $\beta(t)=t$, $c=1$, and
$e_{k}=\|x_{k+1}-x_{k}\|$; for cubic regularized Newton methods with Lipschitz
continuous Hessian [40], the latter conditions are fulfilled with
$\varphi(t)=t^{3}$, $\beta(t)=t^{2}$, $c=1$, and $e_{k}=\|x_{k+1}-x_{k}\|$;
for high-order proximal point methods [2], $\varphi(t)=t^{p+1}$ with $p\geq
1$, $\beta(t)=t^{p}$, $c=1$, and $e_{k}=\|x_{k+1}-x_{k}\|$.

Incorporating the surrogate sequence $\\{e_{k}\\}$ gives us some flexibility
in handling multistep numerical methods with, e.g., momentum steps. As we see
in Section 7, conditions (${\rm H1^{\prime}}$) and (${\rm H2}$) hold with
$e_{k}=\|\widehat{x}_{k+1}-x_{k}\|$, $\varphi(t)=t^{q+2}$, and
$\beta(t)=t^{q+1}$ for some $q>0$, where $\widehat{x}_{k}$ is an auxiliary
sequence generated by the subproblem of the high-order regularization methods,
where $x_{k}={\rm argmin}_{x\in\\{\widehat{x}_{k},w_{k}\\}}f(x)$, and where
$w_{k}=\widehat{x}_{k}+\beta_{k}(\widehat{x}_{k}-\widehat{x}_{k-1})$ with
$\beta_{k}\geq 0$. In the special case where $\varphi(t)=t^{2}$ and
$\beta(t)=t$, there are other general unified frameworks [33], which involve a
bivariate function $F$ serving as an approximation for $f$. While we can
potentially extend further in this direction, our main aim is to provide a
framework applicable for superlinear and quadratic convergence, which is not
discussed in [33].

From now on, we assume that $f:\mathbb{R}^{m}\to\overline{\mathbb{R}}$ is a
proper, l.s.c., bounded from below function. For a given sequence
$\\{x_{k}\\}$, use $\Omega$ to denote the set of its accumulation points.
Given $x\in\mathbb{R}^{m}$, define
$\mathcal{L}(f(x)):=\\{y\in\mathbb{R}^{m}\;|\;f(y)\leq f(x)\\}$. The next two
lemmas present some useful facts needed in what follows.

######  Lemma 4.1 (accumulation points under basic assumptions).

Consider a sequence $\\{(x_{k},e_{k})\\}$ under assumption (${\rm H0}$)–(${\rm
H3}$), and let $\mathcal{L}(f(x_{k_{0}}))$ be bounded for some
$k_{0}\in\mathbb{N}$. Then the following assertions hold:
(i) The set of accumulation points $\Omega$ is nonempty and compact.
(ii) The sequence $\\{x_{k}\\}$ satisfies the relationships

$f(x)=\inf_{k\in\mathbb{N}}f(x_{k})=\lim_{k\to\infty}f(x_{k})\quad\mbox{for
all }\;x\in\Omega.$

(iii) $\Omega\subset\Gamma$ and for any set $\Xi$ satisfying
$\Omega\subset\Xi\subset\Gamma$, we have

$\lim_{k\to\infty}d(x_{k},\Xi)=0,$ (4.1)

where $\Gamma$ is the collection of the first-order stationary points (2.2).

###### Proof.

To verify (i), observe that the descent condition (${\rm H0}$) and the
boundedness of $\mathcal{L}(f(x_{k_{0}}))$ ensure the boundedness of
$\\{x_{k}\\}$, which yields (i) since the closedness of $\Omega$ is easily
derived by the diagonal process.

To proceed with (ii), we deduce from (${\rm H0}$) that

$\inf_{k\in\mathbb{N}}f(x_{k})=\lim_{k\to\infty}f(x_{k}).$ (4.2)

Taking any $x\in\Omega$ allows us to find a subsequence $\\{x_{k_{j}}\\}$ such
that $\lim_{j\to\infty}x_{k_{j}}=x$. Combining this with condition (${\rm
H3}$) and the l.s.c. of $f$ gives us $\limsup_{j\to\infty}f(x_{k_{j}})\leq
f(x)\leq\liminf_{j\to\infty}f(x_{k_{j}})$, which establishes (ii) based on the
relationship provided in (4.2).

To verify the final assertion (iii), combine (i), (ii), and condition (${\rm
H2}$) to get $\Omega\subset\Gamma$. For any set $\Xi$ satisfying
$\Omega\subset\Xi\subset\Gamma$, (4.1) is a direct consequence of the fact
that $\lim_{k\to\infty}d(x_{k},\Omega)=0$. ∎

For a function $\tau:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$, we say it is
asymptotically shrinking around zero if $\tau(0)=0$ and

$\limsup_{t\to 0^{+}}\sum_{n=0}^{\infty}\frac{\tau^{n}(t)}{t}<\infty,$ (4.3)

where $\tau^{0}(t):=t$ and $\tau^{n}(t):=\tau(\tau^{n-1}(t))$ for all
$n\in\mathbb{N}$. It follows from the definition, that the function
$\tau(t)=\alpha t$ with $\alpha\in(0,1)$ is asymptotically shrinking around
zero, while $\tau(t)=t$ is not. The next simple lemma provides an easily
verifiable sufficient condition ensuring this property.

######  Lemma 4.2 (asymptotically shrinking functions).

Let $\tau:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ be a nondecreasing function
with $\tau(0)=0$ and such that $\limsup_{t\to 0^{+}}\frac{\tau(t)}{t}<1$. Then
this function is asymptotically shrinking around zero.

###### Proof.

To verify (4.3), denote $r:=\limsup_{t\to 0^{+}}\frac{\tau(t)}{t}<1$ and for
any $\varepsilon\in\left(r,1\right)$ find $\delta>0$ such that
$\tau(t)<\varepsilon t$ whenever $t\in(0,\delta)$, which yields
$\tau^{2}(t)=\tau(\tau(t))<\varepsilon\tau(t)<\varepsilon^{2}t$ as
$t\in(0,\delta)$. By induction, we get $\tau^{n}(t)\leq\varepsilon^{n}t$ for
all $n\in\mathbb{N}\;\mbox{and}\;t\in(0,\delta)$. Hence

$\sum_{n=0}^{\infty}\frac{\tau^{n}(t)}{t}\leq\sum_{n=0}^{\infty}\varepsilon^{n}=\frac{1}{1-\varepsilon}\quad\;\mbox{whenever
}\;t\in(0,\delta),$

which justifies (4.3) and thus completes the proof. ∎

Now we are ready to establish our first abstract convergence result.

######  Theorem 4.3 (abstract convergence framework).

For some $\eta>0$, let $\xi:[0,\eta)\to\mathbb{R}_{+}$ be a nondecreasing
continuous function with $\xi(0)=0$, and let $\\{s_{k}\\}$ be a nonnegative
sequence with $\lim_{k\to\infty}s_{k}=0$. Consider a sequence
$\\{(x_{k},e_{k})\\}\subset\mathbb{R}^{m}\times\mathbb{R}_{+}$, which
satisfies conditions (${\rm H0}$)–(${\rm H3}$), and assume that
$\mathcal{L}(f(x_{k_{0}}))$ is bounded for some $k_{0}\in\mathbb{N}$. Take
further any point $\overline{x}$, a closed set $\Xi$ with
$\overline{x}\in\Omega\subset\Xi\subset\Gamma$, and a nondecreasing function
$\tau:\mathbb{R}_{+}\to\mathbb{R}_{+}$ that is asymptotically shrinking around
zero. Suppose that there exist
$\ell_{1}\in[0,1),\ell_{2},\ell_{3}\in[0,\infty)$, and
$k_{1}\in\mathbb{N}\setminus\\{0\\}$ such that the following hold whenever
$k\geq k_{1}$ with $x_{k}\in B_{\mathbb{R}^{m}}(\overline{x},\eta)$:

  * (i)

The sequence $\\{s_{k}\\}$ shrinks with respect to the mapping $\tau$, i.e.,

$\,s_{k}\leq\,\tau(s_{k-1}).$ (4.4)

  * (ii)

Surrogate of successive change grows mildly, i.e.,

$e_{k}\leq\ell_{1}e_{k-1}+\ell_{2}\Lambda_{k,k+1}+\ell_{3}s_{k},$ (4.5)

where the sequence $\\{\Lambda_{k,k+1}\\}$ is defined by

$\Lambda_{k,k+1}:=\xi(f(x_{k})-f(\overline{x}))-\xi(f(x_{k+1})-f(\overline{x})).$
(4.6)

Then there exists $k_{2}\in\mathbb{N}$ with $k_{2}\geq k_{1}$ such that the
inclusion $x_{k}\in B_{\mathbb{R}^{m}}(\overline{x},\eta)$ holds for all
$k>k_{2}$, and therefore the estimates in (4.4) and (4.5) are also fulfilled
for all $k>k_{2}$. Moreover, it follows that

$\sum_{k=0}^{\infty}e_{k}<\infty,\quad\sum_{k=1}^{\infty}\|x_{k+1}-x_{k}\|<\infty,$
(4.7)

and the sequence $\\{x_{k}\\}$ converges to $\overline{x}\in\Xi$ as
$k\to\infty$.

###### Proof.

We first see that $\limsup_{k\to\infty}\sum_{n=0}^{\infty}\tau^{n}(s_{k})=0$.
To show this, we observe that $\sum_{n=0}^{\infty}\tau^{n}(0)=0$ and assume
without loss of generality that $s_{k}\neq 0$ for all $k\in\mathbb{N}$. Since
$\lim_{k\to\infty}s_{k}=0$ and $\tau$ is asymptotically shrinking around zero,
we get the equalities

$\limsup_{k\to\infty}\sum_{n=0}^{\infty}\tau^{n}(s_{k})=\limsup_{k\to\infty}\frac{\sum_{n=0}^{\infty}\tau^{n}(s_{k})}{s_{k}}\cdot
s_{k}=\lim_{k\to\infty}s_{k}\cdot\limsup_{k\to\infty}\sum_{n=0}^{\infty}\frac{\tau^{n}(s_{k})}{s_{k}}=0.$
(4.8)

Recalling that $\xi$ is continuous, it follows from (4.8) combined with (${\rm
H0}$), (${\rm H1}$), and Lemma 4.1 that there exists
$k_{2}\geq\max\\{k_{0},k_{1}\\}$ such that $x_{k_{2}}\in
B_{\mathbb{R}^{m}}(\overline{x},\frac{\eta}{2})$, and for all $k\geq k_{2}$ we
have $f(\overline{x})\leq f(x_{k})<f(\overline{x})+\eta$ and

$\frac{\ell_{1}}{1-\ell_{1}}e_{k-1}+\frac{\ell_{2}}{1-\ell_{1}}\xi(f(x_{k})-f(\overline{x}))+\frac{\ell_{3}}{1-\ell_{1}}\sum_{n=0}^{\infty}\tau^{n}(s_{k})<\frac{\eta}{2c}.$
(4.9)

The rest of the proof is split into the following two claims.

Claim 1: For every $k>k_{2}$, the inclusion $x_{k}\in
B_{\mathbb{R}^{m}}(\overline{x},\eta)$ holds. Indeed, suppose on the contrary
that there exists $k>k_{2}$ such that $x_{k}\notin
B_{\mathbb{R}^{m}}(\overline{x},\eta)$. Letting
$\bar{k}:=\min\\{k>k_{2}\;|\;x_{k}\notin
B_{\mathbb{R}^{m}}(\overline{x},\eta)\\}$, observe that for any
$k\in\\{k_{2},\dots,\bar{k}-1\\}$, we have $x_{k}\in
B_{\mathbb{R}^{m}}(\overline{x},\eta)$, and thus the inequalities in (4.4) and
(4.5) are satisfied. Using them together with (4.6) implies that

$\displaystyle\sum_{k=k_{2}}^{\bar{k}-1}e_{k}\leq$ $\displaystyle\
\ell_{1}\sum_{k=k_{2}}^{\bar{k}-1}e_{k-1}+\ell_{2}\sum_{k=k_{2}}^{\bar{k}-1}\Lambda_{k,k+1}+\ell_{3}\sum_{k=k_{2}}^{\bar{k}-1}s_{k}$
$\displaystyle\leq$ $\displaystyle\
\ell_{1}\sum_{k=k_{2}}^{\bar{k}-1}e_{k-1}+\ell_{2}\,\xi\big{(}f(x_{k_{2}})-f(\overline{x})\big{)}+\ell_{3}\big{(}s_{k_{2}}+\tau(s_{k_{2}})+\cdots+\tau^{\bar{k}-k_{2}-1}(s_{k_{2}})\big{)}$
$\displaystyle\leq$ $\displaystyle\
\ell_{1}\sum_{k=k_{2}}^{\bar{k}-1}e_{k-1}+\ell_{2}\,\xi\big{(}f(x_{k_{2}})-f(\overline{x})\big{)}+\ell_{3}\sum_{n=0}^{\infty}\tau^{n}(s_{k_{2}}).$

Rearranging the terms above brings us to the estimate

$\displaystyle\sum_{k=k_{2}}^{\bar{k}-1}e_{k}\leq$
$\displaystyle\frac{\ell_{1}}{1-\ell_{1}}e_{k_{2}-1}+\frac{\ell_{2}}{1-\ell_{1}}\xi\big{(}f(x_{k_{2}})-f(\overline{x})\big{)}+\frac{\ell_{3}}{1-\ell_{1}}\sum_{n=0}^{\infty}\tau^{n}(s_{k_{2}}).$
(4.10)

Combining this with (4.9) and condition (${\rm H1}$), we arrive at

$\displaystyle\|x_{\bar{k}}-\overline{x}\|\leq$
$\displaystyle\|x_{k_{2}}-\overline{x}\|+\sum_{k=k_{2}}^{\bar{k}-1}\|x_{k+1}-x_{k}\|\leq\|x_{k_{2}}-\overline{x}\|+c\sum_{k=k_{2}}^{\bar{k}-1}e_{k}<\eta,$

which contradicts the assumption that $x_{\bar{k}}\notin
B_{\mathbb{R}^{m}}(\overline{x},\eta)$ and thus justifies the claim.

Claim 2: It holds that $\sum_{k=1}^{\infty}\|x_{k}-x_{k+1}\|<\infty$. Indeed,
Claim 1 tells us that the inequalities in (4.4) and (4.5) are satisfied for
all $k>k_{2}$. Consequently, for any $k\geq k_{2}$ and $p>k$, by similar
arguments as those for deriving (4.10) we get the estimate

$\displaystyle\sum_{i=k}^{p}e_{i}\leq$
$\displaystyle\frac{\ell_{1}}{1-\ell_{1}}e_{k-1}+\frac{\ell_{2}}{1-\ell_{1}}\xi\big{(}f(x_{k})-f(\overline{x})\big{)}+\frac{\ell_{3}}{1-\ell_{1}}\sum_{n=0}^{\infty}\tau^{n}(s_{k}).$
(4.11)

Letting $p\rightarrow\infty$ and employing (4.9) yields

$\displaystyle\sum_{k=0}^{\infty}e_{k}\leq$
$\displaystyle\sum_{k=0}^{k_{2}-1}e_{k}+\sum_{i=k_{2}}^{\infty}e_{i}$
$\displaystyle\leq$
$\displaystyle\sum_{k=0}^{k_{2}-1}e_{k}+\frac{\ell_{1}}{1-\ell_{1}}e_{k_{2}-1}+\frac{\ell_{2}}{1-\ell_{1}}\xi\big{(}f(x_{k_{2}})-f(\overline{x})\big{)}+\frac{\ell_{3}}{1-\ell_{1}}\sum_{n=0}^{\infty}\tau^{n}(s_{k_{2}})<\infty,$

which gives us $\sum_{k=1}^{\infty}\|x_{k+1}-x_{k}\|<\infty$ due to (${\rm
H1}$). Therefore, $\\{x_{k}\\}$ is a Cauchy sequence. Since $\overline{x}$ is
an accumulation point of $\\{x_{k}\\}$, it follows that
$x_{k}\rightarrow\overline{x}\in\Xi$ as $k\to\infty$. ∎

In what follows, we study the convergence rate of $\\{x_{k}\\}$. For each $k$,
denote $\Delta_{k}:=\sum_{i=k}^{\infty}e_{i}$ and deduce from Theorem 4.3 that
$\Delta_{k}<\infty$. For any $k$ sufficiently large, it follows from (4.11)
that

$\displaystyle\Delta_{k}=\sum_{i=k}^{\infty}e_{i}\leq$
$\displaystyle\frac{\ell_{1}}{1-\ell_{1}}e_{k-1}+\frac{\ell_{2}}{1-\ell_{1}}\xi\big{(}f(x_{k})-f(\overline{x})\big{)}+\frac{\ell_{3}}{1-\ell_{1}}\sum_{n=0}^{\infty}\tau^{n}(s_{k}),$

which ensures from (${\rm H1}$) that

$\displaystyle\|\overline{x}-x_{k}\|=$
$\displaystyle\lim_{j\to\infty}\|x_{k+j}-x_{k}\|\leq\sum_{i=k}^{\infty}\|x_{i+1}-x_{i}\|\leq\
c\sum_{i=k}^{\infty}e_{i}=c\Delta_{k}$ (4.12) $\displaystyle\leq$
$\displaystyle\
\frac{c\,\ell_{1}}{1-\ell_{1}}e_{k-1}+\frac{c\,\ell_{2}}{1-\ell_{1}}\xi\big{(}f(x_{k})-f(\overline{x})\big{)}+\frac{c\,\ell_{3}}{1-\ell_{1}}\sum_{n=0}^{\infty}\tau^{n}(s_{k}).$

The next theorem establishes a fast convergence rate of the iterative sequence
generated by the abstract algorithm satisfying the basic assumptions (BA)
under generalized metric subregularity.

######  Theorem 4.4 (convergence rate under generalized metric subregularity).

Let $\psi,\beta:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be increasing admissible
functions, let $\\{(x_{k},e_{k})\\}$ be a sequence satisfying the basic
assumptions (${\rm H0}$)–(${\rm H3}$), and let $\overline{x}\in\Omega$ be an
accumulation point of $\\{x_{k}\\}$. Fixing any closed set $\Xi$ with
$\Omega\subset\Xi\subset\Gamma$, assume that $\mathcal{L}(f(x_{k_{0}}))$ is
bounded for some $k_{0}\in\mathbb{N}$ and the following properties are
fulfilled:

  * (i)

Generalized metric subregularity holds at $\overline{x}$ with respect to
$(\psi,\Xi)$, meaning that there exist numbers $\gamma,\eta\in(0,\infty)$ such
that

$\psi\big{(}d(x,\Xi)\big{)}\leq\gamma\,d\big{(}0,\partial
f(x)\big{)}\quad\mbox{ for all }\;x\in B_{\mathbb{R}^{m}}(\overline{x},\eta).$
(4.13)

  * (ii)

Surrogate of successive change bounded in terms of the target set, meaning
that there exist $\ell>0$ and $k_{1}\in\mathbb{N}$ such that

$e_{k}\leq\ell\,d(x_{k},\Xi)\quad\mbox{ for all }\;k\geq k_{1}.$ (4.14)

  * (iii)

Growth rate control is satisfied, meaning that $\limsup_{t\to
0^{+}}\frac{\tau(t)}{t}<1$, where $\tau:\mathbb{R}_{+}\to\mathbb{R}_{+}$ is
given by $\tau(t):=\psi^{-1}\left(\gamma b\beta(\ell t)\right)$ for all
$t\in\mathbb{R}_{+}$.

Then the sequence $\\{x_{k}\\}$ converges to $\overline{x}\in\Xi$ as
$k\to\infty$ with the rate
$\|x_{k}-\overline{x}\|=O(\tau(\|x_{k-1}-\overline{x}\|))$, i.e.,

$\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{{\tau}(\|x_{k-1}-\overline{x}\|)}<\infty.$
(4.15)

###### Proof.

Let us first check that, for any $k\geq k_{1}+1$ with $x_{k}\in
B_{\mathbb{R}^{m}}(\overline{x},\eta)$, we have the estimate

$d(x_{k},\Xi)\leq\tau\big{(}d(x_{k-1},\Xi)\big{)}.$ (4.16)

To this end, fix $k\geq k_{1}+1$ such that $x_{k}\in
B_{\mathbb{R}^{m}}(\overline{x},\eta)$ and deduce from (${\rm H2}$), (4.13),
and (4.14) that

$\psi\big{(}d(x_{k},\Xi)\big{)}\leq\gamma\,d\big{(}0,\partial
f(x_{k})\big{)}\leq\gamma b\,\beta(e_{k-1})\leq\gamma
b\,\beta\big{(}\ell\,d(x_{k-1},\Xi)\big{)},$

where the last inequality is due to the fact that $\beta$ is an increasing
admissible function. Since $\psi$ is also an increasing admissible function,
we get

$d(x_{k},\Xi)\leq\psi^{-1}\big{(}\gamma b\beta(\ell
d(x_{k-1}\Xi)\big{)}=\tau(d(x_{k-1},\Xi))$

and thus verifies (4.16). It follows from Lemma 4.1(iii), Lemma 4.2, and
Theorem 4.3 (applied to $\ell_{1}=\ell_{2}=0$, $\ell_{3}=\ell$, and
$s_{k}=d(x_{k},\Xi)$) that (4.16) holds for all large $k$, and hence
$\\{x_{k}\\}$ converges to $\overline{x}\in\Xi$ as $k\to\infty$.

Using now (4.16), the increasing property of $\tau$, and the fact that
$\overline{x}\in\Xi$, we arrive at

$d(x_{k},\Xi)\leq\tau(d(x_{k-1},\Xi))\leq\tau(\|x_{k-1}-\overline{x}\|)$

for all $k$ sufficiently large. Combining this with (4.12) and recalling that
$\ell_{1}=\ell_{2}=0$, $\ell_{3}=\ell$, and $s_{k}=d(x_{k},\Xi)$ in this case,
we obtain the estimates

$\displaystyle\|x_{k}-\overline{x}\|\leq c\,\Delta_{k}\leq$
$\displaystyle\,c\,\ell\,d(x_{k},\Xi)\sum_{n=0}^{\infty}\frac{\tau^{n}(d(x_{k},\Xi))}{d(x_{k},\Xi)}\leq
c\,\ell\,\tau(\|x_{k-1}-\overline{x}\|)\sum_{n=0}^{\infty}\frac{\tau^{n}(d(x_{k},\Xi))}{d(x_{k},\Xi)},$

which being combined with Lemma 4.1(iii) and Lemma 4.2 justifies (4.15) and
complete the proof. ∎

In the rest of this section, we present discussions on some remarkable
features of our abstract convergence analysis and its comparison with known
results in the literature.

######  Remark 4.5 (discussions on abstract convergence analysis and its
specifications).

$\bullet$ Note first that, for the three assumptions imposed in Theorem 4.4,
the second one (surrogate sequence bounded in terms of the target set) is
often tied up with and indeed guaranteed by the construction of many common
algorithms, while the other two assumptions are related to some regularity of
the function $f$ with respect to the target set. In particular, in the special
case where $e_{k}=\|x_{k+1}-x_{k}\|$, Assumption (ii) in Theorem 4.4 is
automatically satisfied for the proximal methods [5] with $\Xi=\Gamma$, and
for the cubic regularized Newton methods [32] with $\Xi=\Theta$,
$p\in(0,q+1)$.

$\bullet$ For the aforementioned proximal method from [5] to solve
$\min_{x\in\mathbb{R}^{m}}f(x)$ with a fixed proximal parameter $\lambda>0$,
where $f$ is a proper l.s.c. function, the automatic fulfillment of Assumption
(ii) allows us to deduce from Theorem 4.4 that if $\partial f$ is $p$th-order
exponent metrically subregular at $\overline{x}$ with respect to the first-
order stationary set $\Gamma$ for $p\in(0,1)$, then the proximal method
converges at least superlinearly with the convergence rate $\frac{1}{p}$. To
the best of our knowledge, this appears to be new to the literature. Moreover,
we see in Example 4.6 below that the derived convergence rate can indeed be
attained.

$\bullet$ In Section 7, we apply the conducted convergence analysis to the
higher-order regularized Newton method with momentum steps to solve
$\min_{x\in\mathbb{R}^{m}}f(x)$, where $f$ is a $C^{2}$-smooth function whose
Hessian is Hölder continuous with exponent $q\in(0,1]$. As mentioned,
Assumption (ii) holds automatically with respect to the second-order
stationary points $\Theta$ from (2.3). Therefore, if $\partial f$ is $p$th-
order exponent metrically subregular at $\overline{x}$ with respect to
$\Theta$ for $p\in(0,q+1)$, then the sequence generated by the algorithm
converges to a second-order stationary point at least superlinearly with order
$\frac{q+1}{p}$. Even in the special case where $p=1$, this improves the
current literature on high-order regularized Newton methods by obtaining fast
convergence rates under the pointwise metric subregularity (instead of the
uniform metric subregularity/error bound condition as in (3.3)), and in the
more general context with allowing momentum steps; see Remark 7.10 for more
details.

Now we provide a simple example showing that the established convergence rate
can be attained for the proximal method of minimizing a smooth univariate
function.

######  Example 4.6 (tightness of the convergence rate).

Consider applying the proximal point method for the univariate function
$f(t)=|t|^{\frac{3}{2}}$, $t\in\mathbb{R}$, with the iterations

$t_{k+1}={\rm
argmin}_{t\in\mathbb{R}}\big{\\{}f(t)+\frac{\lambda}{2}(t-t_{k})^{2}\big{\\}},\quad
t_{0}=1,$

where $\lambda$ is a fixed positive parameter. Then we have

$\nabla f(t_{k+1})+\lambda(t_{k+1}-t_{k})=\frac{3}{2}{\rm
sign}(t_{k+1})|t_{k+1}|^{\frac{1}{2}}+\lambda(t_{k+1}-t_{k})=0.$

This shows that $t_{k}>0\Rightarrow t_{k+1}>0$, and so $t_{k}>0$ for all $k$,
which further implies that
$t_{k}=\frac{3}{2\lambda}(t_{k+1})^{\frac{1}{2}}+t_{k+1}$ yielding
$t_{k}\geq\frac{3}{2\lambda}(t_{k+1})^{\frac{1}{2}}$. Take $\Xi=\Gamma$, the
first-order stationary set (2.2), and get

$|t_{k+1}-t_{k}|=\frac{3}{2\lambda}|t_{k+1}|^{\frac{1}{2}}\leq|t_{k}|=d(t_{k},\Xi).$

For $w_{k+1}=\nabla f(t_{k+1})=\frac{3}{2}t_{k+1}^{\frac{1}{2}}$, we have
$|w_{k+1}|=\frac{3}{2}t_{k+1}^{\frac{1}{2}}=\lambda|t_{k+1}-t_{k}|$. Choosing
now $\psi(t)=\frac{3}{2}t^{\frac{1}{2}}$ and $\beta(t)=t$ gives us
$\tau(t)=\psi^{-1}(\lambda\beta(t))=O(t^{2})$ and the equalities
$\psi(d(t_{k},\Xi))=\psi(|t_{k}|)=\frac{3}{2}|t_{k}|^{\frac{1}{2}}=d(0,\nabla
f(t_{k}))$. Direct verifications show that all the conditions in Theorem 4.4
are satisfied, and thus it follows from the theorem that
$t_{k}\rightarrow\overline{t}=0$ in a quadratic rate, e.g.,
$|t_{k+1}-\overline{t}|=t_{k+1}=O(t_{k}^{2})=O(|{t_{k}-}\overline{t}|^{2})$.

To determine the exact convergence rate, we solve
$t_{k}=\frac{3}{2\lambda}\,t^{\frac{1}{2}}+t$ in terms of the variable
$t\in\mathbb{R}_{+}$. Letting $u=\sqrt{t}$ provides
$t_{k}=\frac{3}{2\lambda}u+u^{2}$, which implies that
$u=-\frac{3}{4\lambda}+\sqrt{t_{k}+\frac{9}{16\lambda^{2}}}$. Passing finally
to the limit as $k\to\infty$ and remembering that $t_{k}\rightarrow 0$ tell us
that

$t_{k+1}=\left[-\frac{3}{4\lambda}+\sqrt{t_{k}+\frac{9}{16\lambda^{2}}}\right]^{2}=\left[\frac{t_{k}}{\frac{3}{4\lambda}+\sqrt{t_{k}+\frac{9}{16\lambda^{2}}}}\right]^{2}=O(t_{k}^{2}),$

which agrees with the exact quadratic convergence rate derived in Theorem 4.4.

##  5 Abstract Convergence Analysis under the KL Property

In this section, we continue our convergence analysis of abstract algorithms
involving now the Kurdyka-Łojasiewicz (KL) property from Definition 2.2. Here
is the main result of this section.

######  Theorem 5.1 (convergence under the KL properties).

Consider a sequence $\\{(x_{k},e_{k})\\}$, which satisfies assumptions (${\rm
H1^{\prime}}$), (${\rm H2}$), (${\rm H3}$) being such that the set
$\mathcal{L}(f(x_{k_{0}}))$ is bounded for some $k_{0}\in\mathbb{N}$. Let
$\overline{x}$ be an accumulation point of the iterated sequence, and let
$f:\mathbb{R}^{m}\to\overline{\mathbb{R}}$ be an l.s.c. function satisfying
the KL property at $\overline{x}$, where $\eta>0$ and
$\vartheta:[0,\eta)\to\mathbb{R}_{+}$ are taken from Definition 2.2. Suppose
also that there exists a pair $(\mu_{1},\mu_{2})\in(0,1)\times\mathbb{R}_{+}$
for which

$\limsup_{(s,t)\to(0,0)}\frac{\varphi^{-1}(\beta(s)t)}{\mu_{1}s+\mu_{2}t}\leq
1,$ (5.1)

where $\varphi(\cdot)$ and $\beta(\cdot)$ are increasing functions taken from
conditions (${\rm H1^{\prime}}$) and (${\rm H2}$). Then we have
$\sum_{k=1}^{\infty}\|x_{k+1}-x_{k}\|<\infty$, and the sequence $\\{x_{k}\\}$
converges to $\overline{x}$ as $k\to\infty$.

###### Proof.

It follows from (5.1) that for any $\alpha\in\left(1,\frac{1}{\mu_{1}}\right)$
there exists $\delta>0$ such that

$\varphi^{-1}\big{(}\beta(s)t\big{)}\leq\alpha\mu_{1}s+\alpha\mu_{2}t\quad\mbox{
whenever }\;s,t\in(0,\delta).$ (5.2)

Let $\overline{\eta}:=\min\\{\eta,\varepsilon\\}$ with $\varepsilon,\eta$
given in Definition 2.2. It follows from the abstract convergence framework of
Theorem 4.3 with $s_{k}=0$ that the claimed assertions are verified if showing
that there exist constants $\ell_{1}\in(0,1),\ell_{2}\in[0,\infty)$, and
$k_{1}\in\mathbb{N}\setminus\\{0\\}$ such that for any $k\geq k_{1}$ with
$x_{k}\in B_{\mathbb{R}^{m}}(\overline{x},\overline{\eta})$ we have

$e_{k}\leq\ell_{1}e_{k-1}+\ell_{2}\Lambda_{k,k+1}$ (5.3)

with the quantities $\Lambda_{k,k+1}$ defined by

$\Lambda_{k,k+1}:=\vartheta\big{(}f(x_{k})-f(\overline{x})\big{)}-\vartheta\big{(}f(x_{k+1})-f(\overline{x})\big{)}.$

To see this, recall that $\varphi$ is an admissible function and then deduce
from (${\rm H1^{\prime}}$) and Lemma 4.1 that

$f(x_{k+1})\leq f(x_{k})\;\mbox{ for all }\;k\in\mathbb{N},\quad
f(\overline{x})=\inf_{k\in\mathbb{N}}f(x_{k})=\lim_{k\to\infty}f(x_{k}),$

and $\lim_{k\to\infty}e_{k}=0$. It follows from the continuity of $\vartheta$
that there exists $k_{1}\geq 1$ for which

$f(\overline{x})\leq f(x_{k})<f(\overline{x})+\overline{\eta},\quad
e_{k-1}<\delta,\;\mbox{ and }$ (5.4)
$\frac{b}{a}[\vartheta(f(x_{k})-f(\overline{x}))-\vartheta(f(x_{k+1})-f(\overline{x}))]<\delta\;\mbox{
whenever }\;k\geq k_{1}.$ (5.5)

Take any $k\geq k_{1}$ with $x_{k}\in
B_{\mathbb{R}^{m}}(\overline{x},\overline{\eta})$ and observe that if
$e_{k}=0$, then (5.3) holds trivially. Assuming that $e_{k}\neq 0$ and then
using (${\rm H1^{\prime}}$) and (5.4), we get $f(\overline{x})\leq
f(x_{k+1})<f(x_{k})$, which being combined with the KL property and condition
(${\rm H2}$) shows that $w_{k}\neq 0$ and $e_{k-1}\neq 0$. Since
$w_{k}\in\partial f(x_{k})$, the aforementioned conditions readily yield the
estimates

$\vartheta^{\prime}(f(x_{k})-f(\overline{x}))\geq\frac{1}{\|w_{k}\|}\geq\frac{1}{b\beta(e_{k-1})}.$
(5.6)

The concavity of $\vartheta$ in the KL property and assumption (${\rm
H1^{\prime}}$) imply that

$\displaystyle\vartheta\big{(}f(x_{k})-f(\overline{x})\big{)}-\vartheta(f(x_{k+1})-f(\overline{x}))$
$\displaystyle\geq\vartheta^{\prime}\big{(}f(x_{k})-f(\overline{x})\big{)}\big{(}f(x_{k})-f(x_{k+1})\big{)}$
(5.7) $\displaystyle\geq
a\vartheta^{\prime}\big{(}f(x_{k})-f(\overline{x})\big{)}\varphi(e_{k}).$

Substituting (5.6) into (5.7) guarantees that

$\frac{b}{a}\big{[}\vartheta\big{(}f(x_{k})-f(\overline{x})\big{)}-\vartheta\big{(}f(x_{k+1})-f(\overline{x}\big{)}\big{]}\geq\frac{\varphi(e_{k})}{\beta(e_{k-1})},$

which establishes in turn that

$\displaystyle
e_{k}\leq\varphi^{-1}\Big{(}\frac{b}{a}\beta(e_{k-1})\big{[}\vartheta\big{(}f(x_{k})-f(\overline{x})\big{)}-\vartheta\big{(}f(x_{k+1})-f(\overline{x})\big{)}\big{]}\Big{)}.$

Combining the latter with (5.2) and (5.5), we get

$\displaystyle e_{k}$
$\displaystyle\leq\alpha\mu_{1}e_{k-1}+\frac{\alpha\mu_{2}b}{a}\Big{(}\vartheta\big{(}f(x_{k})-f(\overline{x})\big{)}-\vartheta\big{(}f(x_{k+1})-f(\overline{x})\big{)}\Big{)},$

which shows that (5.3) holds with $\ell_{1}:=\alpha\mu_{1}<1$ and
$\ell_{2}:=\frac{\alpha\mu_{2}b}{a}$ and thus completes the proof. ∎

Now we employ Theorem 5.1 and the results of the previous section to find
explicit conditions ensuring superlinear convergence of an abstract algorithm
under the KL property. Talking $\vartheta\colon[0,\eta]\to\mathbb{R}_{+}$ from
Definition 2.2 and the admissible functions $\varphi(\cdot)$ and
$\beta(\cdot)$ from Theorem 5.1, define $\rho:\mathbb{R}_{+}\to\mathbb{R}_{+}$
by

$\rho(t):=\left\\{\begin{array}[]{cc}\big{(}(\vartheta^{-1})^{\prime}\big{)}^{-1}(b\beta(t))&\mbox{
if }\;t>0,\\\ 0&\mbox{ if }\;t=0\end{array}\right.$

and consider the function $\xi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ given by
$\xi(t):=\varphi^{-1}\left(\frac{\vartheta^{-1}(\rho(t))}{a}\right)$ for all
$t\in\mathbb{R}_{+}$.

######  Theorem 5.2 (superlinear convergence rate under the KL property).

Let $\\{(x_{k},e_{k})\\}$, $\mathcal{L}(f(x_{k_{0}}))$, $\overline{x}$, $f$,
$\vartheta$, $\varphi$, and $\beta$ be as in the general setting of Theorem
5.1 under the assumptions (${\rm H1^{\prime}}$), (${\rm H2}$), and (${\rm
H3}$). Take the function $\xi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ as defined
above and assume in addition that it is increasing on $\mathbb{R}_{+}$ with
$\lim_{t\to 0^{+}}\frac{\xi(t)}{t}=0$. The following assertions hold:

  * (i)

If there exists $r\geq 1$ such that $e_{k}\leq r\|x_{k+1}-x_{k}\|$ for all
large $k\in\mathbb{N}$, then the sequence $\\{x_{k}\\}$ converges to
$\overline{x}$ as $k\to\infty$ with the convergence rate

$\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{\widetilde{\xi}(\|x_{k-1}-\overline{x}\|)}<\infty,\;\mbox{
where }\;\widetilde{\xi}(t):=\xi(2rt).$ (5.8)

  * (ii)

If there exist $\ell>0$ and a closed set $\Xi$ satisfying
$\Omega\subset\Xi\subset\Gamma$ and such that

$e_{k}\leq\ell\,d(x_{k},\Xi)\;\mbox{ for all large }\;k\in\mathbb{N},$ (5.9)

then the sequence $\\{x_{k}\\}$ converges to $\overline{x}\in\Xi$ as
$k\to\infty$ with the convergence rate

$\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{\widehat{\xi}(\|x_{k-1}-\overline{x}\|)}<\infty,\;\mbox{
where }\;\widehat{\xi}(t):=\xi(\ell\,t).$ (5.10)

###### Proof.

Suppose without loss of generality that $e_{k}\neq 0$ for all
$k\in\mathbb{N}$. It follows from Theorem 4.3 that (5.6) holds when $k$ is
sufficiently large and that there exists $k_{1}$ such that

$(\vartheta^{-1})^{\prime}\big{(}\vartheta((f(x_{k})-f(\overline{x})))\big{)}=\frac{1}{\vartheta^{\prime}\big{(}f(x_{k})-f(\overline{x})\big{)}}\leq
b\beta(e_{k-1})\quad\mbox{as }\;k\geq k_{1}.$

The latter readily implies that

$\vartheta\big{(}(f(x_{k})-f(\overline{x}))\big{)}\leq\big{(}(\vartheta^{-1})^{\prime}\big{)}^{-1}\big{(}b\beta(e_{k-1})\big{)}=\rho(e_{k-1})\quad\mbox{as
}\;k\geq k_{1}.$ (5.11)

Furthermore, condition (${\rm H1^{\prime}}$) and the first part of (5.4) tell
us that

$a\varphi(e_{k})\leq f(x_{k})-f(x_{k+1})\leq f(x_{k})-f(\overline{x})\;\mbox{
for all }\;k\in\mathbb{N},$

which together with (5.11) yields $e_{k}\leq\xi(e_{k-1})$. Combining this with
the limiting conditions $\lim_{k\to\infty}e_{k}=0$ and $\lim_{t\to
0^{+}}\frac{\xi(t)}{t}=0$ allows us to find a sufficiently large number
$k_{2}\in\mathbb{N}$ such that

$e_{k}\leq\xi(e_{k-1})<\frac{1}{2}e_{k-1}\quad\mbox{for all }\;k\geq k_{2}.$

Invoking again condition (${\rm H1^{\prime}}$) ensures that for any $k\geq
k_{2}$ we have the estimates

$\displaystyle\|\overline{x}-x_{k}\|=\lim_{j\to\infty}\|x_{k+j}-x_{k}\|\leq$
$\displaystyle\sum_{i=k}^{\infty}\|x_{i+1}-x_{i}\|\leq
c\sum_{i=k}^{\infty}e_{i}\leq 2c\,e_{k}\leq 2c\,\xi(e_{k-1}).$ (5.12)

Now we are in a position to justify both assertions of the theorem. Starting
with (i), note that

$\xi(e_{k-1})\leq\xi(r\|x_{k}-x_{k-1}\|)\leq\xi(r\|x_{k}-\overline{x}\|+r\|x_{k-1}-\overline{x}\|)\leq\xi(2r\|x_{k}-\overline{x}\|)+\xi(2r\|x_{k-1}-\overline{x}\|)$

for large $k$, where the last inequality follows from the increasing property
of $\xi$ ensuring that

$\xi(\alpha+\gamma)\leq\max\big{\\{}\xi(2\alpha),\xi(2\gamma)\big{\\}}\leq\xi(2\alpha)+\xi(2\gamma)$

for any $\alpha,\gamma\geq 0$. Observing that $\lim_{t\to
0^{+}}\frac{\xi(2rt)}{t}=0$, it readily follows from $x_{k}\to\overline{x}$
and (5.12) that

$\displaystyle\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{\xi(2r\|x_{k-1}-\overline{x}\|)}=$
$\displaystyle\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{\xi(2r\|x_{k-1}-\overline{x}\|)+\xi(2r\|x_{k}-\overline{x}\|)}$
$\displaystyle\leq$
$\displaystyle\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{\xi(e_{k-1})}<\infty,$

which brings us to (5.8) and thus justifies assertion (i).

To verify finally assertion (ii), observe that the increasing property of
$\xi$ and the inclusion $\overline{x}\in\Xi$ allow us to deduce from (5.9) the
estimates

$\xi(e_{k-1})\leq\xi\big{(}\ell
d(x_{k-1},\Xi)\big{)}\leq\xi\big{(}\ell\|x_{k-1}-\overline{x}\|\big{)}\quad\mbox{
for all }\;k\geq k_{2},$

which together with (5.12) give us (5.10) and thus completes the proof of the
theorem. ∎

We conclude this section with some specifications of the convergence results
obtained under the KL property and comparisons with known results in the
literature.

######  Remark 5.3 (further discussions and comparisons for KL convergence
analysis).

$\bullet$ Observe first that assumption (5.1) in Theorem 5.1 holds
automatically for many common algorithms. For example, in the standard
proximal methods [5] we have $\varphi(t)=t^{2}$ and $\beta(t)=t$, and thus by
setting $(\mu_{1},\mu_{2})=(1/2,1/2)$ in Theorem 5.1, condition (5.1) holds by
the classical AM–GM inequality.

$\bullet$ In the case where $\vartheta(t)=ct^{1-\theta}$ with the KL exponent
$\theta\in[0,1)$, we can obtain the explicit sublinear, linear, and
superlinear convergence rates. In fact, let
$\beta,\varphi,\vartheta:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be such that
$\beta(t)=t^{\alpha},\;\varphi(t)=t^{1+\alpha},\;\mbox{ and
}\vartheta(t)=ct^{1-\theta}$, where $c,\alpha>0$ and $\theta\in[0,1)$. It is
easy to see that the assumption (5.1) in Theorem 5.1 holds with
$(\mu_{1},\mu_{2})=(\frac{\alpha}{\alpha+1},\frac{1}{\alpha+1})$ due to the
AM–GM inequality. In this case, direct verifications show that

$\rho(t):=\big{(}(\vartheta^{-1})^{\prime}\big{)}^{-1}(b\beta(t))=(1-\theta)^{\frac{1-\theta}{\theta}}c^{\frac{1}{\theta}}b^{\frac{1-\theta}{\theta}}t^{\frac{\alpha(1-\theta)}{\theta}}=:\kappa
t^{\frac{\alpha(1-\theta)}{\theta}},$
$\xi(t):=\varphi^{-1}\left(\frac{\vartheta^{-1}(\rho(t))}{a}\right)=a^{-\frac{1}{1+\alpha}}\left(\frac{\kappa}{c}\right)^{\frac{1}{(1+\alpha)(1-\theta)}}t^{\frac{\alpha}{(1+\alpha)\theta}}=:\mu
t^{\frac{\alpha}{(1+\alpha)\theta}}.$

Suppose that condition (5.9) holds, which is true for various common numerical
methods such as proximal-type methods and high-order regularized methods. If
$\theta<\frac{\alpha}{1+\alpha}$, then Theorem 5.2 implies that the sequence
$\\{x_{k}\\}$ converges to $\overline{x}$ superlinearly with the convergence
rate $\frac{\alpha}{(1+\alpha)\theta}$. It will be seen in Section 7 that if
we further assume that $f$ is a ${\cal C}^{2}$-smooth function and satisfies
the strict saddle point property, then Theorem 4.4 and Corollary 6.5 allow us
to improve the superlinear convergence rate to
$\frac{(1-\theta)\alpha}{\theta}$.

$\bullet$ Following the arguments from [4, Theorem 2], we can also obtain
convergence rates in the remaining cases for $\theta$. Indeed, when
$\theta=\frac{\alpha}{1+\alpha}$ there exist $\varrho\in(0,1)$ and
$\zeta\in(0,\infty)$ such that for large $k$ we get

$\|x_{k}-\overline{x}\|\leq\Delta_{k}:=\sum_{i=k}^{\infty}\|x_{i+1}-x_{i}\|\leq\zeta\varrho^{k}.$

If finally $\theta>\frac{\alpha}{1+\alpha}$, then there exists $\mu>0$
ensuring the estimates

$\|x_{k}-\overline{x}\|\leq\Delta_{k}\leq\mu
k^{-\frac{\alpha(1-\alpha)}{(1+\alpha)\theta-\alpha}}\;\mbox{ for all large
}\;k\in\mathbb{N}.$

The proof of this fact is rather standard, and so we omit details here.

$\bullet$ Let us highlight that the superlinear convergence rate derived under
the KL assumptions need not be tight in general, and it can be worse than the
one derived under the generalized metric subregularity. For instance, consider
the situation in Example 4.6, where the proximal point method is applied to
$f(t)=|t|^{\frac{3}{2}}$. As discussed in that example, the sequence
$\\{t_{k}\\}$ generated by the algorithm converges with a quadratic rate, and
the convergence rate agrees with the rate derived under the generalized metric
subregularity. Direct verification shows that the function
$f(t)=|t|^{\frac{3}{2}}$ satisfies the KL property with exponent
$\theta=\frac{1}{3}$, and that we have $\alpha=1$ for the proximal point
method. Thus Theorem 5.2 only implies that $\\{t_{k}\\}$ converges
superlinearly with rate $\frac{3}{2}$ while not quadratically as under
generalized metric subregularity.

##  6 Generalized Metric Subregularity for Second-Order Conditions

In this section, we continue our study of generalized metric subregularity
while concentrating now on deriving verifiable conditions for the fulfillment
of this notion with respect to the set $\Xi=\Theta$ of second-order stationary
points defined in (2.3), where the function $f$ in question is ${\cal
C}^{2}$-smooth. Such a second-order generalized metric subregularity plays a
crucial role in the justification of fast convergence of our new high-order
regularized Newton method in Section 7. We’ll see below that this notion holds
in broad settings of variational analysis and optimization and is satisfied in
important practical models.

Note that if $f$ is convex, then there is no difference between $\Theta$ and
the set $\Gamma$ of first-order stationary points (2.2). We focus in what
follows on nonconvex settings for generalized metric subregularity, where
$\Theta\neq\Gamma$ as in the following simple while rather instructive
example.

######  Example 6.1 (generalized metric subregularity for nonconvex
functions).

Consider the function $f:\mathbb{R}^{m}\rightarrow\mathbb{R}$ given by
$f(x)=(\|x\|^{2}-r)^{2p}$ with $r>0$ and $p\geq 1$. Direct computations show
that $\nabla f(x)={4}p(\|x\|^{2}-r)^{2p-1}x$ and thus

$\nabla^{2}f(x)={8}p(2p-1)(\|x\|^{2}-r)^{2p-2}xx^{T}+{4}p(\|x\|^{2}-r)^{2p-1}I_{m},$

where $I_{m}$ stands for the $m\times m$ identity matrix. Since
$\nabla^{2}f(0)$ is negative-definite, $f$ is nonconvex. Moreover,
$\Gamma=\\{x\;|\;\|x\|=\sqrt{r}\\}\cup\\{0\\}$ and
$\Theta=\\{x\;|\;\|x\|=\sqrt{r}\\}$. Therefore, for any
$\overline{x}\in\Theta$ we have

$\displaystyle
d(x,\Theta)=\big{|}\|x\|-\sqrt{r}\big{|}=\frac{\big{|}\|x\|^{2}-r\big{|}}{\big{|}\|x\|+\sqrt{r}\big{|}}\leq\Big{(}\frac{3}{2}\sqrt{r}\Big{)}^{-1}\big{|}\|x\|^{2}-r\big{|}$
$\displaystyle=\Big{(}\frac{3}{2}\sqrt{r}\Big{)}^{-1}\frac{[{4}p\big{|}\|x\|^{2}-r\big{|}^{2p-1}\|x\|]^{\frac{1}{2p-1}}}{({4}p\|x\|)^{\frac{1}{2p-1}}}\leq(\frac{3}{2}\sqrt{r})^{-1}\frac{\|\nabla
f(x)\|^{\frac{1}{2p-1}}}{({2}p\sqrt{r})^{\frac{1}{2p-1}}}\;\mbox{ whenever
}\;x\in B_{\mathbb{R}^{m}}(\overline{x},\sqrt{r}/2),$

and thus $\nabla f$ satisfies the generalized metric subregularity with
respect to $(\psi,\Xi)$ for $\psi(t)=t^{2p-1}$ and $\Xi=\Theta$.

Let us now introduce the new property that is playing an important role below.
Given a proper l.s.c. function
$f\colon\mathbb{R}^{m}\to\overline{\mathbb{R}}$, we say that $f$ has the weak
separation property (WSP) at $\overline{x}\in\Gamma$ if there is $\varsigma>0$
with

$f(y)\leq f(\overline{x})\quad\mbox{for all }\;y\in\Gamma\cap
B_{\mathbb{R}^{m}}(\overline{x},\varsigma),$ (6.1)

where $\Gamma$ is taken from (2.2). The constant $\varsigma$ is called the
modulus of weak separation. If the inequality in (6.1) is replaced by
equality, such property is frequently used in the study of error bounds under
the name of “separation property” (e.g., in [21, 25]), which inspires our
terminology, While the separation property obviously yields WSP, the converse
fails. For example, consider
$f(x):=-e^{\frac{-1}{x^{2}}}[\cos(\frac{1}{x})]^{2p}$ if $x\neq 0$ and
$f(x):=0$ if $x=0$, where $p\in\mathbb{N}$. Take $\overline{x}=0$ and deduce
from the definition that $f$ satisfies WSP at $\overline{x}$. On the other
hand, $f(\frac{1}{2k\pi+\frac{\pi}{2}})=f(\frac{1}{2k\pi+\frac{3\pi}{2}})=0$
for all $k\in\mathbb{N}$, and hence there exists
$a_{k}\in(\frac{1}{2k\pi+\frac{3\pi}{2}},\frac{1}{2k\pi+\frac{\pi}{2}})$ such
that $f^{\prime}(a_{k})=0$ and $f(a_{k})<0=f(\overline{x})$, which tells us
that the separation property fails.

The next proposition shows that a large class of functions satisfies the weak
separation property.

######  Proposition 6.2 (sufficient conditions for weak separation).

Let $f\colon\mathbb{R}^{m}\to\overline{\mathbb{R}}$ be a proper l.s.c.
function, and let $\overline{x}\in\Gamma$. Suppose that either one of the
following conditions holds:

  * (i)

$f$ is continuous at $\overline{x}$ with respect to ${\rm dom}(\partial f)$,
i.e., $\lim\limits_{{\scriptstyle{z\in{\rm dom}(\partial
f)}\atop\scriptstyle{z\rightarrow\overline{x}}}}f(z)=f(\overline{x})$, and it
satisfies the KL property at $\overline{x}\in\Gamma$.

  * (ii)

$f=\varphi\circ g$, where $\varphi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a
convex function, and where $g:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ is a
smooth mapping such that the Jacobian matrix $\nabla g(\overline{x})$ is
surjective.

Then $f$ enjoys the weak separation property at $\overline{x}$.

###### Proof.

To verify (i), suppose on the contrary that WSP fails at $\bar{x}$. Then there
exists a sequence $y_{k}\rightarrow\overline{x}$ with $y_{k}\in\Gamma$ such
that $f(y_{k})>f(\overline{x})$ for all $k\in\mathbb{N}$. It follows from the
continuity of $f$ at $\overline{x}$ with respect to ${\rm dom}(\partial f)$
that $y_{k}\in\\{x\;|\;f(\overline{x})<f(x)<f(\overline{x})+\eta\\}$ for all
large $k$, where $\eta$ is taken from the assumed KL property at
$\overline{x}$. The latter condition implies that

$\vartheta^{\prime}(f(y_{k})-f(\overline{x}))d(0,\partial f(y_{k}))\geq 1$

while contradicting $y_{k}\in\Gamma$ and hence justifying the claimed WSP.
Assertion (ii) follows directly from Lemma 3.6, which therefore completes the
proof of the proposition. ∎

Another concept used below to study the second-order generalized metric
subregularity applies to ${\cal C}^{2}$-smooth functions. Given such a
function, recall that $\overline{x}$ is its strict saddle point if
$\lambda_{\min}(\nabla^{2}f(\overline{x}))<0$. We say that $f$ satisfies the
strict saddle point property at $\overline{x}\in\Gamma$ if $\overline{x}$ is
either a local minimizer for $f$, or a strict saddle point for $f$. If $f$
satisfies the strict saddle point property at any first-order stationary
point, then we simply say that $f$ satisfies the strict saddle point property.
Furthermore, if for any first-order stationary point $\overline{x}$ of $f$, it
is either a global minimizer for $f$, or a strict saddle point for $f$, then
we say that $f$ satisfies the strong strict saddle point property. It is known
from Morse theory that strict saddle point property holds generically for
${\cal C}^{2}$-smooth functions. Moreover, it has been recognized in the
literature that various classes of nonconvex functions arising in matrix
completion, phase retrieval, neural networks, etc. enjoy the strict saddle
point property; see some instructive examples below.

Before establishing the main result of this section, we present one more
proposition of its own interest telling us that, around a local minimizer, the
distance to $\Gamma$, the set of first-order stationary points, agrees with
the distance to $\Theta$, the set of second-order stationary points, under
WSP. Let us emphasize that in general $\Gamma$ and $\Theta$ are not the same
while the distances to $\Gamma$ and $\Theta$ are under the imposed
assumptions.

######  Proposition 6.3 (distance to stationary points).

Given a ${\cal C}^{2}$-smooth function $f\colon\mathbb{R}^{m}\to\mathbb{R}$
and $\overline{x}\in\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}[\overline{x},\alpha]}f(x)$ for some $\alpha>0$, suppose
that WSP holds at $\overline{x}$ with modulus $\varsigma>0$. Denoting
$\gamma:=\min\\{\alpha,\varsigma\\}$, we have the equality

$d(x,\Theta)=d(x,\Gamma)=d\big{(}x,\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}[\overline{x},\gamma]}f(x)\big{)}=d\big{(}x,[f\leq
f(\overline{x})]\big{)}\;\mbox{ for all }\;x\in
B_{\mathbb{R}^{m}}\big{(}\overline{x},\gamma/4\big{)}.$ (6.2)

###### Proof.

It follows from (6.1), the fact that $\overline{x}\in\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}[\overline{x},\alpha]}f(x)$, and the choice of $\gamma$ that

$\Gamma\cap
B_{\mathbb{R}^{m}}(\overline{x},\gamma)\subset\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}[\overline{x},\gamma]}f(x)\subset[f\leq f(\overline{x})].$

This implies that for any $x\in B_{\mathbb{R}^{m}}(\overline{x},\gamma/2)$ we
get

$\displaystyle d(x,[f\leq f(\overline{x})])\leq
d\big{(}x,\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}[\overline{x},\gamma]}f(x)\big{)}\leq\ d(x,\Gamma\cap
B_{\mathbb{R}^{m}}(\overline{x},\gamma))$ (6.3) $\displaystyle=\
\min\\{d(x,\Gamma\cap
B_{\mathbb{R}^{m}}(\overline{x},\gamma)),d(x,\Gamma\setminus
B_{\mathbb{R}^{m}}(\overline{x},\gamma))\\}=\ d(x,\Gamma)\leq d(x,\Theta),$

where the first equality is due to $d(x,\Gamma\cap
B_{\mathbb{R}^{m}}(\overline{x},\gamma))<\gamma/2$ (by
$\overline{x}\in\Gamma$) and $d(x,\Gamma\setminus
B_{\mathbb{R}^{m}}(\overline{x},\gamma))\geq\gamma/2$. Recalling that
$\overline{x}\in\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}[\overline{x},\alpha]}f(x)$ leads us to

$[f\leq f(\overline{x})]\cap
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)=\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)}f(x)$

and to the distance estimate $\displaystyle d\big{(}x,\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)}f(x)\big{)}\leq\|x-\overline{x}\|<\gamma/4$
for all $x\in B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/4\right)$.
Therefore, taking $x$ from the above neighborhood of $\bar{x}$ brings us to
the equality

$\displaystyle d\big{(}x,[f\leq f(\overline{x})]\big{)}=$
$\displaystyle\min\big{\\{}d\big{(}x,\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)}f(x)\big{)},d\big{(}x,[f\leq
f(\overline{x})]\setminus
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)\big{)}\big{\\}}$ (6.4)
$\displaystyle=$ $\displaystyle\ d\big{(}x,\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)}f(x)\big{)}.$

Observing finally that $\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)}f(x)\subset\Theta$, we
deduce from (6.3) and (6.4) that

$\displaystyle d(x,[f\leq f(\overline{x})])\leq
d\big{(}x,\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}[\overline{x},\gamma]}f(x)\big{)}\leq d(x,\Gamma)\leq
d(x,\Theta)\leq d\big{(}x,\mathop{\arg\min}_{x\in
B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/2\right)}f(x)\big{)}=d(x,[f\leq
f(\overline{x})])$

for any $x\in B_{\mathbb{R}^{m}}\left(\overline{x},\gamma/4\right)$, which
justifies (6.2) and thus completes the proof of the proposition. ∎

Now we are ready to derive sufficient conditions for generalized metric
subregularity broadly used below.

######  Theorem 6.4 (sufficient conditions for generalized metric
subregularity).

Let $f:\mathbb{R}^{m}\to\mathbb{R}$ be a ${\cal C}^{2}$-smooth function, let
$\psi:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be an admissible function, and let
$\overline{x}\in\Theta$. Suppose that both WSP and strict saddle point
property hold for $f$ at $\overline{x}$. Then $\nabla f$ has the generalized
metric subregularity property with respect to $(\psi,\Theta)$ at
$\overline{x}$ if and only if $\nabla f$ has this property at $\overline{x}$
with respect to $(\psi,\Gamma)$. In particular, if $f$ is a subanalytic ${\cal
C}^{2}$-smooth function satisfying the strict saddle point property, then
$\nabla f$ enjoys the generalized metric subregularity property with respect
to $(\psi,\Theta)$ at $\overline{x}\in\Theta$, where $\psi(t)=t^{\gamma}$ for
some $\gamma>0$.

###### Proof.

Note first that by $\overline{x}\in\Theta$ we have $\nabla f(\overline{x})=0$
and $\nabla^{2}f(\overline{x})\succeq 0$. Since $f$ satisfies the strict
saddle point property, $\overline{x}$ must be a local minimizer for $f$.
Therefore, the first conclusion of the theorem follows immediately from
Proposition 6.3.

Suppose now that $f$ is a subanalytic ${\cal C}^{2}$-smooth function
satisfying the strict saddle point property. As mentioned earlier, subanalytic
functions satisfy the KL property [6], and hence we deduce from Proposition
6.2 that the weak separation property holds at $\overline{x}$. By [7,
Proposition 2.13(ii)], the subanalytic property of $f$ ensures that the
functions $h_{1}(x):=d(0,\nabla f(x))$ and $h_{2}(x):=d(x,\Gamma)$ are
subanalytic. Observing that $h_{1}^{-1}(0)\subset h_{2}^{-1}(0)$, we deduce
from the Lojasiewicz factorization lemma for subanalytic functions in [6,
Theorem 6.4] that for each compact set $K$ there exist $c>0$ and
$\gamma_{0}\in(0,1]$ such that $|h_{2}(x)|\leq c|h_{1}(x)|^{\gamma_{0}}$
whenever $x\in K$. This verifies the second conclusion of the theorem and thus
completes the proof. ∎

Next we provide some sufficient conditions for the exponent metric
subregularity with explicit exponents for second-order stationary sets.

######  Corollary 6.5 (exponent metric subregularity for second-order
stationary points).

Let $f\colon\mathbb{R}^{m}\to\mathbb{R}$ be a ${\cal C}^{2}$-smooth function,
and let $\overline{x}\in\Theta$ for the second-order stationary set (2.3).
Suppose that either one of the following conditions holds:

  * (i)

$f$ satisfies the strict saddle point property and the KL property at
$\overline{x}$ with the KL exponent $\theta$.

  * (ii)

$f=\varphi\circ g$, where $\varphi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a
convex function satisfying the KL property at $g(\overline{x})$ with the KL
exponent $\theta$, and where $g:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ is a
smooth mapping with the surjective derivative $\nabla g(\overline{x})$.

Then $\nabla f$ enjoys the generalized metric subregularity property at
$\overline{x}$ with respect to $(\psi,\Theta)$, where
$\psi(t)=t^{\frac{\theta}{1-\theta}}$.

###### Proof.

For (i), we get by the KL property of $f$ at $\overline{x}$ with the exponent
$\theta$ that there are $c,\eta,\epsilon>0$ such that

$d(0,\nabla f(x))\geq c^{-1}\big{(}f(x)-f(\overline{x})\big{)}^{\theta}$ (6.5)

whenever $x\in
B_{\mathbb{R}^{m}}(\overline{x},\epsilon)\cap[f(\overline{x})<f<f(\overline{x})+\eta]$.
Using the continuity of $f$ and shrinking $\epsilon$ if needed tell us that
(6.5) holds for all $x\in
B_{\mathbb{R}^{m}}(\overline{x},\epsilon)\cap[f>f(\overline{x})]$. This
together with [20, Lemma 6.1] implies that there exist $\alpha>0$ and
$\epsilon_{0}\in(0,\epsilon)$ such that

$d(x,[f\leq
f(\overline{x})])\leq\alpha\,\big{(}f(x)-f(\overline{x})\big{)}^{1-\theta}\;\mbox{
for all }\;x\in B_{\mathbb{R}^{m}}(\overline{x},\epsilon_{0}).$

Shrinking $\epsilon_{0}$ again if necessary, we deduce from Propositions 6.2
and 6.3 that

$d(x,\Theta)\leq\alpha\,\big{(}f(x)-f(\overline{x})\big{)}^{1-\theta}\;\mbox{
whenever }\;x\in B_{\mathbb{R}^{m}}(\overline{x},\epsilon_{0}).$

Thus there exists $M>0$ with $d(x,\Theta)\leq M\,d\big{(}0,\nabla
f(x)\big{)}^{\frac{1-\theta}{\theta}}$ for all $x\in
B_{\mathbb{R}^{m}}(\overline{x},\epsilon_{0})$, and so (i) holds.

To justify (ii) under the imposed assumptions, it follows from [21, Theorem
3.2] that $f$ satisfies the KL property at $\overline{x}$ with the KL exponent
$\theta$. Since $\overline{x}\in\Theta\subset\Gamma$, we get from Lemma 3.6
that $f$ satisfies the strict saddle point property at $\overline{x}$, and
therefore the claimed conclusion follows from part (i). ∎

In the rest of this section, we discuss three practical models that often
appear in, e.g., machine learning, image processing, and statistics for which
the obtained sufficient conditions allow us to verify the second-order
generalized metric subregularity.

######  Example 6.6 (over-parameterization of compressed sensing models).

Consider the $\ell_{1}$-regularization problem, known also as the Lasso
problem:

$\min_{x\in\mathbb{R}^{m}}\|Ax-b\|^{2}+\nu\|x\|_{1},$ (6.6)

where $A\in\mathbb{R}^{n\times m}$, $b\in\mathbb{R}^{n}$, $\nu>0$, and
$\|\cdot\|_{1}$ is the usual $\ell_{1}$ norm. A recent interesting way to
solve this problem [34, 35, 36] is to transform it into an equivalent smooth
problem

$\min_{(u,v)\in\mathbb{R}^{m}\times\mathbb{R}^{m}}f_{OP}(u,v):=\|A(u\circ
v)-b\|^{2}+\nu(\|u\|^{2}+\|v\|^{2}),$ (6.7)

where $u\circ v$ is the Hadamard (entrywise) product between the vector $u$
and $v$ in the sense that $(u\circ v)_{i}:=u_{i}v_{i}$, $i=1,\ldots,m$. A nice
feature of this over-parameterized model is that its objective function is a
polynomial (and so ${\cal C}^{2}$-smooth and subanalytic), and it satisfies
the strong strict saddle point property; see [35, Appendix C] for the detailed
derivation, and [34, 36] for more information.

To proceed, we first use Theorem 6.4 to see that the generalized metric
subregularity holds for $\nabla f_{OP}$ with respect to $(\psi,\Theta)$, where
$\psi(t)=t^{\gamma}$ for some $\gamma>0$. In fact, it is possible to identify
the exponent $\gamma$ explicitly. As shown in [34], the fulfillment of the
strict complementarity condition

$0\in 2A^{T}(A\overline{x}-b)+{\rm
ri}\,\big{(}\nu\,\partial\|\cdot\|_{1}(\overline{x})\big{)},$ (6.8)

where ‘${\rm ri}$’ denotes the relative interior, ensures that $f_{OP}$
satisfies the KL property at any $\overline{x}\in\Gamma$ with the KL exponent
$1/2$. In the absence of the strict complementarity condition, it is shown in
[34] that $f_{OP}$ satisfies the KL property at any $\overline{x}\in\Gamma$
with the KL exponent $3/4$.

Therefore, Corollary 6.5, tells us that for any $\overline{x}\in\Theta$
satisfying the strict complementarity condition (6.8), $\nabla f_{OP}$ enjoys
the standard metric subregularity property (as $\psi(t)=t$) at $\overline{x}$
with respect to $\Theta$. In the absence of strict complementarity condition,
$\nabla f_{OP}$ satisfies the generalized metric subregularity property at
$\overline{x}$ with respect to $(\psi,\Theta)$, where $\psi(t)=t^{3}$.

######  Example 6.7 (best rank-one matrix approximation).

Consider the following function $f:\mathbb{R}^{m}\rightarrow\mathbb{R}$ that
appears in the rank-one matrix approximation

$f(x):=\frac{1}{2}\|xx^{T}-M\|^{2}_{F}=\frac{1}{2}\sum_{i,j=1}^{m}(x_{i}x_{j}-M_{ij})^{2},$

where we suppose for simplicity that $M$ is a symmetric $(m\times m)$ matrix
with its maximum eigenvalue $\lambda_{\max}(M)>0$. Direct verification shows
that

$\nabla f(x)=\|x\|^{2}x-Mx\mbox{ and
}\nabla^{2}f(x)=2xx^{T}-M+\|x\|^{2}I_{m},$

and hence we have $\Gamma=\\{x\in\mathbb{R}^{m}\;|\;Mx=\|x\|^{2}x\\}$. Let us
check next that $\Theta=\Omega$, where

$\displaystyle\Omega:=\big{\\{}x\in\mathbb{R}^{m}\;\big{|}\;x\mbox{ is an
eigenvector of }M\mbox{ associated with the largest eigenvalue}\mbox{ and
}\|x\|=\sqrt{\lambda_{\max}(M)}\big{\\}}.$

Indeed, take $x\in\Theta$ and observe that if $x=0$, then $\nabla^{2}f(x)=-M$
having a negative eigenvalue. This is impossible by $x\in\Theta$. For $x\neq
0$, $x$ is an eigenvector of $M$ with the associated eigenvalue
$\lambda=\|x\|^{2}$. Suppose that $\lambda<\lambda_{\max}(M)$ and get, for any
unit eigenvector $d$ associated with $\lambda_{\max}(M)$, that

$0\leq
d^{T}\nabla^{2}f(x)d=2(x^{T}d)^{2}-d^{T}Md+\|x\|^{2}\|d\|^{2}=-\lambda_{\max}(M)+\lambda.$

This is also impossible, and so $\lambda=\lambda_{\max}(M)$ implying that
$\|x\|=\sqrt{\lambda_{\max}(M)}.$ Thus $\Theta\subset\Omega$.

Now take $x\in\Omega$ and see that for any $d\in\mathbb{R}^{m}$ we have

$\displaystyle d^{T}(\nabla^{2}f(x))d$ $\displaystyle=$ $\displaystyle
2(x^{T}d)^{2}-d^{T}Md+\|x\|^{2}\|d\|^{2}$ $\displaystyle\geq$ $\displaystyle
2(x^{T}d)^{2}-\lambda_{\max}(M)\|d\|^{2}+\lambda_{\max}(M)\|d\|^{2}\geq 0,$

which shows that the reverse inclusion holds, and the claim follows.

Suppose next that the largest eigenvalue $\lambda_{\max}(M)$ is simple, i.e.,
its geometric multiplicity is one; note that this condition holds generically.
Then the eigenspace of $M$ associated with $\lambda_{\max}(M)$ is one-
dimensional, and so $\Theta$ consists only of two elements $\\{\pm v\\}$,
where $v$ is the eigenvector associated with the largest eigenvalue, and of
length $\sqrt{\lambda_{\max}(M)}$. Both of these two elements are global
minimizers of $f$. Hence in this case, $f$ satisfies the strong strict saddle
point property. Furthermore, it follows from Theorem 6.4 that the generalized
metric subregularity holds for $\nabla f$ with respect to $(\psi,\Theta)$,
where $\psi(t)=t^{\gamma}$ for some $\gamma>0$. Indeed, direct computations
show that at $\bar{x}=\pm v$, where $v$ is the eigenvector associated with the
largest eigenvalue, we have
$\nabla^{2}f(\bar{x})=2vv^{T}-M+\|v\|^{2}I_{m}=2vv^{T}-M+\lambda_{\max}(M)I_{m}$.
This tells us that $d^{T}\nabla^{2}f(\bar{x})d\geq 0$ for all
$d\in\mathbb{R}^{m}$, and that $d^{T}\nabla^{2}f(\bar{x})d=0$ if and only if
$v^{T}d=0$ and $Md=\lambda_{\max}(M)d$, which happens only when $d=0$.
Therefore, $\nabla^{2}f(\bar{x})\succ 0$, and so the metric subregularity
holds for $\nabla f$ with respect to $\Theta$ at any $\overline{x}\in\Theta$.

######  Example 6.8 (generalized phase retrieval problem).

Consider the optimization problem

$\min_{x\in\mathbb{R}^{m}}f(x)=\sum_{i=1}^{n}\varphi\big{(}g_{i}(x)\big{)},$

where $\varphi:\mathbb{R}\rightarrow\mathbb{R}$ is a ${\cal C}^{2}$ strictly
convex subanalytic function such that $\varphi^{\prime}(0)=0$, and where
$g_{i}:\mathbb{R}^{m}\rightarrow\mathbb{R}$ are defined by
$g_{i}(x):=\frac{1}{\gamma_{i}}[(a_{i}^{T}x)^{2}-b_{i}^{2}]$ with
$\gamma_{i}>0$, $a_{i}\in\mathbb{R}^{m}\backslash\\{0\\}$, and
$b_{i}\in\mathbb{R}\backslash\\{0\\}$, $i=1,\ldots,n$. We consider the two
typical choices for $\gamma_{i}$ as $\gamma_{i}=1$ and $\gamma_{i}=|b_{i}|$,
$i=1,\ldots,n$, and the two typical choices for $\varphi$ given by:

  * •

the polynomial loss function $\varphi_{PL}(t)=t^{2p}$ with $p\geq 1$;

  * •

the pseudo-Huber loss function in the form
$\varphi_{PHL}(t)=\delta^{2}\bigg{(}\sqrt{1+\frac{t^{2}}{\delta^{2}}}-1\bigg{)}$
with $\delta>0$.

This class of problems arises in phase retrieval models (see [8, 9, 40]) when
the goal is to recover an unknown signal from the observed magnitude of some
linear transformation such as, e.g., the Fourier transform.

Below we consider the two settings: (I) the vectors $\\{a_{1},\ldots,a_{n}\\}$
are linearly independent; (II) the vectors $\\{a_{1},\ldots,a_{n}\\}$ are
independent and identically distributed (i.i.d.) standard Gaussian random
vectors, $b_{i}=a_{i}^{T}u$ for some $u\in\mathbb{R}^{m}\setminus\\{0\\}$ and
$\varphi(t)=t^{2}$. Note that in the first setting, the linear independence
condition can be easily verified, and it is usually satisfied when $m$ is much
larger than $n$. The second setting is also frequently considered in the
literature; see, e.g., [8, 9, 40].

First we consider setting (I), where $\\{a_{1},\ldots,a_{n}\\}$ is linearly
independent, to verify that $\nabla f$ satisfies the generalized metric
subregularity property with respect to the second-order stationary set
$\Theta$. Observe that

$\displaystyle\nabla f(x)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\varphi^{\prime}(g_{i}(x))\nabla
g_{i}(x)=\sum_{i=1}^{n}\frac{2}{\gamma_{i}}\,\big{[}(a_{i}^{T}x)\,\varphi^{\prime}\big{(}g_{i}(x)\big{)}\big{]}\,a_{i},$

and thus it follows from the linear independence condition that

$\Gamma=\big{\\{}x\;\big{|}\;\nabla
f(x)=0\big{\\}}=\bigcap_{i=1}^{n}\Big{\\{}x\;\Big{|}\;a_{i}^{T}x=0\;\mbox{or}\;\varphi^{\prime}\big{(}g_{i}(x)\big{)}=0\Big{\\}},$

and for all $x\in\mathbb{R}^{m}$ we have
$\nabla^{2}f(x)=\sum_{i=1}^{n}\frac{2}{\gamma_{i}}\,\big{\\{}\varphi^{\prime}\big{(}g_{i}(x)\big{)}+{\frac{2}{\gamma_{i}}}(a_{i}^{T}x)^{2}\,\varphi^{\prime\prime}(g_{i}(x))\big{\\}}\,a_{i}a_{i}^{T}.$
Let us now show that

$\Theta=\big{\\{}x\;\big{|}\;\varphi^{\prime}\big{(}g_{i}(x)\big{)}=0,\;i=1,\ldots,n\big{\\}}.$
(6.9)

The inclusion “$\supset$” in (6.9) is obvious. To check the reverse inclusion,
pick $x\in\Theta$ and suppose that there exists $i_{0}$ such that
$\varphi^{\prime}\big{(}g_{i_{0}}(x)\big{)}\neq 0$. By $\Theta\subset\Gamma$,
we have $a_{i_{0}}^{T}x=0$, which tells us that
$g_{i_{0}}(x)=(a_{i_{0}}^{T}x)^{2}-b_{i}^{2}=-b_{i}^{2}<0$. Since
$\varphi^{\prime}(0)=0$ and $\varphi$ is strictly convex (and hence
$\varphi^{\prime}$ is strictly increasing), it follows that
$\varphi^{\prime}(g_{i_{0}}(x))<\varphi^{\prime}(0)=0$. For $d=a_{i_{0}}$, we
then have
$d^{T}\nabla^{2}f(x)d={\frac{2}{\gamma_{i}}}\varphi^{\prime}(g_{i_{0}}(x))\|a_{i_{0}}\|^{4}<0$,
which contradicts the assumption that $x\in\Theta$ and thus justifies (6.9).
Observe further that

$\displaystyle\Theta=\big{\\{}x\;\big{|}\;\varphi^{\prime}\big{(}g_{i}(x)\big{)}=0,\;i=1,\ldots,n\big{\\}}=\big{\\{}x\;\big{|}\;g_{i}(x)=0,\;i=1,\ldots,n\big{\\}}=\big{\\{}x\;\big{|}\;|a_{i}^{T}x|=|b_{i}|,\;i=1,\ldots,n\big{\\}}$

telling us that $\Theta$ reduces to the set of global minimizers. Therefore,
the strong strict saddle point property holds for $f$ if the linear
independence condition is satisfied. Then it follows from Theorem 6.4 that
generalized metric subregularity is fulfilled for $\nabla f$ with respect to
$(\psi,\Theta)$, where $\psi(t)=t^{\gamma}$ for some $\gamma>0$.

Let us further specify the exponent $\gamma$ in both bullet cases above by
using Corollary 6.5. In the polynomial case $\varphi(t)=t^{2p}$ with $p\geq
1$, the direct verification shows that $|\varphi^{\prime}(t)|\geq
c\,\varphi(t)^{\frac{2p-1}{2p}}$ for some $c>0$. Thus $\varphi$ satisfies the
KL property with the KL exponent $1-\frac{1}{2p}$. Let
$g(x)=(g_{1}(x),\ldots,g_{n}(x))$ for all $x\in\mathbb{R}^{m}$, where the
components $g_{i}$ are defined above. We deduce from the previous
considerations that the inclusion $x\in\Theta$ implies that $a_{i}^{T}x\neq 0$
whenever $i=1,\ldots,n$. Hence for any $\overline{x}\in\Theta$, the derivative
operator $\nabla g(\overline{x}):\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ is
surjective by the linear independence assumption. Corollary 6.5 tells us in
this case that the generalized metric subregularity holds for $\nabla f$ with
respect to $(\psi,\Theta)$, where $\psi(t)=t^{2p-1}$.

In the case where $\varphi$ is the pseudo-Huber loss, we have
$\varphi^{\prime\prime}(t)>0$ for all $t\in\mathbb{R}$, and it is not hard to
verify that the function $\overline{\varphi}(y):=\sum_{i=1}^{n}\varphi(y_{i})$
satisfies the KL property at
$\overline{y}=(g_{1}(\overline{x}),\ldots,g_{n}(\overline{x}))$ with the KL
exponent $1/2$. Note also that $f(x):=(\overline{\varphi}\circ g)(x)$ with
$g(x)=(g_{1}(x),\ldots,g_{n}(x))$ for all $x\in\mathbb{R}^{m}$, and so
Corollary 6.5 implies that the standard metric subregularity holds for $\nabla
f$ at any $\overline{x}\in\Theta$ with respect to $\Theta$.

Next we consider the second setting (II). As shown in [8] in the typical case
of $\gamma_{i}=|b_{i}|=|a_{i}^{T}u|$, there exist positive constants $c,C$
such that if $n\geq Cm$, where $n$ is the number of samples and $m$ is the
dimension of the underlying space, then with probability at least
$1-e^{-c\,n}$ the only local minimizers of $f$ are $\pm u$ (which are also
global minimizers), $f$ is strongly convex in a neighborhood of $\pm u$, and
all the other critical points are either strict saddle points or local
maximizers with strictly negative definite Hessians. Thus in this setting,
when the number of samples $n$ is sufficiently large, we get with high
probability that $\Theta=\\{\pm u\\}$, and that for any
$\overline{x}\in\Theta$ the strong saddle point property holds at
$\overline{x}$. It follows therefore from Corollary 6.5 that the standard
metric subregularity is satisfied for $\nabla f$ at $\overline{x}$ with
respect to $\Theta$. Note finally that in the case where $\gamma_{i}=1$, a
similar result on the saddle point property is obtained in [9] under the
stronger assumption that $n\geq Cm\log(m)$ for some positive number $C$.

##  7 High-order Regularized Newton Method with Momentum

In this section, we design a new high-order Newtonian method with momentum and
justify its fast convergence by using the above results on generalized metric
regularity and related investigations.

For the optimization problem $\min_{x\in\mathbb{R}^{m}}f(x)$, the following
assumptions are imposed:

######  Assumption 7.1 (major assumptions).

The objective function $f$ satisfies the conditions:

(1) $f$ is ${\cal C}^{2}$-smooth and bounded below, i.e.,
$f^{*}=\inf_{x\in\mathbb{R}^{m}}f(x)>-\infty$.

(2) There exists a closed convex set $\mathcal{F}\subset\mathbb{R}^{m}$ with
nonempty interior such that $\mathcal{L}(f(x_{0}))\subset{\rm
int}(\mathcal{F})$, where $x_{0}\in{\rm int}(\mathcal{F})$ is a starting point
of the iterative process.

(3) The gradient $\nabla f$ is Lipschitz continuous with modulus $L_{1}>0$ on
$\mathcal{F}$, and the Hessian of $f$ is Hölder-continuous on $\mathcal{F}$
with exponent $q$, i.e., there exist numbers $L_{2}>0$ and $q\in(0,1]$ such
that $\|\nabla^{2}f(x)-\nabla^{2}f(y)\|\leq L_{2}\|x-y\|^{q}$ for all
$x,y\in\mathcal{F}$.

Given $x\in\mathbb{R}^{m}$ and $q\in(0,1]$, define the $(q+2)$th-order
regularized quadratic approximation for $f$ at $x$ by

$f_{\sigma}(y;x):=f(x)+\left\langle\nabla
f(x),y-x\right\rangle+\frac{1}{2}\langle\nabla^{2}f(x)(y-x),y-x\rangle+\frac{\sigma}{(q+1)(q+2)}\|y-x\|^{q+2},$
(7.1)

where $\sigma>0$ serves as a regularization parameter. Consider also

$\overline{f}_{\sigma}(x):=\min_{y\in\mathbb{R}^{m}}f_{\sigma}(y;x)\quad\text{and}\quad
y_{\sigma}(x)\in\mathop{\arg\min}_{y\in\mathbb{R}^{m}}f_{\sigma}(y;x).$ (7.2)

Here is our high-order Newtonian method with momentum steps.

Algorithm 1 High-order regularization method with momentum

1: Input: initial point $x_{0}=\widehat{x}_{0}\in\mathbb{R}^{m}$, scalars
$\overline{\sigma}\in\left(\frac{2L_{2}}{q+2},L_{2}\right]$ and
$\zeta\in[0,1)$.

2: for $k=0,1,\dots$ do

3: Regularization step: Choose $\sigma_{k}\in[\overline{\sigma},2L_{2}]$ and
find
$\widehat{x}_{k+1}:=y_{\sigma_{k}}(x_{k})\in\mathop{\arg\min}_{y\in\mathbb{R}^{m}}f_{\sigma_{k}}(y;x_{k}).$
(7.3)

4: Momentum step: $\beta_{k+1}=\min\big{\\{}\zeta,\|\nabla
f(\widehat{x}_{k+1})\|,\|\widehat{x}_{k+1}-x_{k}\|\big{\\}},$ (7.4)
$\widetilde{x}_{k+1}=\widehat{x}_{k+1}+\beta_{k+1}(\widehat{x}_{k+1}-\widehat{x}_{k}).$
(7.5)

5: Monotone step:
$x_{k+1}=\mathop{\arg\min}_{x\in\\{\widehat{x}_{k+1},\widetilde{x}_{k+1}\\}}f(x).$
(7.6)

6: end for

Note that when $q=1$ and $\zeta=0$ (i.e., the Hessian is locally Lipschitzian
and there is no momentum step), this algorithm reduces to the classical cubic
regularized Newton method proposed in [32]. In the case where $\zeta=0$ (i.e.,
no momentum steps are considered), this method has also been considered in
[15] with a comprehensive analysis of its complexity. The
superlinear/quadratic convergence for the cubic Newton method was first
established in [32] under the nondegeneracy condition, and then was relaxed to
the uniform metric subregularity/error bound condition on $\nabla f$ in [40].
We also note that, if $L_{2}$ can be obtained easily, then the parameter
$\sigma_{k}$ in Algorithm 1 can be chosen as $L_{2}$. Otherwise, the parameter
$\sigma_{k}$ therein can be obtained by using line search strategies outlined
in [32]. Incorporating momentum steps is a well-adopted technique in first-
order optimization to accelerate numerical performances. Therefore, it is
conceivable to also consider incorporating the momentum technique into high-
order regularization methods.

To illustrate this, we see from the following plots (Figures 1 and 2) that
incorporating the momentum steps into the cubic Newton methods in solving
phase retrieval and matrix completion problems can lead to faster convergence
with comparable quality of numerical solutions. Here we follow the setup as in
[40] for both problems with dimension $128$, and use their code (available at
https://github.com/ZiruiZhou/cubicreg app.git) for implementing the cubic
regularized Newton method. For the cubic regularized Newton method with
momentum steps, we choose $\xi=0.1$ and set $q=1$ in Algorithm 1 and follow
the same approach as in [40] to solve the subproblems (7.3). Then we use the
same notion of relative error as in [40] and plot the relative error (in the
log scale) in terms of the number of iterations. 444While it is clear from the
presented numerical illustrations that incorporating momentum steps can have
numerical advantages, further extensive numerical experiments are definitely
needed. This goes beyond the scope of this paper and will be carried out in a
separate study.

Figure 1: Phase retrieval problem Figure 2: Matrix completion problem

Let us emphasize that, to the best of our knowledge, superlinear/quadratic
convergence for high-order regularized methods with momentum steps has not
been considered in the literature. We also mention that, even when it is
specialized to the celebrated cubic regularized Newton method without momentum
steps, our assumptions for quadratic convergence are strictly weaker than the
ones imposed in [40].

Note that in the regularization step, Algorithm 1 requires computing
$y_{\sigma_{k}}(x_{k})$, which is a global minimizer of
$f_{\sigma_{k}}(\cdot;x_{k})$. This can be done by solving either an
equivalent convex optimization problem, or an eigenvalue problem; see, e.g,
[15, 32, 40]. The necessary and sufficient optimality conditions for global
minimizers of the regularized quadratic approximation (7.1) presented in the
next lemma are taken from [16].

######  Lemma 7.2 (optimality conditions for regularized quadratic
approximations).

Given $x\in\mathcal{F}$, we have that $y_{\sigma}(x)$ is a global minimizer of
(7.1) if and only if the following conditions hold:

$\nabla
f(x)+\nabla^{2}f(x)(y_{\sigma}(x)-x)+\frac{\sigma}{q+1}\|y_{\sigma}(x)-x\|^{q}(y_{\sigma}(x)-x)=0,$
(7.7) $\nabla^{2}f(x)+\frac{\sigma}{q+1}\|y_{\sigma}(x)-x\|^{q}I_{m}\succeq
0.$ (7.8)

For the reader’s convenience, we also formulate straightforward consequences
of our major requirements in Assumption 7.1 that can be found in [15, (2.7)
and (2.8)].

######  Lemma 7.3 (consequences of major assumptions).

Suppose that all the requirements in Assumption 7.1 are satisfied. Then for
any $x,y\in\mathcal{F}$ we get the estimates

$\|\nabla f(y)-\nabla
f(x)-\nabla^{2}f(x)(y-x)\|\leq\frac{L_{2}}{q+1}\|y-x\|^{q+1},$ (7.9)
$\left|f(y)-f(x)-\langle\nabla
f(x),y-x\rangle-\frac{1}{2}\langle\nabla^{2}f(x)(y-x),y-x\rangle\right|\leq\frac{L_{2}}{(q+1)(q+2)}\|y-x\|^{q+2}.$
(7.10)

The next technical lemma is needed for the convergence justification below.

######  Lemma 7.4 (relationships for Hölder exponents).

Given $b\in(0,\infty)$ and $q\in(0,1]$, the following hold.

(i) For each $\alpha>0$, there is a unique solution $t(\alpha)>2$ to the
equation

$\alpha t^{q+1}-2\alpha t^{q}-b(q+1)t-b=0.$

Moreover, the function $\alpha\mapsto t(\alpha)$ is decreasing on
$(0,\infty)$.

(ii) Letting $a\in(0,\infty)$ and $\ell:=t(a)>0$, suppose that

$ax^{q+1}\leq by^{q+1}+2ax^{q}y+b(q+1)xy^{q}\;\mbox{ for
}\;x,y\in\mathbb{R}_{+}.$ (7.11)

Then for such numbers $x$ and $y$, we have the inequality $x\leq\ell y$.

###### Proof.

To verify (i), we define the function $f(\alpha,t):=\alpha t^{q+1}-2\alpha
t^{q}-b(q+1)t-b$ for all $(\alpha,t)\in(0,\infty)\times\mathbb{R}_{+}$ and
denote $t(\alpha)=\\{t\;|\;f(\alpha,t)=0\\}$ with $\alpha\in(0,\infty)$, which
occurs to be single-valued as shown below. Direct calculations give us the
expressions

$\frac{\partial f}{\partial t}(\alpha,t)=\alpha(q+1)t^{q}-2\alpha
qt^{q-1}-b(q+1),$ $\frac{\partial^{2}f}{\partial t^{2}}(\alpha,t)=\alpha
q(q+1)t^{q-1}-2\alpha q(q-1)t^{q-2}=\alpha
qt^{q-2}\big{(}(q+1)t-2(q-1)\big{)}>0,\quad t\in(0,\infty),$

and hence $\frac{\partial f}{\partial t}(\alpha,\cdot)$ is increasing on
$\mathbb{R}_{+}$. Combining this with the facts that $\lim_{t\to
0^{+}}\frac{\partial f}{\partial t}(\alpha,t)<0$ and
$\lim_{t\to\infty}\frac{\partial f}{\partial t}(\alpha,t)=\infty$ for any
$\alpha\in(0,\infty)$ guarantees the existence of $\widetilde{t}(\alpha)>0$
such that $f(\alpha,\cdot)$ is decreasing on $(0,\widetilde{t}(\alpha)]$ and
increasing on $(\widetilde{t}(\alpha),\infty)$. Observing that
$f(\alpha,0)=-b<0$ and $\lim_{t\to\infty}f(\alpha,t)=\infty$ for any
$\alpha\in(0,\infty)$, we see that the mapping $\alpha\mapsto t(\alpha)$ with
$\alpha\in(0,\infty)$ is single-valued and satisfies the implication

$f(\alpha,t)\leq 0\Longrightarrow t\leq t(\alpha).$ (7.12)

Defining further the univariate function

$\alpha(t):=\frac{b+b(q+1)t}{t^{q+1}-2t^{q}}\quad\mbox{for all
}\;t\in(2,\infty),$

we claim that $t\mapsto\alpha(t)$ is decreasing on $(2,\infty)$ with the range
$(0,\infty)$. This clearly ensures that its inverse function $\alpha\mapsto
t(\alpha)$ is decreasing on $(0,\infty)$ with a range of $(2,\infty)$, and so
(i) follows.

Thus to prove (i), it remains to verify the formulated claim. Direct
calculations show that

$\displaystyle\alpha^{\prime}(t)=$
$\displaystyle\frac{b(q+1)(t^{q+1}-2t^{q})-(b+b(q+1)t)\Big{(}(q+1)t^{q}-2qt^{q-1}\Big{)}}{(t^{q+1}-2t^{q})^{2}}$
(7.13) $\displaystyle=$
$\displaystyle\frac{bt^{q-1}}{(t^{q+1}-2t^{q})^{2}}\Big{[}(q+1)(t^{2}-2t)-(1+(q+1)t)\Big{(}(q+1)t-2q\Big{)}\Big{]}$
$\displaystyle=$
$\displaystyle\frac{bt^{q-1}}{(t^{q+1}-2t^{q})^{2}}\Big{[}-q(q+1)t^{2}+(2q^{2}-q-3)t+2q\Big{]}.$

For all $t\in\mathbb{R}$, we consider the function
$h(t):=-q(q+1)t^{2}+(2q^{2}-q-3)t+2q$ and observe that
$\lim_{t\to-\infty}h(t)=-\infty$ and $h(0)=2q>0$ and $h(2)=-4q-6<0$, which
allows us to deduce from (7.13) that $\alpha(t)$ is decreasing on
$(2,\infty)$. Combining this with the facts that $\lim_{t\to
2}\alpha(t)=\infty$ and $\lim_{t\to\infty}\alpha(t)=0$ justifies the above
claim and hence the entire assertion (i).

To verify now assertion (ii), we deduce from (7.11) that
$ax^{q+1}-by^{q+1}-2ax^{q}y-b(q+1)xy^{q}\leq 0$. Letting $x:=ty$ for some
$t\in\mathbb{R}_{+}$ and substituting it into the above inequality tells us
that

$\left(at^{q+1}-2at^{q}-b(q+1)t-b\right)y^{q+1}\leq 0.$ (7.14)

If $y=0$, then (7.11) implies that $x=0$, and so (ii) trivially holds. To
justify the inequality $x\leq\ell y$, it suffices to consider the case where
$y>0$. Dividing both sides of (7.14) by $y^{q+1}$, we get

$f(a,t)=at^{q+1}-2at^{q}-b(q+1)t-b\leq 0,$

and therefore the claimed inequality follows from (7.12) and the fact that
$t(\alpha)>2$. The proof is complete. ∎

The following lemma is an important step to justify the desired performance of
Algorithm 1.

######  Lemma 7.5 (estimates for regularized quadratic approximations).

Under Assumption 7.1, let $x\in\mathcal{F}$, and let $\widecheck{x}$ be a
projection point of $x$ to $\Theta$. If $\widecheck{x}\in\mathcal{F}$, then
for any $\sigma>0$ we have the estimate

$\|y_{\sigma}(x)-x\|\leq\ell_{\sigma}\,d(x,\Theta),$ (7.15)

where $y_{\sigma}(x)$ is a minimizer of the regularized quadratic
approximation from (7.1) and (7.2) with $\ell_{\sigma}:=t^{*}$ defined as the
unique positive solution $t^{*}$ of the equation $H_{\sigma}(t)=\sigma
t^{q+1}-2\sigma t^{q}-L_{2}(q+1)t-L_{2}=0$ with $L_{2}$ taken from part (3) of
Assumption 7.1.

###### Proof.

Denote $z:=y_{\sigma}(x)$ and deduce from condition (7.2) and Lemma 7.2 that

$0=\nabla f(x)+\nabla^{2}f(x)(z-x)+\frac{\sigma}{q+1}\|z-x\|^{q}(z-x).$ (7.16)

By $\widecheck{x}\in\Theta$, we have $\nabla f(\widecheck{x})=0$ and
$\nabla^{2}f(\widecheck{x})\succeq 0$. Then it follows from (7.16) that

$\displaystyle\left(\nabla^{2}f(\widecheck{x})+\frac{\sigma}{q+1}\|z-x\|^{q}I_{m}\right)(z-\widecheck{x})=\nabla^{2}f(\widecheck{x})\Big{(}(z-x)-(\widecheck{x}-x)\Big{)}+\frac{\sigma}{q+1}\|z-x\|^{q}\Big{(}(z-x)-(\widecheck{x}-x)\Big{)}$
$\displaystyle=\nabla f(\widecheck{x})-\nabla
f(x)-\nabla^{2}f(\widecheck{x})(\widecheck{x}-x)-\frac{\sigma}{q+1}\|z-x\|^{q}(\widecheck{x}-x)-(\nabla^{2}f(x)-\nabla^{2}f(\widecheck{x}))(z-x).$

Combining the latter with $\nabla^{2}f(\widecheck{x})\succeq 0$ gives us

$\left\|\left(\nabla^{2}f(\widecheck{x})+\frac{\sigma}{q+1}\|z-x\|^{q}I_{m}\right)(z-\widecheck{x})\right\|\geq\frac{\sigma}{q+1}\|z-x\|^{q}\|z-\widecheck{x}\|,$

and then employing $\widecheck{x}\in\mathcal{F}$, Lemma 7.3, and Assumption
7.1(3), we arrive at

$\displaystyle\frac{\sigma}{q+1}\|z-x\|^{q}\|z-\widecheck{x}\|\leq$
$\displaystyle\|\nabla f(x)-\nabla
f(\widecheck{x})-\nabla^{2}f(\widecheck{x})(x-\widecheck{x})\|+\frac{\sigma}{q+1}\|z-x\|^{q}\|x-\widecheck{x}\|$
(7.17)
$\displaystyle+\|\nabla^{2}f(x)-\nabla^{2}f(\widecheck{x})\|\cdot\|z-x\|$
$\displaystyle\leq$
$\displaystyle\frac{L_{2}}{q+1}\|x-\widecheck{x}\|^{q+1}+\frac{\sigma}{q+1}\|z-x\|^{q}\|x-\widecheck{x}\|+L_{2}\|z-x\|\cdot\|x-\widecheck{x}\|^{q}.$

Applying further the triangle inequality
$\|z-\widecheck{x}\|\geq\|z-x\|-\|x-\widecheck{x}\|$ ensures that

$\frac{\sigma}{q+1}\|z-x\|^{q+1}-\frac{\sigma}{q+1}\|z-x\|^{q}\|x-\widecheck{x}\|\leq\frac{\sigma}{q+1}\|z-x\|^{q}\|z-\widecheck{x}\|,$

which being substituted into (7.17) yields

$\frac{\sigma}{q+1}\|z-x\|^{q+1}\leq\frac{L_{2}}{q+1}\|x-\widecheck{x}\|^{q+1}+\frac{2\sigma}{q+1}\|z-x\|^{q}\|x-\widecheck{x}\|+L_{2}\|z-x\|\cdot\|x-\widecheck{x}\|^{q}.$

By Lemma 7.4(ii), this allows us to find a positive scalar $\ell_{\sigma}$
(depending only on $\sigma$) such that
$\|z-x\|\leq\ell_{\sigma}\|x-\widecheck{x}\|$. Recalling that
$z=y_{\sigma}(x)$ and $d(x,\Theta)=\|x-\widecheck{x}\|$ verifies the desired
inequality (7.15). ∎

The last lemma here plays a significant role in the convergent analysis of our
algorithm. Its proof is rather technical and mainly follows the lines of
justifying fast convergence of the cubic regularization method in [40] with
additional adaptations to accommodate the momentum steps and the Hölderian
continuity of Hessians. For completeness and the reader’s convenience, we
present details in the Appendix (Section 9).

######  Lemma 7.6 (estimates for iterates of the high-order regularized method
with momentum).

Let $\\{x_{k}\\}$ be a sequence of iterates in Algorithm 1 under Assumption
7.1. If the set $\mathcal{L}(f(x_{k_{0}}))$ is bounded for some
$k_{0}\in\mathbb{N}$, then the following assertions hold.

(i) For all $k\in\mathbb{N}$ with $k\geq k_{0}$, we have the inequalities

$f(x_{k+1})+\frac{(q+2)\overline{\sigma}-2L_{2}}{2(q+1)(q+2)}\|\widehat{x}_{k+1}-x_{k}\|^{q+2}\leq
f(x_{k}),$ (7.18)

and the limit $v:=\lim_{k\to\infty}f(x_{k})$ exists.

(ii) For all $k\in\mathbb{N}$ with $k\geq k_{0}$, the relationships

$\displaystyle\|x_{k+1}-x_{k}\|\leq(1+\gamma)\|\widehat{x}_{k+1}-x_{k}\|,\quad\lim_{k\to\infty}\|\widehat{x}_{k+1}-x_{k}\|=0,$
(7.19) $\|\nabla f(x_{k+1})\|\leq\frac{3(1+\gamma
L_{1})L_{2}}{q+1}\|\widehat{x}_{k+1}-x_{k}\|^{q+1}$ (7.20)

are fulfilled, where the number $\gamma>0$ in (7.19) is defined by

$\gamma:=\frac{1}{1-\zeta}\left[\frac{2(q+1)(q+2)}{(q+2)\overline{\sigma}-2L_{2}}(f(x_{0})-f^{*})\right]^{\frac{1}{q+2}}.$
(7.21)

(iii) The set $\Omega$ of accumulation points of $\\{x_{k}\\}$ is nonempty.
Moreover, for any $\overline{x}\in\Omega$ we have

$f(\overline{x})=v,\quad\nabla f(\overline{x})=0,\;\mbox{ and
}\;\nabla^{2}f(\overline{x})\succeq 0.$ (7.22)

Now we are in a position to establish the main result on the performance of
Algorithm 1.

######  Theorem 7.7 (convergence rate of the high-order algorithm under
generalized metric subregularity).

Let the iterative sequence $\\{x_{k}\\}$ be generated by Algorithm 1, and let
$\bar{x}$ be its accumulation point provided that the set
$\mathcal{L}(f(x_{k_{0}}))$ is bounded for some $k_{0}\in\mathbb{N}$. In
addition to Assumption 7.1, suppose that there exists $\eta>0$ such that the
generalized metric subregularity condition

$\psi\big{(}d(x,\Theta))\leq\|\nabla f(x)\|\;\mbox{ for all }\;x\in
B_{\mathbb{R}^{m}}(\overline{x},\eta)$ (7.23)

holds with respect to $(\psi,\Theta)$, where
$\psi\colon\mathbb{R}_{+}\to\mathbb{R}_{+}$ is an admissible function, and
where $\Theta$ is the set of second-order stationary points (2.3). Define the
function $\tau:\mathbb{R}_{+}\to\mathbb{R}_{+}$ by

$\tau(t):=\psi^{-1}\Big{(}\frac{3(1+\gamma
L_{1})L_{2}\ell^{q+1}}{q+1}t^{q+1}\Big{)},\quad t\in\mathbb{R}_{+},$ (7.24)

where $\ell:=\ell_{\overline{\sigma}}$ with $\ell_{\sigma}$ taken from Lemma
7.5, and where $\gamma$ is given in (7.21). If $\limsup_{t\to
0^{+}}\frac{\tau(t)}{t}<1$, then $\overline{x}\in\Theta$ and the sequence
$\\{x_{k}\\}$ converges to $\overline{x}$ as $k\to\infty$ with the convergence
rate

$\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{{\tau}(\|x_{k-1}-\overline{x}\|)}<\infty.$

###### Proof.

By Lemma 7.6, we have the inclusion $\Omega\subset\Theta$ together with all
the conditions in (7.18)–(7.20). Let us now verify the estimate

$\|\widehat{x}_{k+1}-x_{k}\|\leq\ell d(x_{k},\Theta)$ (7.25)

for any $k\in\mathbb{N}$ sufficiently large. Having this, we arrive at all of
the claimed conclusions of the theorem by applying the abstract convergence
results of Theorem 4.4 with $\beta(t):=t^{q+1}$ and
$e_{k}:=\|\widehat{x}_{k+1}-x_{k}\|$.

To justify (7.25), let $\widecheck{x}_{k}$ be a projection point of $x_{k}$ to
$\Theta$. Thus we deduce from Lemma 4.1(iii) that

$\lim_{k\to\infty}d(x_{k},\Theta)=\lim_{k\to\infty}\|x_{k}-\widecheck{x}_{k}\|=0.$
(7.26)

Moreover, observing that $x_{k}\in\mathcal{L}(f(x_{0}))\subset{\rm
int}(\mathcal{F})$ for all $k\in\mathbb{N}$ and that $\\{x_{k}\\}$ remains
bounded allows us to find a compact set $\mathcal{C}\subset{\rm
int}(\mathcal{F})$ such that $\\{x_{k}\\}\subset\mathcal{C}$. Based on
$\\{x_{k}\\}\subset\mathcal{C}$ and the conditions given by (7.26), we get
that $\lim_{k\to\infty}d(\widecheck{x}_{k},\mathcal{C})=0$. Coupling this with
the inclusion $\mathcal{C}\subset{\rm int}(\mathcal{F})$ and the compactness
of $\mathcal{C}$ indicates that $\widecheck{x}_{k}\in{\rm int}(\mathcal{F})$
for all large $k$. Consequently, there exists $k_{1}\geq 1$ such that
$x_{k},\widecheck{x}_{k}\in\mathcal{F}$ whenever $k\geq k_{1}$. Employing
Lemmas 7.4 and 7.5 together with $\sigma_{k}\geq\overline{\sigma}>0$ for all
$k$ gives us the number $\ell:=\ell_{\overline{\sigma}}$ from Lemma 7.5
ensuring the estimate

$\|\widehat{x}_{k+1}-x_{k}\|\leq\ell d(x_{k},\Theta)\;\mbox{ for all large
}\;k\in\mathbb{N},$

which justifies (7.25) and thus completes the proof of the theorem. ∎

As a consequence of Theorem 7.7, we show now that if $\nabla f$ enjoys the
(pointwise) exponent metric subregularity property with respect to the second-
order stationary set $\Theta$, then the sequence generated by our algorithm
converges to a second-order stationary point at least superlinearly with an
explicit convergence order under a suitable condition on the exponent.

######  Corollary 7.8 (superlinear convergence under exponent metric
subregularity).

Let $f$ satisfy the Assumption 7.1 with the $q$-th order Hölder continuous
Hessian for some $q\in(0,1]$, let $\\{x_{k}\\}$ be generated by Algorithm 1,
and let the set $\mathcal{L}(f(x_{k_{0}}))$ be bounded for some
$k_{0}\in\mathbb{N}$. Taking $\overline{x}\in\Omega$ and $p>0$, suppose that
there exist $c,\eta>0$ such that

$d(x,\Theta)^{p}\leq c\,\|\nabla f(x)\|\;\mbox{ for all }\;x\in
B_{\mathbb{R}^{m}}(\overline{x},\eta).$

If $p<q+1$, then $\\{x_{k}\\}$ converges at least superlinearly to
$\overline{x}\in\Theta$ as $k\to\infty$ with the rate $\frac{q+1}{p}$, i.e.,

$\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{\|x_{k-1}-\overline{x}\|^{\frac{q+1}{p}}}<\infty.$

###### Proof.

Choosing $\psi(t):=c^{-1}t^{p}$, we have $\tau(t)=O(t^{\frac{q+1}{p}})$ and
deduce the conclusion from Theorem 7.7. ∎

Following the discussions in Remark 5.3, we can establish global convergence
of the sequence $\\{x_{k}\\}$ under the KL property and its convergence rate
depending on the KL exponent. For brevity, the proof is skipped.

######  Proposition 7.9 (convergence under the KL property).

Let $f$ satisfy Assumption 7.1 with the $q$-th order Hölder continuous Hessian
for some $q\in(0,1]$. Let $\\{x_{k}\\}$ be generated by Algorithm 1, and let
the set $\mathcal{L}(f(x_{k_{0}}))$ be bounded for some $k_{0}\in\mathbb{N}$.
Take $\overline{x}\in\Omega$ and suppose that $f$ satisfies the KL property at
$\overline{x}$. Then the sequence $\\{x_{k}\\}$ converges to $\overline{x}$,
which is a second-order stationary point of $f$. If furthermore $f$ satisfies
the KL property at $\overline{x}$ with the KL exponent $\theta$, then we have
the following convergence rate:

$\bullet$ If $\theta=\frac{q+1}{q+2}$, then the sequence $\\{x_{k}\\}$
converges linearly.

$\bullet$ If $\theta>\frac{q+1}{q+2}$, then the sequence $\\{x_{k}\\}$
converges sublinearly with the rate
$O(k^{-\frac{(q+1)(1-\theta)}{(q+2)\theta-(q+1)}})$.

$\bullet$ If $\theta<\frac{q+1}{q+2}$, then the sequence $\\{x_{k}\\}$
converges superlinearly with the rate $\frac{q+1}{(q+2)\theta}$.

######  Remark 7.10 (comparison with known results).

To the best of our knowledge, the derived (superlinear/linear/sublinear)
convergence rates are new in the literature for high-order regularization
methods with momentum steps without any convexity assumptions. To compare in
more detail, consider the case where $p=1$, i.e., the metric subregularity of
$\nabla f$ at $\overline{x}$ holds with respect to the second-order stationary
set $\Theta$. In this case, when applying the high-order regularization
methods with momentum steps to a ${\cal C}^{2}$-smooth function $f$ with the
$q$th-order Hölder continuous Hessian, we obtain the superlinear convergence
of $\\{x_{k}\\}$ with rate $q+1$ to a second-order stationary point. Suppose
further that $q=1$ and no momentum step is used. In that case, we recover the
quadratic convergence rate to a second-order stationary point for the cubic
regularized Newton method, but under the weaker assumption of the pointwise
metric subregularity at $\overline{x}$ instead of the stronger error bound
condition used in [40].

Next we provide two examples with explicit degeneracy illustrating that our
convergence results go beyond the current literature on regularized Newton-
type methods of optimization.

######  Example 7.11 (fast and slow convergence without the error bound
condition).

Consider the function $f(x):=(w^{T}x-a)^{2}(w^{T}x-b)^{2p}$ with
$x\in\mathbb{R}^{m}$, $w\in\mathbb{R}^{m}\backslash\\{0\\}$, $0\leq a<b$, and
$m,p\geq 2$. Direct calculations give us the exact expressions for the first-
order stationary set
$\Gamma=\bigcup_{r\in\\{a,b,\frac{b+pa}{1+p}\\}}\big{\\{}x\;\big{|}\;w^{T}x=r\big{\\}}$
and the second-order stationary set
$\Theta=\bigcup_{r\in\\{a,b\\}}\big{\\{}x\;\big{|}\;w^{T}x=r\\}$. For any
$\overline{x}\in\Theta$, we see that $\nabla^{2}f(\overline{x})$ has a zero
eigenvalue. Similarly to Example 3.5, it is easy to check that the uniform
metric subregularity/error bound condition for $\nabla f$ with respect to
$\Theta$ fails in this case.

Let $\overline{x}\in\Theta=\Theta_{1}\cup\Theta_{2}$, where
$\Theta_{1}=\\{x\;|\;w^{T}x=a\\}$ and $\Theta_{2}=\\{x\;|\;w^{T}x=b\\}$. If
$\overline{x}\in\Theta_{1}$, then there exists $C>0$ such that
$d(x,\Theta)=d(x,\Theta_{1})\leq C\,\|\nabla f(x)\|$ for all
$x\in\mathbb{B}_{\mathbb{R}^{m}}(\overline{x},(b-a)/4)$, and so the metric
subregularity condition of $\nabla f$ holds at $\overline{x}$ with respect to
$\Theta$. On the other hand, direct verification shows that $f$ satisfies the
KL property at $\overline{x}$ with the KL exponent $1-\frac{1}{2p}$ for
$\overline{x}\in\Theta_{2}$.

Let $\mathcal{F}$ be a compact set, and let $x_{0}\in\mathcal{F}$ be such that
Assumption 7.1 is satisfied. Then we see that the Hessian of $f$ is Lipschitz
continuous on $\mathcal{F}$, i.e., $q=1$. This yields the convergence
$x_{k}\to\overline{x}\in\Theta$ of the iterative sequence in Algorithm 1. If
$\overline{x}\in\Theta_{1}$, then Corollary 7.8 implies that the convergence
rate is quadratic. If $\overline{x}\in\Theta_{2}$, then it follows from
Proposition 7.9 that $\\{x_{k}\\}$ converges to $\overline{x}$ sublinearly
with the rate $O(k^{-\frac{2}{2p-3}})$.

######  Example 7.12 (linear and sublinear convergence under the KL property).

For $\gamma>2$ and $M>0$, define the ${\cal C}^{2}$-smooth function
$f:\mathbb{R}\rightarrow\mathbb{R}$ by

$f(x):=|\min\\{\max\\{x,0\\},x+M\\}|^{\gamma}=\left\\{\begin{array}[]{ccl}x^{\gamma}&\mbox{
if }&x>0,\\\ 0&\mbox{ if }&x\in[-M,0],\\\ |x+M|^{\gamma}&\mbox{ if
}&x<-M.\end{array}\right.$

We have that $\Gamma=\Theta=[-M,0]$ and that $f$ satisfies the KL property at
any $\overline{x}\in\Theta$ with the KL exponent $\theta=1-\frac{1}{\gamma}$.
On the other hand, the error bound property of $\nabla f$ with respect to
$\Theta$ fails here.

Let $\mathcal{F}$ be a compact set, and let $x_{0}\in\mathcal{F}$ be such that
Assumption 7.1 is satisfied. It can be easily verified that $f^{\prime\prime}$
is $q$th-order Hölder continuous on $\mathcal{F}$ with
$q=\min\\{\gamma-2,1\\}$. If $\gamma\in(2,3]$, then $\theta=\frac{q+1}{q+2}$,
and the sequence of iterates $\\{x_{k}\\}$ of Algorithm 1 converges to
$\overline{x}\in\Theta$ linearly by Proposition 7.9. If $\gamma>3$, then
$\theta>\frac{q+1}{q+2}$, and so $\\{x_{k}\\}$ converges to
$\overline{x}\in\Theta$ sublinearly with the rate
$O(k^{-\frac{2}{\gamma-3}})$. Observe that for $\gamma=3$, the linear
convergence can be indeed achieved. In this case, we have $q=1$ and $L_{2}=6$,
and then take
$\sigma_{k}:=\sigma\in\big{(}\frac{2L_{2}}{q+2},2L_{2}\big{]}=(4,12]$ for all
$k$ and $x_{0}>0$. Assuming without loss of generality that $\\{x_{k}\\}$ is
an infinite sequence, we get by the construction of Algorithm 1 that

$x_{k+1}\in{\rm
argmin}_{y}\big{\\{}f^{\prime}(x_{k})(y-x_{k})+\frac{1}{2}f^{\prime\prime}(x_{k})(y-x_{k})^{2}+\frac{\sigma}{6}|y-x_{k}|^{3}\big{\\}}.$

Letting $t:=x_{k+1}-x_{k}$ gives us
$f^{\prime}(x_{k})+f^{\prime\prime}(x_{k})t+\frac{\sigma}{2}t|t|=0$. Suppose
now that $x_{k}>0$, and then $f^{\prime}(x_{k})>0$ and
$f^{\prime\prime}(x_{k})>0$. This implies that $t<0$ and hence
$3x_{k}^{2}+6x_{k}t-\frac{\sigma}{2}t^{2}=0$. Therefore,
$t=(\frac{6}{\sigma}-\frac{\sqrt{6\sigma+36}}{\sigma})x_{k}$ and so
$x_{k+1}=\rho x_{k}>0$ with
$\rho=1-\frac{\sqrt{6\sigma+36}-6}{\sigma}\in(0,1)$. Arguing by induction
tells us that $x_{k}>0$ and $x_{k+1}=\rho x_{k}$ for all $k\in\mathbb{N}$.
This yields $x_{k}\rightarrow\overline{x}=0\in\Theta$, which confirms that the
convergence rate is linear.

Finally in this section, we specify the convergence results for the case where
the strict saddle point property holds, which allows us to establish stronger
convergence results. Observe to this end that if the objective function $f$
satisfies the strict saddle point property (resp. strong strict saddle point
property), then Algorithm 1 indeed converges to a local minimizer (resp.
global minimizer) of $f$ with the corresponding superlinear rate. In
particular, this covers the situations discussed in the illustrative examples
of Section 6.

The next corollary addresses a concrete case of the over-parameterized
compressed sensing model. In this case, Algorithm 1 converges to a global
minimizer with a quadratic convergence rate under the strict complementary
condition.

######  Corollary 7.13 (quadratic convergence for over-parameterized
compressed sensing models).

Consider the $\ell_{1}$-regularization model (6.6) and the associated over-
parameterized smooth optimization problem $\min_{x\in\mathbb{R}^{2m}}f(x)$,
where $f:=f_{OP}$ as in (6.7). Then the iterative sequence $\\{x_{k}\\}$ of
Algorithm 1 converges to a global minimizer $\bar{x}$ of (6.7) as
$k\to\infty$, and the following assertions hold:

  * (i)

Under the validity of the strict complementary condition (6.8), $\\{x_{k}\\}$
converges to $\overline{x}$ quadratically, i.e.,

$\limsup_{k\to\infty}\frac{\|x_{k}-\overline{x}\|}{\|x_{k-1}-\overline{x}\|^{2}}<\infty.$

  * (ii)

If the strict complementary condition (6.8) fails, then $\\{x_{k}\\}$
converges to $\overline{x}$ with the order $O(k^{-2})$.

###### Proof.

We know from Section 6 that the strong strict saddle point property is
fulfilled for $f=f_{OP}$. To verify (i), recall that if the strict
complementary condition holds, then $\nabla f$ satisfies the metric
subregularity property at $\overline{x}$ with respect to $\Theta$. Direct
verifications show that $f$ is bounded from below by zero, that the set
$\mathcal{L}(f(x_{0}))$ is bounded, and that the Hessian of $f$ is Lipschitz
continuous on
$\mathcal{F}=\mathcal{L}(f(x_{0}))+\mathbb{B}_{\mathbb{R}^{2m}}(0,1)$. By
setting $p=q=1$, we see that $\\{x_{k}\\}$ converges to
$\overline{x}\in\Theta$ in a quadratic rate. Note also that $f$ satisfies the
strong strict saddle point property, and thus $\overline{x}$ is indeed a
global minimizer.

To prove (ii), observe that if the strict complementary condition fails, then
$f$ satisfies the KL property with the exponent $\theta=\frac{3}{4}$.
Therefore, by setting $q=1$ in Proposition 7.9 we see that $\\{x_{k}\\}$
converges to $\overline{x}\in\Theta$ with the rate
$O(k^{-\frac{(q+1)(1-\theta)}{(q+2)\theta-(q+1)}})=O(k^{-2})$. Similarly to
(i), it follows that $\overline{x}$ is a global minimizer of $f$. ∎

######  Remark 7.14 (further comparison).

During the completion of this paper, we became aware of the preprint [24] in
which the authors examined the convergence rate of the high-order regularized
method without momentum steps for composite optimization problems under the
assumption that the Hessian of the smooth part is Lipschitz continuous labeled
there as “strict continuity.” Recall that the main focus of our paper is on
the development of generalized metric subregularity with applications to fast
convergence analysis for general descent methods. This include, in particular,
the high-order regularized methods with momentum steps. We also mention that
the results obtained in [24] cannot cover the setting of Section 7, where we
incorporate momentum steps and can also handle the case of Hölder continuous
Hessians.

##  8 Concluding Remarks

The main contributions of this paper are summarized as follows.

$\bullet$ We introduce a generalized metric subregularity condition, which
serves as an extension of the standard metric subregularity and its Hölderian
version while being strictly weaker than the uniform version (error bound
condition) recently employed in the convergence analysis of the cubic
regularized Newton method. We then develop an abstract extended convergence
framework that enables us to derive superlinear convergence towards specific
target sets (such as the first-order and second-order stationary points) under
the introduced generalized metric subregularity condition. Interestingly, this
framework also extends the widely used KL convergence analysis, and the
derived superlinear convergence rates of this new framework are sharp in the
sense that the rate can be attained.

$\bullet$ We provide easily verifiable sufficient conditions for the
generalized metric subregularity with respect to the second-order stationary
set under the strict saddle point property. We also demonstrate that several
modern practical models appearing in machine learning, statistics, etc., enjoy
the generalized metric subregularity property with respect to the second-order
stationary set in explicit forms. This includes, e.g., objective functions
that arise in the over-parameterized compressed sensing model, best rank-one
matrix approximation, and generalized phase retrieval problems.

$\bullet$ As a major application of generalized metric subregularity and
abstract convergence analysis, we derive superlinear convergence results for
the new high-order regularized Newton method with momentum. This improves the
existing literature by weakening the regularity conditions and extending the
analysis to include momentum steps. Furthermore, when applying the cubic
regularized Newton methods with momentum steps to solve the over-parameterized
compressed sensing model, we obtain global convergence with a quadratic local
convergence rate towards a global minimizer under the strict complementarity
condition.

One important potential future research topic is to extend the abstract
convergence framework to cover nonmonotone numerical algorithms. Another major
goal of our future research is to extend the obtained second-order results
from ${\cal C}^{2}$-smooth functions to the class of ${\cal C}^{1,1}$
functions [27], i.e., continuously differentiable functions with Lipschitzian
gradients, or to functions with a composite structure; see, e.g., [31].

## References

  * [1] Ahookhosh, M., Aragón-Artacho, F.J., Fleming, Vuong, P.: Local convergence of the Levenberg–Marquardt method under Hölder metric subregularity. Adv. Comput. Math. 45, 2771–2806 (2019)
  * [2] Ahookhosh, M., Nesterov, Y.: High-order methods beyond the classical complexity bounds: inexact high-order proximal-point methods. Math. Prog. (2024). https://doi.org/10.1007/s10107-023-02041-4
  * [3] Aragón-Artacho, F.J., Geoffroy, M.H.: Metric subregularity of the convex subdifferential in Banach spaces. J. Nonlinear Convex Anal. 15, 35-47 (2014)
  * [4] Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Prog. 116, 5–16 (2009)
  * [5] Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Prog. 137, 91–129 (2013)
  * [6] Bierstone, E., Milman, P.: Semianalytic and subanalytic sets. IHES Publ. Math. 67, 5–42 (1988)
  * [7] Bolte, J., Daniilidis. A., Lewis, A.S.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17, 1205–1223 (2007)
  * [8] Cai, J.-F., Huang, M., Li, D., Wang, Y.: The global landscape of phase retrieval II. quotient intensity models. Ann. Appl. Math. 38, 62–114 (2022)
  * [9] Cai, J.-F., Huang, M., Li, D., Wang, Y.: Nearly optimal bounds for the global geometric landscape of phase retrieval. Inverse Problems. 39, 075011 (2023)
  * [10] Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity. Math. Prog. 130, 295–319 (2011).
  * [11] Drusvyatskiy, D., Mordukhovich, B.S., Nghia, T.T.A.: Second-order growth, tilt stability, and metric regularity of the subdifferential. J. Convex Anal. 21, 1165—1192 (2014)
  * [12] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Volumes I and II, Springer, New York (2003)
  * [13] Gaydu, M., Geoffroy, M.H., Jean-Alexis, C.: Metric subregularity of order $q$ and the solving of inclusions. Cent. Eur. J. Math. 9, 147–161 (2011)
  * [14] Gfrerer, H., Outrata, J.V.: On semismooth∗ Newton method of solving generalized equations. SIAM J. Optim. 31, 89–517 (2021)
  * [15] Grapiglia, G.N., Nesterov, Yu.: Regularized Newton methods for minimizing functions with Hölder continuous Hessians. SIAM J. Optim. 27, 478–506 (2017)
  * [16] Hsia, Y., Sheu, R.-L., Yuan, Y.-X.: Theory and application of $p$-regularized subproblems for $p>2$. Optim. Methods Softw. 32, 1059–1077 (2017)
  * [17] Izmailov, A.F., Solodov, M.V.: Newton-Type Methods for Optimization and Variational Problems. Springer, New York (2014)
  * [18] Khanh, P.D., Mordukhovich, B.S., Phat, V.T., Tran, D.B.: Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization. Math. Program. 205, 373–429 (2024)
  * [19] Klatte, D., Kummer, B.: Nonsmooth Equations in Optimization: Regularity, Calculus, and Applications. Kluwer, Boston (2002)
  * [20] Li, G., Mordukhovich, B.S.: Hölder metric subregularity with applications to proximal point method. SIAM J. Optim. 22, 1655–1684 (2012)
  * [21] Li, G., Pong, T.K.: Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods. Found. Comput. Math. 18, 1199-1232 (2018)
  * [22] Li, X., Sun, D., Toh, K.-C.: A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems. SIAM J. Optim. 28, 433–458 (2018)
  * [23] Lindstrom, S.B., Lourenço, B.F., Pong, T.K.: Error bounds, facial residual functions and applications to the exponential cone. Math. Program. 200, 229–278 (2023)