text:
\section{Introduction}

Many optimization problems that arise in application fields such as statistics, computer science and data science can be cast into constrained optimization problems that minimize smooth functions over compact sets:
\begin{equation}\label{P00}
  \begin{array}{rl}
\min\limits_{x\in{\mathbb{X}}} & f(x) \ \ \ \ {\rm s.t.} \ \ x \in C,
  \end{array}
\end{equation}
where ${\mathbb{X}}$ is a finite-dimensional Euclidean space, $f:{\mathbb{X}}\rightarrow{\rm I\!R}$ is continuously differentiable and $C$ is a nonempty compact set in ${\mathbb{X}}$.
When projections onto $C$ can be efficiently computed, the classical gradient projection method \cite{Bertsekas99, Goldstein64, LevitinPolyak66} and its variants are usually the prominent choices of algorithms for solving \eqref{P00}, due to their ease of implementation and scalability.

Projections onto $C$, however, are not necessarily easy to compute; see for example \cite{FrGM17,HaJN15} for some concrete instances that arise in applications.
In this case, scalable first-order methods that do not involve projections may be employed. When the $C$ in \eqref{P00} is \emph{convex}, one popular class of such algorithms is the Frank-Wolfe (FW) method (also called the conditional gradient method) \cite{FrankWolfe56} and its variants. Unlike the
gradient projection methods which require efficient projections onto $C$, FW method, in each iteration, makes use of a linear approximation of $f$, and moves towards a minimizer of this linear function over $C$ along a straight line to generate a next iterate in $C$. In particular,
FW method uses a {\em linear-optimization oracle} in each iteration; these kind of oracles can be
much less computationally expensive than projecting onto $C$ in many applications \cite{FrGM17,GarberHazan16,Jaggi13}. Due to their low iteration costs and ease of implementations, FW method
and its variants have found applications in machine learning and have received much renewed interest in recent years \cite{FrGM17,GarberHazan16,Jaggi13,LaZh16,Lacoste15,Pedregosa20}. For example, when $f$ is also convex and satisfies certain curvature conditions, \cite{Jaggi13} established
the $O(1/k)$ complexity of FW-type methods for \eqref{P00} and presented their powerful applications for
solving sparse optimization models. In \cite{GarberHazan16,Lacoste15,Pedregosa20}, linear convergence results of some FW-type methods
were established under suitable conditions such as strong convexity of
$f$ or $C$ in \eqref{P00}.
More recently, refinements on the FW method were presented by incorporating
the so-called ``in-face" directions \cite{FrGM17}, which extended the idea of ``away-steps" proposed earlier in \cite{Guelat86,Wolfe}.
For recent development of FW-type methods, we refer the readers to \cite{BRZ21} for a recent survey.

The previous discussions were on FW-type methods for \eqref{P00} when $C$ is convex.
In the case when $C$ in \eqref{P00} is not convex, the study of FW-type methods are much more limited. Indeed, when $C$ is not convex, a notable difficulty is that one may move \emph{outside of $C$} when moving towards a minimizer of the linear-optimization oracle in an iteration of the FW method.
Despite this difficulty, some important contributions along this direction were given in \cite{RT13,BalashovPolyak20}. Specifically, in \cite{RT13},  FW-type methods have been extended to some optimization models for sparse principal component analysis, whose $C=\{x \in \mathbb{R}^n: \|x\|=1, \, \|x\|_0 \le r\}$, where $\|x\|_0$ denotes the cardinality of $x$ and $r>0$. More recently, \cite{BalashovPolyak20} further discussed how FW-type methods can be developed when $C$ is a sphere or more generally a smooth manifold. Interestingly, the feasible region $C$ considered in \cite{RT13,BalashovPolyak20} have empty interior.

In this paper, different from \cite{RT13,BalashovPolyak20}, we are interested in developing FW type methods for \eqref{P00} when $C$ is nonconvex and has (possibly) nonempty interior. Specifically, we consider the following nonconvex optimization problem:
 \begin{equation}\label{P0}
  \begin{array}{rl}
\min\limits_{x\in{\mathbb{X}}} & f(x) \ \ \ \ {\rm s.t.} \ \ P_1(x) - P_2(x) \leq \sigma,
  \end{array}
\end{equation}
 where $f:{\mathbb{X}}\rightarrow{\rm I\!R}$ is continuously differentiable,
 $P_1:{\mathbb{X}}\to {\rm I\!R}$ and $P_2:{\mathbb{X}}\rightarrow{\rm I\!R}$ are convex functions, $\sigma >0$ and the feasible set $\mathcal{F} :=\{x\in {\mathbb{X}}:\; P_1(x) - P_2(x) \leq \sigma\}$ is nonempty and compact.

It is easy to see that \eqref{P0} is a special case of \eqref{P00} with $C=\{x: P_1(x)-P_2(x) \le \sigma\}$.
Notice that, the model \eqref{P0} covers, for example, sparse optimization models whose feasible region can be described as $\{x \in \mathbb{R}^n: P(x) \le r\}$, with $P$ being a weighted difference of $\ell_1$ and $\ell_2$ norms, and $r>0$. For more optimization models of this form, see Section~\ref{sec:LO} below. Our proposed method is an FW-type method in the sense that we make use of a (generalized) linear-optimization oracle (see Definition~\ref{LOdef}) where we linearize \emph{both} the objective function $f$ and the concave part, $-P_2$, of the constraint function. We invoke this linear-optimization oracle to obtain a search direction and use a line search procedure to construct the next iterate and \emph{stay feasible}. We would like to point out that, when $P_2\equiv 0$, our (generalized) linear-optimization oracle reduces to the classical linear-optimization oracle used in the classical FW method. As a result, similar to classical FW method for \eqref{P00} with convex $C$, our proposed method also does not require projections onto $C$.
On the other hand, a notable difference is that, the feasible regions of the linear-optimization oracles in our proposed method \emph{evolve} as the algorithm progresses. This is opposed to the existing FW methods in the literature where the feasible regions of the linear-optimization oracles are fixed as the feasible region of the original problem. As a result, our convergence analysis is \emph{completely different} from those in the existing literature on FW-type methods.

The organization and contribution of this paper are as follows:
\begin{itemize}
\item[{\rm (1)}] After a quick review on notation and basic mathematical tools in Section~\ref{sec2},  we formulate the (new) linear-optimization oracle of our proposed method in Section~\ref{sec:LO}. We also discuss how these linear-optimization oracle problems can be efficiently solved for several important nonconvex optimization models of the form \eqref{P0} arising from compressed sensing and matrix completion.
\item[{\rm (2)}] In Section~\ref{sec4}, we discuss optimality conditions and define a stationarity measure for \eqref{P0}, which paves the way for the convergence analysis of our new FW type methods later.
\item[{\rm (3)}] In Section~\ref{sec:convergence}, we present a new FW type method for solving \eqref{P0}. Under a suitable strict feasibility condition, we establish that the sequence generated by the proposed method is bounded and any accumulation point is a stationary point of \eqref{P0}. In the case where, additionally, the convex part $P_1$ in the constraint is strongly convex and $f$ is Lipschitz differentiable with nonvanishing gradients on ${\cal F}$, we obtain a $o(1/k)$ complexity in terms of the stationarity measure defined in Section~\ref{sec4}.
\item[{\rm (4)}] In Section~\ref{sec6}, motivated by the success of ``away steps" in accelerating FW method in the convex setting, we further introduce a new FW method with  ``away steps" for \eqref{P0}, and establish its subsequential convergence under suitable conditions.
\item[{\rm (5)}] We conclude this paper with numerical experiments on our proposed FW method and its ``away-step" variant for solving some compressed sensing models in the form of \eqref{P0} in Section~\ref{sec7}.
\end{itemize}

\section{Notation and preliminaries}\label{sec2}
In this paper, we use $ {\mathbb{X}} $ to denote a finite-dimensional Euclidean space. We denote by $ \langle \cdot, \cdot\rangle $ the inner product on $ {\mathbb{X}} $ and $ \|\cdot\| $ the associated norm. Next, we let $ {\rm I\!R}^n $ denote the Euclidean space of dimension $ n $, and $ {\rm I\!R}^{m\times n} $ denote the space of all $ m\times n $ matrices. Moreover, the space of $ n\times n $ symmetric matrices will be denoted by $ S^{n} $ and the cone of $ n\times n $ positive semidefinite matrices will be denoted by $ S_+^{n} $. Finally, we let $ \mathbb N_+ $ denote the set of nonnegative integers.

For a set $ S\subseteq{\mathbb{X}} $ and an $ x\in{\mathbb{X}} $, we define the distance from $ x $ to $ S $ as $ {\rm dist}(x, S):= \inf\{\|x-y\|:\,y\in S\} $. The convex hull of $ S $ is denoted by $ {\rm conv}(S) $, and $ {{\rm bdry}\,} S $ is the boundary of $ S $. If $ S $ is a finite set, we denote by $ \lvert S\rvert $ its cardinal number. We use $ B(x, r) $ to denote the closed ball with center $ x $ and radius $ r >0 $, i.e., $  B(x, r) = \{y\in{\mathbb{X}}: \|x-y\| \le r\} $.

