@inproceedings{3e5223fd0ffb49fcb09f6980ae1d3b29,
title = "Characterizing inverse time dependency in multi-class learning",
abstract = "The training time of most learning algorithms increases as the size of training data increases. Yet, recent advances in linear binary SVM and LR challenge this commonsense by proposing an inverse dependency property, where the training time decreases as the size of training data increases. In this paper, we study the inverse dependency property of multi-class classification problem. We describe a general framework for multi-class classification problem with a single objective to achieve inverse dependency and extend it to three popular multi-class algorithms. We present theoretical results demonstrating its convergence and inverse dependency guarantee. We conduct experiments to empirically verify the inverse dependency of all the three algorithms on large-scale datasets as well as to ensure the accuracy.",
keywords = "Inverse dependency, Large-scale classification, Multi-class learning, Supervised learning",
author = "Danqi Chen and Weizhu Chen and Qiang Yang",
year = "2011",
doi = "10.1109/ICDM.2011.32",
language = "English (US)",
isbn = "9780769544083",
series = "Proceedings - IEEE International Conference on Data Mining, ICDM",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1020--1025",
booktitle = "Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011",
address = "United States",
note = "11th IEEE International Conference on Data Mining, ICDM 2011 ; Conference date: 11-12-2011 Through 14-12-2011",
}