Stochastic Frank-Wolfe methods for nonconvex optimization

By Sashank J. Reddi, Suvrit Sra, Barnab'as P'oczos, Alex Smola. 2016

158 citations recorded by the source corpus.

We study Frank-Wolfe methods for nonconvex stochastic and finite-sum optimization problems. Frank-Wolfe methods (in the convex case) have gained tremendous recent interest in machine learning and optimization due to their projection-free property and their ability to exploit structured constraints. However, our understanding of these algorithms in the nonconvex setting is fairly limited. In this paper, we propose nonconvex stochastic Frank-Wolfe methods and analyze their convergence properties. Furthermore, for objective functions that decompose into a finite-sum, we leverage ideas from variance reduction for convex optimization to obtain new variance reduced nonconvex Frank-Wolfe methods that have provably faster convergence than the classical Frank-Wolfe method.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Automated Scalable Bayesian Inference via Hilbert Coresets (2017, background): “…taking inspiration from the large-scale optimization literature Frank and Wolfe (1956); Gu´elat and Marcotte (1986); Jaggi (2013); Lacoste-Julien and Jaggi (2015); Clarkson (2010); Reddi et al. (2016); Balasubramanian and Ghadimi (2018); Hazan and Luo (2016), we solve the convex optimization in Eq.”
Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization (2019, methodology): “Variance reduction methods have also been widely studied, see, e.g. [1, 5, 7, 10, 19, 21, 25, 26, 28].”
Projection-Free Adaptive Gradients for Large-Scale Optimization (2020, background): “Analyses of these algorithms in the nonconvex setting are provided in Reddi et al. (2016); Yurtsever et al. (2019); Xie et al. (2020).”
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].”
Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, background): “(Reddi et al. 2016) extends this and considers a stochastic version of FW for smooth non-convex functions.”
Fast incremental method for smooth nonconvex optimization (2016, methodology): “As a sequel to this paper, we now have extension to proximal nonsmooth nonconvex VR and stochastic Frank-Wolfe VR methods [21], [22].”