Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets

By Dan Garber, Elad Hazan. 2014

207 citations recorded by the source corpus.

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 1/t2. This gives a quadratic improvement in convergence rate compared to the general case, in which convergence is of the order 1/t, and known to be tight. We show that various balls induced by lp 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 fastrate results for the FW method follow easily from our analysis.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “We now recall the deﬁnitions of smoothness and strong convexity of a function w.r.t. a distance function ω . where This deﬁnition extends the one of strongly convex sets with a general distance function that may not be a norm, see for instance [Garber et al. 2015].”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “More recently, Garber and Hazan (2015) proved a sublinear rate O (1 /t 2 ) by re-placing the lower bound on the gradient by a strong convexity assumption on the function.”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, background): “convex constraint sets, under the strong requirement that the gradient norm is not too small (see [11] for a discussion).”
Projection-Free Optimization on Uniformly Convex Sets (2020, methodology): “We now generalize this result by relaxing the strong convexity of the constraint set C and the quadratic error bound on f (Garber and Hazan, 2015, (1)).”
Frank-Wolfe with Subsampling Oracle (2018, background): “Can this be extended to linearly-convergent FW algorithms (Lacoste-Julien & Jaggi, 2013; 2015; Garber & Hazan, 2015)?”
Curvature of Feasible Sets in Offline and Online Optimization (2020, methodology): “Recently, [18] showed that when the feasible set is strongly convex and the objective function is a strongly convex function (see Definition 3), the Frank-Wolfe method has accelerated convergence rate O( 1 t2 ).”
Complexity of Linear Minimization and Projection on Some Sets (2021, background): “Faster rates can be established under additional assumptions on the properties of f or the geometry of C [41, 23, 20, 31].”
Complexity bounds for primal-dual methods minimizing the model of objective function (2017, background): “Previously known acceleration is related to strong convexity of the domain (see [6]).”
Boosting Frank-Wolfe by Chasing Gradients (2020, background): “For example, the least squares loss x ∈ R 7→ ‖Ax − b‖2 where A ∈ Rm×n and rank(A) = m < n is not strongly convex, however it is gradient dominated (Garber and Hazan, 2015).”
On the Effectiveness of Richardson Extrapolation in Machine Learning (2020, unknown): “It would also be interesting to consider the beneﬁts for Richardson extrapolation for strongly-convex sets (Garber and Hazan, 2015).”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, background): “, [29], [45]) under Hölderian error bound conditions, to interpolate between the well known O(1/k) rate for general convex objectives and the faster rates for strongly convex ones proved in [19] and [30].”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “Moreover, there has been a proliferation of modiﬁcations to these methods, addressing many of their historical limitations (see, e.g., Freund et al. [35], Lacoste-Julien and Jaggi [53], Garber and Hazan [37, 38], Lan et al. [56], Braun et al. [12], Braun et al. [14], Braun et al. [13], Combettes…”
Stochastic Frank-Wolfe methods for nonconvex optimization (2016, background): “There have been several recent works on improving the convergence rates under additional assumptions [7], [16].”
Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (2016, methodology): “In a follow-up work, Lacoste-Julien and Jaggi [15, 16] gave a refined affine-invariant analysis of an algorithm presented in [8] which also uses away steps, and showed that it also converges exponentially fast in the same setting as the Garber-Hazan result.”
Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, methodology): “…tasks rely on norm constraints that are strongly convex, e.g., generalized linear models with l p norm, squared loss regression with l p norm, multitask learning with Group Matrix norm, and matrix completion with Schatten norm (Kim and Xing 2010; Garber and Hazan 2015; Hazan and others 2016).”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, methodology): “Many previous works (e.g., (Levitin and Polyak, 1966; Demyanov and Rubinov, 1970; Dunn, 1979; Garber and Hazan, 2015)) considered this condition of feasible set when studying the FW method.”
Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees (2015, background): “For these theoretical results we assume that f belongs to a finite-dimensional RKHSH, in line with recent literature [2, 10, 17, 18].”