Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
By: Researcher II
Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).
| Authors | Simon Lacoste-Julien, Martin Jaggi, Mark W. Schmidt, Patrick Pletscher |
| Journal/Conference Name | INTERNATIONAL CONFERENCE ON MACHINE LEARNING |
| Paper Category | Computer Science |
| Paper 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. |
| Date of publication | 2013 |
| Code Programming Language | MATLAB |
| Comment |
Copyright Researcher II 2022