Projection-Free Adaptive Gradients for Large-Scale Optimization
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Minimizing finite sums with the stochastic average gradientMathematical Programming, 2016
- Conditional Gradient Sliding for Convex OptimizationSIAM Journal on Optimization, 2016
- Text Categorization Based on Regularized Linear Classification MethodsInformation Retrieval Journal, 2001
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998