Block-Coordinate Frank-Wolfe Optimization for Structural SVMs

Abstract

We propose a randomized block-coordinate variant of the classic Frank-Wolfe algorithm for convex optimization with block-separable constraints. Despite its lower iteration cost, we show that it achieves a similar convergence rate in duality gap as the full Frank-Wolfe algorithm. We also show that, when applied to the dual structural support vector machine (SVM) objective, this yields an online algorithm that has the same low iteration complexity as primal stochastic subgradient methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe algorithm allows us to compute the optimal step-size and yields a computable duality gap guarantee. Our experiments indicate that this simple algorithm outperforms competing structural SVM solvers.

Appears in Proceedings of the 30th International Conference on Machine Learning (ICML 2013). 9 pages main text + 22 pages appendix. Changes from v3 to v4: 1) Re-organized appendix; improved & clarified duality gap proofs; re-drew all plots; 2) Changed convention for Cf definition; 3) Added weighted averaging experiments + convergence results; 4) Clarified main text and relationship with appendix

References in corpus (5)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Introduction to the CoNLL-2000 Shared Task: Chunking
• Proximal Stochastic Dual Coordinate Ascent
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (25)

• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Proximal Stochastic Dual Coordinate Ascent
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Binary Quadratic Programing for Online Tracking of Hundreds of People in Extremely Crowded Scenes
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Metric Learning for Temporal Sequence Alignment
• A Random Block-Coordinate Douglas-Rachford Splitting Method with Low Computational Complexity for Binary Logistic Regression
• End-to-End Learning for Structured Prediction Energy Networks
• Randomized Block Frank-Wolfe for Convergent Large-Scale Learning
• A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
• Optimal Margin Distribution Machine
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
• Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem
• Safe Screening for the Generalized Conditional Gradient Method
• Lazifying Conditional Gradient Algorithms
• Integrated Inference and Learning of Neural Factors in Structural Support Vector Machines
• Zeroth-Order Stochastic Block Coordinate Type Methods for Nonconvex Optimization
• Distributed Block-diagonal Approximation Methods for Regularized Empirical Risk Minimization
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly max-Oracle
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
• Primal-Dual Block Frank-Wolfe
• Frank-Wolfe variants for minimization of a sum of functions