Linearly Convergent Frank-Wolfe with Backtracking Line-Search.

By Fabian Pedregosa, Geoffrey Negiar, Armin Askari, Martin Jaggi. 2018

71 citations recorded by the source corpus.

Structured constraints in Machine Learning have recently brought the Frank-Wolfe (FW) family of algorithms back in the spotlight. While the classical FW algorithm has poor local convergence properties, the Away-steps and Pairwise FW variants have emerged as improved variants with faster convergence. However, these improved variants suffer from two practical limitations: they require at each iteration to solve a 1-dimensional minimization problem to set the step-size and also require the Frank-Wolfe linear subproblems to be solved exactly. In this paper, we propose variants of Away-steps and Pairwise FW that lift both restrictions simultaneously. The proposed methods set the step-size based on a sufficient decrease condition, and do not require prior knowledge of the objective. Furthermore, they inherit all the favorable convergence properties of the exact line-search version, including linear convergence for strongly convex functions over polytopes. Benchmarks on different machine learning problems illustrate large performance gains of the proposed variants.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “Recently, Pedregosa et al. [2020] analyze the rate of the Frank-Wolfe algorithm for smooth function, using backtracking line search , described in Algorithm 3, Appendix C. Algorithm 3 in Appendix C is adaptive to the local smoothness constant, and ensures L k +1 < 2 L f , L f being the smoothness…”
Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method (2021, methodology): “…criteria to measure the optimality errors at x k , which correspondingly associate with the subsequences S 1 and S 2 : For S 1 , we follow [38] to consider E S 1 ( x k ) as the so-called duality gap ⟨∇ f ( x k ) , x k − s k ⟩ , a standard practice within the framework of the Frank-Wolfe…”
Boosting Frank-Wolfe by Chasing Gradients (2020, result): “3 in the Appendix for AFW-L (Pedregosa et al., 2020).”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “In a nutshell, what Pedregosa et al. [69] do is perform a multiplicative search for L until the smoothness inequality Algorithmus 5 : (modiﬁed) Adaptive step-size strategy Unfortunately, checking (adaptive) in practice can be numerically very challenging as we mix function evaluations, gradient…”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, methodology): “We run the standard CG method with backtracking line search (Pedregosa et al., 2020) on the sparse logistic regression problem in (12).”
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization (2020, background): “In fact, many recent papers [10, 3, 37, 38, 20, 19, 39, 16, 40, 41] use a similar way of showing convergence by bounding the number of such ‘bad’ steps with dimension reduction arguments, which crucially rely on maintaining iterates as a convex combination of vertices.”