Starting Small - Learning with Adaptive Sample Sizes

Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1463-1471, 2016.

Abstract

For many machine learning problems, data is abundant and it may be prohibitive to make multiple passes through the full training set. In this context, we investigate strategies for dynamically increasing the effective sample size, when using iterative methods such as stochastic gradient descent. Our interest is motivated by the rise of variance-reduced methods, which achieve linear convergence rates that scale favorably for smaller sample sizes. Exploiting this feature, we show - theoretically and empirically - how to obtain significant speed-ups with a novel algorithm that reaches statistical accuracy on an n-sample in 2n, instead of n log n steps.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-daneshmand16, title = {Starting Small - Learning with Adaptive Sample Sizes}, author = {Daneshmand, Hadi and Lucchi, Aurelien and Hofmann, Thomas}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1463--1471}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/daneshmand16.pdf}, url = {https://proceedings.mlr.press/v48/daneshmand16.html}, abstract = {For many machine learning problems, data is abundant and it may be prohibitive to make multiple passes through the full training set. In this context, we investigate strategies for dynamically increasing the effective sample size, when using iterative methods such as stochastic gradient descent. Our interest is motivated by the rise of variance-reduced methods, which achieve linear convergence rates that scale favorably for smaller sample sizes. Exploiting this feature, we show - theoretically and empirically - how to obtain significant speed-ups with a novel algorithm that reaches statistical accuracy on an n-sample in 2n, instead of n log n steps.} }
Endnote
%0 Conference Paper %T Starting Small - Learning with Adaptive Sample Sizes %A Hadi Daneshmand %A Aurelien Lucchi %A Thomas Hofmann %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-daneshmand16 %I PMLR %P 1463--1471 %U https://proceedings.mlr.press/v48/daneshmand16.html %V 48 %X For many machine learning problems, data is abundant and it may be prohibitive to make multiple passes through the full training set. In this context, we investigate strategies for dynamically increasing the effective sample size, when using iterative methods such as stochastic gradient descent. Our interest is motivated by the rise of variance-reduced methods, which achieve linear convergence rates that scale favorably for smaller sample sizes. Exploiting this feature, we show - theoretically and empirically - how to obtain significant speed-ups with a novel algorithm that reaches statistical accuracy on an n-sample in 2n, instead of n log n steps.
RIS
TY - CPAPER TI - Starting Small - Learning with Adaptive Sample Sizes AU - Hadi Daneshmand AU - Aurelien Lucchi AU - Thomas Hofmann BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-daneshmand16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1463 EP - 1471 L1 - http://proceedings.mlr.press/v48/daneshmand16.pdf UR - https://proceedings.mlr.press/v48/daneshmand16.html AB - For many machine learning problems, data is abundant and it may be prohibitive to make multiple passes through the full training set. In this context, we investigate strategies for dynamically increasing the effective sample size, when using iterative methods such as stochastic gradient descent. Our interest is motivated by the rise of variance-reduced methods, which achieve linear convergence rates that scale favorably for smaller sample sizes. Exploiting this feature, we show - theoretically and empirically - how to obtain significant speed-ups with a novel algorithm that reaches statistical accuracy on an n-sample in 2n, instead of n log n steps. ER -
APA
Daneshmand, H., Lucchi, A. & Hofmann, T.. (2016). Starting Small - Learning with Adaptive Sample Sizes. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1463-1471 Available from https://proceedings.mlr.press/v48/daneshmand16.html.

Related Material