On the Global Linear Convergence of Frank-Wolfe Optimization Variants

Contributions.

We clarify several variants of the Frank-Wolfe algorithm and show that they all converge linearly for any strongly convex function optimized over a polytope domain, with a constant bounded away from zero that only depends on the geometry of the polytope. Our analysis does not depend on the location of the true optimum with respect to the domain, which was a disadvantage of earlier existing results such as , and the newer work of , as well as the line of work of which rely on Robinson’s condition . Our analysis yields a weaker sufficient condition than Robinson’s condition; in particular we can have linear convergence even in some cases when the function has more than one global minima, and is not globally strongly convex. The constant also naturally separates as the product of the condition number of the function with a novel notion of condition number of a polytope, which might have applications in complexity theory.

Related Work.

For the classical Frank-Wolfe algorithm, showed a linear rate for the special case of quadratic objectives when the optimum is in the strict interior of the domain, a result already subsumed by the more general . The early work of showed linear convergence for strongly convex constraint sets, under the strong requirement that the gradient norm is not too small (see for a discussion). The away-steps variant of the Frank-Wolfe algorithm, that can also remove weight from ‘bad’ atoms in the current active set, was proposed in , and later also analyzed in . The precise method is stated below in Algorithm 1. showed a (local) linear convergence rate on polytopes, but the constant unfortunately depends on the distance between the solution and its relative boundary, a quantity that can be arbitrarily small. More recently, have obtained linear convergence results in the case that the optimum solution satisfies Robinson’s condition . In a different recent line of work, have studied a variation of FW that repeatedly moves mass from the worst vertices to the standard FW vertex until a specific condition is satisfied, yielding a linear rate on strongly convex functions. Their algorithm requires the knowledge of several constants though, and moreover is not adaptive to the best-case scenario, unlike the Frank-Wolfe algorithm with away steps and line-search. None of these previous works was shown to be affine invariant, and most require additional knowledge about problem specific parameters.

Setup.

We consider general constrained convex optimization problems of the form:

Examples.

Optimization problems of the form (1) appear widely in machine learning and signal processing applications. The set of atoms $\mathcal{A}$ can represent combinatorial objects of arbitrary type. Efficient linear minimization oracles often exist in the form of dynamic programs or other combinatorial optimization approaches. As an example from tracking in computer vision, $\mathcal{A}$ could be the set of integer flows on a graph , where $\operatorname*{LMO_{\!\mathcal{A}}}$ can be efficiently implemented by a minimum cost network flow algorithm. In this case, $\mathcal{M}$ can also be described with a polynomial number of linear inequalities. But in other examples, $\mathcal{M}$ might not have a polynomial description in terms of linear inequalities, and testing membership in $\mathcal{M}$ might be much more expensive than running the linear oracle. This is the case when optimizing over the base polytope, an object appearing in submodular function optimization . There, the $\operatorname*{LMO_{\!\mathcal{A}}}$ oracle is a simple greedy algorithm. Another example is when $\mathcal{A}$ represents the possible consistent value assignments on cliques of a Markov random field (MRF); $\mathcal{M}$ is the marginal polytope , where testing membership is NP-hard in general, though efficient linear oracles exist for some special cases . Optimization over the marginal polytope appears for example in structured SVM learning and variational inference .

The Original Frank-Wolfe Algorithm.

The Frank-Wolfe (FW) optimization algorithm , also known as conditional gradient , is particularly suited for the setup (1) where $\mathcal{M}$ is only accessed through the linear minimization oracle. It works as follows: At a current iterate $\bm{x}^{(t)}$, the algorithm finds a feasible search atom $\bm{s}_{t}$ to move towards by minimizing the linearization of the objective function $f$ over $\mathcal{M}$ (line 3 in Algorithm 1) – this is where the linear minimization oracle $\operatorname*{LMO_{\!\mathcal{A}}}$ is used. The next iterate $\bm{x}^{(t+1)}$ is then obtained by doing a line-search on $f$ between $\bm{x}^{(t)}$ and $\bm{s}_{t}$ (line 11 in Algorithm 1). One reason for the recent increased popularity of Frank-Wolfe-type algorithms is the sparsity of their iterates: in iteration $t$ of the algorithm, the iterate can be represented as a sparse convex combination of at most $t+1$ atoms $\mathcal{S}^{(t)}\subseteq\mathcal{A}$ of the domain $\mathcal{M}$, which we write as $\bm{x}^{(t)}=\sum_{\bm{v}\in\mathcal{S}^{(t)}}\alpha^{(t)}_{\bm{v}}\bm{v}\vspace{-0.3mm}$. We write $\mathcal{S}^{(t)}$ for the active set, containing the previously discovered search atoms $\bm{s}_{r}$ for $r<t$ that have non-zero weight $\alpha^{(t)}_{\bm{s}_{r}}>0$ in the expansion (potentially also including the starting point $\bm{x}^{(0)}$). While tracking the active set $\mathcal{S}^{(t)}$ is not necessary for the original FW algorithm, the improved variants of FW that we discuss will require that $\mathcal{S}^{(t)}$ is maintained.

Zig-Zagging Phenomenon.

When the optimal solution lies at the boundary of $\mathcal{M}$, the convergence rate of the iterates is slow, i.e. sublinear: f(\bm{x}^{(t)})-f(\bm{x}^{*})\leq O\big{(}1/t\big{)}, for $\bm{x}^{*}$ being an optimal solution . This is because the iterates of the classical FW algorithm start to zig-zag between the vertices defining the face containing the solution $\bm{x}^{*}$ (see left of Figure 1). In fact, the $1/t$ rate is tight for a large class of functions: Canon and Cullum , Wolfe showed (roughly) that f(\bm{x}^{(t)})-f(\bm{x}^{*})\geq\Omega\big{(}1/t^{1+\delta}\big{)} for any $\delta>0$ when $\bm{x}^{*}$ lies on a face of $\mathcal{M}$ with some additional regularity assumptions. Note that this lower bound is different than the \Omega\big{(}1/t\big{)} one presented in [16, Lemma 3] which holds for all one-atom-per-step algorithms but assumes high dimensionality $d\geq t$.

Improved Variants of the Frank-Wolfe Algorithm

To address the zig-zagging problem of FW, Wolfe proposed to add the possibility to move away from an active atom in $\mathcal{S}^{(t)}$ (see middle of Figure 1); this simple modification is sufficient to make the algorithm linearly convergent for strongly convex functions. We describe the away-steps variant of Frank-Wolfe in Algorithm 1.The original algorithm presented in was not convergent; this was corrected by Guélat and Marcotte , assuming a tractable representation of $\mathcal{M}$ with linear inequalities and called it the modified Frank-Wolfe (MFW) algorithm. Our description in Algorithm 1 extends it to the more general setup of (1). The away direction $\bm{d}_{t}^{\hskip 0.41998pt\textnormal{A}}$ is defined in line 4 by finding the atom $\bm{v}_{t}$ in $\mathcal{S}^{(t)}$ that maximizes the potential of descent given by $g_{t}^{\hskip 0.41998pt\textnormal{A}}:=\left\langle-\nabla f(\bm{x}^{(t)}),\bm{x}^{(t)}-\bm{v}_{t}\right\rangle$. Note that this search is over the (typically small) active set $\mathcal{S}^{(t)}$, and is fundamentally easier than the linear oracle $\operatorname*{LMO_{\!\mathcal{A}}}$. The maximum step-size $\gamma_{\textnormal{max}}$ as defined on line 9 ensures that the new iterate $\bm{x}^{(t)}+\gamma\bm{d}_{t}^{\hskip 0.41998pt\textnormal{A}}$ stays in $\mathcal{M}$. In fact, this guarantees that the convex representation is maintained, and we stay inside $\operatorname*{conv}(\mathcal{S}^{(t)})\subseteq\mathcal{M}$. When $\mathcal{M}$ is a simplex, then the barycentric coordinates are unique and $\bm{x}^{(t)}+\gamma_{\textnormal{max}}\bm{d}_{t}^{\hskip 0.41998pt\textnormal{A}}$ truly lies on the boundary of $\mathcal{M}$. On the other hand, if $|\mathcal{A}|>\dim(\mathcal{M})+1$ (e.g. for the cube), then it could hypothetically be possible to have a step-size bigger than $\gamma_{\textnormal{max}}$ which is still feasible. Computing the true maximum feasible step-size would require the ability to know when we cross the boundary of $\mathcal{M}$ along a specific line, which is not possible for general $\mathcal{M}$. Using the conservative maximum step-size of line 9 ensures that we do not need this more powerful oracle. This is why Algorithm 1 requires to maintain $\mathcal{S}^{(t)}$ (unlike standard FW). Finally, as in classical FW, the FW gap $g_{t}^{\hskip 0.35002pt\textnormal{FW}}$ is an upper bound on the unknown suboptimality, and can be used as a stopping criterion:

