New Analysis and Results for the Frank-Wolfe Method

Introduction

The use and analysis of first-order methods in convex optimization has gained a considerable amount of attention in recent years. For many applications – such as LASSO regression, boosting/classification, matrix completion, and other machine learning problems – first-order methods are appealing for a number of reasons. First, these problems are often very high-dimensional and thus, without any special structural knowledge, interior-point methods or other polynomial-time methods are unappealing. Second, optimization models in many settings are dependent on data that can be noisy or otherwise limited, and it is therefore not necessary or even sensible to require very high-accuracy solutions. Thus the weaker rates of convergence of first-order methods are typically satisfactory for such applications. Finally, first-order methods are appealing in many applications due to the lower computational burden per iteration, and the structural implications thereof. Indeed, most first-order methods require, at each iteration, the computation of an exact, approximate, or stochastic (sub)gradient and the computation of a solution to a particular “simple” subproblem. These computations typically scale well with the dimension of the problem and are often amenable to parallelization, distributed architectures, efficient management of sparse data-structures, and the like.

The first set of contributions in this paper concern computational guarantees for arbitrary step-size sequences. In Section 2, we present a new complexity analysis of the Frank-Wolfe method wherein we derive an exact functional dependence of the complexity bound at iteration $k$ as a function of the step-size sequence $\{\bar{\alpha}_{k}\}$. We derive bounds on the deviation from the optimal objective function value (and on the duality gap in the presence of minmax structure), and on the so-called FW gaps, which may be interpreted as specially structured duality gaps. In Section 3, we use the technical theorems developed in Section 2 to derive computational guarantees for a variety of simple step-size rules including the well-studied step-size rule $\bar{\alpha}_{k}:=\frac{2}{k+2}$, simple averaging, and constant step-sizes. Our analysis retains the well-known optimal $O(\frac{1}{k})$ rate (optimal for linear optimization oracle-based methods , following also from ) when the step-size is either given by the rule $\bar{\alpha}_{k}:=\frac{2}{k+2}$ or is determined by a line-search. We also derive an $O\left(\frac{\ln(k)}{k}\right)$ rate for both the case when the step-size is given by simple averaging and in the case when the step-size is simply a suitably chosen constant.

The second set of contributions in this paper concern “warm-start” step-size rules and associated computational guarantees that reflect the the quality of the given initial iterate. The $O(\frac{1}{k})$ computational guarantees associated with the step-size sequence $\bar{\alpha}_{k}:=\frac{2}{k+2}$ are independent of quality of the initial iterate. This is good if the objective function value of the initial iterate is very far from the optimal value, as the computational guarantee is independent of the poor quality of the initial iterate. But if the objective function value of the initial iterate is moderately close to the optimal value, one would want the Frank-Wolfe method, with an appropriate step-size sequence, to have computational guarantees that reflect the closeness to optimality of the initial objective function value. In Section 4, we introduce a modification of the $\bar{\alpha}_{k}:=\frac{2}{k+2}$ step-size rule that incorporates the quality of the initial iterate. Our new step-size rule maintains the $O(\frac{1}{k})$ complexity bound but now the bound is enhanced by the quality of the initial iterate. We also introduce a dynamic version of this warm start step-size rule, which dynamically incorporates all new bound information at each iteration. For the dynamic step-size rule, we also derive a $O(\frac{1}{k})$ complexity bound that depends naturally on all of the bound information obtained throughout the course of the algorithm.

The third set of contributions concern computational guarantees in the presence of approximate computation of gradients and linear optimization subproblem solutions. In Section 5, we first consider a variation of the Frank-Wolfe method where the linear optimization subproblem at iteration $k$ is solved approximately to an (additive) absolute accuracy of $\delta_{k}$. We show that, independent of the choice of step-size sequence $\{\bar{\alpha}_{k}\}$, the Frank-Wolfe method does not suffer from an accumulation of errors in the presence of approximate subproblem solutions. We extend the “technical” complexity theorems of Section 2, which imply, for instance, that when an optimal step-size such as $\bar{\alpha}_{k}:=\frac{2}{k+2}$ is used and the $\{\delta_{k}\}$ accuracy sequence is a constant $\delta$, then a solution with accuracy $O(\frac{1}{k}+\delta)$ can be achieved in $k$ iterations. We next examine variations of the Frank-Wolfe method where exact gradient computations are replaced with inexact gradient computations, under two different models of inexact gradient computations. We show that all of the complexity results under the previously examined approximate subproblem solution case (including, for instance, the non-accumulation of errors) directly apply to the case where exact gradient computations are replaced with the $\delta$-oracle approximate gradient model introduced by d’Aspremont . We also examine replacing exact gradient computations with the $(\delta,L)$-oracle model introduced by Devolder et al. . In this case the Frank-Wolfe method suffers from an accumulation of errors under essentially any step-size sequence $\{\bar{\alpha}_{k}\}$. These results provide some insight into the inherent tradeoffs faced in choosing among several first-order methods.

