A Unified Optimization View on
Generalized Matching Pursuit and Frank-Wolfe

Francesco Locatello Rajiv Khanna* Michael Tschannen* Martin Jaggi

ETH Zürich UT Austin ETH Zürich EPFL

###### Abstract

Two of the most fundamental prototypes of greedy optimization are the matching
pursuit and Frank-Wolfe algorithms. In this paper, we take a unified view on
both classes of methods, leading to the first explicit convergence rates of
matching pursuit methods in an optimization sense, for general sets of atoms.
We derive sublinear ($1/t$) convergence for both classes on general smooth
objectives, and linear convergence on strongly convex objectives, as well as a
clear correspondence of algorithm variants. Our presented algorithms and rates
are affine invariant, and do not need any incoherence or sparsity assumptions.

##  1 Introduction

During the past decade, greedy algorithms have attracted significant attention
and led to many success stories in machine learning and signal processing
(e.g., compressed sensing), and optimization in general. The most prominent
representatives are matching pursuit (MP) algorithms on one hand Mallat &
Zhang (1993), such as, e.g., orthogonal matching pursuit (OMP) Chen et al.
(1989); Tropp (2004), and on the other hand Frank-Wolfe (FW)-type algorithms
Frank & Wolfe (1956). Both operate in the setting of minimizing an objective
over (combinations of) a given set of atoms, or dictionary elements.

The two classes of methods have very strong similarities, in the sense that
they in each iteration rely on the very same subroutine, namely selecting the
atom of largest inner product with the negative gradient, i.e., what we call
the _linear minimization oracle_ (LMO). Yet, the main difference is that MP
methods optimize over the linear span of the atoms, while FW methods optimize
over their convex hull.

Despite the vast literature on MP-type methods which typically gives recovery
guarantees for sparse signals, surprisingly little is known about MP
algorithms in terms of optimization, i.e., how many iterations are needed to
reach a defined target accuracy. In particular, we are not aware of any
general-purpose explicit convergence rates, which hold for an arbitrary given
set of atoms (here “explicit” means that the result must not depend on
iteration-dependent quantities). Indeed, in the context of sparse recovery,
convergence rates typically come as a byproduct of the recovery guarantees and
hence depend on very strong assumptions (from an optimization perspective),
such as incoherence or restricted isometry properties of the atom set Tropp
(2004); Davenport & Wakin (2010). Motivated by this line of work, Gribonval &
Vandergheynst (2006); Temlyakov (2013, 2014); Nguyen & Petrova (2014)
specifically target convergence rates but still rely on incoherence
properties. On the other hand, FW methods are well understood from an
optimization perspective, with strong explicit convergence results available
for a large class of input problems, see, e.g., Jaggi (2013); Lacoste-Julien &
Jaggi (2015) for a recent account.

In this paper, we provide a unified view on MP and FW algorithms from an
optimization perspective. Our joint understanding of both classes of
algorithms has several benefits:

  * •

We provide a clear presentation of MP methods with their FW analogues in a
unified context, for the task of general convex optimization over any set of
atoms from a Hilbert space. Our view also includes weight-corrective variants
of MP and FW which we are able to set in direct correspondence.

  * •

Our derived convergence rates (sub-linear for the case of smooth objective,
and linear/geometric for the case of smooth and strongly convex objective) are
the first explicit optimization rates for MP methods, for general atom sets,
to the best of our knowledge. We set the new rates and their complexity
constants in context with existing FW rates. Our linear convergence rate of MP
is expressed in terms of a new quantity called the _minimal intrinsic
directional width_ of the atoms.

  * •

We allow for approximate subroutines in all proposed MP and FW variants, that
is the use of an approximate linear oracle (LMO). The level of approximation
quality is reflected in all convergence rates.

  * •

Additionally, we give affine invariant extensions of the MP and FW algorithm
variants, as well as convergence rates in terms of affine invariant
quantities. That is, the algorithms and rates will be invariant under affine
transformations and re-parameterizations of the optimization domain (a
property which was known for Newton’s method and FW methods, but is novel in
the MP context).

#### Motivation.

The setting of optimization over linear or convex combinations of atoms has
served as a very useful template in many applications, since the choice of the
atom set conveniently allows to encode structure desired for the use case.
Apart from many applications based on sparse vectors, the use of rank-1 atoms
gives rise to structured matrix and tensor factorizations, see, e.g., Wang et
al. (2014); Yang et al. (2015); Yao & Kwok (2016); Guo et al. (2017). For
example, minimizing the Bregman Divergence over a set of structured rank-1
matrices yields an exponential family structured PCA (Gunasekar et al., 2014).
Other applications include multilinear multitask learning (Romera-Paredes et
al., 2013), matrix completion and image denoising (Tibshirani, 2015).

#### Complexity Constants and Coherence.

While our sub-linear convergence rates for MP and FW only depend on bounded
norm of the iterates and on the diameter of the atom set, the linear rates
also depend on our notion of minimal intrinsic directional width. In contrast
to the notion of (cumulative) coherence commonly used in the context of MP and
OMP Gribonval & Vandergheynst (2006), our width complexity notion is more
robust, e.g., w.r.t. addition of new atoms, and leading to provably better
bounds than coherence. Furthermore, our linear rates are significantly easier
to interpret than the linear rates obtained for FW algorithm variants in
Lacoste-Julien & Jaggi (2015) which rely on a complex geometric quantity
called pyramidal width. Finally, we elucidate the relationship between FW
algorithms and our proposed generalized MP variants, by showing that the
iterates of FW converge to those of MP as $O(1/\alpha)$, if the atom set of FW
is scaled by a growing factor $\alpha$.

We note that a few recent works Shalev-Shwartz et al. (2010); Temlyakov (2013,
2014, 2015); Nguyen & Petrova (2014); Yao & Kwok (2016) proposed similar
algorithms extending MPs to general smooth objective functions, although with
less general convergence rates and without studying the algorithms in the
larger context of MP and FW. The relation to these works is discussed in
detail in Section 8.

#### Notation.

Let $[d]$ be the set $\\{1,2,\ldots,d\\}$. Given a non-empty subset
$\mathcal{A}$ of some vector space, let $\operatorname{conv}(\mathcal{A})$ be
the convex hull of the set $\mathcal{A}$, and let
$\operatorname{lin}(\mathcal{A})$ denote the linear span of the elements in
$\mathcal{A}$. Given a closed set $\mathcal{A}$ we call its diameter
$\operatorname{\mathrm{diam}}(\mathcal{A})=\max_{{\mathbf{z}}_{1},{\mathbf{z}}_{2}\in\mathcal{A}}\|{\mathbf{z}}_{1}-{\mathbf{z}}_{2}\|$
and its radius
$\operatorname{\mathrm{radius}}(\mathcal{A})=\max_{{\mathbf{z}}\in\mathcal{A}}\|{\mathbf{z}}\|$.
Note that for convex hulls of finite atom sets $\mathcal{A}$ we have
$\operatorname{\mathrm{diam}}(\operatorname{conv}(\mathcal{A}))=\operatorname{\mathrm{diam}}(\mathcal{A})$,
i.e., the diameter is attained at two vertices Ziegler (1995).
$\|{\mathbf{x}}\|_{\mathcal{A}}:=\inf\\{c>0\colon{\mathbf{x}}\in
c\cdot\operatorname{conv}(\mathcal{A})\\}$ is the atomic norm of
${\mathbf{x}}$ over a set $\mathcal{A}$ (also known as the gauge function of
$\operatorname{conv}(\mathcal{A})$). We call a subset $\mathcal{A}$ of a
Hilbert space symmetric if $\mathcal{A}=-\mathcal{A}$. We write
$\operatorname{clip}_{[0,1]}(s):=\max\\{0,\min\\{1,s\\}\\}$.

##  2 Matching Pursuit and Frank-Wolfe

We start by reviewing the MP Mallat & Zhang (1993), the OMP Chen et al.
(1989); Tropp (2004), and the FW algorithm Frank & Wolfe (1956); Jaggi (2013)
in Hilbert spaces. The setting considered throughout this paper is the
following. Let $\mathcal{H}$ be a Hilbert space with associated inner product
$\langle{\mathbf{x}},{\mathbf{y}}\rangle,\,\forall\,{\mathbf{x}},{\mathbf{y}}\in\mathcal{H}$.
The inner product induces the norm
$\|{\mathbf{x}}\|^{2}:=\langle{\mathbf{x}},{\mathbf{x}}\rangle,$
$\forall\,{\mathbf{x}}\in\mathcal{H}$. Let $\mathcal{A}\subset\mathcal{H}$ be
a non-empty bounded set (the set of atoms or dictionary) and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be convex and $L$-smooth
($L$-Lipschitz gradient in the finite-dimensional case). If $\mathcal{H}$ is
an infinite-dimensional Hilbert space, then $f$ is assumed to be _Fréchet
differentiable_.

In each iteration, both the MP/OMP and the FW algorithm query a so-called
linear minimization oracle (LMO) which solves the optimization problem

$\textsc{LMO}_{\mathcal{D}}({\mathbf{y}}):=\operatorname*{arg\,min}_{{\mathbf{z}}\in\mathcal{D}}\,\langle{\mathbf{y}},{\mathbf{z}}\rangle$
(1)

for given ${\mathbf{y}}\in\mathcal{H}$ and $\mathcal{D}\subset\mathcal{H}$. As
computing an exact solution (1), depending on $\mathcal{D}$, is often hard in
practice, it is desirable to rely on an _approximate_ LMO that returns an
approximate minimizer of (1). Different notions of approximate LMO s are
discussed in more detail in Section 3.4.

MP and OMP, presented in Algorithm 1, aim at approximating a target point
${\mathbf{y}}\in\mathcal{H}$ as well as possible in the least-squares sense
using no more than $T$ atoms form a possibly countable or finite dictionary
$\mathcal{A}\subset\mathcal{H}$.

Algorithm 1 (Orthogonal) Matching Pursuit

1: init ${\mathbf{x}}_{0}\in\operatorname{lin}(\mathcal{A})$
$\mathcal{S}=\left\\{{\mathbf{x}}_{0}\right\\}$

2: for $t=0\dots T$

3: Find
${\mathbf{z}}_{t}:=(\text{Approx-})\textsc{LMO}_{\mathcal{A}\cup-\mathcal{A}}(-{\mathbf{y}}+{\mathbf{x}}_{t})$

4: $\mathcal{S}=\mathcal{S}\cup{\mathbf{z}}_{t}$

5: Update MP:
${\mathbf{x}}_{t+1}:=\underset{\begin{subarray}{c}{\mathbf{x}}:={\mathbf{x}}_{t}+\gamma{\mathbf{z}}_{t}\\\
\gamma\in{\mathbb{R}}\end{subarray}}{\operatorname*{arg\,min}}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$,
or

6: Update OMP:
${\mathbf{x}}_{t+1}:=\operatorname*{arg\,min}_{{\mathbf{x}}\in\operatorname{lin}(\mathcal{S})}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$

7: end for

At each iteration, OMP adds a new atom to the active set $\mathcal{S}$ and
computes the new iterate as the least-squares approximation of ${\mathbf{y}}$
in terms of the atoms in $\mathcal{S}$. As a result, the residual
${\mathbf{r}}_{t+1}:={\mathbf{y}}-{\mathbf{x}}_{t+1}$ is orthogonal to
$\operatorname{lin}(\mathcal{S})$. This is in contrast to MP, which only
minimizes the residual error $\|{\mathbf{r}}_{t+1}\|^{2}$ w.r.t.
${\mathbf{z}}_{t}$ so that ${\mathbf{r}}_{t+1}$ is orthogonal to
${\mathbf{z}}_{t}$, but not necessarily to all ${\mathbf{z}}_{t^{\prime}}$,
$t^{\prime}\leq t-1$. Note that MP does not require to maintain the active set
$\mathcal{S}$ as the update only relies on ${\mathbf{z}}_{t}$. Also note that
in the signal processing literature MP and OMP are typically formulated using
${\mathbf{z}}_{t}:=\operatorname*{arg\,max}_{{\mathbf{z}}\in\mathcal{A}}\,|\langle{\mathbf{y}}-{\mathbf{x}}_{t},{\mathbf{z}}\rangle|$
in Line 3 of Algorithm 1 instead of
${\mathbf{z}}_{t}:=\textsc{LMO}_{\mathcal{A}\cup-\mathcal{A}}(-{\mathbf{y}}+{\mathbf{x}}_{t})$.
The solution of this alternative LMO definition is equal to that of
$\textsc{LMO}_{\mathcal{A}\cup-\mathcal{A}}$ up to the sign, so that the
iterates ${\mathbf{x}}_{t}$ are identical for both definitions. Relying on
$\textsc{LMO}_{\mathcal{A}\cup-\mathcal{A}}$ here allows to better illustrate
the parallels between MP/OMP and FW.

We now turn to the FW algorithm Frank & Wolfe (1956); Jaggi (2013), also
referred to as conditional gradient in the literature. The FW algorithm,
presented in Algorithm 2, targets the optimization problem

$\displaystyle\min_{{\mathbf{x}}\in\mathcal{D}}f({\mathbf{x}}),$ (2)

where $\mathcal{D}\subset\mathcal{H}$ is convex and bounded. In many
applications, $\mathcal{D}$ is the convex hull of a dictionary $\mathcal{A}$,
i.e., $\mathcal{D}=\operatorname{conv}(\mathcal{A})$, in which case
$\textsc{LMO}_{\mathcal{D}}({\mathbf{y}})=\textsc{LMO}_{\mathcal{A}}({\mathbf{y}})$.

Algorithm 2 Frank-Wolfe

1: init ${\mathbf{x}}_{0}\in\operatorname{conv}(\mathcal{A})$

2: for $t=0\dots T$

3: Find ${\mathbf{z}}_{t}:=(\text{Approx-})\textsc{LMO}_{\mathcal{A}}(\nabla
f({\mathbf{x}}_{t}))$

4:  _Variant 0:_ $\gamma:=\frac{2}{t+2}$

5:  _Variant 1:_
$\gamma:=\displaystyle\operatorname*{arg\,min}_{\gamma\in[0,1]}f({{\mathbf{x}}_{t}\\!+\\!\gamma({\mathbf{z}}_{t}-{\mathbf{x}}_{t})})$

