Boosting Frank-Wolfe by Chasing Gradients

By Cyrille W. Combettes, Sebastian Pokutta. 2020

34 citations recorded by the source corpus.

The Frank-Wolfe algorithm has become a popular first-order optimization algorithm for it is simple and projection-free, and it has been successfully applied to a variety of real-world problems. Its main drawback however lies in its convergence rate, which can be excessively slow due to naive descent directions. We propose to speed up the Frank-Wolfe algorithm by better aligning the descent direction with that of the negative gradient via a subroutine. This subroutine chases the negative gradient direction in a matching pursuit-style while still preserving the projection-free property. Although the approach is reasonably natural, it produces very significant results. We derive convergence rates $\mathcal{O}(1/t)$ to $\mathcal{O}(e^{-\omega t})$ of our method and we demonstrate its competitive advantage both per iteration and in CPU time over the state-of-the-art in a series of computational experiments.

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, background): “…many open questions remain in designing such optimal algorithmic schemes ( e.g. [Braun et al. 2017; Kerdreux et al. 2018b; Braun et al. 2018; Cyrille W Combettes et al. 2020b; Carderera et al. 2020; Mortagy et al. 2020; Cyrille W. Combettes et al. 2020a]) and in their theoretical…”
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization (2020, methodology): “Combettes and Pokutta [28] recently explored employing a FW subroutine to compute an approximate shadow direction, and then they consider that approximate shadow as their descent direction.”
Projection-Free Adaptive Gradients for Large-Scale Optimization (2020, background): “However, by doing so we may lose the precious properties of the descent directions of AdaGrad, as the directions returned by arg minv∈C〈Gt, v〉 can be significantly different from −Gt (Combettes and Pokutta, 2020); see Polyak (1987, Figure 32) for an early illustration of the phenomenon.”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “…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 Pokutta [23], Tsuji et al. [78]) and there is an…”