Frank-Wolfe variants for minimization of a sum of functions

2018/05/25 by Suhail M. Shah, Shah, Suhail M
Computer Science · Engineering · Mathematics · #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1805.10200

Abstract

We propose several variants of the Frank-Wolfe algorithm to minimize a sum of functions. The main proposed algorithm is inspired from the dual averaging scheme of Nesterov adapted for Frank Wolfe in a stochastic setting. A distributed version of this scheme is also suggested. Additionally, we propose a Frank-Wolfe variant based on incremental gradient techniques. The convergence rates for all the proposed algorithms are established. The performance is studied on least squares regression and multinomial classification.

Citations

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Primal-dual subgradient methods for convex problems
• Optimization Methods for Large-Scale Machine Learning

Related

• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features
• Frank-Wolfe Methods in Probability Space
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
• Frank-Wolfe Style Algorithms for Large Scale Optimization
• Stochastic Frank-Wolfe Methods for Nonconvex Optimization