Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We describe and analyze two stochastic methods for l₁ regularized loss minimization problems, such as the Lasso. The first method updates the weight of a single feature at each iteration while the second method updates the entire weight vector but only uses a single training example at each iteration. In both methods, the choice of feature/example is uniformly at random. Our theoretical runtime analysis suggests that the stochastic methods should outperform state-of-the-art deterministic approaches, including their deterministic counterparts, when the size of the problem is large. We demonstrate the advantage of stochastic methods by experimenting with synthetic and natural data sets.

REFERENCES

• 1: Beck, A., & Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31, 167--175.
• 2: Bottou, L. (Web Page). Stochastic gradient descent examples. http://leon.bottou.org/projects/sgd.
• 3: Bottou, L., & Bousquet, O. (2008). The tradeoffs of large scale learning. Advances in Neural Information Processing Systems 20 (pp. 161--168).
• 4: Léon Bottou , Yann Le Cun, On-line learning for very large data sets: Research Articles, Applied Stochastic Models in Business and Industry, v.21 n.2, p.137-151, March 2005 [doi>10.1002/asmb.v21:2]
• 5: Kenneth L. Clarkson, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.922-931, January 20-22, 2008, San Francisco, California
• 6: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 7: John Duchi , Shai Shalev-Shwartz , Yoram Singer , Tushar Chandra, Efficient projections onto the l₁-ball for learning in high dimensions, Proceedings of the 25th international conference on Machine learning, p.272-279, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390191]
• 8: Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. Ann. Statist., 32, 407--499.
• 9: Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Res. Logist. Quart., 3, 95--110.
• 10: Friedman, J., Hastie, T., & Tibshirani, R. (2008). Regularized paths for generalized linear models via coordinate descent (Technical Report). Department of Statistics, Stanford University.
• 11: Genkin, A., Lewis, D., & Madigan, D. (2007). Large-scale Bayesian logistic regression for text categorization. Technometrics, 49, 291--304.
• 12: Claudio Gentile, The Robustness of the p-Norm Algorithms, Machine Learning, v.53 n.3, p.265-299, December 2003 [doi>10.1023/A:1026319107706]
• 13: Adam J. Grove , Nick Littlestone , Dale Schuurmans, General Convergence Results for Linear Discriminant Updates, Machine Learning, v.43 n.3, p.173-210, June 2001 [doi>10.1023/A:1010844028087]
• 14: Jyrki Kivinen , Manfred K. Warmuth, Exponentiated gradient versus gradient descent for linear predictors, Information and Computation, v.132 n.1, p.1-63, Jan. 10, 1997 [doi>10.1006/inco.1996.2612]
• 15: Kwangmoo Koh , Seung-Jean Kim , Stephen Boyd, An Interior-Point Method for Large-Scale l₁-Regularized Logistic Regression, The Journal of Machine Learning Research, 8, p.1519-1555, 12/1/2007
• 16: Langford, J., Li, L., & Zhang, T. (2009). Sparse online learning via truncated gradient. Advances in Neural Information Processing Systems 21 (pp. 905--912).
• 17: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 18: Z. Q. Luo , P. Tseng, On the convergence of the coordinate descent method for convex differentiable minimization, Journal of Optimization Theory and Applications, v.72 n.1, p.7-35, Jan., 1992 [doi>10.1007/BF00939948]
• 19: Shai Shalev-Shwartz , Yoram Singer , Nathan Srebro, Pegasos: Primal Estimated sub-GrAdient SOlver for SVM, Proceedings of the 24th international conference on Machine learning, p.807-814, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273598]
• 20: Shai Shalev-Shwartz , Nathan Srebro, SVM optimization: inverse dependence on training set size, Proceedings of the 25th international conference on Machine learning, p.928-935, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390273]
• 21: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc B., 58, 267--288.
• 22: Tseng, P., & Yun, S. (2009). A block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. J. Optim. Theory Appl., 140, 513--535.
• 23: Wu, T. T., & Lange, K. (2008). Coordinate descent algorithms for lasso penalized regression. Annals of Applied Statistics, 2, 224--244.
• 24: Zhang, T. (2003). Sequential greedy approximation for certain convex optimization problems. IEEE Transaction on Information Theory, 49, 682--691.
• 25: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory