On the Global Linear Convergence of Frank-Wolfe Optimization Variants

Simon Lacoste-Julien; Martin Jaggi

Source-linked AI summary

On the Global Linear Convergence of Frank-Wolfe Optimization Variants

Simon Lacoste-Julien, Martin Jaggi

arXiv:1511.05932v1Nov 18, 2015math.OCcs.LGstat.ML

TL;DR

Frank-Wolfe can be sublinear when the optimum lies on a boundary, motivating variants that take away steps or correct over active atoms. The paper analyzes four such variants using polytope geometry and proves global geometric convergence under strong convexity, while identifying practical scope and complexity limitations.

Problem
Frank-Wolfe has a sublinear rate when the solution lies on the boundary, raising whether its variants can achieve linear convergence without relying on the optimum’s interior location.
Method
The paper analyzes away-steps FW, pairwise FW, fully-corrective FW, and Wolfe’s min-norm-point algorithm through pairwise FW directions and the pyramidal width of the atom set.
Results
All four variants have global geometric convergence on polytopes for strongly convex objectives, with progress indexed by good steps and the FW gap bounded by primal error.
Takeaways & Limitations
Away-step variants address boundary-induced zig-zagging using only linear minimization and active-set operations, while preserving structured-polytope applications.
Takeaways & Limitations
The analysis uses a conservative maximum feasible step-size, and the practical usefulness of the acceleration remains open because constants depend on dimensionality.

Abstract

from arXiv · show

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 less-known 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.

1 Improved Variants of the Frank-Wolfe Algorithm

The paper presents away-step, pairwise, fully-corrective, and Wolfe min-norm-point variants that augment Frank-Wolfe by modifying or correcting atom weights while using linear-oracle access.

Away-Steps Frank-Wolfe: Away-steps FW adds moves away from an active atom, using the active set rather than a stronger feasibility oracle to preserve feasibility.The maximum step-size maintains the convex representation and keeps iterates inside conv(S(t)) ⊆ M.
Pairwise Frank-Wolfe: Pairwise FW transfers weight from the away atom to the FW atom while leaving all other active weights unchanged.This differs from classical FW, which shrinks all active weights at every iteration.
Pairwise Frank-Wolfe: Pairwise FW provides the proof technique establishing global linear convergence for away-steps, fully-corrective, and Wolfe min-norm-point variants.The pairwise step can also prune sparse active sets efficiently, although its theoretical rate guarantee is looser because swap steps are difficult to bound.
Fully-Corrective Frank-Wolfe, and Wolfe’s Min-Norm Point Algorithm: Fully-corrective FW re-optimizes over a correction polytope conv(A(t)) instead of using line-search, allowing variants including simplicial decomposition.Wolfe’s min-norm-point algorithm instead uses a sequence of affine projections and can be computed more efficiently.
Fully-Corrective Frank-Wolfe, and Wolfe’s Min-Norm Point Algorithm: Approximate correction is sufficient for global linear convergence if it maintains the active-set relationship and makes at least as much progress as a FW step.The correction need not solve the active-set subproblem exactly and can itself be implemented using away-steps FW.

2 Global Linear Convergence Analysis

The convergence analysis replaces dependence on the optimum’s location with a geometric quantity of the atom set, yielding global geometric decrease for four Frank-Wolfe variants on polytope domains.

Intuition for the Convergence Proofs: Boundary optima make standard Frank-Wolfe sublinear because its update direction can become nearly orthogonal to the negative gradient.Interior-optimum analyses instead depend on a positive distance from the domain boundary.
Intuition for the Convergence Proofs: The pyramidal width of A lower-bounds the useful alignment of pairwise FW directions with negative-gradient directions using only the geometry of M.This geometric quantity supports the global convergence argument without requiring the optimum to lie in the relative interior.
Convergence Results: All four variants decrease suboptimality geometrically on good steps under an L-Lipschitz gradient and µ-strong convexity over M = conv(A).Theorem 1 uses M = diam(M) and δ = PWidth(A) in the convergence constant.
Convergence Results: k(t) = t for FCFW, k(t) ≥ t/2 for MNP and AFW, and k(t) ≥ t/(3|A|!+1) for PFW, yielding h_t ≤ h_0 exp(−ρ k(t)).For general convex objectives with µ = 0, the guarantee becomes h_t = O(1/k(t)).
Convergence Results: The FW gap is linearly controlled through the primal error, extending the convergence result beyond objective suboptimality.The paper states that prior linear-convergence results had not shown linear convergence of the duality gap.

