Solving large scale linear prediction problems using stochastic gradient descent algorithms

TLDR

Linear prediction methods such as least squares, logistic regression, and support vector machines are widely used in statistics and machine learning, are efficient and simple to implement, and are related to online algorithms like the perceptron. The study investigates stochastic gradient descent algorithms applied to regularized linear prediction methods. The authors analyze SGD on regularized linear prediction models, derive numerical convergence rates, discuss implications, and plan experiments on text data to illustrate the theoretical findings. The analysis yields numerical convergence rates for SGD on regularized linear prediction, underscoring its practical effectiveness.

Abstract

Linear prediction methods, such as least squares for regression, logistic regression and support vector machines for classification, have been extensively used in statistics and machine learning. In this paper, we study stochastic gradient descent (SGD) algorithms on regularized forms of linear prediction methods. This class of methods, related to online algorithms such as perceptron, are both efficient and very simple to implement. We obtain numerical rate of convergence for such algorithms, and discuss its implications. Experiments on text data will be provided to demonstrate numerical and statistical consequences of our theoretical findings.