An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms

Contributions.

We show that the Frank-Wolfe algorithm with away-steps converges linearly (i.e. with a geometric rate) for any strongly convex objective function optimized over a polytope domain, with a constant bounded away from zero that only depends on the geometry of the polytope. Our convergence analysis is affine invariant (both the algorithm and the convergence rate are unaffected by an affine transformation of the variables). Also, 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 [Wol70, GM86, BT04], and the later results [AST08, KY10, AFÑS13] that need Robinson’s condition [Rob82]. 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. As a second contribution, we provide an affine invariant version of the analysis of [GM86] showing that the classical (unmodified) Frank-Wolfe algorithm converges linearly on strongly convex functions when the optimum lies in the interior.

Related Work.

The away-steps variant of the Frank-Wolfe algorithm, that can also remove weight from “bad” ones of the currently active atoms, was proposed in [Wol70], and later also analyzed in [GM86]. The precise algorithm is stated below in Algorithm 1. An alternative away-step algorithm (with a sublinear convergence rate) has been considered by [Cla10], namely performing an away step whenever the number of atoms of non-zero weight has exceeded a fixed target size. The disadvantage of this method is that it requires knowledge of the curvature constant, which is not realistic in many practical applications. For the classical Frank-Wolfe algorithm, the early work of [LP66, Theorem 6.1] has shown a linear convergence rate under the strong requirement that the objective is strongly convex, and furthermore the domain is strongly convex as a set. [BT04] has shown a linear rate for the special case of quadratic objectives when the optimum is in the strict interior of the domain, but their result was already subsumed by [GM86]. More recently [AST08, KY10, AFÑS13] have obtained linear convergence results in the case that the optimum solution satisfies Robinson’s condition [Rob82]. In a different recent line of work, [GH13a, GH13b] has studied an algorithm variationThis can be interpreted as a concrete instantiation of the stronger oracle proposed in [Lan13]. that moves mass from the worst vertices to the “towards” vertex until a specific condition is satisfied, yielding a linear convergence rate. 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.

Frank-Wolfe Algorithms, and Away-Steps

We consider general constrained convex optimization problems of the form

We assume $f$ is convex and differentiable, and that the domain $\mathcal{D}$ is a bounded convex subset of a vector space. The Frank-Wolfe method [FW56], also known as conditional gradient [LP66] works as follows: At a current $\bm{x}^{(k)}$, the algorithm considers the linearization of the objective function, and moves slightly towards a minimizer of this linear function (taken over the same domain). In terms of convergence, it is known that the iterates of Frank-Wolfe satisfy f(\bm{x}^{(k)})-f(\bm{x}^{*})\leq O\big{(}1/k\big{)}, for $\bm{x}^{*}$ being an optimal solution [FW56, DH78, Jag13]. One of the main reasons for the recent increased popularity of Frank-Wolfe-type algorithms is the sparsity of the iterates, i.e. that the iterate is always represented as a sparse convex combination of at most $k$ vertices $\mathcal{S}^{(k)}\subseteq\mathcal{V}$ of the domain $\mathcal{D}$, which we write as $\bm{x}^{(k)}=\sum_{\bm{v}\in\mathcal{S}^{(k)}}\alpha^{(k)}_{\bm{v}}\bm{v}$. Here $\mathcal{V}$ is defined to be the set of vertices (extreme points) of $\mathcal{D}$, so that $\mathcal{D}=\operatorname*{conv}(\mathcal{V})$. We assume that the linear oracle defining $\bm{s}_{k}$ always returns a point from $\mathcal{V}$ as a minimizer.

The away-steps variant of Frank-Wolfe, as stated in Algorithm 1, was proposed in [Wol70], with the idea to also remove weight from “bad” ones of the currently active atoms. Note that the classical Frank-Wolfe algorithm is obtained by only using the FW direction in Algorithm 1. If $\gamma_{k}=\gamma_{\textrm{max}}$, then we call this step a drop step, as it fully removes the vertex $\bm{v}_{k}$ from the currently active set of atoms $\mathcal{S}^{(k)}$. The updates of the algorithm are of the following form: For a FW step, we have $\mathcal{S}^{(k+1)}=\{\bm{s}_{k}\}$ if $\gamma_{k}=1$; otherwise $\mathcal{S}^{(k+1)}=\mathcal{S}^{(k)}\cup\{\bm{s}_{k}\}$. Also, we have $\alpha^{(k+1)}_{\bm{s}_{k}}:=(1-\gamma_{k})\alpha^{(k)}_{\bm{s}_{k}}+\gamma_{k}$ and $\alpha^{(k+1)}_{\bm{v}}:=(1-\gamma_{k})\alpha^{(k)}_{\bm{v}}$ for $\bm{v}\in\mathcal{S}^{(k)}\setminus\{\bm{s}_{k}\}$. For an away step, we have $\mathcal{S}^{(k+1)}=\mathcal{S}^{(k)}\setminus\{\bm{v}_{k}\}$ if $\gamma_{k}=\gamma_{\textrm{max}}$ (a drop step); otherwise $\mathcal{S}^{(k+1)}=\mathcal{S}^{(k)}$. Also, we have $\alpha^{(k+1)}_{\bm{v}_{k}}:=(1+\gamma_{k})\alpha^{(k)}_{\bm{v}_{k}}-\gamma_{k}$ and $\alpha^{(k+1)}_{\bm{v}}:=(1+\gamma_{k})\alpha^{(k)}_{\bm{v}}$ for $\bm{v}\in\mathcal{S}^{(k)}\setminus\{\bm{v}_{k}\}$.

Affine Invariant Measures of Smoothness and Strong Convexity

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{D}$, by a surjective linear or affine map $M:\hat{\mathcal{D}}\rightarrow\mathcal{D}$, then the “old” and “new” optimization problems $\min_{\bm{x}\in\mathcal{D}}f(\bm{x})$ and $\min_{\hat{\bm{x}}\in\hat{\mathcal{D}}}\hat{f}(\hat{\bm{x}})$ for $\hat{f}(\hat{\bm{x}}):=f(M\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 $M$, and the Frank-Wolfe algorithm is affine invariant in the even stronger sense under arbitrary $M$ [Jag13]. (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}=M^{T}\nabla f$.)

Affine Invariant Measures of Smoothness.

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{D}$ with respect to some arbitrary chosen norm $\left\lVert.\right\rVert$, then

where $\operatorname{diam}_{\left\lVert.\right\rVert}(.)$ denotes the $\left\lVert.\right\rVert$-diameter, see [Jag13, Lemma 7]. While the early papers [FW56, Dun79] 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. $C_{f}$ combines the complexity of $\mathcal{D}$ and the curvature of $f$ into a single quantity.

An Affine Invariant Notion of Strong Convexity.

Inspired by the affine invariant curvature measure, one can also define a related affine invariant measure of strong convexity, when combined with the assumption of the optimum $\bm{x}^{*}$ being in the strict interior of $\mathcal{D}$:

