∎ 11institutetext: Ching-pei Lee 22institutetext: 22email:
<EMAIL_ADDRESS>Institute of Statistical Sciences, Academia
Sinica, Taipei, Taiwan

# Accelerating Inexact Successive Quadratic Approximation for Regularized
Optimization Through Manifold Identification††thanks: Version of . This work
was supported in part by MOST of R.O.C. grant 109-2222-E-001-003 -MY3.

Ching-pei Lee

###### Abstract

For regularized optimization that minimizes the sum of a smooth term and a
regularizer that promotes structured solutions, inexact proximal-Newton-type
methods, or successive quadratic approximation (SQA) methods, are widely used
for their superlinear convergence in terms of iterations. However, unlike the
counter parts in smooth optimization, they suffer from lengthy running time in
solving regularized subproblems because even approximate solutions cannot be
computed easily, so their empirical time cost is not as impressive. In this
work, we first show that for partly smooth regularizers, although general
inexact solutions cannot identify the active manifold that makes the objective
function smooth, approximate solutions generated by commonly-used subproblem
solvers will identify this manifold, even with arbitrarily low solution
precision. We then utilize this property to propose an improved SQA method,
ISQA+, that switches to efficient smooth optimization methods after this
manifold is identified. We show that for a wide class of degenerate solutions,
ISQA+ possesses superlinear convergence not just only in iterations, but also
in running time because the cost per iteration is bounded. In particular, our
superlinear convergence result holds on problems satisfying a sharpness
condition more general than that in existing literature. Experiments on real-
world problems also confirm that ISQA+ greatly improves the state of the art
for regularized optimization.

###### Keywords:

Variable metric Manifold identification Regularized optimization Inexact
method Superlinear convergence

###### MSC:

49M15 90C55 49K40 90C31 90C55 65K05

##  1 Introduction

Consider the following regularized optimization problem:

$\min_{x\in\mathcal{E}}\quad F(x)\coloneqq f(x)+\Psi(x),$ (1)

where $\mathcal{E}$ is a Euclidean space with an inner product
$\langle\cdot,\,\cdot\rangle$ and its induced norm ${\left\|{\cdot}\right\|}$,
the regularizer $\Psi$ is extended-valued, convex, proper, and lower-
semicontinuous, $f$ is continuously differentiable with Lipschitz-continuous
gradients, and the solution set $\Omega$ is non-empty. This type of problems
is ubiquitous in applications such as machine learning and signal processing
(see, for example, Tibshirani (1996); Candès and Recht (2009); Candès et al
(2006)). One widely-used method for Eq. 1 is inexact successive quadratic
approximation (ISQA). At the $t$th iteration with iterate $x^{t}$, ISQA
obtains the update direction $p^{t}$ by approximately solving

$\displaystyle p^{t}\approx\operatorname*{\arg\,min}_{p\in\mathcal{E}}\quad
Q_{H_{t}}\left(p;x^{t}\right),$ (2) $\displaystyle
Q_{H_{t}}\left(p;x^{t}\right)\coloneqq\langle\nabla
f\left(x^{t}\right),\,p\rangle+\frac{1}{2}\langle
p,\,H_{t}p\rangle+\Psi\left(x^{t}+p\right)-\Psi\left(x^{t}\right),$ (3)

where $H_{t}$ is a self-adjoint positive-semidefinite linear endomorphism of
$\mathcal{E}$. The iterate is then updated along $p^{t}$ with a step size
$\alpha_{t}>0$.

ISQA is among the most efficient for Eq. 1. Its variants differ in the choice
of $H_{t}$ and $\alpha_{t}$, and how accurately Eq. 2 is solved. In this
class, proximal Newton (PN) (Lee et al, 2014; Li et al, 2017) and proximal
quasi-Newton (PQN) (Scheinberg and Tang, 2016) are popular for their fast
convergence in iterations. Regrettably, their subproblem has no closed-form
solution as $H_{t}$ is non-diagonal, so one needs to use an iterative solver
for Eq. 2 and the running time to reach the accuracy requirement can hence be
lengthy. For example, to attain the same superlinear convergence as truncated
Newton for smooth optimization, PN that takes $H_{t}=\nabla^{2}f$ requires
increasing accuracies for the subproblem solution, implying a growing and
unbounded number of inner iterations of the subproblem solver. Its superlinear
convergence thus gives little practical advantage in running time. On the
contrary, in smooth optimization, one can solve Eq. 2 with a bounded cost by
either conjugate gradient (CG) or matrix factorizations since $\Psi\equiv 0$.
The advantage of second-order methods over the first-order ones in regularized
optimization is therefore not as significant as that in smooth optimization.

A possible remedy when $\Psi$ is partly smooth (Lewis, 2002) is to switch to
smooth optimization after identifying an active manifold $\mathcal{M}$ that
contains a solution $\hat{x}$ to Eq. 1 and makes $\Psi$ confined to it smooth.
We say an algorithm can identify $\mathcal{M}$ if there is a neighborhood $U$
of $\hat{x}$ such that $x^{t}\in U$ implies $x^{t+1}\in\mathcal{M}$, and call
it possesses the manifold identification property. Unfortunately, for ISQA,
this property in general only holds when Eq. 2 is always solved exactly.
Indeed, even if each $p^{t}$ is arbitrarily close to the corresponding exact
solution, it is possible that no iterate lies in the active manifold, as shown
below.

###### Example 1

Consider the following simple example of Eq. 1 with
$\Psi(\cdot)=\|\cdot\|_{1}$:

$\min_{x\in\mathbb{R}^{2}}\,(x_{1}-2.5)^{2}+(x_{2}-0.3)^{2}+\|x\|_{1},$

whose only solution is ${\hat{x}}=(2,0)$, and $\|x\|_{1}$ is smooth relative
to $\mathcal{M}=\\{x\mid x_{2}=0\\}$ around ${\hat{x}}$. Consider
$\\{x^{t}\\}$ with $x^{t}_{1}=2+f(t),x^{t}_{2}=f(t)$, for some $f(t)>0$ with
$f(t)\downarrow 0$, and let $H_{t}\equiv I,\alpha_{t}\equiv 1$, and
$p^{t}=x^{t+1}-x^{t}$. The optimum of Eq. 2 is $p^{t*}={\hat{x}}-x^{t}$, so
$\|x^{t}-{\hat{x}}\|=O(f(t))$ and $\|p^{t}-p^{t*}\|=O(f(t))$. As $f$ is
arbitrary, both the subproblem inexact solution and its corresponding
objective converge to the optimum arbitrarily fast, but
$x^{t}\notin\mathcal{M}$ for all $t$. ∎

Moreover, some versions of inexact PN generalize the stopping condition of CG
for truncated Newton to require $\|r^{t}\|\rightarrow 0$, where

$r^{t}\coloneqq\operatorname*{\arg\,min}_{r}\|r\|,\quad\text{ subject to
}\quad r\in\partial_{p}Q_{H_{t}}(p^{t};x^{t}),$ (4)

but Example 1 gives a sequence of $\\{\|r^{t}\|\\}$ converging to $1$, hinting
that such a condition might have an implicit relation with manifold
identification.

Interestingly, in our numerical experience in Lee and Wright (2019); Lee et al
(2019); Li et al (2020), ISQA with approximate subproblem solutions, even
without an increasing solution precision and on problems that are not strongly
convex, often identifies the active manifold rapidly. We thus aim to provide
theoretical support for such a phenomenon and utilize it to devise more
efficient and practical methods that trace the superior performance of second-
order methods in smooth optimization.

In this work, we show that ISQA essentially possesses the manifold
identification property, by giving a sufficient condition for inexact
solutions of Eq. 2 in ISQA to identify the active manifold that is satisfied
by the output of most of the widely-used subproblem solvers even if Eq. 2 is
solved arbitrarily roughly. We also show that
${\left\|{r^{t}}\right\|}\downarrow 0$ is indeed sufficient for manifold
identification, so PN can achieve superlinear convergence in a more efficient
way through this property. When the iterates do not lie in a compact set, it
is possible that the iterates do not converge, in which case even algorithms
possessing the manifold identification property might fail to identify the
active manifold because the iterates never enter a neighborhood that enables
the identification. Therefore, we also show convergence of the iterates even
when $F$ is not coercive, under a sharpness condition widely-seen in real-
world problems that generalizes the quadratic growth condition and the weak
sharp minima. Based on these results, we propose an improved, practical
algorithm ISQA+ that switches to smooth optimization after the active manifold
is presumably identified. We show that ISQA+ is thus superior to existing PN-
type methods as it possesses the same superlinear and even quadratic rates in
iterations but has an upper-bounded cost per iteration. ISQA+ hence also
converges superlinearly in running time, which, to our best knowledge, is the
first of the kind. Our analysis is more general than existing ones in
guaranteeing superlinear convergence in a broader class of degenerate
problems. Numerical results also confirm ISQA+’s much improved efficiency over
PN and PQN.

###  1.1 Related Work

ISQA for Eq. 1 or the special case of constrained optimization has been well-
studied, and we refer the readers to Lee and Wright (2019) for a detailed
review of related methods. We mention here in particular the works Lee et al
(2014); Byrd et al (2016); Li et al (2017); Yue et al (2019) that provided
superlinear convergence results. Lee et al (2014) first analyzed the
superlinear convergence of PN and PQN. Their analysis considers only strongly
convex $f$, so both the convergence of the iterate and the positive-
definiteness of the Hessian are guaranteed. Their inexact version requires
$\|r^{t}\|\downarrow 0$, which might not happen when the solutions to Eq. 2
are only approximate, as illustrated in Example 1. With the same requirement
for $\|r^{t}\|$ as Lee et al (2014), Li et al (2017) showed that superlinear
convergence for inexact PN can be achieved when $f$ is self-concordant. Byrd
et al (2016) focused on $\Psi(\cdot)=\|\cdot\|_{1}$ and showed superlinear
convergence of PN under the subproblem stopping condition Eq. 10 defined in
Section 2, which is achievable as long as $p^{t}$ is close enough to the
optimum of Eq. 2. To cope with degenerate cases in which the Hessian is only
positive semidefinite, Yue et al (2019) used the stopping condition of Byrd et
al (2016) to propose a damping PN for general $\Psi$ and showed that its
iterates converge and achieve superlinear convergence under convexity and the
error-bound (EB) condition (Luo and Tseng, 1992) even if $F$ is not coercive.
A common drawback of Lee et al (2014); Byrd et al (2016); Li et al (2017); Yue
et al (2019) is that they all require increasing precisions in the subproblem
solve, so the superlinear rate is observed only in iterations but not in
running time in their experiments. In contrast, by switching to smooth
optimization after identifying the active manifold, ISQA+ achieves superlinear
convergence not only in iterations but also in time, and is thus much more
efficient in practice. Our superlinear convergence result also allows a
broader range of degeneracy than that in Yue et al (2019).

Although ISQA is intensively studied, its ability for manifold identification
is barely discussed because this does not in general hold, as noted in Example
1. Hare (2011) showed that ISQA identifies the active manifold under the
impractical assumptions that Eq. 2 is always solved exactly and the iterates
converge, and his analysis cannot be extended to inexact versions. Our
observation in Lee and Wright (2019); Lee et al (2019); Li et al (2020) that
ISQA identifies the active manifold empirically motivated this work to provide
theoretical guarantees for this phenomenon.

Manifold identification requires the iterates, or at least a subsequence, to
converge to a point of partial smoothness. In most existing analyses for Eq.
1, iterate convergence is proven under either: (i) $f$ is convex and the
algorithm is a first-order one, (ii) $F$ is strongly convex, or (iii) the
iterates lie in a compact set. Analyses for the first scenario rely on the
implicit regularization of first-order methods such that their iterates lie in
a bounded region (Liang et al, 2017), but this is not applicable to ISQA.
Under the second condition, convergence of the objective directly implies that
of the iterates. For the third case, the compact set assumption is usually
achieved by assuming that the algorithm is a descent one and $\Omega$ and thus
all level sets are compact, which in a Euclidean space is equivalent to that
$F$ is coercive. Convergence of the full iterate sequence is then usually
proven under the Kurdyka-Łojasiewicz (KL) condition, as done in Chouzenoux et
al (2014); Bonettini et al (2020); Attouch et al (2010). Note that strong
convexity of $F$ in the second scenario also implies its coerciveness. Since
manifold identification only requires a convergent subsequence, coerciveness
of $F$ alone without the KL condition or strong convexity suffices. However,
it is too strong a condition because it excludes the case of an unbounded
$\Omega$. The only exception is Yue et al (2019) that shows the convergence of
the iterates for their specific algorithm under EB and convexity of $f$. Our
analysis for iterate convergence is more general in covering a much broader
algorithmic framework and requiring only a general sharpness condition that
contains both EB and the weak-sharp minima (Burke and Ferris, 1993) as special
cases.

Our design of the two-stage ISQA+ is inspired by Lee and Wright (2012); Li et
al (2020) in conjecturing that the active manifold is identified after the
current manifold remains unchanged, but the design of the first stage is quite
different and we also add in additional safeguards in the second stage. Lee
and Wright (2012) used dual averaging in the first stage for optimizing the
expected value of an objective function involving random variables, so their
algorithm is more suitable for stochastic settings. Li et al (2020) focused on
distributed optimization and their usage of manifold identification is for
reducing the communication cost.

###  1.2 Outline

This work is outlined as follows. In Section 2, we describe the algorithmic
framework and give preliminary properties. Technical results in Section 3
prove the manifold identification property of ISQA and the convergence of the
iterates. We then describe the proposed ISQA+ and show its superlinear
convergence in running time in Section 4. The effectiveness of ISQA+ is then
illustrated through extensive numerical experiments in Section 5. Section 6
finally concludes this work. Our implementation of the described algorithms is
available at https://www.github.com/leepei/ISQA_plus/.

##  2 Preliminaries

We denote the minimum of Eq. 1 by $F^{*}$; the domain of $\Psi$ by
$\text{dom}(\Psi)$; and the set of convex, proper, and lower semicontinuous
functions by $\Gamma_{0}$. For any set $C$, $\mbox{\rm relint}(C)$ denotes its
relative interior. We will frequently use the following notations.

$\delta_{t}\coloneqq F(x^{t})-F^{*},\quad
P_{\Omega}(x)\coloneqq\operatorname*{\arg\,min}_{y\in\Omega}\|x-y\|,\quad\mbox{\rm
dist}(x,\Omega)\coloneqq\|x-P_{\Omega}(x)\|.$

