Convergence Rate of Frank-Wolfe for Non-Convex Objectives

By Simon Lacoste-Julien. 2016

225 citations recorded by the source corpus.

We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of $O(1/\sqrt{t})$ on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gradient methods (though on slightly different measures of stationarity).

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Joint Discovery of Object States and Manipulation Actions (2017, methodology): “Moreover, [28] recently showed that the Frank-Wolfe algorithm with line-search converges to a stationary point for non-convex objectives at a rate of”
Unsupervised Learning from Narrated Instruction Videos (2015, background): “However, the standard convergence proof for Frank-Wolfe can easily be extended to show that it converges at a rate of O (1 / √ k ) to a stationary point on non-convex objectives [33].”
Towards Practical Differentially Private Convex Optimization (2019, background): “The Frank-Wolfe algorithm [25] has also seen a resurgence lately [26], [27], [28], [29].”
Optimal Transport for structured data with application on graphs (2018, background): “While the problem is non convex, conditional gradient is known to converge to a local stationary point (Lacoste-Julien, 2016).”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “…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 and…”
Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, methodology): “(Lacoste-Julien 2016) proves that FW for smooth non-convex functions converges to a stationary point, at a rate of O( 1 √ t ),”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, methodology): “Such an assumption is common in the analysis of the CG method and has the advantage of being affineinvariant, e.g., see (Jaggi, 2013; Lacoste-Julien, 2016).”
Fast Cluster Detection in Networks by First Order Optimization (2021, methodology): “We adapt the well known FW gap ([10], [22]) to the maximization case, thus obtaining the following measure of stationarity G(w) := max y∈Q ∇f(w)(w − y) = max a∈A ∇f(w)(w − a) = max a∈A −λa(w) , (4.”
Stochastic Frank-Wolfe methods for nonconvex optimization (2016, methodology): “Theorem 1 (Lacoste-Julien, 2016)).”
Linearly Convergent Frank-Wolfe with Backtracking Line-Search. (2018, methodology): “The next result states the linear convergence of some algorithm variants and uses the notions of pyramidal width (PWidth) and minimal directional width (mDW) that have been developed in (Lacoste-Julien, 2016) and (Locatello et al., 2017) respectively, which we state in Appendix B for completeness.”
Complexity of Linear Minimization and Projection on Some Sets (2021, background): “When f is nonconvex, [35] showed that FW converges to a stationary point at a rate O(1/ √ t) in the gap maxv∈C〈xt − v,∇f(xt)〉 [28], which has inspired a line of work in stochastic optimization [48, 52, 51, 10, 53].”
Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection (2020, unknown): “As we discuss in Appendix 9, Assumption 2 can be shown to be equivalent to the interior point condition of Frank-Wolfe algorithm (Bach et al., 2012; Lacoste-Julien, 2016; Chen et al., 2012).”
Learning from Narrated Instruction Videos (2015, background): “Wolfe can easily be extended to show that it converges at a rate of Oð1= ffiffiffi k p Þ to a stationary point on non-convex objectives [18].”