Here the point $\overline{\bm{s}}$ is defined to be the point where the ray from $\bm{x}$ to the optimum $\bm{x}^{*}$ pinches the boundary of the set $\mathcal{D}$, i.e. furthest away from $\bm{x}$ while still in $\mathcal{D}$, $\overline{\bm{s}}(\bm{x},\bm{x}^{*},\mathcal{D}):=\textrm{ray}(\bm{x},\bm{x}^{*})\cap\partial\mathcal{D}$. We will later show that this strict interior assumption, which can be very prohibitive, can be removed for the Frank-Wolfe algorithm with away steps, as we explain in Section 4. Clearly, the quantity $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}$ is affine invariant, as it only depends on the inner products of feasible points with the gradient.

For all pairs of functions $f$ and bounded sets $\mathcal{D}$, it holds that $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}\leq C_{f}$.

The following simple lemma gives an interpretation of the very abstract (affine invariant) quantity defined above, in terms of classical norms and strong-convexity properties.

Let $f$ be a convex differentiable function and suppose $f$ is strongly convex w.r.t. some arbitrary norm $\left\lVert.\right\rVert$ over the domain $\mathcal{D}$ with strong-convexity constant $\mu>0$. Furthermore, suppose that the (unique) optimum $x^{*}$ lies in the relative interior of $\mathcal{D}$, i.e. ${\delta_{\bm{x}^{*}\!,\mathcal{D}}}:=\inf_{\bm{s}\in\partial\mathcal{D}}\left\lVert\bm{s}-\bm{x}^{*}\right\rVert>0$. Then

Linear Convergence of Frank-Wolfe

We obtain an affine invariant linear convergence proof for the standard FW algorithm when $f$ is strongly convex and the solution $\bm{x}^{*}$ lies in the relative interior of $\mathcal{D}$ (an improvement over [GM86]).

Suppose that $f$ has smoothness constant $C_{f}$ as defined in (1), as well as “interior” strong convexity constant $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}$ as defined in (3). Then the error of the iterates of the Frank-Wolfe algorithm with step-size $\gamma:=\min\{1,\frac{g_{k}}{C_{f}}\}$ (or using line-search) decreases geometrically, that is

where $\rho_{f}^{\hskip 0.35002pt\textsf{FW}}:=\min\{\frac{1}{2},\frac{\mu_{f}^{\hskip 0.25002pt\textsf{FW}}}{C_{f}}\}$. Here in each iteration, $h_{k}:=f(\bm{x}^{(k)})-f(\bm{x}^{*})$ denotes the primal error, and g_{k}:=g(\bm{x}^{(k)}):=\displaystyle\max_{\bm{s}\in\mathcal{D}}\,\big{\langle}\nabla f(\bm{x}^{(k)}),\bm{x}^{(k)}-\bm{s}\big{\rangle} is the duality gap as defined by [Jag13].

Linear Convergence of Frank-Wolfe with Away-Steps

We now show the linear convergence of FW with away-steps under strong convexity, without any assumption on the location of the optimum with respect to the domain. However, our convergence rate will depend on a purely geometric complexity constant of the domain $\mathcal{D}$, as we show below.

The trick is to use anchor points in the domain 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 away-steps algorithm. Let $\bm{s}_{f}(\bm{x}):=$$~{}\operatorname*{\arg\min}_{\bm{v}\in\mathcal{V}}\left\langle\nabla f(\bm{x}),\bm{v}\right\rangle$ (the standard Frank-Wolfe direction). To define the away-vertex, we consider all possible expansions of $\bm{x}$ as a convex combination of vertices. Let $\mathcal{S}_{\bm{x}}:=\{\mathcal{S}\,|\,\mathcal{S}\subseteq\mathcal{V}$ 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}\}$. 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 vertex in the algorithm supposing that the current set of active vertices was $\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 vertex (that is, the vertex which would yield the smallest away descent).

We can now define the strong convexity constant $\mu_{f}^{\hskip 0.41998pt\textsf{A}}$ which depends both on the function $f$ and the domain $\mathcal{D}$:

Here the positive quantity $\gamma^{\hskip 0.41998pt\textsf{A}}(\bm{x},\bm{x}^{*}):=\frac{\left\langle\nabla f(\bm{x}),\bm{x}^{*}-\bm{x}\right\rangle}{\left\langle\nabla f(\bm{x}),\bm{s}_{f}(\bm{x})-\bm{v}_{f}(\bm{x})\right\rangle}$ plays the role of $\gamma$ in definition (1).

Interpretation.

The above complexity definition is already sufficient for us to prove the linear convergence. Additionally, the constant can be understood in terms of the geometry of $\mathcal{D}$, as follows:

Directional Width.

The directional width of a set $\mathcal{D}$ with respect to a direction $\bm{d}$ (and underlying inner product norm $\left\lVert\cdot\right\rVert$) is defined as \mathop{dirW}(\mathcal{D},\bm{d}):=\max_{\bm{x}\in\mathcal{D}}\big{\langle}\frac{\bm{d}}{\left\lVert\bm{d}\right\rVert_{*}},\bm{x}\big{\rangle}-\min_{\bm{x}\in\mathcal{D}}\big{\langle}\frac{\bm{d}}{\left\lVert\bm{d}\right\rVert_{*}},\bm{x}\big{\rangle}.

Pyramidal Width.

We define the pyramidal directional width of a set $\mathcal{D}$ with respect to a direction $\bm{d}$ and a base point $\bm{x}\in\mathcal{D}$ to be $\mathop{PdirW}(\mathcal{D},\bm{d},\bm{x}):=\min_{\mathcal{S}\in\mathcal{S}_{\bm{x}}}\mathop{dirW}(\mathcal{S}\cup\{\bm{s}(\mathcal{D},\bm{d})\},\;\bm{d})$ where $\bm{s}(\mathcal{D},\bm{d}):=\operatorname*{\arg\max}_{\bm{v}\in\mathcal{D}}\left\langle\bm{d},\bm{v}\right\rangle$. To define the pyramidal width of a set, we take the infimum over a set of possible feasible directions $\bm{d}$ (in order to avoid the problem of zero width). A direction $\bm{d}$ is feasible for $\mathcal{D}$ from $\bm{x}$ if it points inwards the set, (i.e. $\bm{d}\in\text{cone}(\mathcal{D}-\bm{x})$).

We define the pyramidal width of a set $\mathcal{D}$ to be the smallest pyramidal width of all its faces, i.e.

Any curved domain will yield a pyramidal width of zero, because then the set of active atoms $\mathcal{S}_{\bm{x}}$ can contain vertices arbitrary close to the boundary forming a very narrow pyramid. The pyramidal width quantity is thus only useful on polytopes (the convex hull of a finite set of points).

Let $\bm{v}(\bm{x},\bm{d}):=$ the vertex which achieves the minimum in $\min_{\mathcal{S}\in\mathcal{S}_{\bm{x}}}\max_{\bm{v}\in\mathcal{S}}\left\langle\bm{d},-\bm{v}\right\rangle$ for a polytope $\mathcal{K}$ and $\bm{x}\in\mathcal{K}$. Then we have \mathop{PdirW}(\mathcal{K},\bm{d},\bm{x})=\big{\langle}\frac{\bm{d}}{\left\lVert\bm{d}\right\rVert_{*}},\bm{s}(\mathcal{K},\bm{d})-\bm{v}(\bm{x},\bm{d})\big{\rangle}.