6:  _Variant 2:_
$\gamma:=\operatorname{clip}_{[0,1]}\\!\big{[}\frac{\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{\operatorname{\mathrm{diam}}_{\|.\|\\!}(\mathcal{A})^{2}L}\big{]}$

7:  _Variant 3:_
$\gamma:=\operatorname{clip}_{[0,1]}\\!\big{[}\frac{\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{\|{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}L}\big{]}$

8: Update
${\mathbf{x}}_{t+1}:={\mathbf{x}}_{t}+\gamma({\mathbf{z}}_{t}-{\mathbf{x}}_{t})$

9: end for

At each iteration, the FW algorithm selects a new atom ${\mathbf{z}}_{t}$ from
$\mathcal{D}$ by querying the LMO and computes the new iterate as a convex
combination of ${\mathbf{z}}_{t}$ and the old iterate ${\mathbf{x}}_{t}$. As
discussed in Jaggi (2013), the convex update can be performed either by line
search (line 5 in Algorithm 2) or as a convex combination of all previously
selected atoms ${\mathbf{z}}_{t^{\prime}}$, $t^{\prime}\leq t$.

The steps in Line 3 of MP (Algorithm 1) and Line 3 of FW (Algorithm 2)
(finding the step direction) are identical up to symmetrization of
$\mathcal{A}$. This is seen as follows. Recall that MP and OMP approximate
${\mathbf{y}}$ in the least-squares sense, i.e., they aim at minimizing
$f({\mathbf{x}}):=\frac{1}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$. For this
choice of $f$ we have $\nabla
f({\mathbf{x}}_{t})=-{\mathbf{y}}+{{\boldsymbol{x}}}_{t}=-{\mathbf{r}}_{t}$,
i.e.,
$\textsc{LMO}_{\mathcal{A}\cup-\mathcal{A}}(-{\mathbf{r}}_{t})=\textsc{LMO}_{\mathcal{A}\cup-\mathcal{A}}(\nabla
f({\mathbf{x}}_{t}))$.

##  3 Greedy Algorithms in Hilbert Spaces

We present new greedy algorithms—inspired by MP, OMP, and FW—for the
minimization of functions $f$ over a convex and bounded set
$\mathcal{D}\subset\mathcal{H}$, or over the linear span of a dictionary
$\mathcal{A}\subset\mathcal{H}$. As MP, OMP, and FW, these algorithms
alternate between querying the LMO defined in (1) and updating the current
iterate ${\mathbf{x}}_{t}$. Common to all of our algorithms is that their
update step minimizes an upper bound of $f$ at ${\mathbf{x}}_{t}$, given as

$g_{{\mathbf{x}}_{t}}({\mathbf{x}}):=f({\mathbf{x}}_{t})+\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}-{\mathbf{x}}_{t}\rangle+\frac{L}{2}\|{\mathbf{x}}-{\mathbf{x}}_{t}\|^{2}$
(3)

where $L$ is an upper bound on the smoothness constant of $f$ w.r.t. a chosen
norm $\|.\|$. Optimizing this norm problem instead of the original $f$
objective allows for substantial efficiency gains in the case of complicated
$f$ objective.

We note that our algorithms can be made _affine invariant_ , i.e., invariant
under affine transformations and re-parameterizations of the domain, by simple
modifications of the update steps. For simplicity of exposition, we present
these algorithm versions, along with corresponding sub-linear and linear
convergence results later in Section 6.

###  3.1 Constrained Optimization

We consider constrained optimization problems of the form (2) with
$\mathcal{D}:=\operatorname{conv}(\mathcal{A})$ for some dictionary
$\mathcal{A}\subset\mathcal{H}$. Inspired by the fully-corrective Frank-Wolfe
variant (see, e.g., Holloway (1974); Jaggi (2013)) which, in each update step,
re-optimizes the original objective over the convex hull of all previously
selected atoms, $\operatorname{conv}(\mathcal{S})$, we instead propose to
minimize the simpler quadratic upper bound (3) over the atom selected at the
current iteration (using line-search) or over
$\operatorname{conv}(\mathcal{S})$. We call this algorithm variant, presented
in Algorithm 3, _norm-corrective Frank-Wolfe_.

Algorithm 3 Norm-Corrective Frank-Wolfe

1: init ${\mathbf{x}}_{0}\in\operatorname{conv}(\mathcal{A})$, and
$\mathcal{S}:=\\{{\mathbf{x}}_{0}\\}$

2: for $t=0\dots T$

3: Find ${\mathbf{z}}_{t}:=(\text{Approx-})\textsc{LMO}_{\mathcal{A}}(\nabla
f({\mathbf{x}}_{t}))$

4: $\mathcal{S}:=\mathcal{S}\cup\\{{\mathbf{z}}_{t}\\}$

5: Let ${\mathbf{b}}:={\mathbf{x}}_{t}-\frac{1}{L}\nabla f({\mathbf{x}}_{t})$

6: Variant 0: Update
${\mathbf{x}}_{t+1}:=\displaystyle\operatorname*{arg\,min}_{\begin{subarray}{c}\\!\\!\\!\\!{\mathbf{z}}:={\mathbf{x}}_{t}+\gamma({\mathbf{z}}_{t}-{\mathbf{x}}_{t})\\\
\gamma\in[0,1]\end{subarray}}\\!\\!\\!\|{{\mathbf{z}}-{\mathbf{b}}}\|_{2}^{2}$
Variant 1: Update
${\mathbf{x}}_{t+1}:=\displaystyle\operatorname*{arg\,min}_{{\mathbf{z}}\in\operatorname{conv}(\mathcal{S})}\|{{\mathbf{z}}-{\mathbf{b}}}\|_{2}^{2}$

7:  _Optional:_ Correction of some/all atoms ${\mathbf{z}}_{0\ldots t}$

8: end for

The name “norm-corrective” is used to illustrate that the algorithm employs a
simple squared norm surrogate function (or upper bound on $f$), which only
depends on the smoothness constant $L$. This is in contrast to second-order
optimization methods such as Newton’s method, which rely on a non-uniform
quadratic surrogate function at each iteration. Importantly, we do not need to
know $L$ (and the corresponding constant in the affine invariant algorithm
versions in Section 6) exactly in any of the proposed algorithms; an upper
bound is always sufficient to ensure convergence. Finding the closest point in
norm can typically be performed much more efficiently than solving a general
optimization problem, such as if we would minimize $f$ over the same domain,
which is what the “fully-corrective” algorithm variants require in each
iteration. Approximately solving the subproblem in Variant 1 can be done
efficiently using projected gradient steps on the weights (as projection onto
the simplex and L1 ball is efficient). Assuming a fixed quadratic subproblem
as in Variant 1, the CoGEnT algorithm of Rao et al. (2015) uses the same
“enhancement” steps. The difference in the presentation here is that we
address general $f$, so that the quadratic correction subproblem changes in
every iteration in our case.

###  3.2 Optimization over the linear span of a dictionary

We now move on to optimization over linear span of a dictionary
$\mathcal{A}\subset\mathcal{H}$, i.e., we consider problems of the form

$\displaystyle\min_{{\mathbf{x}}\in\operatorname{lin}(\mathcal{A})}f({\mathbf{x}}).$
(4)

To solve (4), we present the Norm-Corrective Generalized Matching Pursuit
(GMP) in Algorithm 4 which is again based on the quadratic upper bound (3) and
can be seen as an extension of MP and OMP to smooth functions $f$.

Algorithm 4 Norm-Corrective Generalized Matching Pursuit

1: init ${\mathbf{x}}_{0}\in\operatorname{lin}(\mathcal{A})$, and
$\mathcal{S}:=\\{{\mathbf{x}}_{0}\\}$

2: for $t=0\dots T$

3: Find ${\mathbf{z}}_{t}:=(\text{Approx-})\textsc{LMO}_{\mathcal{A}}(\nabla
f({\mathbf{x}}_{t}))$

4: $\mathcal{S}:=\mathcal{S}\cup\\{{\mathbf{z}}_{t}\\}$

5: Let ${\mathbf{b}}:={\mathbf{x}}_{t}-\frac{1}{L}\nabla f({\mathbf{x}}_{t})$

6: Variant 0: Update
${\mathbf{x}}_{t+1}:=\displaystyle\operatorname*{arg\,min}_{\begin{subarray}{c}{\mathbf{z}}:={\mathbf{x}}_{t}+\gamma{\mathbf{z}}_{t}\\\
\gamma\in{\mathbb{R}}\end{subarray}}\|{{\mathbf{z}}-{\mathbf{b}}}\|_{2}^{2}$
Variant 1: Update
${\mathbf{x}}_{t+1}:=\displaystyle\operatorname*{arg\,min}_{{\mathbf{z}}\in\operatorname{lin}(\mathcal{S})}\|{{\mathbf{z}}-{\mathbf{b}}}\|_{2}^{2}$

7:  _Optional:_ Correction of some/all atoms ${\mathbf{z}}_{0\ldots t}$

8: end for

Here, the updates in line 6 are again either over the most recently selected
atom (Variant 0) or over all perviously selected atoms (Variant 1). However,
the optimization is unconstrained as opposed to norm-corrective FW. Note that
the update step in line 6 of Algorithm 4 Variant 0 (line-search) has the
closed-form solution
$\gamma=-\frac{\langle{\mathbf{x}}_{t}-{\mathbf{b}},{\mathbf{z}}_{t}\rangle}{\|{\mathbf{z}}_{t}\|^{2}}$.

It is important to stress the fact that for Variant 1, at the end of iteration
$t$, $\nabla f({{\boldsymbol{x}}}_{t+1})$ is not always orthogonal to
$\operatorname{lin}(\mathcal{S})$ as it is the case for OMP (see the
discussion in Section 2).

This difference is rooted in the fact that the OMP residual
${\mathbf{r}}_{t+1}={\mathbf{y}}-{\mathbf{x}}_{t+1}$ (i.e., the gradient at
iteration $t+1$, $\nabla f({{\boldsymbol{x}}}_{t+1})$) can be obtained by
projecting the ${\mathbf{r}}_{t}$ (i.e., the gradient at iteration $t$,
$\nabla f({{\boldsymbol{x}}}_{t})$) onto the orthogonal complement of
$\hat{\mathbf{z}}_{t}$, where $\hat{\mathbf{z}}_{t}$ is obtained by
orthogonalizing ${\mathbf{z}}_{t}$ w.r.t. ${\mathbf{z}}_{t^{\prime}}$,
$t^{\prime}\leq t-1$. In other words, the OMP update step maintains
orthogonality of the gradient w.r.t. the atoms selected in all previous
iterations, which is not the case for general smooth functions $f$ due to
varying curvature.

###  3.3 Discussion

The update step in line 6 in Algorithms 3 and 4 is very similar to a projected
gradient descent step with a step-size of $1/L$ (i.e.,
${\mathbf{b}}={\mathbf{x}}_{t}-\frac{1}{L}\nabla f({\mathbf{x}}_{t})$ is a
gradient descent step with step size $1/L$ and the update step in line 6 is a
projection of ${\mathbf{b}}$). However, the crucial difference to projected
gradient descent is that the projection step is only partial, i.e., the
projection is only onto $\operatorname{conv}(\mathcal{S})$ and
$\operatorname{lin}(\mathcal{S})$ instead of the entire constraint set
$\operatorname{conv}(\mathcal{A})$ and $\operatorname{lin}(\mathcal{A})$ for
Algorithms 3 and 4, respectively.

The total number of iterations $T$ of Algorithms 3 and 4 controls the trade-
off between approximation quality, i.e., how close $f({\mathbf{x}}_{T})$ is to
the optimum $f({\mathbf{x}}^{\star})$, and the “structuredness” of the
(approximate) solution ${\mathbf{x}}_{T}$. The structure is due to the fact
that we only use $T$ atoms from $\mathcal{A}$ and due to the structure of the
atoms themselves (e.g., sparsity). A concrete example for an application of
Algorithm 4 that requires such a structure is low-rank matrix factorization:
Choosing for $f$ a function measuring the approximation quality of a given
matrix to a target matrix and rank-1 matrices with unit norm as atom set, $T$
controls the rank of the solution matrix.

###  3.4 Approximate linear oracles and atom corrections

Recall that an exact LMO is often very costly, in particular when applied to
matrix (or tensor) factorization problems, while approximate versions can be
much more efficient. We now generalize all the presented Algorithms to allow
for an _approximate LMO_. Different notions of such an LMO were already
explored for the Frank-Wolfe framework in Lacoste-Julien et al. (2013). Here,
we focus on multiplicative errors and define two different approximate LMO s,
one for Algorithm 3 and another one for Algorithm 4. We discuss their
relationship in Section 7. Formally, for a given quality parameter
$\delta_{\textsf{FW}}\in\left(0,1\right]$ and for a given direction
${\mathbf{d}}\in\mathcal{H}$, the approximate LMO for Algorithm 3 returns a
vector $\tilde{{\mathbf{z}}}\in\mathcal{A}$ satisfying

$\langle{\mathbf{d}},\tilde{{\mathbf{z}}}-{\mathbf{x}}_{t}\rangle\leq\delta_{\textsf{FW}}\min_{{\mathbf{z}}\in\mathcal{A}}\langle{\mathbf{d}},{\mathbf{z}}-{\mathbf{x}}_{t}\rangle.$
(5)

For given quality parameter $\delta_{\textsf{MP}}\in\left(0,1\right]$ and
given direction ${\mathbf{d}}\in\mathcal{H}$, the approximate LMO for
Algorithm 4 returns a vector $\tilde{{\mathbf{z}}}\in\mathcal{A}$ such that

$\langle{\mathbf{d}},\tilde{{\mathbf{z}}}\rangle\leq\delta_{\textsf{MP}}\langle{\mathbf{d}},{\mathbf{z}}\rangle,$
(6)

where ${\mathbf{z}}=\textsc{LMO}_{\mathcal{A}}({\mathbf{d}})$. We will often
refer to the quality parameter simply as $\delta$.

Further, as shown in line 7 of Algorithms 3 and 4, we also allow for
correction of some/all atoms in the active set $\mathcal{S}$, see, e.g., Laue
(2012); Guo et al. (2017), to obtain a better objective cost while maintaining
the same (small) number of atoms.

##  4 Sublinear Convergence Rates

In this section we present sub-linear convergence guarantees for Algorithms 3
and 4. All proofs are deferred to the Appendix in the supplement.

#### Frank-Wolfe algorithm variants.

We start with the convergence result for Algorithm 3, which targets
optimization problems of the form (2). Let
${\mathbf{x}}^{\star}\in\operatorname*{arg\,min}_{{\mathbf{x}}\in\operatorname{conv}(\mathcal{A})}f({\mathbf{x}})$
be an optimal solution of (2).

######  Theorem 1.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be $L$-smooth w.r.t. a given
norm $\|.\|$, over $\operatorname{conv}(\mathcal{A})$. Then, the Frank-Wolfe
method (Algorithm 2), as well as Norm-Corrective Frank-Wolfe (Algorithm 3),
converge for $t\geq 0$ as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{2\left(\frac{1}{\delta}L\operatorname{\mathrm{diam}}_{\|.\|\\!}(\mathcal{A})^{2}+\varepsilon_{0}\right)}{\delta
t+2}$

where $\varepsilon_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\star})$ is the
initial error in objective, and $\delta\in(0,1]$ is the accuracy parameter of
the employed approximate LMO (Equation (5)).

#### Matching pursuit algorithm variants.

We now move on to Algorithm 4 which solves optimization problems over a linear
span, as given in (4). We again write
${\mathbf{x}}^{\star}\in\operatorname*{arg\,min}_{{\mathbf{x}}\in\operatorname{lin}(\mathcal{A})}f({\mathbf{x}})$
for an optimal solution. Our rates will crucially depend on a (possibly loose)
upper bound on the atomic norm of the solution and iterates: Let $\rho>0$ s.t.

$\rho\geq\max\left\\{\|{\mathbf{x}}^{\star}\|_{\mathcal{A}},\|{\mathbf{x}}_{0}\|_{\mathcal{A}}\ldots,\|{\mathbf{x}}_{T}\|_{\mathcal{A}}\right\\}.$
(7)