3 Pyramidal Width

The section defines pyramidal width as a polytope-dependent geometric quantity that bounds progress toward the optimum and enters the global linear convergence constant.

Pyramidal Width: Pyramidal directional width measures the width of a pyramid formed from an active-set base and a Frank-Wolfe summit in a chosen direction.The construction uses the feasible direction, base point, active-set candidates, and selected FW atom.
Pyramidal Width: Pyramidal width takes the smallest relevant directional width over feasible directions and all faces of the convex hull.Restricting directions to those pointing inward avoids zero width from infeasible directions.
Progress Bound: Theorem 3 lower-bounds progress along the pairwise FW direction using the error direction and negative gradient.The bound applies to a suboptimal point, an active set, and the pairwise direction selected from the atom set and active set.
Condition Number: The domain condition number is (M/δ)^2, the squared ratio of diameter to pyramidal width, and larger eccentricity implies slower convergence.The inverse linear-rate constant factors into the objective condition number L/µ and this geometric domain term.
Complexity: For the unit simplex, the resulting strongly convex optimization complexity is O(d L/µ log(1/ϵ)), consistent with a 1/t lower bound through t ≤ d.The supplied complexity passage reports linear dependence on dimension and the Frank-Wolfe lower-bound regime.

4 Non-Strongly Convex Generalization

The paper extends global linear convergence of all considered Frank-Wolfe variants to objectives that are convex but not necessarily strongly convex in the original variables.

Generalization: The extension covers f(x) = g(Ax) + ⟨b, x⟩ when g is strongly convex and continuously differentiable over AM.For general A, f remains convex but may fail to be strongly convex.
Generalization: Linear convergence still holds with the rate constant’s µ replaced by the generalized constant µ̃ from Lemma 9.The statement applies to all Frank-Wolfe variants covered by the paper.

5 Illustrative Experiments

Two experiments evaluate the variants on constrained Lasso and video co-localization, where away-steps and pairwise FW outperform original FW and show linear convergence.

Constrained Lasso: The constrained Lasso experiment uses a scaled L1-ball, a random 200×500 Gaussian matrix, a 50-entry sparse vector, and 10% additive noise.The linear minimization oracle selects the matrix column with best inner product against the residual.
Video Co-localization: The video co-localization experiment solves a quadratic program over a flow polytope with 660 variables, using shortest-path dynamic programming for the linear oracle.The flow polytope is the convex hull of network paths.
Results: Away-steps and pairwise FW outperform original FW and exhibit linear convergence in both experiments.Figure 2 plots the duality gap gFW t against iterations for the Lasso and video co-localization problems.
Results: The paper also reports an experiment demonstrating the empirical tightness of the theoretical linear convergence-rate constant.The supplied outline identifies this as the purpose of a separate experiment in Section E.

A.1 Wolfe’s Min-Norm Point (MNP) algorithm

Wolfe’s min-norm point algorithm is presented as a correction-based Frank-Wolfe variant that uses affine-hull projections and differs from fully-corrective FW in its correction polytope and atom management.

MNP Structure: The generalized MNP algorithm runs the Frank-Wolfe outer loop with a correction subroutine called the minor cycle.Wolfe’s terminology distinguishes the correction minor cycle from the Frank-Wolfe major cycle.
MNP versus FCFW: MNP differs from fully-corrective FW because it performs sequential affine projections, which can produce a different update from optimizing directly over the correction polytope.Standard FCFW optimizes f over conv(A(t)), whereas MNP uses affine projections on the active set.
MNP versus FCFW: After correction, MNP makes the iterate minimize f over both the active-set affine hull and its convex hull, while FCFW minimizes over conv(A(t) ∪ {st}).This equivalence for MNP can fail when more than one atom is dropped during correction.
Atom Management: MNP keeps correction atoms affinely independent and identical to the active set, whereas FCFW may retain redundant or inactive atoms.Affine-hull projections are especially efficient for Euclidean-norm objectives when a triangular active-set representation is maintained.
Assumption: MNP requires minimization over the affine hull of M to be well-defined and efficient, while its line search uses only the explicitly listed active-set convex hull.The correction line search can be computed in O(|S(k−1)|).