The level set $\text{Lev}\left({\xi}\right)\coloneqq\left\\{x\mid
F(x)-F^{*}\leq\xi\right\\}$ for any $\xi\geq 0$ is closed but not necessarily
bounded. A function is $L$-smooth if it is differentiable with the gradient
$L$-Lipschitz continuous. We denote the identity operator by $I$. For self-
adjoint linear endomorphisms $A,B$ of $\mathcal{E}$, $A\succ B$ ($\succeq$)
means $A-B$ is positive definite (positive semidefinite). We abbreviate
$A\succ\tau I$ to $A\succ\tau$ for $\tau\in\mathbb{R}$. The set of $A$ with
$A\succ 0$ ($\succeq$) is denoted by $\SS$ (${\mathcal{S_{+}}}$). The
subdifferential $\partial\Psi(x)$ of $\Psi$ at $x$ is well-defined as
$\Psi\in\Gamma_{0}$, hence so does the generalized gradient $\partial
F(x)=\nabla f(x)+\partial\Psi(x)$. For any $g\in\Gamma_{0}$, $\tau\geq 0$, and
$\Lambda\in{\mathcal{S_{+}}}$, the proximal mapping

$\mbox{\rm prox}^{\Lambda}_{\tau
g}(x)\coloneqq\operatorname*{\arg\,min}_{y\in\mathcal{E}}\,\frac{1}{2}\langle
x-y,\,\Lambda(x-y)\rangle+\tau g\left(y\right)$ (5)

is continuous and finite in $\mathcal{E}$ even outside $\text{dom}(g)$. When
$\Lambda=I$, Eq. 5 is shorten to $\mbox{\rm prox}_{\tau g}(x)$. For Eq. 2, we
denote its optimal solution by $p^{t*}$. When there is no ambiguity, we
abbreviate $Q_{H_{t}}(\cdot;x^{t})$ to $Q_{t}(\cdot)$, $Q_{t}(p^{t})$ to
$\hat{Q}_{t}$, and $Q_{t}(p^{t*})$ to $Q_{t}^{*}$.

###  2.1 Algorithmic Framework

We give out details in defining the ISQA framework by discussing the choice of
$H_{t}$, the subproblem solver and its stopping condition, and how sufficient
objective decrease is ensured. We consider the algorithm a two-level loop
procedure, where the outer loop updates the iterate $x^{t}$ and the iterations
of the subproblem solver form the inner loop.

After obtaining $p^{t}$ from Eq. 2, we need to find a step size $\alpha_{t}>0$
for it to ensure a sufficient objective decrease. Given
$\gamma,\beta\in(0,1)$, we take $\alpha_{t}$ as the largest value in
$\\{\beta^{0},\beta^{1},\dotsc\\}$ satisfying an Armijo-like condition.

$F\left(x^{t}+\alpha_{t}p^{t}\right)\leq
F\left(x^{t}\right)+\gamma\alpha_{t}Q_{t}(p^{t}).$ (6)

This condition is satisfied by all $\alpha_{t}$ small enough as long as
$Q_{t}(p^{t})<0$ and $Q_{t}(\cdot)$ is strongly convex; see (Lee and Wright,
2019, Lemma 3).

For the choice of $H_{t}$, we only make the following blanket assumption
without further specification to make our analysis more general.

$\exists M,m>0,\quad\text{ such that }\quad M\succeq H_{t}\succeq m,\;\forall
t\geq 0.$ (7)

For Eq. 2, any suitable solver for regularized optimization, such as proximal
gradient, (variance-reduced) stochastic gradient methods, and their variants,
can be used, and the following are common for their inner loop termination:

$\displaystyle\hat{Q}_{t}-Q_{t}^{*}\leq\epsilon_{t},$ (8)
$\displaystyle\left\|r^{t}\right\|\leq\epsilon_{t},\quad\text{ or }$ (9)
$\displaystyle
G^{\tau}_{H_{t}}\left(p^{t};x^{t}\right)\coloneqq{\left\|{p^{t}-\bar{p}^{t}_{\tau}}\right\|}\leq\epsilon_{t},$
(10)

for some given $\epsilon_{t}\geq 0$ and $\tau>0$, where

$\displaystyle\bar{p}^{t}_{\tau}$ $\displaystyle\coloneqq\mbox{\rm
prox}_{\tau\Psi}\left(\left(x^{t}+p^{t}\right)-\tau\left(\nabla
f(x^{t})+H_{t}p^{t}\right)\right)-x^{t}.$ (11)

The point $\bar{p}^{t}_{\tau}$ in Eq. 11 is computed by taking a proximal
gradient step of the subproblem Eq. 2 from $p^{t}$, and thus
$\bar{p}^{t}-p^{t}$ is the norm of the proximal gradient (with step size
$\tau$) of $Q_{t}$ at $p^{t}$. Because the subproblem is strongly convex, the
norm of the proximal gradient is zero if and only if $p^{t}$ is the unique
solution to the subproblem. We will see in the next subsection that the norm
of this proximal gradient squared is also equivalent to the objective distance
to the optimum of the subproblem. We summarize this framework in Algorithm 1.

input : $x^{0}\in\mathcal{E}$, $\gamma,\beta\in(0,1)$

for  _$t=0,1,\dotsc$_ do

$\alpha_{t}\leftarrow 1$, pick $\epsilon_{t}\geq 0$ and $H_{t}$, and solve Eq.
2 for $p^{t}$ satisfying Eq. 8, Eq. 9, or Eq. 10

while  _Eq. 6 is not satisfied_ do $\alpha_{t}\leftarrow\beta\alpha_{t}$

$x^{t+1}\leftarrow x^{t}+\alpha_{t}p^{t}$

Algorithm 1 A Framework of ISQA for Eq. 1

###  2.2 Basic Properties

Under Eq. 7, Eq. 3 is $m$-strongly convex with respect to $p$, so the
following standard results hold for any $\tau\in(0,1/M]$ and any
$p^{t}\in\mathcal{E}$ (Nesterov, 2018; Drusvyatskiy and Lewis, 2018).

$\displaystyle\|r^{t}\|^{2}\geq
2m\left(Q_{t}(p^{t})-Q_{t}^{*}\right)\geq\frac{m}{M}G^{\tau}_{H_{t}}\left(p^{t};x^{t}\right)^{2},$
(12) $\displaystyle
G^{\tau}_{H_{t}}\left(p^{t};x^{t}\right)^{2}\geq\tau\left(\frac{(2m^{-1}+\tau)(1+M\tau)}{\tau}-\frac{1}{2}\right)^{-1}\left(Q_{t}\left(\bar{p}^{t}_{\tau}\right)-Q_{t}^{*}\right).$
(13)

Therefore, Eq. 10 and Eq. 8 are almost equivalent and implied by Eq. 9, while
Example 1 has shown that Eq. 9 is a stronger condition not implied by Eq. 8.
Although Eq. 13 does not show that Eq. 10 directly implies Eq. 8, once Eq. 10
is satisfied, we can use it to find $\bar{p}^{t}_{\tau}$ satisfying Eq. 8 from
$p^{t}$.

A central focus of this work is manifold identification, so we first formally
define manifolds following Vaisman (1984). A set
$\mathcal{M}\in\mathbb{R}^{m}$ is a $p$-dimensional $\mathcal{C}^{k}$ manifold
around $x\in\mathbb{R}^{m}$ if there is a $\mathcal{C}^{k}$ function
$\Phi:\mathbb{R}^{m}\rightarrow\mathbb{R}^{m-p}$ whose derivative at $x$ is
surjective such that for $y$ close enough to $x$, $y\in\mathcal{M}$ if and
only if $\Phi(y)=0$. Through the implicit function theorem, we can also use a
$\mathcal{C}^{k}$ parameterization
$\phi:\mathbb{R}^{p}\rightarrow\mathcal{M}$, with $\phi(y)=x$ and the
derivative injective at $y$, to describe a neighborhood of $x$ on
$\mathcal{M}$. Now we are ready for the definition of partial smoothness
(Lewis, 2002) that we assume for the regularizer when discussing manifold
identification.

######  Definition 1 (Partly smooth)

A function $\Psi$ is partly smooth at a point $x^{*}$ relative to a set
$\mathcal{M}$ containing $x^{*}$ if $\partial\Psi(x^{*})\neq\emptyset$ and:

  1. 1.

Around $x^{*}$, $\mathcal{M}$ is a $\mathcal{C}^{2}$-manifold and
$\Psi|_{\mathcal{M}}$ is $\mathcal{C}^{2}$.

  2. 2.

The affine span of $\partial\Psi(x)$ is a translate of the normal space to
$\mathcal{M}$ at $x^{*}$.

  3. 3.

$\partial\Psi$ is continuous at $x^{*}$ relative to $\mathcal{M}$.

  4. 4.

$\Psi$ is regular at all points $x\in\mathcal{M}$ with
$\partial\Psi(x)\neq\emptyset$ around $x^{*}$.

Intuitively, it means $\Psi$ is smooth around $x^{*}$ in $\mathcal{M}$ but
changes drastically along directions leaving the manifold. We also call this
$\mathcal{M}$ the active manifold. Note that any convex function $\Psi$ is
regular with nonempty subdifferential everywhere in its domain.

As the original identification results in (Hare and Lewis, 2004, Theorem 5.3)
and (Lewis and Zhang, 2013, Theorem 4.10) require the sum $F$ to be partly
smooth but our setting does not require so for $f$, we first provide a result
relaxing the conditions to ensure identification in our scenario.

###### Lemma 1

Consider Eq. 1 with $f\in\mathcal{C}^{1}$ and $\Psi$ partly smooth at a point
$x^{*}$ relative to a $\mathcal{C}^{2}$-manifold $\mathcal{M}$. If $\Psi$ is
prox-regular at $x^{*}$, the nondegenerate condition

$0\in\mbox{\rm relint}\left(\partial F(x^{*})\right)=\nabla f(x^{*})+\mbox{\rm
relint}\left(\partial\Psi(x^{*})\right)$ (14)

holds, and there is a sequence $\\{x^{t}\\}$ converging to $x^{*}$ with
$F(x^{t})\rightarrow F(x^{*})$, then

$\mbox{\rm dist}\left(0,\partial F(x^{t})\right)\rightarrow
0\quad\Leftrightarrow\quad x^{t}\in\mathcal{M}\text{ for all t large}.$

###### Proof

We first observe that as $f\in\mathcal{C}^{1}$, $x^{t}\rightarrow x^{*}$
implies $f(x^{t})\rightarrow f(x^{*})$, whose combination with
$F(x^{t})\rightarrow F(x^{*})$ further implies
$\Psi(x^{t})\rightarrow\Psi(x^{*})$. Therefore, the premises of (Lewis and
Zhang, 2013, Theorem 4.10) on $\Psi$ are satisfied. We then note that

$\mbox{\rm dist}\left(0,\partial F(x^{t})\right)\rightarrow
0\quad\Leftrightarrow\quad\mbox{\rm dist}\left(-\nabla f(x^{t}),\partial
f(x^{t})\right)\rightarrow 0.$ (15)

Again from that $f\in\mathcal{C}^{1}$, $x^{k}\rightarrow x^{*}$ implies
$\nabla f(x^{k})\rightarrow\nabla f(x^{*})$, so by Eq. 14, Eq. 15 is further
equivalent to

$\mbox{\rm dist}\left(-\nabla f(x^{*}),\partial\Psi(x^{t})\right)\rightarrow
0,$

which is the necessary and sufficient condition for $x^{t}\in\mathcal{M}$ for
all $t$ large in (Lewis and Zhang, 2013, Theorem 4.10) because Eq. 14
indicates that $-\nabla f(x^{*})\in\mbox{\rm relint}(\partial\Psi(x^{*}))$. We
then apply that theorem to obtain the desired result. ∎

Using Lemma 1, We further state an identification result for Eq. 1 under our
setting without the need to check whether $\\{F(x^{t})\\}$ converges to
$F(x^{*})$. This will be useful in our later theoretical development.

###### Lemma 2

Consider Eq. 1 with $f\in\mathcal{C}^{1}$ and $\Psi\in\Gamma_{0}$. If $\Psi$
is partly smooth relative to a manifold $\mathcal{M}$ at a point $x^{*}$
satisfying Eq. 14, and there is a sequence $\\{x^{t}\\}$ converging to
$x^{*}$, then we have

$\mbox{\rm dist}\left(0,\partial F(x^{t})\right)\rightarrow
0\quad\Rightarrow\quad x^{t}\in\mathcal{M}\text{ for all t large}.$

###### Proof

First, since $\Psi$ is convex, it is prox-regular in its domain. Next, as
$\Psi\in\Gamma_{0}$, it is subdifferentially continuous at
$x^{*}\in\text{dom}(\Psi)$ by (Rockafellar and Wets, 2009, Example 13.30).
Thus, $\mbox{\rm dist}(0,\partial F(x^{t}))\rightarrow 0\in\partial F(x^{*})$
and $x^{t}\rightarrow x^{*}$ imply that $F(x^{t})\rightarrow F(x^{*})$. The
desired result is then obtained by applying Lemma 1. ∎

We note that the requirement of the above two lemmas is partial smoothness of
$\Psi$, instead of $F$, at $x^{*}$. Therefore, it is possible that
$F\mid_{\mathcal{M}}$ is not $\mathcal{C}^{2}$, as we only require
$\Psi\mid_{\mathcal{M}}\in\mathcal{C}^{2}$ and $f$ being $L$-smooth.

##  3 Manifold Identification of ISQA

Our first major result is the manifold identification property of Algorithm 1.
We start with showing that the strong condition Eq. 9 with
$\epsilon_{t}\downarrow 0$ is sufficient.

###### Theorem 3.1

Consider a point $x^{*}$ satisfying Eq. 14 with $\Psi\in\Gamma_{0}$ partly
smooth at $x^{*}$ relative to some manifold $\mathcal{M}$. Assume $f$ is
locally $L$-smooth for $L>0$ around $x^{*}$. If Algorithm 1 is run with the
condition Eq. 9 and Eq. 7 holds, then there exist $\epsilon,\delta>0$ such
that $\|{x^{t}}-x^{*}\|\leq\delta,\epsilon_{t}\leq\epsilon$, and
$\alpha_{t}=1$ imply $x^{t+1}\in\mathcal{M}$.

###### Proof

Since each iteration of Algorithm 1 is independent of the previous ones, we
abuse the notation to let $x^{t}$ be the input of Algorithm 1 at the $t$th
iteration and $p^{t}$ the corresponding inexact solution to Eq. 2, but
$x^{t+1}$ is irrelevant to $p^{t}$ or $\alpha_{t}$. Assume for contradiction
the statement is false. Then there exist a sequence
$\\{x^{t}\\}\subset\mathcal{E}$ converging to $x^{*}$, a nonnegative sequence
$\\{\epsilon_{t}\\}$ converging to $0$, a sequence $\\{H_{t}\\}\subset\SS$
satisfying Eq. 7, and a sequence $\\{p^{t}\\}\subset\mathcal{E}$ such that
$Q_{H_{t}}(p^{t};x^{t})$ in Eq. 3 satisfies Eq. 9 for all $t$, yet
$x^{t}+p^{t}\notin\mathcal{M}$ for all $t$. From Eq. 4,

$r^{t}-\nabla
f\left(x^{t}\right)-H_{t}p^{t}\in\partial\Psi\left(x^{t}+p^{t}\right),\quad\forall
t\geq 0.$ (16)