If the optimum is not unique, we consider ${\mathbf{x}}^{\star}$ to be one of
largest atomic norm. We now present the convergence results for the Matching
Pursuit algorithm variants.

######  Theorem 2.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded and symmetric set, and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be $L$-smooth w.r.t. a given
norm $\|.\|$, over $\rho\operatorname{conv}(\mathcal{A})$ with $\rho<\infty$.
Then, Norm-Corrective Matching Pursuit (Algorithm 4), converges for $t\geq 0$
as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{4\left(\frac{2}{\delta}L\rho^{2}\operatorname{\mathrm{radius}}_{\|.\|\\!}(\mathcal{A})^{2}+\varepsilon_{0}\right)}{\delta
t+4}$

where $\varepsilon_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\star})$ is the
initial error in objective, and $\delta\in(0,1]$ is the relative accuracy of
the employed approximate LMO (6).

The proof of Theorem 2 extends the FW convergence analysis from
$\operatorname{conv}(\mathcal{A})$ to $\operatorname{lin}(\mathcal{A})$ by
rescaling $\operatorname{conv}(\mathcal{A})$ so that it includes
${\mathbf{x}}^{\star}$ and ${\mathbf{x}}_{t}$ for all $t\leq T$, the reason
for which the rate in Theorem 2 depends on the upper bound $\rho$ on the
atomic norm of ${\mathbf{x}}^{\star}$ and ${\mathbf{x}}_{t}$, $t\leq T$. The
relationship between Norm-Corrective FW and Norm-Corrective GMP is
systematically studied in Section 7.

Using well-known results from convex optimization, we can particularize
Theorem 2 for $f({\mathbf{x}}):=\frac{1}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$
and obtain iterate-independent constants (i.e., constants independent of
$\rho$) as follows.

######  Definition 3.

The effective inradius of a convex set $\mathcal{A}$, denoted by
$\operatorname{\mathrm{inr}}(\mathcal{A})$, is the radius of the largest
$d$-dimensional Euclidean ball which can be inscribed in $\mathcal{A}$, where
$d$ is the dimension of the subspace spanned by
$\operatorname{lin}(\mathcal{A})$.

######  Corollary 4.

Let $\mathcal{A}\in{\mathbb{R}}^{d}$ be a finite symmetric set of atoms, or
the convex hull of a finite set of atoms, and let
$\tilde{\rho}\geq\max\left\\{\|{\mathbf{x}}^{\star}\|,\|{\mathbf{x}}_{0}\|,\ldots,\|{\mathbf{x}}_{T}\|\right\\}$,
$\tilde{\rho}<\infty$. Then, under the conditions of Theorem 2, Algorithm 4
converges both with
$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{2\tilde{\rho}^{2}\operatorname{\mathrm{diam}}_{\|.\|\\!}(\mathcal{A})^{2}}{\delta^{2}\operatorname{\mathrm{inr}}(\operatorname{conv}(\mathcal{A}))^{2}(t+2)}$.
If further $f({\mathbf{x}}):=\frac{1}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$,
then $\tilde{\rho}$ can be replaced by $\|{\mathbf{y}}\|$.

The effective inradius
$\operatorname{\mathrm{inr}}(\operatorname{conv}(\mathcal{A}))$ generally
depends on the ambient space dimension $d$. For example, the effective
inradius of the L1-ball scales as $O(\sqrt{d})$. Hence, if $\mathcal{A}$ is
the L1-ball, Corollary 4 tells us that we need to take $T$ at least on the
order of $d$ to obtain an $O(1)$ error
$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$.

##  5 Linear Convergence Rates

It is possible to obtain faster convergence rates for some classes of
objective functions, still over arbitrary dictionaries. In this section, we
present linear convergence rates for our generalized matching pursuit,
Algorithm 4. While linear rates have recently been demonstrated for Frank-
Wolfe algorithm variants for strongly convex objectives by (Lacoste-Julien &
Jaggi, 2015), we are not aware of any existing _explicit_ linear convergence
rates for matching pursuit algorithms (see Section 8 for a discussion).

We begin our analysis by proposing a new geometric complexity measure of the
atom set which we call the minimal intrinsic directional width. It builds upon
the classic geometric width as follows:

######  Definition 5.

The _directional width of a set $\mathcal{A}$_ as a function of a given non-
zero vector ${\mathbf{d}}$ is defined as

$W_{\mathcal{A}}({\mathbf{d}}):=\max_{{\mathbf{z}}\in\mathcal{A}}\,\textstyle\langle\frac{{\mathbf{d}}}{\|{\mathbf{d}}\|},{\mathbf{z}}\rangle.\vspace{-2mm}$

In general, the directional width can be zero depending on the choice of
${\mathbf{d}}$. Building upon the the concept of directional width, we are
ready to define our main complexity constant, which will be crucial to our
linear convergence guarantees.

######  Definition 6.

Given a bounded set $\mathcal{A}$, we define its _minimal intrinsic
directional width_ as

$\operatorname{mDW(\mathcal{A})}:=\min_{\begin{subarray}{c}{\mathbf{d}}\in\operatorname{lin}(\mathcal{A})\\\
{\mathbf{d}}\neq\mathbf{0}\end{subarray}}W_{\mathcal{A}}({\mathbf{d}})\
.\vspace{-2mm}$

A crucial aspect of the preceding definition is that only directions in
$\operatorname{lin}(\mathcal{A})$ are allowed, hence the name intrinsic. If
the minimum was not over
${{\boldsymbol{d}}}\in\operatorname{lin}(\mathcal{A})$, the width would be
zero whenever $\mathcal{A}$ does not span the ambient space.

#### Properties.

Note that $\operatorname{mDW(\mathcal{A})}>0$ implies that the origin is in
the relative interior of $\operatorname{conv}(\mathcal{A})$ and hence the
atomic is well defined $\forall{\mathbf{x}}\in\operatorname{lin}(\mathcal{A})$
(which ensures that $\rho<\infty$). Furthermore, note how for a fixed sequence
of iterates and ${\mathbf{x}}^{\star}$ the value of $\rho$ is a monotone
decreasing function of the $\operatorname{mDW(\mathcal{A})}$. Moreover, any
symmetric set satisfies the property $\operatorname{mDW(\mathcal{A})}>0$. For
example, the L1 ball in ${\mathbb{R}}^{d}$ has
$\operatorname{mDW(\mathcal{A})}=\frac{1}{\sqrt{d}}$. The quantity
$\operatorname{mDW(\mathcal{A})}$ is meaningful for both undercomplete and
overcomplete, possibly continuous, atom sets, and plays a similar role as the
coherence in coherence-based convergence analysis of MPs (this is discussed in
more detail at the end of this section).

We now present our main linear convergence result for optimization over the
linear span of atoms as defined in (4). As we will only consider strongly
convex objective functions $f$, the optimum ${\mathbf{x}}^{\star}$ is unique
here, as opposed to the general context of our sub-linear rates.

######  Theorem 7.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set such that
$\operatorname{mDW(\mathcal{A})}>0$, and let the objective function
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be both globally $L$-smooth
and globally $\mu$-strongly convex w.r.t. a given norm $\|.\|$ over
$\rho\operatorname{conv}(\mathcal{A})$. Then, for $t\geq 0$, the suboptimality
of the iterates of Algorithm 4 decays exponentially as

$\varepsilon_{t+1}\leq\left(1-\delta^{2}\frac{\mu\operatorname{mDW(\mathcal{A})}^{2}}{L\operatorname{\mathrm{radius}}_{\|.\|\\!}(\mathcal{A})^{2}}\right)\varepsilon_{t},$

where $\varepsilon_{t}:=f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ is the
suboptimality at step $t$, and $\delta\in(0,1]$ is the relative accuracy
parameter of the employed approximate LMO (6).

Even though $\operatorname{mDW(\mathcal{A})}$ can take on values larger than
$1$ (depending on $\mathcal{A}$) the rate in Theorem 7 is always valid as
$\operatorname{mDW(\mathcal{A})}/\operatorname{\mathrm{radius}}_{\|.\|\\!}(\mathcal{A})<1$
for any non-empty $\mathcal{A}$.

We present an additional illustrative experiment measuring the practical
dependence of the convergence upon the defined
$\operatorname{mDW(\mathcal{A})}$ quantity in Appendix A.

#### Lower Bounds.

We continue by presenting a lower bound on the decay of the suboptimality of
the iterates for GMP. This lower bound depends on the width $W_{\mathcal{A}}$,
which shows that this quantity plays a fundamental role for the convergence of
GMP. We first consider the general strongly convex and smooth functions and
the particularize the result for the least-squares function
$f({\mathbf{x}}):=\frac{1}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$, which allows
to compute the update in closed-form. Furthermore, we consider only the case
of the exact oracle ($\delta=1$ in Equation (6)).

######  Theorem 8.

Assume that ${\mathbf{x}}^{\star}\in\operatorname{lin}(\mathcal{A})$ and let
${\mathbf{z}}_{t}$ be the atom selected at iteration $t$ by the LMO. Then,
under the assumptions of Theorem 7, the suboptimality of the iterates of
Algorithm 4 Variant 0 with an exact LMO ($\delta=1$) does not decay faster
than

$\varepsilon_{t+1}\geq\left(1-\frac{W_{\mathcal{A}}(-\nabla
f({\mathbf{x}}_{t}))^{2}}{\|{\mathbf{z}}_{t}\|^{2}}\frac{2L-\mu}{\mu}\right)\varepsilon_{t}\vspace{-1mm}$

Note that the lower bound on the exponential decay given in Theorem 8 depends
on the iteration $t$. We now particularize the result for the least-squares
function.

######  Corollary 9.

Let $\mathcal{A}:=\\{\pm{\mathbf{e}}_{i}\\}\subset{\mathbb{R}}^{d}$ be the
vertices of the L1 ball. Suppose we are minimizing
$f({\mathbf{x}}):=\frac{1}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$ over the
linear span of $\mathcal{A}$ with ${\mathbf{y}}\in{\mathbb{R}}^{d}$. Let
${\mathbf{x}}_{0}$ be the starting point of the Matching Pursuit Algorithm and
assume that $\forall i\in[d]\ ({\mathbf{x}}_{0})_{i}\neq y_{i}$. Then

$\varepsilon_{t+1}\geq\left(1-\frac{1}{d-t}\right)\varepsilon_{t}\
.\vspace{-3mm}$

This result is discussed in more detail in Appendix B.8.

#### Relationship between $\operatorname{mDW(\mathcal{A})}$ and cumulative
coherence.

It is interesting to compare the rate in Theorem 2 with the coherence-based
rates from the literature, such as Gribonval & Vandergheynst (2006). In order
to relate the two notions of cumulative coherence and directional width, we
need some additional assumptions. We only consider the least-squares function
in ${\mathbb{R}}^{d}$ and assume that its minimizer over ${\mathbb{R}}^{d}$
lies in the span of the atom set $\mathcal{A}$. Further, we require symmetry
so that the definition of LMO given in Equation (1) is equivalent (up to the
sign) to the one used for MP in Gribonval & Vandergheynst (2006).

######  Theorem 10.

Let $\mathcal{A}\subset{\mathbb{R}}^{d}$ be a symmetric set of $2n$ atoms with
$\|{\mathbf{s}}\|_{2}=1$ for all ${\mathbf{s}}\in\mathcal{A}$. Let
$\mathcal{B}$ be a set such that $\mathcal{A}=\mathcal{B}\cup-\mathcal{B}$
with $\mathcal{B}\cap-\mathcal{B}=\emptyset$ and $|\mathcal{B}|=n$. Then, the
cumulative coherence of the set $\mathcal{B}$, defined as
$\mu(\mathcal{B},m):=\max_{\mathcal{I}\subset\mathcal{B},|\mathcal{I}|=m}\max_{{\mathbf{s}}_{i}\in\mathcal{B}\backslash\mathcal{I}}\sum_{{\mathbf{s}}_{j}\in\mathcal{I}}|\langle{\mathbf{s}}_{i},{\mathbf{s}}_{j}\rangle|$,
$m<n$, is lower-bounded as $\mu(\mathcal{B},n-1)\geq
1-n\cdot\operatorname{mDW(\mathcal{A})}^{2}$.

In essence, Theorem 10 shows that if the directional width is close to zero,
the cumulative coherence is close to 1 with a factor that depends on $n$. Note
that by increasing the number of atoms, both the cumulative coherence and
$\operatorname{mDW(\mathcal{A})}$ grow. Recall that when the cumulative
coherence is 1, according to the rate for MP in Gribonval & Vandergheynst
(2006) there is no linear convergence. Furthermore, our rate is more robust
than the one in Gribonval & Vandergheynst (2006) in the following sense. An
adversary could add an atom to the dictionary, making the coherence 1. In
contrast, adding an atom cannot make $\operatorname{mDW(\mathcal{A})}=0$. In
addition, if the atom is added so that $\operatorname{mDW(\mathcal{A})}$ is
arbitrarily small, the cumulative coherence is arbitrarily close to 1 by
Theorem 10. Finally, the linear rate for MP presented in Gribonval &
Vandergheynst (2006) assumes that the optimum can be represented exactly using
$m$ atoms. Therefore, the rate depends on $\mu(\mathcal{B},m-1)$ while
$\operatorname{mDW(\mathcal{A})}$ can be compared only to the cumulative
coherence of the whole set (i.e., $\mu(\mathcal{B},n-1)$) since it is an
intrinsic property of the atom set.

##  6 Affine Invariant Algorithms and Rates

We now present affine invariant versions of Algorithms 3 and 4, along with
sub-linear and linear convergence guarantees. An optimization method is called
_affine invariant_ if it is invariant under affine transformations of the
input problem: If one chooses any re-parameterization of the domain
$\mathcal{Q}$ by a _surjective_ linear or affine map
${\mathbf{M}}:\hat{\mathcal{Q}}\rightarrow\mathcal{Q}$, then the “old” and
“new” optimization problems $\min_{{\mathbf{x}}\in\mathcal{Q}}f({\mathbf{x}})$
and $\min_{\hat{\mathbf{x}}\in\hat{\mathcal{Q}}}\hat{f}(\hat{\mathbf{x}})$ for
$\hat{f}(\hat{\mathbf{x}}):=f({\mathbf{M}}\hat{\mathbf{x}})$ look the same to
the algorithm.

###  6.1 Affine Invariant Frank-Wolfe

To define an affine invariant upper bound on the objective function $f$, we
use the affine invariant definition of the _curvature constant_ from Jaggi
(2013)

$C_{f,\mathcal{A}}:=\sup_{\begin{subarray}{c}{\mathbf{s}}\in\mathcal{A},\,{\mathbf{x}}\in\operatorname{conv}(\mathcal{A})\\\
\gamma\in[0,1]\\\
{\mathbf{y}}={\mathbf{x}}+\gamma({\mathbf{s}}-{\mathbf{x}})\end{subarray}}\frac{2}{\gamma^{2}}D({\mathbf{y}},{\mathbf{x}}),\vspace{-1mm}$
(8)

where for cleaner exposition, we have used the shorthand notation
$D({\mathbf{y}},{\mathbf{x}})$ to denote the difference of $f({\mathbf{y}})$
and its linear approximation at ${\mathbf{x}}$, i.e.,