If $\gamma_{t}=\gamma_{\textnormal{max}}$, then we call this step a drop step, as it fully removes the atom $\bm{v}_{t}$ from the currently active set of atoms $\mathcal{S}^{(t)}$ (by settings its weight to zero). The weight updates for lines 12 and 13 are of the following form: For a FW step, we have $\mathcal{S}^{(t+1)}=\{\bm{s}_{t}\}$ if $\gamma_{t}=1$; otherwise $\mathcal{S}^{(t+1)}=\mathcal{S}^{(t)}\cup\{\bm{s}_{t}\}$. Also, we have $\alpha^{(t+1)}_{\bm{s}_{t}}:=(1-\gamma_{t})\alpha^{(t)}_{\bm{s}_{t}}+\gamma_{t}$ and $\alpha^{(t+1)}_{\bm{v}}:=(1-\gamma_{t})\alpha^{(t)}_{\bm{v}}$ for $\bm{v}\in\mathcal{S}^{(t)}\setminus\{\bm{s}_{t}\}$. For an away step, we have $\mathcal{S}^{(t+1)}=\mathcal{S}^{(t)}\setminus\{\bm{v}_{t}\}$ if $\gamma_{t}=\gamma_{\textnormal{max}}$ (a drop step); otherwise $\mathcal{S}^{(t+1)}=\mathcal{S}^{(t)}$. Also, we have $\alpha^{(t+1)}_{\bm{v}_{t}}:=(1+\gamma_{t})\alpha^{(t)}_{\bm{v}_{t}}-\gamma_{t}$ and $\alpha^{(t+1)}_{\bm{v}}:=(1+\gamma_{t})\alpha^{(t)}_{\bm{v}}$ for $\bm{v}\in\mathcal{S}^{(t)}\setminus\{\bm{v}_{t}\}$.

Pairwise Frank-Wolfe.

The next variant that we present is inspired by an early algorithm by Mitchell et al. , called the MDM algorithm, originally invented for the polytope distance problem. Here the idea is to only move weight mass between two atoms in each step. More precisely, the generalized method as presented in Algorithm 2 moves weight from the away atom $\bm{v}_{t}$ to the FW atom $\bm{s}_{t}$, and keeps all other $\alpha$ weights un-changed. We call such a swap of mass between the two atoms a pairwise FW step, i.e. $\alpha_{\bm{v}_{t}}^{(t+1)}=\alpha_{\bm{v}_{t}}^{(t)}-\gamma$ and $\alpha_{\bm{s}_{t}}^{(t+1)}=\alpha_{\bm{s}_{t}}^{(t)}+\gamma$ for some step-size $\gamma\leq\gamma_{\textnormal{max}}:=\alpha_{\bm{v}_{t}}^{(t)}$. In contrast, classical FW shrinks all active weights at every iteration.

The pairwise FW direction will also be central to our proof technique to provide the first global linear convergence rate for away-steps FW, as well as the fully-corrective variant and Wolfe’s min-norm-point algorithm.

As we will see in Section 2.2, the rate guarantee for the pairwise FW variant is more loose than for the other variants, because we cannot provide a satisfactory bound on the number of the problematic swap steps (defined just before Theorem 1). Nevertheless, the algorithm seems to perform quite well in practice, often outperforming away-steps FW, especially in the important case of sparse solutions, that is if the optimal solution $\bm{x}^{*}$ lies on a low-dimensional face of $\mathcal{M}$ (and thus one wants to keep the active set $\mathcal{S}^{(t)}$ small). The pairwise FW step is arguably more efficient at pruning the coordinates in $\mathcal{S}^{(t)}\!$. In contrast to the away step which moves the mass back uniformly onto all other active elements $\mathcal{S}^{(t)}$ (and might require more corrections later), the pairwise FW step only moves the mass onto the (good) FW atom $\bm{s}_{t}$. A slightly different version than Algorithm 2 was also proposed by Ñanculef et al. , though their convergence proofs were incomplete (see Appendix A.3). The algorithm is related to classical working set algorithms, such as the SMO algorithm used to train SVMs . We refer to for an empirical comparison for SVMs, as well as their Section 5 for more related work. See also Appendix A.3 for a link between pairwise FW and .

Fully-Corrective Frank-Wolfe, and Wolfe’s Min-Norm Point Algorithm.

When the linear oracle is expensive, it might be worthwhile to do more work to optimize over the active set $\mathcal{S}^{(t)}$ in between each call to the linear oracle, rather than just performing an away or pairwise step. We give in Algorithm 3 the fully-corrective Frank-Wolfe (FCFW) variant, that maintains a correction polytope defined by a set of atoms $\mathcal{A}^{(t)}$ (potentially larger than the active set $\mathcal{S}^{(t)}$). Rather than obtaining the next iterate by line-search, $\bm{x}^{(t+1)}$ is obtained by re-optimizing $f$ over $\operatorname*{conv}(\mathcal{A}^{(t)})$. Depending on how the correction is implemented, and how the correction atoms $\mathcal{A}^{(t)}$ are maintained, several variants can be obtained. These variants are known under many names, such as the extended FW method by Holloway or the simplicial decomposition method . Wolfe’s min-norm point (MNP) algorithm for polytope distance problems is often confused with FCFW for quadratic objectives. The major difference is that standard FCFW optimizes $f$ over $\operatorname*{conv}(\mathcal{A}^{(t)})$, whereas MNP implements the correction as a sequence of affine projections that potentially yield a different update, but can be computed more efficiently in several practical applications . We describe precisely in Appendix A.1 a generalization of the MNP algorithm as a specific case of the correction subroutine from step 7 of the generic Algorithm 3.

The original convergence analysis of the FCFW algorithm (and also MNP algorithm ) only showed that they were finitely convergent, with a bound on the number of iterations in terms of the cardinality of $\mathcal{A}$ (unfortunately an exponential number in general). Holloway also argued that FCFW had an asymptotic linear convergence based on the flawed argument of Wolfe . As far as we know, our work is the first to provide global linear convergence rates for FCFW and MNP for general strongly convex functions. Moreover, the proof of convergence for FCFW does not require an exact solution to the correction step; instead, we show that the weaker properties stated for the approximate correction procedure in Algorithm 4 are sufficient for a global linear convergence rate (this correction could be implemented using away-steps FW, as done for example in ).

Global Linear Convergence Analysis

We first give the general intuition for the linear convergence proof of the different FW variants, starting from the work of Guélat and Marcotte . We assume that the objective function $f$ is smooth over a compact set $\mathcal{M}$, i.e. its gradient is Lipschitz continuous with constant $L$. Also let $M:=\operatorname{diam}(\mathcal{M})$. Let $\bm{d}_{t}$ be the direction in which the line-search is executed by the algorithm (Line 11 in Algorithm 1). By the standard descent lemma [see e.g. (1.2.5) in 28], we have:

We let $\bm{r}_{t}:=-\nabla f(\bm{x}^{(t)})$ and let $h_{t}:=f(\bm{x}^{(t)})-f(\bm{x}^{*})$ be the suboptimality error. Supposing for now that $\gamma_{\textnormal{max}}\geq\gamma_{t}^{*}:=\left\langle\bm{r}_{t},\bm{d}_{t}\right\rangle/(L\|\bm{d}_{t}\|^{2}$). We can set $\gamma=\gamma_{t}^{*}$ to minimize the RHS of (2), subtract $f(\bm{x}^{*})$ on both sides, and re-organize to get a lower bound on the progress:

where we use the ‘hat’ notation to denote normalized vectors: $\hat{\bm{d}}_{t}:=\bm{d}_{t}/\|\bm{d}_{t}\|$. Let $\bm{e}_{t}:=\bm{x}^{*}-\bm{x}^{(t)}$ be the error vector. By $\mu$-strong convexity of $f$, we have:

The RHS is lower bounded by its minimum as a function of $\gamma$ (unconstrained), achieved using $\gamma:=\langle\bm{r}_{t},\bm{e}_{t}\rangle/(\mu\|\bm{e}_{t}\|^{2})$. We are then free to use any value of $\gamma$ on the LHS and maintain a valid bound. In particular, we use $\gamma=1$ to obtain $f(\bm{x}^{*})$. Again re-arranging, we get:

The inequality (5) is fairly general and valid for any line-search method in direction $\bm{d}_{t}$. To get a linear convergence rate, we need to lower bound (by a positive constant) the term in front of $h_{t}$ on the RHS, which depends on the angle between the update direction $\bm{d}_{t}$ and the negative gradient $\bm{r}_{t}$. If we assume that the solution $\bm{x}^{*}$ lies in the relative interior of $\mathcal{M}$ with a distance of at least $\delta>0$ from the boundary, then $\langle\bm{r}_{t},\bm{d}_{t}\rangle\geq\delta\|\bm{r}_{t}\|$ for the FW direction $\bm{d}_{t}^{\hskip 0.35002pt\textnormal{FW}}$, and by combining with $\|\bm{d}_{t}\|\leq M$, we get a linear rate with constant $1-\frac{\mu}{L}(\frac{\delta}{M})^{2}$ (this was the result from ). On the other hand, if $\bm{x}^{*}$ lies on the boundary, then $\langle\hat{\bm{r}}_{t},\hat{\bm{d}}_{t}\rangle$ gets arbitrary close to zero for standard FW (the zig-zagging phenomenon) and the convergence is sublinear.

