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 (3)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Proximal Stochastic Dual Coordinate Ascent
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (5)

• Proximal Stochastic Dual Coordinate Ascent
• Metric Learning for Temporal Sequence Alignment
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
• A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly max-Oracle