Source-linked AI summary
Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
Dan Garber, Elad Hazan
TL;DR
Frank-Wolfe offers projection-free optimization through linear optimization, but its general convergence rate is limited to 1/t. The paper analyzes smooth strongly convex optimization over strongly convex sets, proves an O(1/t^2) rate for vanilla Frank-Wolfe, and identifies practical norm-based sets where the linear oracle is straightforward. It also derives several previous fast-rate results from the same analysis.
Problem
Frank-Wolfe's tight general convergence rate is 1/t, motivating faster projection-free methods that can approach projected first-order methods.
Method
The paper analyzes vanilla Frank-Wolfe for smooth strongly convex optimization over strongly convex feasible sets and studies norm-induced constraint balls.
Results
O(1/t^2) is the proved convergence rate for smooth strongly-convex optimization over strongly-convex sets, and previous fast-rate results follow from the analysis.
Takeaways & Limitations
ℓp, Schatten, and matrix group norm balls support strongly convex constraints with straightforward closed-form linear optimization.
Takeaways & Limitations
The proof leaves optimization over the intersection of the feasible set and a small ball as a potentially costly linear-oracle subproblem.
Abstract
from arXiv · showhide
The Frank-Wolfe method (a.k.a. conditional gradient algorithm) for smooth optimization has regained much interest in recent years in the context of large scale optimization and machine learning. A key advantage of the method is that it avoids projections - the computational bottleneck in many applications - replacing it by a linear optimization step. Despite this advantage, the known convergence rates of the FW method fall behind standard first order methods for most settings of interest. It is an active line of research to derive faster linear optimization-based algorithms for various settings of convex optimization. In this paper we consider the special case of optimization over strongly convex sets, for which we prove that the vanila FW method converges at a rate of $\frac{1}{t^2}$. This gives a quadratic improvement in convergence rate compared to the general case, in which convergence is of the order $\frac{1}{t}$, and known to be tight. We show that various balls induced by $\ell_p$ norms, Schatten norms and group norms are strongly convex on one hand and on the other hand, linear optimization over these sets is straightforward and admits a closed-form solution. We further show how several previous fast-rate results for the FW method follow easily from our analysis.
1. Introduction
Frank-Wolfe is a projection-free first-order method valued for large-scale optimization, but its standard 1/t convergence rate is slower than rates of optimal first-order methods. This paper studies strongly convex feasible sets, proving an accelerated rate for vanilla Frank-Wolfe and connecting the setting to practical norm-based constraints.
- Motivation: Frank-Wolfe minimizes smooth convex functions over convex sets using iterative linear optimization instead of projections.This projection-free structure has supported practical algorithms with provable rates in several large-scale machine-learning problems.
- Motivation: 1/t is the tight general convergence rate for Frank-Wolfe, motivating the search for faster projection-free methods.Projected methods achieve faster rates in corresponding smooth convex settings, including 1/t^2 for accelerated gradient descent.
- Contribution: 1/t^2 is the convergence rate proved here for vanilla Frank-Wolfe when the objective and feasible set are strongly convex.The improvement is independent of dimension and lies between the standard 1/t rate and a linear rate.
- Applications: ℓp, Schatten, and matrix group norm balls provide strongly convex constraint sets for which linear optimization has a closed-form solution.The paper highlights regularized linear regression as an optimization example with such constraints.
- Related Work: Earlier faster Frank-Wolfe results relied on settings such as polytopes, interior optima, away steps, stronger quadratic oracles, or gradient lower bounds.The paper positions its analysis alongside these prior results and shows that previous fast-rate results can follow from its analysis.
2. Preliminaries
The preliminaries define smoothness and strong convexity for functions and sets, then specify the projection-free Frank-Wolfe algorithm and its baseline and strongly-convex convergence results.
- Smoothness and Strong Convexity: The framework uses dual norms on a finite vector space to define smoothness and strong convexity over a convex set.
- Smoothness and Strong Convexity: A strongly convex set contains a norm-induced ball centered at every convex combination of two feasible points, with radius proportional to γ(1 −γ) α.
- Smoothness and Strong Convexity: The analysis assumes a full-dimensional feasible set, while lower-dimensional cases can replace the gradient with its projection onto the set’s affine span.
- The Frank-Wolfe Algorithm: Frank-Wolfe repeatedly calls a linear optimization oracle at the gradient and updates by a convex combination selected through a cheap line search.
- Our Results: Under strong convexity of both the objective and feasible set, the paper establishes its faster convergence theorem for the same algorithm, with M defined from αf, αK, and βf.
3. Proof of Theorem 2
The proof links strong convexity of the feasible set to a larger duality gap and uses this relationship to establish the Frank-Wolfe method's accelerated 1/t^2 convergence rate.
- The approximation error is defined as h_t = f(x_t) − f(x∗), measuring the iterate's suboptimality.
- Strong convexity makes the duality gap increase with ∥p_t − x_t∥, preventing the gap from becoming arbitrarily small when this distance is large.
- The proof constructs a feasible point from the normalized negative gradient and uses the linear oracle's optimality together with strong convexity of K.
- Smoothness of f converts the duality-gap bound into a recurrence for the next approximation error h_{t+1}.
- 1/t^2 convergence follows by induction from the recurrence and an appropriate step-size choice, while the error is nonincreasing across iterations.
- The argument distinguishes cases in the recurrence's maximum and proves the bound for each, completing the induction.
4. Derivation of Previous Fast Rates Results and Extensions
The paper derives earlier fast-rate results from its framework and extends applicability beyond strongly convex objectives to smooth convex functions satisfying a gradient-growth condition.
- For strongly convex feasible sets with a gradient bounded below, the framework recovers the linear rate e^−Θ(t) established in earlier work.
- For arbitrary convex sets with an interior optimum, an interior-ball construction yields a linear convergence result under the stated smoothness and convexity assumptions.
- The central lemma requires only convexity and smoothness of the objective, not strong convexity, provided the objective satisfies the required gradient-growth condition.
- The resulting analysis applies to a convex feasibility problem for an underdetermined linear system, whose least-squares objective is smooth and convex but not strongly convex.
5. Examples of Strongly Convex Sets
The paper identifies norm-induced balls that are strongly convex and retain simple linear optimization oracles, covering ℓ_p, Schatten ℓ_p, and group-norm constructions.
- The section targets convex sets that are both strongly convex and compatible with simple, efficient linear optimization oracles.
- Sublevel-set and norm-squared lemmas provide strong-convexity guarantees for Euclidean and general norm balls.
- ℓ_p balls: For p ∈ (1, 2], ℓ_p balls admit a closed-form linear minimizer computed in time linear in the number of nonzeros of the objective.
- Schatten ℓ_p balls: For p ∈ (1, 2], Schatten ℓ_p balls are strongly convex with respect to the Frobenius norm and have a closed-form oracle based on the objective's singular value decomposition.
- Group-norm balls: Group-norm balls have a stated strong-convexity parameter and admit linear optimization in time linear in the number of nonzeros in the linear objective.
6. Conclusions and Open Problems
The paper establishes an accelerated O(1/t^2) Frank-Wolfe rate under strong convexity and identifies open questions about reaching linear rates and extending faster rates beyond strongly convex norm-induced balls.
- O(1/t^2) convergence is proved for smooth, strongly-convex optimization over strongly-convex sets, improving on the tight general-case rate.
- Various machine-learning regularization functions induce strongly convex sets, and previous fast-rate Frank-Wolfe results follow from the analysis.
- Projection/prox-based methods achieve O(log(1/ϵ)) for smooth strongly convex objectives, motivating the question of whether Frank-Wolfe can attain that rate on strongly convex sets.
- An open question is whether faster rates extend to norm-induced balls whose norms yield smooth rather than strongly convex functions, including ℓp balls for p > 2.
- A broader open problem is a linear-optimization-oracle method matching optimal projection/prox-based gradient rates across regimes, including nonsmooth problems.
A. Proof of Theorem 1
The proof of Theorem 1 uses the Frank-Wolfe update's optimal step size to establish an inductive error bound, beginning with a base case and splitting the induction into two cases.
- The proof fixes an iteration and invokes the smoothness of f to obtain the key one-step inequality.
- The optimal step size ensures h_{t+1} ≤ h_t, providing monotonicity used in the argument.
- For t = 1, choosing η_0 = 1 yields the base-case bound h_1 ≤ β_f D^2.
- The induction assumes h_t ≤ C/t and then considers two cases, including the regime h_t > C/(2t).
- The proof uses a constant K satisfying K^2 < C as part of the induction bounds.
B.1. Proof of Lemma 3
The proof of Lemma 3 establishes strong convexity through norm inequalities, a direct expansion, and the strong-convexity property of the underlying function.
- The proof starts with x, y ∈ E, γ ∈ [0, 1], and z ∈ E under the stated function-value constraints.
- The triangle inequality is applied to bound the norm of γx + (1 − γ)y + z.
- The argument then invokes that f is α-strongly convex with respect to the norm ∥·∥.
- An algebraic inequality involving a and b is used before substituting the resulting bound back into Eq. (11).
B.2. Proof of Corollary 1
The corollary proof applies the strong-convexity result to norm balls, using the parameter for ℓp balls and norm-based inequalities for vector and matrix cases.
- Strong convexity of the set with respect to ∥·∥p follows directly from Lemma 3.
- For B_p(r), the strong-convexity parameter is α = (p − 1)/r with respect to ∥·∥p.
- The proof considers p ∈ (1, 2] and vectors v ∈ R^n when establishing the needed norm inequality.
- For a vector z′ satisfying ∥z′∥F ≤ 1, the proof derives an additional bound used in the corollary.
- A further case is identified as (1/2 − 1/p)r-strongly convex with respect to ∥·∥2.
B.3. Proof of Lemma 5
The proof establishes strong-convexity properties for vector and matrix norm balls by combining dual norms, Hölder’s inequality, and strong-convexity/smoothness duality. It then specializes these results to mixed and Frobenius norms.
- Duality between ℓ_p and ℓ_q norms, together with Hölder’s inequality, verifies membership in the corresponding ℓ_p ball.The proof applies the same pattern to points x in B_p(r).
- The analogous argument for Schatten norms uses duality between ∥·∥S(p) and ∥·∥S(q) and verifies membership in B_S(p)(r).The construction first selects X and then proves that X lies in the required Schatten ball.
- For p, s ∈ (1, 2], Lemma 10 derives strong convexity of mixed matrix norms from smoothness and strong-convexity duality.The proof uses dual exponents z and q and the dual norm pair ∥·∥s,p and ∥·∥z,q.
- The proof transfers the mixed-norm result to the Frobenius norm using ∥·∥F ≡ ∥·∥2,2 and row-wise norm inequalities.For a matrix A, the Frobenius norm is bounded by an ℓ_p aggregation of row-wise ℓ_s norms.
- The mixed norm ∥·∥s,p is shown to be strongly convex with respect to itself, with a coefficient involving (s+p−2)r.The argument applies the resulting lemma to X, Y, γ, and a matrix Z constrained by ∥Z∥s,p ≤ 1.