Abstract: Assume a teacher provides examples (x_t,y_t) 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].

@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},
}

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