Efficient projections onto the l1-ball for learning in high dimensions

ABSTRACT

We describe efficient algorithms for projecting a vector onto the l₁-ball. We present two methods for projection. The first performs exact projection in O(n) expected time, where n is the dimension of the space. The second works on vectors k of whose elements are perturbed outside the l₁-ball, projecting in O(k log(n)) time. This setting is especially useful for online learning in sparse feature spaces such as text categorization applications. We demonstrate the merits and effectiveness of our algorithms in numerous batch and online learning tasks. We show that variants of stochastic gradient projection methods augmented with our efficient projection procedures outperform interior point methods, which are considered state-of-the-art optimization techniques. We also show that in online settings gradient updates with l₁ projections outperform the exponentiated gradient algorithm while obtaining models with high degrees of sparsity.

REFERENCES

• 1: Beck, A., & Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31, 167--175.
• 2: Bertsekas, D. (1999). Nonlinear programming. Athena Scientific.
• 3: Candes, E. J. (2006). Compressive sampling. Proc. of the Int. Congress of Math., Madrid, Spain.
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: Koby Crammer , Yoram Singer, On the Learnability and Design of Output Codes for Multiclass Problems, Machine Learning, v.47 n.2-3, p.201-233, May-June 2002 [doi>10.1023/A:1013637720281]
• 6: Donoho, D. (2006a). Compressed sensing. Technical Report, Stanford University.
• 7: Donoho, D. (2006b). For most large underdetermined systems of linear equations, the minimal l₁-norm solution is also the sparsest solution. Comm. Pure Appl. Math. 59.
• 8: Friedman, J., Hastie, T., & Tibshirani, R. (2007). Pathwise co-ordinate optimization. Annals of Applied Statistics, 1, 302--332.
• 9: Gafni, E., & Bertsekas, D. P. (1984). Two-metric projection methods for constrained optimization. SIAM Journal on Control and Optimization, 22, 936--964.
• 10: Hazan, E. (2006). Approximate convex optimization by online game playing. Unpublished manuscript.
• 11: Kim, S.-J., Koh, K., Lustig, M., Boyd, S., & Gorinevsky, D. (2007). An interior-point method for large-scale l₁-regularized least squares. IEEE Journal on Selected Topics in Signal Processing, 4, 606--617.
• 12: 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]
• 13: 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
• 14: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 15: Andrew Y. Ng, Feature selection, L₁ vs. L₂ regularization, and rotational invariance, Proceedings of the twenty-first international conference on Machine learning, p.78, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015435]
• 16: Shai Shalev-Shwartz , Yoram Singer, Efficient Learning of Label Ranking by Soft Projections onto Polyhedra, The Journal of Machine Learning Research, 7, p.1567-1599, 12/1/2006
• 17: 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]
• 18: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 19: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc B., 58, 267--288.
• 20: Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. Proceedings of the Twentieth International Conference on Machine Learning.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems; Curve, surface, solid, and object representations
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation; Feature evaluation and selection
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Design, Theory