The Frank-Wolfe Method

We recall the Frank-Wolfe method for convex optimization, see Frank and Wolfe , also Demyanov and Rubinov , Levitin and Polyak , and Polyak , stated here for maximization problems:

As a consequence of solving the linear optimization problem in step (2.) of the method, one conveniently obtains the following upper bound on the optimal value $h^{*}$ of (1):

and it follows from the fact that the linearization of $h(\cdot)$ at $\lambda_{k}$ dominates $h(\cdot)$ that $B^{w}_{k}$ is a valid upper bound on $h^{*}$. We also study the quantity $G_{k}$ :

which we refer to as the “FW gap” at iteration $k$ for convenience. Note that $G_{k}\geq h^{\ast}-h(\lambda_{k})\geq 0$. The use of the upper bound $B^{w}_{k}$ dates to the original 1956 paper of Frank and Wolfe . As early as 1970, Demyanov and Rubinov used the FW gap quantities extensively in their convergence proofs of the Frank-Wolfe method, and perhaps this quantity was used even earlier. In certain contexts, $G_{k}$ is an important quantity by itself, see for example Hearn , Khachiyan and Giesen et al. . Indeed, Hearn studies basic properties of the FW gaps independent of their use in any algorithmic schemes. For results concerning upper bound guarantees on $G_{k}$ for specific and general problems see Khachiyan , Clarkson , Hazan , Jaggi , Giesen et al. , and Harchaoui et al. . Both $B^{w}_{k}$ and $G_{k}$ are computed directly from the solution of the linear optimization problem in step (2.) and are recorded therein for convenience.

In some of our analysis of the Frank-Wolfe method, the computational guarantees will depend on the quality of upper bounds on $h^{*}$. In addition to the Wolfe bound $B^{w}_{k}$, step (3.) allows for an “optional other upper bound $B^{o}_{k}$ ” that also might be computed at iteration $k$. Sometimes there is structural knowledge of an upper bound as a consequence of a dual problem associated with (1), as when $h(\cdot)$ is conveyed with minmax structure, namely:

where the dual problem corresponds to our problem of interest (1). Weak duality holds, namely $h(\lambda)\leq h^{*}\leq f(x)$ for all $x\in P,\lambda\in Q$. At any iterate $\lambda_{k}\in Q$ of the Frank-Wolfe method one can construct a “minmax” upper bound on $h^{*}$ by considering the variable $x$ in that structure:

and it follows from weak duality that $B^{o}_{k}:=B^{m}_{k}$ is a valid upper bound for all $k$. Notice that $x_{k}$ defined above is the “optimal response” to $\lambda_{k}$ in a minmax sense and hence is a natural choice of duality-paired variable associated with the variable $\lambda_{k}$. Under certain regularity conditions, for instance when $h(\cdot)$ is globally differentiable on $E$, one can show that $B^{m}_{k}$ is at least as tight a bound as Wolfe’s bound, namely $B^{m}_{k}\leq B^{w}_{k}$ for all $k$ (see Proposition A.1), and therefore the FW gap $G_{k}$ conveniently bounds this minmax duality gap: $B^{m}_{k}-h(\lambda_{k})\leq B^{w}_{k}-h(\lambda_{k})=G_{k}$.

(Indeed, in the minmax setting notice that the optimal response $x_{k}$ in (6) is a function of the current iterate $\lambda_{k}$ and hence $f(x_{k})-h(\lambda_{k})=B^{m}_{k}-h(\lambda_{k})$ is not just any duality gap but rather is determined completely by the current iterate $\lambda_{k}$. This special feature of the duality gap $B^{m}_{k}-h(\lambda_{k})$ is exploited in the application of the Frank-Wolfe method to rounding of polytopes , parametric optimization on the spectrahedron , and to regularized regression (and perhaps elsewhere as well), where bounds on the FW gap $G_{k}$ are used to bound $B^{m}_{k}-h(\lambda_{k})$ directly.)

We also mention that in some applications there might be exact knowledge of the optimal value $h^{*}$, such as in certain linear regression and/or machine learning applications where one knows a priori that the optimal value of the loss function is zero. In these situations one can set $B^{o}_{k}\leftarrow h^{*}$.

Towards stating and proving complexity bounds for the Frank-Wolfe method, we use the following curvature constant $C_{h,Q}$, which is defined to be the minimal value of $C$ satisfying:

