Guarantees for Approximate Incremental SVMs

Abstract: Assume a teacher provides examples (xt,yt) one by one. An approximate incremental SVM computes a sequence of classifiers that are close to the true SVM solutions computed on the successive incremental training sets. We show that simple algorithms can satisfy an averaged accuracy criterion with a computational cost that scales as well as the best SVM algorithms with the number of examples. Finally, we exhibit some experiments highlighting the benefits of joining fast incremental optimization and curriculum and active learning [Schohn and Cohn, 2000, Bordes et al., 2005, Bengio et al., 2009].

Nicolas Usunier, Antoine Bordes and Léon Bottou: Guarantees for Approximate Incremental SVMs, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 9:884-891, Edited by Yee Whye Teh and Mike Titterington, Chia Laguna Resort, Sardinia, Italy, May 2010.

aistat-2010.djvu aistat-2010.pdf aistat-2010.ps.gz 

@inproceedings{usunier-bordes-bottou-2010,
  author = {Usunier, Nicolas and Bordes, Antoine and Bottou, L\'{e}on},
  title = {Guarantees for Approximate Incremental SVMs},
  booktitle = {Proceedings of the Thirteenth International 
               Conference on Artificial Intelligence and Statistics},
  pages = {884-891},
  year = {2010},
  editor = {Teh, Yee Whye and Titterington, Mike},
  volume = {9},
  address = {Chia Laguna Resort, Sardinia, Italy},
  month = {May},
  url = {http://leon.bottou.org/papers/usunier-bordes-bottou-2010},
}

Notes

This paper finally explains why the Huller, LASVM, and LaRank algorithms nearly match their batch counterparts after performing a single pass on the dataset.