Least Squares Revisited: Scalable Approaches for Multi-class Prediction

By Alekh Agarwal, Sham M. Kakade, Nikos Karampatziakis, Le Song, Gregory Valiant. 2013

31 citations recorded by the source corpus.

This work provides simple algorithms for multiclass (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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, methodology): “We use the multi-class regularized least squares classiﬁcation model which is known to have comparable performance to SVMs (Rifkin and Klautau, 2004; Agarwal et al., 2014) but can be trained signiﬁcantly faster.”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, methodology): “adient algorithm, and they may be further rened with more sophisticated techniques and analysis. For example, techniques for reducing variance of SGD proposed in [37], mini-batch and preconditioning [41, 42] can be used to reduce the constant factors in the bound signicantly. Theorem 4 also reveals ”
Hyperband: Bandit-Based Configuration Evaluation for Hyperparameter Optimization (2016, methodology): “We use the multi-class regularized least squares classiﬁcation model which is known to have comparable performance to SVMs (Rifkin & Klautau, 2004; Agarwal et al., 2014) but can be trained signiﬁcantly faster.”