see ; we present a short proof of this inequality in Proposition A.2 for completeness. In contrast to other (proximal) first-order methods, the Frank-Wolfe method does not depend on a choice of norm. The norm invariant definition of $C_{h,Q}$ and the fact that (8) holds for any norm are therefore particularly appealing properties of $C_{h,Q}$ as a behavioral measure for the Frank-Wolfe method.

As a prelude to stating our main technical results, we define the following two auxiliary sequences, where $\alpha_{k}$ and $\beta_{k}$ are functions of the first $k$ step-size sequence values, $\bar{\alpha}_{1},\ldots,\bar{\alpha}_{k}$, from the Frank-Wolfe method:

(Here and in what follows we use the conventions: $\prod_{j=1}^{0}\cdot=1$ and $\sum_{i=1}^{0}\cdot=0$ .)

The following two theorems are our main technical constructs that will be used to develop the results herein. The first theorem concerns optimality gap bounds.

The second theorem concerns the FW gap values $G_{k}$ from step (2.) in particular.

Theorems 2.1 and 2.2 can be applied to yield specific complexity results for any specific step-size sequence $\{\bar{\alpha}_{k}\}$ (satisfying the mild assumption that $\bar{\alpha}_{k}<1$) through the use of the implied $\{\alpha_{k}\}$ and $\{\beta_{k}\}$ dual averages sequences. This is shown for several useful step-size sequences in the next section.

Proof of Theorem 2.1: We will show the slightly more general result for $k\geq 0$:

from which (10) follows by substituting $B=B_{k}$ above.

For $k=0$ the result follows trivially since $\beta_{1}=1$ and the summation term on the right side of (12) is zero by the conventions for null products and summations stated earlier. For $k\geq 1$, we begin by observing that the following equalities hold for the dual averages sequences (9):

where the first equality above uses identity (14), the first inequality uses the fact that $B_{k}\leq B^{w}_{i}$ for $i\leq k$, and the second inequality uses (15) and the fact that $\beta_{1}=1$. The result then follows by dividing by $\beta_{k+1}$ and rearranging terms. ∎

Proof of Theorem 2.2: For $i\geq 1$ we have:

Combining (17) with Theorem 2.1 we obtain:

Computational Guarantees for Specific Step-size Sequences

Herein we use Theorems 2.1 and 2.2 to derive computational guarantees for a variety of specific step-size sequences.

Before developing computational guarantees for specific step-sizes, we present a property of the pre-start step (Procedure 2) that has implications for such computational guarantees.

Let $\lambda_{1}$ and $B_{0}$ be computed by the pre-start step Procedure 2. Then $B_{0}-h(\lambda_{1})\leq\frac{1}{2}C_{h,Q}$.

and the result follows by rearranging terms. ∎

Suppose we initiate the Frank-Wolfe method with the pre-start step Procedure 2 from a given value $\lambda_{0}\in Q$ (which by definition assigns the step-size $\bar{\alpha}_{0}=1$ as discussed earlier), and then use the step-size $\bar{\alpha}_{i}=2/(i+2)$ for $i\geq 1$. This can be written equivalently as:

Computational guarantees for this sequence appeared in Clarkson , Hazan (with a corrected proof in Giesen et al. ), and Jaggi . In unpublished correspondence with the first author in 2007, Nemirovski presented a short inductive proof of convergence of the Frank-Wolfe method using this step-size rule.

We use the phrase “bound gap” to generically refer to the difference between an upper bound $B$ on $h^{*}$ and the value $h(\lambda)$, namely $B-h(\lambda)$. The following result describes guarantees on the bound gap $B_{k}-h(\lambda_{k+1})$ and the FW gap $G_{k}$ using the step-size sequence (18), that are applications of Theorems 2.1 and 2.2, and that are very minor improvements of existing results as discussed below.

Under the step-size sequence (18), the following inequalities hold for all $k\geq 1$:

The bound (19) is a very minor improvement over that in Hazan , Giesen et al. , Jaggi , and Harchaoui et al. , as the denominator is additively larger by $1$ (after accounting for the pre-start step and the different indexing conventions). The bound (20) is a modification of the original bound in Jaggi , and is also a slight improvement of the bound in Harchaoui et al. inasmuch as the denominator is additively larger by $1$ and the bound is valid for all $k\geq 1$.

Proof of Bound 3.1: Using (18) it is easy to show that the dual averages sequences (9) satisfy $\beta_{k}=\frac{k(k+1)}{2}$ and $\alpha_{k}=k+1$ for $k\geq 1$. Utilizing Theorem 2.1, we have for $k\geq 1$:

where the second inequality uses $B_{k}\leq B_{0}$, the third inequality uses Proposition 3.1, the first equality substitutes the dual averages sequence values, and the final inequality follows from Proposition A.3. This proves (19).

where the first inequality uses Proposition A.5 and the second inequality uses $\lceil\frac{k}{2}\rceil\leq\frac{k}{2}+\frac{1}{2}$. We also have:

where the first inequality uses Proposition A.5 and the second inequality uses $\lceil\frac{k}{2}\rceil\geq\frac{k}{2}$. Applying Theorem 2.2 and using (21) and (22) yields:

2 Simple Averaging

Consider the following step-size sequence:

Under the step-size sequence (23), the following inequality holds for all $k\geq 0$:

and the following inequality holds for all $k\geq 2$:

Proof of Bound 3.2: Using (23) it is easy to show that the dual averages sequences (9) are given by $\beta_{k}=k$ and $\alpha_{k}=1$ for $k\geq 1$. Utilizing Theorem 2.1 and Proposition 3.1, we have for $k\geq 1$:

3 Constant Step-size

Given $\bar{\alpha}\in(0,1)$, consider using the following constant step-size rule:

Under the step-size sequence (28), the following inequality holds for all $k\geq 1$:

If the pre-start step Procedure 2 is used, then:

If we decide a priori to run the Frank-Wolfe method for $k$ iterations after the pre-start step Procedure 2, then we can optimize the bound (30) with respect to $\bar{\alpha}$. The optimized value of $\bar{\alpha}$ in the bound (30) is easily derived to be:

With $\bar{\alpha}$ determined by (31), we obtain a simplified bound from (30) and also a guarantee for the FW gap sequence $\{G_{k}\}$ if the method is continued with the same constant step-size (31) for an additional $k+1$ iterations.

If we use the pre-start step Procedure 2 and the constant step-size sequence (31) for all iterations, then after $k$ iterations the following inequality holds:

Furthermore, after $2k+1$ iterations the following inequality holds:

It is curious to note that the bounds (24) and (32) are almost identical, although (32) requires fixing a priori the number of iterations $k$.

Proof of Bound 3.3: Under the step-size rule (28) it is straightforward to show that the dual averages sequences (9) are for $i\geq 1$:

It therefore follows from Theorem 2.1 that:

which proves (29). If the pre-start step Procedure 2 is used, then using Proposition 3.1 it follows that $B_{k}-h(\lambda_{1})\leq B_{0}-h(\lambda_{1})\leq\frac{1}{2}C_{h,Q}$, whereby from (29) we obtain:

Proof of Bound 3.4: Substituting the step-size (31) into (30) we obtain:

where the second inequality follows from (i) of Proposition A.4. This proves (32). To prove (33), notice that inequality (34) together with the subsequent chain of inequalities in the proofs of (29), (30), and (32) show that:

Using (35) and the substitution $\sum_{i=k+1}^{2k+1}\bar{\alpha}_{i}=(k+1)\bar{\alpha}$ and $\sum_{i=k+1}^{2k+1}\bar{\alpha}_{i}^{2}=(k+1)\bar{\alpha}^{2}$ in Theorem 2.2 yields:

where the second inequality uses (ii) of Proposition A.4 and the third inequality uses (i) of Proposition A.4. ∎

4 Extensions using Line-Searches

For inexact line-search methods, Dunn analyzes versions of the Frank-Wolfe method with an Armijo line-search and also a Goldstein line-search rule. In addition to convergence and computational guarantees for convex problems, also contains results for the case when the objective function is non-concave. And in prior work, Dunn presents convergence and computational guarantees for the case when the step-size $\bar{\alpha}_{k}$ is determined from the structure of the lower quadratic approximation of $h(\cdot)$ in (7), if the curvature constant $C_{h,Q}$ is known or upper-bounded. And in the case when no prior information about $C_{h,Q}$ is given, has a clever recursion for determining a step-size that still accounts for the lower quadratic approximation without estimation of $C_{h,Q}$.

Computational Guarantees for a Warm Start

In the framework of this study, the well-studied step-size sequence (18) and associated computational guarantees (Bound 3.1) corresponds to running the Frank-Wolfe method initiated with the pre-start step from the initial point $\lambda_{0}$. One feature of the main computational guarantees as presented in the bounds (19) and (20) is their insensitivity to the quality of the initial point $\lambda_{0}$. This is good if $h(\lambda_{0})$ is very far from the optimal value $h^{\ast}$, as the poor quality of the initial point does not affect the computational guarantee. But if $h(\lambda_{0})$ is moderately close to the optimal value, one would want the Frank-Wolfe method, with an appropriate step-size sequence, to have computational guarantees that reflect the closeness to optimality of the initial objective function value $h(\lambda_{0})$. Let us see how this can be done.

