Frank-Wolfe Style Algorithms for Large Scale Optimization
This work addresses scalability issues in large-scale optimization for researchers and practitioners, but it is incremental as it builds on the standard Frank-Wolfe algorithm.
The authors tackled the challenge of scaling Frank-Wolfe algorithms to enormous optimization problems by introducing variants that use stochastic gradients, approximate subproblem solutions, and sketched decision variables, achieving an optimal convergence rate of O(1/k) up to constants.
We introduce a few variants on Frank-Wolfe style algorithms suitable for large scale optimization. We show how to modify the standard Frank-Wolfe algorithm using stochastic gradients, approximate subproblem solutions, and sketched decision variables in order to scale to enormous problems while preserving (up to constants) the optimal convergence rate $\mathcal{O}(\frac{1}{k})$.