Therefore, we get from Eq. 16 that

$\displaystyle\mbox{\rm dist}\left(0,\partial
F\left(x^{t}+p^{t}\right)\right)$ $\displaystyle=\mbox{\rm dist}\left(-\nabla
f\left(x^{t}+p^{t}\right),\partial\Psi\left(x^{t}+p^{t}\right)\right)$
$\displaystyle\leq{\left\|{-\nabla
f\left(x^{t}+p^{t}\right)-\left(r^{t}-\nabla
f\left(x^{t}\right)-H_{t}p^{t}\right)}\right\|}$
$\displaystyle\leq{\left\|{\nabla f\left(x^{t}+p^{t}\right)-\nabla
f\left(x^{t}\right)}\right\|}+{\left\|{r^{t}}\right\|}+{\left\|{H_{t}}\right\|}{\left\|{p^{t}}\right\|}$
$\displaystyle\leq\left(L+M\right){\left\|{p^{t}}\right\|}+{\left\|{r^{t}}\right\|}.$
(17)

From Eq. 7 and the convexity of $\Psi$, $Q_{H_{t}}(\cdot;x^{t})$ is
$m$-strongly convex, which implies

$Q_{H_{t}}\left(p;x^{t}\right)-Q_{H_{t}}\left(p^{t*};x^{t}\right)\geq\frac{m}{2}{\left\|{p-p^{t*}}\right\|}^{2},\quad\forall
p\in\mathcal{E}.$ (18)

Combining Eq. 18 and Eq. 12 shows that

$m^{-1}\|r^{t}\|+\|p^{t*}\|\geq\|p^{t}\|.$ (19)

Since $\\{x^{t}\\}$ converges to $x^{*}$, by the argument in (Wright, 2012,
Lemma 3.2), we get

$p^{t*}=O(\|x^{t}-x^{*}\|)$ (20)

whenever $x^{t}$ is close enough to $x^{*}$. Thus Eq. 19, Eq. 20, Eq. 9, and
that $\epsilon_{t}\downarrow 0$ imply

$\lim_{t\rightarrow\infty}\|p^{t}\|=0,$ (21)

Substituting Eq. 9 and Eq. 21 into Eq. 17 gives $\mbox{\rm dist}(0,\partial
F(x^{t}))\rightarrow 0$, and by Eq. 21 we also get $x^{t}+p^{t}\rightarrow
x^{*}+0=x^{*}$. Therefore Lemma 2 implies that $x^{t}+p^{t}\in\mathcal{M}$ for
all $t$ large enough, proving the desired contradiction. ∎

Theorem 3.1 shows that if a variant of PN or PQN needs $\|r^{t}\|\downarrow 0$
to achieve superlinear convergence, $\mathcal{M}$ will be identified in the
middle, so one can reduce the running time by switching to smooth optimization
that can be conducted more efficiently while possessing the same superlinear
convergence. Moreover, although Theorem 3.1 shows that Eq. 9 is sufficient for
identifying the active manifold, it might never be satisfied as Example 1
showed. We therefore provide another sufficient condition for ISQA to identify
the active manifold that is satisfied by most of the widely-used solvers for
Eq. 2, showing that ISQA essentially possesses the manifold identification
property. This result uses the condition Eq. 8, which is weaker than Eq. 4,
and we follow Lee and Wright (2019) to define $\\{\epsilon_{t}\\}$ using a
given $\eta\in[0,1)$:

$\epsilon_{t}=\eta\left(Q_{t}(0)-Q_{t}^{*}\right)=-\eta Q_{t}^{*}.$ (22)

As argued in Lee and Wright (2019) and practically adopted in various
implementations including Lee and Chang (2020); Dünner et al (2018); Lee et al
(2019), it is easy to ensure that Eq. 8 with Eq. 22 holds for some $\eta<1$
under Eq. 7 (although the explicit value might be unknown) if we apply a
linear-convergent subproblem solver with at least a pre-specified number of
iterations to Eq. 2.

###### Theorem 3.2

Consider the setting of Theorem 3.1. If Algorithm 1 is run with Eq. 8 and Eq.
22 for some $\eta\in[0,1)$, Eq. 7 holds, and the update direction $p^{t}$
satisfies

$x^{t}+p^{t}=\mbox{\rm
prox}^{\Lambda_{t}}_{\Psi}\left(y^{t}-\Lambda_{t}^{-1}\left(\nabla
f\left(x^{t}\right)+H_{t}\left(y^{t}-x^{t}\right)+s^{t}\right)\right),$ (23)

where $s^{t}$ satisfies $\|s^{t}\|\leq
R\left({\left\|{y^{t}-(x^{t}+p^{t*})}\right\|}\right)$ for some
$R:[0,\infty)\rightarrow[0,\infty)$ continuous in its domain with $R(0)=0$,
$\Lambda_{t}\in\SS$ with $M_{1}\succeq\Lambda_{t}$ for $M_{1}>0$, and $y^{t}$
satisfies

$\displaystyle{\left\|{\left(y^{t}-x^{t}\right)-p^{t*}}\right\|}$
$\displaystyle\leq\eta_{1}\left(Q_{t}(0)-Q_{t}^{*}\right)^{\nu}$ (24)

for some $\nu>0$ and $\eta_{1}\geq 0$, then there exists $\epsilon,\delta>0$
such that $\|x^{t}-x^{*}\|\leq\epsilon,|Q_{t}^{*}|\leq\delta$, and
$\alpha_{t}=1$ imply $x^{t+1}\in\mathcal{M}$.

###### Proof

Suppose the statement is not true for contradiction. Then there exist a
continuous function $R:[0,\infty)\rightarrow[0,\infty)$ with $R(0)=0$,
$\eta_{1}\geq 0$, $M_{1}>0$, a sequence $\\{x^{t}\\}\subset\mathcal{E}$
converging to $x^{*}$, a sequence $\\{H_{t}\\}\subset\SS$ satisfying Eq. 7 and

$\lim_{t\rightarrow\infty}\,\min_{p}\quad Q_{H_{t}}\left(p;x^{t}\right)=0,$
(25)

three sequences $\\{p^{t}\\},\\{y^{t}\\},\\{s^{t}\\}\subset\mathcal{E}$ and a
sequence $\\{\Lambda_{t}\\}\subset\SS$ with $M_{1}\succeq\Lambda_{t}$ such
that Eq. 8 with Eq. 22 and Eq. 23-Eq. 24 hold, yet
$x^{t}+p^{t}\notin\mathcal{M}$ for all $t$. We abuse the notation to let
$p^{t*}$ and $Q^{*}_{t}$ respectively denote the optimal solution and
objective value for $\min_{p}Q_{H_{t}}(p;x^{t})$, but $x^{t+1}$ is irrelevant
to $p^{t}$ or $\alpha_{t}$.

The optimality condition of Eq. 5 applied to Eq. 23 indicates that

$-\Lambda_{t}\left(x^{t}-y^{t}\right)-\left(\nabla
f\left(x^{t}\right)+H_{t}\left(y^{t}-x^{t}\right)+s^{t}\right)\in\partial\Psi\left(x^{t}+p^{t}\right).$
(26)

Thus, we have

$\displaystyle~{}\mbox{\rm dist}\left(0,\partial
F\left(x^{t}+p^{t}\right)\right)$ $\displaystyle\leq$
$\displaystyle~{}\left\|\nabla
f\left(x^{t}+p^{t}\right)-\Lambda_{t}\left(x^{t}+p^{t}-y^{t}\right)-\nabla
f\left(x^{t}\right)\right.\left.-H_{t}\left(y^{t}-x^{t}\right)-s^{t}\right\|$
$\displaystyle\leq$ $\displaystyle~{}{\left\|{\nabla
f\left(x^{t}+p^{t}\right)-\nabla
f\left(x^{t}\right)}\right\|}+M_{1}\left({\left\|{x^{t}-y^{t}}\right\|}+{\left\|{p^{t}}\right\|}\right)+M{\left\|{y^{t}-x^{t}}\right\|}+{\left\|{s^{t}}\right\|}$
$\displaystyle\leq$
$\displaystyle~{}(L+M_{1}){\left\|{p^{t}}\right\|}+(M+M_{1}){\left\|{y^{t}-x^{t}}\right\|}+{\left\|{s^{t}}\right\|}.$
(27)

For the first two terms in Eq. 27, the triangle inequality and Eq. 18 imply

$\displaystyle\begin{aligned}
{\left\|{p^{t}}\right\|}\leq{\left\|{p^{t}-p^{t*}}\right\|}+{\left\|{p^{t*}}\right\|}\leq&~{}\sqrt{2m^{-1}}\sqrt{Q_{t}\left(p^{t}\right)-Q^{*}_{t}}+\sqrt{2m^{-1}}\sqrt{0-Q^{*}_{t}}\\\
\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:multiplicative}}}{{\leq}}&~{}\left(\sqrt{\eta}+1\right)\sqrt{2m^{-1}}\sqrt{-Q^{*}_{t}},\text{
and }\end{aligned}$ (28)
$\displaystyle{\left\|{y^{t}-x^{t}}\right\|}\leq{\left\|{\left(y^{t}-x^{t}\right)-p^{t*}}\right\|}+{\left\|{p^{t*}}\right\|}\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:bdd0}}}{{\leq}}\eta_{1}\left(-Q^{*}_{t}\right)^{\nu}+\sqrt{2m^{-1}}\sqrt{-Q^{*}_{t}}.$
(29)

For the last term in Eq. 27, we have from our definition of $s^{t}$ that

$\displaystyle{\left\|{s^{t}}\right\|}$ $\displaystyle\leq
R\left({\left\|{y^{t}-\left(x^{t}+p^{t*}\right)}\right\|}\right).$ (30)

By substituting Eq. 28-Eq. 30 back into Eq. 27, clearly there are
$C_{1},C_{2}>0$ such that

$\mbox{\rm dist}\left(0,\partial F\left(x^{t}+p^{t}\right)\right)\leq
C_{1}\sqrt{-Q^{*}_{t}}+C_{2}\left(-Q^{*}_{t}\right)^{\nu}{+R\left({\left\|{y^{t}-\left(x^{t}+p^{t*}\right)}\right\|}\right).}$
(31)

Note that $Q_{H_{t}}(0;x^{t})\equiv 0$, so $-Q^{*}_{t}\geq 0$ from its
optimality and the right-hand side of Eq. 31 is well-defined. Next, we see
from Eq. 25, Eq. 24, and the continuity of $R$ that

$\lim_{t\rightarrow\infty}{\left\|{\left(y^{t}-x^{t}\right)-p^{t*}}\right\|}=0,\quad\Rightarrow\quad\lim_{t\rightarrow\infty}R\left({\left\|{\left(y^{t}-x^{t}\right)-p^{t*}}\right\|}\right)=0.$
(32)

Applying Eq. 25 and Eq. 32 to Eq. 31 and letting $t$ approach infinity then
yield

$\lim_{t\rightarrow\infty}\mbox{\rm dist}\left(0,\partial
F\left(x^{t}+p^{t}\right)\right)=0.$ (33)

Next, from Eq. 28 and Eq. 25, it is also clear that
${\left\|{p^{t}}\right\|}\rightarrow 0$, so from the convergence of $x^{t}$ to
$x^{*}$ we have

$x^{t}+p^{t}\rightarrow x^{*}+0=x^{*}.$ (34)

Now Eq. 34 and Eq. 33 allow us to apply Lemma 2 so $x^{t}+p^{t}\in\mathcal{M}$
for all $t$ large enough, leading to the desired contradiction. ∎

The function $R$ can be seen as a general residual function and we just need
from it that $s^{t}$ approaches $0$ with
${\left\|{y^{t}-(x^{t}+p^{t*}}\right\|}$, and Theorem 3.2 can be used as long
as we can show that such an $R$ exists, even if the exact form is unknown.
Condition Eq. 24 is deliberately chosen to exclude the objective
$Q_{t}(y^{t}-x^{t})$ so that broader algorithmic choices like those with
$y^{t}\notin\text{dom}(\Psi)$ can be included.

One concern for Theorem 3.2 is the requirement of $|Q_{t}^{*}|\leq\delta$.
Fortunately, for Algorithm 1 with Eq. 8 and Eq. 22, if $\alpha_{t}$ are lower-
bounded by some $\bar{\alpha}>0$ (which is true under Eq. 7 by (Lee and
Wright, 2019, Corollary 1)) and $F$ is lower-bounded, then Eq. 6 together with
Eq. 8 and Eq. 22 shows that $-Q_{t}^{*}$ is summable and thus decreasing to
$0$.

We now provide several examples satisfying Eq. 23-Eq. 24 to demonstrate the
usefulness of Theorem 3.2. In our description below, $p^{t,i}$ denotes the
$i$th iterate of the subproblem solver at the $t$th outer iteration and
$x^{t,i}\coloneqq x^{t}+p^{t,i}$.

  * •

Using $x^{t+1}=x^{t}+\bar{p}^{t}_{\tau}$ from Eq. 11: Assume we have a
tentative $p^{t}$ that satisfies Eq. 10 for some $\hat{\epsilon}_{t}$, and we
use Eq. 11 to generate $\bar{p}^{t}_{\tau}$ as the output satisfying Eq. 8 for
a corresponding $\epsilon_{t}$ calculated by Eq. 13. We see that it is of the
form Eq. 23 with $s^{t}=0$, $y^{t}=x^{t}+p^{t}$, and $\Lambda_{t}=I/\tau$.
From Eq. 13 we know that Eq. 8 is satisfied, while (Drusvyatskiy and Lewis,
2018, Corollary 3.6) and Eq. 12 guarantees Eq. 24 with $\nu=1/2$.

  * •

Proximal gradient (PG): These methods generate the inner iterates by

$x^{t,0}=x^{t},\,x^{t,i+1}=\mbox{\rm
prox}^{\lambda_{t,i}I}_{\Psi}\left(x^{t,i}-\lambda_{t,i}^{-1}\left(\nabla
f\left(x^{t}\right)+H_{t}\left(x^{t,i}-x^{t}\right)\right)\right),\forall
i>0,$

for some $\\{\lambda_{t,i}\\}$ bounded in a positive range that guarantees
$\\{Q_{t}(p^{t,i})\\}_{i}$ is a decreasing sequence for all $t$ (decided
through pre-specification, line search, or other mechanisms). Therefore, for
any $t$, no matter what value of $i$ is the last inner iteration, Eq. 23 is
satisfied with $y^{t}=x^{t,i-1},s^{t}=0,\Lambda_{t,i}=\lambda_{t,i-1}I$. The
condition Eq. 22 holds for some $\eta<1$ because proximal-gradient-type
methods are a descent method with $Q$-linear convergence on strongly convex
problems, and Eq. 24 holds for $\eta_{1}\sqrt{2\eta/m}$ and $\nu=1/2$ from Eq.
18.

  * •

Accelerated proximal gradient (APG): The iterates are generated by

$\displaystyle\begin{cases}y^{t,1}&=x^{t,0}=x^{t},\\\
y^{t,i}&=x^{t,i-1}+\left(1-\frac{2}{\sqrt{\kappa(H_{t})}+1}\right)\left(x^{t,i-1}-x^{t,i-2}\right),\forall
i>1,\end{cases}$ (35) $\displaystyle x^{t,i}=\mbox{\rm
prox}^{{\left\|{H_{t}}\right\|}I}_{\Psi}\left(y^{t,i}-{\left\|{H_{t}}\right\|}^{-1}\left(\nabla
f\left(x^{t}\right)+H_{t}\left(y^{t,i}-x^{t}\right)\right)\right),\forall
i>1,$ (36)

where $\kappa(H_{t})\geq 1$ is the condition number of $H_{t}$. APG satisfies
(Nesterov, 2018):

$Q_{t}\left(x^{t,i}-x^{t}\right)-Q_{t}^{*}\leq-2\left(1-\kappa(H_{t})^{-1/2}\right)^{i}Q_{t}^{*},\quad\forall
i>0,\quad\forall t\geq 0.$ (37)

Since $\kappa(H_{t})\geq 1$, $p^{t,i}$ satisfies Eq. 8 with Eq. 22 for all
$i\geq\ln 2\sqrt{\kappa(H_{t})}$. If such a $p^{t,i}$ is output as our
$p^{t}$, we see from Eq. 36 that Eq. 23 holds with $s^{t}=0$ and
$\Lambda_{t}=\|H_{t}\|I$. The only condition to check is hence whether
$y^{t,i}$ satisfies Eq. 24. The case of $i=1$ holds trivially with
$\eta_{1}=\sqrt{2/m}$. For $i>1$, Eq. 24 holds with $\eta_{1}=3\sqrt{2\eta
m^{-1}}$ and $\nu=1/2$ because

$\displaystyle~{}{\left\|{y^{t,i}-\left(x^{t}+p^{t*}\right)}\right\|}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:ag}}}{{\leq}}$
$\displaystyle~{}\left(1-\frac{2}{\sqrt{\kappa(H_{t})}+1}\right){\left\|{x^{t,i-1}-x^{t,i-2}}\right\|}+{\left\|{x^{t,i-1}-\left(x^{t}+p^{t*}\right)}\right\|}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:qg},\lx@cref{creftype~refnum}{eq:agrate}}}{{\leq}}$
$\displaystyle~{}\left({\left\|{x^{t,i-1}-x^{t}-p^{t*}}\right\|}+{\left\|{x^{t,i-2}-x^{t}-p^{t*}}\right\|}\right)+\sqrt{2\eta
m^{-1}}\sqrt{-Q_{t}^{*}}$ $\displaystyle\leq$ $\displaystyle~{}3\sqrt{2\eta
m^{-1}}\sqrt{-Q_{t}^{*}}.$

  * •