The key insight to prove the global linear convergence for AFW is to relate $\langle\bm{r}_{t},\bm{d}_{t}\rangle$ with the pairwise FW direction $\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}:=\bm{s}_{t}-\bm{v}_{t}$. By the way the direction $\bm{d}_{t}$ is chosen on lines 6 to 10 of Algorithm 1, we have:

We thus have $\langle\bm{r}_{t},\bm{d}_{t}\rangle\geq\langle\bm{r}_{t},\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}\rangle/2$. Now the crucial property of the pairwise FW direction is that for any potential negative gradient direction $\bm{r}_{t}$, the worst case inner product $\langle\hat{\bm{r}}_{t},\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}\rangle$

can be lower bounded away from zero by a quantity depending only on the geometry of $\mathcal{M}$ (unless we are at the optimum). We call this quantity the pyramidal width of $\mathcal{A}$. The figure on the right shows the six possible pairwise FW directions $\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}$ for a triangle domain, depending on which colored area the $\bm{r}_{t}$ direction falls into. We will see that the pyramidal width is related to the smallest width of pyramids that we can construct from $\mathcal{A}$ in a specific way related to the choice of the away and towards atoms $\bm{v}_{t}$ and $\bm{s}_{t}$. See (9) and our main Theorem 3 in Section 3.

This gives the main argument for the linear convergence of AFW for steps where $\gamma_{t}^{*}\leq\gamma_{\textnormal{max}}$. When $\gamma_{\textnormal{max}}$ is too small, AFW will perform a drop step, as the line-search will truncate the step-size to $\gamma_{t}=\gamma_{\textnormal{max}}$. We cannot guarantee sufficient progress in this case, but the drop step decreases the active set size by one, and thus they cannot happen too often (not more than half the time). These are the main elements for the global linear convergence proof for AFW. The rest is to carefully consider various boundary cases. We can re-use the same techniques to prove the convergence for pairwise FW, though unfortunately the latter also has the possibility of problematic swap steps. While their number can be bounded, so far we only found the extremely loose bound quoted in Theorem 1.

Proof Sketch for FCFW.

For FCFW, by line 4 of the correction Algorithm 4, the away gap satisfies $g_{t}^{\hskip 0.41998pt\textnormal{A}}\leq\epsilon$ at the beginning of a new iteration. Supposing that the algorithm does not exit at line 6 of Algorithm 3, we have $g_{t}^{\hskip 0.35002pt\textnormal{FW}}>\epsilon$ and therefore $2\langle\bm{r}_{t},\bm{d}_{t}^{\hskip 0.35002pt\textnormal{FW}}\rangle\geq\langle\bm{r}_{t},\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}\rangle$ using a similar argument as in (6). Finally, by line 3 of Algorithm 4, the correction is guaranteed to make at least as much progress as a line-search in direction $\bm{d}_{t}^{\hskip 0.35002pt\textnormal{FW}}$, and so the progress bound (5) applies also to FCFW.

2 Convergence Results

We now give the global linear convergence rates for the four variants of the FW algorithm: away-steps FW (AFW Alg. 1); pairwise FW (PFW Alg. 2); fully-corrective FW (FCFW Alg. 3 with approximate correction Alg. 4); and Wolfe’s min-norm point algorithm (Alg. 3 with MNP-correction as Alg. 5 in Appendix A.1). For the AFW, MNP and PFW algorithms, we call a drop step when the active set shrinks $|S^{(t+1)}|<|S^{(t)}|$. For the PFW algorithm, we also have the possibility of a swap step where $\gamma_{t}=\gamma_{\textnormal{max}}$ but $|S^{(t+1)}|=|S^{(t)}|$ (i.e. the mass was fully swapped from the away atom to the FW atom). A nice property of FCFW is that it does not have any drop step (it executes both FW steps and away steps simultaneously while guaranteeing enough progress at every iteration).

Suppose that $f$ has $L$-Lipschitz gradientFor AFW and PFW, we actually require that $\nabla f$ is $L$-Lipschitz over the larger domain $\mathcal{M}+\mathcal{M}-\mathcal{M}$. and is $\mu$-strongly convex over $\mathcal{M}=\operatorname*{conv}(\mathcal{A})$. Let $M=\operatorname{diam}(\mathcal{M})$ and $\delta=\mathop{PW\!idth}(\mathcal{A})$ as defined by (9). Then the suboptimality $h_{t}$ of the iterates of all the four variants of the FW algorithm decreases geometrically at each step that is not a drop step nor a swap step (i.e. when $\gamma_{t}<\gamma_{\textnormal{max}}$, called a ‘good step’), that is

Let $k(t)$ be the number of ‘good steps’ up to iteration $t$. We have $k(t)=t$ for FCFW; $k(t)\geq t/2$ for MNP and AFW; and $k(t)\geq t/(3|\mathcal{A}|!+1)$ for PFW (because of the swap steps). This yields a global linear convergence rate of $h_{t}\leq h_{0}\exp(-\rho\,k(t))$ for all variants. If $\mu=0$ (general convex), then $h_{t}=O(1/k(t))$ instead. See Theorem 8 in Appendix D for an affine invariant version and proof.

Note that to our knowledge, none of the existing linear convergence results showed that the duality gap was also linearly convergent. The result for the gap follows directly from the simple manipulation of (2); putting the FW gap to the LHS and optimizing the RHS for $\gamma\in$.

Suppose that $f$ has $L$-Lipschitz gradient over $\mathcal{M}$ with $M:=\operatorname{diam}(\mathcal{M})$. Then the FW gap $g_{t}^{\hskip 0.35002pt\textnormal{FW}}$ for any algorithm is upper bounded by the primal error $h_{t}$ as follows:

Pyramidal Width

We now describe the claimed lower bound on the angle between the negative gradient and the pairwise FW direction, which depends only on the geometric properties of $\mathcal{M}$. According to our argument about the progress bound (5) and the PFW gap (6), our goal is to find a lower bound on $\langle\bm{r}_{t},\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}\rangle/\langle\bm{r}_{t},\hat{\bm{e}}_{t}\rangle$. First note that $\langle\bm{r}_{t},\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}\rangle\!=\!\langle\bm{r}_{t},\bm{s}_{t}\!-\!\bm{v}_{t}\rangle\!=\displaystyle\max_{\bm{s}\in\mathcal{M},\bm{v}\in\mathcal{S}^{(t)}}\langle\bm{r}_{t},\bm{s}-\bm{v}\rangle$ where $\mathcal{S}^{(t)}$ is a possible active set for $\bm{x}^{(t)}$. This looks like the directional width of a pyramid with base $\mathcal{S}^{(t)}$ and summit $\bm{s}_{t}$. To be conservative, we consider the worst case possible active set for $\bm{x}^{(t)}$; this is what we will call the pyramid directional width $\mathop{PdirW}(\mathcal{A},\bm{r}_{t},\bm{x}^{(t)})$. We start with the following definitions.

The directional width of a set $\mathcal{A}$ with respect to a direction $\bm{r}$ is defined as \mathop{dirW}(\mathcal{A},\bm{r}):=\max_{\bm{s},\bm{v}\in\mathcal{A}}\big{\langle}\frac{\bm{r}}{\left\lVert\bm{r}\right\rVert},\bm{s}-\bm{v}\big{\rangle}. The width of $\mathcal{A}$ is the minimum directional width over all possible directions in its affine hull.

Pyramidal Directional Width.

We define the pyramidal directional width of a set $\mathcal{A}$ with respect to a direction $\bm{r}$ and a base point $\bm{x}\in\mathcal{M}$ to be

where $\mathcal{S}_{\bm{x}}:=\{\mathcal{S}\,|\,\mathcal{S}\subseteq\mathcal{A}$ such that $\bm{x}$ is a properBy proper convex combination, we mean that all coefficients are non-zero in the convex combination. convex combination of all the elements in $\mathcal{S}\}$, and $\bm{s}(\mathcal{A},\bm{r}):=\operatorname*{\arg\max}_{\bm{v}\in\mathcal{A}}\langle\bm{r},\bm{v}\rangle$ is the FW atom used as a summit.

Pyramidal Width.

