Decomposition-Invariant Conditional Gradient for General Polytopes with Line Search
Mohammad Ali Bashiri, Xinhua Zhang
Abstract
Frank-Wolfe (FW) algorithms with linear convergence rates have recently achieved great efficiency in many applications. Garber and Meshi (2016) designed a new decomposition-invariant pairwise FW variant with favorable dependency on the domain geometry. Unfortunately, it applies only to a restricted class of polytopes and cannot achieve theoretical and practical efficiency at the same time. In this paper, we show that by employing an away-step update, similar rates can be generalized to arbitrary polytopes with strong empirical performance. A new "condition number" of the domain is introduced which allows leveraging the sparsity of the solution. We applied the method to a reformulation of SVM, and the linear convergence rate depends, for the first time, on the number of support vectors.
BibTeX
@inproceedings{NIPS2017_99adff45,
author = {Bashiri, Mohammad Ali and Zhang, Xinhua},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Decomposition-Invariant Conditional Gradient for General Polytopes with Line Search},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/99adff456950dd9629a5260c4de21858-Paper.pdf},
volume = {30},
year = {2017}
}