Prox-SAGA/SVRG: These methods update the iterates by

$x^{t,i}=\mbox{\rm
prox}^{\lambda_{t}I}_{\Psi}\left(x^{t,i-1}-\lambda_{t}^{-1}\left(\nabla
f\left(x^{t}\right)+H_{t}\left(x^{t,i-1}-x^{t}\right)+s^{t}\right)\right),$

with $x^{t,0}=x^{t}$, $\\{\lambda_{t}\\}$ bounded in a positive range, and
$\\{s^{t,i}\\}$ are random variables converging to $0$ as $x^{t,i}-x^{t}$
approaches $p^{t*}$. (For a detailed description, see, for example, Poon et al
(2018).) It is shown in Xiao and Zhang (2014) that for prox-SVRG,
$Q_{t}(x^{t,i}-x^{t})-Q_{t}^{*}$ converges linearly to $0$ with respect to $i$
if $\lambda_{t}$ is small enough, so Eq. 8 with Eq. 22 is satisfied. A similar
but more involved bound for prox-SAGA can be derived from the results in
Defazio et al (2014). When $p^{t,i}=x^{t,i}-x^{t}$ for some $i>0$ is output as
$p^{t}$, we get $y^{t}=x^{t,i-1}$, $\Lambda_{t}=\lambda_{t}I$, and
$s^{t}=s^{t,i}$ in Eq. 23, so the requirements of Theorem 3.2 hold.

If $\Psi$ is block-separable and $\mathcal{M}$ decomposable into a product of
submanifolds that conform with the blocks of $\Psi$, Eq. 23 can be modified
easily to suit block-wise solvers like block-coordinate descent. This
extension simply adapts the analysis above to the block-wise setting, so the
proof is straightforward and omitted for brevity.

Theorem 3.1 and Theorem 3.2 both indicate that for Algorithm 1 to identify
$\mathcal{M}$, we need $x^{t}$ (or at least a subsequence) to converge to a
point $x^{*}$ of partial smoothness. We thus complement our analysis to show
the convergence of the iterates under convexity of $f$ and a local sharpness
condition, which is a special case of the KL condition and is universal in
real-world problems, without requiring coerciveness of $F$. In particular, we
assume $F$ satisfy the following for some $\zeta,\xi>0$, and $\theta\in(0,1]$:

$\zeta\mbox{\rm
dist}(x,\Omega)\leq\left(F(x)-F^{*}\right)^{\theta},\quad\forall
x\in\text{Lev}\left({\xi}\right).$ (38)

This is the well-known quadratic growth condition when $\theta=1/2$, and
$\theta=1$ corresponds to the weak-sharp minima (Burke and Ferris, 1993). As
discussed in Section 1.1, under convexity of $f$, Yue et al (2019) showed that
the iterates of their PN variant converge to some $x^{*}\in\Omega$ if $F$
satisfies EB, which is equivalent to the quadratic growth condition in their
setting (Drusvyatskiy and Lewis, 2018). Our analysis allows broader choices of
$H_{t}$ and (strong) iterate convergence is proven for $\theta\in(1/4,1]$.

###### Theorem 3.3

Consider Algorithm 1 with any $x^{0}\in\mathcal{E}$. Assume that
$\Omega\neq\emptyset$, $f$ is convex and $L$-smooth for $L>0$,
$\Psi\in\Gamma_{0}$, Eq. 7 holds, there is $\eta\in[0,1)$ such that $p^{t}$
satisfies Eq. 8 with Eq. 22 for all $t$, and that Eq. 38 holds for
$\xi,\zeta>0$ and $\theta\in(1/4,1]$. Then $x^{t}\rightarrow x^{*}$ strongly
for some $x^{*}\in\Omega$.

The convergence in Theorem 3.3 holds true in infinite dimensional real Hilbert
spaces with strong convergence (which is indistinguishable from weak
convergence in the finite-dimensional case), and the proof in Appendix 0.B is
written in this general scenario. The key of its proof is our following
improved convergence rate, which might have its own interest. Except for that
the case of $\theta=1/2$ has been proven by Peng et al (2020) and that
$\theta=0$ reduces to the general convex case analyzed in Lee and Wright
(2019), this faster convergence rate is, up to our knowledge, new for ISQA.

###### Theorem 3.4

Consider the settings of Theorem 3.3 but with $\theta\in[0,1]$, $\mathcal{E}$
a real Hilbert space and $x^{0}\in\text{Lev}\left({\xi}\right)$. Then there is
$\bar{\alpha}>0$ such that $\alpha_{t}\geq\bar{\alpha}$ for all $t$ and the
following hold.

  1. 1.

For $\theta\in(1/2,1]$: When $\delta_{t}$ is large enough such that

$\delta_{t}>\left(\zeta^{2}M^{-1}\right)^{\frac{1}{2\theta-1}},$ (39)

we have

$\displaystyle\delta_{t+1}$
$\displaystyle\leq\delta_{t}\left(1-\frac{(1-\eta)\alpha_{t}\gamma\zeta^{2}\xi^{1-2\theta}}{2M}\right).$
(40)

Next, let $t_{0}$ be the first index failing Eq. 39, then for all $t\geq
t_{0}$ we have

$\delta_{t+1}\leq\delta_{t}\left(1-\frac{(1-\eta)\alpha_{t}\gamma}{2}\right).$
(41)

  2. 2.

For $\theta=1/2$, we have global Q-linear convergence of $\delta_{t}$ in the
form

$\frac{\delta_{t+1}}{\delta_{t}}\leq
1-\left(1-\eta\right)\alpha_{t}\gamma\cdot\begin{cases}\frac{\zeta^{2}}{2\|H_{t}\|},&\text{
if }\zeta^{2}\leq\|H_{t}\|,\\\
\left(1-\frac{\|H_{t}\|}{2\zeta^{2}}\right),&\text{
else,}\end{cases}\quad\forall t\geq 0.$ (42)

  3. 3.

For $\theta\in{[}0,1/2)$, Eq. 41 takes place when $\delta_{t}$ is large enough
to satisfy Eq. 39. Let $t_{0}$ be the first index such that Eq. 39 fails, then

$\displaystyle\frac{\delta_{t}}{\delta_{t_{0}}}\leq\left(\left(1-2\theta\right)\sum_{i=t_{0}}^{t-1}\alpha_{i}\right)^{-\frac{1}{1-2\theta}}\leq\left(\left(1-2\theta\right)(t-t_{0})\bar{\alpha}\right)^{-\frac{1}{1-2\theta}},\,\forall
t\geq t_{0}.$ (43)

##  4 An Efficient Inexact SQA Method with Superlinear Convergence in Running
Time

Now that it is clear ISQA is able to identify the active manifold, we utilize
the fact that the optimization problem reduces to a smooth one after the
manifold is identified to devise more efficient approaches, with safeguards to
ensure that the correct manifold is really identified. The improved algorithm,
ISQA+, is presented in Algorithm 2 and we explain the details below.

input : $x^{0}\in\mathcal{E}$, $\gamma,\beta,\in(0,1)$, $S,T\in\mathbb{N}$, a
subproblem solver $\mathcal{A}$ satisfying Eq. 23-Eq. 24 and is linear
convergent for Eq. 2

Compute an upper bound $\hat{L}$ of the Lipschitz constant $L$ for $\nabla f$

$\text{SmoothStep}\leftarrow 0$, $\text{Unchanged}\leftarrow 0$

for  _$t=0,1,\dotsc$_ do

Identify $\mathcal{M}\ni x^{t}$ such that $\Psi$ is partly smooth relative to
$\mathcal{M}$ at $x^{t}$

if  _$\mathcal{M}$ remains the same from last iteration and
$\mathcal{M}\neq\emptyset$_ then

$\text{Unchanged}\leftarrow\text{Unchanged}+1$

if  _$\text{Unchanged} <S$_ then

$\text{SmoothStep}\leftarrow 0$

Decide $H_{t}$ and solve Eq. 2 using $\mathcal{A}$ with at least $T$
iterations

while  _Eq. 6 is not satisfied with $\alpha_{t}=1$_ do

Enlarge $H_{t}$ and resolve Eq. 2 using $\mathcal{A}$ with at least $T$
iterations

$x^{t+1}\leftarrow x^{t}+p^{t}$

else

if  _$\text{SmoothStep}=1$_ then

$\text{SmoothStep}\leftarrow 0$ and conduct a proximal gradient step
$x^{t+1}=\mbox{\rm prox}^{{\hat{L}}I}_{\Psi}\left(x^{t}-{\hat{L}}^{-1}\nabla
f\left(x^{t}\right)\right)$ (44)

else

Manifold optimization: try to find $x^{t+1}$ with $F(x^{t+1}{)}\leq F(x^{t})$
by

  * •

Variant I: truncated Newton: Algorithm 3

  * •

Variant II: Riemannian quasi-Newton

if  _Manifold optimization fails_ then $x^{t+1}\leftarrow x^{t}$,
$\text{Unchanged}\leftarrow 0$

else SmoothStep $\leftarrow 1$

Algorithm 2 ISQA+: An improved inexact successive quadratic approximation
method utilizing manifold identification

ISQA+ has two stages, separated by the event of identifying the active
manifold $\mathcal{M}$ of a cluster point $x^{*}$. Our analysis showed that
iterates converging to $x^{*}$ will eventually identify $\mathcal{M}$, but
since neither $x^{*}$ nor $\mathcal{M}$ is known a priori, the conjecture of
identification can only be made when $\mathcal{M}$ remains unchanged for $S>0$
iterations.

Most parts in the first stage are the same as Algorithm 1, although we have
added specifications for the subproblem solver according to Theorem 3.2. The
only major difference is that instead of linesearch, ISQA+ adjusts $H_{t}$ and
re-solve Eq. 2 whenever Eq. 6 with $\alpha_{t}=1$ fails. This trust-region-
like approach has guaranteed global convergence from Lee and Wright (2019) and
ensures $\alpha_{t}=1$ for Theorem 3.2 to be applicable.

In the second stage, we alternate between a standard proximal gradient (PG)
step Eq. 44 and a manifold optimization (MO) step. PG is equivalent to solving
Eq. 2 with $H_{t}={\hat{L}}I$ to optimality, so Theorem 3.2 applies. When
$\mathcal{M}$ is not correctly identified, a PG step thus prevents us from
sticking at a wrong manifold, while when the superlinear convergence phase of
the MO step is reached, using PG instead of solving Eq. 2 with a sophisticated
$H_{t}$ avoids redundant computation.

When the objective is partly smooth relative to a manifold $\mathcal{M}$,
optimizing it within $\mathcal{M}$ can be cast as a manifold optimization
problem, and efficient algorithms for this type is abundant (see, for example,
Absil et al (2009) for an overview). The difference between applying MO
methods and sticking to Eq. 2 is that in the former, we can obtain the exact
solution to the subproblem for generating the update direction in finite time,
because the subproblem in the MO step is simply an unconstrained quadratic
optimization problem whose solution can be found by solving a linear system,
while in the latter it takes indefinitely long to compute the exact solution,
so the former is preferred in practice for better running time. Although we
did not assume that $f$ is twice-differentiable, its generalized Hessian
(denoted by $\nabla^{2}f$) exists everywhere since the gradient is Lipschitz-
continuous (Hiriart-Urruty et al, 1984). As discussed in Section 2, we can
find a $\mathcal{C}^{2}$ parameterization $\phi$ of $\mathcal{M}$ around
$x^{*}$, and we use this $\phi$ to describe a truncated semismooth Newton
(TSSN) approach. Since $\mathcal{M}$ might change between iterations, when we
are conducting MO at the $t$th iteration, we find a parameterization
$\phi_{t}$ of the current $\mathcal{M}$ and a point $y^{t}$ such that
$\phi_{t}(y^{t})=x^{t}$. If $\mathcal{M}$ remains fixed, we also retain the
same $\phi_{t}$. The TSSN step $q^{t}$ is then obtained by using
preconditioned CG (PCG, see for example (Nocedal and Wright, 2006, Chapter 5))
to find an approximate solution for

