Frank-Wolfe with Subsampling Oracle

By Thomas Kerdreux, Fabian Pedregosa, Alexandre d'Aspremont. 2018

20 citations recorded by the source corpus.

We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small \emph{subset} of the original domain. The first algorithm that we propose is a randomized variant of the original FW algorithm and achieves a $\mathcal{O}(1/t)$ sublinear convergence rate as in the deterministic counterpart. The second algorithm is a randomized variant of the Away-step FW algorithm, and again as its deterministic counterpart, reaches linear (i.e., exponential) convergence rate making it the first provably convergent randomized variant of Away-step FW. In both cases, while subsampling reduces the convergence rate by a constant factor, the linear minimization step can be a fraction of the cost of that of the deterministic versions, especially when the data is streamed. We illustrate computational gains of the algorithms on regression problems, involving both $\ell_1$ and latent group lasso penalties.

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

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “…al. 2016; Paty et al. 2019; Luise et al. 2019]; however, 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…”
Boosting Frank-Wolfe by Chasing Gradients (2020, background): “It could also be interesting to investigate how to make each oracle call cheaper via, e.g., lazification (Braun et al., 2017) or subsampling (Kerdreux et al., 2018).”
Linearly Convergent Frank-Wolfe with Backtracking Line-Search. (2018, methodology): “A possible extension of this work is to develop back-tracking step-size strategies for randomized variants of FW such as (Lacoste-Julien et al., 2013; Kerdreux et al., 2018; Mokhtari et al., 2018), in which there is stochasticity in the linear subproblems.”
Blended Conditional Gradients: the unconditioning of conditional gradients (2018, methodology): “The use of an inexpensive oracle based on a subset of the vertices of P , as an alternative to the full LP oracle, has been considered in Kerdreux et al. [2018b].”