To define the pyramidal width of a set, we take the minimum over the cone of possible feasible directions $\bm{r}$ (in order to avoid the problem of zero width). A direction $\bm{r}$ is feasible for $\mathcal{A}$ from $\bm{x}$ if it points inwards $\operatorname*{conv}(\mathcal{A})$, (i.e. $\bm{r}\in\text{cone}(\mathcal{A}-\bm{x})$). We define the pyramidal width of a set $\mathcal{A}$ to be the smallest pyramidal width of all its faces, i.e.

Let $\bm{x}\in\mathcal{M}=\operatorname*{conv}(\mathcal{A})$ be a suboptimal point and $\mathcal{S}$ be an active set for $\bm{x}$. Let $\bm{x}^{*}$ be an optimal point and corresponding error direction $\hat{\bm{e}}=(\bm{x}^{*}-\bm{x})/\left\lVert\bm{x}^{*}-\bm{x}\right\rVert$, and negative gradient $\bm{r}:=-\nabla f(\bm{x})$ (and so $\langle\bm{r},\hat{\bm{e}}\rangle>0$). Let $\bm{d}=\bm{s}\!-\!\bm{v}$ be the pairwise FW direction obtained over $\mathcal{A}$ and $\mathcal{S}$ with negative gradient $\bm{r}$. Then

1 Properties of Pyramidal Width and Consequences

The pyramidal width of a set $\mathcal{A}$ is lower bounded by the minimal width over all subsets of atoms, and thus is strictly greater than zero if the number of atoms is finite. On the other hand, this lower bound is often too loose to be useful, as in particular, vertex subsets of the unit cube in dimension $d$ can have exponentially small width $O(d^{-\frac{d}{2}})$ [see Corollary 27 in 37]. On the other hand, as we show here, the pyramidal width of the unit cube is actually $1/\sqrt{d}$, justifying why we kept the tighter but more involved definition (9). See Appendix B.1 for the proof.

For the probability simplex with $d$ vertices, the pyramidal width is actually the same as its width, which is $2/\sqrt{d}$ when $d$ is even, and $2/\sqrt{d\!-\!1/d}$ when $d$ is odd (see Appendix B.1). In contrast, the pyramidal width of an infinite set can be zero. For example, for a curved domain, the set of active atoms $\mathcal{S}$ can contain vertices forming a very narrow pyramid, yielding a zero width in the limit.

Condition Number of a Set.

The inverse of the rate constant $\rho$ appearing in Theorem 1 is the product of two terms: $L/\mu$ is the standard condition number of the objective function appearing in the rates of gradient methods in convex optimization. The second quantity $(M/\delta)^{2}$ (diameter over pyramidal width) can be interpreted as a condition number of the domain $\mathcal{M}$, or its eccentricity. The more eccentric the constraint set (large diameter compared to its pyramidal width), the slower the convergence. The best condition number of a function is when its level sets are spherical; the analog in term of the constraint sets is actually the regular simplex, which has the maximum width-to-diameter ratio amongst all simplices [see Corollary 1 in 3]. Its eccentricity is (at most) $d/2$. In contrast, the eccentricity of the unit cube is $d^{2}$, which is much worse.

We conjecture that the pyramidal width of a set of vertices (i.e. extrema of their convex hull) is non-increasing when another vertex is added (assuming that all previous points remain vertices). For example, the unit cube can be obtained by iteratively adding vertices to the regular probability simplex, and the pyramidal width thereby decreases from $2/\sqrt{d}$ to $1/\sqrt{d}$. This property could provide lower bounds for the pyramidal width of more complicated polytopes, such as $1/\sqrt{d}$ for the $d$-dimensional marginal polytope, as it can be obtained by removing vertices from the unit cube.

Complexity Lower Bounds.

Combining the convergence Theorem 1 and the condition number of the unit simplex, we get a complexity of $O(d\frac{L}{\mu}\log(\frac{1}{\epsilon}))$ to reach $\epsilon$-accuracy when optimizing a strongly convex function over the unit simplex. Here the linear dependence on $d$ should not come as a surprise, in view of the known lower bound of $1/t$ for $t\leq d$ for Frank-Wolfe type methods .

Applications to Submodular Minimization.

See Appendix A.2 for a consequence of our linear rate for the popular MNP algorithm for submodular function optimization (over the base polytope).

Non-Strongly Convex Generalization

Illustrative Experiments

Acknowledgements.

We thank J.B. Alayrac, E. Hazan, A. Hubard, A. Osokin and P. Marcotte for helpful discussions. This work was partially supported by the MSR-Inria Joint Center and a Google Research Award.

References

Outline.

The appendix is organized as follows: In Appendix A, we discuss some of the Frank-Wolfe algorithm variants in more details and related work (including the MNP algorithm in Appendix A.1 and its application to submodular minimization in Appendix A.2).

In Appendix B, we discuss the pyramidal width for some particular cases of sets (such as the probability simplex and the unit cube), and then provide the proof of the main Theorem 3 relating the pyramidal width to the progress quantity essential for the linear convergence rate. Section C presents an affine invariant version of the complexity constants.

In the following Section D, we show the main linear convergence result for the four variants of the FW algorithm, and also discuss the sublinear rates for general convex functions. Section E presents a simple experiment demonstrating the empirical tightness of the theoretical linear convergence rate constant. Finally, in Appendix F we discuss the generalization of the linear convergence to some cases of non-strongly convex functions in more details.

Appendix A More on Frank-Wolfe Algorithm Variants

A generalization of Wolfe’s min-norm point (MNP) algorithm for general convex functions is to run Algorithm 3 with the correction subroutine in step 7 implemented as presented below in Algorithm 5. In Wolfe’s paper , the correction step is called the minor cycle; whereas the FW outer loop is called the major cycle.

As we have mentioned in Section 1, MNP for polytope distance is often confused with fully-corrective FW as presented in Algorithm 3, for quadratic objectives. In fact, standard FCFW optimizes $f$ over $\operatorname*{conv}(\mathcal{A}^{(t)})$, whereas MNP implements the correction as a sequence of affine projections on the active set that potentially yield a different update.

There are two main differences between FCFW and the MNP algorithm. First, after a correction step, MNP guarantees that $\bm{x}^{(t+1)}$ is both the minimizer of $f$ over the affine hull of $\mathcal{A}^{(t+1)}$ and also $\operatorname*{conv}(\mathcal{A}^{(t+1)})$ (where $\mathcal{A}^{(t+1)}$ might be much smaller than $\mathcal{A}^{(t)}\cup\{\bm{s}_{t}\}$), whereas FCFW guarantees that $\bm{x}^{(t+1)}$ is the minimizer of $f$ over $\operatorname*{conv}(\mathcal{A}^{(t)}\cup\{\bm{s}_{t}\})$ – this is usually not the case for MNP unless at most one atom was dropped from the correction polytope, as is apparent from our convergence proof. Secondly, the correction atoms $\mathcal{A}^{(t)}$ are always affinely independent for MNP and are identical to the active set $\mathcal{S}^{(t)}$, whereas FCFW can use both redundant as well as inactive atoms. The advantage of the MNP implementation using affine hull projections is that the correction can be efficiently implemented when $f$ is the Euclidean norm, especially when a triangular array representation of the active set is maintained (see the careful implementation details in Wolfe’s original paper ).

The MNP variant indeed only makes sense when the minimization of $f$ over the affine hull of $\mathcal{M}$ is well-defined (and is efficient). Note though that the line-search in step 7 does not require any new information about $\mathcal{M}$, as it is made only with respect to $\operatorname*{conv}(\mathcal{S}^{(k-1)})$, for which we have an explicit list of vertices. This line-search can be efficiently computed in $O(|\mathcal{S}^{(k-1)}|)$, and is well described for example in step 2(d)(iii) of Algorithm 1 of \citetsupChakrabarty:2014:MNP.

A.2 Applications to Submodular Minimization

An interesting consequence of our global linear convergence result for FW algorithm variants here is the potential to reduce the gap between the known theoretical rates and the impressive empirical performance of MNP for submodular function minimization (over the base polytope). While Bach already showed convergence of FW in this case, \citetsupChakrabarty:2014:MNP later gave a weaker convergence rate for Wolfe’s MNP variant. For exact submodular function optimization, the overall complexity by \citepsupChakrabarty:2014:MNP was $O(d^{5}F^{2})$ (with some corrections\citetsupChakrabarty:2014:MNP quoted a complexity of $O(d^{7}F^{2})$ for MNP. However, this fell short of the earlier result of Bach for classic FW in the submodular minimization case, which was better by two $O(d)$ factors. \citepsupChakrabarty:2014:MNP counted $O(d^{3})$ per iteration of the MNP algorithm whereas Wolfe had provided a $O(d^{2})$ implementation; and they missed that there were at least $t/2$ good cycles (‘non drop steps’) after $t$ iterations, rather than $O(t/d)$ as they have used. ), where $F$ is the maximum absolute value of the integer-valued submodular function. This is in contrast to $O(d^{5}\log(d\,F))$ for the fastest algorithms \citepsupIwata:2002:subraey. Using our linear convergence, the $F$ factor can be put back in the $\log$ term for MNP,This is assuming that the eccentricity of the base polytope does not depend on $F$, which remains to be proven. matching their empirical observations that the MNP algorithm was not too sensitive to $F$. The same follows for AFW and FCFW, which is novel.