$\displaystyle q^{t}$
$\displaystyle\approx\operatorname*{\arg\,min}_{q}\quad\langle
g^{t},\,q\rangle+\frac{1}{2}\langle q,\,H_{t}q\rangle,\quad\text{ or
equivalently }\quad H_{t}q^{t}\approx-g^{t},$ (45) $\displaystyle g^{t}$
$\displaystyle\coloneqq\nabla
F(\phi_{t}(y^{t})),\;H_{t}\coloneqq\nabla^{2}F\left(\phi_{t}(y^{t})\right)+\mu_{t}I,\;\mu_{t}\coloneqq
c{\left\|{g^{t}}\right\|}^{\rho}$

that satisfies

${\left\|{H_{t}q^{t}+g^{t}}\right\|}\leq
0.1\min\left\\{{\left\|{g^{t}}\right\|},{\left\|{g^{t}}\right\|}^{1+\rho}\right\\}$
(46)

with pre-specified $c>0$ and $\rho\in(0,1]$. We then run a backtracking line
search procedure to find a suitable step size $\alpha_{t}>0$. For achieving
superlinear convergence, we should accept unit step size whenever possible, so
we only require the objective not to increase. If $q^{t}$ is not a descent
direction or $\alpha_{t}$ is too small, we consider the MO step failed and go
back to the first stage. If $\alpha_{t}<1$, the superlinear convergence phase
is not entered yet, and likely $\mathcal{M}$ has not been correctly
identified, so we also switch back to the first stage. This algorithm is
summarized in Algorithm 3. When products between
$\nabla^{2}F(\phi_{t}(y^{t}))$ and arbitrary points, required by PCG, cannot
be done easily, one can adopt Riemannian quasi-Newton approaches like Huang et
al (2015) instead.

input : $x^{t}\in\mathcal{E}$, $c>0$, $\rho\in(0,1]$,
$\underline{\alpha},\beta,\gamma\in(0,1)$, and a manifold $\mathcal{M}$

Obtain parameterization $\phi_{t}$ for $\mathcal{M}$ and point $y^{t}$ with
$\phi_{t}(y^{t})=x^{t}$

$\alpha_{t}\leftarrow 1$, and compute $g^{t}$ in Eq. 45

Obtain by PCG an approximation solution $q^{t}$ to Eq. 45 satisfying Eq. 46

if  _$\langle q^{t},\,g^{t}\rangle\geq 0$_ then Report MO step fails and exit

while  _$F(\phi_{t}(y^{t}+\alpha_{t}q^{t})) >F(x^{t})$ and
$\alpha_{t}>\underline{\alpha}$_ do $\alpha_{t}\leftarrow\beta\alpha_{t}$

if  _$\alpha_{t}\leq\underline{\alpha}$_ then Report MO step fails

else $x^{t+1}\leftarrow\phi_{t}(y^{t}+\alpha_{t}q^{t})$

Algorithm 3 Truncated semismooth Newton on Manifold

###  4.1 Global Convergence

This section provides global convergence guarantees for Algorithm 2. Because
MO steps do not increase the objective value, global convergence of Algorithm
2 follows from the analysis in Lee and Wright (2019) by treating Eq. 44 as
solving Eq. 2 with $H_{t}=\hat{L}I$ and noting that this update always
satisfies Eq. 6 with $\alpha_{t}=1$. For completeness, we still state these
results, and provide a proof in Appendix 0.C.

First, we restate a result in Lee and Wright (2019) to bound the number of
steps spent in the while-loop for enlarging $H_{t}$ in Algorithm 2.

######  Lemma 3 ((Lee and Wright, 2019, Lemma 4))

Given an initial choice $H_{t}^{0}$ for $H_{t}$ at the $t$th iteration of
Algorithm 2 (so initially we start with $H_{t}=H_{t}^{0}$ and modify it when
Eq. 6 fails with $\alpha_{t}=1$) and a parameter $\beta\in(0,1)$, consider the
following two variants for enlarging $H_{t}$, starting with $\sigma=1$:

$\displaystyle\sigma\leftarrow\beta\sigma,\quad H_{t}\leftarrow
H_{t}^{0}/\sigma,$ (Variant 1) $\displaystyle H_{t}\leftarrow
H_{t}^{0}+\sigma^{-1}I,\quad\sigma\leftarrow\beta\sigma,$ (Variant 2)

we then have the following bounds if every time the approximate solution to
Eq. 2 always satisfies $Q_{H_{t}}(p^{t};x^{t})\leq 0$.

  1. 1.

If $H_{t}^{0}$ satisfies $M_{0}^{t}\succeq H_{t}^{0}\succeq m_{0}^{t}$ for
some $M_{0}^{t}\geq m_{0}^{t}>0$, then the final $H_{t}$ from Eq. Variant 1
satisfies $\|H_{t}\|\leq M\max\left\\{1,L/(\beta m)\right\\}$, and the while-
loop terminates within $\lceil\log_{\beta^{-1}}L/m\rceil$ rounds.

  2. 2.

If $H_{t}^{0}\succeq 0$, then the final $H_{t}$ from Eq. Variant 2 satisfies
${\left\|{H_{t}}\right\|}\leq M+\max\left\\{1,L/\beta\right\\}$ and the while-
loops terminates within $1+\lceil\log_{\beta^{-1}}{L}\rceil$ rounds.

Now we provide global convergence guarantees for Algorithm 2 without the need
of manifold identification. From Lemma 3, we can simply assume without loss of
generality that Eq. 7 holds for the final $H_{t}$ that leads to the final
update direction that satisfies Eq. 6.

###### Theorem 4.1

Consider Eq. 1 with $f$ $L$-smooth for $L>0$, $\Psi\in\Gamma_{0}$, and
$\Omega\neq\emptyset$. Assume Algorithm 2 is applied with an initial point
$x^{0}$, the estimate $\hat{L}$ satisfies $\hat{L}\geq L$, Eq. 7 holds for the
final $H_{t}$ after exiting the while-loop, and Eq. 8 is satisfied with Eq. 22
for some $\eta\in[0,1)$ fixed over $t$. Let $\\{k_{t}\\}$ be the iterations
that the MO step is not attempted (so either Eq. 2 is solved approximately or
Eq. 44 is conducted), then we have $k_{t}\leq 2t$ for all $t$. By denoting
$\tilde{M}\coloneqq\max\left\\{\hat{L},M\right\\},\quad\tilde{m}\coloneqq\min\left\\{\hat{L},m\right\\}$,
we have the following convergence rate guarantees.

  1. 1.

Let $G_{t}\coloneqq\operatorname*{\arg\,min}_{p}Q_{I}(p;x^{t})$, then
${\left\|{G_{k_{t}}}\right\|}\rightarrow 0$, and for all $t\geq 0$, we have

$\min_{0\leq i\leq
t}{\left\|{G_{k_{i}}}\right\|}^{2}\leq\frac{F(x^{0})-F^{*}}{\gamma(t+1)}\frac{\tilde{M}^{2}\left(1+\tilde{m}^{-1}+\sqrt{1-2\tilde{M}^{-1}+\tilde{m}^{-2}}\right)^{2}}{2(1-\eta)\tilde{m}}.$

Moreover, $G_{t}=0$ if and only if $0\in\partial F(x^{t})$, and therefore any
limit point of $\\{x^{k_{t}}\\}$ is a stationary point of Eq. 1.

  2. 2.

If in addition $f$ is convex and there exists $R_{0}\in[0,\infty)$ such that

$\sup_{x:F\left(x\right)\leq
F\left(x^{0}\right)}\left\|x-P_{\Omega}(x)\right\|=R_{0},$ (47)

in other words, Eq. 38 holds with $\theta=0$, $\zeta=R_{0}^{-1}$, and
$\xi=F(x^{0})-F^{*}$, then:

    1. 2.1.

When $F(x^{k_{t}})-F^{*}\geq\tilde{M}R_{0}^{2}$, we have

$F\left(x^{k_{t}+1}\right)-F^{*}\leq\left(1-\frac{\gamma(1-\eta)}{2}\right)\left(F\left(x^{k_{t}}\right)-F^{*}\right).$

    2. 2.2.

Let
$t_{0}\coloneqq\operatorname*{\arg\,min}_{t}\\{t:F\left(x^{k_{t}}\right)-F^{*}<\tilde{M}R_{0}^{2}\\}$,
we have for all $t\geq t_{0}$ that

$F\left(x^{k_{t}}\right)-F^{*}\leq\frac{2\tilde{M}R_{0}^{2}}{\gamma\left(1-\eta\right)\left(t-t_{0}\right)+2}.$

Moreover, we have

$t_{0}\leq\max\left\\{0,1+\frac{2}{\gamma\left(1-\eta\right)}\log\frac{F\left(x^{0}\right)-F^{*}}{\tilde{M}R_{0}^{2}}\right\\}.$

In summary, we have $F(x^{t})-F^{*}=O\left(t^{-1}\right)$.

  3. 3.

The results of Theorem 3.4 hold, with $M$ and ${\left\|{H_{t}}\right\|}$
replaced by $\tilde{M}$, $\delta_{t}$ by $\delta_{k_{t}}$, $\alpha_{t}$ and
$\bar{\alpha}$ by $1$, $\delta_{t}$ by $\delta_{k_{t}}$, $\delta_{t+1}$ by
$\delta_{k_{t}+1}$, and $\delta_{t_{0}}$ by $\delta_{k_{t_{0}}}$.

###  4.2 Superlinear and Quadratic Convergence

Following the argument in the previous subsection to treat Eq. 44 as solving
Eq. 2 exactly, the manifold identification property of Eq. 44 also follows
from Theorem 3.2. We thus focus on its local convergence in this subsection.
In what follows, we will show that $x^{t}$ converges to a stationary point
$x^{*}$ satisfying Eq. 14 superlinearly or even quadratically in the second
stage.

Let $\mathcal{M}$ be the active manifold of $x^{*}$ and $\phi$ be a
parameterization of $\mathcal{M}$ with $\phi(y^{*})=x^{*}$ for some point
$y^{*}$. We can thus assume without loss of generality $\phi_{t}=\phi$ for all
$t$ that identified $\mathcal{M}$. We denote $F_{\phi}(y)\coloneqq F(\phi(y))$
and assume that $\nabla F_{\phi}$ is strongly semismooth (Mifflin, 1977)
around $y^{*}$, which means it is directionally differentiable at $y^{*}$ and
for any $\nabla^{2}F_{\phi}(y^{*}+\Delta y)\in\partial(\nabla
F_{\phi}(y^{*}+\Delta y))$ with $\Delta y\rightarrow 0$,

$\nabla F_{\phi}(y^{*}+\Delta y)-\nabla
F_{\phi}(y^{*})-\nabla^{2}F_{\phi}(y^{*}+\Delta y)\Delta y=O\left(\|\Delta
y\|^{2}\right).$ (48)

This is a generalization of Lipschitzian Hessian and includes broader cases
such as those $F_{\phi}$ with $\nabla F_{\phi}$ piece-wise linear. We do not
assume $\nabla^{2}F_{\phi}(y^{*})\succ 0$ like existing analysis for Newton’s
method, but consider a degenerate case in which there is a neighborhood
$U_{1}$ of $y^{*}$ such that

$\nabla^{2}F_{\phi}(y){\succeq}0,\quad\forall\nabla^{2}F_{\phi}(y)\in\partial\left(\nabla
F_{\phi}(y)\right),\quad\forall y\in U_{1}.$ (49)

Note that Eq. 49 implies that $F_{\phi}$ is convex within $U_{1}$. We can
decompose $\mathcal{E}$ into the direct sum of the tangent and the normal
spaces of $\mathcal{M}$ at $x^{*}$, and thus its stationarity implies $\nabla
F_{\phi}(y^{*})=0$. This and Eq. 49 mean $y^{*}$ is a local optimum of
$F_{\phi}$, and hence $x^{*}$ is a local minimum of $F$ when $f$ is
$L$-smooth, following the argument of (Wright, 2012, Theorem 2.5). We also
assume that $F_{\phi}$ satisfies a sharpness condition similar to Eq. 38 in a
neighborhood $U_{2}$ of $y^{*}$:

$\zeta^{\hat{\theta}}{\left\|{y-y^{*}}\right\|}\leq\left(F_{\phi}(y)-F\left(y^{*}\right)\right)^{\hat{\theta}},\quad\forall
y\in U_{2},$ (50)

for some $\zeta>0$ and ${\hat{\theta}}\in(0,1/2]$.111${\hat{\theta}}>1/2$
cannot happen unless $F_{\phi}$ is a constant in $U_{2}$. By shrinking the
neighborhoods if necessary, we assume without loss of generality that
$U_{1}=U_{2}$ and denote it by $U$. Note that the conventional assumption of
twice-differentiability with Lipschitz-continuous and positive-definite
Hessian at $y^{*}$ is a special case that satisfies Eq. 49 and Eq. 50 with
$\hat{\theta}=1/2$.

We define $d_{t}\coloneqq{\left\|{y^{t}-y^{*}}\right\|}$ and use it to bound
$y^{t}+q^{t}$ and $\nabla F_{\phi}(y^{t}+q^{t})$.

###### Lemma 4

Consider a stationary point $x^{*}$ of Eq. 1 with $\Psi$ partly smooth at it
relative to a manifold $\mathcal{M}$ with a parameterization $\phi$ and a
point $y^{*}$ such that $\phi(y^{*})=x^{*}$, and assume Eq. 49 holds within a
neighborhood $U$ of $y^{*}$. If $\nabla F_{\phi}$ is strongly semismooth at
$y^{*}$, then $y^{t}\in U$ implies that any $q^{t}$ satisfying Eq. 46 is
bounded by

$\displaystyle{\left\|{q^{t}}\right\|}\leq
2d_{t}+\mu_{t}^{-1}O\left(d_{t}^{2}\right)+0.1\mu_{t}^{-1}{\left\|{g^{t}}\right\|}^{1+\rho}.$
(51)

###### Proof

From Eq. 46, we can find $\psi_{t}\in\mathcal{E}$ such that

$H_{t}q^{t}+g^{t}=\psi_{t},\quad{\left\|{\psi_{t}}\right\|}\leq
0.1{\left\|{g^{t}}\right\|}^{1+\rho}.$ (52)

From Eq. 49 and Eq. 45, we have

$H_{t}\succeq\mu_{t}\succ 0,$ (53)

so $H_{t}$ is invertible. We then get

$\displaystyle{\left\|{y^{t}+q^{t}-y^{*}}\right\|}\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:error}}}{{=}}$
$\displaystyle~{}{\left\|{H_{t}^{-1}\left(\psi_{t}-g^{t}+H_{t}\left(y^{t}-y^{*}\right)\right)}\right\|}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:newton}}}{{\leq}}$
$\displaystyle~{}{\left\|{H_{t}^{-1}}\right\|}\left({\left\|{\psi_{t}}\right\|}+{\left\|{g^{t}-\nabla^{2}F\left(\phi_{t}\left(y^{t}\right)\right)d_{t}}\right\|}+\mu_{t}d_{t}\right)$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:Hlower},\lx@cref{creftype~refnum}{eq:error},\lx@cref{creftype~refnum}{eq:semismoothp}}}{{\leq}}$
$\displaystyle~{}0.1\mu_{t}^{-1}{\left\|{g^{t}}\right\|}^{1+\rho}+\mu_{t}^{-1}O\left(d_{t}^{2}\right)+d_{t}.$
(54)

