On the Global Linear Convergence of Frank-Wolfe Optimization Variants
The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine learning applications. However, its convergence rate is known to be slow (sublinear) when the solution lies at the boundary. A simple lessknown fix is to add the possibility to take 'away steps' during optimization, an operation that importantly does not require a feasibility oracle. In this paper, we highlight and clarify several variants of the Frank-Wolfe optimization algorithm that have been successfully applied in practice: away-steps FW, pairwise FW, fully-corrective FW and Wolfe's minimum norm point algorithm, and prove for the first time that they all enjoy global linear convergence, under a weaker condition than strong convexity of the objective. The constant in the convergence rate has an elegant interpretation as the product of the (classical) condition number of the function with a novel geometric quantity that plays the role of a 'condition number' of the constraint set. We provide pointers to where these algorithms have made a difference in practice, in particular with the flow polytope, the marginal polytope and the base polytope for submodular optimization.
The Frank-Wolfe algorithm [9] (also known as conditional gradient) is one of the earliest existing methods for constrained convex optimization, and has seen an impressive revival recently due to its nice properties compared to projected or proximal gradient methods, in particular for sparse optimization and machine learning applications.
On the other hand, the classical projected gradient and proximal methods have been known to exhibit a very nice adaptive acceleration property, namely that the the convergence rate becomes linear for strongly convex objective, i.e. that the optimization error of the same algorithm after t iterations will decrease geometrically with O((1 − ρ) t ) instead of the usual O(1/t) for general convex objective functions. It has become an active research topic recently whether such an acceleration is also possible for Frank-Wolfe type methods.
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 [34,12,5], and the newer work of [28], as well as the line of work of [1,19,26] which rely on Robinson's condition [30]. 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, [5] 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 [12]. The early work of [23] showed linear convergence for strongly 1
The Frank-Wolfe algorithm [9] (also known as conditional gradient) is one of the earliest existing methods for constrained convex optimization, and has seen an impressive revival recently due to its nice properties compared to projected or proximal gradient methods, in particular for sparse optimization and machine learning applications.
On the other hand, the classical projected gradient and proximal methods have been known to exhibit a very nice adaptive acceleration property, namely that the the convergence rate becomes linear for strongly convex objective, i.e. that the optimization error of the same algorithm after t iterations will decrease geometrically with O((1 − ρ) t ) instead of the usual O(1/t) for general convex objective functions. It has become an active research topic recently whether such an acceleration is also possible for Frank-Wolfe type methods.
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 [34,12,5], and the newer work of [28], as well as the line of work of [1,19,26] which rely on Robinson's condition [30]. 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, [5] 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 [12]. The early work of [23] showed linear convergence for strongly convex constraint sets, under the strong requirement that the gradient norm is not too small (see [11] 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 [34], and later also analyzed in [12]. The precise method is stated below in Algorithm 1. [12] 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, [1,19,26] have obtained linear convergence results in the case that the optimum solution satisfies Robinson's condition [30]. In a different recent line of work, [10,22] 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:
with only access to:
where A ⊆ R d is a finite set of vectors that we call atoms. 1 We assume that the function f is µ-strongly convex with L-Lipschitz continuous gradient over M. We also consider weaker conditions than strong convexity for f in Section 4. As A is finite, M is a (convex and bounded) polytope. The methods that we consider in this paper only require access to a linear minimization oracle LMO A (.) associated with the domain M through a generating set of atoms A. This oracle is defined as to return a minimizer of a linear subproblem over M = conv(A), for any given direction r ∈ R d .
Report for "On the Global Linear Convergence of Frank-Wolfe Optimization Variants".  ## SummaryThe authors consider the problem of minimizing a strongly convex or partially strongly convex function over a polyhedron. They describe and analyse different variants of the Frank-Wolfe algorithm. The authors show that the different variants of the algorithm allow to bypass the known fact that the vanilla Frank-Wolfe algorithm is not able to take advantage of strong convexity properties of the objective function. This leads to proof of linear convergence for all the variants presented. The analysis is based on the introduction of a combinatorial positive constant that relates to a notion of condition number for polyhedra. Numerical results on both synthetic and real examples are presented.## Main commentsThe paper present various versions of the original algorithm which were introduced previously in the literature. Linear convergence is a new finding for some of the variants and constitutes an interesting contribution. Furthermore, the pyramidal width introduced in the paper may have interesting applications beyond linear oracle based method. The proof arguments are reasonable up to my understanding and I do not see any major issue related to the content of this work. I detail a few comments that should be taken into account in the next paragraph, some of them may need to be reflected in the text. Additional minor comments are given in the following section. ## Detailed comments- It may be worth mentioning what happens for these algorithms when the strong convexity assumption is not verified.- There is a lot of emphasis on the notion of affine invariance. I understand the idea and it is important. But I think it could be clarified. For example, I think that the fact that the linear map is surjective is important. Also I do not think that the statement that A is arbitrary in [17] (line 710) is true as the paragraph dedicated to affine invariance in [17] mentions explicitly the surjectivity. - In the proof of Theorem 3 in the appendix, I think that the conclusion of line 640 is correct but the arguments are not. First, it could be explicitly mentioned what is meant by KKT. Second KKT only expresses stationarity at the first order and I am not sure that this is enough to conclude that the solution of minimizing a linear function on the intersection of a cone and the unit (euclidean) sphere is on the relative boundary of the cone. I do not know what the authors expicitly meant by "KKT", but for example for the cone $\RR_+ \times \RR$, $d= (-1,0)$ does not belong to the cone and $y = (1,0)$ is in the interior of the cone and satisfies some stationarity conditionwhich I guess correspond more or less to the KKT condition the authors have in mind.- The MNP variant actually requires to have a subroutine that minimizes the objective over an affine hull. Since in the model, $f$ is only defined on script M, the setting in which this make sense is slightly different. Furthermore, this has very important practical implications in terms of implementation. This could be emphasized. I guess the line search in step 7 involves the constraints. In this case, this is another significant requirement compared to other variants for which this is explicitly avoided (see line 163).- The authors claim that everything works the same for the partially strongly convex model just by replacing a constant by another. It is a bit fast since the constants in (21) and (34) look quite different, in particular, there are multiplicative 2 factor that do not occur at the same place. Some hints are welcome.- The away step variant under the partial strongly convex model was treated in [4]. Is there a difference in the estimated rates? It would be nice to have a discussion, for example based on the cases for which the pyramidal width is known.- For the simplex, the fact that the pyramidal width is the same as the width deserves more justification. Also the presentation would benefit from a more precise citation of [2] (which result the authors refere to in this paper).- Up to my understanding, the convergence analysis of [12] does not treat the case "strongly convex objective + strongly convex set". This paper actually proposes the linear convergence as an open problem contrary to what is stated in the introduction.  ## Minor comments- The abstract mentions "weaker condition than strong convexity". I would add "of the objective".- May be add some reference about the convergence rates of projected gradient method- Line 99: typo "While the tracking the active set"- Regarding footnote 3, the lower bound actually holds for specific sequences that never reach the face of interest. It does not hold for every sequence, it depends on the initialization and the problem at hand.- Line (151) mentions that the active set is small, while after a large number of iterations it is potentially large, unless there is some specific step performed to optimize the vertex representation.- Line 178: "is to in each step only move", I would add commas- Line 188: typo "due our"- Line 210: typo "more computed more efficiently"- Line 212: "overarching"?- (7) could actually be summarized as $h_t \geq \min{g_t/2, g_t^2/(LM^2)}- The authors conjecture a nonincreasingness property for the constant they introduced. Do they have an intuition why this should be the case beyond the fact that this constant is greater for smaller for the cube than the simplex?- Figure 2 is hardly readable- On page 12 (appendix), the notation $r$ is used in the main text and in footnote 7 to denote two different thing. Similar comment holds for y.- The argument following (14) go really fast and non trivial details are missing. It should be written explicitly that (14) is equivalent to the problem mentioned on line 640. Here also, $y$ and $y^*$ are used to denote the decision variable and solution of two different problems.- On line 689, (14) should be (15).- Line 700 makes a self reference to "the appendix": it is itself part of the appendix.- Line 950, I guess "drop step" should be "swap step".- In (33), $B$ should be $B_1$.