We say that an extended-real-valued function $ f:{\mathbb{X}}\rightarrow [-\infty, \infty] $ is proper if its effective domain $ {\rm dom}\, f:=\{x\in{\mathbb{X}}:\, f(x)<\infty \} $ is not empty and $ f(x)>-\infty $ for every $ x\in{\mathbb{X}} $. A proper function is said to be closed if it is lower semicontinuous. The limiting subdifferential of a proper closed function $ h $ at $ \bar x\in{\rm dom}\, h $ is given as
\[
\partial h(\bar x):= \left\{\upsilon\in{\mathbb{X}}:\; \exists x^k\overset{h}\rightarrow \bar x \text{ and } \upsilon^k \in \widehat{\partial} h(x^k) \text{ with } \upsilon^k \rightarrow \upsilon\right\},
\]
where $ x^k\overset{h}\rightarrow \bar x $ means $ x^k\rightarrow \bar x $ and $ h(x^k)\rightarrow h(\bar x) $; here, $\widehat{\partial} h$ is the so-called regular (or Fr\'{e}chet) subdifferential, which, for any $x\in {\rm dom\,} h$, is given by
\[
\widehat{\partial} h(x):=\left\{\upsilon\in{\mathbb{X}} :\; \liminf\limits_{z\rightarrow x,z\neq x}\frac{h(z)-h(x)-\langle \upsilon,z-x\rangle }{\|z-x\|}\ge 0 \right\}.
\]
By convention, we set $\widehat{\partial}h(x)= \partial h(x) = \emptyset$ if $ x\notin {\rm dom}\, h $. It is known that $\partial h(x) = \{\nabla h(x)\}$ if $h$ is continuously differentiable at $x$; see \cite[Exercise~8.8(b)]{RoWe98}. Moreover, when $h$ is proper closed and convex, $\partial h$ reduces to the classical subdifferential in convex analysis; see \cite[Proposition~8.12]{RoWe98}.
Next, for a locally Lipschitz continuous function $ h $, we define its Clarke subdifferential at $ \bar x$ as
\[
\partial^\circ h(\bar x):= \left\{\upsilon\in{\mathbb{X}} :\; \limsup_{x\rightarrow \bar x, t\downarrow 0} \frac{f(x+tw)-f(x)}{t}\geq \langle \upsilon, w\rangle \text{ for all } w\in{\mathbb{X}}\right\};
\]
it holds that $\widehat{\partial}h(\bar x) \subseteq \partial h(\bar x)\subseteq \partial^\circ h(\bar x)$; see \cite[Theorem~5.2.22]{BoZh04}.

We now recall a suitable constraint qualification on the constraint set of \eqref{P0} and present the notion of stationary points of \eqref{P0}.
\begin{definition}[{gMFCQ}
For \eqref{P0}, we say that the generalized Mangasarian-Fromovitz constraint qualification (gMFCQ) holds at an $x^*\in\mathcal{F}$ if the following implication holds:
\[
{\rm If }\; P_1(x^*) - P_2(x^*) = \sigma,  \;{\rm then }\; 0\not\in\partial^\circ(P_1 - P_2)(x^*).
\]
\end{definition}
Note that gMFCQ reduces to the standard MFCQ when $P_1-P_2$ is smooth.

\begin{definition}[{Stationary point}]\label{Stationary}
We say that an $x^*\in{\mathbb{X}}$ is a stationary point of \eqref{P0} if there exists $\lambda_*\in{\rm I\!R}_+$ such that $(x^*,\lambda_*)$ satisfies
\begin{enumerate}[{\rm (i)}]
	\item $0\in \nabla f(x^*) + \lambda_*(\partial P_1(x^*) - \partial P_2(x^*))$;
	\item $\lambda_*(P_1(x^*) - P_2(x^*) - \sigma)=0$, and $P_1(x^*) - P_2(x^*) \leq \sigma$.
\end{enumerate}
\end{definition}
We next deduce that any local minimizer of \eqref{P0} is a stationary point under gMFCQ.
\begin{proposition}\label{loc-sta}
Consider \eqref{P0}. If the gMFCQ holds at every point in $\mathcal{F}$, then any local minimizer of \eqref{P0} is a stationary point of \eqref{P0}.
\end{proposition}
\begin{proof}
For any local minimizer $x^*$ of \eqref{P0}, we can deduce from \cite[Theorem~10.1]{RoWe98} that
\begin{equation}\label{subdif}
0\in\partial(f + \delta_{[P_1 - P_2\leq\sigma]})(x^*),
\end{equation}
where $ \delta_S $ is the indicator function of the set $ S $. Below, we consider two cases.

{\bf Case 1:} $P_1(x^*) - P_2(x^*) < \sigma$. As $P_1$ and $P_2$ are real-valued convex functions, they are also continuous. By the continuity of $P_1$ and $P_2$ and \eqref{subdif}, we have that $\nabla f(x^*) = 0$. Thus $x^*$ is a stationary point of \eqref{P0} (with $\lambda_* = 0$ in Definition~\ref{Stationary}).

{\bf Case 2:} $P_1(x^*) - P_2(x^*) = \sigma$. Then we have that
\[
\begin{aligned}
0&\in\partial(f + \delta_{[P_1 - P_2\leq\sigma]})(x^*) \overset{\rm (a)} = \nabla f(x^*) + \mathcal{N}_{[P_1 - P_2\leq\sigma]}(x^*)\\
&\overset{\rm (b)}\subseteq \nabla f(x^*) + \bigcup\limits_{\lambda\ge0}\lambda\partial^\circ(P_1 - P_2)(x^*)\overset{\rm (c)}\subseteq \nabla f(x^*) + \bigcup\limits_{\lambda\ge0}\lambda(\partial P_1(x^*) - \partial P_2(x^*)).
\end{aligned}
\]
where $ \mathcal{N}_S(x):= \partial \delta_S(x) $ is the limiting normal cone of the set $ S $ at $ x $, and (a) holds in view of \cite[Exercise~8.8]{RoWe98} and the smoothness of $ f $, (b) follows from \cite[Theorem~5.2.22]{BoZh04}, the first corollary to \cite[Theorem~2.4.7]{Cl90} and the fact that $0\not\in\partial^\circ(P_1 - P_2)(x^*)$ (thanks to the gMFCQ), (c) holds because of \cite[Proposition~2.3.3]{Cl90}, \cite[Proposition~2.3.1]{Cl90} and \cite[Theorem~6.2.2]{BoLe06}. Then, there exists $\lambda_*\ge0$ such that $0\in \nabla f(x^*) + \lambda_*(\partial P_1(x^*) - \partial P_2(x^*))$. Noticing that $P_1(x^*) - P_2(x^*) = \sigma$, we also have $\lambda_*(P_1(x^*) - P_2(x^*) - \sigma)=0$. Therefore, $x^*$ is a stationary point of \eqref{P0}.
\end{proof}

Before ending this section, we state two lemmas that will be used subsequently in our discussion of stationarity measure in Section~\ref{sec4} and our convergence analysis in Sections~\ref{sec:convergence} and \ref{sec6}. The first lemma is due to Robinson \cite{Rob75} and concerns error bounds for the so-called ${\cal K}-$convex functions: Given a closed convex cone ${\cal K}\subseteq {\rm I\!R}^m$, we say that $g: {\mathbb{X}}\rightarrow {\rm I\!R}^m$ is $\mathcal{K}-$convex if
\[
\lambda g(x) + (1 - \lambda)g(y)\in g(\lambda x + (1 - \lambda)y) +\mathcal{K},\ \ \forall  x, y\in {\mathbb{X}}, \ \lambda\in [0,1].
\]
\begin{lemma}\label{ErrorBounded}
Let $\mathcal{K}\subseteq {\rm I\!R}^m$ be a closed convex cone and $g:{\mathbb{X}}\to {\rm I\!R}^m$
be a ${\cal K}-$convex function. Let $\Omega := \{x\in {\mathbb{X}}:\; 0 \in g(x) + {\cal K}\}$ and suppose there exist $x^s\in \Omega$ and $\delta > 0$ such that $B(0,\delta)\subseteq g(x^s) + \mathcal{K}$.
Then
\[
{\rm dist}(x,\Omega)\leq \frac{\|x - x^s\|}{\delta}{\rm dist}(0, g(x) + \mathcal{K}), \ \forall x\in {\mathbb{X}}.
\]
\end{lemma}

Our next lemma concerns the convergence of descent algorithms with line-search based on the Armijo rule, which will be used in our convergence analysis. The proof is standard and follows a similar idea as in \cite[Proposition~1.2.1]{Bertsekas99}. Here we include the proof for the ease of readers.
\begin{lemma}\label{Armijolemma}
Let $ \Gamma \subseteq {\mathbb{X}} $ be a compact set. Suppose that $ f:\; {\mathbb{X}}\rightarrow {\rm I\!R} $ is continuously differentiable on an open set containing $\Gamma$. Let $ c\in(0, 1) $, $ \eta\in(0, 1) $ and $ \{\alpha_k^{0}\} $ satisfy $ 0<\inf_k \alpha_k^0\leq \sup_k \alpha_k^0< \infty $. Let $ x^0\in\Gamma $, $\{\alpha_k\}$ be a positive sequence, and $\{x^k\}$ and $ \{d^k\} $ be bounded sequences such that the following conditions hold for each $ k\in\mathbb N_+ $:
	\begin{enumerate}[{\rm (i)}]
		\item $\langle \nabla f(x^k), d^k\rangle < 0$.
		\item $ \alpha_k $ is computed via Armijo line search with backtracking from $\alpha^0_k$, i.e., $\alpha_k = \alpha^0_k\eta^{j_k}$ with
		\begin{equation}\label{Armijols}
		\!\!\!\!\!\!j_k\!:=\! \mathop{\rm arg\,min}\left\{j\!\in\! \mathbb{N}_+\!\!:\! \; f(x^k\!+\!\alpha_k^0\eta^jd^k)\!\leq\! f(x^k) \!+\! c\alpha_k^0\eta^j\langle\nabla f(x^k),d^k\rangle\right\}\!.\!\!\!\!  \ \footnote{Here and throughout this paper, we use $\mathop{\rm Arg\,min}$ to denote the set of minimizers, and write $\mathop{\rm arg\,min}$ when the set of minimizers is a singleton.}
		\end{equation}
		\item $ x^{k+1}\in\Gamma $ and satisfies $ f(x^{k+1})\leq f(x^k+\alpha_kd^k) $.
	\end{enumerate}
   Then, it holds that $ \lim_{k\to\infty} \langle\nabla f(x^k),d^k\rangle =0 $.
\end{lemma}
\begin{proof}
According to \eqref{Armijols} and item (iii), we have for every $k\in\mathbb{N}_+ $,
\[
-c\alpha_k\langle \nabla f(x^k), d^k\rangle\leq f(x^{k}) - f(x^k+\alpha_kd^k) \leq f(x^k) - f(x^{k+1}).
\]
Summing from $ k=0 $ to $ \infty $ on both sides of the above display, we obtain
\[
-c\sum\limits_{k=0}^\infty \alpha_k \langle \nabla f(x^k), d^k\rangle \leq f(x^0) - \inf\limits_{x\in\Gamma} f(x) < \infty;
\]
here, $\inf_\Gamma f$ is finite because $\Gamma$ is compact and  $f$ is continuously differentiable on an open set containing $\Gamma$.  Using this together with item (i), we can deduce that
\begin{equation}\label{sddlim}
	\lim_{k\to\infty} \alpha_k\langle \nabla f(x^k), d^k\rangle = 0.
\end{equation}

Next, notice that $\{x^{k}\}\subseteq \Gamma$ and $\Gamma$ is compact. This together with the boundedness of $\{d^k\} $ and the continuity of $ \nabla f $ implies that $ \{\langle\nabla f(x^k), d^k\rangle\} $ is bounded. Therefore, to prove the desired conclusion, it suffices to show that the limit of any convergent subsequence of $ \{\langle\nabla f(x^k), d^k\rangle\} $ is zero.

To this end, fix any convergent subsequence $ \{ \langle\nabla f(x^{k_t}), d^{k_t}\rangle \} $. Since $ \{\alpha_k\} $ is also bounded, by passing to a further subsequence if necessary, we have $\lim_{t\to\infty} (x^{k_t}, d^{k_t}, \alpha_{k_t}) = (x^*, d^*, \alpha_*)$ for some $ x^*\in\Gamma $, $ d^*\in{\mathbb{X}} $ and $ \alpha_*\geq 0 $. We consider two cases:

{\bf Case 1}: $ \alpha_*>0 $. Then $ \lim_{t\to\infty} \langle\nabla f(x^{k_t}), d^{k_t}\rangle = 0 $ follows directly from \eqref{sddlim}.

{\bf Case 2}: $\alpha_*=0$. In this case, using the fact that $ \inf \alpha_k^0 > 0 $ and the definition of $\alpha_k$ in \eqref{Armijols}, we see that backtracking must have been invoked for all large $t$, i.e., there exists $T $ such that $j_{k_t} \ge 1$ whenever $t\ge T$. Then $j = j_{k_t}-1$ violates the inequality in \eqref{Armijols}, i.e.,
\[
f(x^{k_t}+\eta^{-1}\alpha_{k_t}d^{k_t}) > f(x^{k_t}) + c\eta^{-1}\alpha_{k_t}\langle\nabla f(x^{k_t}), d^{k_t}\rangle \; \text{for every}\; t\geq T.
\]
Dividing both sides of the above inequality by $ \alpha_{k_t}/\eta $ and rearranging terms, we obtain
\[
\frac{f(x^{k_t}+\eta^{-1}\alpha_{k_t}d^{k_t}) - f(x^{k_t})}{\eta^{-1}\alpha_{k_t}} > c\langle\nabla f(x^{k_t}), d^{k_t}\rangle  \; \text{for every}\; t\geq T.
\]
Passing to the limit and rearranging terms in the above display, we have
\[
(1-c)\langle\nabla f(x^*), d^*\rangle \geq 0.
\]
Since $ c\in(0, 1) $, we see further that
\[
\lim_{t\to\infty} \langle\nabla f(x^{k_t}), d^{k_t}\rangle = \langle\nabla f(x^*), d^*\rangle \geq 0.
\]
On the other hand, we have $\lim_{t\to\infty} \langle\nabla f(x^{k_t}), d^{k_t}\rangle  \leq 0$
because $ \langle\nabla f(x^k), d^k\rangle < 0$ for every $ k $. Thus, we conclude that $ \lim_{t\to\infty} \langle\nabla f(x^{k_t}), d^{k_t}\rangle = 0 $.
\end{proof}

\section{Linear-optimization oracles: Examples}\label{sec:LO}

Recall that the FW method \cite{FrankWolfe56, DeRu70, Jaggi13, GarberHazan16} can be efficiently employed in some instances of \eqref{P00} when $C$ is \emph{convex} but the projections onto $C$ are difficult. Concrete examples of such $C$ include the $\ell_p$ norm ball constraint when $p\in(1, \infty)\setminus\{2\}$, the nuclear norm ball constraint that arises in matrix completion problems for recommender systems \cite{FrGM17}, and the total-variation norm ball adopted in image reconstruction tasks \cite{HaJN15}; for these examples, the so-called linear-optimization oracle can be carried out efficiently. Such oracle is used in each iteration of the FW method to generate a test point, and the next iterate of the FW method is obtained as a suitable \emph{convex combination} of the current iterate and the test point. Note that \emph{convexity} of $C$ in \eqref{P00} is crucial here so that the next iterate stays feasible. Since the constraint set of \eqref{P0} can be nonconvex in general, it appears that the classic FW method described above cannot be directly applied to solve \eqref{P0}.

As a first step towards developing FW method for \eqref{P0}, let us define a (new) notion of linear-optimization oracle for the possibly nonconvex constraint set in \eqref{P0}. We will then discuss how to solve the linear-optimization oracles that correspond to some concrete applications. Our new FW-type methods for \eqref{P0} based on this new notion of linear-optimization oracles will be presented as Algorithms~\ref{FW_nonconvex} and \ref{alg:aw-fw} in Sections~\ref{sec:convergence} and \ref{sec6}, respectively.
\begin{definition}[{Linear-optimization oracle}]\label{LOdef}
Let $P_1$, $P_2$ and $\sigma$ be defined in \eqref{P0}, $y\in \mathcal{F}$, $\xi\in\partial P_2(y)$, and define
\begin{equation}\label{Fyxi}
{\cal F}(y,\xi) := \{x\in {\mathbb{X}}:\; P_1(x) - \langle \xi, x - y\rangle - P_2(y) \leq \sigma\}.
\end{equation}
Let $a\in {\mathbb{X}}$. A linear-optimization oracle for $(a, y, \xi)$ (denoted by ${\cal LO}(a, y, \xi)$ or ${\cal LO}$ for brevity) computes a solution of the following problem
\begin{equation}\label{LO}
  \begin{array}{rl}
\min\limits_{x\in{\mathbb{X}}} & \langle a, x\rangle\ \ \ \ {\rm s.t.}\ \  x\in {\cal F}(y,\xi).
  \end{array}
\end{equation}
\end{definition}
\begin{remark}[{Well-definedness of ${\cal LO}$}]\label{welldefined}
Notice that problem \eqref{LO} is well-defined. Indeed, given $y\in \mathcal{F}$ and $\xi\in\partial P_2(y)$, we have
\begin{equation}\label{constrain}
\begin{aligned}
y\in {\cal F}(y,\xi) &= \{x\in {\mathbb{X}}:\; P_1(x) - P_2(y) - \langle \xi, x- y\rangle \leq \sigma\}\\
&\subseteq \{x\in {\mathbb{X}}:\; P_1(x) - P_2(x) \leq \sigma\} = {\cal F}\subseteq B(0,M),
\end{aligned}
\end{equation}
where the first set inclusion follows from the convexity of $P_2$ and the fact that $\xi\in\partial P_2(y)$, and the second set inclusion holds for some $M > 0$ due to the compactness of $\cal F$. Thus, problem \eqref{LO} is minimizing a linear objective function over a compact nonempty constraint set. Hence, its set of optimal solutions is nonempty.
\end{remark}

We now present in the following subsections some concrete examples of ${\cal LO}$ (in the sense of Definition~\ref{LOdef}) that can be carried out efficiently. Our first two examples arise from sparsity inducing problems (group sparsity) and the matrix completion problem, respectively. Our third example concerns the case when $P_1$ is strongly convex, where the ${\cal LO}$ can be shown to be related to the computation of the proximal mapping of a suitable function.

\subsection{Group sparsity}\label{gl}
In this subsection, we let $ {\mathbb{X}} ={\rm I\!R}^n $ and let $x_J$ denote the subvector of $ x \in {\rm I\!R}^n$ indexed by $ J $, where $ J\subseteq \{1,\ldots n\} $. We consider $P_1$ and $P_2$ as in the following assumption and discuss the corresponding ${\cal LO}$.
\begin{assumption}\label{assump31}
Let $ {\mathbb{X}} ={\rm I\!R}^n $ and $\mathcal{J}$ be a partition of $\{1,2,\ldots, n\}$. Let $P_1(x) = \sum_{J\in\mathcal{J}}\|x_J\|$ and $P_2$ be a norm such that $P_2\le \mu P_1$ for some $\mu\in[0,1)$.
\end{assumption}
Notice that the choice of $P_1$ and $P_2$ in Assumption~\ref{assump31} (together with $\sigma > 0$) ensures that the constraint set $\{x\in {\mathbb{X}}:\; P_1(x) - P_2(x)\le \sigma\}$ is compact and nonempty. Thus, in view of Remark~\ref{welldefined}, the corresponding ${\cal LO}$ is well-defined.
The choice of $P_1$ in Assumption~\ref{assump31} is known as the group LASSO regularizer \cite{YuLi06}. As in \cite{YinLouHeXin15}, here we consider a natural extension that subtracts a norm $P_2$ from the group LASSO regularizer. An example of $P_2$ satisfying Assumption~\ref{assump31} is $P_2(x)=\mu\|x\|$ with $\mu \in [0,1)$.

With $P_1$ and $P_2$ in \eqref{P0} chosen as in Assumption~\ref{assump31}, for any given $a\in{\rm I\!R}^n$, any $y\in {\cal F} $ and any $\xi\in\partial P_2(y)$, it holds that $P_2(y) = \langle\xi,y\rangle$ and hence the corresponding ${\cal LO}(a, y, \xi)$ solves a problem of the following form:
\begin{equation}\label{sgl}
\begin{array}{rl}
\min\limits_{x\in{\rm I\!R}^n} & \displaystyle \langle a, x\rangle \ \ \ \
{\rm s.t.} \ \ \displaystyle \sum\limits_{J\in\mathcal{J}}\|x_J\| - \langle\xi, x\rangle\leq \sigma.
  \end{array}
\end{equation}
We next derive a closed form formula that describes an output of ${\cal LO}(a, y, \xi)$. To proceed with our derivation, we first establish the following lemma.
\begin{lemma}\label{gruopsub}
Let $b\in {\rm I\!R}^p\backslash \{0\}$ and $c\in {\rm I\!R}^p$ with $\|c\|<1$. Consider
\begin{equation}\label{sgleq33}
\kappa: = \min\limits_{\|x\| = 1}  \frac{\langle b, x\rangle}{1 - \langle c, x\rangle}.
\end{equation}
Then $\kappa < 0$ and it holds that
\begin{equation*}
c - \frac{\langle b, c\rangle + \sqrt{\langle b, c\rangle^2 - \|b\|^2(\|c\|^2 - 1)}}{\|b\|^2}b \ \in\  \mathop{\rm Arg\,min}\limits_{\|x\| = 1}  \frac{\langle b, x\rangle}{1 - \langle c, x\rangle}.
\end{equation*}
\end{lemma}
\begin{proof}
First note that \eqref{sgleq33} is equivalent to the following problem
\begin{equation}\label{sgleq34}
\min\limits_{\|x\| = 1}  \frac{\langle b, x\rangle}{\|x\| - \langle c, x\rangle}.
\end{equation}
Since $\|c\| < 1$, we must have $\|x\| \pm \langle c, x\rangle > 0$ whenever $\|x\|=1$. Thus, the optimal value $\kappa$ of the above optimization problem must be negative.\footnote{Since $b\neq 0$, the objective in \eqref{sgleq34} is negative at $x = -\frac{b}{\|b\|}$.}

Since the objective of \eqref{sgleq34} is (positively) $0$-homogeneous, we see that an $x^*$ solves \eqref{sgleq34} if and only if $x^* = \frac{x_1^*}{\|x_1^*\|}$, where
\begin{equation}\label{sgleq4}
x_1^*\in \mathop{\rm Arg\,min}\limits_{x_1\in{\rm I\!R}^p\setminus\{0\}}  \frac{\langle b, x_1\rangle}{\|x_1\| - \langle c, x_1\rangle}.
\end{equation}
Using the (positive) $0$-homogeneity of the objective function in \eqref{sgleq4}, one can see further that an optimal solution $x_2^*\in{\rm I\!R}^p$ of the following problem must be optimal for \eqref{sgleq4}:
\begin{equation}\label{sgleq5}
\begin{array}{rl}
\min\limits_{x_2\in{\rm I\!R}^p} & \langle b, x_2\rangle\ \ \ \ {\rm s.t.} \ \ \|x_2\| - \langle c, x_2\rangle = 1.
\end{array}
\end{equation}
We now turn to solving \eqref{sgleq5}. For any $x_2$ satisfying $\|x_2\| - \langle c, x_2\rangle = 1$, we have $x_2 \neq 0$ and $\frac{x_2}{\|x_2\|} - c \neq 0$ (thanks to $\|c\|<1$). Thus, the LICQ holds for \eqref{sgleq5}. Hence, for any optimal solution $x_2^*$ of \eqref{sgleq5},\footnote{Since $\|c\| < 1$, the feasible set of \eqref{sgleq5} is compact and nonempty. This implies that the set of optimal solutions is nonempty.} there exists $\lambda_*\in{\rm I\!R}$ such that
\[
0= b + \lambda_*\left(\frac{x_2^*}{\|x_2^*\|} - c\right)
\]
Since $b\not= 0$, we have that $\lambda_*\not= 0$ and hence $\frac{x_2^*}{\|x_2^*\|} = c - \lambda_*^{-1}b$, which further gives
\begin{equation}\label{findlambda}
  \|c - \lambda^{-1}_*b\|^2 = 1.
\end{equation}
Next, since $c - \lambda^{-1}_*b$ is a positive rescaling of $x_2^*$, we conclude using the relations between \eqref{sgleq34}, \eqref{sgleq4} and \eqref{sgleq5} that $c - \lambda^{-1}_*b$ is an optimal solution of \eqref{sgleq34}. Since $\kappa < 0$, we must then have
\[
0>\langle b, c - \lambda^{-1}_*b\rangle = \langle b, c\rangle - \lambda^{-1}_*\|b\|^2 \quad\Longrightarrow\quad \lambda_*^{-1} > \frac{\langle b, c\rangle}{\|b\|^2}.
\]
Using this together with \eqref{findlambda}, we see that $\lambda^{-1}_*$ must be the larger solution of the quadratic equation $\|c - tb\|^2 = 1$. Solving this quadratic equation, we obtain that
\[
\lambda_*^{-1} = \frac{2\langle b, c\rangle + \sqrt{4\langle b, c\rangle^2 - 4\|b\|^2(\|c\|^2 - 1)}}{2\|b\|^2}.
\]
Combining this with the fact that $c - \lambda^{-1}_*b$ is an optimal solution of \eqref{sgleq34} (and hence \eqref{sgleq33}) completes the proof.
\end{proof}

We now present a closed form solution of problem~\eqref{sgl}. For notational convenience, we define for any $x\in {\rm I\!R}^p$ the following sign function,
\begin{equation}\label{sign}
{\rm Sgn}(x):= \begin{cases}
\frac{x}{\|x\|} & {\rm if}\ x\not=0,\\
\frac{e}{\|e\|} & {\rm if}\ x = 0,
\end{cases}
\end{equation}
where $e$ is the vector of all ones of dimension $p$.

\begin{theorem}[{Closed form solution for \eqref{sgl}}]
  Consider \eqref{sgl} with $a\neq 0$. For each $J\in {\cal J}$, fix any vector $v_J\in {\rm I\!R}^{\lvert J\rvert}$ with $\|v_J\|=1$ and define
\begin{equation}\label{wstar}
w_J^*=
\begin{cases}
  v_J & {\rm if}\  a_J = 0,\\
  \xi_J - \frac{\langle a_J, \xi_J\rangle + \sqrt{\langle a_J, \xi_J\rangle^2 - \|a_J\|^2(\|\xi_J\|^2 - 1)}}{\|a_J\|^2}a_J & {\rm otherwise}.
\end{cases}
\end{equation}
Let $\mathcal{I}:= \mathop{\rm Arg\,min}_{J\in {\cal J}}\{\kappa_J\}$, where
  \begin{equation}\label{sgleq3}
\kappa_J := \min\limits_{\|w_J\| = 1}  \frac{\langle a_J, w_J\rangle}{1 - \langle \xi_J, w_J\rangle},
\end{equation}
and fixed any $J_0\in\mathcal{I}$.\footnote{These $\kappa_J$ are readily computable. Indeed, as we will point out later in the proof of this theorem, the $w^*_J$ in \eqref{wstar} solves the minimization problem in \eqref{sgleq3}, thanks to Lemma~\ref{gruopsub}.} Then a solution $x^*= (x^*_J)_{J\in {\cal J}}$ of \eqref{sgl} is given by
\begin{equation}\label{hahahahaha}
x^*_J = \begin{cases}
  \frac{\sigma w_{J_0}^*}{1 - \langle \xi_{J_0}, w_{J_0}^*\rangle} & {\rm if}\ J = J_0,\\
  0 & {\rm otherwise}.
\end{cases}
\end{equation}
\end{theorem}
\begin{proof}
The existence of optimal solutions to \eqref{sgl} follows from Remark~\ref{welldefined}.
Also, for each $J\in {\cal J}$, we have $\|\xi_J\|\leq \mu < 1$ (thanks to the fact that $P_2$ is a norm, $P_2\leq\mu P_1$ and $\mu< 1$). In addition, from \eqref{sign}, then one can check readily that $\|{\rm Sgn}(x_J)\| = 1$ and $x_J = \|x_J\|{\rm Sgn}(x_J)$. In particular, we have $1 - \langle\xi_J, {\rm Sgn}(x_J)\rangle > 0$.

For each $J\in\mathcal{J}$, let $u_J = (1 - \langle\xi_J, {\rm Sgn}(x_J)\rangle)x_J$. Then we have $\|u_J\| = \big(1 - \langle\xi_J, {\rm Sgn}(x_J)\rangle\big)\|x_J\|$ and ${\rm Sgn}(u_J) = {\rm Sgn}(x_J)$. Thus, we obtain the following equivalences:
\begin{equation*
\begin{split}
&\sum\limits_{J\in\mathcal{J}}(\|x_J\| \!-\! \langle\xi_J, x_J\rangle)\!\leq\! \sigma
\!\Longleftrightarrow\!\! \sum\limits_{J\in\mathcal{J}}\!(1 \!-\! \langle\xi_J, {\rm Sgn}(x_J)\rangle)\|x_J\|\!\leq\! \sigma
\!\Longleftrightarrow\!\! \sum\limits_{J\in\mathcal{J}}\! \|u_J\|\! \leq \sigma.
\end{split}
\end{equation*}
Hence, an $\widehat x$ solves \eqref{sgl} if and only if $\widehat x_J = \frac{\widehat u_J}{(1 - \langle\xi_J, {\rm Sgn}(\widehat u_J)\rangle)}$ for each $J\in\mathcal{J}$, where
\begin{equation}\label{sgleq1}
\widehat u\in\mathop{\rm Arg\,min}\limits_{\sum\limits_{J\in\mathcal{J}}\|u_J\| \leq \sigma} \sum\limits_{J\in\mathcal{J}}\left\langle a_J, \frac{u_J}{1 - \langle\xi_J, {\rm Sgn}(u_J)\rangle} \right\rangle
\end{equation}

We next discuss how to find such a $\widehat u$. Notice that any $u_J\in{\rm I\!R}^{\lvert J\rvert}$ can be written as $u_J = r_Jw_J$ for some $r_J\geq 0$ and $w_J\in {\rm I\!R}^{\lvert J\rvert}$ satisfying $\|w_J\| = 1$. Consequently, $\widehat u$ satisfies \eqref{sgleq1} if and only if $\widehat u_J = \widehat r_J\widehat w_J$, for each $J\in\mathcal{J}$, where
\begin{equation}\label{sgleq2}
\begin{aligned}
(\widehat r, \widehat w)\in \mathop{\rm Arg\,min}\limits_{(r, w)\in{\rm I\!R}^{\lvert\cal{J}\rvert}\times{\rm I\!R}^n}& \displaystyle\sum\limits_{J\in\mathcal{J}} \left\langle a_J, \frac{ w_J}{1 - \langle\xi_J, w_J\rangle} \right\rangle r_J\\
  {\rm s.t.} & \displaystyle\sum_{J\in {\cal J}}r_J \le \sigma,\\
  & \displaystyle r_J\geq 0, \ \ \|w_J\| = 1, \  \ \forall J\in\mathcal{J}.
\end{aligned}
\end{equation}
To solve \eqref{sgleq2}, we start with the minimization with respect to $w_J$. This amounts to solving the optimization problems \eqref{sgleq3} for each $J\in\mathcal{J}$. There are two cases:
\begin{itemize}
  \item If $a_J = 0$, then $\kappa_J = 0$ and the minimum in \eqref{sgleq3} is achieved at any feasible $w_J$; in particular, one can take $\widehat w_J = v_J$ (with $v_J$ as in \eqref{wstar}).
  \item If $a_J \not= 0$, we can apply Lemma~\ref{gruopsub} with $p := \lvert J\rvert$, $b := a_J$ and $c := \xi_J$, to deduce that $\kappa_J < 0$ and a minimizer is given as in \eqref{wstar}.
\end{itemize}
Thus, one can take $\widehat w _J = w^*_J$ in \eqref{wstar} as a minimizer (with respect to $w_J$) in \eqref{sgleq2}.

Now, to solve \eqref{sgleq2}, it remains to consider the following problem to find an $\widehat r$:
\begin{equation}\label{sgleq6}
\begin{array}{rl}
  \min\limits_{r\in{\rm I\!R}^{\lvert\cal{J}\rvert}} & \displaystyle\sum\limits_{J\in\mathcal{J}} \kappa_Jr_J\ \ \ \ \ \ {\rm s.t.}\ \ \ \displaystyle\sum_{J\in {\cal J}}r_J \le \sigma,\ \ r_J \ge 0,\ \ \forall J\in {\cal J}.
\end{array}
\end{equation}
Recall that $\mathcal{I}= \mathop{\rm Arg\,min}_{J}\{\kappa_J\}$ and $J_0$ is a fixed element in $\mathcal{I}$. Since $\kappa_{J} \leq 0$ for any $J\in\mathcal{J}$, we see that $r^* = (r^*_J)_{J\in {\cal J}}$ defined below is an optimal solution of \eqref{sgleq6}:
\begin{equation}\label{rstar}
r^*_J = \begin{cases}
  \sigma & {\rm if}\ J = J_0,\\
  0 & {\rm otherwise}.
\end{cases}
\end{equation}
Hence, a solution to \eqref{sgleq2} is given by $\widehat r = r_J^*$ and $\widehat w = w_J^*$, for each $J$, defined in \eqref{rstar} and \eqref{wstar} respectively.

Finally, invoking the relationship between \eqref{sgleq1} and \eqref{sgleq2}, we see that $\widehat u$ with $\widehat u_J:= r^*_Jw^*_J$ for each $J$ solves \eqref{sgleq1}. Recall that \eqref{sgl} and \eqref{sgleq1} are related via $u_J = (1 - \langle\xi_J, {\rm Sgn}(x_J)\rangle)x_J$ and $x_J = \frac{1}{1 - \langle \xi_J, {\rm Sgn}(u_J)\rangle}u_J$ for all $J$. Thus, we conclude that an optimal solution $x^*= (x^*_J)_{J\in {\cal J}}$ of \eqref{sgl} is given by:
\begin{equation*}
x^*_J = \frac{1}{1 - \langle \xi_J, {\rm Sgn}(r_J^*w^*_J)\rangle}r_J^*w^*_J = \begin{cases}
  \frac{\sigma w_{J_0}^*}{1 - \langle \xi_{J_0}, w_{J_0}^*\rangle} & {\rm if}\ J = J_0,\\
  0 & {\rm otherwise}.
\end{cases}
\end{equation*}
This completes the proof.
\end{proof}

\begin{remark}[Element-wise sparsity]\label{cssparsity}
On passing, we discuss an interesting special case where every $J\in\mathcal{J}$ is a singleton. In this case, we have $P_1 = \|\cdot\|_1$ and $P_2:{\rm I\!R}^n\rightarrow{\rm I\!R}$ is a norm satisfying $P_2\le \mu P_1$ for some $\mu\in[0,1)$. Such a setting arises in compressed sensing \cite{LouYan18,YinLouHeXin15}, where $P_2$ can be chosen as $P_2 = \mu\|\cdot\|$ for some $\mu \in [0,1)$, resulting in the difference of $\ell_1$ and (a positive multiple of) $\ell_2$ norm regularizer. A closed form formula that describes an output of the corresponding ${\cal LO}(a, y, \xi)$ can be readily deduced from \eqref{hahahahaha} as follows, upon invoking \eqref{wstar} and \eqref{rstar}:
\begin{equation}\label{xstar}
x^*_i=\begin{cases}
\displaystyle\frac{-\sigma{\rm Sgn}(a_{i_0})}{1 + \xi_{i_0}{\rm Sgn}(a_{i_0})} & i=i_0,\\
\displaystyle 0 & i\neq i_0,
\end{cases}
\end{equation}
where $ \mathcal{I}:= \mathop{\rm Arg\,min}_{i}\left\{ \frac{-\lvert a_i\rvert }{1 + \xi_i {\rm Sgn}(a_i)} \right\} $ with $ i_0 $ being any fixed element of $\mathcal{I} $, and ${\rm Sgn}$ is defined in \eqref{sign}.
\end{remark}

\subsection{Matrix completion}\label{mc}
In this subsection, we let ${\mathbb{X}} = {\rm I\!R}^{m\times n}$. For an $ X\in{\mathbb{X}} $, we denote by $ \|X\|_* $ and $ \|X\|_F $ its nuclear norm and Frobenius norm, respectively. We consider $P_1$ and $P_2$ as in the following assumption and discuss the corresponding ${\cal LO}$.
\begin{assumption}\label{assump32}
Let ${\mathbb{X}} = {\rm I\!R}^{m\times n}$, $P_1(X) = \|X\|_*$ and $P_2$ be a norm function such that $P_2\le \mu P_1$ for some $\mu\in[0,1)$.
\end{assumption}
Observe that under the choice of $P_1$ and $P_2$ in Assumption~\ref{assump32} (together with $\sigma > 0$), the set $\{x\in {\mathbb{X}}:\; P_1(x) - P_2(x)\le \sigma\}$ is nonempty and compact. Hence, the corresponding ${\cal LO}$ is well-defined thanks to Remark~\ref{welldefined}.
An example of $P_2$ is $P_2(X)= \mu\|X\|_F$ with $\mu \in [0,1)$. In this case, the regularization $ P(X)=\|X\|_* - \mu\|X\|_F $ has been used in low rank matrix completion, which can be viewed as an extension of the $ \ell_{1-2} $ metric in compressed sensing. Exact and stable recovery condition and numerical advantages of this class of nonconvex nonsmooth low-rank metric with $ \mu=1 $ are discussed in \cite{MaLou17}.

Now, with $P_1$ and $P_2$ in \eqref{P0} chosen as in Assumption~\ref{assump32}, for any given $A\in{\rm I\!R}^{m\times n}$, any $Y\in {\cal F} $ and any $\Xi\in \partial P_2(Y)$, it holds that $P_2(Y) = \langle\Xi,Y\rangle$ and thus the corresponding ${\cal LO}(A, Y, \Xi)$ solves a problem of the form:
\begin{equation}\label{lo-mat}
\min\limits_{X\in{\rm I\!R}^{m\times n}} \langle A, X \rangle \quad \text{s.t.}\; \|X\|_* -\langle \Xi, X\rangle \leq \sigma.
\end{equation}We next present a closed form solution of \eqref{lo-mat}. For notational simplicity, we write
\begin{equation}\label{AandXi}
  \widetilde{A} = \begin{bmatrix}
	0 & A \\ A^T & 0
	\end{bmatrix}\ \ \ {\rm and}\ \ \ \widetilde{\Xi}= \begin{bmatrix}
	0 & \Xi \\ \Xi^T & 0
	\end{bmatrix}.
\end{equation}

\begin{theorem}\label{cfs-mat}
	Consider \eqref{lo-mat} with $A\neq 0$. Let $ z\in{\rm I\!R}^{m+n} $ be a generalized eigenvector of the smallest generalized eigenvalue of the matrix pencil $ (\widetilde A, I - \widetilde\Xi) $, and satisfy $z^T(I - \widetilde\Xi)z = 1$, where $\widetilde A$ and $\widetilde\Xi$ are given in \eqref{AandXi}. Then $ X^*=2\sigma z_1z_2^T $ is an optimal solution of \eqref{lo-mat}, where $ z=\begin{bmatrix}
  z_1^T & z_2^T
\end{bmatrix}^T $ with $ z_1\in{\rm I\!R}^m $ and $ z_2\in{\rm I\!R}^n $.
\end{theorem}
\begin{proof}
	For notational convenience, we write
	\begin{equation}\label{Zstar}
	Z^*:= 2\sigma zz^T=\begin{bmatrix}
	U^* & X^* \\ (X^*)^T & V^*
	\end{bmatrix}\succeq 0,
	\end{equation}
	where $ U^* = 2{\sigma}z_1z_1^T $ and $ V^* =  2{\sigma}z_2z_2^T $.

	We first claim that $ Z^* $ is a solution of the following optimization problem:\footnote{Note that $I - \widetilde \Xi \succ 0$ because the spectral norm of $\Xi$ is at most $\mu < 1$. Thus, the feasible set of \eqref{auxp} is nonempty and compact, and hence the set of optimal solution is nonempty.}
	\begin{equation}\label{auxp}
	\min\limits_{Y\in{\mathcal S}^{m+n}_+}\; \langle \widetilde{A}, Y\rangle \quad \text{s.t.}\; \langle I-\widetilde{\Xi}, Y \rangle \leq 2\sigma.
	\end{equation}
	Indeed, by adding a slack variable $ \alpha\in{\rm I\!R}_+ $, \eqref{auxp} can be written as
	\begin{equation}\label{auxp1}
	\min\limits_{Y\in{\mathcal S}^{m+n}_+, \alpha \geq 0}\; \langle \widetilde{A}, Y\rangle \quad \text{s.t.}\; \langle I-\widetilde{\Xi}, Y \rangle +\alpha = 2\sigma.
	\end{equation}
	Note that there is only one equality constraint in the above semidefinite programming problem, and there must be a solution $ (Y^*, \alpha_*) $ that is an extreme point of the feasible set of \eqref{auxp1} (as the solution set of \eqref{auxp1} does not contain a line). According to \cite[Theorem~2.2]{Pataki98}, the rank $ r_Y $ of $ Y^* $ and the rank $ r_\alpha $ of $\alpha_* $ satisfy
	\[
	r_Y(r_Y+1) + r_\alpha (r_\alpha +1 ) \leq 2.
	\]
	Since $ A\neq 0 $, we must have $ Y^*\neq 0 $. This fact together with the above display implies that $ r_Y = 1 $ and $r_{\alpha}=0$. Therefore, we can write the rank-1 solution $ Y^* $ of \eqref{auxp1} as $ Y^* = 2\sigma y^*(y^*)^T $ for some $ y^*\in{\rm I\!R}^{m+n}$ that solves
	\begin{equation*}
	\min_{y\in{\rm I\!R}^{m+n}} y^T\widetilde{A}y \quad \text{s.t.}\; y^T(I-\widetilde{\Xi})y = 1.
	\end{equation*}
	Such a $y^*$ can be obtained as a generalized eigenvector that corresponds to the smallest generalized eigenvalue of the matrix pencil $ (\widetilde A, I-\widetilde\Xi) $ and satisfies $ y^T(I-\widetilde{\Xi})y = 1 $. Now, recalling the definitions of $ z $ and $ Z^* $, we see that $ Z^* $ is a solution of \eqref{auxp}.

	We are now ready to prove that $ X^* $ is a solution of \eqref{lo-mat}. First, recall from \cite{ReFa10} that the nuclear norm of a matrix $ X\in{\rm I\!R}^{m\times n} $ can be represented as:
	\begin{equation}\label{nucn}
	\!\!\!\!\!\|X\|_* = \min\limits_{U, V} \left\{\frac12\left(
	{\rm tr}(U)+{\rm tr}(V)\right):\; \begin{bmatrix}
	U & X \\ X^T & V
	\end{bmatrix}\succeq 0,\; U\in S^{m},\; V\in S^n
	\right\}.\footnote{We would like to point out that the minimum is attainable according to the discussions in \cite{ReFa10}.}
	\end{equation}
	One can then deduce that
	\begin{equation}\label{feasXstar}
	\begin{split}
	&\|X^*\|_*-\langle \Xi, X^* \rangle \overset{\rm (a)}\leq \frac12\left({\rm tr}(U^*)+{\rm tr}(V^*)\right) - \langle \Xi, X^*\rangle\\
	& \overset{\rm (b)}=
	\frac12{\rm tr}(Z^*)-\frac12 \langle \widetilde{\Xi}, Z^*\rangle = \frac12 \langle I-\widetilde{\Xi}, Z^*\rangle \leq
	\sigma,
	\end{split}
	\end{equation}
	where (a) follows from \eqref{nucn} and the definition of $U^*$ and $V^*$ in \eqref{Zstar}, and (b) uses the definitions of $ \widetilde\Xi $ and $ Z^* $. This shows that $X^*$ is feasible for \eqref{lo-mat}.

	Next, for any $ \widetilde X\in{\rm I\!R}^{m\times n} $ satisfying $ \|\widetilde X\|_*-\langle \Xi, \widetilde X\rangle\leq \sigma $, we define $ (\widetilde U, \widetilde V) $ as the minimizer in \eqref{nucn} corresponding to $\|\widetilde X\|_*$.
	Let
\[\widetilde Z=\begin{bmatrix}
	\widetilde{U} & \widetilde{X} \\ \widetilde{X}^T & \widetilde{V}
	\end{bmatrix}.
 \]
 We can check directly that $ \widetilde Z $ is feasible for \eqref{auxp} by using the feasibility of $ \widetilde X $ for \eqref{lo-mat} and the definitions of $ \widetilde A $ and $ \widetilde \Xi $. Then we have
	\[
	\langle A, X^*\rangle = \frac12 \langle \widetilde{A}, Z^*\rangle \overset{\rm (a)}\leq \frac12\langle \widetilde{A}, \widetilde{Z}\rangle \overset{\rm
		(b)}= \langle A, \widetilde{X}\rangle,
	\]
	where (a) uses the optimality of $ Z^* $ and the feasibility of $ \widetilde Z $ for \eqref{auxp}, and (b) uses the definition of $ \widetilde{A} $. This together with \eqref{feasXstar} shows that $ X^*=2 \sigma z_1z_2^T $ solves \eqref{lo-mat}.
\end{proof}

\begin{remark}
To obtain a closed form solution of \eqref{lo-mat}, we have to compute a generalized eigenvector $ z $ as shown in Theorem~\ref{cfs-mat}. Noticing that $I - \widetilde \Xi \succ 0$ (thanks to the fact that the spectral norm of $\Xi$ is at most $\mu < 1$), such a generalized eigenvector $z$ can be found efficiently by  {\sf eigifp} \cite{YeGolub02}: {\sf eigifp} is an iterative solver based on Krylov subspace methods and only requires matrix vector multiplications $ \widetilde{A}u $ and $ \widetilde{\Xi}u $ in each iteration.
\end{remark}

\subsection{The case where $P_1$ is strongly convex}\label{sec:scsubp}
In this subsection, we assume that $ P_1 $ in \eqref{P0} is strongly convex with modulus $ \rho>0 $. We will argue that the corresponding ${\cal LO}$ involves a linear-optimization problem over a strongly convex set. Also, under suitable constraint qualifications, its solution involves computation of proximal mapping.

To this end, consider any given $ a\in{\mathbb{X}}\backslash\{0\} $, any $ y \in {\cal F} $ and any $ \xi\in\partial P_2(y) $.  Then the corresponding $ {\cal LO}(a, y, \xi) $ solves a problem of the following form:
\begin{equation}\label{LOsc}
	\begin{array}{cl}
	\min\limits_{x\in{\mathbb{X}}} & \langle a, x \rangle\ \ \ \ {\rm s.t.} \ \  \widetilde P_1(x) + \frac{\rho}{2}\|x\|^2 -\langle \xi, x\rangle \leq \widetilde{\sigma},
	\end{array}
\end{equation}
where $ \widetilde P_1 := P_1 -\frac{\rho}2\|\cdot\|^2 $ and $ \widetilde\sigma = \sigma + P_2(y) - \langle\xi, y\rangle $.
Moreover, $\widetilde P_1$ is convex.

Now, suppose that Slater's condition holds for the constraint set in \eqref{LOsc}.
Let $ x^* $ be a solution of \eqref{LOsc}. Since $a\neq 0$, we see from \cite[Corollary~28.1]{Ro70} and \cite[Theorem~28.3]{Ro70} that there exists $ \lambda_* > 0 $
such that
\begin{subnumcases}{}
	 x^* = \mathop{\rm arg\,min}_{x\in{\mathbb{X}}} \;\left\{\langle a, x\rangle + \lambda_*\left(\widetilde P_1(x) + \frac{\rho}2\|x\|^2- \langle \xi, x\rangle - \widetilde{\sigma}\right)\right\},	 \label{xlambda} \\
	P_1(x^*) - \langle \xi, x^*\rangle  = \widetilde{\sigma}. \label{eqconst}
\end{subnumcases}
Let $ \iota_* = \lambda_*^{-1} $. One can then deduce from \eqref{xlambda} that
\begin{equation}\label{xprox}
x^* = {\rm Prox}_{\frac 1{\rho}\widetilde P_1}\left(\frac{1}{\rho}(\xi - \iota_* a)\right),
\end{equation}
where $ {\rm Prox}_{g}(y):=\inf_{x\in {\mathbb{X}}}\left\{ g(x) + \frac{1}{2}\|x-y\|^2\right\}$ is the proximal mapping of the proper closed function $ g $ at $ y $. Substituting the above expression into \eqref{eqconst}, we obtain a one-dimensional nonlinear equation in $ \iota_* $ as follows:
\begin{equation*
P_1\left( {\rm Prox}_{\frac 1{\rho}\widetilde P_1}\left(\frac{1}{\rho}(\xi - \iota_* a)\right)\right) - \left\langle \xi,  {\rm Prox}_{\frac 1{\rho}\widetilde P_1}\left(\frac{1}{\rho}(\xi - \iota_* a)\right)\right\rangle  = \widetilde{\sigma}.
\end{equation*}
By standard root-finding procedures, one can solve for $ \iota_*>0 $. Then a solution $ x^* $ to \eqref{LOsc} can be obtained as \eqref{xprox}.

On passing, we would like to point out that any difference-of-convex (DC) function $ P_1-P_2 $ can be rewritten as the difference of strongly convex functions: Indeed, we trivially have for any $\rho > 0$ that $P_1 - P_2 = [P_1 + \frac\rho2\|\cdot\|^2] - [P_2 + \frac\rho2\|\cdot\|^2]$. Thus, the discussions in this section can be applied to the examples in Sections~\ref{gl} and \ref{mc} after transforming the DC functions therein to the difference of strongly convex functions. However, the ${\cal LO}$ involved will then require computing proximal mappings, which can be inefficient compared with the oracles described in Sections~\ref{gl} and \ref{mc}.

\section{Optimality condition}\label{sec4}
In this section, we discuss optimality conditions and define a stationarity measure for problem \eqref{P0} that are important for our algorithmic development later. We consider the following assumption.
\begin{assumption}\label{assumption1}
In \eqref{P0}, for any $y\in\mathcal{F}$ and $\xi\in\partial P_2(y)$, there exists $x^\odot_{(y, \xi)}\in{\mathbb{X}}$ so that the following holds:
\begin{equation}\label{assumine}
P_1(x^\odot_{(y, \xi)}) - P_2(y) - \langle\xi, x^\odot_{(y, \xi)} - y\rangle < \sigma.
\end{equation}
\end{assumption}

Note that Assumption~\ref{assumption1} holds in the examples described under Assumption~\ref{assump31} or \ref{assump32}. In fact, if we take $x^\odot_{(y, \xi)} = 0$ for any $y\in\mathcal{F}$ and $\xi\in\partial P_2(y)$, one can see that \eqref{assumine} holds for those $P_1$ and $P_2$. Moreover, it is interesting to note that Assumption~\ref{assumption1} depends on the choices of $P_1$ and $P_2$ in the DC decomposition of the constraint function. In contrast, the validity of gMFCQ is independent of the choices of $P_1$ and $P_2$.

We now study some relationships between gMFCQ and Assumption~\ref{assumption1}, and show in particular that under Assumption~\ref{assumption1} every local minimizer of \eqref{P0} is a stationary point.
\begin{proposition}\label{slaequ}
Consider \eqref{P0}. Then the following statements hold:
\begin{enumerate}[{\rm (i)}]
	\item If Assumption~\ref{assumption1} holds, then the gMFCQ holds at every point in $\mathcal{F}$.
	\item If gMFCQ holds and $-P_2$ is regular at every point in $\{x\in{\mathbb{X}}:\; P_1(x) - P_2(x) = \sigma\}$, then Assumption~\ref{assumption1} holds.
\end{enumerate}
\end{proposition}
\begin{remark}
From Proposition~\ref{loc-sta}, when the gMFCQ holds at every point in $\mathcal{F}$, we see that any local minimizer of \eqref{P0} is a stationary point of \eqref{P0}. Then we can deduce from Proposition~\ref{slaequ}(i) that any local minimizer of \eqref{P0} is a stationary point of \eqref{P0} when Assumption~\ref{assumption1} holds.
\end{remark}
\begin{proof}
(i): Suppose to the contrary that the gMFCQ fails at some $\bar{x}\in\mathcal{F}$, that is, there exists $\bar x$ with $P_1(\bar x) - P_2(\bar x) = \sigma$ but $0\in\partial^\circ (P_1 - P_2)(\bar x)$. This implies that $0\in\partial P_1(\bar x) - \partial P_2(\bar x)$, and hence there exists $\bar\xi\in\partial P_2(\bar x)$ satisfying $\bar\xi\in\partial P_1(\bar x)$. Moreover, by Assumption~\ref{assumption1}, there exists $x^\odot_{(\bar x, \bar\xi)}\in{\mathbb{X}}$ such that
\[
\sigma > P_1(x^\odot_{(\bar x, \bar\xi)}) - P_2(\bar x) - \langle\bar\xi, x^\odot_{(\bar x, \bar\xi)} - \bar x\rangle \overset{\rm (a)}\geq P_1(\bar x) - P_2(\bar x).
\]
where (a) follows from the convexity of $P_1$ and the fact that $\bar\xi\in\partial P_1(\bar x)$. The above display contradicts $P_1(\bar x) - P_2(\bar x) = \sigma$. Hence the gMFCQ holds at every point in $\mathcal{F}$.

(ii): Suppose to the contrary that Assumption~\ref{assumption1} fails. Then there exist $y\in {\cal F}$ and $\xi\in\partial P_2(y)$ such that for all $x\in{\mathbb{X}}$, $P_1(x) - P_2(y) - \langle\xi, x - y\rangle \geq \sigma$.
In particular, we have $P_1(y) - P_2(y) = P_1(y) - P_2(y) - \langle\xi, y - y\rangle \geq \sigma$, which together with $y\in {\cal F}$ implies
$P_1(y) - P_2(y) = \sigma$.

Since $P_1(y) - P_2(y) = \sigma$, we conclude that $y$ is a minimizer of the function $x\mapsto P_1(x) - P_2(y) - \langle\xi, x - y\rangle $. Then, we deduce from the first-order optimality condition that
\begin{equation*}
\begin{aligned}
0 &\in \partial P_1(y) - \xi\subseteq \partial P_1(y) - \partial P_2(y) \overset{\rm (a)}= \partial^\circ P_1(y) - \partial^\circ P_2(y) \\
& \overset{\rm (b)}= \partial^\circ P_1(y) + \partial^\circ(- P_2)(y) \overset{\rm (c)}= \partial^\circ(P_1 - P_2)(y),
\end{aligned}
\end{equation*}
where (a) follows from \cite[Theorem~6.2.2]{BoLe06}, (b) holds because of \cite[Proposition~2.3.1]{Cl90}, and (c) is true in view of Corollary~1 of \cite[Proposition~2.9.8]{Cl90} and the regularity properties of $-P_2$ (by assumption) and $P_1$ (thanks to convexity). The above display contradicts the gMFCQ. Thus, Assumption~\ref{assumption1} holds.
\end{proof}

Next, we present equivalent characterizations of a stationary point of \eqref{P0}.
\begin{lemma}\label{equistat}
Consider \eqref{P0} and suppose that Assumption~\ref{assumption1} holds. Let $x^*\in {\cal F}$. Then the following statements are equivalent:
\begin{enumerate}[{\rm (i)}]
  \item $x^*$ is a stationary point of \eqref{P0}.
  \item There exists $\xi^*\in\partial P_2(x^*)$ such that $x^*\in\mathop{\rm Arg\,min}_{x\in  {\cal F}(x^*,\xi^*)}\{\langle \nabla f(x^*), x\rangle\}$.\footnote{See \eqref{Fyxi} for the definition of ${\cal F}(x^*,\xi^*)$.}
  \item There exist $\xi^*\in\partial P_2(x^*)$ and $u^*\in\mathop{\rm Arg\,min}_{x\in {\cal F}(x^*,\xi^*)}\{\langle \nabla f(x^*), x\rangle\}$ such that
	\[
	\langle \nabla f(x^*), u^* - x^*\rangle = 0.
	\]
\end{enumerate}
\end{lemma}
\begin{proof}
(i)$\Leftrightarrow$(ii): By Assumption~\ref{assumption1}, for any $x^*\in\mathcal{F}$ and for any $\xi^*\in\partial P_2(x^*)$, one
can see that the constraint set ${\cal F}(x^*,\xi^*) = \{x:\; P_1(x) - P_2(x^*) - \langle \xi^*, x - x^*\rangle \leq
\sigma\}$ contains a Slater point $x^\odot_{(x^*, \xi^*)}$. Then, in view of \cite[Corollary~28.2.1, Theorem~28.3]{Ro70}, we see that (i) is equivalent to (ii).

(ii)$\Rightarrow$(iii): Let $\xi^*$ be as in item (ii). Then $\mathop{\rm Arg\,min}_{x\in  {\cal F}(x^*,\xi^*)}\{\langle \nabla f(x^*), x\rangle\}$ is nonempty thanks to \eqref{constrain}. Now, pick any $u^*\in\mathop{\rm Arg\,min}_{x\in  {\cal F}(x^*,\xi^*)}\{\langle \nabla f(x^*), x\rangle\}$, we obtain $P_1(u^*) - P_2(x^*) - \langle \xi^*, u^* - x^*\rangle \leq \sigma$ and
\begin{equation*}
\langle \nabla f(x^*), u^* \rangle \leq \langle \nabla f(x^*), x^*\rangle,
\end{equation*}
because $x^*\in {\cal F}(x^*,\xi^*)$. Next, since $x^*\in\mathop{\rm Arg\,min}_{x\in  {\cal F}(x^*,\xi^*)}\{\langle \nabla f(x^*), x\rangle\}$, one has
\[
\langle \nabla f(x^*), x^* \rangle \leq \langle \nabla f(x^*), u^*\rangle
\]
Combining the above two displays yields $\langle \nabla f(x^*), u^* - x^*\rangle = 0$.

(iii)$\Rightarrow$(ii): Let $\xi^*$ and $u^*$ be as in item (iii). Then
\[
\langle \nabla f(x^*), x^*\rangle = \langle \nabla f(x^*), u^*\rangle = \min\limits_{x\in {\cal F}(x^*,\xi^*)}\{\langle \nabla f(x^*), x\rangle\}.
\]
Now, since $x^*\in\mathcal{F}$ and hence $x^*\in {\cal F}(x^*,\xi^*)$, we conclude that (ii) holds.
\end{proof}

Finally, we will introduce a stationarity measure for \eqref{P0} which plays an important role in our convergence analysis later. Specifically, we define a merit function $G: \mathcal{F} \rightarrow \mathbb{R}$ by
\begin{equation}\label{defG}
G(x)=\inf_{\xi \in \partial P_2(x)} \max_{y \in \mathcal{F}(x, \xi)} \langle \nabla f(x), x-y\rangle\ \ \ \ \mbox{ for all } x \in \mathcal{F},
\end{equation}
where ${\cal F}(x,\xi)$ is defined as in \eqref{Fyxi}. Note that the maximum in the definition of $G$ is attained.\footnote{
The attainment of the maximum in the definition of $G$ follows from the fact that $\mathcal{F}(x, \xi)$ is a nonempty compact set for all $x \in \mathcal{F}$ and $\xi \in \partial P_2(x)$; see \eqref{constrain}.} In addition, notice that when $ P_2\equiv 0 $, the function $ G $ in \eqref{defG} reduces to the $g$ in \cite[Eq.~(2)]{Jaggi13}: this latter function was used as a measure for optimality in \cite{Jaggi13} where $f$ was assumed to be convex. Here, for problem \eqref{P0} with a possibly nonzero $P_2$, we argue that $G$ can be regarded as a measure for ``proximity to stationarity" for any feasible points of \eqref{P0}, under Assumption~\ref{assumption1}.
\begin{theorem}[Stationarity measure]\label{lemma:1}
Consider \eqref{P0} and suppose that Assumption~\ref{assumption1} holds.  Then, the following statements hold for the $G$ in \eqref{defG}:
\begin{enumerate}[{\rm (i)}]
\item $G(x) \ge 0$ for all $x \in \mathcal{F}$.
\item Let $\{x^k\}\subseteq  \mathcal{F}$.  If $G(x^k) \rightarrow 0$ and $x^k \rightarrow x^*$ for some $x^*$, then $x^*\in {\cal F}$ and is a stationary point of  \eqref{P0}.
\item For $x^* \in \mathcal{F}$, we have $G(x^*)=0$  if and only if $x^*$ is a stationary point of \eqref{P0}.
\end{enumerate}
\end{theorem}
\begin{proof}
Item {\rm (i)} holds in view of \eqref{constrain} and the definition of $G$.

To prove {\rm (ii)}, let $\{x^k\} \subseteq \mathcal{F}$ and $x^k \rightarrow x^*$ with $G(x^k) \rightarrow 0$. Then $x^*\in\mathcal{F}$ because ${\cal F}$ is closed.
Next, notice that
\[
0 \le G(x^k)=\inf_{\xi \in \partial P_2(x^k)} \max_{y \in \mathcal{F}(x^k, \xi)} \langle \nabla f(x^k), x^k-y\rangle \rightarrow 0.
\]
So there exist $\xi^k \in \partial P_2(x^k)$  and $y^k \in {\rm Argmax}_{y \in \mathcal{F}(x^k, \xi^k)}\langle \nabla f(x^k), x^k-y\rangle$ such that
\begin{equation}\label{eq:use1}
\langle \nabla f(x^k), x^k-y^k \rangle \rightarrow 0.
\end{equation}
Note that $\{y^k\}\subseteq {\cal F}$ in view of \eqref{constrain} and is hence bounded. Moreover, $\{x^k\}$ is bounded and hence $\{\xi^k\}$ is bounded in view of \cite[Theorem~2.6]{Tuy98} and the continuity and convexity of $P_2$.
Passing to convergent subsequences if necessary, we may assume that $y^k \rightarrow y^*$ and $\xi^k \rightarrow \xi^*$ for some
 $y^* \in \mathcal{F}$ and $\xi^* \in \partial P_2(x^*)$ (thanks to the closedness of $\partial P_2$). Passing to the limit in \eqref{eq:use1} and using the continuity of $\nabla f$, we have
\begin{equation}\label{eq:use2}
\langle \nabla f(x^*), x^*-y^* \rangle =0.
\end{equation}

We next claim that
\begin{equation}\label{minsub}
x^* \in \mathop{\rm Arg\,min}\limits_{x\in{\mathbb{X}}}\{\langle\nabla f(x^*), x\rangle:\; P_1(x) - P_2(x^*) - \langle\xi^*, x -
x^*\rangle\leq\sigma \}.
\end{equation}
Granting this, in view of Lemma~\ref{equistat}(i), (ii) and the fact that $\xi^*\in \partial P_2(x^*)$, we can then conclude that $x^*$ is a stationary point of \eqref{P0}.

It now remains to establish \eqref{minsub}. To this end, we first define the following
\begin{equation}\label{Omegag}
\begin{array}{ll}
\!\!\!\!\!g_{k}(x)\!:=\!  P_1(x) \!-\! P_2(x^{k}) \!-\!\langle\xi^{k}, x -x^{k}\rangle \!-\! \sigma, & \Omega_{k} \!:=\! \{x\in{\mathbb{X}}:\, g_{k}(x) \leq 0\}
\ \forall k,\!\!\!\!\!\!\\
\!\!\!\!\!g_{*}(x)\!:=\!  P_1(x) \!-\! P_2(x^*) \!-\!\langle\xi^*, x -x^*\rangle \!-\! \sigma,& \Omega_{*} \!:=\! \{x\in{\mathbb{X}}:\, g_{*}(x) \leq 0\}.
\end{array}
\end{equation}
Then, because $x^{k}\to x^*$ and $\xi^{k}\to \xi^*$, we have $\lim_{k\to\infty}g_{k}(x) = g_{*}(x)$ for any $x\in{\rm I\!R}^n$.

Since $x^*\in\mathcal{F}$ and $\xi^*\in\partial P_2(x^*)$, by Assumption~\ref{assumption1}, there exists $x^\odot_{({x^*, \xi^*})}$ such that $g_{*}(x^\odot_{({x^*, \xi^*})}) < 0$, i.e. there exists $\delta_1 > 0$ such that $g_{*}(x^\odot_{({x^*, \xi^*})}) = -\delta_1 < 0$. Moreover, since $g_{k}(x^\odot_{({x^*, \xi^*})}) \to g_{*}(x^\odot_{({x^*, \xi^*})})$, there exists $N_0 > 0$, such that for any $k > N_0$ we have that $g_{k}(x^\odot_{({x^*, \xi^*})}) \leq g_*(x^\odot_{({x^*, \xi^*})}) + \frac{\delta_1}{2} = -\frac{\delta_1}{2}  < 0$.

We now apply Lemma~\ref{ErrorBounded} with $\Omega := \Omega_{k}$, ${\cal K} := {\rm I\!R}_+$, $x^s = x^\odot_{({x^*, \xi^*})}$ and $\delta = \frac{\delta_1}{2}$ to obtain, for each $k > N_0$, that,
\begin{equation}\label{erro}
\begin{aligned}
{\rm dist}(z, \Omega_{k})&\leq 2\delta_1^{-1}\|z - x^\odot_{(x^*, \xi^*)}\|{\rm dist}(0, g_{k}(z) + {\rm I\!R}_+)\\
&\leq 4M\delta_1^{-1}{\rm dist}(0, g_{k}(z) + {\rm I\!R}_+) = 4M\delta_1^{-1}[g_{k}(z)]_+, \
\forall z\in B(0, M),
\end{aligned}
\end{equation}
where $M$ is defined as in \eqref{constrain}, and the second inequality follows from the fact that $\|x^\odot_{(x^*, \xi^*)}\| \le M$ (thanks to \eqref{constrain} and the definition of $x^\odot_{(x^*, \xi^*)}$).

Fix any $u\in \Omega_*$. Since $x^*\in\mathcal{F}$ and $\xi^*\in\partial P_2(x^*)$, by \eqref{constrain}, we have $u\in B(0, M)$.
Moreover, applying \eqref{erro} with $z = u$, we have, for each $k > N_0$,
\[
\|u - {\rm Proj}_{\Omega_{k}}(u)\| = {\rm dist}(u, \Omega_{k})\leq
4M\delta_1^{-1}[g_{k}(u)]_+,
\]
where ${\rm Proj}_{\Omega_{k}}$ is the projection mapping onto $\Omega_k$.
Since $P_1(u) - P_2(x^*) - \langle\xi^*, u - x^*\rangle \le \sigma $ (thanks to $u\in \Omega_*$), we have $[g_{k}(u)]_+\rightarrow 0$ since $x^{k}\rightarrow
x^*$ and $\xi^{k}\rightarrow \xi^*$. From this relation and the above display, we have shown that
\begin{equation}\label{limitproju}
\mbox{For each }u\in \Omega_*, \mbox{ it holds that } \lim_{k\to \infty}{\rm Proj}_{\Omega_{k}}(u) = u,
\end{equation}
where $\Omega_*$ and $\Omega_{k}$ are as in \eqref{Omegag}. Now, since $y^k \in {\rm Argmax}_{y \in \mathcal{F}(x^k, \xi^k)}\langle \nabla f(x^k), x^k-y\rangle$ and noting that $\Omega_k = \mathcal{F}(x^k, \xi^k)$, we see that for any $u\in \Omega_*$,
\[
\langle\nabla f(x^{k}), y^{k} - x^{k}\rangle \leq \langle\nabla f(x^{k}), {\rm Proj}_{\Omega_{k}}(u) -
x^{k}\rangle.
\]
Passing to the limits and noting \eqref{limitproju}, we have
\[
\langle\nabla f(x^*), y^* - x^*\rangle \leq \langle\nabla f(x^*), u - x^*\rangle.
\]
Moreover, in view of \eqref{eq:use2}, we have
\[
\langle\nabla f(x^*), x^* - x^*\rangle = 0 = \langle\nabla f(x^*), y^* - x^*\rangle \leq \langle\nabla f(x^*), u
- x^*\rangle,
\]
Since $u\in \Omega_*$ is chosen arbitrarily, we deduce that \eqref{minsub} holds.

To see {\rm (iii)}, applying {\rm (ii)} with $x^k\equiv x^* \in \mathcal{F}$, we see that if $G(x^*)=0$ then $x^*$ is a stationary point of \eqref{P0}. Conversely, suppose that $x^*$ is a stationary point of \eqref{P0}. Then, from Lemma \ref{equistat}, there exists $\xi^* \in \partial P_2(x^*)$ such that
\[
x^* \in \mathop{\rm Arg\,min}_{y \in \mathcal{F}(x^*, \xi^*)} \langle \nabla f(x^*), y-x^*\rangle = \mathop{\rm Arg\,max}_{y \in \mathcal{F}(x^*, \xi^*)} \langle \nabla f(x^*), x^*-y\rangle.
\]
This shows that $G(x^*) \le 0$. Note that $x^* \in \mathcal{F}$ and hence $G(x^*) \ge 0$ from item (i). Therefore, we see that $G(x^*)=0$.
\end{proof}

\section{Algorithm and convergence analysis}\label{sec:convergence}

We present our FW type algorithm for solving \eqref{P0} as Algorithm~\ref{FW_nonconvex} below, which involves an ${\cal LO}$ (defined in Definition~\ref{LOdef}) and a line-search strategy \eqref{linesearch}. Notice that the structure of the algorithm is similar to that of the classical FW algorithm \cite{LaZh16, Lacoste15,Jaggi13}. The main difference is that the constraint sets in the linear-optimization oracles involved in the classic FW algorithm are the same at each step, while the constraint sets in the ${\cal LO}$s in  Algorithm~\ref{FW_nonconvex} change with iteration.
\begin{algorithm}
	\caption{Frank-Wolfe type algorithm for \eqref{P0} under Assumption~\ref{assumption1}}\label{FW_nonconvex}
	\begin{algorithmic
		\State \vspace{-0.15 cm}
		\begin{description}
		  \item[\bf Step 0.] Choose $x^0\in \mathcal{F}$, $c,\, \eta\in (0, 1)$, and a sequence $\{\alpha^0_k\}\subseteq(0,1]$ with $\inf_k\alpha^0_k > 0$. Set $k = 0$.  \vspace{0.1 cm}
		  \item[\bf Step 1.] Pick $\xi^k\in\partial P_2(x^k)$ and let $u^k$ be an output of ${\cal LO}(\nabla f(x^k), x^k, \xi^k)$ (see Definition~\ref{LOdef}).  Let $ d^k = d^k_{\rm fw} :=u^k-x^k $.

 \noindent If $\langle\nabla f(x^k), d^k\rangle = 0$, terminate.	 \vspace{0.1 cm}
		  \item[\bf Step 2.] Find $ \alpha_k = \alpha_k^0\eta^{j_k} $ with $ j_k $ being the smallest nonnegative integer such that
			\begin{equation}\label{linesearch}
			 f(x^k + \alpha_k d^k) \le f(x^k) + c\alpha_k\langle\nabla f(x^k), d^k \rangle.
			\end{equation}
		  \item[\bf Step 3.] Set $\widehat x^{k+1} = x^k + \alpha_k d^k$. Choose $x^{k+1}\in\mathcal{F}$ such that $ f(x^{k+1})\leq f(\widehat x^{k+1}) $. Update $k \leftarrow k+1$ and go to Step 1.
		\end{description}
	\end{algorithmic}
\end{algorithm}

Before we analyze the well-definedness and other theoretical properties of Algorithm~\ref{FW_nonconvex}, we first comment on the termination condition in Algorithm~\ref{FW_nonconvex}.
\begin{remark}[Termination condition in Step 1]\label{term:step1}
Notice that $u^k$ is an output of ${\cal LO}(\nabla f(x^k), x^k, \xi^k)$. This means, in view of Definition~\ref{LOdef}, that $u^k\in\mathop{\rm Arg\,min}_{x\in {\cal F}(x^k,\xi^k)}\{\langle \nabla f(x^k), x - x^k\rangle\}$. If $\langle\nabla f(x^k), u^k - x^k\rangle = 0$, then we deduce from Lemma~\ref{equistat}(iii) that $x^k$ is a stationary point of \eqref{P0}. Moreover, if $x^k$ is not a stationary point of \eqref{P0}, we have that $\langle\nabla f(x^k), u^k - x^k\rangle < 0$ (since we always have $\langle\nabla f(x^k), u^k - x^k\rangle \leq 0$, thanks to $x^k\in {\cal F}$ and hence $x^k\in\mathcal{F}(x^k,\xi^k)$).
\end{remark}

Next we show that Algorithm~\ref{FW_nonconvex} is well-defined. By Remark~\ref{term:step1}, it suffices to show that, if $x^k\in {\cal F}$ for some $k\ge 0$ is not a stationary point of \eqref{P0} and a $ \xi^k\in\partial P_2(x^k) $ is given, then ${\cal LO}(\nabla f(x^k), x^k, \xi^k)$ has an output, the line-search step in Step 2 terminates in finitely many inner iterations, and an $x^{k+1}\in\mathcal F$ can be generated. This together with an induction argument would establish the well-definedness of Algorithm~\ref{FW_nonconvex}.

\begin{proposition}[Well-definedness of Algorithm~\ref{FW_nonconvex}]\label{Prop1}
Consider Algorithm~\ref{FW_nonconvex} for solving \eqref{P0} under Assumption~\ref{assumption1}. Suppose that an $x^k\in\mathcal{F}$ is generated at the end of the $k$-th iteration of Algorithm~\ref{FW_nonconvex} for some $k\geq 0$ and suppose that $ x^k $ is not a stationary point of \eqref{P0}. Then the following
statements hold for this $k$:
\begin{enumerate}[{\rm (i)}]
  \item The ${\cal LO}(\nabla f(x^k), x^k, \xi^k)$ is well-defined, i.e. the corresponding linear-optimization problem has an optimal solution.
  \item Step 2 of Algorithm~\ref{FW_nonconvex} terminates in finitely many inner iterations.
  \item $\widehat{x}^{k+1}\in {\cal F}$.
\end{enumerate}
Thus, an $x^{k+1}\in {\cal F}$ can be generated at the end of the $(k+1)$th iteration of Algorithm~\ref{FW_nonconvex}.
\end{proposition}
\begin{proof}
(i): The well-definedness follows from Remark~\ref{welldefined}.

(ii): Define $\psi(\alpha) := f(x^k + \alpha(u^k - x^k))$. Since $f$ is continuously differentiable, for each $\alpha > 0$, by the mean value theorem, there exists $t_\alpha\in (0,\alpha)$ such that
\[
\begin{split}
&f(x^k + \alpha(u^k - x^k)) = \psi(\alpha) = \psi(0) + \alpha \psi'(t_\alpha) \\
&= \psi(0) + c\alpha \psi'(0) + \alpha [(1-c)\psi'(0) + \psi'(t_\alpha) - \psi'(0)]\\
& = f(x^k) + c \alpha\langle\nabla f(x^k), u^k - x^k\rangle \\
&\ \ \ \ +\alpha\left((1-c)\langle\nabla f(x^k), u^k - x^k\rangle + [\psi'(t_\alpha) - \psi'(0)]\right)
\end{split}
\]
Noting that $\langle\nabla f(x^k), u^k - x^k\rangle < 0$ (thanks to Remark~\ref{term:step1} and the fact that $x^k$ is not a stationary point of \eqref{P0}), $c\in (0,1)$ and that $\lim_{\alpha\downarrow 0}\psi'(t_\alpha) = \psi'(0)$ (thanks to the continuity of $\nabla f$), we conclude that \eqref{linesearch} is satisfied for all sufficiently small $\alpha > 0$.

(iii): Recall from \eqref{constrain} that $x^k\in {\cal F}(x^k,\xi^k)$. Moreover, since $u^k$ is an output of ${\cal LO}(\nabla f(x^k), x^k, \xi^k)$, we also have $u^k\in {\cal F}(x^k,\xi^k)$. These together with $\alpha_k\in(0,1]$ and the convexity of ${\cal F}(x^k,\xi^k)$ imply that
\[
\widehat x^{k+1} := x^k + \alpha_k(u^k - x^k) = \alpha_k u^k +(1-\alpha_k)x^k \in {\cal F}(x^k,\xi^k)\subseteq\mathcal{F}.
 \]
Then an $x^{k+1}\in {\cal F}$ can be generated at the end of the $(k+1)$th iteration of Algorithm~\ref{FW_nonconvex}, since we can at least choose $x^{k+1} := \widehat x^{k+1}$.
\end{proof}
\begin{remark}[Choice of $ x^{k+1} $]
From Proposition~\ref{Prop1}, we see that one can always choose $x^{k+1} = \widehat x^{k+1}$. Here, observing that the constraint functions are all positively homogeneous (as the difference of two norms) in the examples we discussed in Sections~\ref{gl} and \ref{mc}, we introduce a boundary boosting technique to choose $ x^{k+1} $ for those examples. The main idea is to leverage the positive homogeneity of $ P_1-P_2 $. Specifically, if $ c_1 := P_1(\widehat x^{k+1}) - P_2(\widehat x^{k+1})< \sigma $ and $ c_1>0 $, we define $ \widetilde{x}^{k+1} = \frac{\sigma}{c_1}\widehat x^{k+1} $. It follows that $ P_1(\widetilde x^{k+1}) - P_2(\widetilde x^{k+1}) = \frac{\sigma}{c_1}(P_1(\widehat x^{k+1}) - P_2(\widehat x^{k+1})) = \sigma $. Then we choose
\begin{equation}\label{choosexk+1}
	x^{k+1} = \begin{cases}
	\widetilde x^{k+1} & \text{if}\;  c_1>0 \;\text{and}\; f(\widetilde x^{k+1}) \leq f(\widehat x^{k+1}), \\
	\widehat{x}^{k+1} & \text{otherwise}.
	\end{cases}
\end{equation}
\end{remark}

We next show that the sequence $\{x^k\}$ generated by Algorithm~\ref{FW_nonconvex} clusters at a stationary point of \eqref{P0}. Notice from Remark~\ref{term:step1} and Proposition~\ref{Prop1} that $\{x^k\}$ is either an infinite sequence or is a finite sequence that ends at a stationary point of
\eqref{P0}. Without loss of generality, we assume that $\{x^k\}$ is an infinite sequence.
\begin{theorem}[Subsequential convergence]\label{thm-fw}
Consider \eqref{P0} and suppose that Assumption~\ref{assumption1} holds. Let $\{x^k\}$ be an infinite sequence generated by
Algorithm~\ref{FW_nonconvex} and let $G$ be defined as in \eqref{defG}. Then the sequence $\{x^k\}$ is bounded and $G(x^k) \rightarrow 0$ as $k \rightarrow \infty$. Moreover, any accumulation point of $ \{x^k\} $ is a stationary point of \eqref{P0}.
\end{theorem}
\begin{proof}
The boundedness of $\{x^k\}$ follows from the boundedness of $\mathcal{F}$ and the fact that $\{x^k\}\subseteq\mathcal{F}$. Next, we recall from the definition that $u^{k}$ is an output of ${\cal LO}(\nabla f(x^{k}), x^{k}, \xi^{k})$. This shows that
\[
0 \le G(x^{k})\le \max_{y \in \mathcal{F}(x^{k}, \xi^{k})} \langle \nabla f(x^{k}), x^{k}-y\rangle = \langle \nabla f(x^{k}), x^{k}-u^{k}\rangle,
\]
where the first inequality follows from Theorem~\ref{lemma:1}(i) and the fact that $x^{k} \in \mathcal{F}$. In addition, in view of Remark~\ref{term:step1}, we deduce from Lemma \ref{Armijolemma} (with $\Gamma:= \mathcal{F}$) that
\[
\lim_{k\to\infty}\langle \nabla f(x^{k}), u^{k}-x^{k}\rangle =  0.
\]
Thus, we have $G(x^{k}) \rightarrow 0$. Now it follows directly from Theorem~\ref{lemma:1}(ii) that any accumulation point of $ \{x^k\} $ is a stationary point of \eqref{P0}.
\end{proof}

\subsection{The case when $P_1$ is strongly convex}
We now consider the case where $P_1$ in \eqref{P0} is a strongly convex function. We consider the following additional assumption.
\begin{assumption}\label{ass:nonzerograd}
  In \eqref{P0}, it holds that $\nabla f(x)\neq 0$ for all $x\in {\cal F}$ and $\nabla f$ is Lipschitz continuous on ${\cal F}$, i.e., there exists $L > 0$ such that
  \[
   \|\nabla f(x) - \nabla f(y)\|\le L\|x - y\|\ \ {\rm whenever}\ x,y\in {\cal F}.
  \]
\end{assumption}
The Lipschitz continuity requirement on $\nabla f$ in Assumption~\ref{ass:nonzerograd} is standard when it comes to complexity analysis of first-order methods; see, for example, \cite{Ne04}.
Moreover, the condition of nonvanishing gradient in Assumption~\ref{ass:nonzerograd} eliminates the ``uninteresting" situation where a feasible point of problem~\eqref{P0} is a stationary point of the {\em unconstrained} problem $\min_{x \in {\mathbb{X}}} f(x)$.

\begin{proposition}\label{Prop5.2}
Consider \eqref{P0} with $P_1$ being strongly convex. Suppose that Assumptions~\ref{assumption1} and \ref{ass:nonzerograd} hold. Let $\{\alpha_k\}$ and $\{d^k\}$ be two infinite sequences generated by
Algorithm~\ref{FW_nonconvex}. Then
\[
\sum_{k=0}^{\infty}  \|d^k\|^2 <+\infty\ \ {  and}\ \ \inf_k\alpha_k > 0.
\]
\end{proposition}
\begin{proof}
Since $u^{k}$ is an output of ${\cal LO}(\nabla f(x^{k}), x^{k}, \xi^{k})$ and Assumption~\ref{assumption1} holds, by \cite[Corollary~28.2.1, Theorem~28.3]{Ro70}, there exist $\lambda_k \ge 0$ and $w^k \in \partial P_1(u^k)$ such that
\begin{equation}\label{eq:KKT0}
\begin{array}{rl}
  &\nabla f(x^k)+ \lambda_k (w^k- \xi^k)=0,\\ [2 pt]
  &\lambda_k (P_1(u^k)- \langle \xi^k, u^k-x^k \rangle -P_2(x^k)-\sigma)=0.
\end{array}
\end{equation}

We claim that $\underline{\lambda}:=\inf\{\lambda_k: k \in \mathbb{N}\}>0$. Suppose not, by passing to subsequences if necessary, we may assume that $\lambda_k \rightarrow 0$ and $x^k \rightarrow x^*$ for some $x^*$. Note that $x^*\in {\cal F}$. Passing to the limit in the first relation of \eqref{eq:KKT0} and noting that $\{w^k\}$ and $\{\xi^k\}$ are bounded (thanks to the boundedness of $\{x^k\}$, $\{u^k\}$, the continuity of $P_1$ and $P_2$, and \cite[Theorem~2.6]{Tuy98}), we have
\[
\nabla f(x^*)=0.
\]
This contradicts Assumption~\ref{ass:nonzerograd}. Thus, $\underline{\lambda}=\inf\{\lambda_k: k \in \mathbb{N}\}>0$.

Next, let $\rho > 0$ denote the modulus of strong convexity of $P_1$. Using \eqref{eq:KKT0}, we have
\begin{eqnarray}\label{eq:ineq}
&&\langle \nabla f(x^k), u^k-x^k\rangle  =   \langle -\lambda_k (w^k- \xi^k), u^k-x^k\rangle \notag \\
&& =  \lambda_k  \langle w^k, x^k-u^k\rangle + \lambda_k  \langle \xi^k, u^k-x^k\rangle \notag \\
&& \le  \lambda_k (P_1(x^k)-P_1(u^k) -\frac{\rho}{2}\|x^k-u^k\|^2) + \lambda_k (P_1(u^k)-P_2(x^k)-\sigma) \notag \\
&& =  \lambda_k(P_1(x^k)-P_2(x^k)-\sigma) - \frac{\rho \lambda_k}{2}\|x^k-u^k\|^2 \le  - \frac{\rho \underline{\lambda}}{2}\|x^k-u^k\|^2.
\end{eqnarray}
where the first inequality holds in view of the second relation of \eqref{eq:KKT0} and the definition of $\rho$, and the last inequality holds because $x^k \in \mathcal{F}$.
This together with the definition of $x^{k+1}$ and \eqref{linesearch} shows that
\[
f(x^{k+1}) \le f(\widehat{x}^{k+1}) \le f(x^k) + c\alpha_k\langle\nabla f(x^k), u^k - x^k\rangle  \le f(x^k) - c\alpha_k\frac{\rho \underline{\lambda}}{2}\|x^k-u^k\|^2.
\]
Note that $\{x^k\} \subseteq \mathcal{F}$ (so that $\inf_k f(x^k) > -\infty$). Using this and summing the above display from $k = 0$ to $\infty$, we see further that
\begin{equation}\label{hahahaha2}
\sum_{k=0}^{\infty} \alpha_k  \|d^k\|^2=\sum_{k=0}^{\infty} \alpha_k  \|x^k-u^k\|^2 <+\infty.
\end{equation}

We now show that $\inf_k\alpha_k>0$. To see this, first recall from \eqref{constrain} that $x^k\in {\cal F}(x^k,\xi^k)$, and note from the definition that $u^k\in {\cal F}(x^k,\xi^k)$. Moreover, since ${\cal F}(x^k,\xi^k)$ is convex, we have $x^k+ \alpha (u^k-x^k) \in {\cal F}(x^k,\xi^k) \subseteq {\cal F}$ for all $\alpha\in [0,1]$. Then, for any $\alpha\in [0,1]$, with $L$ as in Assumption~\ref{ass:nonzerograd}, we have
\begin{align*}
&f(x^k+ \alpha (u^k-x^k))  \le  f(x^k) + \alpha \langle \nabla f(x^k), u^k-x^k\rangle+ \frac{L \alpha^2}{2}\|u^k-x^k\|^2 \\
& =  f(x^k) + c \alpha \langle \nabla f(x^k), u^k-x^k\rangle \\
& \ \ \ \ +\bigg[(1-c)\alpha \langle \nabla f(x^k), u^k-x^k\rangle + \frac{L \alpha^2}{2}\|u^k-x^k\|^2\bigg] \\
& \le  f(x^k) + c \alpha \langle \nabla f(x^k), u^k-x^k\rangle + \alpha  \|u^k-x^k\|^2 \,  \bigg[- \, \frac{(1-c) \rho \underline{\lambda}}{2}  + \frac{L \alpha}{2}\bigg],
\end{align*}
where the last inequality follows from \eqref{eq:ineq}.
This shows that the line search criterion \eqref{linesearch} will be satisfied as long as
$\alpha \le \frac{(1-c)\rho \underline{\lambda}}{L}$.
Consequently, we have
$\alpha_k \ge \min\{ \alpha_k^0, \frac{(1-c)\rho \underline{\lambda} \eta}{L} \}$,
and so $\inf_k\alpha_k \ge \min\{ \inf_{k}\alpha_k^0, \frac{(1-c)\rho \underline{\lambda} \eta}{L}\}>0$.
The desired conclusion now follows immediately from this and \eqref{hahahaha2}.
\end{proof}

Next, we derive a $o(1/k)$ complexity in terms of the stationarity measure $G$ defined in \eqref{defG} under the strong convexity of $P_1$.
\begin{theorem}
Consider \eqref{P0} with $P_1$ being strongly convex. Suppose that Assumptions~\ref{assumption1} and \ref{ass:nonzerograd} hold. Let $\{x^k\}$ be an infinite sequence generated by
Algorithm~\ref{FW_nonconvex} and let $G$ be defined as in \eqref{defG}. Then
\[
\sum_{k=0}^{\infty}  G(x^k) <+\infty \ \mbox{ and }\ k \big[\min_{0 \le t \le k} G(x^t) \big] \rightarrow 0.
\]
\end{theorem}
\begin{proof}
Recalling that $u^k$ is an output of ${\cal LO}(\nabla f(x^{k}), x^{k}, \xi^{k})$, where $\xi^k \in \partial P_2(x^k)$, we have
\[
G(x^k)\le \max_{y \in \mathcal{F}(x^k, \xi^k)} \langle \nabla f(x^k), x^k-y\rangle = \langle \nabla f(x^k), x^k-u^k\rangle
\]
This together with the definition of $x^{k+1}$ implies that
\[
f(x^{k+1})-f(x^k) \le f(\widehat{x}^{k+1})-f(x^k) \le c \alpha^k \langle \nabla f(x^{k}), u^k-x^k\rangle \le - c \alpha^k G(x^k).
\]
Summing the above display from $k = 0$ to $\infty$ and recalling $\inf_k f(x^k) > -\infty$ (since $\{x^k\}\subseteq {\cal F}$), we see that $\sum_{k=0}^{\infty} \alpha_k G(x^k)<\infty$.
Since $\inf_k\alpha_k > 0$ from Proposition~\ref{Prop5.2} and $G(x^k)\ge 0$ (see Theorem~\ref{lemma:1}(i)), we deduce further that
$\sum_{k=0}^{\infty} G(x^k)<\infty$.

Finally, let $a_k=\min_{0 \le t \le k} G(x^t)$. Then $\{a_k\}$ is nonnnegative (see Theorem~\ref{lemma:1}(i)) and non-increasing. On the other hand, the Cauchy criterion for the convergent series gives $\lim_{k\to\infty}\sum_{t=k}^{2k} G(x^t) = 0$. This implies that
\[
(k+1) \, a_{2k} \le G(x^k)+\ldots + G(x^{2k}) = \sum_{t=k}^{2k} G(x^t) \rightarrow 0
\]
Similarly, one can show that $\lim_{k\to\infty}(k+1)a_{2k+1}= 0$.
Thus, we have $\lim_{k\to\infty}k a_{k} = 0$ as desired.
\end{proof}

\section{Away-step Frank-Wolfe type algorithm}\label{sec6}
When $f$ and $C$ in \eqref{P00} are convex and $C = {\rm conv}(\mathcal A) $ for some finite set $ \mathcal A $ (whose elements are called atoms), the so-called away-step technique was proposed in \cite{Guelat86} to accelerate the convergence of FW method; see \cite{Lacoste15, Garber16, Clarkson10} for recent developments. The key ingredient in the away-step technique is to keep track of \emph{a convex decomposition of the current iterate into atoms in $ \mathcal A $}. The away step then selects one atom from the current decomposition that ``differs" most from the gradient direction. The FW method with away step requires to maintain the set of the ``active" atoms used in the aforementioned decomposition and update this active set in each iteration (see \cite[Algorithm~1]{Lacoste15} for more details).

In our nonconvex settings, the feasible set of ${\cal LO}$ is not necessarily a convex hull of finitely many atoms, and it can vary from iteration to iteration. In particular, the active atoms used for the current iteration may be infeasible for the subproblem of the next iteration. It seems difficult to maintain the decomposition with a uniform atomic set $ \mathcal A $ and possibly meaningless to update the decomposition based on previous information. In view of this, we do not store atoms used in the decompositions of previous iterates, but generate a new set of atoms in each iteration based on the current iterate. Below we describe the details of how to decompose the iterate and construct away-step oracles for our FW method for \eqref{P0}.

We first introduce our away-step oracle, which mimics the away step used in the classical FW method.

\begin{definition}[Away-step oracles]\label{awdef}
Let $P_1$, $P_2$ and $\sigma$ be defined in \eqref{P0}, $ y\in\mathcal F $ and $ \xi\in\partial P_2(y) $.
Given $ a\in{\mathbb{X}}\setminus\{0\} $, choose a set
\begin{equation}\label{Sy}
	\mathcal S(y, \xi)=\left\{v_1,\ldots, v_{m_y} \right\}\subseteq {{\rm bdry}\,} {\cal F}(y,\xi)
\end{equation}
so that $ y = \sum_{i=1}^{m_y} c_i v_i $ for some $ c_1,\ldots,c_{m_y}>0$ satisfying $ \sum_{i=1}^{m_y} c_i = 1$, where $1\le m_y\leq n+1 $ with $ n $ being the dimension of $ {\mathbb{X}} $.
We define the away-step oracle $ {\cal AWO}(a, \mathcal S(y,\xi)) $ as
\begin{equation}\label{aw-step}
\begin{array}{cl}
\max\limits_{x\in {\mathbb{X}}} & \langle a, x \rangle \ \ \ \
{\rm s.t.} \ \ x \in {\rm conv}(\mathcal{S}(y, \xi)).
\end{array}
\end{equation}
\end{definition}

The choice of the set $ \mathcal S(y, \xi) $ is essential for $ {\cal AWO}(a, \mathcal S(y,\xi)) $. Specific strategies of choosing $ \mathcal S(y,\xi) $ and how the $ {\cal AWO} $ can be carried out efficiently for some concrete examples will be discussed in Section~\ref{sec:aw3exs}. Here, we first comment on the existence of such $ \mathcal S(y,\xi) $.

\begin{remark}[Existence of $S(y,\xi)$]\label{remark1}
Since $y\in {\cal F}$ and $ \xi\in\partial P_2(y) $ in Definition~\ref{awdef}, we see from \eqref{constrain} that $y \in {\cal F}(y,\xi)$. Since ${\cal F}(y,\xi)$ is compact and convex, it is the convex hull of all its extreme points; in particular, ${\cal F}(y,\xi) = {\rm conv}\, ({{\rm bdry}\,} {\cal F}(y,\xi))$.
The existence of $v_i$ and $c_i$ in Definition~\ref{awdef} now follows from this and the Carath\'{e}odory's theorem.
\end{remark}

Next, we note that ${\cal AWO}$ is well-defined, because it is solving a maximization problem with a linear objective and a nonempty compact feasible set. We register this simple observation as our next proposition.
\begin{proposition}[Well-definedness of ${\cal AWO}$]
Consider \eqref{P0}. For any fixed $ y\in \mathcal{F} $, $ \xi\in \partial P_2(y) $ and any set $ \mathcal S(y,\xi) $ given as in \eqref{Sy}, the away-step oracle $ {\cal AWO}(\nabla f(y), \mathcal S(y,\xi)) $ in \eqref{aw-step} is well-defined.
\end{proposition}

We now present our Frank-Wolfe type algorithm with away step as Algorithm~\ref{alg:aw-fw} to enhance Algorithm~\ref{FW_nonconvex} for solving \eqref{P0} under Assumption~\ref{assumption1}.
\begin{algorithm}
	\caption{Away-step Frank-Wolfe type algorithm for \eqref{P0} under Assumption~\ref{assumption1}}\label{alg:aw-fw}
	\begin{algorithmic}
		\State \vspace{-0.25 cm}
		\begin{description}
			\item[\bf Step 0.] Choose $x^0\in \mathcal{F}$, $ 0<\epsilon< \zeta < \infty$, $c,\,\eta\in (0, 1)$ and a sequence $ \{\alpha_k^0\}\subseteq (0,1] $ with $\inf_k \alpha_k^0 > 0$. Set $k = 0$.\vspace{0.1 cm}

			\item[\bf Step 1.] Pick $\xi^k\in\partial P_2(x^k)$. Compute $ u^k_{\rm fw}$ by calling ${\cal LO}(\nabla f(x^k),x^k, \xi^k)$ (see Definition~\ref{LOdef}) and set $ d_{\rm fw}^k := u^k_{\rm fw} - x^k $.

\noindent If $ \langle \nabla f(x^k), u_{\rm fw}^k-x^k\rangle = 0 $, terminate. \vspace{0.1 cm}

			\item[\bf Step 2.] Choose $ \mathcal S(x^k, \xi^k) $ as in \eqref{Sy} and call $ {\cal AWO}(\nabla f(x^k),\mathcal S(x^k, \xi^k)) $  (see Definition~\ref{awdef}) to compute $ u^k_{\rm aw} $.
Set $ d^k_{\rm aw} := x^k - u^k_{\rm aw} $ and choose an $ \alpha^k_{\rm aw}\le \max\left\{\alpha\geq 0:\; x^k+\alpha d^k_{\rm aw} \in {\rm conv}(\mathcal S(x^k,\xi^k)) \right\} $.\vspace{0.1 cm}

			\item[\bf Step 3.] If $ \langle \nabla f(x^k), d^k_{\rm fw}\rangle > \langle \nabla f(x^k), d^k_{\rm aw}\rangle $ and $\alpha_{\rm aw}^k\in(\epsilon, \zeta] $, set $ d^k =  d^k_{\rm aw} $ and $ \widetilde\alpha_k^0  = \alpha_{\rm aw}^k $; we declare that an AW step is taken.\vspace{0.1 cm}

\noindent Otherwise,  set $ d^k = d^k_{\rm fw}$ and $\widetilde \alpha^0_k = \alpha^0_k$; we declare that an FW step is taken.\vspace{0.1 cm}

			\item[\bf Step 4.] Find $ \alpha_k = \widetilde \alpha_k^0\eta^{j_k} $ with $ j_k $ being the smallest nonnegative integer such that
			\begin{equation}\label{ls_awfw}
			  f(x^k + \alpha_k d^k) \le f(x^k) + c\alpha_k\langle\nabla f(x^k), d^k \rangle.
			\end{equation}
			\item[\bf Step 5.] Set $\widehat x^{k+1} = x^k + \alpha_k d^k$. Choose $ x^{k+1}\in\mathcal F $ such that $ f(x^{k+1})\leq f(\widehat x^{k+1}) $. Update $k \leftarrow k+1$ and go to Step 1.
		\end{description}
	\end{algorithmic}
\end{algorithm}

\begin{remark}[{Well-definedness of Algorithm~\ref{alg:aw-fw}}]\label{welldefined:Alg2}
Similar to Proposition~\ref{Prop1}, we can argue the well-definedness of Algorithm~\ref{alg:aw-fw} as follows: Suppose that a nonstationary $x^k\in {\cal F}$ is given for some $k \ge 0$. Note that $\langle \nabla f(x^k), u_{\rm fw}^k-x^k\rangle\le 0$ because $x^k \in {\cal F}(x^k,\xi^k)$. Since $x^k$ is not stationary, we further have $\langle \nabla f(x^k), u_{\rm fw}^k-x^k\rangle< 0$ in view of Lemma~\ref{equistat}. Then the rule of choosing $d^k$ in Step~3 of Algorithm~\ref{alg:aw-fw} yields $ \langle \nabla f(x^k), d^k\rangle < 0 $. Therefore, one can show similarly as in Proposition~\ref{Prop1} that the line-search subroutine in Step~4 of Algorithm~\ref{alg:aw-fw} can terminate in finitely many inner iterations. Furthermore, from the definition of $\alpha_k$, one can deduce that $ \widehat{x}^{k+1} \in\mathcal F(x^k,\xi^k)\subseteq {\cal F} $. Then an $ x^{k+1} \in {\cal F}$ can be generated at the end of the ($k+1$)th iteration of Algorithm~\ref{alg:aw-fw}, since we can at least choose $ x^{k+1}:=\widehat{x}^{k+1} $.
\end{remark}

We next show that the sequence $\{x^k\}$ generated by Algorithm~\ref{alg:aw-fw} clusters
at a stationary point of \eqref{P0}. From the discussion in Remarks~\ref{term:step1} and \ref{welldefined:Alg2}, we see that $\{x^k\}$ is either an infinite sequence or is a finite sequence that terminates at a stationary point of \eqref{P0}. Without loss of generality, we assume that $\{x^k\}$ is an infinite sequence.

\begin{theorem}[Subsequential convergence]\label{thm-fw-aw}
Consider \eqref{P0} and suppose that Assumption~\ref{assumption1} holds. Let $ \{x^k\} $ be an infinite sequence generated by
Algorithm~\ref{alg:aw-fw}. Then $ \{x^k\} $ is bounded and every accumulation point of $ \{x^k\} $ is a stationary point of \eqref{P0}.
\end{theorem}
\begin{proof}
Note that $\{x^k\}$ is bounded because $\{x^k\}\subseteq {\cal F}$. Similarly, $\{u^k_{\rm aw}\}$ and $\{u^k_{\rm fw}\}$ are bounded, and we also have the boundedness of $\{\xi^k\}$ in view of \cite[Theorem~2.6]{Tuy98}, the continuity of $P_2$ and the boundedness of $\{x^k\}$.

Next, observe from Step 3 of Algorithm~\ref{alg:aw-fw}, the descent property of the FW direction (i.e., $\langle \nabla f(x^k), u^k_{\rm fw} -x^k \rangle \leq \langle \nabla f(x^k), x^k -x^k\rangle = 0$ for all $k$) and the assumption that $\{x^k\}$ is an infinite sequence (so that $\langle \nabla f(x^k), u^k_{\rm fw} -x^k \rangle < 0$ according to Step 1)
that $ d^{k} $ is a descent direction for every $ k $, i.e., $ \langle \nabla f(x^k), d^k\rangle < 0 $ for every $ k $. In view of this, \eqref{ls_awfw} and Lemma~\ref{Armijolemma} (with $\Gamma:= \mathcal{F}$), we have
\begin{equation}\label{limitf}
\lim_{k\to\infty}\langle \nabla f(x^k), d^k\rangle = 0.
\end{equation}

Now, let $x^*$ be an accumulation point of $\{x^k\}$. Then, in view of the boundedness of $ \{(x^k,\xi^k,u^k_{\rm aw},u^k_{\rm fw})\} $, there exists a subsequence $ \{(x^{k_t},\xi^{k_t},u^{k_t}_{\rm aw},u^{k_t}_{\rm fw})\} $ that
converges to $ (x^*, \xi^*, u^*_{\rm aw} , u^*_{\rm fw}) $ for some $\xi^*\in\partial P_2(x^*)$ (thanks to the closedness of $\partial P_2$), $u^*_{\rm aw}\in {\cal F}$ and $u^*_{\rm fw}\in {\cal F}$. We consider two cases.

{\bf Case 1}: Suppose that $ \{x^{k_t}\} $ is followed by infinitely many FW steps and finitely many AW steps. By passing to a further subsequence, we assume without loss of generality that $ x^{k_t} $ is followed by an FW step for all $t$, i.e., $d^{k_t} = u^{k_t}_{\rm fw} - x^{k_t}$ for all $t$. Since $u^k_{\rm fw}$ is an output of ${\cal LO}(\nabla f(x^k),x^k,\xi^k)$, we have from the definition of $G$ in \eqref{defG} and \eqref{limitf} that
\[
0 \le G(x^{k_t})\le \langle \nabla f(x^{k_t}), x^{k_t}-u^{k_t}_{\rm fw}\rangle = - \langle \nabla f(x^{k_t}), d^{k_t}\rangle \to 0.
\]
This together with Theorem~\ref{lemma:1}(ii) shows that $x^*$ is a stationary point of \eqref{P0}.

{\bf Case 2}: Suppose that the AW step is invoked infinitely many times in $ \{x^{k_t}\} $.
Passing to a further subsequence, we assume without loss of generality that $ x^{k_t} $ is followed by an AW step for all $ t $, i.e., $d^{k_t} = x^{k_t} - u^{k_t}_{\rm aw}$ for all $t$. Then in view of Step 3, we have
\begin{equation}\label{dirule}
\langle \nabla f(x^{k_t}), x^{k_t}-u^{k_t}_{\rm aw}\rangle = \langle \nabla f(x^{k_t}), d^{k_t}\rangle < \langle \nabla f(x^{k_t}), u^{k_t}_{\rm fw}-x^{k_t}\rangle.
\end{equation}
Now, recalling the definition of $G$ in \eqref{defG} and the facts that $\xi^{k_t} \in \partial P_2(x^{k_t})$ and $u^{k_t}_{\rm fw}$ is an output of ${\cal LO}(\nabla f(x^k),x^k, \xi^k)$, we deduce further that
\[
\begin{aligned}
0\le G(x^{k_t})&\le \max_{y \in \mathcal{F}(x^{k_t}, \xi^{k_t})} \langle \nabla f(x^{k_t}), x^{k_t}-y\rangle = \langle \nabla f(x^{k_t}), x^{k_t}-u^{k_t}_{\rm fw}\rangle \\
& \le - \langle \nabla f(x^{k_t}), x^{k_t}-u^{k_t}_{\rm aw}\rangle = - \langle \nabla f(x^{k_t}), d^{k_t}\rangle \rightarrow 0,
\end{aligned}
\]
where the second inequality follows from \eqref{dirule} and the last relation follows from \eqref{limitf}.
This together with Theorem~\ref{lemma:1}(ii) implies that $ x^* $ is a stationary point of problem~\eqref{P0}. This completes the proof.
\end{proof}

\subsection{{$ {\cal AWO} $} for $P_1$ and $P_2$ as in Assumption~\ref{assump31} or \ref{assump32}}\label{sec:aw3exs}
In this section, we discuss how to construct the set $ \mathcal S(y,\xi) $ and obtain a solution for ${\cal AWO}$ when $ P_1 $ and $ P_2 $ are described as in Assumption~\ref{assump31} or \ref{assump32}.

Note that the $ P_1 $ in Assumption~\ref{assump31} or \ref{assump32} are ``atomic norms" that can be written as a gauge function of the form:
\begin{equation}\label{atomic}
\|x\|_\mathcal{A} = \inf\{t\geq 0:\; x\in t\;{\rm conv}(\mathcal{A}) \}
\end{equation}
for some symmetric compact atomic set $\mathcal{A}\subseteq {\mathbb{X}} $ with $0 \in {\rm conv}({\cal A})$. For more discussions on atomic norm, we refer the readers to \cite{Chandrasekaran10}. Below, we list the atomic sets for the $P_1$ in the two scenarios discussed in Assumptions \ref{assump31} and \ref{assump32}.
\begin{itemize}
	\item {\bf Scenario~1.} $ \mathcal{A}_{\rm gl} = \bigcup_{J\in{\cal J}}\mathcal{A}_J$ with
\[
\mathcal A_{J} = \{x:\,\|x_{J}\| = 1,\; x_I= 0, \forall I\in \mathcal J\setminus \{J\} \}
\]
for each $ J\in\mathcal J $, where $ \mathcal J $ is a partition of $ \{1,\ldots, n\} $. This corresponds to $ P_1(x) = \sum_{J\in\mathcal J} \|x_{J}\| $ (see \cite[Corollary~2.2]{RaoRecht12}) in Assumption~\ref{assump31}.
	\item {\bf Scenario~2.} $ \mathcal A_* = \{uv^T:\; u\in{\rm I\!R}^m, v\in{\rm I\!R}^n \;{\rm with}\;\|u\| = \|v\| = 1 \} $. This corresponds to $ P_1(X) = \|X\|_* $ (see \cite[Section~2.2]{Chandrasekaran10}) in Assumption~\ref{assump32}.
\end{itemize}
For the rest of this section, we will focus on \eqref{atomic} with ${\cal A} = {\cal A}_{\rm gl}$ or ${\cal A}_*$.
Based on these two atomic sets, we first construct a set that provides potential choices for the elements of $ \mathcal S(y,\xi) $ in ${\cal AWO}$ for problems in Sections~\ref{gl} and \ref{mc}.
\begin{proposition}\label{atomprop}
	Consider \eqref{P0}. Let $ P_1 = \|\cdot\|_{\mathcal A} $ as in \eqref{atomic} with ${\cal A} = {\cal A}_{\rm gl}$ or ${\cal A}_*$, and let $ P_2 $ be a norm function such that $ P_2\leq \mu P_1$ for some $ \mu \in[0,1) $. Given $ y\in\mathcal F $ and $ \xi\in\partial P_2(y) $, let
	\[
	\mathcal V(y,\xi) = \left\{\frac{{\sigma}s}{1-\langle \xi, s\rangle}:\; s\in {\cal A} \right\}.
	\]
    Then the following statements hold:
	\begin{enumerate}[{\rm (i)}]
		\item For any $ s \in {\cal A}$, we have $ 1-\langle\xi, s\rangle >0 $;
		\item For any $ v\in\mathcal{V}(y,\xi) $, it holds that
\[\|v\|_\mathcal{A} - P_2(y) - \langle \xi, v - y\rangle = \|v\|_\mathcal{A} - \langle \xi, v \rangle =\sigma.\]
	\end{enumerate}
\end{proposition}
\begin{proof}
	For notational simplicity, we write $ P_2(x)= \mu \gamma(x) $ for some norm function $\gamma$, and use $ \gamma^\circ $ to denote the dual norm of $ \gamma $. Since $ \xi\in\partial P_2(y) $, we see that $ \gamma^\circ(\xi)\leq \mu $. Since we have $\|s\|_{\cal A} = 1$ for all $s\in {\cal A}$ (recall that ${\cal A} = {\cal A}_{\rm gl}$ or ${\cal A}_*$), it follows that
	\begin{equation*}
	\begin{split}
	&1-\langle\xi, s\rangle \geq \|s\|_\mathcal{A} - \gamma^\circ(\xi)\gamma(s)\geq \|s\|_\mathcal{A}-\mu \gamma(s) = P_1(s)- P_2(s) \\
	&\overset{\rm (a)}\geq P_1(s)-\mu P_1(s) = 1-\mu >0,
	\end{split}
	\end{equation*}
	where the first inequality and the last equality holds because $P_1(s) = \|s\|_\mathcal{A}=1 $, and (a) holds because $ P_2\leq \mu P_1  $. This proves (i).

	We now prove (ii). Fix any $ v\in\mathcal{V}(y,\xi) $. Then we have
	\begin{equation*}
	\begin{split}
	&\|v\|_\mathcal{A} - P_2(y)- \langle\xi, v-y\rangle= \frac{{\sigma}\left(\|s\|_\mathcal{A} -\langle \xi, s\rangle \right)}{1-\langle \xi, s\rangle} -P_2(y) +\langle \xi, y\rangle \\
	&\overset{\rm (a)}= \sigma - P_2(y) +\langle\xi,y\rangle \overset{\rm (b)}= \sigma,
	\end{split}
	\end{equation*}
	where (a) holds since $ \|s\|_\mathcal{A} = 1 $, and (b) holds as $P_2$ is a norm and $\xi\in \partial P_2(y)$.
\end{proof}
In the next two subsections, we will present a strategy of choosing $ \mathcal{S}(y,\xi) $ in {\bf Scenarios 1} and {\bf 2}, and discuss how to determine the stepsize $ \alpha_{\rm aw} $ in Step~2 in Algorithm~\ref{alg:aw-fw}. Here, we first exclude the case $ y=0 $: In this case, the away-step direction $ d_{\rm aw} $ will always be inferior to $ d_{\rm fw} $ in Step~3 if we choose $ \xi=0 $ (note that $ 0\in\partial P_2(0) $ since $P_2$ is a norm). To see this, note that $ \mathcal{F}(0,0)=\{x:\; \|x\|_\mathcal{A}\leq \sigma \} $. Therefore, we have
\[
\langle \nabla f(0), 0 - u_{\rm aw} \rangle = \langle \nabla f(0), (-u_{\rm aw}) - 0\rangle \geq \langle \nabla f(0), u_{\rm fw}-0\rangle,
\]
where we use the facts that $ -u_{\rm aw}\in\mathcal{F}(0,0) $ (thanks to the symmetry of $ \mathcal{F}(0,0) $) and $ u_{\rm fw} $ is the output of ${\cal LO}(\nabla f(0),0,0)$ for the last inequality. In other words, if $x^k = 0$ and is not stationary, and if we set $\xi^k = 0$, then $d^k = u^k_{\rm fw} - x^k$.

\subsubsection{Constructing $ \mathcal S(y, \xi) $ in ${\cal AWO}$ in Step 2 of Algorithm~\ref{alg:aw-fw}} \label{sec:syxi}

Let $ P_1 $ and $ P_2 $ be as in Assumption~\ref{assump31} or \ref{assump32}. As discussed before, these $ P_1 $ can be written as $ P_1=\|\cdot\|_\mathcal A $ with ${\cal A} = {\cal A}_{\rm gl}$ or ${\cal A}_*$.

We now discuss the choice of ${\cal S}(y,\xi)$ in \eqref{aw-step} when $y\in\mathcal{F}\setminus\{0\}$. To this end, fix any $ y\in\mathcal{F}\setminus\{0\}$ and pick $ \xi\in\partial P_2(y)$. From the definition of the atomic norm \eqref{atomic}, there exist a positive integer $ m\leq n+1 $, a set of atoms $ \{s_i\}_{i=1}^m\subset \mathcal A $ and nonnegative coefficients $ \{r_i\}_{i=1}^m $ such that
\begin{equation}\label{atomrep}
 y = \|y\|_\mathcal{A} \sum\limits_{i=1}^m r_i s_i \;\text{and}\;  \sum\limits_{i=1}^m r_i =1 .
\end{equation}
Specifically, for ${\cal A} = {\cal A}_{\rm gl}$ and ${\cal A}_*$ in {\bf Scenarios 1} and {\bf 2}, respectively, we can derive the representation in \eqref{atomrep} with
\begin{enumerate}[{\rm (i)}]
	\item $ m = \lvert\mathcal{J}\rvert, $ $ r_i = \|y_{J_i}\|/\sum_{i=1}^m \|y_{J_i}\| $ and $ s_i = {\rm Sgn}(y_{J_i}) $ for $ i = 1,\ldots,m $, where we number the elements of ${\cal J}$ as $\{J_1,\ldots,J_m\}$,  $ y=[y_{J_i}]_{i=1}^m\in{\rm I\!R}^n $ and ${\rm Sgn}$ is defined in \eqref{sign};
	\item $ m = {\rm rank}(Y)$, $ r_i = \lambda_i/\|Y\|_* $ and $ s_i = u_iw_i^T $ for $ i=1, \ldots, {\rm rank}(Y) $, where $ u_i $'s (resp., $ w_i $'s) are columns of $ U $ (resp., $ W $) from the thin SVD of $ Y= U\Lambda W^T $, and $ \lambda_i $'s are the diagonal entries of $ \Lambda $.
\end{enumerate}

With respect to \eqref{atomrep}, we define $ \mathcal I_y:=\{i:\, r_i\neq 0, i=1, \ldots, m\} $ and
\begin{equation}\label{vicidef}
v_i := \frac{\sigma s_i}{1-\langle\xi, s_i\rangle}, \;{\rm and}\;   c_i := \dfrac{r_i\|y\|_\mathcal{A}(1-\langle\xi, s_i\rangle)}{\sigma},\quad  \forall i=1, \ldots, m.
\end{equation}
It then follows that
\begin{equation}\label{ydcomp1}
y = \sum\limits_{i=1}^m c_i v_i = \sum\limits_{i\in\mathcal I_y} c_i v_i.
\end{equation}
Now, using Proposition~\ref{atomprop} and the definition of $ c_i $ and $ v_i $ in \eqref{vicidef}, and recalling that $ y\neq 0 $ and $ r_i>0 $ for every $ i\in\mathcal{I}_y $, one can deduce that $ v_i \in {{\rm bdry}\,} \mathcal F(y,\xi) $ (defined in \eqref{Fyxi}) and $ c_i>0$ for every $ i\in\mathcal{I}_y $. Moreover, it holds that
\begin{equation}\label{sumci}
\sum\limits_{i\in\mathcal I_y} c_i = \sum\limits_{i\in\mathcal I_y} \frac{r_i\|y\|_\mathcal A - \|y\|_\mathcal A \langle\xi,r_i s_i\rangle }{\sigma} \overset{\rm (a)} = \frac{\|y\|_\mathcal A -\langle \xi, y \rangle}{\sigma} \overset{\rm (b)} \le 1,
\end{equation}
where (a) uses \eqref{atomrep} and the fact $ \sum_{i\in\mathcal I_y} r_i = \sum_{i=1}^m r_i=1 $, and (b) holds because $ y\in\mathcal F (y,\xi) $ (see \eqref{constrain}), $\xi\in \partial P_2(y)$ and $P_2$ is a norm. When $ \sum_{i\in {\mathcal{I}_y}} c_i = 1$, the decomposition \eqref{ydcomp1} of $ y $ satisfies the conditions in Definition~\ref{awdef}. Therefore, we can choose $ \mathcal{S}(y,\xi)=\{v_i:\;i\in\mathcal{I}_y\} $. Otherwise, choose any $ i_0\in\mathcal{I}_y $ and set $ \bar c=1-\sum_{i\in\mathcal{I}_y} c_i > 0$. The
\begin{equation}\label{ydcomp2}
\begin{split}
	y = c_{i_0}v_{i_0} + \sum_{i\in\mathcal{I}_y\setminus\{i_0\}}c_i v_i \overset{\rm (a)}=& \sum_{i\in\mathcal{I}_y\setminus\{i_0\}}c_i v_i +  \left(c_{i_0}+\frac{\bar c(1-\langle\xi, s_{i_0}\rangle )}{2}\right)v_{i_0} \\
	&+ \frac{\bar c(1+\langle\xi, s_{i_0}\rangle )}{2}\cdot \frac{-\sigma s_{i_0}}{(1+\langle\xi, s_{i_0}\rangle)},
\end{split}
\end{equation}
where (a) uses the fact that $ v_{i_0}=\frac{\sigma s_{i_0}}{1-\langle\xi, s_{i_0}\rangle} $.
Note that $ \frac{-\sigma s_{i_0}}{1+\langle\xi, s_{i_0}\rangle}\in\mathcal{V}(y,\xi) $ since $-s_{i_0}\in {\cal A}$ and $ \|-s_{i_0}\|_{\cal A} = 1$. Furthermore, we can check directly that the decomposition of $ y $ in \eqref{ydcomp2} is a convex combination of elements in $ \mathcal{V}(y,\xi)\subset \mathcal F(y,\xi) $ (see Proposition~\ref{atomprop}(i) for the positivity of $1 \pm \langle\xi,s_{i_0}\rangle$). In summary, we can choose the set $ \mathcal S(y,\xi) $ in \eqref{aw-step} as
\begin{equation}\label{Syxi}
\mathcal{S}(y, \xi) = \begin{cases}
\left\{\frac{\sigma s_i}{1-\langle\xi, s_i\rangle}: i\in \mathcal I_y\right\} & {\rm if}\; \sum\limits_{i\in\mathcal{I}_y} c_i=1;\\
 \left\{\frac{\sigma s_i}{1-\langle\xi, s_i\rangle}: i\in \mathcal I_y\right\}\cup \left\{\frac{-\sigma s_{i_0}}{1+\langle\xi, s_{i_0}\rangle}\right\} & {\rm otherwise,}
\end{cases}
\end{equation}
where $i_0$ is an arbitrarily chosen element in ${\mathcal{I}}_y$.

Now we give a solution $u_{\rm aw}$ of \eqref{aw-step}, which can be found by maximizing $ \langle a, x\rangle $ over the finite discrete set $ \mathcal S(y, \xi) $. In particular, a solution of \eqref{aw-step} is
\begin{equation}\label{uaw}
u_{\rm aw} =
\begin{cases}
\frac{\sigma s_{i_*}}{1-\langle\xi, s_{i_*}\rangle}  & {\rm if}\; \sum\limits_{i\in\mathcal{I}_y} c_i=1 \;{\rm or}\; \langle a, \frac{-\sigma s_{i_0}}{1+\langle \xi, s_{i_0}\rangle}\rangle < \langle a, \frac{\sigma s_{i_*}}{1-\langle \xi, s_{i_*}\rangle}\rangle;  \\
\frac{-\sigma s_{i_0}}{1+\langle \xi, s_{i_0}\rangle} & {\rm otherwise,}
\end{cases}
\end{equation}
where $ i_*\in\mathop{\rm Arg\,max}_{i\in\mathcal I_y} \left\langle a, \frac{\sigma s_i}{1-\langle\xi, s_i\rangle}\right\rangle  $. Recall that $i_0$ can be chosen to be any element in ${\cal I}_y$. In our numerical experiments in Section~\ref{sec7} below, for simplicity, we choose $i_0 = i_*$ in \eqref{uaw}.

\subsubsection{Choosing the $ \alpha_{\rm aw} $ in Step 2 of Algorithm~\ref{alg:aw-fw}}

Let $ P_1 $ and $ P_2 $ be as in Assumption~\ref{assump31} or \ref{assump32}.
Given $ y \in\mathcal F\setminus\{0\}$ and $ \xi\in\partial P_2(y)$, with $ \mathcal S(y,\xi) $ and $ u_{\rm aw} $ determined as in \eqref{Syxi} and \eqref{uaw}, we discuss how to find an $ \alpha_{\rm aw} \le \max\{\alpha\geq 0:y+\alpha d_{\rm aw}\in {\rm conv}(\mathcal S(y,\xi))\} $ along the away-step direction $ d_{\rm aw}  = y - u_{\rm aw}$. Note that the sets $ \mathcal S(y, \xi) $ in Section~\ref{sec:syxi} are all discrete sets with finite elements. For notational simplicity, we write
\[
\mathcal S(y,\xi) = \{v_1, \ldots, v_{q} \}
\]
with $ q=\lvert\mathcal{I}_y\rvert $ or $ \lvert\mathcal{I}_y\rvert+1 $, where $\mathcal{I}_y$ is defined as in Section~\ref{sec:syxi}. According to \eqref{ydcomp2} and \eqref{uaw}, we see that $ u_{\rm aw}\in\mathcal S(y,\xi) $ and
\begin{equation}\label{yrep}
	y = \sum_{i=1}^{q} \widetilde c_i v_i
\end{equation}
with $\widetilde c_i> 0 $ for every $ i=1,\ldots,q $ and $ \sum_{i=1}^{q}\widetilde c_i=1 $. Suppose that $ u_{\rm aw} = v_{i_1} $ for some $  v_{i_1}\in \mathcal S(y,\xi)$. Then one can choose
\begin{equation*}
	\alpha_{\rm aw} \le \max\{\alpha\geq 0:\; y+\alpha(y - v_{i_1}) \in {\rm conv} (\mathcal S(y, \xi))\}.
\end{equation*}
Define $ y(\alpha) = y+\alpha(y-v_{i_1}) $. Using \eqref{yrep}, we have
\[
\begin{split}
y(\alpha) = (1+\alpha)\sum\limits_{i\neq i_1}\widetilde c_i v_i + ((1+\alpha)\widetilde c_{i_1} -\alpha) v_{i_1}.
\end{split}
\]
To ensure that $ y(\alpha)\in {\rm conv}(S(y,\xi)) $, we impose the following conditions on $ \alpha $:
\begin{align}
	&(1+\alpha)\sum_{i\neq i_1}\widetilde c_i + (1+\alpha)\widetilde c_{i_1}-\alpha = 1, \label{alpha_ineq2} \\
    &(1+\alpha)\widetilde c_{i_1} -\alpha \geq 0. \label{alpha_ineq1}
\end{align}
Since $ \sum_{i=1}^{q} \widetilde c_i=1 $ (thanks to \eqref{sumci} and \eqref{ydcomp2}), we have $\sum_{i\neq i_1}\widetilde c_i =1 - \widetilde c_{i_1}$. It follows that
\[
(1+\alpha)\sum_{i\neq i_1}\widetilde c_i + (1+\alpha)\widetilde c_{i_1}-\alpha= (1+\alpha)(1-\widetilde c_{i_1})+(1+\alpha)\widetilde c_{i_1} - \alpha  = 1.
\]
That is, \eqref{alpha_ineq2} holds automatically for any $ \alpha\geq 0 $. So \eqref{alpha_ineq1} is sufficient to ensure that $ y(\alpha)\in{\rm conv}(\mathcal S(y,\xi)) $. We can thus choose
\begin{equation*}
\alpha_{\rm aw} = \min\left\{\frac{\widetilde c_{i_1}}{1-\widetilde c_{i_1}},\zeta\right\},
\end{equation*}
where $\zeta$ is given in Step 0 of Algorithm~\ref{alg:aw-fw}.
Here, we would like to mention that the expression $\frac{\widetilde c_{i_1}}{1-\widetilde c_{i_1}}$ coincides with the formula of the feasible stepsize $ \gamma_{\rm max} $ given in the FW method with away-step in convex setting proposed in \cite{Lacoste15}.

\section{Numerical experiments}\label{sec7}
In this section, we conduct numerical experiments to illustrate the performances of Algorithm~\ref{FW_nonconvex} and Algorithm~\ref{alg:aw-fw}.

Our simulations are based on the compressed sensing (CS) problem \cite{CandesTao06,Donoho06,Eldar12}, which aims to recover a sparse signal $ x_0\in{\rm I\!R}^n $ from a noisy linear measurement $ b\in{\rm I\!R}^m $ given by $Ax_0 +\widehat n $ with sensing matrix $ A\in{\rm I\!R}^{m\times n} $ and noise vector $ \widehat n\in{\rm I\!R}^m $. Motivated by the model with cardinality constraint for CS in \cite{Patterson13}, here we consider a CS model that minimizes the least squares loss over a sparsity inducing DC constraint described in Remark~\ref{cssparsity} as follows:
\begin{equation}\label{prob:cs}
\begin{array}{cl}
	\min\limits_{x\in{\rm I\!R}^{n}} & \frac12\|Ax-b\|^2\\
	\text{s.t.} & \|x\|_1-\mu\|x\| \leq \sigma,
\end{array}
\end{equation}
where $ \mu \in (0, 1) $ and $ \sigma > 0 $. Recall from Section~\ref{sec:scsubp} that the DC constraint function in \eqref{prob:cs} can be trivially transformed to the difference of two strongly convex functions with given $ \rho>0 $. Here, we also consider the following \textit{equivalent} formulation of \eqref{prob:cs}:
\begin{equation}\label{prob:cs-sc}
	\begin{array}{cl}
	\min\limits_{x\in{\rm I\!R}^{n}} & \frac12\|Ax-b\|^2\\
	\text{s.t.} & \left[\|x\|_1+\frac{\rho}{2}\|x\|^2\right]-\left[\mu\|x\|+\frac{\rho}{2}\|x\|^2\right] \leq \sigma.
	\end{array}
\end{equation}
Observe that Assumption~\ref{assumption1} holds for \eqref{prob:cs} with $P_1 = \|\cdot\|_1$ and $P_2 = \mu \|\cdot\|$: Indeed, it suffices to take $x^\odot_{(y,\xi)} = 0$ for any $y \in {\cal F}$ and $\xi\in \mu\partial \|y\|$.
Now, using this, Proposition~\ref{slaequ}(ii) and the fact that $ -\mu\|\cdot\| - \frac{\rho}2\|\cdot\|^2 $ is regular at every $ x\in{\rm I\!R}^n\setminus\{0\} $, we deduce further that Assumption~\ref{assumption1} is also satisfied for \eqref{prob:cs-sc} if we let $ P_1=\|\cdot\|_1+\frac{\rho}{2}\|\cdot\|^2 $ and $ P_2 = \mu\|\cdot\|+\frac{\rho}{2}\|\cdot\|^2 $. Thus, we can apply Theorem~\ref{thm-fw} to conclude that the sequence generated by Algorithm~\ref{FW_nonconvex} (applied to \eqref{prob:cs} and \eqref{prob:cs-sc} with the aforementioned $P_1$ and $P_2$) clusters at a stationary point of \eqref{prob:cs}. Moreover, the convergence of Algorithm~\ref{alg:aw-fw} applied to \eqref{prob:cs} also follows from Theorem~\ref{thm-fw-aw}.

In the remainder of this section, we perform numerical experiments to study the performances of Algorithm~\ref{FW_nonconvex} and Algorithm~\ref{alg:aw-fw} for solving randomly generated instances of \eqref{prob:cs}. Specifically, we apply Algorithm~\ref{FW_nonconvex} to \eqref{prob:cs} directly (i.e., with $P_1 = \|\cdot\|_1$ and $P_2 = \mu \|\cdot\|$) as well as to \eqref{prob:cs-sc} (i.e., with $ P_1=\|\cdot\|_1+\frac{\rho}{2}\|\cdot\|^2 $ and $ P_2 = \mu\|\cdot\|+\frac{\rho}{2}\|\cdot\|^2 $) for $ \rho = 0.01$, $0.05$ and $0.1$, respectively: For ease of reference, we refer to these approaches as FW, $ {\rm FW}_{\rho_{0.01}} $, $ {\rm FW}_{\rho_{0.05}} $ and ${\rm FW}_{\rho_{0.1}}$, respectively. We also apply Algorithm~\ref{alg:aw-fw} to \eqref{prob:cs} and refer to it as AFW.\footnote{Note that the discussion in Section~\ref{sec:aw3exs} requires that $P_1$ satisfies Assumption~\ref{assump31} or \ref{assump32}, which does not cover the decomposition considered in \eqref{prob:cs-sc}. Thus, we do not consider away-step oracle for algorithms based on \eqref{prob:cs-sc}.} All numerical experiments are performed in MATLAB 2019b on a 64-bit PC with an Intel Core i7-6700 CPU (3.40GHz) and 32GB of RAM.

\paragraph{Algorithm settings.}
We initialize all algorithms at the origin, which is feasible for \eqref{prob:cs} (also for \eqref{prob:cs-sc} with any $\rho > 0$). We set $ c=10^{-4} $, $ \eta = 1/2 $ and choose $\alpha_0^0 = 1$ and, for $k\ge 1$,
\begin{equation*}
 	\alpha_k^0 = \begin{cases}
 	\max\left\{10^{-8}, \min\left\{2\alpha_{k}^{\rm fw}, 1\right\}\right\} & \;\text{if}\; d^{k-1} = d^{k-1}_{\rm fw} \;\text{and}\;  j_{k-1} = 0,\\
 	\max\left\{10^{-8}, \min\left\{\alpha_{k}^{\rm fw}, 1\right\}\right\} & \; \text{otherwise},
 	\end{cases}
\end{equation*}
where $ \alpha_{k}^{\rm fw} $ is the stepsize used in the most recent FW step.\footnote{Note that by our choice of $\xi^k$ below and the discussion right before Section~\ref{sec:syxi}, we must have $d^0 = d^0_{\rm fw}$ in AFW.} In the tests of FW and AFW for \eqref{prob:cs}, we compute a closed-form solution of $ {\cal LO}$  through \eqref{xstar} with $ a = A^T(Ax^k - b) $ and $ \xi = \xi^k:= \mathop{\rm arg\,min}_{u\in \mu\partial\|x^k\|}\{\|u\|\} $ in each iteration. Moreover, when applying AFW for solving \eqref{prob:cs}, we set $ \epsilon = 10^{-5} $ and $ \zeta=10^{5} $, and we compute a solution of $ {\cal AWO}(x^k, \mathcal S(x^k, \xi^k)) $ through \eqref{uaw} with $ a = A^T(Ax^k - b) $, $ \xi = \xi^k:= \mathop{\rm arg\,min}_{u\in \mu\partial\|x^k\|}\{\|u\|\} $ and $ \mathcal I_{y}=\left\{i:\;x^k_i\neq 0\right\} $. Regarding the $ {\cal LO}$ in $ {\rm FW}_{\rho_{0.01}} $ (and, similarly, in $ {\rm FW}_{\rho_{0.05}} $ and $ {\rm FW}_{\rho_{0.1}} $) for solving \eqref{prob:cs-sc}, we compute its solution by using \eqref{xprox} with $ a= A^T(Ax^k - b)$, $ \xi = \xi^k:= \rho x^k + \mathop{\rm arg\,min}_{u\in \mu\partial\|x^k\|}\{\|u\|\}$ and $\widetilde P_1 = \|\cdot\|_1 $. Moreover, leveraging the positive homogeneity of $ \|\cdot\|_1-\mu\|\cdot\| $, we adopt the strategy in \eqref{choosexk+1} to determine $ x^{k+1}$ in all the five algorithms. Finally, we terminate these algorithms if one of the following criteria is satisfied:
\begin{itemize}
	\item the number of iterations exceeds 10000;
	\item the computational time exceeds a given upper bound $ {\rm T}^{\max} $;
	\item $\lvert\langle A^T(Ax^k - b), d^k_{\rm fw}\rangle \rvert < 10^{-10} \cdot\max\{\frac12\|A x^k - b\|^2,1\}$.
\end{itemize}
\paragraph{Randomly generated instances.}
We first generate a matrix whose entries follow i.i.d. standard Gaussian distribution. We then normalize each column and take it as the sensing matrix $A$ in \eqref{prob:cs}. Next, we generate an $s$-sparse vector with $s$ i.i.d. standard Gaussian entries at random (uniformly chosen) positions and let it be the original signal $x_{\rm orig}\in\mathbb{R}^{n}$. Then we set $ b = Ax_{\rm orig}+0.01\varepsilon $, where $ \varepsilon\in{\rm I\!R}^{m} $ has i.i.d. standard Gaussian entries. Finally, we set $ \mu =0.5 $ and $ \sigma=\left(\|x_{\rm orig}\|_1-\mu\|x_{\rm orig}\|\right)/1.1 $.

In our tests, we consider $ (n, m, s) = (2560i, 720i, 80i) $ with $ i\in\{1, 3\} $. For each $ i  = 1$ and $3$, we set $ {\rm T}^{\max} = 5$ and $30$ seconds, respectively, and generate 30 random instances as described above.
We observe that the algorithms solving \eqref{prob:cs-sc} (i.e., $ {\rm FW}_{\rho_{0.01}} $, $ {\rm FW}_{\rho_{0.05}} $ and $ {\rm FW}_{\rho_{0.1}} $) generally take more time in each iteration than the FW and AFW for \eqref{prob:cs}, but they satisfy the third termination criterion in fewer iterations if $ \rho $ is properly chosen. To better illustrate the performance of these algorithms, we follow \cite{Gillis12, YangPongChen18} and plot an evolution of the objective function value relative to the initial value and the ``best" objective value achievable. To this end, we first define the following ratio for each $ k $:
\[
e(k) = \frac{f_k - f_{\min}}{f_0 - f_{\min}},
\]
where $ f_k = \frac12\|Ax^k - b\|^2 $, $ f_0 = \frac12\|Ax^0 - b\|^2 $ and $ f_{\min} $ is the minimum of the obtained objective function values at termination among all 5 algorithms. Note that $ e(k)\in[0,1] $ for all $ k $ and it decreases with respect to $ k $ since $ f_k $ decreases with respect to $ k $ in all algorithms. Let $ \mathcal T(k) $ denote the total computational time used by the first $ k $ iterations. We next define the evolution of the (relative) objective function value with respect to the computational time as follows:
\[
E(t) = \min\limits_k\{e(k):\; \mathcal T(k)\leq t \}.
\]
Notice that $ E(t)\in[0, 1] $ for any $ t\in [0, {\rm T}^{\max}] $. For $ i=1$ and $3$, we plot the averaged $ E(t) $ for each algorithm, averaged over the 30 random instances, in Figure~\ref{fig:fig1}. From the plots, we see that $ {\rm FW}_{\rho_{0.1}} $ performs best among all algorithms, and the performance of the approaches based on solving \eqref{prob:cs-sc} decays as $\rho$ decreases. On the other hand, by comparing the performances of FW and AFW, we see that our proposed away-step technique does improve the performance of FW empirically.

\begin{figure}
	\caption{Plots of the evolution of the averaged $E(t)$.}
	\label{fig:fig1}

	\begin{subfigure}{.5\textwidth}
		\centering
		\includegraphics[scale=0.45]{FvalTimeTrace_index_1-24-Dec-2021-11-26-eps-converted-to.pdf}
	\end{subfigure}
	\begin{subfigure}{.4\textwidth}
		\centering
		\includegraphics[scale=0.45]{FvalTimeTrace_index_3-24-Dec-2021-11-26-eps-converted-to.pdf}
	\end{subfigure}
\end{figure}

\vspace{3mm}
{{\bf Acknowledgements.} Yongle Zhang was supported partly by the National Natural Science Foundation of China (11901414) and (11871359). Guoyin Li  was partially supported by  discovery projects from Australian Research Council (DP190100555 and DP210101025). Ting Kei Pong was supported in part by the Hong Kong Research Grants Council PolyU153004/18p.}

redpajama_set_name: RedPajamaArXiv