From the triangle inequality, we have
${\left\|{q^{t}}\right\|}\leq{\left\|{y^{t}-y^{*}}\right\|}+{\left\|{y^{t}+q^{t}-y^{*}}\right\|}$,
whose combination with Eq. 54 proves Eq. 51. ∎

###### Lemma 5

Consider the setting of Lemma 4 and further assume that $\nabla F_{\phi}$ is
strongly semismooth in $U$, $\Psi\in\Gamma_{0}$, and $f$ is $L$-smooth. The
following hold.

  1. 1.

If $\rho\in(0,1]$ and $F_{\phi}$ satisfies Eq. 50 with $\hat{\theta}=1/2$ for
some $\zeta>0$, then

${\left\|{y^{t}+q^{t}-y^{*}}\right\|}=O\left(d_{t}^{1+\rho}\right),\quad{\left\|{\nabla
F_{\phi}(y^{t}+q^{t})}\right\|}=O\left({\left\|{g^{t}}\right\|}^{1+\rho}\right).$
(55)

  2. 2.

If $\rho=0.69$ and $F_{\phi}$ satisfies Eq. 50 for some $\zeta>0$ and
$\hat{\theta}\geq 3/8$, then

${\left\|{y^{t}+q^{t}-y^{*}}\right\|}=o\left(d_{t}\right),\quad{\left\|{\nabla
F_{\phi}(y^{t}+q^{t})}\right\|}=o\left({\left\|{g^{t}}\right\|}\right).$ (56)

###### Proof

From the assumptions on $\Psi$, $\phi$, and $f$, $F_{\phi}$ is twice-
differentiable almost everywhere, and within any compact set $K$ containing
$y^{*}$, any $\nabla^{2}F_{\phi}\in\partial\nabla F_{\phi}$ is upper-bounded
by some $L_{K}>0$ ($f(\phi(y))$ is differentiable with the gradient Lipschitz-
continuous, and $\nabla^{2}(\Psi(\phi(y))$ is upper-bounded), so $F_{\phi}$ is
$L_{K}$-smooth within $K$. Since $K$ is arbitrary, we let $K\supset U$ and
obtain

${\left\|{g^{t}}\right\|}\leq L_{K}d_{t}.$ (57)

Since Eq. 49 implies that $F_{\phi}$ is convex in $U$, Eq. 50 leads to

${\left\|{\nabla
F_{\phi}\left(y\right)}\right\|}\geq\zeta{\left\|{y-y^{*}}\right\|}^{(1-\hat{\theta})/\hat{\theta}},\quad\forall
y\in U.$ (58)

For the first case, Eq. 57-Eq. 58 show $g^{t}=\Theta(d^{t})$, so Lemma 4
implies

${\left\|{q^{t}}\right\|}=O(d_{t})=O(g^{t}).$ (59)

Thus, by the triangle inequality, Eq. 55 is proven by

$\displaystyle{\left\|{\nabla F_{\phi}\left(y^{t}+q^{t}\right)}\right\|}=$
$\displaystyle~{}{\left\|{\nabla
F_{\phi}\left(y^{t}+q^{t}\right)+\psi_{t}-\psi_{t}}\right\|}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:error}}}{{\leq}}$
$\displaystyle~{}{\left\|{\nabla
F_{\phi}\left(y^{t}+q^{t}\right)-g^{t}-H_{t}q^{t}}\right\|}+0.1{\left\|{g^{t}}\right\|}^{1+\rho}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:semismoothp},\lx@cref{creftype~refnum}{eq:newton}}}{{\leq}}$
$\displaystyle~{}O\left({\left\|{q^{t}}\right\|}^{2}\right)+\mu_{t}{\left\|{q^{t}}\right\|}+0.1{\left\|{g^{t}}\right\|}^{1+\rho}\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:qtbound},\lx@cref{creftype~refnum}{eq:newton}}}{{=}}O\left({\left\|{g^{t}}\right\|}^{1+\rho}\right).$
(60)

In the second case, $\hat{\theta}/(1-\hat{\theta})\geq 3/5$, so Eq. 45, Lemma
4 and Eq. 57-Eq. 58 imply

${\left\|{q^{t}}\right\|}=O\left(d_{t}^{0.85}\right).$ (61)

We then get from $\rho=0.69$ that

$\displaystyle{\left\|{\nabla
F_{\phi}\left(y^{t}+q^{t}\right)}\right\|}\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:yq}}}{{\leq}}$
$\displaystyle~{}O\left({\left\|{q^{t}}\right\|}^{2}\right)+\mu_{t}{\left\|{q^{t}}\right\|}+0.1{\left\|{g^{t}}\right\|}^{1.69}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:gt},\lx@cref{creftype~refnum}{eq:newton},\lx@cref{creftype~refnum}{eq:qbound}}}{{=}}$
$\displaystyle~{}O\left(d_{t}^{1.7}\right)+2\mu
d_{t}+O(d_{t}^{2})+O\left(d_{t}^{1.69}\right)=O(d_{t}^{1.69}).$ (62)

From Eq. 58 we get that

${\left\|{y^{t}+q^{t}-y^{*}}\right\|}=O\left({\left\|{\nabla
F_{\phi}\left(y^{t}+q^{t}\right)}\right\|}^{0.6}\right)\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:gbound}}}{{\leq}}O\left((d_{t}^{1.69})^{0.6}\right)=O\left(d_{t}^{1.014}\right),$

proving the first equation in Eq. 56. The second one is then proven by

${\left\|{\nabla
F_{\phi}\left(y^{t}+q^{t}\right)}\right\|}\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:gbound}}}{{\leq}}O\left((d_{t}^{1.69})\right)\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:gradbound}}}{{=}}O\left({\left\|{g^{t}}\right\|}^{1.014}\right).$
∎

Now we are able to show two-step superlinear convergence of
${\left\|{x-x^{*}}\right\|}$.

###### Theorem 4.2

Consider the setting of Lemma 5 and assume in addition that $x^{*}$ satisfies
Eq. 14. Then there is a neighborhood $V$ of $x^{*}$ such that if at the
$t_{0}$th iteration of Algorithm 2 for some $t_{0}>0$ we have that
$x^{t_{0}}\in V$, Unchanged $\geq S$, $\mathcal{M}$ is correctly identified
with parameterization $\phi$ and $\phi(y^{*})=x^{*}$, and $\alpha_{t}=1$ is
taken in Algorithm 3 for all $t\geq t_{0}$, we get the following for all
$t\geq t_{0}$.

  1. 1.

For $\rho\in(0,1]$ and $F_{\phi}$ satisfying Eq. 50 with $\hat{\theta}=1/2$
for some $\zeta>0$:

${\left\|{x^{t+2}-x^{*}}\right\|}=O\left({\left\|{x^{t}-x^{*}}\right\|}^{1+\rho}\right),{\left\|{\nabla
F_{\phi}\left(x^{t+2}\right)}\right\|}=O\left({\left\|{\nabla
F_{\phi}\left(x^{t}\right)}\right\|}^{1+\rho}\right).$ (63)

  2. 2.

For $\rho=0.69$ and $F_{\phi}$ satisfying Eq. 50 for some $\zeta>0$ and
$\hat{\theta}\geq 3/8$,

${\left\|{x^{t+2}-x^{*}}\right\|}=o\left({\left\|{x^{t}-x^{*}}\right\|}\right).$

###### Proof

In our discussion below, $V_{i}$ and $U_{i}$ for $i\in\mathbb{N}$ are
respectively neighborhoods of $x^{*}$ and $y^{*}$.

Since $\phi$ is $\mathcal{C}^{2}$, there is $U_{1}$ of $y^{*}$ such that

$\phi\left(y\right)-\phi\left(y^{*}\right)=\langle\nabla\phi(y^{*}),\,y-y^{*}\rangle+O\left({\left\|{y-y^{*}}\right\|}^{2}\right),\forall
y\in U_{1}.$ (64)

Because the derivative of $\phi$ at $y^{*}$ is injective, Eq. 64 implies

${\left\|{\phi\left(y\right)-\phi\left(y^{*}\right)}\right\|}=\Theta\left({\left\|{y-y^{*}}\right\|}\right),\forall
y\in U_{1}.$ (65)

If the $t$th iteration is a TSSN step, we define $y^{t}$ to be the point such
that $\phi(y^{t})=x^{t}$. If either case in Lemma 5 holds and $q^{t}$
satisfies Eq. 46, from that
${\left\|{y^{t}+q^{t}-y^{*}}\right\|}=o({\left\|{y^{t}-y^{*}}\right\|})$ we
can find $U_{2}\subset U$ such that $y^{t}\in U_{2}$ implies $y^{t}+q^{t}\in
U_{2}$. Take $U_{3}\coloneqq U_{1}\cap U_{2}\subset U$, for $y^{t}\in U_{3}$
and $x^{t+1}=\phi(y^{t}+q^{t})$, we get $y^{t}+q^{t}\in U_{3}\subset U_{1}$,
and hence the following from Eq. 65.

${\left\|{x^{t+1}-x^{*}}\right\|}=\Theta\left({\left\|{y^{t}+q^{t}-y^{*}}\right\|}\right),\quad{\left\|{x^{t}-x^{*}}\right\|}=\Theta\left({\left\|{y^{t}-y^{*}}\right\|}\right).$
(66)

On the other hand, consider the case in which the $t$th iteration is a PG
step. As $\phi$ is $\mathcal{C}^{2}$ and $\phi(y^{*})=x^{*}$, we can find
$V_{1}$ such that $\phi(U_{3})\supset V_{1}\cap\mathcal{M}$. From (Wright,
2012, Lemma 3.2), there is $V_{2}$ such that $x^{t}\in V_{2}$ implies

${\left\|{x^{t+1}-x^{*}}\right\|}=O({\left\|{x^{t}-x^{*}}\right\|}),$ (67)

so there is $V_{3}\subset V_{2}$ such that $x^{t+1}\in V_{1}$ if $x^{t}\in
V_{3}$. Therefore, from Theorem 3.2 (applicable because we have assumed Eq.
14), there is $V_{4}$ such that $x^{t}\in V_{4}$ implies
$x^{t+1}\in\mathcal{M}$. Take $V_{5}\coloneqq V_{4}\cap V_{3}$, then $x^{t}\in
V_{5}$ implies $x^{t+1}\in V_{1}\cap\mathcal{M}$, thus we can find $y^{t+1}\in
U_{3}$ with $\phi(y^{t+1})=x^{t+1}$.

Now consider the first case in the statement. If at the $t$th iteration we
have $x^{t}\in V_{5}$ and have taken Eq. 44, then $x^{t+1}\in
V_{1}\cap\mathcal{M}$ with $x^{t+1}=\phi(y^{t+1})$ for some $y^{t+1}\in
U_{3}$, so we can take a TSSN step at the $(t+1)$th iteration and

$\displaystyle{\left\|{x^{t+2}-x^{*}}\right\|}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:propogate}}}{{=}}\Theta\left({\left\|{y^{t+1}+q^{t+1}-y^{*}}\right\|}\right)\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{lemma:yt}}}{{=}}O\left({\left\|{y^{t+1}-y^{*}}\right\|}^{1+\rho}\right)$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:propogate}}}{{=}}O\left({\left\|{x^{t+1}-x^{*}}\right\|}^{1+\rho}\right)\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:pgsize}}}{{=}}O\left({\left\|{x^{t}-x^{*}}\right\|}^{1+\rho}\right),$
(68)

so there is $V_{6}\subset V_{5}$ such that $x^{t}\in V_{6}$ implies
$x^{t+2}\in V_{6}$ as well and the superlinear convergence in Eq. 68
propagates to $t+2,t+4,\dotsc$. We therefore see that
${\left\|{x^{t+2i+1}-x^{*}}\right\|}=O({\left\|{x^{t+2i-1}-x^{*}}\right\|}^{1+\rho})$
for $i\in\mathbb{N}$ as well, so there is $V_{7}\subset V_{1}$ such that
$x^{t+2i-1}\in V_{7}\cap\mathcal{M}$ implies $x^{t+2i+1}\in
V_{7}\cap\mathcal{M}$ as well.

Let $V=V_{7}\cap V_{6}$, we see that $x^{t}\in V\cap\mathcal{M}$ implies
$x^{t+2}\in V\cap\mathcal{M}$ no matter we take PG or TSSN first, proving the
first equation in Eq. 63. The convergence of $\nabla F_{\phi}$ then follows
from Eq. 57 and Eq. 58. The superlinear convergence in the second case follows
the same argument. ∎

Note that when $\rho=1$ in the first case, we obtain quadratic convergence.

The analysis in Yue et al (2019) assumed directly Eq. 58 instead of Eq. 50,
together with a Lipschitzian Hessian for $f$, under the setting of regularized
optimization to get a superlinear rate. In the context of smooth optimization,
our analysis is more general in allowing non-twice-differentiable functions.
Our analysis also gives a wider range for superlinear convergence. In
particular, for Eq. 58, Yue et al (2019) only allowed $\tilde{\theta}=1$,
where $\tilde{\theta}{\coloneqq}\hat{\theta}/(1-\hat{\theta})$, whereas our
result extends the range of superlinear convergence to $\tilde{\theta}\geq
0.6$.

###### Remark 1

PCG returns the exact solution of Eq. 45 in $d$ steps, where $d$ is the
dimension of $\mathcal{M}$, and each step involves only a bounded number of
basic linear algebra operations, so the running time of Algorithm 3 is upper
bounded. Therefore, superlinear convergence of Algorithm 2 in terms of
iterations from Theorem 4.2 implies that in terms of running time as well.
This contrasts with existing PN approaches, as they all require applying an
iterative subproblem solver to Eq. 2 with increasing precision, which also
takes increasing time per iteration because Eq. 2 has no closed-form solution.

##  5 Numerical Results

We conduct numerical experiments on $\ell_{1}$-regularized logistic regression
to support our theory, which is of the form in Eq. 1 with
$\mathcal{E}=\mathbb{R}^{d}$ for some $d\in\mathbb{N}$,

$\Psi(x)=\lambda{\left\|{x}\right\|}_{1},\;f(x)=\sum_{i=1}^{n}\log\left(1+\exp\left(-b_{i}\langle
a_{i},\,x\rangle\right)\right),$ (69)

