Least Squares Revisited: Scalable Approaches for Multi-class Prediction

Alekh Agarwal, Sham Kakade, Nikos Karampatziakis, Le Song, Gregory Valiant
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):541-549, 2014.

Abstract

This work provides simple algorithms for multi-class (and multi-label) prediction in settings where both the number of examples n and the data dimension d are relatively large. These robust and parameter free algorithms are essentially iterative least-squares updates and very versatile both in theory and in practice. On the theoretical front, we present several variants with convergence guarantees. Owing to their effective use of second-order structure, these algorithms are substantially better than first-order methods in many practical scenarios. On the empirical side, we show how to scale our approach to high dimensional datasets, achieving dramatic computational speedups over popular optimization packages such as Liblinear and Vowpal Wabbit on standard datasets (MNIST and CIFAR-10), while attaining state-of-the-art accuracies.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-agarwala14, title = {Least Squares Revisited: Scalable Approaches for Multi-class Prediction}, author = {Agarwal, Alekh and Kakade, Sham and Karampatziakis, Nikos and Song, Le and Valiant, Gregory}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {541--549}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/agarwala14.pdf}, url = {https://proceedings.mlr.press/v32/agarwala14.html}, abstract = {This work provides simple algorithms for multi-class (and multi-label) prediction in settings where both the number of examples n and the data dimension d are relatively large. These robust and parameter free algorithms are essentially iterative least-squares updates and very versatile both in theory and in practice. On the theoretical front, we present several variants with convergence guarantees. Owing to their effective use of second-order structure, these algorithms are substantially better than first-order methods in many practical scenarios. On the empirical side, we show how to scale our approach to high dimensional datasets, achieving dramatic computational speedups over popular optimization packages such as Liblinear and Vowpal Wabbit on standard datasets (MNIST and CIFAR-10), while attaining state-of-the-art accuracies.} }
Endnote
%0 Conference Paper %T Least Squares Revisited: Scalable Approaches for Multi-class Prediction %A Alekh Agarwal %A Sham Kakade %A Nikos Karampatziakis %A Le Song %A Gregory Valiant %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-agarwala14 %I PMLR %P 541--549 %U https://proceedings.mlr.press/v32/agarwala14.html %V 32 %N 2 %X This work provides simple algorithms for multi-class (and multi-label) prediction in settings where both the number of examples n and the data dimension d are relatively large. These robust and parameter free algorithms are essentially iterative least-squares updates and very versatile both in theory and in practice. On the theoretical front, we present several variants with convergence guarantees. Owing to their effective use of second-order structure, these algorithms are substantially better than first-order methods in many practical scenarios. On the empirical side, we show how to scale our approach to high dimensional datasets, achieving dramatic computational speedups over popular optimization packages such as Liblinear and Vowpal Wabbit on standard datasets (MNIST and CIFAR-10), while attaining state-of-the-art accuracies.
RIS
TY - CPAPER TI - Least Squares Revisited: Scalable Approaches for Multi-class Prediction AU - Alekh Agarwal AU - Sham Kakade AU - Nikos Karampatziakis AU - Le Song AU - Gregory Valiant BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-agarwala14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 541 EP - 549 L1 - http://proceedings.mlr.press/v32/agarwala14.pdf UR - https://proceedings.mlr.press/v32/agarwala14.html AB - This work provides simple algorithms for multi-class (and multi-label) prediction in settings where both the number of examples n and the data dimension d are relatively large. These robust and parameter free algorithms are essentially iterative least-squares updates and very versatile both in theory and in practice. On the theoretical front, we present several variants with convergence guarantees. Owing to their effective use of second-order structure, these algorithms are substantially better than first-order methods in many practical scenarios. On the empirical side, we show how to scale our approach to high dimensional datasets, achieving dramatic computational speedups over popular optimization packages such as Liblinear and Vowpal Wabbit on standard datasets (MNIST and CIFAR-10), while attaining state-of-the-art accuracies. ER -
APA
Agarwal, A., Kakade, S., Karampatziakis, N., Song, L. & Valiant, G.. (2014). Least Squares Revisited: Scalable Approaches for Multi-class Prediction. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):541-549 Available from https://proceedings.mlr.press/v32/agarwala14.html.

Related Material