Projection-Free Adaptive Gradients for Large-Scale Optimization

By Cyrille W. Combettes, Christoph Spiegel, Sebastian Pokutta. 2020

13 citations recorded by the source corpus.

The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. Starting from the design of adaptive gradient algorithms, we propose to solve the occurring constrained optimization subproblems \emph{very} incompletely via a fixed and small number of iterations of the Frank-Wolfe algorithm (often times only $2$ iterations), in order to preserve the low per-iteration complexity. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives.

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

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “They form a practical family of algorithms [Jaggi 2013; Bojanowski et al. 2014; Alayrac et al. 2016; Seguin et al. 2016; Peyre et al. 2017; Miech x k +1 = (1 − γ t ) x k + γ k v k ⊲ Convex update 5: end for et al. 2018; Lacoste-Julien et al. 2015b; Courty et al. 2016; Paty et al. 2019; Luise et al. ”
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].”