Let $f$ be a convex differentiable function and suppose that $f$ is $\mu$-strongly convex w.r.t. some inner product norm $\left\lVert\cdot\right\rVert$ over the domain $\mathcal{D}$ with strong-convexity constant $\mu\geq 0$. Then

Suppose that $f$ has smoothness constant $C_{f}^{\hskip 0.41998pt\textsf{A}}$,For a convenience in the proof, we use a slightly modified curvature constant $C_{f}^{\hskip 0.41998pt\textsf{A}}$, which is identical to the definition of $C_{f}$, except that both positive and negative step-sizes are allowed, i.e. the range of $\gamma$ in the definition for $C_{f}$ is replaced by $$instead of just$$. Note that boundedness of this (again affine invariant) $C_{f}^{\hskip 0.41998pt\textsf{A}}$ is still implied by the Lipschitz continuity of the gradient of $f$ (over the slightly larger domain $\mathcal{D}+\mathcal{D}-\mathcal{D}$, but with the same diameter constant).as well as geometric strong convexity constant $\mu_{f}^{\hskip 0.41998pt\textsf{A}}$ as defined in (4). Then the error of the iterates of the FW algorithm with away-stepsIn the algorithm, one can either use line-search or set the step-size as the feasible one that minimizes the quadratic upper bound given by the curvature $C_{f}^{\hskip 0.41998pt\textsf{A}}$, i.e. $\gamma_{k}:=\min\{1,\gamma_{\textrm{max}},\gamma^{\textrm{B}}_{k}\}$ where $\gamma^{\textrm{B}}_{k}:=\frac{g_{k}}{2C_{f}^{\hskip 0.29999pt\textsf{A}}}$ and $g_{k}:=\langle-\nabla f(\bm{x}^{(k)}),\bm{s}_{k}-\bm{v}_{k}\rangle$. (Algorithm 1) decreases geometrically at each step that is not a drop step (i.e. when $\gamma_{k}<\gamma_{\textrm{max}}$), that is

where $\rho_{f}^{\hskip 0.41998pt\textsf{A}}:=\frac{\mu_{f}^{\hskip 0.29999pt\textsf{A}}}{4C_{f}^{\hskip 0.29999pt\textsf{A}}}$. Moreover, the number of drop steps up to iteration $k$ is bounded by $k/2$. This yields the global linear convergence rate of $h_{k}\leq h_{0}\exp(-\frac{1}{2}\rho_{f}^{\hskip 0.41998pt\textsf{A}}k)$.

Acknowledgements.

Simon Lacoste-Julien acknowledges support by the ERC (SIERRA-ERC-239993). Martin Jaggi acknowledges support by the Simons Institute for the Theory of Computing, by the Swiss National Science Foundation (SNSF), and by the ERC Project SIPA.

References

Appendix A Linear Convergence of Frank-Wolfe for Strongly Convex Functions with Optimum in the Interior

We re-state and interpret the “interior” strong convexity constant $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}$ as defined in (3), that is

Here the point $\overline{\bm{s}}$ is defined to be the point where the ray from $\bm{x}$ to $\bm{x}^{*}$ pinches the boundary of the set $\mathcal{D}$, i.e. $\overline{\bm{s}}(\bm{x},\bm{x}^{*},\mathcal{D}):=\textrm{ray}(\bm{x},\bm{x}^{*})\cap\partial\mathcal{D}$.

Recalling that the curvature $C_{f}$ by definition (1) provides an affine-invariant quadratic upper bound on the function $f$, the strong convexity constant $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}$ here gives rise to an analogous quadratic lower bound, that is

if the point $\bm{y}=\bm{x}+\gamma(\overline{\bm{s}}-\bm{x})$ is determined by the boundary point $\overline{\bm{s}}(\bm{x},\bm{x}^{*},\mathcal{D})$ and an arbitrary step-size $\gamma\in$, i.e., if the point $\bm{y}$ lies on the segment which is between $\bm{x}$ and the boundary of $\mathcal{D}$, and passes through $\bm{x}^{*}$.

Here we prove Lemma 2, which gives a simple geometric interpretation of the abstract (affine invariant) quantity $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}$ defined above, in terms of classical norms and strong-convexity properties.

Let $f$ be a convex differentiable function and suppose $f$ is strongly convex w.r.t. some arbitrary norm $\left\lVert.\right\rVert$ over the domain $\mathcal{D}$ with strong-convexity constant $\mu>0$.

Furthermore, suppose that the (unique) optimum $x^{*}$ lies in the relative interior of $\mathcal{D}$, i.e. ${\delta_{\bm{x}^{*}\!,\mathcal{D}}}:=\inf_{\bm{s}\in\partial\mathcal{D}}\left\lVert\bm{s}-\bm{x}^{*}\right\rVert>0$. Then

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

We want to use this lower bound in the definition (3) of the affine invariant strong convexity constant. Observe that $\frac{1}{\gamma^{2}}\left\lVert\bm{y}-\bm{x}\right\rVert^{2}=\left\lVert\overline{\bm{s}}-\bm{x}\right\rVert^{2}$ for any $\bm{x}$ used in (3) since $\bm{y}:=\bm{x}+\gamma(\overline{\bm{s}}-\bm{x})\in\mathcal{D}$ by convexity. Moreover, by the definition of $\overline{\bm{s}}$ and ${\delta_{\bm{x}^{*}\!,\mathcal{D}}}$, $\left\lVert\overline{\bm{s}}-\bm{x}\right\rVert\geq\left\lVert\overline{\bm{s}}-\bm{x}^{*}\right\rVert\geq{\delta_{\bm{x}^{*}\!,\mathcal{D}}}$. Therefore, we can lower bound $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}$ as

A.2 Convergence Analysis

The definition of the curvature constant $C_{f}$ as in (1) directly gives an affine invariant quadratic upper bound on the objective function, as follows:

Let $\bm{x}_{\gamma}:=\bm{x}+\gamma(\bm{s}-\bm{x})$ be the point obtained by moving with step-size $\gamma$ in direction $\bm{s}\in\mathcal{D}$. By definition of $C_{f}$, we have

This crucial bound enables us to analyze the objective improvement in each iteration in Frank-Wolfe-type algorithms, as in [Jag13]: If the point $\bm{s}$ is the standard Frank-Wolfe direction returned by an exact linear oracle, then the middle quantity is exactly the negative of the duality gap, $\left\langle\nabla f(\bm{x}),\bm{s}-\bm{x}\right\rangle=-g(\bm{x})$. If an inexact linear oracle is used instead, which has multiplicative approximation quality $\nu$ (to be defined below), then we always have the upper bound

Inexact Linear Oracles.

The standard linear oracle used inside the classical Frank-Wolfe algorithm is given by $\bm{s}\in\operatorname*{\arg\min}_{\bm{v}\in\mathcal{D}}\left\langle\nabla f(\bm{x}),\bm{v}\right\rangle$. We say that the linear oracle satisfies multiplicative accuracy $\nu$ for some $\nu\in$, if for any $\bm{x}\in\mathcal{D}$, the returned $\bm{s}$ is such that

