Linear Convergence of Stochastic Frank Wolfe Variants

2017/03/21 by Donald Goldfarb, Goldfarb, Donald, Garud Iyengar +3 · 4 citations
Computer Science · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Neural Networks and Applications #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1703.07269

openalex publication_date 2017/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we show that the Away-step Stochastic Frank-Wolfe Algorithm (ASFW) and Pairwise Stochastic Frank-Wolfe algorithm (PSFW) converge linearly in expectation. We also show that if an algorithm convergences linearly in expectation then it converges linearly almost surely. In order to prove these results, we develop a novel proof technique based on concepts of empirical processes and concentration inequalities. Such a technique has rarely been used to derive the convergence rates of stochastic optimization algorithms. In large-scale numerical experiments, ASFW and PSFW perform as well as or better than their stochastic competitors in actual CPU time.

Cited by

• MEMOIR: Multi-class Extreme Classification with Inexact Margin
• A Fully Adaptive Frank-Wolfe Algorithm for Relatively Smooth Problems and Its Application to Centralized Distributed Optimization
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity

Related

• A New Convergence Analysis of Two Stochastic Frank-Wolfe Algorithms
• Stochastic Frank-Wolfe: Unified Analysis and Zoo of Special Cases
• Stochastic Frank-Wolfe Methods for Nonconvex Optimization
• Frank-Wolfe Style Algorithms for Large Scale Optimization
• Exponential Concentration in Stochastic Approximation