where $\lambda>0$ decides the weight of the regularization and
$(a_{i},b_{i})\in\mathbb{R}^{d}\times\\{-1,1\\}$ for $i=1,\dotsc,n$ are the
data points. Note that $\lambda{\left\|{x}\right\|}_{1}$ is partly smooth at
every $x\in\mathbb{R}^{d}$ relative to $\mathcal{M}_{x}\coloneqq\left\\{y\mid
y_{i}=0,\forall i\in I_{x}\right\\}$, where $I_{x}\coloneqq\\{i\mid
x_{i}=0\\}$.

We use public available real-world data sets listed in Table 1.222Downloaded
from http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. All experiments
are conducted with $\lambda=1$ in Eq. 69. All methods are implemented in C++,
and we set $\gamma=10^{-4},\beta=0.5,T=5$ throughout for ISQA and ISQA+.

Table 1: Data statistics. Dataset | #instances ($n$) | #features ($d$)
---|---|---
a9a | 32,561 | 123
realsim | 72,309 | 20,958
news20 | 19,996 | 1,355,191
ijcnn1 | 49,990 | 22
covtype.scale | 581,012 | 54
rcv1-test | 677,399 | 47,226
epsilon | 400,000 | 2,000
webspam | 350,000 | 16,609,143

###  5.1 Manifold Identification of Different Subproblem Solvers

We start with examining the ability for manifold identification of different
subproblem solvers. We run both ISQA and the first stage of ISQA+ (by setting
$S=\infty$) and consider two settings for $H_{t}$. The first is the L-BFGS
approximation with a safeguard in Lee et al (2019), and we set $m=10$ and
$\delta=10^{-10}$ in their notation following their experimental setting. The
second is a PN approach in Yue et al (2019) that uses
$H_{t}=\nabla^{2}f\left(x^{t}\right)+c{\left\|{x^{t}-\mbox{\rm
prox}_{\Psi}\left(x^{t}-\nabla f\left(x^{t}\right)\right)}\right\|}^{\rho}I$,
and we set $\rho=0.5,c=10^{-6}$ following their suggestion. In both cases, we
enlarge $H_{t}$ in Algorithm 2 through $H_{t}\leftarrow 2H_{t}$.

We compare the following subproblem solvers.

  * •

SpaRSA (Wright et al, 2009): a backtracking PG-type method with the initial
step sizes estimated by the Barzilai-Borwein method.

  * •

APG (Nesterov, 2013): See Eq. 35-Eq. 36. We use a simple heuristic of
restarting whenever the objective is not decreasing.

  * •

Random-permutation cyclic coordinate descent (RPCD): Cyclic proximal
coordinate descent with the order of coordinates reshuffled every epoch.

The results presented in Table 2 show that all subproblem solvers for ISQA+
can identify the active manifold, verifying Theorem 3.2. Because the step
sizes are mostly one in this experiment, even solvers for ISQA can identify
the active manifold. Among the solvers, RPCD is the most efficient and stable
in identifying the active manifold, so we stick to it in subsequent
experiments.

Table 2: Outer iterations and time (seconds) for different subproblem solvers to identify the active manifold. For each ISQA+ variant, the fastest running time among all subproblem solvers is boldfaced.  Dataset |  | a9a | realsim | news20
---|---|---|---|---
|  | Time | Iter. | Time | Iter. | Time | Iter.
ISQA+-LBFGS | SpaRSA | 0.7 | 229 | 5.0 | 185 | 10.3 | 136
APG | 1.3 | 408 | 11.8 | 408 | 16.7 | 230
RPCD | 0.6 | 190 | 5.7 | 165 | 9.6 | 131
ISQA-LBFGS | SpaRSA | 0.9 | 238 | 5.9 | 225 | 6.1 | 129
APG | 1.8 | 617 | 12.5 | 418 | 11.9 | 237
RPCD | 0.8 | 238 | 6.1 | 174 | 7.8 | 149
ISQA+-Newton | SpaRSA | 3.3 | 16 | 13.9 | 11 | 6.6 | 19
APG | 6.3 | 45 | 99.6 | 76 | 8.7 | 19
RPCD | 6.6 | 371 | 1.6 | 11 | 0.5 | 7
ISQA-Newton | SpaRSA | 3.4 | 16 | 14.2 | 11 | 6.4 | 19
APG | 6.3 | 45 | 88.5 | 76 | 8.8 | 19
RPCD | 6.8 | 371 | 1.6 | 11 | 0.6 | 7

###  5.2 Comparing ISQA+ with Existing Algorithms

We proceed to compare ISQA+ with the following state of the art for Eq. 1
using the relative objective value: $(F(x)-F^{*})/F^{*}$.

  * •

LHAC (Scheinberg and Tang, 2016): an inexact proximal L-BFGS method with RPCD
for Eq. 2 and a trust-region-like approach. Identical to our L-BFGS variant,
we set $m=10$ for constructing $H_{t}$ in this experiment.

  * •

NewGLMNET (Yuan et al, 2012): a line-search PN with an RPCD subproblem solver.

IRPN (Yue et al, 2019) is another PN method that performs slightly faster than
NewGLMNET, but their algorithmic frameworks are similar and the experiment in
Yue et al (2019) showed that the running time of NewGLMNET is competitive. We
thus use NewGLMNET as the representative because its code is open-sourced.

For ISQA+, we set $S=10$ and use both PN and L-BFGS variants with RPCD in the
first stage and Algorithm 3 with $\rho=0.5,c=10^{-6}$ in the second. For PCG,
we use the diagonals of $H_{t}$ as the preconditioner. We use a heuristic to
let PCG start with an iteration bound $T_{0}=5$, double it whenever
$\alpha_{t}=1$ until reaching the dimension of $\mathcal{M}$, and reset it to
$5$ when $\alpha_{t}<1$. For the value of $S$, although tuning it properly
might lead to even better performance, we observe that the current setting
already suffices to demonstrate the improved performance of the proposed
algorithm.

Results in Fig. 1 show the superlinear convergence in running time of ISQA+,
while LHAC and NewGLMNET only exhibit linear convergence. We observe that for
data with $n\gg d$, including a9a, ijcnn1, covtype.scale, and epsilon, L-BFGS
approaches are faster because $H_{t}p$ can be evaluated cheaply (LHAC failed
on covtype.scale due to implementation issues), and PN approaches are faster
otherwise, so no algorithm is always superior. Nonetheless, for the same type
of $H_{t}$, ISQA+-LBFGS and ISQA+-Newton respectively improve state-of-the-art
algorithms LHAC and NewGLMNET greatly because of the fast local convergence,
especially when the base method converges slowly.

|  |
---|---|---
|  |
|  |

(a) a9a

(b) realsim

(c) news20

(d) ijcnn1

(e) covtype.scale

(f) rcv1-test

(g) epsilon

(h) webspam

(i) webspam (finer scale)

Figure 1: Comparison of Different Algorithms. For covtype.scale, LHAC is not
shown because it failed to converge.

##  6 Conclusions

In this paper, we showed that for regularized problems with a partly smooth
regularizer, inexact successive quadratic approximation is essentially able to
identify the active manifold because a mild sufficient condition is satisfied
by most of commonly-used subproblem solvers. An efficient algorithm ISQA+
utilizing this property is proposed to attain superlinear convergence on a
wide class of degenerate problems in running time, greatly improving upon
state of the art for regularized problems that only exhibit superlinear
convergence in outer iterations. Numerical evidence illustrated that ISQA+
significantly improves the running time of state of the art for regularized
optimization.

## Acknowledgements

I thank Steve Wright for pointing out the direction of manifold
identification. It is my great pleasure to have worked with him during my PhD
study, and this work is extended from my research in that period. I also thank
Michael Ferris for the inspiration of the sharpness condition.

## References

  * Absil et al (2009) Absil PA, Mahony R, Sepulchre R (2009) Optimization algorithms on matrix manifolds. Princeton University Press
  * Attouch et al (2010) Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Mathematics of Operations Research 35(2):438–457
  * Bolte et al (2017) Bolte J, Nguyen TP, Peypouquet J, Suter BW (2017) From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming 165(2):471–507
  * Bonettini et al (2020) Bonettini S, Prato M, Rebegoldi S (2020) Convergence of inexact forward–backward algorithms using the forward–backward envelope. SIAM Journal on Optimization 30(4):3069–3097
  * Burke and Ferris (1993) Burke JV, Ferris MC (1993) Weak sharp minima in mathematical programming. SIAM Journal on Control and Optimization 31(5):1340–1359
  * Byrd et al (2016) Byrd RH, Nocedal J, Oztoprak F (2016) An inexact successive quadratic approximation method for ${L}-1$ regularized optimization. Mathematical Programming 157(2):375–396
  * Candès and Recht (2009) Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Foundations of Computational mathematics 9(6):717–772
  * Candès et al (2006) Candès EJ, Romberg JK, Tao T (2006) Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 59(8):1207–1223
  * Chouzenoux et al (2014) Chouzenoux E, Pesquet JC, Repetti A (2014) Variable metric forward–backward algorithm for minimizing the sum of a differentiable function and a convex function. Journal of Optimization Theory and Applications 162(1):107–132
  * Defazio et al (2014) Defazio A, Bach F, Lacoste-Julien S (2014) Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In: Advances in neural information processing systems, pp 1646–1654
  * Drusvyatskiy and Lewis (2018) Drusvyatskiy D, Lewis AS (2018) Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research 43(3):919–948
  * Dünner et al (2018) Dünner C, Lucchi A, Gargiani M, Bian A, Hofmann T, Jaggi M (2018) A distributed second-order algorithm you can trust. In: Proceedings of the International Conference on Machine Learning
  * Hare (2011) Hare W (2011) Identifying active manifolds in regularization problems. In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, pp 261–271
  * Hare and Lewis (2004) Hare WL, Lewis AS (2004) Identifying active constraints via partial smoothness and prox-regularity. Journal of Convex Analysis 11(2):251–266
  * Hiriart-Urruty et al (1984) Hiriart-Urruty JB, Strodiot JJ, Nguyen VH (1984) Generalized Hessian matrix and second-order optimality conditions for problems with ${C}^{1,1}$ data. Applied Mathematics and Optimization 11(1):43–56
  * Huang et al (2015) Huang W, Gallivan KA, Absil PA (2015) A Broyden class of quasi-Newton methods for Riemannian optimization. SIAM Journal on Optimization 25(3):1660–1685
  * Lee and Chang (2020) Lee Cp, Chang KW (2020) Distributed block-diagonal approximation methods for regularized empirical risk minimization. Machine Learning 109:813–852
  * Lee and Wright (2019) Lee Cp, Wright SJ (2019) Inexact successive quadratic approximation for regularized optimization. Computational Optimization and Applications 72:641–674
  * Lee et al (2019) Lee Cp, Lim CH, Wright SJ (2019) A distributed quasi-Newton algorithm for primal and dual regularized empirical risk minimization. Tech. rep.
  * Lee et al (2014) Lee JD, Sun Y, Saunders MA (2014) Proximal Newton-type methods for minimizing composite functions. SIAM Journal on Optimization 24(3):1420–1443
  * Lee and Wright (2012) Lee S, Wright SJ (2012) Manifold identification in dual averaging for regularized stochastic online learning. Journal of Machine Learning Research 13:1705–1744
  * Lewis (2002) Lewis AS (2002) Active sets, nonsmoothness, and sensitivity. SIAM Journal on Optimization 13(3):702–725
  * Lewis and Zhang (2013) Lewis AS, Zhang S (2013) Partial smoothness, tilt stability, and generalized Hessians. SIAM Journal on Optimization 23(1):74–94
  * Li et al (2017) Li J, Andersen MS, Vandenberghe L (2017) Inexact proximal Newton methods for self-concordant functions. Mathematical Methods of Operations Research 85(1):19–41
  * Li et al (2020) Li YS, Chiang WL, Lee Cp (2020) Manifold identification for ultimately communication-efficient distributed optimization. In: Proceedings of the International Conference on Machine Learning
  * Liang et al (2017) Liang J, Fadili J, Peyré G (2017) Activity identification and local linear convergence of forward–backward-type methods. SIAM Journal on Optimization 27(1):408–437
  * Luo and Tseng (1992) Luo ZQ, Tseng P (1992) Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM Journal on Optimization 2(1):43–54
  * Mifflin (1977) Mifflin R (1977) Semismooth and semiconvex functions in constrained optimization. SIAM Journal on Control and Optimization 15(6):959–972
  * Nesterov (2013) Nesterov Y (2013) Gradient methods for minimizing composite functions. Mathematical Programming 140(1):125–161
  * Nesterov (2018) Nesterov Y (2018) Lectures on convex optimization, vol 137. Springer
  * Nocedal and Wright (2006) Nocedal J, Wright SJ (2006) Numerical optimization, 2nd edn. Springer
  * Peng et al (2020) Peng W, Zhang H, Zhang X, Cheng L (2020) Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions. Journal of Global Optimization pp 1–21
  * Polyak (1987) Polyak BT (1987) Introduction to Optimization. Translation Series in Mathematics and Engineering
  * Poon et al (2018) Poon C, Liang J, Schönlieb CB (2018) Local convergence properties of SAGA/prox-SVRG and acceleration. In: Proceedings of the International Conference on Machine Learning
  * Rockafellar and Wets (2009) Rockafellar RT, Wets RJB (2009) Variational analysis, vol 317. Springer Science & Business Media
  * Scheinberg and Tang (2016) Scheinberg K, Tang X (2016) Practical inexact proximal quasi-Newton method with global complexity analysis. Mathematical Programming 160(1-2):495–529
  * Tibshirani (1996) Tibshirani R (1996) Regression shrinkage and selection via the LASSO. Journal of the Royal Statistical Society Series B 58:267–288
  * Tseng and Yun (2009) Tseng P, Yun S (2009) A coordinate gradient descent method for nonsmooth separable minimization. Mathematical Programming 117(1):387–423
  * Vaisman (1984) Vaisman I (1984) Monographs and textbooks in pure and applied mathematics, Marcel Dekker, New York
  * Wright (2012) Wright SJ (2012) Accelerated block-coordinate relaxation for regularized optimization. SIAM Journal on Optimization 22(1):159–186
  * Wright et al (2009) Wright SJ, Nowak RD, Figueiredo MAT (2009) Sparse reconstruction by separable approximation. IEEE Transactions on Signal Processing 57(7):2479–2493
  * Xiao and Zhang (2014) Xiao L, Zhang T (2014) A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization 24(4):2057–2075
  * Yuan et al (2012) Yuan GX, Ho CH, Lin CJ (2012) An improved GLMNET for ${L1}$-regularized logistic regression. Journal of Machine Learning Research 13:1999–2030
  * Yue et al (2019) Yue MC, Zhou Z, So AMC (2019) A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo–Tseng error bound property. Mathematical Programming 174(1-2):327–358

##  Appendix 0.A Proof of Theorem 3.4

###### Proof

For any $t\geq 0$, (Lee and Wright, 2019, Lemma 5) gives

$\displaystyle
Q^{*}_{t}\leq\min_{\lambda\in[0,1]}\,\lambda(F^{*}-F\left(x^{t}\right))+\frac{\lambda^{2}}{2}\|H_{t}\|\mbox{\rm
dist}(x^{t},\Omega)^{2}.$ (70)