Note that the classical Frank-Wolfe direction $\bm{s}$ satisfies this inequality with $\nu=1$. The inequality means that the oracle answer $\bm{s}$ attains at least a $\nu$-fraction of the current duality gap g(\bm{x}):=\displaystyle\max_{\bm{s}\in\mathcal{D}}\,\big{\langle}\nabla f(\bm{x}^{(k)}),\bm{x}-\bm{s}\big{\rangle} as defined by [Jag13].

Related work. The sublinear convergence of Frank-Wolfe with $O(1/k)$ is known to also hold if this linear subproblems are only solved approximately (meaning that the linear oracle is inexact). For additive approximation accuracy, this was shown by [DH78, Dun79] for the line-search case, and by [Jag11, Jag13] for the simpler $\frac{2}{k+2}$ step-size and the primal-dual convergence. For multiplicative accuracy (relative to the duality gap), it was shown by [LJJSP13, Appendix C]. The case of the inexact or noisy gradient information can also be analyzed in the same way, as discussed in [Jag13, FG13].

Linear Convergence Proof.

Here we prove a slightly stronger version of Theorem 3, showing the linear convergence also in the case where the linear subproblems in each iteration are only solved approximately. The exact oracle case is obtained for $\nu:=1$.

Suppose that $f$ has smoothness constant $C_{f}$ as defined in (1), as well as “interior” strong convexity constant $\mu_{f}^{\hskip 0.35002pt\textsf{FW}}$ as defined in (3).

Then the error of the iterates of the Frank-Wolfe algorithm with step-size $\gamma:=\min\{1,\frac{\nu g_{k}}{C_{f}}\}$ (or using line-search) decreases geometrically, that is

where $\rho_{f}^{\hskip 0.35002pt\textsf{FW}}:=\min\{\frac{\nu}{2},\nu^{2}\frac{\mu_{f}^{\hskip 0.25002pt\textsf{FW}}}{C_{f}}\}$. Here in each iteration, $h_{k}:=f(\bm{x}^{(k)})-f(\bm{x}^{*})$ denotes the primal error, and g_{k}:=g(\bm{x}^{(k)}):=\displaystyle\max_{\bm{s}\in\mathcal{D}}\,\big{\langle}\nabla f(\bm{x}^{(k)}),\bm{x}^{(k)}-\bm{s}\big{\rangle} is the duality gap as defined by [Jag13], and $\nu\in$ is the multiplicative approximation quality to which the linear sub-problems are solved.

Applying the strong convexity bound (6) at the current iterate $\bm{x}:=\bm{x}^{(k)}$ for the special step-size $\overline{\gamma}$ such that $\bm{y}=\bm{x}^{(k)}+\overline{\gamma}(\overline{\bm{s}}-\bm{x}^{(k)})=\bm{x}^{*}$ gives

Therefore $h_{k}\leq-\frac{\overline{\gamma}^{2}}{2}\mu_{f}^{\hskip 0.35002pt\textsf{FW}}+\overline{\gamma}g_{k}$, which is upper bounded by $\frac{{g_{k}}^{2}}{2\mu_{f}^{\hskip 0.25002pt\textsf{FW}}}$. (Here we have used the trivial inequality $0\leq a^{2}-2ab+b^{2}$ for the choice of numbers $a:=\frac{g_{k}}{\mu_{f}^{\hskip 0.25002pt\textsf{FW}}}$ and $b:=\overline{\gamma}$)

We now want to use the curvature definition to lower bound the absolute progress $h_{k}-h_{k+1}$. The definition of the curvature $C_{f}$ in the form of the quadratic upper bound (7) reads as $h_{k}-h_{k+1}\geq\gamma\nu g_{k}-\frac{\gamma^{2}}{2}C_{f}$. Using this for the particular step-size $\gamma:=\frac{\nu g_{k}}{C_{f}}$, the r.h.s. is $=\frac{\nu^{2}g_{k}^{2}}{2C_{f}}$. (The border case when $\frac{\nu g_{k}}{C_{f}}>1$ will be discussed separately below). The same inequality also holds in the line-search case, as the improvement only gets better. Combining the two bounds, we have obtained

implying that we have a geometric rate of decrease h_{k+1}\leq\Big{(}1-\nu^{2}\frac{\mu_{f}^{\hskip 0.25002pt\textsf{FW}}}{C_{f}}\Big{)}h_{k}.

Border case. In the above analysis, we have assumed that the step-size $\gamma:=\frac{\nu g_{k}}{C_{f}}\leq 1$. If this is not the case (i.e. if $\nu g_{k}>C_{f}$), then the actual step-size in the algorithm is clipped to $1$, in which case the curvature upper bound (7) for $\gamma:=1$ gives $h_{k}-h_{k+1}~{}\geq~{}\nu g_{k}-\frac{1}{2}C_{f}>\nu g_{k}-\frac{1}{2}\nu g_{k}=\frac{\nu}{2}g_{k}$. Using that the main property $h_{k}\leq g_{k}$ of the duality gap (by convexity), we therefore have $\frac{h_{k}-h_{k+1}}{h_{k}}>\frac{\nu}{2}$, which gives a geometric decrease of the error with constant $1-\frac{\nu}{2}$. ∎

Appendix B Linear Convergence of FW with Away-Steps under Strong Convexity

The geometric strong convexity constant $\mu_{f}^{\hskip 0.41998pt\textsf{A}}$, as defined in (4), 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{D}$. The goal of this subsection is to prove Lemma 6, which provides a geometric interpretation of $\mu_{f}^{\hskip 0.41998pt\textsf{A}}$. The lemma allows us to bound the constant $\mu_{f}^{\hskip 0.41998pt\textsf{A}}$ in terms of the strong convexity of the objective function, combined with a purely geometric complexity measure of the domain $\mathcal{D}$. In the following Section B.2 below, we will show the linear convergence of Algorithm 1 under the assumption that $\mu_{f}^{\hskip 0.41998pt\textsf{A}}>0$. From the view of Lemma 6, $\mu_{f}^{\hskip 0.41998pt\textsf{A}}>0$ is a slightly weaker condition than the strong convexity of the function over a polytope domain (it is implied by strong convexity).

We recall the definition of $\mu_{f}^{\hskip 0.41998pt\textsf{A}}$ as given in (4):

Here the positive quantity $\gamma^{\hskip 0.41998pt\textsf{A}}(\bm{x},\bm{x}^{*}):=\frac{\left\langle\nabla f(\bm{x}),\bm{x}^{*}-\bm{x}\right\rangle}{\left\langle\nabla f(\bm{x}),\bm{s}_{f}(\bm{x})-\bm{v}_{f}(\bm{x})\right\rangle}$ plays the role of $\gamma$ in the analogous upper bound definition (1) for the curvature. We recall that $\bm{s}_{f}(\bm{x}):=\operatorname*{\arg\min}_{\bm{v}\in\mathcal{V}}\left\langle\nabla f(\bm{x}),\bm{v}\right\rangle$ and that $\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$.