A.2 Applications to Submodular Minimization

The global linear convergence result improves the theoretical complexity of Wolfe’s minimum norm point algorithm for submodular minimization and aligns it with observed insensitivity to function magnitude.

Using linear convergence, MNP complexity changes from O(d5F 2) to O(d5 log(d F)), matching the fastest known algorithms’ logarithmic dependence on F.The same improvement applies to AFW and FCFW.
The result helps narrow the gap between MNP’s previously weaker theoretical rates and its strong empirical performance on base polytopes.
MNP’s observed performance was not highly sensitive to F, consistent with placing the F factor inside a logarithm.

A.3 Pairwise Frank-Wolfe

The paper analyzes pairwise Frank-Wolfe as an adaptive alternative to a more complex local-linear-oracle approach, while correcting limitations and proof issues in related work.

Pairwise Frank-Wolfe: Pairwise FW transfers weight from an away atom to a FW atom, and Garber–Hazan’s local linear oracle implements this through a sequence of such steps.
Pairwise Frank-Wolfe: The proposed pairwise FW variant performs one line-search in the pairwise direction, yielding a fully adaptive algorithm with a global linear convergence rate.
Related work: Garber and Hazan’s method requires several loose constants for step sizes, constraining behavior to its worst-case analysis.
Related work: The paper notes that prior complexity accounting for MNP contained both an overestimated per-iteration cost and an underestimated number of good cycles.
Caveat: The logarithmic-complexity implication for MNP assumes that the base polytope’s eccentricity does not depend on F, which remains unproved.
Related work: The paper identifies corrections to convergence proofs for a method choosing between standard and pairwise FW steps after line search.
Related work: Pairwise FW steps can stall when the maximal feasible step size α_vt is too small, although the cited global-convergence statement remains correct for its algorithm.
Related work: Earlier analyses of away-step and related methods had constants depending on the solution’s distance to the relative boundary or on the optimum’s location.

B.1 Pyramidal Width of the Cube and Probability Simplex

The section evaluates pyramidal width and condition-number behavior for the cube and probability simplex, showing strong dimension dependence for the cube and explicit simplex widths.

Cube: For the cube, the proof uses active-set structure and feasible directions to establish a pyramidal-width lower bound of 1/√d.
Cube: The cube proof’s lower bound is attained by an interior point with the canonical basis as active set and direction coordinates r_i = −1/√d.
Cube: A tighter condition measure based on ||s−v|| rather than the diameter could improve constants generally, but not the cube’s Ω(d²) scaling.
Cube: The cube’s condition number is at least k² = d²/4, so tightening the geometric definition does not change its Ω(d²) dependence.
Probability Simplex: For the probability simplex, pyramidal width equals standard width because relative-interior active sets contain all atoms and faces are lower-dimensional simplices.
Probability Simplex: The section notes that proving the obtained simplex values are minimal is non-trivial and relies on previously computed regular-simplex width.
Probability Simplex: The probability simplex width is 2/d when d is even and slightly larger, 2/√(d²−1), when d is odd.

B.2 Proof of Theorem 3 on the Pyramidal Width

The proof establishes a geometric lower bound for the pairwise FW progress quantity by projecting non-feasible directions onto successively lower-dimensional faces until feasibility is recovered.

