Semi-Stochastic Frank-Wolfe Algorithms with Away-Steps for Block-Coordinate Structure Problems

2016/02/04 by Donald Goldfarb, Goldfarb, Donald, Garud Iyengar +3
Computer Science · Decision Sciences · Engineering · Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Probabilistic and Robust Engineering Design #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1602.01543

openalex publication_date 2016/02/04 · arxiv created 2016/02/12 · arxiv updated 2016/02/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We propose a semi-stochastic Frank-Wolfe algorithm with away-steps for regularized empirical risk minimization and extend it to problems with block-coordinate structure. Our algorithms use adaptive step-size and we show that they converge linearly in expectation. The proposed algorithms can be applied to many important problems in statistics and machine learning including regularized generalized linear models, support vector machines and many others. In preliminary numerical tests on structural SVM and graph-guided fused LASSO, our algorithms outperform other competing algorithms in both iteration cost and total number of data passes.

Citations

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Smoothing Proximal Gradient Method for General Structured Sparse Learning
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization

Related

• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization
• Frank-Wolfe with Subsampling Oracle
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization