Solving large scale linear prediction problems using stochastic gradient descent algorithms

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.

REFERENCES

• 1: Nicoló Cesa-Bianchi, Analysis of two gradient-based algorithms for on-line regression, Journal of Computer and System Sciences, v.59 n.3, p.392-411, Dec. 1999 [doi>10.1006/jcss.1999.1635 ]
• 2: Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.1-8, July 06, 2002 [doi>10.3115/1118693.1118694]
• 3: Yoav Freund , Robert E. Schapire, Large Margin Classification Using the Perceptron Algorithm, Machine Learning, v.37 n.3, p.277-296, Dec. 1999 [doi>10.1023/A:1007662407062 ]
• 4: Jyrki Kivinen , Alex J. Smola , Robert C. Williamson, Large Margin Classification for Moving Targets, Proceedings of the 13th International Conference on Algorithmic Learning Theory, p.113-127, November 24-26, 2002
• 5: J. Kivinen , M. K. Warmuth, Relative Loss Bounds for Multidimensional Regression Problems, Machine Learning, v.45 n.3, p.301-329, December 2001 [doi>10.1023/A:1017938623079 ]
• 6: Kushner, H. J., & Yin, G. G. (1997). Stochastic approximation algorithms and applications. New York: Springer-Verlag.
• 7: Li, F., & Yang, Y. (2003). A loss function analysis for classification methods in text categorization. ICML 03 (pp. 472--479).
• 8: B. T. Polyak , A. B. Juditsky, Acceleration of stochastic approximation by averaging, SIAM Journal on Control and Optimization, v.30 n.4, p.838-855, July 1992 [doi>10.1137/0330046]
• 9: Rosenblatt, F. (1962). Principles of neurodynamics: Perceptrons and the theory of brain mechanisms. New York: Spartan.
• 10: Tong Zhang , Frank J. Oles, Text Categorization Based on Regularized Linear Classification Methods, Information Retrieval, v.4 n.1, p.5-31, April 2001 [doi>10.1023/A:1011441423217 ]