A.3 Pairwise Frank-Wolfe

Our new analysis of the pairwise Frank-Wolfe variant as introduced in Section 1 is motivated by the work of Garber and Hazan , who provided the first variant of Frank-Wolfe with a global linear convergence rate with explicit constants that do not depend on the location of the optimum $\bm{x}^{*}$, for a more complex extension of such a pairwise algorithm. An important contribution of the work of Garber and Hazan was to define the concept of local linear oracle, which (approximately) minimizes a linear function on the intersection of $\mathcal{M}$ and a small ball around $\bm{x}^{(t)}$ (hence the name local). They showed that if such a local linear oracle was available, then one could replace the step that moves towards $\bm{s}_{t}$ in the standard FW procedure with a constant step-size move towards the point returned by the local linear oracle to obtain a globally linearly convergent algorithm. They then demonstrated how to implement such a local linear oracle by using only one call to the linear oracle (to get $\bm{s}_{t}$), as well as sorting the atoms in $\mathcal{S}^{(t)}$ in decreasing order of their inner product with $\nabla f(\bm{x}^{(t)})$ (note that the first element then is the away atom $\bm{v}_{t}$ from Algorithm 1). The procedure implementing the local linear oracle amounts to iteratively swapping the mass from the away atom $\bm{v}_{t}$ to the FW atom $\bm{s}_{t}$ until enough mass has been moved (given by some precomputed constants). If the amount of mass to move is bigger than $\alpha_{\bm{v}_{t}}^{(t)}$, then one sets $\alpha_{\bm{v}_{t}}^{(t)}$ to zero and start moving mass from the second away atom, and so on, until enough mass has been moved (which is why the sorting is needed). We call such a swap of mass between the away atom and the FW atom a pairwise FW step, i.e. $\alpha_{\bm{v}_{t}}^{(t+1)}=\alpha_{\bm{v}_{t}}^{(t)}-\gamma$ and $\alpha_{\bm{s}_{t}}^{(t+1)}=\alpha_{\bm{s}_{t}}^{(t)}+\gamma$ for some step-size $\gamma\leq\gamma_{\textnormal{max}}:=\alpha_{\bm{v}_{t}}^{(t)}$. The local linear oracle is implemented as a sequence of pairwise FW steps, always keeping the same FW atom $\bm{s}_{t}$ as the target, but updating the away atom to move from as we set their coordinates to zero.

A major disadvantage of the algorithm presented by Garber and Hazan is that their algorithm is not adaptive: it requires the computation of several (loose) constants to determine the step-sizes, which means that the behavior of the algorithm is stuck in its worst-case analysis. The pairwise Frank-Wolfe variant is obtained by simply doing one line-search in the pairwise Frank-Wolfe direction $\bm{d}^{\hskip 0.35002pt\textnormal{PFW}}_{t}:=\bm{s}_{t}-\bm{v}_{t}$ (see Algorithm 2). This gives a fully adaptive algorithm, and it turns out that this is sufficient to yield a global linear convergent rate.

We here point out some corrections to the convergence proofs given in for a variant of pairwise FW that chooses between a standard FW step and a pairwise FW step by picking the one which makes the most progress on the objective after a line-search. [27, Proposition $1$] states the global convergence of their algorithm by arguing that $\langle-\nabla f(\bm{x}^{(t)}),\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}\rangle\geq\langle-\nabla f(\bm{x}^{(t)}),\bm{d}_{t}^{\hskip 0.35002pt\textnormal{FW}}\rangle$ and then stating that they can re-use the same pattern as the standard FW convergence proof but with the direction $\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}$. But this is forgetting the fact that the maximal step-size $\gamma_{\textnormal{max}}=\alpha_{\bm{v}_{t}}$ for a pairwise FW step can be too small to make sufficient progress. Their global convergence statement is still correct as every step of their algorithm makes more progress than a FW step, which already has a global convergence result, but this is not the argument they made. Similarly, they state a global linear convergence result in their Proposition 4, citing a proof from \citepsupallende2013PFW. On the other hand, the relevant used Proposition 3 in \citepsupallende2013PFW forgot to consider the possibility of problematic swap steps that we had to painfully bound in our convergence Theorem 8; they only considered drop steps or ‘good steps’, thereby missing a bound on the number of swap steps to get a valid global bound.

A.4 Other Related Work

Appendix B Pyramidal Width

First consider a point $\bm{x}$ in the interior of the cube, and let $\bm{r}$ be the unit length direction achieving the smallest pyramidal width for $\bm{x}$. Let $\bm{s}=\bm{s}(\mathcal{A},\bm{r})$ (the FW atom in direction $\bm{r}$). Without loss of generality, by symmetry,We thank Jean-Baptiste Alayrac for inspiring us to use symmetry in the proof. we can rotate the cube so that $\bm{s}$ lies at the origin. This implies that each coordinate of $\bm{r}$ is non-positive. Represent a vertex $\bm{v}$ of the cube as its set of indices for which $v_{i}=1$. Then $\left\langle\bm{r},\bm{s}-\bm{v}\right\rangle=\sum_{i\in\bm{v}}-r_{i}\geq\max_{i\in\bm{v}}|r_{i}|$. Consider any possible active set $\mathcal{S}$; as $\bm{x}$ has all its coordinate strictly positive, for each dimension $i$, there must exist an element of $\mathcal{S}$ with its $i$ coordinate equals to 1. This means that $\max_{\bm{v}\in\mathcal{S}}\langle\bm{r},\bm{s}-\bm{v}\rangle\geq\|\bm{r}\|_{\infty}$. But as $\bm{r}$ has unit Euclidean norm, then $\|\bm{r}\|_{\infty}\geq 1/\sqrt{d}$. Now consider $\bm{x}$ to lie on a facet of the cube (i.e. the active set $\mathcal{S}$ is lower dimensional); and let $I:=\{i:r_{i}<0\}$. Since $\bm{r}$ has to be feasible from $\bm{x}$, for each $i\in I$, we cannot have $x_{i}=0$ and thus there exists an element of the active set with its $i^{\text{th}}$ coordinate equal to 1. We thus have that $\max_{\bm{v}\in\mathcal{S}}\langle\bm{r},\bm{s}-\bm{v}\rangle\geq\|\bm{r}\|_{\infty}\geq 1/\sqrt{|I|}\geq 1/\sqrt{d}$. Using the same argument on a lower dimensional $\mathcal{K}$ give a lower bound of $1/\sqrt{\dim(\mathcal{K})}$ which is bigger. These cover all the possibilities appearing in the definition of the pyramidal width, and thus the lower bound is correct. It is achieved by choosing an $\bm{x}$ in the interior, the canonical basis as the active set $\mathcal{S}$, and the direction defined by $r_{i}=-1/\sqrt{d}$ for each $i$. ∎

We note that both the active set definition $\mathcal{S}$ and the feasibility condition on $\bm{r}$ were crucially used in the above proof to obtain such a large value for the pyramidal width of the unit cube, thus justifying the somewhat involved definition appearing in (9). On the other hand, the astute reader might have noticed that the important quantity to lower bound for the linear convergence rate of the different FW variants is $\frac{\langle\bm{r}_{t},\hat{\bm{d}}_{t}\rangle}{\langle\bm{r}_{t},\hat{\bm{e}}_{t}\rangle}$ (as in (5)), rather than the looser value $\frac{1}{M}\frac{\langle\bm{r}_{t},\bm{d}_{t}\rangle}{\langle\bm{r}_{t},\hat{\bm{e}}_{t}\rangle}$ that we used to handle the proof of the difficult Theorem 3 (where we recall that $M$ is the diameter of $\mathcal{M}$). One could thus hope to get a tighter measure for the condition number of a set by considering $\|\bm{s}-\bm{v}\|$ (with $\bm{s}$ and $\bm{v}$ the minimizing witnesses for the pyramidal width) instead of the diameter $M$ in the ratio diameter / pyramidal width. This might give a tighter constant for general sets, but in the case of the cube, it does not change the general $\Omega(d^{2})$ dependence for its condition number. To see this, suppose that $d$ is even and let $k=d/2$. Consider the direction $\bm{r}$ with $r_{i}:=-1$ for $1\leq i\leq k$, and $r_{i}:=-\epsilon$ for $(k\!+\!1)\leq i\leq d$. We thus have that the FW atom $\bm{s}(\mathcal{A},\bm{r})$ is the origin as before. Consider $\bm{x}$ such that $x_{i}:=1/k$ for $1\leq i\leq k$, and $x_{i}:=1$ for $(k\!+\!1)\leq i\leq d$, that is, $\bm{x}$ is the uniform convex combination of the $k$ vertices which has only one non-zero in the first $k$ coordinates, and the last $k$ coordinates all equal to $1$. We have that $\bm{r}$ is a feasible direction from $\bm{x}$, and that all vertices in the active set for $\bm{x}$ have the same inner product with $\bm{r}$: $\max_{\bm{v}\in\mathcal{S}}\langle\bm{r},\bm{s}-\bm{v}\rangle=1+k\epsilon$. We thus have:

Squaring the inverse, we thus get that the condition number of the cube is at least $k^{2}=d^{2}/4$ even using this tighter definition, thus not changing the $\Omega(d^{2})$ dependence.

For any $\bm{x}$ in the relative interior of the probability simplex on $d$ vertices, we have that $\mathcal{S}=\mathcal{A}$, and thus the pyramidal directional width (8) in the feasible direction $\bm{r}$ with base point $\bm{x}$ is the same as the standard directional width. Moreover, any face of the probability simplex is just a probability simplex in lower dimensions (with bigger width). This is why the pyramidal width of the probability simplex is the same as its standard width. The width of a regular simplex was implicitly given in ; we provide more details here on this citation. Alexander considers a regular simplex with $k$ vertices and side length $\Delta$. For any partition of the $k$ points into a set of $r$ and $k-r$ points (for $r\leq\left\lfloor{k/2}\right\rfloor$), one can compute the distance $c(r,\Delta)$ between the flats (affine hulls) of the two sets (which also corresponds to a specific directional width). Alexander gives a formula on the third line of p. 91 in for the square of this distance:

The width of the regular simplex is obtained by taking the minimum of (11) with respect to $r\leq\left\lfloor{k/2}\right\rfloor$. As (11) is a decreasing function up to $r=k/2$, we obtain its minimum by substituting $r=\left\lfloor{k/2}\right\rfloor$. By using $\Delta=\sqrt{2}$, $k=d$ and $r=\left\lfloor{d/2}\right\rfloor$ in (11), we get that the width for the probability simplex on $d$ vertices is $2/\sqrt{d}$ when $d$ is even and the slightly bigger $2/\sqrt{d-1/d}$ when $d$ is odd.

From the pyramidal width perspective, one can obtain these numbers by considering any relative interior point of the probability simplex as $\bm{x}$ and considering the following feasible $\bm{r}$. For $d$ even, we let $r_{i}:=1$ for $1\leq i\leq d/2$ and $r_{i}:=-1$ for $i>d/2$. Note that $\sum_{i}r_{i}=0$ and thus $\bm{r}$ is a feasible direction for a point in the relative interior of the probability simplex. Then $\max_{\bm{s},\bm{v}\in\mathcal{A}}\langle\frac{\bm{r}}{\|\bm{r}\|},\bm{s}-\bm{v}\rangle=\frac{1}{\sqrt{d}}(1+1)=\frac{2}{\sqrt{d}}$ as claimed. For $d$ odd, we can choose $r_{i}:=\frac{2}{d-1}$ for $1\leq i\leq\frac{d-1}{2}$, and $r_{i}:=\frac{2}{d+1}$ for $i\geq\frac{d+1}{2}$. Then $\|\bm{r}\|=\sqrt{\frac{4d}{d^{2}-1}}$ and $\max_{\bm{s},\bm{v}\in\mathcal{A}}\langle\frac{\bm{r}}{\|\bm{r}\|},\bm{s}-\bm{v}\rangle=\sqrt{\frac{4d}{d^{2}-1}}=2/\sqrt{d-1/d}$ as claimed. Showing that these obtained values were the minimum possible ones is non-trivial though, which is why we appealed to the width of the regular simplex computed from .

B.2 Proof of Theorem 3 on the Pyramidal Width

In this section, we prove the main technical result in our paper: a geometric lower bound for the crucial quantity appearing in the linear convergence rate for the FW optimization variants.

Let $\bm{x}\in\mathcal{M}=\operatorname*{conv}(\mathcal{A})$ be a suboptimal point and $\mathcal{S}$ be an active set for $\bm{x}$. Let $\bm{x}^{*}$ be an optimal point and corresponding error direction $\hat{\bm{e}}=(\bm{x}^{*}-\bm{x})/\left\lVert\bm{x}^{*}-\bm{x}\right\rVert$, and negative gradient $\bm{r}:=-\nabla f(\bm{x})$ (and so $\langle\bm{r},\hat{\bm{e}}\rangle>0$). Let $\bm{d}^{\hskip 0.35002pt\textnormal{PFW}}$ be the pairwise FW direction obtained over $\mathcal{A}$ and $\mathcal{S}$ with negative gradient $\bm{r}$. Then we have:

We first give a proof sketch, and then give the full proof.

Recall that a direction $\bm{r}$ is feasible for $\mathcal{A}$ from $\bm{x}$ if it points inwards $\operatorname*{conv}(\mathcal{A})$, i.e. $\bm{r}\in\text{cone}(\mathcal{A}-\bm{x})$.

By Cauchy-Schwarz, the denominator of (12) is at most $\left\lVert\bm{r}\right\rVert$. If $\bm{r}$ is a feasible direction from $\bm{x}$ for $\mathcal{A}$, then the LHS is lower bounded by $\mathop{PdirW}(\mathcal{A},\bm{r},\bm{x})$ as $\bm{d}^{\hskip 0.35002pt\textnormal{PFW}}$ is included as a possible $\bm{s}-\bm{v}$ direction considered in the definition of $\mathop{PdirW}$ (8). If $\bm{r}$ is not feasible from $\bm{x}$, this means that $\bm{x}$ lies on the boundary of $\mathcal{M}$. One can then show that the potential $\bm{x}^{*}$ that can maximize $\langle\bm{r},\hat{\bm{e}}\rangle$ has also to lie on a facet $\mathcal{K}$ of $\mathcal{M}$ containing $\bm{x}$ (see Lemma 5 below). The idea is then to project $\bm{r}$ onto $\mathcal{K}$, and re-do the argument with $\mathcal{K}$ replacing $\mathcal{M}$ and show that the inequality is in the right direction. This explains why all the subfaces of $\mathcal{M}$ are considered in the definition of the pyramidal width (9), and that only feasible directions are considered. ∎

Let $\bm{x}$ be at the origin, inside a polytope $\mathcal{K}$ and suppose that $\bm{r}\in\text{span}(\mathcal{K})$ is not a feasible direction for $\mathcal{K}$ from $\bm{x}$ (i.e. $\bm{r}\notin\text{cone}(\mathcal{K})$). Then a feasible direction in $\mathcal{K}$ minimizing the angle with $\bm{r}$ lies on a facetAs a reminder, we define a k-face of $\mathcal{M}$ (a $k$-dimensional face of $\mathcal{M}$) a set $\mathcal{K}$ such that $\mathcal{K}=\mathcal{M}\cap\{\bm{y}:\left\langle\bm{r},\bm{y}-\bm{x}\right\rangle=\mathbf{0}\}$ for some normal vector $\bm{r}$ and fixed reference point $\bm{x}\in\mathcal{K}$ with the additional property that $\mathcal{M}$ lies on one side of the given half-space determined by $\bm{r}$ i.e. $\left\langle\bm{r},\bm{y}-\bm{x}\right\rangle\leq\mathbf{0}$ $\forall\bm{y}\in\mathcal{M}$. $k$ is the dimensionality of the affine hull of $\mathcal{K}$. We call a $k$-face of dimensions $k=0$, $1$, $\textrm{dim}(\mathcal{M})-2$ and $\textrm{dim}(\mathcal{M})-1$ a vertex, edge, ridge and facet respectively. $\mathcal{M}$ is a $k$-face of itself with $k=\textrm{dim}(\mathcal{M})$. See Definition 2.1 in the book of \citetsupZiegler:1995td, which we also recommend for more background material on polytopes. $\mathcal{K}^{\prime}$ of $\mathcal{K}$ that includes the origin $\bm{x}$. That is:

where $\mathcal{K}^{\prime}$ contains $\bm{x}$, $\|\cdot\|$ is the Euclidean norm and $\bm{r}^{\prime}$ is defined as the orthogonal projection of $\bm{r}$ on $\text{span}(\mathcal{K}^{\prime})$.

This seems like an obvious geometric fact (see Figure 3), but we prove it formally, as sometimes high dimensional geometry is tricky (for example, the result is false without the assumption that $\bm{r}\in\text{span}(\mathcal{K})$ or if $\|\cdot\|$ is not the Euclidean norm). Rewrite the optimization variable on the LHS of (13) as $\hat{\bm{e}}=\frac{\bm{e}}{\|\bm{e}\|}$. The optimization domain for $\hat{\bm{e}}$ is thus the intersection between the unit sphere and $\text{cone}(\mathcal{K})$. We now show that any maximizer $\hat{\bm{e}}^{*}$ cannot lie in the relative interior of $\text{cone}(\mathcal{K})$, and thus it has to lie on a facet of $\text{cone}(\mathcal{K})$, implying then that a corresponding maximizer $\bm{e}^{*}$ is lying on a facet of $\mathcal{K}$ containing $\bm{x}$, concluding the proof for the first equality in (13).

First, as $\bm{r}\in\text{span}(\mathcal{K})$, we can consider without loss of generality that $\text{cone}(\mathcal{K})$ is full dimensional by projecting on its affine hull if needed. We want to solve $\max_{\hat{\bm{e}}}\left\langle\bm{r},\hat{\bm{e}}\right\rangle$ s.t. $\|\hat{\bm{e}}\|^{2}=1$ and $\hat{\bm{e}}\in\text{cone}(\mathcal{K})$. By contradiction, we suppose that $\hat{\bm{e}}^{*}$ lies in the interior of $\text{cone}(\mathcal{K})$, and so we can remove the polyhedral cone constraint. The gradient of the objective is the constant $\bm{r}$ and the gradient of the equality constraint is $2\hat{\bm{e}}$. By the Karush-Kuhn-Tucker (KKT) necessary conditions for a stationary point to the problem with the only equality constraint $\|\hat{\bm{e}}\|^{2}=1$ (see e.g. \citepsup[Proposition 3.3.1 in][]bertsekas1999nonlinear), then the gradient of the objective is collinear to the gradient of the equality constraint, i.e. we have $\hat{\bm{e}}^{*}=\pm\hat{\bm{r}}$. Since $\hat{\bm{r}}$ is not feasible, then $\hat{\bm{e}}^{*}=-\hat{\bm{r}}$, which is actually a local minimum of the inner product by Cauchy-Schwarz. We thus conclude that the maximizing $\hat{\bm{e}}^{*}$ lies on the boundary of $\text{cone}(\mathcal{K})$, concluding the proof for the first equality in (13).

For the second equality in (13), we simply use the fact that $\bm{r}-\bm{r}^{\prime}$ is orthogonal to the elements of $\mathcal{K}^{\prime}$ by the definition of the orthogonal projection. ∎

Let $\hat{\bm{e}}(\bm{x}^{*}):=\frac{\bm{x}^{*}-\bm{x}}{\left\lVert\bm{x}^{*}-\bm{x}\right\rVert}$ be the normalized error vector. We consider the worst-case possibility for $\bm{x}^{*}$. As $\bm{x}$ is not optimal, we require that $\left\langle\bm{r},\hat{\bm{e}}(\bm{x}^{*})\right\rangle>0$. We recall that by definition of the pairwise FW direction:

By Cauchy-Schwarz, we always have $\left\langle\bm{r},\hat{\bm{e}}(\bm{x}^{*})\right\rangle\leq\|\bm{r}\|$. If $\bm{r}$ is a feasible direction from $\bm{x}$ in $\operatorname*{conv}(\mathcal{A})$, then $\bm{r}$ appears in the set of directions considered in the definition of the pyramidal width (9) for $\mathcal{A}$ and so from (14), we have that the inequality (12) holds.

The first term on the RHS of (15) just comes from the definition of $\bm{d}^{\hskip 0.35002pt\textnormal{PFW}}$ (with equality), whereas the second term is considering the worst case possibility for $\bm{x}^{*}$ to lower bound the LHS. Note also that the second term has to be strictly greater to zero since $\bm{x}$ is not optimal.

where $\bm{r}^{\prime}$ is the result of the orthogonal projection of $\bm{r}$ on $\text{span}(\mathcal{K}^{\prime})$. We now look at how the numerator of (15) transforms when considering $\bm{r}^{\prime}$ and $\mathcal{K}^{\prime}$:

Plugging (16) and (17) into the inequality (15), we get:

Appendix C Affine Invariant Formulation

Here we provide linear convergence proofs in terms of affine invariant quantities, since all the Frank-Wolfe algorithm variants presented in this paper are affine invariant. The statements presented in the main paper above are special cases of the following more general theorems, by using the bounds (20) for the curvature constant $C_{f}$, and Theorem 6 for the affine invariant strong convexity $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$.

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{M}$ by a surjective linear or affine map $\bm{A}:\hat{\mathcal{M}}\rightarrow\mathcal{M}$, then the “old” and “new” optimization problems $\min_{\bm{x}\in\mathcal{M}}f(\bm{x})$ and $\min_{\hat{\bm{x}}\in\hat{\mathcal{M}}}\hat{f}(\hat{\bm{x}})$ for $\hat{f}(\hat{\bm{x}}):=f(\bm{A}\hat{\bm{x}})$ look completely the same to the algorithm.

More precisely, every “new” iterate must remain exactly the transform of the corresponding old iterate; an affine invariant analysis should thus yield the convergence rate and constants unchanged by the transformation. It is well known that Newton’s method is affine invariant under invertible $\bm{A}$, and the Frank-Wolfe algorithm and all the variants presented here are affine invariant in the even stronger sense under arbitrary surjective $\bm{A}$ . (This is directly implied if the algorithm and all constants appearing in the analysis only depend on inner products with the gradient, which are preserved since $\nabla\hat{f}=\bm{A}^{T}\nabla f$.)

Note however that the property of being an extremum point (vertex) of $\mathcal{M}$ is not affine invariant (see [5, Section 3.1] for an example). This explains why we presented all algorithms here as working with atoms $\mathcal{A}$ rather than vertices of the domain, thus maintaining the affine invariance of the algorithms as well as their convergence analysis.

The definition of $C_{f}$ closely mimics the fundamental descent lemma (2). The assumption of bounded curvature $C_{f}$ closely corresponds to a Lipschitz assumption on the gradient of $f$. More precisely, if $\nabla f$ is $L$-Lipschitz continuous on $\mathcal{M}$ with respect to some arbitrary chosen norm $\left\lVert.\right\rVert$ in dual pairing, i.e. $\left\lVert\nabla f(\bm{x})-\nabla f(\bm{y})\right\rVert_{*}\leq L\left\lVert\bm{x}-\bm{y}\right\rVert$, then

where $\operatorname{diam}_{\left\lVert.\right\rVert}(.)$ denotes the $\left\lVert.\right\rVert$-diameter, see [16, Lemma 7]. While the early papers on the Frank-Wolfe algorithm relied on such Lipschitz constants with respect to a norm, the curvature constant $C_{f}$ here is affine invariant, does not depend on any norm, and gives tighter convergence rates. The quantity $C_{f}$ combines the complexity of the domain $\mathcal{M}$ and the curvature of the objective function $f$ into a single quantity. The advantage of this combination is well illustrated in [22, Lemma A.1], where Frank-Wolfe was used to optimize a quadratic function over product of probability simplices with an exponential number of dimensions. In this case, the Lipschitz constant could be exponentially worse than the curvature constant which does take the simplex geometry of $\mathcal{M}$ into account.

An Affine Invariant Notion of Strong Convexity which Depends on the Geometry of ℳℳ\mathcal{M}.

We now present the affine invariant analog of the strong convexity bound (4), which could be interpreted as the lower curvature $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$ analog of $C_{f}$. The role of $\gamma$ in the definition (19) of $C_{f}$ was to define an affine invariant scale by only looking at proportions over lines (as line segments between $\bm{x}$ and $\bm{s}$ in this case). The trick here is to use anchor points in $\mathcal{A}$ in order to define standard lengths (by looking at proportions on lines). These anchor points ($\bm{s}_{f}(\bm{x})$ and $\bm{v}_{f}(\bm{x})$ defined below) are motivated directly from the FW atom and the away atom appearing in the away-steps FW algorithm. Specifically, let $\bm{x}^{*}$ be a potential optimal point and $\bm{x}$ a non-optimal point; thus we have $\left\langle-\nabla f(\bm{x}),\bm{x}^{*}-\bm{x}\right\rangle>0$ (i.e. $\bm{x}^{*}\!-\!\bm{x}$ is a strict descent direction from $\bm{x}$ for $f$). We then define the positive step-size quantity:

This quantity is motivated from both (6) and the linear rate inequality (5), and enables to transfer lengths from the error $\bm{e}_{t}=\bm{x}^{*}-\bm{x}_{t}$ to the pairwise FW direction $\bm{d}_{t}^{\hskip 0.35002pt\textnormal{PFW}}=\bm{s}_{f}(\bm{x}_{t})-\bm{v}_{f}(\bm{x}_{t})$. More precisely, $\bm{s}_{f}(\bm{x}):=$$~{}\operatorname*{\arg\min}_{\bm{v}\in\mathcal{A}}\left\langle\nabla f(\bm{x}),\bm{v}\right\rangle$ is the standard FW atom. To define the away-atom, we consider all possible expansions of $\bm{x}$ as a convex combination of atoms.As we are working with general polytopes, the expansion of a point as a convex combination of atoms is not necessarily unique. We recall that set of possible active sets is $\mathcal{S}_{\bm{x}}:=\{\mathcal{S}\,|\,\mathcal{S}\subseteq\mathcal{A}$ such that $\bm{x}$ is a proper convex combination of all the elements in $\mathcal{S}\}$. For a given set $\mathcal{S}$, we write $\bm{v}_{\mathcal{S}}(\bm{x}):=\operatorname*{\arg\max}_{\bm{v}\in\mathcal{S}}\left\langle\nabla f(\bm{x}),\bm{v}\right\rangle$ for the away atom in the algorithm supposing that the current set of active atoms is $\mathcal{S}$. Finally, we define $\bm{v}_{f}(\bm{x}):=\displaystyle\operatorname*{\arg\min}_{\{\bm{v}=\bm{v}_{\mathcal{S}}(\bm{x})\,|\,\mathcal{S}\in\mathcal{S}_{\bm{x}}\}}\textstyle\left\langle\nabla f(\bm{x}),\bm{v}\right\rangle$ to be the worst-case away atom (that is, the atom which would yield the smallest away descent).

We then define the geometric strong convexity constant $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$ which depends both on the function $f$ and the domain $\mathcal{M}=\operatorname*{conv}(\mathcal{A})$:

The geometric strong convexity constant $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$, as defined in (22), is affine invariant, since it only depends on the inner products of feasible points with the gradient. Also, it combines both the complexity of the function $f$ and the geometry of the domain $\mathcal{M}$. Theorem 6 allows us to lower bound the constant $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$ in terms of the strong convexity of the objective function, combined with a purely geometric complexity measure of the domain $\mathcal{M}$ (its pyramidal width $\mathop{PW\!idth}(\mathcal{A})$ (9)). In the following Section D below, we will show the linear convergence of the four variants of the FW algorithm presented in this paper under the assumption that $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}>0$.

In view of the following Theorem 6, we have that the condition $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}>0$ is slightly weaker than the strong convexity of the objective functionAs an example of function that is not strongly convex but can still have $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}>0$, consider $f(\bm{x}):=g(\bm{A}\bm{x})$ where $g$ is $\mu_{g}$-strongly convex, but the matrix $\bm{A}$ is rank deficient. Then by using the affine invariance of the definition of $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$ and using Theorem (6) applied on the equivalent problem on $g$ with domain $\operatorname*{conv}(\bm{A}\mathcal{A})$, we get $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}\geq\mu_{g}\cdot(\mathop{PW\!idth}(\bm{A}\mathcal{A}))^{2}>0$. over a polytope domain (it is implied by strong convexity).

Let $f$ be a convex differentiable function and suppose that $f$ is $\mu$-strongly convex w.r.t. to the Euclidean norm $\left\lVert\cdot\right\rVert$ over the domain $\mathcal{M}=\operatorname*{conv}(\mathcal{A})$ with strong-convexity constant $\mu\geq 0$. Then

By definition of strong convexity with respect to a norm, we have that for any $\bm{x},\bm{y}\in\mathcal{M}$,

Using the strong convexity bound (24) with $\bm{y}:=\bm{x}^{*}$ on the right hand side of equation (22) (and using the shorthand $\bm{r}_{\bm{x}}:=-\nabla f(\bm{x})$ ), we thus get:

where $\hat{\bm{e}}(\bm{x}^{*},\bm{x}):=\frac{\bm{x}^{*}-\bm{x}}{\left\lVert\bm{x}^{*}-\bm{x}\right\rVert}$ is the unit length feasible direction from $\bm{x}$ to $\bm{x}^{*}$. We are thus taking an infimum over all possible feasible directions starting from $\bm{x}$ (i.e. which moves within $\mathcal{M}$) with the additional constraint that it makes a positive inner product with the negative gradient $\bm{r}_{\bm{x}}$, i.e. it is a strict descent direction. This is only possible if $\bm{x}$ is not already optimal, i.e. $\bm{x}\in\mathcal{M}\setminus\mathcal{X}^{*}$ where $\mathcal{X}^{*}:=\{\bm{x}^{*}\in\mathcal{M}:\left\langle\bm{r}_{\bm{x}^{*}},\bm{x}-\bm{x}^{*}\right\rangle\leq 0\,\,\forall\bm{x}\in\mathcal{M}\}$ is the set of optimal points.

We note that $\bm{s}_{f}(\bm{x})-\bm{v}_{f}(\bm{x})$ is a valid pairwise FW direction for a specific active set $\mathcal{S}$ for $\bm{x}$, and so we can re-use (12) from Theorem 3 for the right hand side of (25) to conclude the proof. ∎

We now proceed to present the main linear convergence result in the next section, using only the mentioned affine invariant quantities.

Appendix D Linear Convergence Proofs

Because of the additional possibility of the away step in Algorithm 1, we need to define the following slightly modified additional curvature constant, which will be needed for the linear convergence analysis of the algorithm:

By comparing with $C_{f}$ (19), we see that the modification is that $\bm{y}$ is defined with any direction $\bm{s}-\bm{v}$ instead of a standard FW direction $\bm{s}-\bm{x}$. This allows to use the away direction or the pairwise FW direction even though these might yield some $\bm{y}$’s which are outside of the domain $\mathcal{M}$ when using $\gamma>\gamma_{\textnormal{max}}$ (in fact, $\bm{y}\in\mathcal{M}^{\hskip 0.41998pt\textnormal{A}}:=\mathcal{M}+(\mathcal{M}-\mathcal{M})$ in the Minkowski sense). On the other hand, by re-using a similar argument as in [16, Lemma 7], we can obtain the same bound (20) for $C_{f}^{\hskip 0.41998pt\textnormal{A}}$, with the only difference that the Lipschitz constant $L$ for the gradient function has to be valid on $\mathcal{M}^{\hskip 0.41998pt\textnormal{A}}$ instead of just $\mathcal{M}$.

For all pairs of functions $f$ and compact domains $\mathcal{M}$, it holds that $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}\leq C_{f}$ (and $C_{f}\leq C_{f}^{\hskip 0.41998pt\textnormal{A}}$).

Let $\bm{x}$ be a vertex of $\mathcal{M}$, so that $\mathcal{S}=\{\bm{x}\}$. Then $\bm{x}=\bm{v}_{f}(\bm{x})$. Pick $\bm{x}^{*}:=\bm{s}_{f}(\bm{x})$ and substitute in the definition for $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$ (22). Then $\gamma^{\hskip 0.41998pt\textnormal{A}}(\bm{x},\bm{x}^{*})=1$ and so we have $\bm{y}:=\bm{x}^{*}=\bm{x}+\gamma(\bm{x}^{*}-\bm{x})$ with $\gamma=1$ which can also be used in the definition of $C_{f}$ (19). Thus, we have $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}\leq 2\left(f(\bm{y})-f(\bm{x})-\langle\nabla f(\bm{x}),\bm{y}-\bm{x}\rangle\right)\leq C_{f}$. ∎

We now give the global linear convergence rates for the four variants of the FW algorithm: away-steps FW (AFW Algorithm 1); pairwise FW (PFW Algorithm 2); fully-corrective FW (FCFW Algorithm 3 with approximate correction as per Algorithm 4); and Wolfe’s min-norm point algorithm (Algorithm 3 with MNP-correction given in Algorithm 5). For the AFW, MNP and PFW algorithms, we call a drop step when the active set shrinks, i.e. $|S^{(t+1)}|<|S^{(t)}|$. For the PFW algorithm, we also have the possibility of a swap step, where $\gamma_{t}=\gamma_{\textnormal{max}}$ but the size of the active set stays constant $|S^{(t+1)}|=|S^{(t)}|$ (i.e. the mass gets fully swapped from the away atom to the FW atom). We note that a nice property of the FCFW variant is that it does not have any drop steps (it executes both FW steps and away steps simultaneously while guaranteeing enough progress at every iteration).

Suppose that $f$ has smoothness constant $C_{f}^{\hskip 0.41998pt\textnormal{A}}$ ($C_{f}$ for FCFW and MNP), as well as geometric strong convexity constant $\mu_{f}^{\hskip 0.41998pt\textnormal{A}}$ as defined in (22). Then the suboptimality $h_{t}:=f(\bm{x}^{(t)})-f(\bm{x}^{*})$ of the iterates of all the four variants of the FW algorithm decreases geometrically at each step that is not a drop step nor a swap step (i.e. when $\gamma_{t}<\gamma_{\textnormal{max}}$, called a ‘good step’Note that any step with $\gamma_{\textnormal{max}}\geq 1$ can also be considered a ‘good step’, even if $\gamma_{t}=\gamma_{\textnormal{max}}$, as is apparent from the proof. The problematic steps arise only when $\gamma_{\textnormal{max}}\ll 1$.), that is