Combining Eq. 70 and Eq. 38 then leads to

$\displaystyle
Q^{*}_{t}\leq-\lambda\delta_{t}+\frac{\lambda^{2}\|H_{t}\|\delta_{t}^{2\theta}}{2\zeta^{2}},\;\;\forall\lambda\in[0,1].$
(71)

Through Eq. 6, Eq. 8, and Eq. 22, we can further deduce from Eq. 71 that

$\displaystyle~{}\delta_{t+1}-\delta_{t}\leq\alpha_{t}\gamma\left(1-\eta\right)Q_{t}^{*}\leq\alpha_{t}\gamma(1-\eta)\left(-\lambda\delta_{t}+\frac{\lambda^{2}M\delta_{t}^{2\theta}}{2\zeta^{2}}\right),\quad\forall\lambda\in[0,1].$
(72)

When $\theta=1/2$, clearly Eq. 71-Eq. 72 imply

$\delta_{t+1}\leq\min_{\lambda\in[0,1]}\,\delta_{t}\left(1-\alpha_{t}\gamma\left(1-\eta\right)\left(\lambda-\frac{\lambda^{2}\|H_{t}\|}{2\zeta^{2}}\right)\right).$
(73)

Setting $\lambda=\min\left\\{1,\zeta^{2}\|H_{t}\|^{-1}\right\\}$ in Eq. 73
then proves Eq. 42.

For $\theta\neq 1/2$, we will use Eq. 72 with

$\lambda=\min\left\\{1,\zeta^{2}\delta_{t}^{1-2\theta}M^{-1}\right\\}.$ (74)

The case in which $\lambda=1$ in Eq. 74 suggests that
$M\delta_{t}^{2\theta-1}\zeta^{-2}\leq 1$ and corresponds to the following
linear decrease.

$\displaystyle\delta_{t+1}-\delta_{t}\leq\alpha_{t}\gamma(1-\eta)\delta_{t}\left(-1+\frac{M\delta_{t}^{2\theta-1}}{2\zeta^{2}}\right)\leq-\delta_{t}\frac{\alpha_{t}\gamma(1-\eta)}{2},$

which is exactly Eq. 41. When $\theta>1/2$, $2\theta-1>0$ so
$M\delta_{t}^{2\theta-1}\zeta^{-2}\leq 1$ if and only if Eq. 39 fails, and
when $\theta<1/2$, it is the opposite case because $2\theta-1<0$.

When $\lambda=\zeta^{2}\delta_{t}^{1-2\theta}M^{-1}$ in Eq. 74, Eq. 72 leads
to

$\delta_{t+1}\leq\delta_{t}-\frac{\alpha_{t}\left(1-\eta\right)\gamma\zeta^{2}}{2M}\delta_{t}^{2-2\theta}.$
(75)

For $\theta>1/2$, this happens when Eq. 39 holds. The rate Eq. 40 is then
obtained from Eq. 75 by $-\delta_{t}^{1-2\theta}\leq-\xi^{1-2\theta}$ for all
$t$, implied by $x^{0}\in\text{Lev}\left({\xi}\right)$ and the monotonicity of
$\\{\delta_{t}\\}$. For $\theta<1/2$, since $1-2\theta>0$, $\lambda<1$ if
$\delta_{t}$ is small enough to fail Eq. 39. We have $2-2\theta>1$, so Eq. 75
and Lemma 6 in (Polyak, 1987, Chapter 2.2) imply Eq. 43. ∎

##  Appendix 0.B Proof of Theorem 3.3

From Theorem 3.4, we have gotten a faster convergence speed of the objective.
We then need to relate it to the decrease of $\hat{Q}_{t}$ and $Q_{t}^{*}$
before proving Theorem 3.3.

###### Lemma 6

Consider Algorithm 1. If $\Omega\neq\emptyset$, $f$ is $L$-smooth for $L>0$,
$\Psi\in\Gamma_{0}$, and there are $m>0$ and $\eta\in[0,1)$ such that
$H_{t}\succeq m$ and $p^{t}$ satisfies Eq. 8 with Eq. 22 for all $t$, then

$\displaystyle\hat{Q}_{t}-Q_{t}^{*}\leq\frac{\eta\delta_{t}}{\gamma\bar{\alpha}(1-\eta)},\quad-
Q_{t}^{*}\leq\frac{\delta_{t}}{\gamma\bar{\alpha}(1-\eta)},\quad\forall t\geq
0,$ (76)

where $\bar{\alpha}>0$ is the constant in Theorem 3.4.

###### Proof

From Eq. 8, Eq. 22, and $Q_{t}(0)=0$, we know that

$\displaystyle-\hat{Q}_{t}\geq-(1-\eta)Q_{t}^{*}.$ (77)

By Eq. 77, Eq. 6, $\delta_{t}\geq 0$, and $\alpha_{t}\geq\bar{\alpha}$ from
Theorem 3.4, the second inequality of Eq. 76 is proven by

$\delta_{t}\geq\delta_{t}-\delta_{t+1}\geq-\gamma\alpha_{t}\left(1-\eta\right)Q_{t}^{*}\geq-\gamma\bar{\alpha}\left(1-\eta\right)Q_{t}^{*}.$
(78)

For the first inequality, the case of $\eta=0$ holds trivially. If
$\eta\in(0,1)$, Eq. 77 implies

$\displaystyle-\eta\hat{Q}_{t}\geq(1-\eta)\left(\hat{Q}_{t}-Q_{t}^{*}\right)\quad\Rightarrow\quad-\hat{Q}_{t}\geq\frac{1-\eta}{\eta}\left(\hat{Q}_{t}-Q_{t}^{*}\right).$
(79)

Following the same logic for obtaining Eq. 78, we get from Eq. 6 and Eq. 79
that

$\eta\delta_{t}\geq\gamma\alpha_{t}(1-\eta)\left(\hat{Q}_{t}-Q_{t}^{*}\right)\geq\gamma\bar{\alpha}(1-\eta)\left(\hat{Q}_{t}-Q_{t}^{*}\right).$

######  Proof (Proof of Theorem 3.3)

Lemma 6 together with Eq. 18 implies that

${\left\|{p^{t}-p^{t*}}\right\|}=O\left(\delta_{t}^{\frac{1}{2}}\right),\quad{\left\|{p^{t*}}\right\|}={\left\|{0-p^{t*}}\right\|}=O\left(\delta_{t}^{\frac{1}{2}}\right).$
(80)

Through the triangle inequality, we have from Eq. 80 and $\alpha_{t}\leq 1$
that

${\left\|{x^{t+1}-x^{t}}\right\|}={\left\|{\alpha_{t}p^{t}}\right\|}=\alpha_{t}{\left\|{p^{t}}\right\|}\leq{\left\|{p^{t}}\right\|}\leq{\left\|{p^{t*}}\right\|}+{\left\|{p^{t}-p^{t*}}\right\|}=O\left(\delta_{t}^{\frac{1}{2}}\right).$
(81)

Condition Eq. 38 implies that for any $x^{0}$, $\mbox{\rm dist}(x,\Omega)$ is
upper-bounded for all $x\in\text{Lev}({F(x^{0})})$, as argued in Bolte et al
(2017). Thus, (Lee and Wright, 2019, Theorem 1) implies that
$\text{Lev}\left({\xi}\right)$ is reached in finite iterations. As the
asymptotic convergence is concerned, we assume
$x^{0}\in\text{Lev}\left({\xi}\right)$ without loss of generality.

We now apply Theorem 3.4 and separately consider $\theta\in[1/2,1]$ and
$\theta\in(1/4,1/2)$. When $\theta\in[1/2,1]$, $\\{\delta_{t}\\}$ converges
$Q$-linearly to $0$, so there exist $t_{0}\geq 0$ and $\tau\in[0,1)$ such that

$\delta_{t+1}\leq\tau\delta_{t},\quad\forall t\geq t_{0}.$

Thus for any $t_{1}\geq t_{2}\geq t_{0}$, we have from the triangle inequality
and Eq. 81 that

$\displaystyle~{}{\left\|{x^{t_{1}}-x^{t_{2}}}\right\|}\leq\sum_{t=t_{2}}^{t_{1}-1}{\left\|{x^{t+1}-x^{t}}\right\|}$
$\displaystyle=$
$\displaystyle~{}O\left(\sum_{t=t_{2}}^{t_{1}-1}\sqrt{\tau^{t-t_{0}}\delta_{t_{0}}}\right)=O\left(\sqrt{\delta_{t_{0}}}\sqrt{\tau^{t_{2}-t_{0}}}\left(1-\sqrt{\tau^{t_{1}-t_{2}}}\right)(1-\sqrt{\tau})^{-1}\right),$

whose right-hand side converges to $0$ as $t_{2}$ approaches infinity.
Therefore, $\\{x^{t}\\}$ is a Cauchy sequence and converges to a point $x^{*}$
as $\mathcal{E}$ is a complete space.

Similarly, for $\theta\in(1/4,1/2)$, Theorem 3.4 implies that there is
$t_{0}\geq 0$ such that

$\sqrt{\delta_{t}}=O\left(t^{-\frac{1}{2(1-2\theta)}}\right)=O\left(t^{-\tau}\right),\quad\forall
t\geq t_{0}$

with $\tau=1/(2(1-2\theta))\in(1,\infty)$. Therefore,

$\sum_{t=t_{2}}^{\infty}t^{-\tau}=O\left(t_{2}^{-\tau+1}\right),\quad\forall
t_{2}\geq t_{0},$

and the right-hand side converges to $0$. We thus have from above that
$\sum_{t=t_{2}}^{t_{1}-1}\sqrt{\delta_{t}}$ converges to $0$ as $t_{2}$
approaches infinity, and Eq. 81 shows that so does
$\sum_{t=t_{2}}^{t_{1}-1}{\left\|{x^{t+1}-x^{t}}\right\|}$. This shows that
$\\{x^{t}\\}$ is a Cauchy sequence and hence converges to a point
$x^{*}\in\mathcal{E}$.

It remains to show that $x^{*}\in\Omega$. Since $f$ is continuous and $\Psi$
is lower semicontinuous, $F$ is also lower semicontinuous. Therefore, we have
that

$\lim\inf_{t\rightarrow\infty}F\left(x^{t}\right)\geq F\left(x^{*}\right)\geq
F^{*}.$ (82)

However, (Lee and Wright, 2019, Theorem 1) implies
$\lim_{t\rightarrow\infty}F(x^{t})=F^{*}$, which together with Eq. 82 shows
that $F(x^{*})=F^{*}$, and hence $x^{*}\in\Omega$. ∎

##  Appendix 0.C Proof of Theorem 4.1

###### Proof

We first note that Eq. 44 can be seen as solving Eq. 2 exactly with
$H_{t}=\hat{L}I$, and it is widely-known that for $\hat{L}\geq L$, Eq. 6 is
always satisfied with $\alpha_{t}=1$. Therefore, under Eq. 7, we have

$\tilde{M}\succeq H_{k_{t}}\succeq\tilde{m},\quad\forall t\geq 0,$ (83)

and Eq. 8 with Eq. 22 holds for all $k_{t}$. For the MO steps, we note that it
does not increase the objective value, so for any computation involving the
objective change, we can safely skip them. That $k_{t}\leq 2t$ for any $t$ is
clear, since we do not conduct two consecutive MO steps.

  1. 1.

The part of $G_{t}=0$ if and only if $0\in\partial F(x^{t})$ is well-known.
See, for example, (Lee and Wright, 2019, Lemma 7). Thus, the claim of
stationarity of the limit points follow directly from the claim that
$G_{k_{t}}\rightarrow 0$.

Now let us prove that $G_{k_{t}}\rightarrow 0$ and the upper bound for
$\min_{0\leq k\leq t}{\left\|{G_{k_{t}}}\right\|}^{2}$. For the $k_{i}$th
iteration, we get from Eq. 6, and that Eq. 22 indicates that
$\hat{Q}_{k_{i}}<0$, that

$-\gamma\hat{Q}_{k_{i}}\leq
F\left(x^{k_{i}}\right)-F\left(x^{k_{i}+1}\right).$ (84)

By applying Eq. 22 and Eq. 8 to Eq. 84, we further get

$-\gamma(1-\eta)Q_{k_{i}}^{*}\leq
F\left(x^{k_{i}}\right)-F\left(x^{k_{i}+1}\right).$

By summing Eq. 84 over $i=0,\dotsc,t$, we get

$-\gamma(1-\eta)\sum_{i=0}^{t}Q_{k_{i}}^{*}\leq\sum_{i=0}^{t}F\left(x^{k_{i}}\right)-F\left(x^{k_{i}+1}\right)\leq
F\left(x^{k_{0}}\right)-F\left(x^{k_{t}+1}\right)\leq F(x^{0})-F^{*},$ (85)

where the penultimate inequality is from that $F(x^{t})$ is nonincreasing.
Following (Lee and Wright, 2019, Lemma 7) and (Tseng and Yun, 2009, Lemma 3),
we then have from Eq. 83 that

$\frac{F(x^{0})-F^{*}}{\gamma(1-\eta)}\geq\sum_{i=0}^{t}-Q_{k_{i}}^{*}\geq\sum_{i=0}^{t}\frac{2\tilde{m}}{\tilde{M}^{2}\left(1+\tilde{m}^{-1}+\sqrt{1-2\tilde{M}^{-1}+\tilde{m}^{-2}}\right)^{2}}{\left\|{G_{k_{i}}}\right\|}^{2}.$
(86)

Since the above is true for any $t\geq 0$, it shows that
$\\{{\left\|{G_{k_{t}}}\right\|}^{2}\\}$ is summable, so
${\left\|{G_{k_{t}}}\right\|}^{2}$ converges to $0$, which implies that
$G_{k_{t}}\rightarrow 0$. The rate is then obtained from Eq. 86 by noting that

$\sum_{i=0}^{t}{\left\|{G_{k_{i}}}\right\|}^{2}\geq\left(t+1\right)\min_{0\leq
i\leq t}{\left\|{G_{k_{i}}}\right\|}^{2}.$

  2. 2.

This part follows directly from the proof of (Lee and Wright, 2019, Theorem 1)
by replacing $t$ by $t_{k}$, noting that MO steps do not increase the
objective value so $\delta_{k_{t+1}}\leq\delta_{k_{t}+1}$ for all $t$, and
using the bound

$\langle
x^{t}-P_{\Omega}(x^{t}),\,H_{t}(x^{t}-P_{\Omega}(x^{t}))\rangle\leq\tilde{M}{\left\|{x^{t}-P_{\Omega}(x^{t}}\right\|}^{2}\leq
MR_{0}^{2},\quad\forall t\geq 0$

from Eq. 47.

  3. 3.

This part follows from the proof of Theorem 3.4 again by using Eq. 83 and that
$\delta_{k_{t+1}}\leq\delta_{k_{t}+1}$ for all $t$.