$D({\mathbf{y}},{\mathbf{x}}):=f({\mathbf{y}})-f({\mathbf{x}})-\langle{\mathbf{y}}-{\mathbf{x}},\nabla
f({\mathbf{x}})\rangle.$

Bounded curvature $C_{f,\mathcal{A}}$ closely corresponds to smoothness of the
objective $f$. More precisely, if $\nabla f$ is $L$-Lipschitz continuous on
$\operatorname{conv}(\mathcal{A})$ with respect to some arbitrary chosen norm
${\left\lVert.\right\rVert}$, i.e., ${\left\lVert\nabla f({\mathbf{x}})-\nabla
f({\mathbf{y}})\right\rVert}_{*}\leq
L{\left\lVert{\mathbf{x}}-{\mathbf{y}}\right\rVert}$, where $\|.\|_{*}$ is the
dual norm of $\|.\|$, then

$C_{f,\mathcal{A}}\leq
L\operatorname{\mathrm{diam}}_{{\left\lVert.\right\rVert}}(\mathcal{A})^{2}\
,$ (9)

where $\operatorname{\mathrm{diam}}_{{\left\lVert.\right\rVert}}(.)$ denotes
the ${\left\lVert.\right\rVert}$-diameter, see (Jaggi, 2013, Lemma 7). The
curvature constant $C_{f,\mathcal{A}}$ is affine invariant, does not depend on
any norm. It combines the complexity of the domain
$\operatorname{conv}(\mathcal{A})$ and the curvature of the objective function
$f$ into a single quantity.

We are now ready to present the affine invariant version of the Norm-
Corrective Frank-Wolfe algorithm (Algorithm 3).

Algorithm 5 Affine Invariant Frank-Wolfe

Same as Algorithm 3, except,

5\. $\gamma:=\operatorname{clip}_{[0,1]}\\!\big{[}\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle/C_{f,\mathcal{A}}\big{]}$

6\. Update
${\mathbf{x}}_{t+1}:={\mathbf{x}}_{t}+\gamma({\mathbf{z}}_{t}-{\mathbf{x}}_{t})$

The following theorem characterizes the sub-linear convergence rate of
Algorithm 5.

######  Theorem 11.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be a convex function with
curvature $C_{f,\mathcal{A}}$ over $\mathcal{A}$ as defined in (8). Then, the
Affine Invariant Frank-Wolfe algorithm (Algorithm 5) converges for $t\geq 0$
as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{2\left(\frac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)}{\delta
t+2}$

where $\varepsilon_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\star})$ is the
initial error in objective, and $\delta\in(0,1]$ is the accuracy parameter of
the employed approximate LMO (Equation (5)).

###  6.2 Affine Invariant Generalized Matching Pursuit

To design an affine invariant MP algorithm we will rely on the following
slight variation of $C_{f,\mathcal{A}}$ (defined in (8)) using
${\mathbf{y}}={\mathbf{x}}+\gamma{\mathbf{s}}$ instead of
${\mathbf{y}}={\mathbf{x}}+\gamma({\mathbf{s}}-{\mathbf{x}})$, i.e.,

$C_{f,\mathcal{A}}^{\textsf{MP}}:=\sup_{\begin{subarray}{c}{\mathbf{s}}\in\mathcal{A},\,{\mathbf{x}}\in\operatorname{conv}(\mathcal{A})\\\
\gamma\in[0,1]\\\
{\mathbf{y}}={\mathbf{x}}+\gamma{\mathbf{s}}\end{subarray}}\frac{2}{\gamma^{2}}D({\mathbf{y}},{\mathbf{x}}).$
(10)

Throughout this section, we again assume availability of a finite constant
$\rho>0$ as an upper bound of the atomic norms $\|.\|_{\mathcal{A}}$ of the
optimum ${\mathbf{x}}^{\star}$, as well as the iterate sequence
$({\mathbf{x}}_{t})_{t=0}^{T}$ up to the current iteration, as defined in (7).
We now present the affine invariant version of the Norm-Corrective GMP
algorithm (Algorithm 4, Variant 0) in Algorithm 6. The algorithm uses the
bounded curvature $C_{f,\rho\mathcal{A}}^{\textsf{MP}}$ over the rescaled set
$\rho\operatorname{conv}(\mathcal{A})$, rather than
$\operatorname{conv}(\mathcal{A})$.

Algorithm 6 Affine Invariant Generalized Matching Pursuit

Same as Algorithm 4 except,

5\. Variant 1: $\gamma:=\langle-\nabla
f({\mathbf{x}}_{t}),\rho^{2}{\mathbf{z}}_{t}\rangle/C_{f,\rho\mathcal{A}}^{\textsf{MP}}$

6\. Update ${\mathbf{x}}_{t+1}:={\mathbf{x}}_{t}+\gamma{\mathbf{z}}_{t}$

5\. Variant 2:
${\mathbf{x}}_{t+1}=\operatorname*{arg\,min}_{{\mathbf{x}}\in\operatorname{lin}(\mathcal{S})}f({\mathbf{x}})$

A sub-linear convergence guarantee for Algorithm 6 is presented in the
following theorem.

######  Theorem 12.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded and symmetric set such that
$\rho<\infty$. Then, Algorithm 6 converges for $t\geq 0$ as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{2\left(\frac{2}{\delta}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{\frac{\delta}{2}t+2},\vspace{-1mm}$

where $\delta\in(0,1]$ is the relative accuracy parameter of the employed
approximate LMO (6).

Exact knowledge of $C_{f,\rho\mathcal{A}}^{\textsf{MP}}$ is not required: The
same theorem also holds if any upper bound on
$C_{f,\rho\mathcal{A}}^{\textsf{MP}}$ is used in the algorithm and resulting
rate instead. Note further that the convergence guarantee in Theorem 12 is
linear invariant only as the assumption of $\mathcal{A}$ being symmetric
precludes affine maps involving translations.

We proceed by establishing a linear convergence guarantee for Algorithm 6. For
lower-bounding the error at iteration $t$, we need to define an affine
invariant analog of strong convexity over the requisite domain. The following
positive step size quantity relates the dual certificate value of the descent
direction ${\mathbf{x}}^{\star}-{\mathbf{x}}$ with the MP selected atom,

$\gamma({\mathbf{x}},{\mathbf{x}}^{\star}):=\frac{\langle-\nabla
f({\mathbf{x}}),{\mathbf{x}}^{\star}-{\mathbf{x}}\rangle}{\langle-\nabla
f({\mathbf{x}}),{\mathbf{s}}({\mathbf{x}})\rangle}\ ,$ (11)

for
${\mathbf{s}}({\mathbf{x}}):=\operatorname*{arg\,min}_{{\mathbf{s}}\in\mathcal{A}}\
\langle\nabla f({\mathbf{x}}),{\mathbf{s}}\rangle$.

A quantity similar to (11) but using a different direction
${\mathbf{s}}({\mathbf{x}})$ was also used by (Lacoste-Julien & Jaggi, 2015)
to study linear convergence of FW variants. We now define the complexity
measure $\mu_{f,\mathcal{A}}^{\textsf{MP}}$, which serves as an affine
invariant notion of strong convexity of the objective $f$, over the domain
$\operatorname{conv}(\mathcal{A})$.

$\mu_{f,\mathcal{A}}^{\textsf{MP}}:=\inf_{{\mathbf{x}}\in\operatorname{conv}(\mathcal{A})}\inf_{\begin{subarray}{c}{\mathbf{x}}^{\star}\in\operatorname{conv}(\mathcal{A})\\\
\langle\nabla
f({\mathbf{x}}),{\mathbf{x}}^{\star}-{\mathbf{x}}\rangle<0\end{subarray}}\frac{2}{\gamma({\mathbf{x}},{\mathbf{x}}^{\star})^{2}}D({\mathbf{x}}^{\star},{\mathbf{x}}).\vspace{-1mm}$
(12)

In the following, our results will depend on
$\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}$, which is this quantity
$\mu_{f,\mathcal{A}}^{\textsf{MP}}$ taken over the scaled set
$\rho\mathcal{A}$ instead of $\mathcal{A}$. This is analogous to the
smoothness parameter $C_{f,\mathcal{A}}^{\textsf{MP}}$ as we have seen in the
previous results. Theorem 13 characterizes the linear convergence of Algorithm
6.

######  Theorem 13.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set. Then, Algorithm 6
converges linearly as

$\varepsilon_{t+1}\leq\bigg{(}1-\delta^{2}\frac{\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}}{C_{f,\rho\mathcal{A}}^{\textsf{MP}}}\bigg{)}\varepsilon_{t}\vspace{-1mm}$

where $\varepsilon_{t}:=f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ is the
suboptimality at step $t$, and $\delta\in(0,1]$ is the relative accuracy
parameter of the employed approximate LMO (6).

#### Discussion:

Note that the new affine invariant convergence rates in Theorems 11, 12, and
13 do imply the rates presented earlier for their norm-based algorithm
counterparts in Theorems 1, 2, and 7, respectively, for any choice of norm.
This follows simply establishing the relationships between $C_{f,\mathcal{A}}$
and $L$ (see (9)) and accordingly for the strong convexity notion
$\mu_{f,\mathcal{A}}^{\textsf{MP}}$ compared to $\mu$. For the latter, it is
not hard to show that if $\operatorname{mDW(\mathcal{A})}>0$,
$\mu_{f,\mathcal{A}}^{\textsf{MP}}\geq\mu\operatorname{mDW(\mathcal{A})}^{2}$,
see Lemma 16 in the appendix. The affine invariant convergence guarantees are
therefore more general than the norm-based ones.

##  7 On the Relationship Between Matching Pursuit and Frank-Wolfe

The sub-linear convergence rates for MP and FW are related by the constant
$\rho$ that essentially simulates a “blown up” set in which the analysis of FW
can be applied. In this section, we explore this relationship.

Let $\alpha\mathcal{A}:=\\{\alpha{\mathbf{z}}\ |\
{\mathbf{z}}\in\mathcal{A}\\}$, and assume $\alpha\geq\frac{\rho}{\delta}$. We
will consider Norm-Corrective FW (Algorithm 3) on the set $\alpha\mathcal{A}$
and analyze its behavior when $\alpha$ grows to infinity, relating the
iterates of Algorithm 3 with the ones of Algorithm 4.

######  Theorem 14.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be a $L$-smooth convex
function. Let $\alpha>0$ and let us fix $t>0$ with iterate ${\mathbf{x}}_{t}$.
There exists a polynomial function $\theta(f,{\mathbf{x}}_{t},\alpha)$ such
that if $\theta(f,{\mathbf{x}}_{t},\alpha)\leq 1$ the new iterate
${\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}$ of Frank-Wolfe (Algorithm 2) using
the set $\alpha\mathcal{A}$ converges to the new iterate
${\mathbf{x}}_{t+1}^{\textsf{MP}}$ of Matching Pursuit (Algorithm 4) applied
on the linear span of the set $\mathcal{A}$ with rate:

$\big{\|}{\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}-{\mathbf{x}}_{t+1}^{\textsf{MP}}\big{\|}\in
O\left(\frac{1}{\alpha}\right).$

In particular, when $\alpha$ grows to infinity, the condition
$\theta(f,{\mathbf{x}}_{t},\alpha)\leq 1$ always holds (for all steps $t$).
Otherwise, the difference of the iterates satisfies
$\big{\|}{\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}-{\mathbf{x}}_{t+1}^{\textsf{MP}}\big{\|}\in
O\left({\alpha}\right).$

Our analysis shows that, in some sense, FW can be suitable to solve the
optimization problem (4). Indeed, if we knew the atomic norm of the iterates
and the optimum in advance (which is usually not the case in practice), we
could just consider a large enough convex set and run FW (Algorithm 2) on
$\alpha\mathcal{A}$ with $\alpha=\rho$ ($\rho$ as defined in Section 4) for an
exact oracle (this can be seen in the proof of Theorem 2).

##  8 Relation to Prior Generalizations of MP

Shalev-Shwartz et al. (2010), Temlyakov (2013, 2014, 2015), and Nguyen &
Petrova (2014) propose and study algorithms similar to Algorithm 4—although
using the objective function directly in the update step instead of a
quadratic upper bound—for the optimization of smooth functions on Banach
spaces. Nguyen & Petrova (2014) consider orthonormal bases as dictionaries
only. The sub-linear rates derived in Temlyakov (2013, 2014, 2015); Nguyen &
Petrova (2014) are similar to ours, whereas the linear rates in Temlyakov
(2013, 2014) critically rely on incoherence and approximate sparsity (of the
optimal solution) assumptions. Most importantly, these linear rates only hold
for a finite number of iterations that is related to the sparsity level of the
solution. Note that the linear rates for (least-squares) MP and OMP in
Gribonval & Vandergheynst (2006) hold under similar incoherence and sparsity
assumptions. The linear rates for a fully-corrective GMP variant in Shalev-
Shwartz et al. (2010) holds under a (sparsity-based) restricted strong
convexity assumption.

Much more general rates are known for the class of random pursuit algorithms —
which are derivative-free and use random directions instead of an LMO — as
shown by Stich et al. (2013). These rates only apply to the unconstrained
setting $\mathcal{A}={\mathbb{R}}^{d}$ (so do not cover the general Hilbert-
space case) and do scale with the dimension as $\Theta(d)$, whereas our rates
are dimension independent (but need an LMO).

In the statistics community, very related methods are studied under the names
of, e.g., forward selection and stage-wise algorithms, see (Tibshirani, 2015)
for a recent overview. The stage-wise framework considers the evolution of the
solution—the regularization path—as the scaling of the constraint set grows
(or the corresponding regularizer weakens). Our results can help to also equip
such algorithms with explicit convergence rate, at any fixed regularizer
value.

To the best of our knowledge, the only prior work on greedy optimization that
also relies on a quadratic upper bound of the (smooth) objective function in
the update step is Yao & Kwok (2016). However, Yao & Kwok (2016) specifically
targets matrix completion, considers the set of unit norm rank-one matrices as
dictionary only, and obtains problem-specific (i.e., matrix-specific) and
iterate-dependent (implicit) sub-linear and linear rates. Hence, the setting
considered here, i.e., functions on Hilbert spaces and general dictionaries,
and the linear rate depending only on geometric properties of the dictionary
enjoy much higher generality.

Finally, recovery guarantees for sparse solutions of convex optimization
problems using generalized MPs were proposed, e.g., in Blumensath & Davies
(2008); Zhang (2011).

#### Acknowledgments:

The authors thank Zaid Harchaoui and Gunnar Rätsch for fruitful discussions.
FL is supported by the Max Plank-ETH Center for Learning Systems.

## References

  * Blumensath & Davies (2008) Blumensath, Thomas and Davies, Mike E.  Gradient pursuit for non-linear sparse signal modelling.  In _European Signal Processing Conference_ , pp. 1–5. IEEE, 2008\.
  * Chandrasekaran et al. (2012) Chandrasekaran, Venkat, Recht, Benjamin, Parrilo, Pablo A., and Willsky, Alan S.  The convex geometry of linear inverse problems.  _Foundations of Computational Mathematics_ , 12(6):805–849, 2012.
  * Chen et al. (1989) Chen, Sheng, Billings, Stephen A, and Luo, Wan.  Orthogonal least squares methods and their application to non-linear system identification.  _International Journal of control_ , 50(5):1873–1896, 1989.
  * Davenport & Wakin (2010) Davenport, Mark A and Wakin, Michael B.  Analysis of orthogonal matching pursuit using the restricted isometry property.  _IEEE Transactions on Information Theory_ , 56(9):4395–4401, 2010.
  * DeVore & Temlyakov (1996) DeVore, Ronald A. and Temlyakov, Vladimir N.  Some remarks on greedy algorithms.  _Adv. Comput. Math._ , 5(1):173–187, 1996.
  * Frank & Wolfe (1956) Frank, M and Wolfe, P.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 1956.
  * Gribonval & Vandergheynst (2006) Gribonval, Rémi and Vandergheynst, P.  On the exponential convergence of matching pursuits in quasi-incoherent dictionaries.  _IEEE Transactions on Information Theory_ , 52(1):255–261, 2006.
  * Gunasekar et al. (2014) Gunasekar, Suriya, Ravikumar, Pradeep, and Ghosh, Joydeep.  Exponential family matrix completion under structural constraint.  In _International Conference on Machine Learning (ICML)_ , jun 2014\.
  * Guo et al. (2017) Guo, Xiawei, Yao, Quanming, and Kwok, James T.  Efficient sparse low-rank tensor completion using the Frank-Wolfe algorithm.  In _AAAI Conference on Artificial Intelligence_ , 2017.
  * Holloway (1974) Holloway, Charles A.  An extension of the frank and Wolfe method of feasible directions.  _Mathematical Programming_ , 6(1):14–27, 1974\.
  * Jaggi (2013) Jaggi, Martin.  Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization.  In _ICML 2013 - Proceedings of the 30th International Conference on Machine Learning_ , 2013.
  * Lacoste-Julien & Jaggi (2015) Lacoste-Julien, Simon and Jaggi, Martin.  On the Global Linear Convergence of Frank-Wolfe Optimization Variants.  In _NIPS 2015_ , pp. 496–504, 2015.
  * Lacoste-Julien et al. (2013) Lacoste-Julien, Simon, Jaggi, Martin, Schmidt, Mark, and Pletscher, Patrick.  Block-Coordinate Frank-Wolfe Optimization for Structural SVMs.  In _ICML 2013 - Proceedings of the 30th International Conference on Machine Learning_ , 2013.
  * Laue (2012) Laue, Sören.  A Hybrid Algorithm for Convex Semidefinite Optimization.  In _ICML_ , 2012.
  * Mallat & Zhang (1993) Mallat, Stéphane and Zhang, Zhifeng.  Matching pursuits with time-frequency dictionaries.  _IEEE Transactions on Signal Processing_ , 41(12):3397–3415, 1993.
  * Nguyen & Petrova (2014) Nguyen, Hao and Petrova, Guergana.  Greedy strategies for convex optimization.  _Calcolo_ , pp. 1–18, 2014.
  * Rao et al. (2015) Rao, Nikhil, Shah, Parikshit, and Wright, Stephen J.  Forward - Backward Greedy Algorithms for Atomic Norm Regularization.  _IEEE Transactions on Signal Processing_ , 63(21):5798–5811, 2015.
  * Romera-Paredes et al. (2013) Romera-Paredes, Bernardino, Aung, Hane, Bianchi-Berthouze, Nadia, and Pontil, Massimiliano.  Multilinear multitask learning.  In _Proceedings of the 30th International Conference on Machine Learning_ , pp. 1444–1452, 2013.
  * Shalev-Shwartz et al. (2010) Shalev-Shwartz, Shai, Srebro, Nathan, and Zhang, Tong.  Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints.  _SIAM Journal on Optimization_ , 20:2807–2832, 2010.
  * Soltanolkotabi & Candès (2012) Soltanolkotabi, Mahdi and Candès, Emmanuel J.  A geometric analysis of subspace clustering with outliers.  _The Annals of Statistics_ , 40(4):2195–2238, 2012.
  * Stich et al. (2013) Stich, S U, Müller, C L, and Gärtner, Bernd.  Optimization of Convex Functions with Random Pursuit.  _SIAM Journal on Optimization_ , 23(2):1284–1309, April 2013.
  * Temlyakov (2013) Temlyakov, Vladimir.  Chebushev Greedy Algorithm in convex optimization.  _arXiv.org_ , December 2013.
  * Temlyakov (2014) Temlyakov, Vladimir.  Greedy algorithms in convex optimization on Banach spaces.  In _48th Asilomar Conference on Signals, Systems and Computers_ , pp. 1331–1335. IEEE, 2014.
  * Temlyakov (2015) Temlyakov, VN.  Greedy approximation in convex optimization.  _Constructive Approximation_ , 41(2):269–296, 2015.
  * Tibshirani (2015) Tibshirani, Ryan J.  A general framework for fast stagewise algorithms.  _Journal of Machine Learning Research_ , 16:2543–2588, 2015\.
  * Tropp (2004) Tropp, Joel A.  Greed is good: algorithmic results for sparse approximation.  _IEEE Transactions on Information Theory_ , 50(10):2231–2242, 2004.
  * Wang et al. (2014) Wang, Zheng, jun Lai, Ming, Lu, Zhaosong, Fan, Wei, Davulcu, Hasan, and Ye, Jieping.  Rank-one matrix pursuit for matrix completion.  In _ICML_ , pp. 91–99, 2014.
  * Yang et al. (2015) Yang, Yuning, Mehrkanoon, Siamak, and Suykens, Johan A K.  Higher order Matching Pursuit for Low Rank Tensor Learning.  _arXiv.org_ , March 2015.
  * Yao & Kwok (2016) Yao, Quanming and Kwok, James T.  Greedy learning of generalized low-rank models.  In _IJCAI_ , 2016.
  * Zhang (2011) Zhang, Tong.  Sparse Recovery With Orthogonal Matching Pursuit Under RIP.  _IEEE Transactions on Information Theory_ , 57(9):6215–6221, 2011.
  * Ziegler (1995) Ziegler, Günter M.  _Lectures on Polytopes_ , volume 152 of _Graduate Texts in Mathematics_.  Springer Verlag, 1995.

##  Appendix A An Illustrative Experiment

In this section we numerically investigate the tightness of the linear rate
presented in Theorem 7 and illustrate the impact of the
$\operatorname{mDW(\mathcal{A})}$ on the empirical rate of Algorithm 4
(Variant 0, with exact LMO). The experiment setup is the following. We
minimize the function
$f({\mathbf{x}})=\|{\mathbf{x}}^{\star}-{\mathbf{x}}\|^{2}$ over the set

$\mathcal{A}:=\\{\mathcal{A}_{\theta}\cup-\mathcal{A}_{\theta}\\}\ \text{
where }\ \mathcal{A}_{\theta}:=\Big{\\{}{1\choose
0},{\cos\theta\choose\sin\theta}\Big{\\}}\vspace{-2mm}$

with $\theta\in(0,\pi/2]$ and
${\mathbf{x}}^{\star}:=\left(-1,1\right)^{\top}$.

This choice for the set $\mathcal{A}$ allows to control
$\operatorname{mDW(\mathcal{A})}$ by acting on $\theta$. In Figure 1 we plot
the ratio between the theoretical linear rate in Theorem 7 and the empirical
rate, averaged over 20 random initializations chosen within
$\operatorname{conv}(\mathcal{A})$. The rate is tight when the bound on the
error decrease matches the empirical decay, i.e., when their ratio is equal to
1. It can be seen that the upper bound in Theorem 7 is within a factor 2.5 of
the empirical rate on average.

Figure 1: Ratio of theoretical rate and empirical rate, minimum, maximum and
average ratio over 20 runs from random starting point in
$\operatorname{conv}(\mathcal{A})$.

##  Appendix B Proofs of the Main Results

An optimization method is called _affine invariant_ if it is invariant under
affine transformations of the input problem: If one chooses any re-
parameterization of the domain $\mathcal{Q}$ by a _surjective_ linear or
affine map ${\mathbf{M}}:\hat{\mathcal{Q}}\rightarrow\mathcal{Q}$, then the
“old” and “new” optimization problems
$\min_{{\mathbf{x}}\in\mathcal{Q}}f({\mathbf{x}})$ and
$\min_{\hat{\mathbf{x}}\in\hat{\mathcal{Q}}}\hat{f}(\hat{\mathbf{x}})$ for
$\hat{f}(\hat{\mathbf{x}}):=f({\mathbf{M}}\hat{\mathbf{x}})$ look the same to
the algorithm Jaggi (2013).

###  B.1 Sublinear FW rate

######  Theorem’ 11.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be a convex function with
curvature $C_{f,\mathcal{A}}$ over $\mathcal{A}$ as defined in (8). Then, the
Frank-Wolfe method (Algorithm 2) with step-size variants 1 and 2, converges
for $t\geq 0$ as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{2\left(\frac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)}{\delta
t+2}$

where $\varepsilon_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\star})$ is the
initial error in objective, and $\delta\in(0,1]$ is the accuracy parameter of
the employed approximate LMO (Equation (5)).

###### Proof.

At iteration $t$, let ${\mathbf{z}}_{t}\in\mathcal{A}$ be the atom selected by
the Approx-LMO. The key to the proof is to use the definition of the curvature
constant $C_{f,\mathcal{A}}$ as to give an affine invariant upper bound on the
objective $f$:

$\displaystyle
f({\mathbf{x}}_{t}+\gamma({\mathbf{z}}_{t}-{\mathbf{x}}_{t}))\leq\ $
$\displaystyle
g_{{\mathbf{x}}_{t}}({\mathbf{x}}_{t}+\gamma({\mathbf{z}}_{t}-{\mathbf{x}}_{t})):=$
(13) $\displaystyle f({\mathbf{x}}_{t})+\gamma\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}$
$\displaystyle-{\mathbf{x}}_{t}\rangle+\frac{\gamma^{2}}{2}C_{f,\mathcal{A}}.$

By computing the closed-form-solution for $\gamma$ minimizing the right hand
side, we have

$\gamma=\frac{\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{C_{f,\mathcal{A}}}\
.$ (14)

This is exactly the update-step used by variant 2 of the FW algorithm
(Algorithm 2). In other words, the algorithm in each iteration performs a step
as to minimize this upper bound to $f$, over the line segment
$[{\mathbf{x}}_{t},{\mathbf{z}}]$.

Writing $\varepsilon_{t}:=f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ for the
suboptimality, we apply the certificate property of the duality gap,
$\varepsilon_{t}\leq\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle$. Combining this
with the given approximation quality $\delta\in(0,1]$ of the used Approx-LMO,
we have

$\delta\varepsilon_{t}\leq\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle\ .$

Continuing from (B.1),

$\displaystyle\varepsilon_{t+1}$
$\displaystyle\leq\varepsilon_{t}+\min_{\gamma\in[0,1]}\left\\{-\gamma\delta\varepsilon_{t}+\frac{\gamma^{2}}{2}C_{f,\mathcal{A}}\right\\}$
$\displaystyle\leq\varepsilon_{t}-\frac{2}{\delta
t+2}\delta\varepsilon_{t}+\frac{1}{2}\left(\frac{2}{\delta
t+2}\right)^{2}C_{f,\mathcal{A}}$

Finally, we show by induction

$\varepsilon_{t}\leq
2\frac{\left(\frac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)}{\delta
t+2}.$

for $t\geq 0$.

When $t=0$ we get
$\varepsilon_{0}\leq\left(\frac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)$.
Therefore, the base case holds. We now prove the induction step assuming
$\varepsilon_{t}\leq\tfrac{2\left(\tfrac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)}{\delta
t+2}$.

$\displaystyle\varepsilon_{t+1}$
$\displaystyle\leq\left(1-\tfrac{2\delta}{\delta
t+2}\right)\varepsilon_{t}+\tfrac{1}{2}C_{f,\mathcal{A}}\left(\tfrac{2}{\delta
t+2}\right)^{2}$ $\displaystyle\leq\left(1-\tfrac{2\delta}{\delta
t+2}\right)\tfrac{2\left(\tfrac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)}{\delta
t+2}$ $\displaystyle\quad+\tfrac{1}{2}\left(\tfrac{2}{\delta
t+2}\right)^{2}C_{f,\mathcal{A}}+\tfrac{2}{(\delta
t+2)^{2}}\delta\varepsilon_{0}$
$\displaystyle=\tfrac{2\left(\tfrac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)}{\delta
t+2}\left(1-\tfrac{2\delta}{\delta t+2}+\tfrac{\delta}{\delta t+2}\right)$
$\displaystyle\leq\tfrac{2\left(\tfrac{1}{\delta}C_{f,\mathcal{A}}+\varepsilon_{0}\right)}{\delta(t+1)+2}$

The same rate will hold for variant 1 (line-search on the true $f$) of
Algorithm 2, since the resulting objective per step will always be at least as
good as the pre-determined step-size as in variant 2. ∎

#### Norm-based Variants.

Note that for any choice of norm $\|.\|$, the analogous sublinear convergence
rates do hold if the objective function is L-smooth (i.e., $\nabla f$ is
$L$-Lipschitz) with respect to the norm $\|.\|$.

######  Theorem’ 1.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be $L$-smooth w.r.t. a given
norm $\|.\|$, over $\operatorname{conv}(\mathcal{A})$. Then, the Frank-Wolfe
method (Algorithm 2) , as well as Norm-Corrective Frank-Wolfe (Algorithm 3),
converge for $t\geq 0$ as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{2\left(\frac{1}{\delta}L\operatorname{\mathrm{diam}}_{\|.\|\\!}(\mathcal{A})^{2}+\varepsilon_{0}\right)}{\delta
t+2}$

where $\varepsilon_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\star})$ is the
initial error in objective, and $\delta\in(0,1]$ is the accuracy parameter of
the employed approximate LMO (Equation (5)).

###### Proof.

The proof for variant 3 of Algorithm 2 follows directly from the fact that any
norm gives an upper bound on $C_{f,\mathcal{A}}$, as shown in (9).

For variant 4 of Algorithm 2, as well as for the Norm-Corrective Frank-Wolfe
(Algorithm 3), the analogous convergence rate follows by using the quadratic
upper bound

$g_{{\mathbf{x}}_{t}}({\mathbf{x}})=f({\mathbf{x}}_{t})+\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}-{\mathbf{x}}_{t}\rangle+\frac{L}{2}\|{\mathbf{x}}-{\mathbf{x}}_{t}\|^{2}$
(15)

instead of (B.1) in the above proof. ∎

Also compare the above proof to Theorem C.1 Lacoste-Julien et al. (2013),
which can be extended to the same algorithm variants as of our interest here.

###  B.2 Sublinear MP rates