We will consider starting the Frank-Wolfe method without the pre-start step, started at an initial point $\lambda_{1}$, and let $C_{1}$ be a given estimate of the curvature constant $C_{h,Q}$. Consider the following step-size sequence:

Comparing (36) to the well-studied step-size rule (18), one can think of the above step-size rule as acting “as if” the Frank-Wolfe method had run for $\frac{2C_{1}}{B_{1}-h(\lambda_{1})}$ iterations before arriving at $\lambda_{1}$. The next result presents a computational guarantee associated with this step-size rule.

Under the step-size sequence (36), the following inequality holds for all $k\geq 1$:

Notice that in the case when $C_{1}=C_{h,Q}$, the bound in (37) simplifies conveniently to:

Also, as a function of the estimate $C_{1}$ of the curvature constant, it is easily verified that the bound in (37) is optimized at $C_{1}=C_{h,Q}$.

We remark that the bound (37) (or (38)) is small to the extent that the initial bound gap $B_{1}-h(\lambda_{1})$ is small, as one would want. However, to the extent that $B_{1}-h(\lambda_{1})$ is small, the incremental decrease in the bound due to an additional iteration is less. In other words, while the bound (37) is nicely sensitive to the initial bound gap, there is no longer rapid decrease in the bound in the early iterations. It is as if the algorithm had already run for $\left(\frac{2C_{1}}{B_{1}-h(\lambda_{1})}\right)$ iterations to arrive at the initial iterate $\lambda_{1}$, with a corresponding dampening in the marginal value of each iteration after then. This is a structural feature of the Frank-Wolfe method that is different from first-order methods that use prox functions and/or projections.

Proof of Bound 4.1: Define $s=\frac{2C_{1}}{B_{1}-h(\lambda_{1})}$, whereby $\bar{\alpha}_{i}=\frac{2}{s+1+i}$ for $i\geq 1$. It then is straightforward to show that the dual averages sequences (9) are for $i\geq 1$:

Utilizing Theorem 2.1 and (39), we have for $k\geq 1$:

The step-size sequence (36) determines all step-sizes for the Frank-Wolfe method based on two pieces of information at the initial point $\lambda_{1}$: (i) the initial bound gap $B_{1}-h(\lambda_{1})$, and (ii) the given estimate $C_{1}$ of the curvature constant. The step-size sequence (36) is a static warm-start strategy in that all step-sizes are determined by information that is available or computed at the first iterate. Let us see how we can improve the computational guarantee by treating every iterate as if it were the initial iterate, and hence dynamically determine the steps-size sequence as a function of accumulated information about the bound gap and the curvature constant.

where we note that $\bar{\alpha}_{k}$ depends explicitly on the value of $C_{k}$. Comparing $\bar{\alpha}_{k}$ in (40) with (18), we interpret $\frac{2C_{k}}{B_{k}-h(\lambda_{k})}$ to be “as if” the current iteration $k$ was preceded by $\frac{2C_{k}}{B_{k}-h(\lambda_{k})}$ iterations of the Frank-Wolfe method using the standard step-size (18). This interpretation is also in concert with that of the static warm-start step-size rule (36).

We now discuss how we propose to compute the new estimate $C_{k}$ of the curvature constant $C_{h,Q}$ at iteration $k$. Because $C_{k}$ will be only an estimate of $C_{h,Q}$, we will need to require that $C_{k}$ (and the step-size $\bar{\alpha}_{k}$ (40) that depends explicitly on $C_{k}$) satisfy:

We have the following computational guarantees for the Frank-Wolfe method with dynamic step-sizes (Method 3):

The iterates of the Frank-Wolfe method with dynamic step-sizes (Method 3) satisfy the following for any $k\geq 1$:

Furthermore, if the doubling strategy is used to update the estimates $\{C_{k}\}$ of $C_{h,Q}$, it holds that $C_{k}\leq\max\{C_{0},2C_{h,Q}\}$.

Proof of Bound 4.2: Let $i\geq 1$. For convenience define $A_{i}=\frac{2C_{i}}{B_{i}-h(\lambda_{i})}$, and in this notation (40) is $\bar{\alpha}_{i}=\frac{2}{A_{i}+2}$. Applying (ii) in step (4.) of Method 3 we have:

where the last inequality follows from the fact that $(a+2)^{2}>a^{2}+4a+3=(a+1)(a+3)$ for $a\geq 0$. Therefore

Analysis of the Frank-Wolfe Method with Inexact Gradient Computations and/or Subproblem Solutions