We recall the definition of the pyramidal directional width of a set $\mathcal{D}$ with respect to a direction $\bm{d}$ and a base point $\bm{x}\in\mathcal{D}$: $\mathop{PdirW}(\mathcal{D},\bm{d},\bm{x}):=\min_{\mathcal{S}\in\mathcal{S}_{\bm{x}}}\mathop{dirW}(\mathcal{S}\cup\{\bm{s}(\mathcal{D},\bm{d})\},\;\bm{d})$ where $\bm{s}(\mathcal{D},\bm{d}):=\operatorname*{\arg\max}_{\bm{v}\in\mathcal{D}}\left\langle\bm{d},\bm{v}\right\rangle$. We now provide a proof of Remark 5, which will be useful at the end of the proof of Lemma 6.

Let $\bm{v}(\bm{x},\bm{d}):=$ the vertex which achieves the minimizer of $\min_{\mathcal{S}\in\mathcal{S}_{\bm{x}}}\max_{\bm{v}\in\mathcal{S}}\left\langle\bm{d},-\bm{v}\right\rangle$ for a polytope $\mathcal{K}$ and $\bm{x}\in\mathcal{K}$. Then we have

Finally, we introduce a final concept that will be useful in the proof. We say that a direction $\bm{d}$ exposes a facetAs a reminder, we define a k-face of $\mathcal{D}$ (a $k$-dimensional face of $\mathcal{D}$) a set $\mathcal{K}$ such that $\mathcal{K}=\mathcal{D}\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{D}$ 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{D}$. $k$ is the dimensionality of the affine hull of $\mathcal{K}$. We call a $k$-face of dimensions $k=0$, $1$, $\textrm{dim}(\mathcal{D})-2$ and $\textrm{dim}(\mathcal{D})-1$ a vertex, edge, ridge and facet respectively. $\mathcal{D}$ is a $k$-face of itself with $k=\textrm{dim}(\mathcal{D})$. See definition 2.1 in [Zie95]. $\mathcal{F}$ of the polytope $\mathcal{D}$ at $\bm{x}$ if 1) $\mathcal{F}$ includes $\bm{x}$ and is a facet of $\mathcal{D}$; and 2) the orthogonal component of $\bm{d}$ to this facet defines this facet with $\bm{d}$ on one side and $\mathcal{D}-\bm{x}$ on the other side. In other words, let $\mathcal{F}_{\bm{s}}:=\textrm{span}(\mathcal{D}-\bm{x})$ be the affine hull of $\mathcal{F}$ re-centered at $\bm{x}$; let $\bm{P}_{\mathcal{F}_{\bm{s}}}$ be the orthogonal projection operator onto $\mathcal{F}_{\bm{s}}$; then the second condition can be expressed as $\mathcal{F}=\{\bm{y}\in\mathcal{D}:\left\langle(\mathbf{I}-\bm{P}_{\mathcal{F}_{\bm{s}}})\bm{d},\bm{y}-\bm{x}\right\rangle=0\}$ and $\left\langle(\mathbf{I}-\bm{P}_{\mathcal{F}_{\bm{s}}})\bm{d},\bm{y}-\bm{x}\right\rangle\leq 0$ $\forall\bm{y}\in\mathcal{D}$ (note that $(\mathbf{I}-\bm{P}_{\mathcal{F}_{\bm{s}}})\bm{d}$ is the orthogonal component of $\bm{d}$ to the facet $\mathcal{F}$). Note that these conditions imply that $\bm{d}$ cannot be a feasible direction, i.e. $\bm{d}\notin\textrm{cone}(\mathcal{D}-\bm{x})$ and that $\bm{x}$ must be on the (relative) boundary of $\mathcal{D}$. It turns out that the converse is also true: if $\bm{d}\notin\textrm{cone}(\mathcal{D}-\bm{x})$, then there must exist at least a facet of $\mathcal{D}$ exposed by $\bm{d}$ at $\bm{x}$.To find such an exposed facet, consider the $\mathcal{H}$-polyhedron representation of $\textrm{cone}(\mathcal{D}-\bm{x})$ (see [Zie95]). As $\bm{d}$ is not feasible, at least one halfspace constraint must be violated; the intersection of the hyperplane determining this halfspace constraint with $\mathcal{D}-\bm{x}$ yields (the translation of) one exposed facet.

Let $f$ be a convex differentiable function and suppose that $f$ is $\mu$-strongly convex w.r.t. some inner product norm $\left\lVert\cdot\right\rVert$ over the domain $\mathcal{D}$ 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{D}$,

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

where $\hat{\bm{r}}_{\bm{x},\bm{x}^{*}}:=\frac{\bm{x}^{*}-\bm{x}}{\left\lVert\bm{x}^{*}-\bm{x}\right\rVert}$ is the unit norm 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{D}$) 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{D}\setminus\mathcal{X}^{*}$ where $\mathcal{X}^{*}:=\{\bm{x}^{*}\in\mathcal{D}:\left\langle\bm{r}_{\bm{x}^{*}},\bm{x}-\bm{x}^{*}\right\rangle\leq 0\,\,\forall\bm{x}\in\mathcal{D}\}$ is the set of optimal points. [NOTE: I know that by strong convexity it only contains one point; but I wanted to keep it general here just to see the effect of the constraints and to get more intuition about the constants].

In the other possibility ($\bm{d}_{0}\notin\text{cone}(\mathcal{K}_{0})$), then there must exist a least one facet $\mathcal{K}_{1}$ of $\mathcal{K}_{0}$ that is exposed by $\bm{d}_{0}$ at $\mathbf{0}$ (note that we cannot have $\bm{d}_{0}=\mathbf{0}$ since $\bm{x}\notin\mathcal{X}^{*}$). We now project $\bm{d}_{0}$ on $\text{span}(\mathcal{K}_{1})$: $\bm{d}_{1}:=\bm{P}_{1}\bm{d}_{0}$, and we show how the lower bound transforms. This yields the following inequalities:

From the first to the second line, we used the fact that $\left\langle\bm{r}_{\bm{x}}-\bm{d}_{0},\bm{y}\right\rangle=0$ for any $\bm{y}\in\mathcal{K}_{0}=\mathcal{D}-\bm{x}$ as $\bm{d}_{0}$ is the orthogonal projection of $\bm{r}_{\bm{x}}$ on $\mathcal{C}_{0}=\text{span}(\mathcal{K}_{0})$ (and thus we also have that $\left\langle\bm{r}_{\bm{x}},\bm{s}_{f}(\bm{x})-\bm{x}\right\rangle=\left\langle\bm{d}_{0},\bm{s}(\mathcal{K}_{0},\bm{d}_{0})\right\rangle$). To go from the second to the third line, we use the fact that the first term yields an inequality as $\mathcal{K}_{1}\subseteq\mathcal{K}_{0}$. Also, let $\mathcal{K}_{\bm{x}}$ be the minimal dimensional face of $\mathcal{D}$ containing $\bm{x}$ (and thus $\bm{x}$ is in the relative interior of $\mathcal{K}_{\bm{x}}$). Note that $\bigcup\mathcal{S}_{\bm{x}}=\text{vertices}(\mathcal{K}_{\bm{x}})$, and also that $\mathcal{K}_{\bm{x}}$ is included in any other face containing $\bm{x}$. We thus have $\mathcal{S}\subseteq\mathcal{K}_{1}+\bm{x}$ for any $\mathcal{S}\in\mathcal{S}_{\bm{x}}$ and thus the second term on the second line yielded an equality. The fourth line used the fact that $\bm{d}_{0}-\bm{d}_{1}$ is orthogonal to members of $\mathcal{K}_{1}$. The fifth line used the definition of $\bm{s}(\mathcal{K}_{1},\bm{d}_{1})$ and introduced the notation $\bm{v}(\bm{x},\bm{d}):=$ the vertex $\bm{v}\in\mathcal{K}_{\bm{x}}$ which achieves the minimizer of $\min_{\mathcal{S}\in\mathcal{S}_{\bm{x}}}\max_{\bm{v}\in\mathcal{S}}\left\langle\bm{d},-\bm{v}\right\rangle$.

To deal with $\left\langle\bm{r}_{\bm{x}},\hat{\bm{r}}_{\bm{x},\bm{x}^{*}}\right\rangle=\left\langle\bm{d}_{0},\hat{\bm{r}}_{\bm{x},\bm{x}^{*}}\right\rangle$, we use the crucial fact that $\bm{d}_{0}$ exposes the facet $\mathcal{K}_{1}$ of $\mathcal{K}_{0}$. This implies that $\left\langle\bm{d}_{0}-\bm{P}_{0}\bm{d}_{0},\hat{\bm{r}}_{\bm{x},\bm{x}^{*}}\right\rangle\leq 0$ for all $\bm{x}^{*}-\bm{x}\in\mathcal{K}_{0}\setminus\{\mathbf{0}\}$. So consider $\bm{r}_{0}:=\displaystyle\operatorname*{\arg\max}_{\begin{subarray}{c}\bm{y}\in\mathcal{K}_{0}\\ \left\langle\bm{d}_{0},\bm{y}\right\rangle>0\end{subarray}}\left\langle\bm{d}_{0},\frac{\bm{y}}{\left\lVert\bm{y}\right\rVert}\right\rangle$. We claim that we can choose $\bm{r}_{0}\in\mathcal{K}_{1}$. To see this, let $\bm{r}_{1}=\bm{P}_{1}\bm{r}_{0}$ and write $\bm{r}_{1}^{\perp}=\bm{r}_{0}-\bm{r}_{1}$ and $\bm{d}_{1}^{\perp}=\bm{d}_{0}-\bm{d}_{1}$. Then we have:

Note that in the third line, we have used that $\left\lVert\bm{r}_{1}\right\rVert=\left\lVert\bm{P}_{1}\bm{r}_{0}-\bm{P}_{1}\mathbf{0}\right\rVert\leq\left\lVert\bm{r}_{0}-\mathbf{0}\right\rVert$ by the contraction property of the orthogonal projection for inner product norms.The contraction property is only valid for inner product norms (i.e. $\left\lVert\cdot\right\rVert=\sqrt{\left\langle\cdot,\cdot\right\rangle}$), so this is where the assumption that the norm was generated by an inner product comes into play. In the last line, we have an equality instead of the $\leq$ inequality as $\left\langle\bm{d}_{1},\bm{y}\right\rangle=\left\langle\bm{d}_{0},\bm{y}\right\rangle$ $\forall\bm{y}\in\mathcal{K}_{1}$ and $\mathcal{K}_{1}\subseteq\mathcal{K}_{0}$, and so we also have the $\geq$ direction. Combining the facts from (12) and (13), we get in this case:

We are now back to a similar situation as before, but with $\mathcal{K}_{1}$ instead of $\mathcal{K}_{0}$ as the reference polytope. Note that by the third line of (13), we have $\left\langle\bm{d}_{1},\bm{r}_{1}\right\rangle\geq\left\langle\bm{d}_{0},\bm{r}_{0}\right\rangle>0$ and thus $\bm{d}_{1}\neq\mathbf{0}$ (which is crucial to avoid a trivial lower bound of zero). So again, we consider whether $\bm{d}_{1}\in\text{cone}(\mathcal{K}_{1})$. If $\bm{d}_{1}\in\text{cone}(\mathcal{K}_{1})$, we stop here with $\bm{d}=\bm{d}_{1}$ and $\mathcal{K}=\mathcal{K}_{1}$. By Cauchy-Schwartz, we again have $\displaystyle\max_{\begin{subarray}{c}\bm{y}\in\mathcal{K}\\ \left\langle\bm{d},\bm{y}\right\rangle>0\end{subarray}}\left\langle\bm{d},\frac{\bm{y}}{\left\lVert\bm{y}\right\rVert}\right\rangle\leq\left\lVert\bm{d}\right\rVert_{*}$, and so we conclude

where $\bm{d}\in\text{cone}(\mathcal{K})\setminus\{\mathbf{0}\}$.

If $\bm{d}_{1}\notin\text{cone}(\mathcal{K}_{1})$, then we continue our iterative process: we get that $\bm{d}_{1}$ exposes a facet $\mathcal{K}_{2}$ of $\mathcal{K}_{1}$. We thus project $\bm{d}_{1}$ on $\mathcal{K}_{2}$ to get $\bm{d}_{2}=\bm{P}_{2}\bm{d}_{1}$. We can repeat exactly the same argument as before to get (12) and (13) with $\bm{d}_{2}$ and $\mathcal{K}_{2}$ in place of $\bm{d}_{1}$ and $\mathcal{K}_{1}$ (and $\bm{d}_{2}\neq\mathbf{0}$). If $\bm{d}_{2}\in\text{cone}(\mathcal{K}_{2})$, then we stop with $\bm{d}=\bm{d}_{2}$ and $\mathcal{K}=\mathcal{K}_{2}$ and we again get the inequality (14). Otherwise, we get an exposed facet $\mathcal{K}_{3}$, and repeat the process with $\bm{d}_{3}=\bm{P}_{3}\bm{d}_{2}$. This process must stop at some point $l$: at the latest, we will reach $\mathcal{K}_{l}=\mathcal{K}_{\bm{x}}-\bm{x}$, the minimal dimensional face containing $\mathbf{0}$. In this case we must have $\bm{d}_{l}\in\text{cone}(\mathcal{K}_{l})$ as $\mathbf{0}$ is in the relative interior of $\mathcal{K}_{l}$ for a minimal face and so all directions are feasible. We also note that $\bm{d}_{l}\neq\mathbf{0}$ by the argument in (13) that implies $\left\langle\bm{d}_{l},s(\mathcal{K}_{l},\bm{d}_{l})\right\rangle>0$ (this condition is crucial to avoid having a lower bound of zero!). The latter also implies that the dimensionality of $\mathcal{K}_{l}$ must at least be 1. Letting again $\bm{d}=\bm{d}_{l}$ and $\mathcal{K}=\mathcal{K}_{l}$, we get inequality (14) with $\bm{d}\in\text{cone}(\mathcal{K})\setminus\{\mathbf{0}\}$.

For the last inequality, we used (9) from Remark 5. Combining this statement with (11) concludes the proof. ∎