######  Theorem’ 12.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded and symmetric set and let
$\rho:=\max\left\\{\|{\mathbf{x}}^{\star}\|_{\mathcal{A}},\|{\mathbf{x}}_{0}\|_{\mathcal{A}},\ldots,\|{\mathbf{x}}_{T}\|_{\mathcal{A}}\right\\}$.
Then, Algorithm 6 converges for $t\geq 0$ as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{4\left(\frac{2}{\delta}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{\delta
t+4},$

where $\delta\in(0,1]$ is the relative accuracy parameter of the employed
approximate LMO (6).

###### Proof.

Recall that $\tilde{{\mathbf{z}}}_{t}$ is the atom selected in iteration $t$
by the approximate LMO defined in (6). We start by upper-bounding $f$ on
$\rho\operatorname{conv}(\mathcal{A})$ using the definition of
$C_{f,\rho\mathcal{A}}^{\textsf{MP}}$ as follows

$\displaystyle f({\mathbf{x}}_{t+1})$ $\displaystyle\leq$
$\displaystyle\min_{\gamma\in[0,1]}f({\mathbf{x}}_{t})+\gamma\langle\nabla
f({\mathbf{x}}_{t}),\rho\tilde{{\mathbf{z}}}_{t}\rangle+\frac{\gamma^{2}}{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}}$
(16) $\displaystyle\leq$ $\displaystyle
f({\mathbf{x}}_{t})+\min_{\gamma\in[0,1]}\left\\{-\frac{\delta}{2}\gamma\varepsilon_{t}+\frac{\gamma^{2}}{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}}\right\\},$

where the first inequality holds for Algorithm 6 because the step size in
Algorithm 6 is chosen by minimizing the RHS over $\gamma\in{\mathbb{R}}$. To
get the second inequality note that both $-{\mathbf{x}}_{t}$ and
${\mathbf{x}}^{\star}$ are in $\rho\cdot\operatorname{conv}(\mathcal{A})$ by
symmetry. We therefore have the following sequence of inequalities

$\displaystyle\langle\nabla
f({\mathbf{x}}_{t}),-2\frac{\rho}{\delta}\tilde{{\mathbf{z}}}_{t}\rangle$
$\displaystyle=\langle\nabla
f({\mathbf{x}}_{t}),-\frac{\rho}{\delta}\tilde{{\mathbf{z}}}_{t}\rangle+\langle\nabla
f({\mathbf{x}}_{t}),-\frac{\rho}{\delta}\tilde{{\mathbf{z}}}_{t}\rangle$
$\displaystyle\geq\langle\nabla
f({\mathbf{x}}_{t}),-\rho{\mathbf{z}}_{t}\rangle+\langle\nabla
f({\mathbf{x}}_{t}),-\rho{\mathbf{z}}_{t}\rangle$ (17)
$\displaystyle\geq\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}_{t}-{\mathbf{x}}^{\star}\rangle$ (18)
$\displaystyle\geq
f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})=:\varepsilon_{t},$ (19)

where (17) follows from the definition of inexactness of the LMO (Equation
(6)) and (18) from the fact that $-\rho{\mathbf{z}}_{t}$ has the largest inner
product with the positive gradient with respect to all the elements in
$\operatorname{conv}(\rho\mathcal{A})$. Note that by the symmetry of
$\mathcal{A}$ and by definition of $\rho$ both $-{\mathbf{x}}_{t}$ and
${\mathbf{x}}^{\star}$ are in $\operatorname{conv}(\rho\mathcal{A})$. Equation
(19) (known as weak duality) again follows from the convexity of $f$.

Now, subtracting $f({\mathbf{x}}^{\star})$ from both sides of (16), we get

$\displaystyle\varepsilon_{t+1}$
$\displaystyle\leq\varepsilon_{t}+\min_{\gamma\in[0,1]}\left\\{-\frac{\delta}{2}\gamma\varepsilon_{t}+\frac{\gamma^{2}}{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}}\right\\}$
$\displaystyle\leq\varepsilon_{t}-\frac{2}{\delta^{\prime}t+2}\delta^{\prime}\varepsilon_{t}+\frac{1}{2}\left(\frac{2}{\delta^{\prime}t+2}\right)^{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}},$

where we set $\delta^{\prime}:=\delta/2$ and used
$\gamma=\frac{2}{\delta^{\prime}t+2}\in[0,1]$ to obtain the second inequality.
Finally, we show by induction

$\varepsilon_{t}\leq\frac{4\left(\frac{2}{\delta}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{t+4}=2\frac{\left(\frac{1}{\delta^{\prime}}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{\delta^{\prime}t+2}$

for $t\geq 0$.

When $t=0$ we get
$\varepsilon_{0}\leq\left(\frac{1}{\delta^{\prime}}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)$.
Therefore, the base case holds. We now prove the induction step assuming
$\varepsilon_{t}\leq\tfrac{2\left(\frac{1}{\delta^{\prime}}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{\delta^{\prime}t+2}$
as :

$\displaystyle\varepsilon_{t+1}$
$\displaystyle\leq\left(1-\tfrac{2\delta^{\prime}}{\delta^{\prime}t+2}\right)\varepsilon_{t}+\tfrac{1}{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}}\left(\tfrac{2}{\delta^{\prime}t+2}\right)^{2}$
$\displaystyle\leq\left(1-\tfrac{2\delta^{\prime}}{\delta^{\prime}t+2}\right)\tfrac{2\left(\frac{1}{\delta^{\prime}}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{\delta^{\prime}t+2}$
$\displaystyle\quad+\tfrac{1}{2}\left(\tfrac{2}{\delta^{\prime}t+2}\right)^{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\tfrac{2}{(\delta^{\prime}t+2)^{2}}\delta^{\prime}\varepsilon_{0}$
$\displaystyle=\tfrac{2\left(\frac{1}{\delta^{\prime}}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{\delta^{\prime}t+2}\left(1-\tfrac{2\delta^{\prime}}{\delta^{\prime}t+2}+\tfrac{\delta^{\prime}}{\delta^{\prime}t+2}\right)$
$\displaystyle\leq\tfrac{2\left(\frac{1}{\delta^{\prime}}C_{f,\rho\mathcal{A}}^{\textsf{MP}}+\varepsilon_{0}\right)}{\delta^{\prime}(t+1)+2}.$

∎

We next explore the relationship of $C_{f,\rho\mathcal{A}}^{\textsf{MP}}$ and
the smoothness parameter. Recall that $f$ is _$L$ -smooth_ w.r.t. a given norm
$\|.\|$ over a set $\mathcal{Q}$ if

$\|\nabla f({\mathbf{x}})-\nabla f({\mathbf{y}})\|_{*}\leq
L\|{\mathbf{x}}-{\mathbf{y}}\|\text{ for all
}{\mathbf{x}},{\mathbf{y}}\in\mathcal{Q}\ ,$ (20)

where $\|.\|_{*}$ is the dual norm of $\|.\|$.

######  Lemma 15.

Assume $f$ is $L$-smooth w.r.t. a given norm $\|.\|$, over the set
$\operatorname{conv}(\mathcal{A})$ with $\operatorname{mDW(\mathcal{A})}>0$.
Then,

$C_{f,\mathcal{A}}^{\textsf{MP}}\leq
L\,\operatorname{\mathrm{radius}}_{{\left\lVert.\right\rVert}}(\mathcal{A})^{2}$
(21)

###### Proof.

By the definition of smoothness of $f$ w.r.t. $\|.\|$,

$\displaystyle
D({\mathbf{y}},{\mathbf{x}})\leq\frac{L}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}.$

Hence, from the definition of $C_{f,\mathcal{A}}^{\textsf{MP}}$,

$\displaystyle C_{f,\mathcal{A}}^{\textsf{MP}}$ $\displaystyle\leq$
$\displaystyle\sup_{\begin{subarray}{c}{\mathbf{s}}\in\mathcal{A},\,{\mathbf{x}}\in\operatorname{conv}{(\mathcal{A})}\\\
\gamma\in[0,1]\\\
{\mathbf{y}}={\mathbf{x}}+\gamma{\mathbf{s}}\end{subarray}}\frac{2}{\gamma^{2}}\frac{L}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$
$\displaystyle=$ $\displaystyle
L\sup_{{\mathbf{s}}\in\operatorname{conv}{(\mathcal{A})}}\,\|{\mathbf{s}}\|^{2}$
$\displaystyle=$ $\displaystyle
L\,\operatorname{\mathrm{radius}}_{{\left\lVert.\right\rVert}}(\mathcal{A})^{2}\
.$

∎

As an immediate corollary of the above lemma, we have that
$C_{f,\rho\mathcal{A}}^{\textsf{MP}}\leq
L\,\rho^{2}\operatorname{\mathrm{radius}}_{{\left\lVert.\right\rVert}}(\mathcal{A})^{2}$
for any scaled set $\rho\mathcal{A}$ and any norm, if $f$ is $L$-smooth w.r.t.
that norm.

Related to our above complexity quantities $C_{f,\mathcal{A}}$ given in (8)
and $C_{f,\mathcal{A}}^{\textsf{MP}}$ given in (10), Lacoste-Julien & Jaggi
(2015) have defined a slight variation called
$C_{f,\mathcal{A}}^{\textsf{AW}}$, in order to bound the convergence rates for
the Away-Step and Pairwise FW methods. $C_{f,\mathcal{A}}^{\textsf{AW}}$ is
defined as

$C_{f,\mathcal{A}}^{\textsf{AW}}:=\sup_{\begin{subarray}{c}{\mathbf{s}},{\mathbf{v}}\in\mathcal{A},\,{\mathbf{x}}\in\operatorname{conv}(\mathcal{A})\\\
\gamma\in[0,1]\\\
{\mathbf{y}}={\mathbf{x}}+\gamma({\mathbf{s}}-{\mathbf{v}})\end{subarray}}\frac{2}{\gamma^{2}}D({\mathbf{y}},{\mathbf{x}}).$
(22)

Our $C_{f,\mathcal{A}}^{\textsf{MP}}$ can be considered as a variant of
$C_{f,\mathcal{A}}^{\textsf{AW}}$ with the away atom ${\mathbf{v}}$ fixed to
be $0$. Thus, $C_{f,\mathcal{A}}^{\textsf{MP}}\leq
C_{f,\mathcal{A}}^{\textsf{AW}}$.

#### Norm-based Variants.

Note that for any choice of norm $\|.\|$, the analogous sublinear convergence
rates do hold if the objective function is L-smooth (i.e., $\nabla f$ is
$L$-Lipschitz) with respect to the norm $\|.\|$.

######  Theorem’ 2.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded and symmetric set, and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be $L$-smooth w.r.t. a given
norm $\|.\|$, over $\rho\operatorname{conv}(\mathcal{A})$, with $\rho<\infty$.
Then, Norm-Corrective Matching Pursuit (Algorithm 4), converges for $t\geq 0$
as

$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})\leq\frac{2\left(\frac{2}{\delta}L\rho^{2}\operatorname{\mathrm{radius}}_{\|.\|\\!}(\mathcal{A})^{2}+\varepsilon_{0}\right)}{\frac{\delta}{2}t+2}$

where $\varepsilon_{0}:=f({\mathbf{x}}_{0})-f({\mathbf{x}}^{\star})$ is the
initial error in objective, and $\delta\in(0,1]$ is the relative accuracy of
the employed approximate LMO (6).

###### Proof.

The proof follows directly from the fact that
$C_{f,\rho\mathcal{A}}^{\textsf{MP}}\leq
L\,\rho^{2}\operatorname{\mathrm{radius}}_{{\left\lVert.\right\rVert}}(\mathcal{A})^{2}$
for any scaled set $\rho\mathcal{A}$, under smoothness of $f$, as shown in
Lemma 15. ∎

###  B.3 Linear MP rates

######  Theorem’ 13.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set.

Then, Algorithm 6 converges linearly as

$\varepsilon_{t+1}\leq\bigg{(}1-\delta^{2}\frac{\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}}{C_{f,\rho\mathcal{A}}^{\textsf{MP}}}\bigg{)}\varepsilon_{t}$

where $\varepsilon_{t}:=f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ is the
suboptimality at step $t$, and $\delta\in(0,1]$ is the relative accuracy
parameter of the employed approximate LMO (Equation (6)).

###### Proof.

Using the definition of $C_{f,\rho\mathcal{A}}^{\textsf{MP}}$ we upper-bound
$f$ on $\rho\operatorname{conv}(\mathcal{A})$ as follows

$\displaystyle f({\mathbf{x}}_{t+1})$ $\displaystyle\leq$
$\displaystyle\min_{\gamma\in[0,1]}f({\mathbf{x}}_{t})+\gamma\langle\nabla
f({\mathbf{x}}_{t}),\rho\tilde{{\mathbf{z}}}_{t}\rangle+\frac{\gamma^{2}}{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}}$
$\displaystyle=$
$\displaystyle\min_{\gamma\in{\mathbb{R}}}f({\mathbf{x}}_{t})+\gamma\langle\nabla
f({\mathbf{x}}_{t}),\rho\tilde{{\mathbf{z}}}_{t}\rangle+\frac{\gamma^{2}}{2}C_{f,\rho\mathcal{A}}^{\textsf{MP}}$
$\displaystyle=$ $\displaystyle
f({\mathbf{x}}_{t})-\frac{\rho^{2}}{2C_{f,\rho\mathcal{A}}^{\textsf{MP}}}\left\langle\nabla
f({\mathbf{x}}_{t}),\tilde{{\mathbf{z}}}_{t}\right\rangle^{2}.$

This upper bound holds for Algorithm 6 as $\gamma$ minimizing the RHS of the
first equality coincides with the update of Algorithm 6 Line 5. The first
equality holds as $C_{f,\rho\mathcal{A}}^{\textsf{MP}}$ is defined on
$\rho\operatorname{conv}(\mathcal{A})$ and
$\rho\operatorname{conv}(\mathcal{A})$ contains all iterates by definition, so
that the unconstrained minimum lies in $[0,1]$.

Using $\varepsilon_{t}=f({\mathbf{x}}^{\star})-f({\mathbf{x}}_{t})$, we can
lower bound the error decay as

$\displaystyle\varepsilon_{t}-\varepsilon_{t+1}\geq\frac{\rho^{2}}{2C_{f,\rho\mathcal{A}}^{\textsf{MP}}}\left\langle\nabla
f({\mathbf{x}}_{t}),\tilde{{\mathbf{z}}}_{t}\right\rangle^{2}.$ (23)

Starting from the definition of $\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}$ in
(12), we get,

$\displaystyle\frac{\gamma({\mathbf{x}}_{t},{\mathbf{x}}^{\star})^{2}}{2}\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}$
$\displaystyle\leq$ $\displaystyle
f({\mathbf{x}}^{\star})-f({\mathbf{x}}_{t})-\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}^{\star}-{\mathbf{x}}_{t})\rangle$
$\displaystyle=$
$\displaystyle-\varepsilon_{t}+\gamma({\mathbf{x}}_{t},{\mathbf{x}}^{\star})\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{s}}({\mathbf{x}}_{t})\rangle,$

which gives

$\displaystyle\varepsilon_{t}$ $\displaystyle\leq$
$\displaystyle-\frac{\gamma({\mathbf{x}}_{t},{\mathbf{x}}^{\star})^{2}}{2}\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}+\gamma({\mathbf{x}}_{t},{\mathbf{x}}^{\star})\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{s}}({\mathbf{x}}_{t})\rangle$ (24)
$\displaystyle\leq$ $\displaystyle\frac{\langle-\nabla
f({\mathbf{x}}_{t}),{\mathbf{s}}({\mathbf{x}}_{t})\rangle^{2}}{2\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}}$
$\displaystyle=$ $\displaystyle\frac{\langle-\nabla
f({\mathbf{x}}_{t}),\rho\tilde{{\mathbf{z}}}_{t}\rangle^{2}}{2\delta^{2}\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}}$

