Efficient Euclidean projections in linear time

ABSTRACT

We consider the problem of computing the Euclidean projection of a vector of length n onto a closed convex set including the l₁ ball and the specialized polyhedra employed in (Shalev-Shwartz & Singer, 2006). These problems have played building block roles in solving several l₁-norm based sparse learning problems. Existing methods have a worst-case time complexity of O(n log n). In this paper, we propose to cast both Euclidean projections as root finding problems associated with specific auxiliary functions, which can be solved in linear time via bisection. We further make use of the special structure of the auxiliary functions, and propose an improved bisection algorithm. Empirical studies demonstrate that the proposed algorithms are much more efficient than the competing ones for computing the projections.

REFERENCES

• 1: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 2: Brent, R. (1971). An algorithm with guaranteed convergence for finding a zero of a function. Computer Journal, 14, 422--425.
• 3: Candès, E., & Wakin, M. (2008). An introduction to compressive sampling. IEEE Signal Processing Magazine, 25, 21--30.
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: Donoho, D. (2006). Compressed sensing. IEEE Transactions on Information Theory, 52, 1289--1306.
• 6: 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]
• 7: 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
• 8: Nemirovski, A. (1994). Efficient methods in convex programming. Lecture Notes.
• 9: Nesterov, Y. (2003). Introductory lectures on convex optimization: A basic course. Kluwer Academic Publishers.
• 10: 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]
• 11: Shalev-Shwartz, S. (2007). Online learning: Theory algorithms, and applications. Doctoral dissertation, Hebrew University.
• 12: 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
• 13: Shalev-Shwartz, S., & Srebro, N. (2008). Iterative loss minimization with l₁-norm constraint and guarantees on sparsity (Technical Report). TTI.
• 14: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B, 58, 267--288.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming

  I. Computing Methodologies
  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