B.2 Linear Convergence Proof

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 algorithmThis can be avoided if the algorithm uses the step-size that minimizes a quadratic upper bound (see the proof for Theorem 7; we can actually use $\gamma_{k}:=\min\{1,\gamma_{\textrm{max}},\frac{g_{k}}{2C_{f}}\}$); but then one needs to compute an upper bound on $C_{f}$ to run the algorithm (which is not always easy). Moreover, this algorithm might have less chance to get the ‘best case’ behavior by being less adaptive.:

By comparing with $C_{f}$ (1), we see that the modification is that $\bm{y}$ is defined with the away direction $\bm{x}-\bm{s}$ instead of a standard FW direction $\bm{s}-\bm{x}$. This might yield some $\bm{y}$’s which are outside of the domain $\mathcal{D}$ (in fact, $\bm{y}\in\mathcal{D}^{\hskip 0.41998pt\textsf{A}}:=\mathcal{D}+(\mathcal{D}-\mathcal{D})$ in the Minkowski sense). On the other hand, by re-using a similar argument as in [Jag13, Lemma 7], we can obtain the same bound (2) for $C_{f}^{-}$, with the only difference that the Lipschitz constant $L$ for the gradient function has to be valid on $\mathcal{D}^{\hskip 0.41998pt\textsf{A}}$ instead of just $\mathcal{D}$. Finally, the curvature constant for Algorithm 1 is simply the worst-case possibility between the standard FW steps and the away steps:

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

