In most machine learning problems, we tend to think that training algorithms require more computation time as the number of training samples increases. In this paper we discuss two contexts in which this is not true. In the case of SVM optimization, assuming some desired generalization error, the PEGASOS algorithm statistically needs less runtime with more data. In the case of learning halfspaces over sparse vectors, more training examples reduce the training runtime from exponential to polynomial time.
Document link: https://www.ideals.illinois.edu/handle/2142/112789
citation:
@article{Miranda2015,
author = {Miranda, Brando and Wu, Michael and Sun, He},
keywords = {SVM,ai,algorithmic aspects of machine learning,artificial intelligence,machine learning,machine learning theory,pegasos,statistical machine learning,text},
month = {may},
title = {{Reducing Training Time with More Data - a Review}},
url = {https://www.ideals.illinois.edu/handle/2142/112789},
year = {2015}
}
or
Miranda, B., Wu, M., & Sun, H. (2015). Reducing Training Time with More Data - a Review. https://www.ideals.illinois.edu/handle/2142/112789