where the last inequality is by the quality of the approximate LMO as used in
the algorithm, as defined in (6).

Combining equations (23) and (24), we have

$\displaystyle\varepsilon_{t}-\varepsilon_{t+1}\geq\delta^{2}\frac{\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}}{C_{f,\rho\mathcal{A}}^{\textsf{MP}}}\,\varepsilon_{t},$

which proves the claimed result. ∎

Similar to the relationship between $C_{f}$ and smoothness, we explore the
relationship of $\mu_{f,\mathcal{A}}^{\textsf{MP}}$ with strong convexity.
Lemma 16 is analogous to a similar result explored for the Frank-Wolfe case by
Lacoste-Julien & Jaggi (2015) relating an analogous quantity to the more
complex notion of pyramidal width.

######  Lemma 16.

If $f$ is $\mu$-strongly convex over the domain
$\rho\operatorname{conv}(\mathcal{A})$ with respect to some arbitrary chosen
norm ${\left\lVert.\right\rVert}$ and $\operatorname{mDW(\mathcal{A})}>0$,
then

$\mu_{f,\mathcal{A}}^{\textsf{MP}}\geq\mu\operatorname{mDW(\mathcal{A})}^{2}$
(25)

###### Proof.

By the definition of strong convexity, for any
${\mathbf{x}}\in\rho\operatorname{conv}(\mathcal{A})$,

$D({\mathbf{x}}^{\star},{\mathbf{x}})\geq\mu\|{\mathbf{x}}^{\star}-{\mathbf{x}}\|^{2}.$

Hence,

$\displaystyle\mu_{f,\mathcal{A}}^{\textsf{MP}}$ $\displaystyle\geq$
$\displaystyle\frac{\mu}{\gamma({\mathbf{x}},{\mathbf{x}}^{\star})^{2}}\|{\mathbf{x}}^{\star}-{\mathbf{x}}\|$
$\displaystyle=$ $\displaystyle\mu\frac{\langle-\nabla
f({\mathbf{x}}),{\mathbf{s}}({\mathbf{x}})\rangle}{\langle-\nabla
f({\mathbf{x}}),\frac{{\mathbf{x}}^{\star}-{\mathbf{x}}}{\|{\mathbf{x}}^{\star}-{\mathbf{x}}\|}\rangle}^{2}$

We now split $-\nabla
f({\mathbf{x}})={\mathbf{d}}_{\parallel}+{\mathbf{d}}_{\perp}$, so that
${\mathbf{d}}_{\parallel}\in\operatorname{lin}(\mathcal{A})$ while
${\mathbf{d}}_{\perp}$ lies in the orthogonal complement of
$\operatorname{lin}(\mathcal{A})$. Since
${\mathbf{s}}({\mathbf{x}}),{\mathbf{x}}^{\star},{\mathbf{x}}$ all lie in
$\rho\operatorname{conv}(\mathcal{A})\subseteq\operatorname{lin}(\mathcal{A})$,
we get

$\displaystyle\mu_{f,\mathcal{A}}^{\textsf{MP}}$ $\displaystyle\geq$
$\displaystyle\mu\frac{\langle{\mathbf{d}}_{\parallel},{\mathbf{s}}({\mathbf{x}})\rangle}{\langle{\mathbf{d}}_{\parallel},\frac{{\mathbf{x}}^{\star}-{\mathbf{x}}}{\|{\mathbf{x}}^{\star}-{\mathbf{x}}\|}\rangle}^{2}$
$\displaystyle\geq$
$\displaystyle\mu\frac{\langle{\mathbf{d}}_{\parallel},{\mathbf{s}}({\mathbf{x}})\rangle^{2}}{\|{\mathbf{d}}_{\parallel}\|^{2}}$
$\displaystyle=$
$\displaystyle\mu\Big{\langle}\frac{{\mathbf{d}}_{\parallel}}{\|{\mathbf{d}}_{\parallel}\|},{\mathbf{s}}({\mathbf{x}})\Big{\rangle}^{2}$
$\displaystyle\geq$ $\displaystyle\mu\operatorname{mDW(\mathcal{A})}^{2},$

where the last inequality holds since $\operatorname{mDW(\mathcal{A})}>0$.
Indeed, it holds that:

$\displaystyle\langle\frac{{\mathbf{d}}_{\parallel}}{\|{\mathbf{d}}_{\parallel}\|},{\mathbf{s}}({\mathbf{x}})\rangle=\max_{{\mathbf{z}}\in\mathcal{A}}\langle\frac{-{\mathbf{d}}_{\parallel}}{\|{\mathbf{d}}_{\parallel}\|},{\mathbf{z}}\rangle\geq\operatorname{mDW(\mathcal{A})}$
(26)

which can be squared provided that
$\langle\frac{{\mathbf{d}}_{\parallel}}{\|{\mathbf{d}}_{\parallel}\|},{\mathbf{s}}({\mathbf{x}})\rangle$
and $\operatorname{mDW(\mathcal{A})}$ are both positive which is the case if
$\operatorname{mDW(\mathcal{A})}>0$. ∎

#### Norm-based Variants

######  Theorem’ 7.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set such that
$\operatorname{mDW(\mathcal{A})}>0$. and let the objective function
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be both $L$-smooth and
$\mu$-strongly convex over $\rho\operatorname{conv}(\mathcal{A})$.

Then, Matching Pursuit and Norm-Corrective Matching Pursuit (Algorithm 4)
converge linearly as

$\varepsilon_{t+1}\leq\bigg{(}1-\delta^{2}\frac{\mu\operatorname{mDW(\mathcal{A})}^{2}}{L\operatorname{\mathrm{radius}}(\mathcal{A})^{2}}\bigg{)}\varepsilon_{t}$

where $\varepsilon_{t}:=f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ is the
suboptimality at step $t$, and $\delta\in(0,1]$ is the relative accuracy
parameter of the employed approximate LMO (Equation (6)).

###### Proof.

From Lemma 15, $C_{f,\rho\mathcal{A}}^{\textsf{MP}}\leq
L\rho^{2}\operatorname{\mathrm{radius}}_{{\left\lVert.\right\rVert}}(\mathcal{A})^{2}$,
while from Lemma 16,
$\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}\geq\mu\rho^{2}\operatorname{mDW(\mathcal{A})}^{2}$.
Combining,

$\displaystyle\frac{\mu_{f,\rho\mathcal{A}}^{\textsf{MP}}}{C_{f,\rho\mathcal{A}}^{\textsf{MP}}}\geq\frac{\mu\operatorname{mDW(\mathcal{A})}^{2}}{L\operatorname{\mathrm{radius}}(\mathcal{A})^{2}}$

The result now follows from Theorem 13. ∎

###  B.4 Proof of Corollary 4

We have

$\|{\mathbf{x}}_{t}\|_{\mathcal{A}}\leq\frac{\|{\mathbf{x}}_{t}\|}{\operatorname{\mathrm{inr}}(\operatorname{conv}(\mathcal{A}))},$
(27)

for all $t=1\dots T$, and hence
$\rho\leq\frac{\tilde{\rho}}{\operatorname{\mathrm{inr}}(\operatorname{conv}(\mathcal{A}))}$,
which yields the first upper bound on
$f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ in Corollary 4. Here, (27)
essentially follows from the definition of the atomic norm. A formal proof can
be obtained by writing the atomic norm as the value of an $\ell_{1}$-norm
minimization problem Chandrasekaran et al. (2012) and using arguments from the
proof of Theorem 2.5 in Soltanolkotabi & Candès (2012).

To get upper bound on $f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ for
$f({\mathbf{x}})=\frac{1}{2}d^{2}({\mathbf{x}},{\mathbf{y}})$, note that for
this particular choice of $f$, ${\mathbf{x}}_{t}-{\mathbf{b}}={\mathbf{y}}$
and the update step in Algorithm 4 can be written as
${\mathbf{x}}_{t+1}=\mathcal{P}_{t}{\mathbf{y}}$, where $\mathcal{P}_{t}$ is
the orthogonal projection operator onto $\mathcal{S}$ in iteration $t$. Hence,
we have $\|{\mathbf{x}}_{t}\|\leq\|{\mathbf{y}}\|$, for all $t\in[T]$, as a
consequence of $\|\mathcal{P}_{t}\|_{\mathrm{op}}=1$.

###  B.5 Lower Bound

######  Theorem’ 8.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set and let the objective
function $f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be both $L$-smooth
and $\mu$-strongly convex. Assume,
${\mathbf{x}}^{\star}:=\operatorname*{arg\,min}_{{\mathbf{x}}\in\operatorname{lin}(\mathcal{A})}f({\mathbf{x}})=\operatorname*{arg\,min}_{{\mathbf{x}}\in\mathcal{H}}f({\mathbf{x}})$.
Let $\varepsilon_{t}:=f({\mathbf{x}}_{t})-f({\mathbf{x}}^{\star})$ be the
suboptimality of the iterates and ${\mathbf{z}}_{t}$ the atom selected at
iteration $t$ by the LMO. Then, for $t\geq 0$ the suboptimality of the
iterates of Matching Pursuit (Algorithm 4 variant 0) with an exact LMO does
not decay faster than:

$\varepsilon_{t+1}\geq\left(1-\frac{W_{\mathcal{A}}(-\nabla
f({\mathbf{x}}_{t}))^{2}}{\|{\mathbf{z}}_{t}\|^{2}}\frac{2L-\mu}{\mu}\right)\varepsilon_{t}$

###### Proof.

First of all we note how the least-squares function is both $L$-smooth and
$\mu$-strongly convex with $L=\mu$. Recall that the new iterate
${\mathbf{x}}_{t+1}$ is obtained as
${\mathbf{x}}_{t+1}={\mathbf{x}}_{t}+\gamma{\mathbf{z}}_{t}$ where
$\gamma=-\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle}{L\|{\mathbf{z}}_{t}\|^{2}}$. By
strong convexity we get:

$\displaystyle f({\mathbf{x}}_{t+1})$ $\displaystyle\geq
f({\mathbf{x}}_{t})-\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle^{2}}{L\|{\mathbf{z}}_{t}\|^{2}}+$
$\displaystyle+\frac{\mu}{2}\left(\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle}{L\|{\mathbf{z}}_{t}\|^{2}}\right)^{2}\|{\mathbf{z}}_{t}\|^{2}$

and subtracting $f({\mathbf{x}}^{\star})$ on both sides yields:

$\displaystyle\varepsilon_{t+1}$
$\displaystyle\geq\varepsilon_{t}-\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle^{2}}{L\|{\mathbf{z}}_{t}\|^{2}}+\frac{\mu}{2}\left(\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle}{L\|{\mathbf{z}}_{t}\|^{2}}\right)^{2}\|{\mathbf{z}}_{t}\|^{2}$
$\displaystyle\geq\varepsilon_{t}-\frac{1}{L}\Big{\langle}\nabla
f({\mathbf{x}}_{t}),\frac{{\mathbf{z}}_{t}}{\|{\mathbf{z}}_{t}\|}\Big{\rangle}^{2}\left(1-\frac{\mu}{2L}\right).$
(28)

By smoothness we obtain:

$\displaystyle\
f({\mathbf{x}}_{t}+\gamma({\mathbf{x}}^{\star}-{\mathbf{x}}_{t}))$
$\displaystyle\leq$ $\displaystyle\ f({\mathbf{x}}_{t})+\gamma\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\rangle+\gamma^{2}\frac{L}{2}\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|^{2}.$

Now we can further lower bound the LHS by $f({\mathbf{x}}^{\star})$ and
minimize the RHS by $\gamma=-\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\rangle}{L\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|^{2}}$.
Therefore:

$\displaystyle f({\mathbf{x}}^{\star})\leq$ (29) $\displaystyle\textstyle
f({\mathbf{x}}_{t})-\frac{1}{L}\langle\nabla
f({\mathbf{x}}_{t}),\frac{{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}}{\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|}\rangle^{2}+\frac{1}{2L}\langle\nabla
f({\mathbf{x}}_{t}),\frac{{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}}{\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|}\rangle^{2}$

which by definition of $\varepsilon_{t}$ becomes:

$\displaystyle\textstyle\varepsilon_{t}\geq\frac{1}{2L}\langle\nabla
f({\mathbf{x}}_{t}),\frac{{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}}{\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|}\rangle^{2}$
$\displaystyle\textstyle=\frac{1}{2L}\|\nabla
f({\mathbf{x}}_{t})\|^{2}\langle\frac{\nabla f({\mathbf{x}}_{t})}{\|\nabla
f({\mathbf{x}}_{t})\|},\frac{{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}}{\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|}\rangle^{2}$
(30) $\displaystyle\textstyle\geq\frac{1}{2L}\|\nabla
f({\mathbf{x}}_{t})\|^{2}\frac{\mu}{L}.$

Recall the first-order optimality condition for constrained optimization. We
have that $\langle\nabla
f({\mathbf{x}}^{\star}),{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\rangle=0$. In
the last inequality of Equation (B.5) we used the following arguments along
with the first order optimality condition:

$\displaystyle-\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\rangle$
$\displaystyle\overset{\begin{subarray}{c}\text{str. conv}\\\ +\\\ \text{opt.
cond.}\end{subarray}}{\geq}{\mu\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|^{2}}$

multiplying and dividing by the norm of the gradient and rearranging we
obtain:

$\displaystyle-\left\langle\frac{\nabla f({\mathbf{x}}_{t})}{\|\nabla
f({\mathbf{x}}_{t})\|},\frac{{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}}{\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|}\right\rangle$
$\displaystyle\geq\mu\frac{\|{\mathbf{x}}^{\star}-{\mathbf{x}}_{t}\|}{\|\nabla
f({\mathbf{x}}_{t})\|}\overset{\begin{subarray}{c}\text{L-smooth}\\\ +\\\
\text{opt. cond.}\end{subarray}}{\geq}\frac{\mu}{L}$

By taking the square we obtain the inequality used in Equation (B.5).

Combining (B.5) with (B.5) (the latter being $1\leq
2L\tfrac{L}{\mu}\tfrac{1}{\|\nabla
f({\mathbf{x}}_{t})\|^{2}}\varepsilon_{t}$), we finally obtain:

$\displaystyle\varepsilon_{t+1}$
$\displaystyle\geq\varepsilon_{t}-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\frac{{\mathbf{z}}_{t}}{\|{\mathbf{z}}_{t}\|}\rangle^{2}}{\|\nabla
f({\mathbf{x}}_{t})\|^{2}}\frac{2L}{\mu}\left(1-\frac{\mu}{2L}\right)\varepsilon_{t}$
$\displaystyle=\varepsilon_{t}-\frac{W_{\mathcal{A}}(-\nabla
f({\mathbf{x}}_{t}))^{2}}{\|{\mathbf{z}}_{t}\|^{2}}\frac{2L}{\mu}\left(\frac{2L-\mu}{2L}\right)\varepsilon_{t}$
$\displaystyle=\varepsilon_{t}-\frac{W_{\mathcal{A}}(-\nabla
f({\mathbf{x}}_{t}))^{2}}{\|{\mathbf{z}}_{t}\|^{2}}\tfrac{1}{\mu}(2L-\mu)\varepsilon_{t}$

∎

###  B.6 Proof of Theorem 10

Let $\mathcal{A}\in{\mathbb{R}}^{d}$ be a symmetric set with
$\|{\mathbf{s}}\|_{2}=1$, for all ${\mathbf{s}}\in\mathcal{A}$, which spans
${\mathbb{R}}^{d}$. Let also $\mathcal{B}$ be a set such that
$\mathcal{A}=\mathcal{B}\cup-\mathcal{B}$ with
$\mathcal{B}\cap-\mathcal{B}=\emptyset$ and $|\mathcal{B}|=n$.

Our proofs rely on the Gram matrix ${\mathbf{G}}(\mathcal{J})$ of the atoms in
$\mathcal{B}$ indexed by $\mathcal{J}\subseteq[n]$, i.e.,
$({\mathbf{G}}(\mathcal{J}))_{i,j}:=\langle{\mathbf{s}}_{i},{\mathbf{s}}_{j}\rangle,i,j\in\mathcal{J}$.

To prove Theorem 10 , we use the following known results.

######  Lemma 17 (Tropp (2004)).

The smallest eigenvalue $\gamma_{\min}({\mathbf{G}}(\mathcal{J}))$ of
${\mathbf{G}}(\mathcal{J})$ obeys
$\gamma_{\min}({\mathbf{G}}(\mathcal{J}))>1-\mu(\mathcal{B},m-1)$, where
$m=|\mathcal{J}|$.

######  Lemma 18 (DeVore & Temlyakov (1996)).

For every index set $\mathcal{J}\subseteq[n]$ and every linear combination
${\mathbf{p}}$ of the atoms in $\mathcal{B}$ indexed by $\mathcal{J}$, i.e.,
${\mathbf{p}}:=\sum_{j\in\mathcal{J}}v_{j}{\mathbf{s}}_{j}$, we have
$\max_{j\in\mathcal{J}}|\langle{\mathbf{p}},{\mathbf{s}}_{j}\rangle|\geq\frac{\|{\mathbf{p}}\|^{2}}{\|{\mathbf{v}}\|_{1}}=\frac{\langle{\mathbf{v}},{\mathbf{G}}(\mathcal{J}){\mathbf{v}}\rangle_{2}}{\|{\mathbf{v}}\|_{1}}$,
where ${\mathbf{v}}\neq\textbf{0}$ is the vector having the $v_{j}$ as
entries.

######  Theorem’ 10.

Let $\mathcal{A}\subset{\mathbb{R}}^{d}$ be a symmetric set of $2n$ atoms with
$\|{\mathbf{s}}\|_{2}=1$ for all ${\mathbf{s}}\in\mathcal{A}$. Let also
$\mathcal{B}$ be a set such that $\mathcal{A}=\mathcal{B}\cup-\mathcal{B}$
with $\mathcal{B}\cap-\mathcal{B}=\emptyset$ and $|\mathcal{B}|=n$. Then, the
cumulative coherence of the set $\mathcal{B}$ is bounded by:
$\mu(\mathcal{B},n-1)\geq 1-n\cdot\operatorname{mDW(\mathcal{A})}^{2}$.

###### Proof.

For each direction ${\mathbf{d}}\in\operatorname{lin}(\mathcal{A})$ with
$\|{\mathbf{d}}\|=1$ it holds that:

$\displaystyle\max_{{\mathbf{z}}\in\mathcal{A}}|\langle{\mathbf{d}},{\mathbf{z}}\rangle|$
$\displaystyle\overset{\text{Lemma~{}\ref{thm:lowerbounddotprod}}}{\geq}{\frac{\|{\mathbf{d}}\|^{2}}{\|{\mathbf{v}}\|_{1}}}$
$\displaystyle=\frac{\sqrt{\langle{\mathbf{v}},{\mathbf{G}}(\mathcal{J}){\mathbf{v}}\rangle_{2}}\|{\mathbf{d}}\|}{\|{\mathbf{v}}\|_{1}}$
$\displaystyle\geq\frac{\sqrt{\langle{\mathbf{v}},{\mathbf{G}}(\mathcal{J}){\mathbf{v}}\rangle_{2}}}{\sqrt{n}\|{\mathbf{v}}\|_{2}}$
$\displaystyle\overset{\text{Lemma~{}\ref{thm:eigenval}}}{\geq}\sqrt{\frac{1-\mu(\mathcal{B},n-1)}{n}}$

This holds for every direction in $\operatorname{lin}(\mathcal{A})$, included
the one that minimizes
$\max_{{\mathbf{z}}\in\mathcal{A}}|\langle{\mathbf{d}},{\mathbf{z}}\rangle|$.
Therefore, we have:

$\displaystyle\operatorname{mDW(\mathcal{A})}^{2}\geq\frac{1-\mu(\mathcal{B},n-1)}{n}$

Rearranging we obtain:

$\displaystyle\mu(\mathcal{B},n-1)\geq
1-n\cdot\operatorname{mDW(\mathcal{A})}^{2}.$

∎

###  B.7 On the Relationship Between Matching Pursuit and Frank-Wolfe

######  Theorem’ 14.

Let $\mathcal{A}\subset\mathcal{H}$ be a bounded set and let
$f\colon\mathcal{H}{\,\rightarrow\,}{\mathbb{R}}$ be a $L$-smooth convex
function. Let $\alpha>0$ and let us fix an iteration $t>0$ and the iterate
computed at the previous iteration ${\mathbf{x}}_{t}$. If
$-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}\leq
1$ the new iterate
${\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}={\mathbf{x}}_{t}+\gamma(\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t})\big{|}_{\gamma\in[0,1]}$
of Frank-Wolfe (Algorithm 2) using the set
$\alpha\mathcal{A}=\left\\{{\mathbf{x}}:\exists{\mathbf{z}}\in\mathcal{A}\
s.t.\ {\mathbf{x}}=\alpha{\mathbf{z}}\right\\}$ converges to the new iterate
${\mathbf{x}}_{t+1}^{\textsf{MP}}={\mathbf{x}}_{t}+\gamma{\mathbf{z}}_{t}\big{|}_{\gamma\in{\mathbb{R}}}$
of Matching Pursuit (Algorithm 4 variant 0) applied on the linear span of the
set $\mathcal{A}$ with rate:

$\|{\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}-{\mathbf{x}}_{t+1}^{\textsf{MP}}\|\in
O\left(\frac{1}{\alpha}\right)$

In particular when $\alpha$ grows to infinity the condition
$-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}\leq
1$ always holds (for all steps $t$). If the condition $-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}\leq
1$ is not satisfied at step $t$ then the difference of the iterates increases
linearly:

$\|{\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}-{\mathbf{x}}_{t+1}^{\textsf{MP}}\|\in
O\left({\alpha}\right)$

###### Proof.

In both the algorithms the new iterate is obtained by minimizing the quadratic
approximation of $f$ computed at ${\mathbf{x}}_{t}$. Let
$g_{{\mathbf{x}}_{t}}({\mathbf{x}})$ be the quadratic approximation of $f$ at
${\mathbf{x}}_{t}$ given by

$g_{{\mathbf{x}}_{t}}({\mathbf{x}})=f({\mathbf{x}}_{t})+\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{x}}-{\mathbf{x}}_{t}\rangle+\frac{L}{2}\|{\mathbf{x}}-{\mathbf{x}}_{t}\|^{2}.$

At iteration $t>0$ the new iterate ${\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}$
of Frank-Wolfe (Algorithm 2) on the set
$\operatorname{conv}(\alpha\mathcal{A})$ is computed as
${\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}={\mathbf{x}}_{t}+\gamma(\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t})$,
where:

$\displaystyle\gamma$
$\displaystyle=\operatorname*{arg\,min}_{\gamma\in[0,1]}g_{{\mathbf{x}}_{t}}({\mathbf{x}}_{t}+\gamma(\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}))$
$\displaystyle=f({\mathbf{x}}_{t})+$
$\displaystyle\quad\min_{\gamma\in[0,1]}\left\\{+\gamma\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle+\frac{L\gamma^{2}}{2}\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}\right\\}$

which solved for $\gamma$ yields:

${\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}=\begin{cases}\mbox{if
}-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}\leq
1:\\\ \quad{\mathbf{x}}_{t}-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}(\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t})\\\
\mbox{otherwise:}\\\ \quad\alpha{\mathbf{z}}_{t}\end{cases}$ (31)

On the other hand, the new iterate ${\mathbf{x}}_{t+1}^{\textsf{MP}}$ of
Matching Pursuit (Algorithm 4 variant 0) on the set $\mathcal{A}$ is computed
as ${\mathbf{x}}_{t+1}^{\textsf{MP}}={\mathbf{x}}_{t}+\gamma{\mathbf{z}}_{t}$
where:

$\displaystyle\gamma$
$\displaystyle=\operatorname*{arg\,min}_{\gamma\in{\mathbb{R}}}g_{{\mathbf{x}}_{t}}({\mathbf{x}}_{t}+\gamma{\mathbf{z}}_{t})$
$\displaystyle=f({\mathbf{x}}_{t})+\min_{\gamma\in{\mathbb{R}}}\left\\{+\gamma\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle+\frac{L\gamma^{2}}{2}\|{\mathbf{z}}_{t}\|^{2}\right\\}$

which solved for $\gamma$ yields:

${\mathbf{x}}_{t+1}^{\textsf{MP}}={\mathbf{x}}_{t}-\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle}{L\|{\mathbf{z}}_{t}\|^{2}}{\mathbf{z}}_{t}$
(32)

Now:

$\displaystyle\|{\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}-{\mathbf{x}}_{t+1}^{\textsf{MP}}\|=$
$\displaystyle\quad\begin{cases}\mbox{if }-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}\leq
1:\\\ \quad\|\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle}{L\|{\mathbf{z}}_{t}\|^{2}}{\mathbf{z}}_{t}-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}(\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t})\|\\\
\mbox{otherwise:}\\\ \quad\|\alpha{\mathbf{z}}_{t}+\frac{\langle\nabla
f({\mathbf{x}}_{t}),{\mathbf{z}}_{t}\rangle}{L\|{\mathbf{z}}_{t}\|^{2}}{\mathbf{z}}_{t}\|\end{cases}$

Using the fact that
$\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}=\langle\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t},\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle$
it is easy to show that the distance depends on $1/\alpha$ when
$-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}\leq
1$ while is linear in $\alpha$ in the other case. Furthermore, when $\alpha$
grows $-\frac{\langle\nabla
f({\mathbf{x}}_{t}),\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\rangle}{L\|\alpha{\mathbf{z}}_{t}-{\mathbf{x}}_{t}\|^{2}}\leq
1$ always holds. Therefore:

$\lim_{\alpha\rightarrow\infty}\|{\mathbf{x}}_{t+1}^{\textsf{FW}_{\alpha}}-{\mathbf{x}}_{t+1}^{\textsf{MP}}\|=0$
(33)

Therefore, the Frank-Wolfe step converges to the Matching-Pursuit step when
$\alpha$ (i.e., the diameter of the set) grows to infinity. ∎

###  B.8 Proof of Corollary 9

Let us discuss the following example. Let
$\Delta=\left\\{{\mathbf{e}}_{1},\ldots,{\mathbf{e}}_{d}\right\\}$ be the
natural basis of ${\mathbb{R}}^{d}$ and assume we are minimizing
$f({\mathbf{x}})=\frac{1}{2}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}$ over the set
$\operatorname{lin}(\mathcal{A})=\operatorname{lin}(\Delta\cup-\Delta)=\operatorname{lin}\left(\left\\{{\mathbf{e}}_{1},-{\mathbf{e}}_{1},\ldots,{\mathbf{e}}_{d},-{\mathbf{e}}_{d}\right\\}\right)$
(i.e., symmetrized $\Delta$) starting from ${\mathbf{x}}_{0}=\textbf{0}$. We
further assume that each component of the target vector ${\mathbf{y}}$ is
equal to 1. This satisfies the assumptions of Theorem 8. To estimate the lower
bound constant we note that if $\mu=L$ then
$\frac{L}{\mu}\frac{2L-\mu}{\mu}=1$. We now have to bound
$\frac{W_{\mathcal{A}}(-\nabla
f({\mathbf{x}}_{t}))^{2}}{\|{\mathbf{z}}_{t}\|^{2}}$. At iteration $t<d$ we
know that $\nabla f({\mathbf{x}}_{t})=-({\mathbf{y}}-{\mathbf{x}}_{t})$. By
the specific assumptions we made on the set $\mathcal{A}$ and since
${\mathbf{y}}$ has a 1 in each component, ${\mathbf{x}}_{t}$ has exactly $t$
values which are equal to $1$ and $d-t$ zeros. Note that the minimization over
the span of the symmetrized natural basis ensures that Matching Pursuit and
Norm-Corrective Matching Pursuit coincide by Gram-Schmidt. Indeed, this case
is equivalent to computing the representation of the vector ${\mathbf{y}}$ in
the natural basis, one component at the time. Each step affects only one of
the components of the residual and keeps the rest untouched, which is to say
that if they were zero at iteration $t-1$ they are zero also at iteration $t$.
Therefore, the other $d-t$ non zero components have the same value they had at
the first iteration, which is to say they are all equal to $-1$. Then, we have

$\frac{W_{\mathcal{A}}(-\nabla
f({\mathbf{x}}_{t}))^{2}}{\|{\mathbf{z}}_{t}\|^{2}}=\frac{1}{d-t}.$ (34)

The lower bound becomes:

$\displaystyle\varepsilon_{t+1}\geq\left(1-\frac{1}{d-t}\right)\varepsilon_{t}.$

Let us now consider the upper bound. Using the same argument of Equation (34)
we have that the exponential decay is:

$\displaystyle\varepsilon_{t+1}\leq\left(1-\frac{1}{d-t}\right)\varepsilon_{t}.$

Therefore, the exponential decay is tight in this example. In Theorem 7 we
further bound the decay so that it depends only on the geometry of the atoms
set. In this example we have
$\operatorname{mDW(\mathcal{A})}^{2}=\frac{1}{d}$. Hence, we have:

$\displaystyle\varepsilon_{t+1}\leq\left(1-\frac{1}{d-t}\right)\varepsilon_{t}\leq\left(1-\frac{1}{d}\right)\varepsilon_{t}.$

Therefore, the ratio
$\frac{\operatorname{mDW(\mathcal{A})}}{\operatorname{\mathrm{radius}}(\mathcal{A})}$
in the linear convergence rate (Theorem 7) makes it loose in this example. On
the other hand, it does not depend on the particular iterate and yields the
global linear convergence rate. Note that the
$\operatorname{mDW(\mathcal{A})}$ is a geometric quantity and does not depend
on either ${\mathbf{x}}_{0}$ or ${\mathbf{y}}$. On the other hand, in the case
of the symmetrized natural basis we can give an explicit value for
$W_{\mathcal{A}}(-\nabla f({\mathbf{x}}_{t}))$ at every iteration.

After this discussion, the proof of Corollary 4 is trivial considering that at
iteration $t$ the gradient changed from the first iteration only in the
indexes in $\mathcal{I}$ (they became zero).