In this section we present and analyze extensions of the Frank-Wolfe method in the presence of inexact computation of gradients and/or subproblem solutions. We first consider the case when the linear optimization subproblem is solved approximately.

which shows that $B^{w}_{k}$ is a valid upper bound on $h^{*}$, with similar properties for $G_{k}$. The following two theorems extend Theorem 2.1 and Theorem 2.2 to the case of approximate subproblem solutions. Analogous to the the case of exact subproblem solutions, these two theorems can easily be used to derive suitable bounds for specific step-sizes rules such as those in Sections 3 and 4.

The pre-start step (Procedure 2 can also be generalized to the case of approximate solution of the linear optimization subproblem. Let $\lambda_{1}$ and $B_{0}$ be computed by the pre-start step with a $\delta=\delta_{0}$-approximate subproblem solution. Then Proposition 3.1 generalizes to:

and hence if the pre-start step is used (46) implies that:

Let us now discuss implications of Theorems 5.1 and 5.2, and Remark 5.1. Observe that the bounds on the right-hand sides of (46) and (47) are composed of the exact terms which appear on the right-hand sides of (10) and (11), plus additional terms involving the solution accuracy sequence $\delta_{1},\ldots,\delta_{k}$. It follows from (14) that these latter terms are particular convex combinations of the $\delta_{i}$ values and zero, and in (48) the last term is a convex combination of the $\delta_{i}$ values, whereby they are trivially bounded above by $\max\{\delta_{1},\ldots,\delta_{k}\}$. When $\delta_{i}:=\delta$ is a constant, then this bound is simply $\delta$, and we see that the errors due to the approximate computation of linear optimization subproblem solutions do not accumulate, independent of the choice of step-size sequence $\{\bar{\alpha}_{k}\}$. In other words, Theorem 5.1 implies that if we are able to solve the linear optimization subproblems to an accuracy of $\delta$, then the Frank-Wolfe method can solve (1) to an accuracy of $\delta$ plus a function of the step-size sequence $\{\bar{\alpha}_{k}\}$, the latter of which can be made to go to zero at an appropriate rate depending on the choice of step-sizes. Similar observations hold for the terms depending on $\delta_{1},\ldots,\delta_{k}$ that appear on the right-hand side of (47).

Note that Jaggi considers the case where $\delta_{i}:=\frac{1}{2}\delta\bar{\alpha}_{i}C_{h,Q}$ (for some fixed $\delta\geq 0$) and $\bar{\alpha}_{i}:=\frac{2}{i+2}$ for $i\geq 0$ (or $\bar{\alpha}_{i}$ is determined by a line-search), and shows that in this case Method 4 achieves $O\left(\frac{1}{k}\right)$ convergence in terms of both the optimality gap and the FW gaps. These results can be recovered as a particular instantiation of Theorems 5.1 and 5.2 using similar logic as in the proof of Bound 3.1.

Proof of Theorem 5.1: First recall the identities (13) and (14) for the dual averages sequences (9). Following the proof of Theorem 2.1, we then have for $i\geq 1$:

where the third equality above uses the definition of the Wolfe upper bound (2) in Method 4. The rest of the proof follows exactly as in the proof of Theorem 2.1. ∎

Proof of Theorem 5.2: For $i\geq 1$ we have:

The rest of the proof follows by combining (49) with Theorem 5.1 and proceeding as in the proof of Theorem 2.2. ∎

2 Frank-Wolfe Method with Inexact Gradient Computations

We now consider a version of the Frank-Wolfe method where the exact gradient computation is replaced with the computation of an approximate gradient, as was explored in Section 3 of Jaggi . We analyze two different models of approximate gradients and derive computational guarantees for each model. We first consider the $\delta$-oracle model of d’Aspremont , which was developed in the context of accelerated first-order methods. For $\delta\geq 0$, a $\delta$-oracle is a (possibly non-unique) mapping $g_{\delta}(\cdot):Q\to E^{\ast}$ that satisfies:

Note that the definition of the $\delta$-oracle does not consider inexact computation of function values. Depending on the choice of step-size sequence $\{\bar{\alpha}_{k}\}$, this assumption is acceptable as the Frank-Wolfe method may or may not need to compute function values. (The warm-start step-size rule (40) requires computing function values, as does the computation of the upper bounds $\{B_{k}^{w}\}$, in which case a definition analogous to (50) for function values can be utilized.)

The next proposition states the following: suppose one solves for the exact solution of the linear optimization subproblem using the $\delta$-oracle instead of the exact gradient. Then the absolute suboptimality of the computed solution in terms of the exact gradient is at most $2\delta$.

Let $\hat{\lambda}\in\arg\max\limits_{\lambda\in Q}\left\{\nabla h(\bar{\lambda})^{T}\lambda\right\}$. Then, we have:

Now consider a version of the Frank-Wolfe method where the computation of $\nabla h(\lambda_{k})$ at step (1.) is replaced with the computation of $g_{\delta_{k}}(\lambda_{k})$. Then Proposition 5.1 implies that such a version can be viewed simply as a special case of the version of the Frank-Wolfe method with approximate subproblem solutions (Method 4) of Section 5.1 with $\delta_{k}$ replaced by $2\delta_{k}$. Thus, we may readily apply Theorems 5.1 and 5.2 and Proposition 5.1 to this case. In particular, similar to the results in regarding error non-accumulation for an accelerated first-order method, the results herein imply that there is no accumulation of errors for a version of the Frank-Wolfe method that computes approximate gradients with a $\delta$-oracle at each iteration. Furthermore, it is a simple extension to consider a version of the Frank-Wolfe method that computes both (i) approximate gradients with a $\delta$-oracle, and (ii) approximate linear optimization subproblem solutions.

where $\|\cdot\|$ is a choice of norm on $E$. Note that in contrast to the $\delta$-oracle model, the $(\delta,L)$-oracle model does assume that the function $h(\cdot)$ is smooth or even concave – it simply assumes that there is an oracle returning the pair $(h_{(\delta,L)}(\bar{\lambda}),g_{(\delta,L)}(\bar{\lambda}))$ satisfying (51) and (52).

As with Theorem 5.1, observe that the terms on the right-hand side of (53) are composed of the exact terms which appear on the right-hand side of (10), plus an additional term that is a function of $\delta_{1},\ldots,\delta_{k}$. Unfortunately, Theorem 5.3 implies an accumulation of errors for Method 5 under essentially any choice of step-size sequence $\{\bar{\alpha}_{k}\}$. Indeed, suppose that $\beta_{i}=O(i^{\gamma})$ for some $\gamma\geq 0$, then $\sum_{i=1}^{k}\beta_{i+1}=O(k^{\gamma+1})$, and in the constant case where $\delta_{i}:=\delta$, we have $\frac{\sum_{i=1}^{k}\beta_{i+1}\delta_{i}}{\beta_{k+1}}=O(k\delta)$. Therefore in order to achieve an $O\left(\frac{1}{k}\right)$ rate of convergence (for example with the step-size sequence (18)) we need $\delta=O\left(\frac{1}{k^{2}}\right)$. This negative result nevertheless contributes to the understanding of the merits and demerits of different first-order methods as follows. Note that in it is shown that the “classical” gradient methods (both primal and dual), which require solving a proximal projection problem at each iteration, achieve an $O\left(\frac{1}{k}+\delta\right)$ accuracy under the $(\delta,L)$-oracle model for constant $(\delta,L)$. On the other hand, it is also shown in that all accelerated first-order methods (which also solve proximal projection problems at each iteration) generically achieve an $O\left(\frac{1}{k^{2}}+k\delta\right)$ accuracy and thus suffer from an accumulation of errors under the $(\delta,L)$-oracle model. As discussed in the Introduction herein, the Frank-Wolfe method offers two possible advantages over these proximal methods: (i) the possibility that solving the linear optimization subproblem is easier than the projection-type problem in an iteration of a proximal method, and/or (ii) the possibility of greater structure (sparsity, low rank) of the iterates. In Figure 1 we summarize the cogent properties of these three methods (or classes of methods) under exact gradient computation as well as with the $(\delta,L)$-oracle model. As can be seen from the table in Figure 1, no single method dominates in the three categories of properties shown in the table; thus there are inherent tradeoffs among these methods/classes.

Proof of Theorem 5.3: Note that (51) and (52) with $\bar{\lambda}=\lambda$ imply that:

Recall properties (13) and (14) of the dual averages sequences (9). Following the proof of Theorem 2.1, we then have for $i\geq 1$:

where the first inequality uses (52), and the second inequality uses (54) and the definition of the Wolfe upper bound in Method 5. The rest of the proof follows as in the proof of Theorem 2.1. ∎

Summary/Conclusions

The Frank-Wolfe method is the subject of substantial renewed interest due to the relevance of applications (e.g., regularized regression, boosting/classification, matrix completion, image construction, other machine learning problems), the need in many applications for only moderately high accuracy solutions, the applicability of the method on truly large-scale problems, and the appeal of structural implications (sparsity, low-rank) induced by the method itself. The method requires (at each iteration) the solution of a linear optimization subproblem over the feasible region of interest, in contrast to most other first-order methods which require (at each iteration) the solution of a certain projection subproblem over the feasible region defined by a strongly convex prox function. As such, the Frank-Wolfe method is particularly efficient in various important application settings including matrix completion.

In this paper we have developed new analysis and results for the Frank-Wolfe method. Virtually all of our results are consequences and applications of Theorems 2.1 and 2.2, which present computational guarantees for optimality gaps (Theorem 2.1) and the “FW gaps” (Theorem 2.2) for arbitrary step-size sequences $\{\bar{\alpha}_{k}\}$ of the Frank-Wolfe method. These technical theorems are applied to yield computational guarantees for the well-studied step-size rule $\bar{\alpha}_{k}:=\frac{2}{k+2}$ (Section 3.1), simple averaging (Section 3.2), and constant step-size rules (Section 3.3). The second set of contributions in the paper concern “warm start” step-size rules and computational guarantees that reflect the quality of the given initial iterate (Section 4) as well as the accumulated information about the optimality gap and the curvature constant over a sequence of iterations (Section 4.1). The third set of contributions concerns computational guarantees in the presence of an approximate solution of the linear optimization subproblem (Section 5.1) and approximate computation of gradients (Section 5.2).

We end with the following observation: that the well-studied step-size rule $\bar{\alpha}_{k}:=\frac{2}{k+2}$ does not require any estimation of the curvature constant $C_{h,Q}$ (which is generically not known). Therefore this rule is in essence fully-automatically scaled as regards the curvature $C_{h,Q}$. In contrast, the dynamic warm-start step-size rule (40), which incorporates accumulated information over a sequence of iterates, requires updating estimates of the curvature constant $C_{h,Q}$ that satisfy certain conditions. It is an open challenge to develop a dynamic warm-start step-size strategy that is automatically scaled and so does not require computing or updating estimates of $C_{h,Q}$.

References

Appendix A Appendix

Let $B_{k}^{w}$ and $B_{k}^{m}$ be as defined in Section 2. Suppose that there exists an open set $\hat{Q}\subseteq E$ containing $Q$ such that $\phi(x,\cdot)$ is differentiable on $\hat{Q}$ for each fixed $x\in P$, and that $h(\cdot)$ has the minmax structure (4) on $\hat{Q}$ and is differentiable on $\hat{Q}$. Then it holds that:

Furthermore, it holds that $B_{k}^{w}=B_{k}^{m}$ in the case when $\phi(x,\cdot)$ is linear in the variable $\lambda$.

It is simple to show that $B_{k}^{m}\geq h^{*}$. At the current iterate $\lambda_{k}\in Q$, define $x_{k}\in\arg\min\limits_{x\in P}\phi(x,\lambda_{k})$. Then from the definition of $h(\lambda)$ and the concavity of $\phi(x_{k},\cdot)$ we have:

whereby $\nabla_{\lambda}\phi(x_{k},\lambda_{k})$ is a subgradient of $h(\cdot)$ at $\lambda_{k}$. It then follows from the differentiability of $h(\cdot)$ that $\nabla h(\lambda_{k})=\nabla_{\lambda}\phi(x_{k},\lambda_{k})$, and this implies from (55) that:

If $\phi(x,\lambda)$ is linear in $\lambda$, then the second inequality in (55) is an equality, as is (56). ∎

For $k\geq 0$ the following inequality holds:

The inequality above holds at equality for $k=0$. By induction, suppose the inequality is true for some given $k\geq 0$, then

which combined with (57) completes the induction. ∎

For $k\geq 1$ let $\bar{\alpha}:=1-\frac{1}{\sqrt[k]{k+1}}$. Then the following inequalities holds:

$\displaystyle\frac{\ln(k+1)}{k}\geq\bar{\alpha}$ , and

To prove (i), define $f(t):=1-e^{-t}$, and noting that $f(\cdot)$ is a concave function, the gradient inequality for $f(\cdot)$ at $t=0$ is

Substituting $t=\frac{\ln(k+1)}{k}$ yields

Note that (ii) holds for $k=1$, so assume now that $k\geq 2$. To prove (ii) for $k\geq 2$, substitute $t=-\frac{\ln(k+1)}{k}$ into the gradient inequality above to obtain $-\frac{\ln(k+1)}{k}\geq 1-(k+1)^{\frac{1}{k}}$ which can be rearranged to:

Finally, rearranging (59) and multiplying by $k+1$ yields (ii). ∎

It is easy to verify that the integral expressions in (62) match the bounds in (60) and (61) for the specific choices of $f(t)=\frac{1}{t}$ and $f(t)=\frac{1}{t^{2}}$, respectively. ∎