Theorem 3: Theorem 3 lower-bounds pairwise FW progress using the negative gradient, normalized error direction, active set, and pyramidal-width geometry.
Lemma 5: Figure 3 depicts the minimizing direction and the facet K′ used in this projection argument.
Proof strategy: The proof defines feasibility as membership in cone(A−x) and uses orthogonal projection because orthogonal components do not affect the relevant inner products.
Lemma 5: Lemma 5 shows that a feasible unit direction minimizing angle with a non-feasible r lies on a facet containing the current point, under Euclidean norm and r ∈ span(K).
Proof strategy: If the negative-gradient direction is feasible, its pairwise direction is directly covered by the pyramidal-width definition.
Proof strategy: If the direction is infeasible, the proof projects it onto a facet containing the current point and repeats this reduction on lower-dimensional faces.
Proof strategy: The process terminates at the lowest-dimensional face containing the current point, where every direction in its span is feasible.
Convergence implication: The resulting convergence analysis combines objective smoothness and strong convexity with the domain’s pyramidal width.

D Linear Convergence Proofs

The paper establishes global linear convergence for AFW, PFW, FCFW, and MNP on polytopes, using curvature and geometric strong-convexity quantities. The rates account for algorithm-specific good, drop, and swap steps.

Global convergence: The four Frank-Wolfe variants converge linearly for strongly convex objectives over polytopes.The analysis uses a geometric strong convexity constant and a modified curvature constant.
Step types: Good steps decrease suboptimality geometrically, while drop and swap steps determine how often that decrease applies.A good step has γt < γmax; problematic steps include active-set drops and PFW swaps.
Global convergence: AFW and MNP have at most t/2 drop steps, whereas FCFW has no bad steps and PFW has at most 3|A|! swap steps between good steps.Consequently, AFW and MNP incur an extra factor of 1/2 in their global rate, while FCFW does not.
General convex objectives: For general convex objectives with zero geometric strong-convexity constant, all four variants have O(1/k(t)) convergence in the number of good steps.The good-step counts are t for FCFW, at least t/2 for AFW and MNP, and at least t/(3|A|! + 1) for PFW.
Proof strategy: The proof bounds suboptimality through geometric strong convexity and bounds progress through curvature, then controls bad steps combinatorially.The modified curvature constant permits away and pairwise directions, including directions that may leave the feasible domain for extended step sizes.

E Empirical Tightness of Linear Rate Constant

A triangle-domain experiment tests whether the theoretical linear-rate constant is tight as the domain angle shrinks. PFW closely tracks theory, while empirical comparisons with AFW depend on the theoretical rate.

Experimental setup: The experiment tests AFW and PFW on triangle domains with increasingly small θ, producing theoretical rates from 0.04 to 1e−7.The objective is quadratic, has condition number L/µ = 1, and places x∗ on an edge.
Empirical tightness: The estimated-to-theoretical rate ratio for PFW stays around 10 across six orders of magnitude in the rate.The study uses 20 random interior starting points and estimates rates from 2000 iterations.
Refined bound: A tighter PFW constant based on finite worst-case angles improves the bound by about a factor of 4 but still does not match the empirical observation.The refined constant is based on sin²(θ/2) for the triangle domain.
Algorithm comparison: PFW appears faster at larger theoretical rates, whereas AFW has a slightly better empirical rate for very small rates.The comparison is between the empirical rates of PFW and AFW.

F Non-Strongly Convex Generalization

The paper generalizes its convergence analysis beyond strongly convex objectives to objectives with a structured strongly convex component and a linear term. The resulting generalized geometric constant preserves affine invariance but depends on the solution set.

Generalized objectives: The generalized setting uses f(x) = g(Ax) + ⟨b, x⟩, where g is strongly convex over the transformed domain AM.The linear term and rank-deficient map allow objectives that are not strongly convex in x.
Generalized condition: A generalized geometric strong-convexity constant ˜µf is defined using a supremum over the solution set and remains affine invariant.Unlike the original quantity, it depends on the location of the solution set X∗.
Generalized condition: The generalized constant satisfies ˜µf ≥ ˜µ · (PWidth(M))².The bound connects the generalized objective condition to the pyramidal width of the domain.
Scope of guarantee: The condition ˜µf > 0 is weaker than generalized strong convexity in the Hoffman sense, although Hoffman strong convexity implies it.The proof follows the earlier convergence argument after replacing the classical geometric constant.
Convergence extension: All four Frank-Wolfe variants retain the linear convergence theorem when µA_f is replaced by ˜µf.The same algorithm-specific constants and treatment of drop and swap steps apply.