Choose $\bm{x}^{*}:=\bm{s}_{f}(\bm{x})$ for an $\bm{x}$ that is an away corner (i.e. $\bm{x}=\bm{v}_{f}(\bm{x})$) in (4). Then $\gamma^{\hskip 0.41998pt\textsf{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}$. Thus, we have $\mu_{f}^{\hskip 0.41998pt\textsf{A}}\leq f(\bm{y})-f(\bm{x})-\langle\nabla f(\bm{x}),\bm{y}-\bm{x}\rangle\leq C_{f}$. ∎

Suppose that $f$ has smoothness constant $C_{f}^{\hskip 0.41998pt\textsf{A}}$ as defined in (16), as well as geometric strong convexity constant $\mu_{f}^{\hskip 0.41998pt\textsf{A}}$ as defined in (4). Then the error of the iterates of the FW algorithm with away-stepsIn the algorithm, one can either use line-search or set the step-size as the feasible one that minimizes the quadratic upper bound given by the curvature $C_{f}$, i.e. $\gamma_{k}:=\min\{1,\gamma_{\textrm{max}},\gamma^{\textrm{B}}_{k}\}$ where $\gamma^{\textrm{B}}_{k}:=\frac{g_{k}}{2C_{f}^{\hskip 0.29999pt\textsf{A}}}$ and $g_{k}:=\langle-\nabla f(\bm{x}^{(k)}),\bm{s}_{k}-\bm{v}_{k}\rangle$. (Algorithm 1) decreases geometrically at each step that is not a drop step (i.e. when $\gamma_{k}<\gamma_{\textrm{max}}$), that is

where $\rho_{f}^{\hskip 0.41998pt\textsf{A}}:=\frac{\mu_{f}^{\hskip 0.29999pt\textsf{A}}}{4C_{f}^{\hskip 0.29999pt\textsf{A}}}$. Moreover, the number of drop steps up to iteration $k$ is bounded by $k/2$. This yields the global linear convergence rate of $h_{k}\leq h_{0}\exp(-\frac{1}{2}\rho_{f}^{\hskip 0.41998pt\textsf{A}}k)$.

The general idea of the proof is to use the definition of the geometric strong convexity constant to upper bound $h_{k}$, while using the definition of the curvature constant $C_{f}^{\hskip 0.41998pt\textsf{A}}$ to lower bound the decrease in primal suboptimality $h_{k}-h_{k+1}$ for the ‘good steps’ of Algorithm 1. Then we upper bound the number of ‘bad steps’ (the drop steps).

Upper bounding $h_{k}$. In the whole proof, we assume that $\bm{x}^{(k)}$ is not already optimal, i.e. that $h_{k}>0$. If $h_{k}=0$, then because line-search is used, we will have $h_{k+1}\leq h_{k}=0$ and so the geometric rate of decrease is trivially true in this case.If the fixed schedule step-size is used, $h_{k}=0$ implies that $g_{k}=0$ and so $\gamma_{k}=0$ and thus $h_{k+1}=h_{k}$. Let $\bm{x}^{*}$ be an optimum point (which is not necessarily unique). As $h_{k}>0$, we have that $\left\langle\nabla f(\bm{x}^{(k)}),\bm{x}^{*}-\bm{x}^{(k)}\right\rangle<0$. We can thus apply the geometric strong convexity bound (4) at the current iterate $\bm{x}:=\bm{x}^{(k)}$ using $\bm{x}^{*}$ as an optimum reference point to get (with $\overline{\gamma}:=\gamma^{\hskip 0.41998pt\textsf{A}}(\bm{x}^{(k)},\bm{x}^{*})$):

where we define $g_{k}:=\left\langle-\nabla f(\bm{x}^{(k)}),\bm{s}_{k}-\bm{v}_{k}\right\rangle$ (note that $h_{k}\leq g_{k}$ and so $g_{k}$ also gives a primal suboptimality certificate). For the third line, we have used the definition of $\bm{v}_{f}(\bm{x})$ which implies $\left\langle\nabla f(\bm{x}^{(k)}),\bm{v}_{f}(\bm{x}^{(k)})\right\rangle\leq\left\langle\nabla f(\bm{x}^{(k)}),\bm{v}_{k}\right\rangle$. Therefore $h_{k}\leq-\frac{{\overline{\gamma}}^{2}}{2}\mu_{f}^{\hskip 0.41998pt\textsf{A}}+\overline{\gamma}g_{k}$, which is always upper boundedHere we have used the trivial inequality $0\leq a^{2}-2ab+b^{2}$ for the choice of numbers $a:=\frac{g_{k}}{\mu_{f}^{\hskip 0.29999pt\textsf{A}}}$ and $b:=\overline{\gamma}$.o by $\frac{{g_{k}}^{2}}{2\mu_{f}^{\hskip 0.29999pt\textsf{A}}}$:

Lower bounding progress $h_{k}-h_{k+1}$. A key aspect of the proof is to use the following observation: because of the way the direction $\bm{d}_{k}$ is chosen in Algorithm 1, we have

and thus $g_{k}$ characterizes the quality of the direction $\bm{d}_{k}$. To see this, note that $2\left\langle\nabla f(\bm{x}^{(k)}),\bm{d}_{k}\right\rangle\leq\left\langle\nabla f(\bm{x}^{(k)}),\bm{d}_{k}^{\hskip 0.35002pt\textsf{FW}}\right\rangle+\left\langle\nabla f(\bm{x}^{(k)}),\bm{d}_{k}^{\hskip 0.41998pt\textsf{A}}\right\rangle=\left\langle\nabla f(\bm{x}^{(k)}),\bm{d}_{k}^{\hskip 0.35002pt\textsf{FW}}+\bm{d}_{k}^{\hskip 0.41998pt\textsf{A}}\right\rangle=-g_{k}$.

We first consider the case $\gamma_{\textrm{max}}\geq 1$. Let $\bm{x}_{\gamma}:=\bm{x}^{(k)}+\gamma\bm{d}_{k}$ be the point obtained by moving with step-size $\gamma$ in direction $\bm{d}_{k}$, where $\bm{d}_{k}$ is the one chosen by Algorithm 1. By using $\bm{s}:=\bm{x}^{(k)}+\bm{d}_{k}$ (a feasible point as $\gamma_{\textrm{max}}\geq 1$), $\bm{x}:=\bm{x}^{(k)}$ and $\bm{y}:=\bm{x}_{\gamma}$ in the definition of the curvature constant $C_{f}$ (1), and solving for $f(\bm{x}_{\gamma})$, we get $f(\bm{x}_{\gamma})\leq f(\bm{x}^{(k)})+\gamma\left\langle\nabla f(\bm{x}^{(k)}),\bm{d}_{k}\right\rangle+\frac{\gamma^{2}}{2}C_{f}$, valid $\forall\gamma\in$. As $\gamma_{k}$ is obtained by line search and that $\subseteq[0,\gamma_{\textrm{max}}]$, we also have that $f(\bm{x}^{(k+1)})=f(\bm{x}_{\gamma_{k}})\leq f(\bm{x}_{\gamma})$ $\forall\gamma\in$. Combining these two inequalities, subtracting $f(\bm{x}^{*})$ on both sides, and using $C_{f}\leq C_{f}^{\hskip 0.41998pt\textsf{A}}$ to simplify the possibilities yields $h_{k+1}\leq h_{k}+\gamma\left\langle\nabla f(\bm{x}^{(k)}),\bm{d}_{k}\right\rangle+\frac{\gamma^{2}}{2}C_{f}^{\hskip 0.41998pt\textsf{A}}$.

Using the crucial gap inequality (18), we get $h_{k+1}\leq h_{k}-\gamma\frac{g_{k}}{2}+\frac{\gamma^{2}}{2}C_{f}^{\hskip 0.41998pt\textsf{A}}$, and so:

We can minimize the bound (19) on the right hand side by letting $\gamma=\gamma^{\textrm{B}}_{k}:=\frac{g_{k}}{2C_{f}^{\hskip 0.29999pt\textsf{A}}}$ – supposing that $\gamma^{\textrm{B}}_{k}\leq 1$, we then get $h_{k}-h_{k+1}\geq\frac{g_{k}^{2}}{8C_{f}^{\hskip 0.29999pt\textsf{A}}}$ (we cover the case $\gamma^{\textrm{B}}_{k}>1$ later). By combining this inequality with the one from geometric strong convexity (17), we get

implying that we have a geometric rate of decrease h_{k+1}\leq\Big{(}1-\frac{\mu_{f}^{\hskip 0.29999pt\textsf{A}}}{4C_{f}^{\hskip 0.29999pt\textsf{A}}}\Big{)}h_{k} (this is a ‘good step’).

Boundary cases. We now consider the case $\gamma^{\textrm{B}}_{k}>1$ (with $\gamma_{\textrm{max}}\geq 1$ still). The condition $\gamma^{\textrm{B}}_{k}>1$ then translates to $g_{k}\geq 2C_{f}^{\hskip 0.41998pt\textsf{A}}$, which we can use in (19) with $\gamma=1$ to get $h_{k}-h_{k+1}\geq\frac{g_{k}}{2}-\frac{g_{k}}{4}=\frac{g_{k}}{4}$. Combining this inequality with $h_{k}\leq g_{k}$ gives the geometric decrease $h_{k+1}\leq\left(1-\frac{1}{4}\right)h_{k}$ (also a ‘good step’). $\rho_{f}^{\hskip 0.41998pt\textsf{A}}$ is obtained by considering the worst-case of the constants obtained from $\gamma^{\textrm{B}}_{k}>1$ and $\gamma^{\textrm{B}}_{k}\leq 1$. (Note that always $\mu_{f}^{\hskip 0.41998pt\textsf{A}}\leq C_{f}^{\hskip 0.41998pt\textsf{A}}$ by definition, as discussed in Remark 8).

Finally, we are left with the case that $\gamma_{\textrm{max}}<1$. This is thus an away step and so $\bm{d}_{k}=\bm{d}_{k}^{\hskip 0.41998pt\textsf{A}}=\bm{x}^{(k)}-\bm{v}_{k}$. Here, we use the away version $C_{f}^{-}$ of the definition for $C_{f}^{\hskip 0.41998pt\textsf{A}}$: by letting $\bm{s}:=\bm{v}_{k}$, $\bm{x}:=\bm{x}^{(k)}$ and $\bm{y}:=\bm{x}_{\gamma}$ in (15), we also get the bound $f(\bm{x}_{\gamma})\leq f(\bm{x}^{(k)})+\gamma\left\langle\nabla f(\bm{x}^{(k)}),\bm{d}_{k}\right\rangle+\frac{\gamma^{2}}{2}C_{f}^{\hskip 0.41998pt\textsf{A}}$, valid $\forall\gamma\in$ (but note here that the points $\bm{x}_{\gamma}$ are not feasible for $\gamma>\gamma_{\textrm{max}}$ – the bound considers some points outside of $\mathcal{D}$). We now have two options: either $\gamma_{k}=\gamma_{\textrm{max}}$ (a drop step) or $\gamma_{k}<\gamma_{\textrm{max}}$. In the case $\gamma_{k}<\gamma_{\textrm{max}}$ (the line-search yields a solution in the interior of $[0,\gamma_{\textrm{max}}]$), then because $f(\bm{x}_{\gamma})$ is convex in $\gamma$, we know that $\min_{\gamma\in[0,\gamma_{\textrm{max}}]}f(\bm{x}_{\gamma})=\min_{\gamma\geq 0}f(\bm{x}_{\gamma})$ and thus $\min_{\gamma\in[0,\gamma_{\textrm{max}}]}f(\bm{x}_{\gamma})=f(\bm{x}^{(k+1)})\leq f(\bm{x}_{\gamma})$ $\forall\gamma\in$. We can then re-use the same argument above equation (19) to get the inequality (19), and again considering both the case $\gamma^{\textrm{B}}_{k}\leq 1$ (which yields inequality (20)) and the case $\gamma^{\textrm{B}}_{k}>1$ (which yields $(1-\frac{1}{4})$ as the geometric rate constant), we get a ‘good step’ with $1-\rho_{f}^{\hskip 0.41998pt\textsf{A}}$ as the worst-case geometric rate constant.

Finally, we can easily bound the number of drop steps possible up to iteration $k$ with the following argument (the drop steps are the ‘bad steps’ for which we cannot show good progress). Let $A_{k}$ be the number of steps that added a vertex in the expansion (only standard FW steps can do this) and let $D_{k}$ be the number of drop steps. We have that $|\mathcal{S}^{(k)}|=|\mathcal{S}^{(0)}|+A_{k}-D_{k}$. Moreover, we have that $A_{k}+D_{k}\leq k$. We thus have $1\leq|\mathcal{S}^{(k)}|\leq|\mathcal{S}^{(0)}|+k-2D_{k}$, implying that $D_{k}\leq\frac{1}{2}(|\mathcal{S}^{(0)}|-1+k)=\frac{k}{2}$, as stated in the theorem. ∎