An efficient projection for l1, ∞ regularization

ABSTRACT

In recent years the l₁, _∞ norm has been proposed for joint regularization. In essence, this type of regularization aims at extending the l₁ framework for learning sparse models to a setting where the goal is to learn a set of jointly sparse models. In this paper we derive a simple and effective projected gradient method for optimization of l₁, _∞ regularized problems. The main challenge in developing such a method resides on being able to compute efficient projections to the l₁, _∞ ball. We present an algorithm that works in O(n log n) time and O(n) memory where n is the number of parameters. We test our algorithm in a multi-task image annotation problem. Our results show that l₁, _∞ leads to better performance than both l₂ and l₁ regularization and that it is is effective in discovering jointly sparse solutions.

REFERENCES

• 1: Shivani Agarwal , Thore Graepel , Ralf Herbrich , Sariel Har-Peled , Dan Roth, Generalization Bounds for the Area Under the ROC Curve, The Journal of Machine Learning Research, 6, p.393-425, 12/1/2005
• 2: Argyriou, A., Evgeniou, T., & Pontil, M. (2007). Multi-task feature learning. Advances in Neural Information Processing Systems 19 (pp. 41--48).
• 3: Bertsekas, D. (1999). Nonlinear programming. Athena Scientific.
• 4: Donoho, D. (2004). For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution. (Technical Report). Statistics Dept., Stanford University.
• 5: 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]
• 6: Kristen Grauman , Trevor Darrell, The Pyramid Match Kernel: Efficient Learning with Sets of Features, The Journal of Machine Learning Research, 8, p.725-760, 5/1/2007
• 7: Lee, S. I., Ganapathi, V., & Koller, D. (2007). Effcient structure learning of markov networks using l1-regularization. Advances in Neural Information Processing Systems 19 (pp. 817--824).
• 8: Meier, L., van de Geer, S., & Buhlmann, P. (2006). The group lasso for logistic regression (Technical Report). ETH Seminar fur Statistik.
• 9: 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]
• 10: David Nister , Henrik Stewenius, Scalable Recognition with a Vocabulary Tree, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.2161-2168, June 17-22, 2006 [doi>10.1109/CVPR.2006.264]
• 11: Obozinski, G., Taskar, B., & Jordan, M. (2006). Multitask feature selection (Technical Report). Statistics Dept., University of California, Berkeley.
• 12: Park, M. Y., & Hastie, T. (2006). Regularization path algorithms for detecting gene interactions (Technical Report). Stanford University.
• 13: Quattoni, A., Collins, M., & Darrell, T. (2008). Transfer learning for image classification with sparse prototype representations. Proc. of Conf. on Computer Vision and Pattern Recognition.
• 14: Schmidt, M., Murphy, K., Fung, G., & Rosale, R. (2008). Structure learning in random fields for heart motion abnormality detection. Proc. of Conf. on Computer Vision and Pattern Recognition.
• 15: Schmidt, M., van den Berg, E., Friedlander, M., & Murphy, K. (2009). Optimizing costly functions with simple constraints: A limited-memory projected quasi-newton algorithm. Proc. of Conf. on Artificial Intelligence and Statistics (pp. 456--463).
• 16: 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]
• 17: Similä, T., & Tikka, J. (2007). Input selection and shrinkage in multiresponse linear regression. Computational Statistics and Data Analysis, 52, 406--422.
• 18: Joel A. Tropp, Algorithms for simultaneous sparse approximation: part II: Convex relaxation, Signal Processing, v.86 n.3, p.589-602, March 2006 [doi>10.1016/j.sigpro.2005.05.031]
• 19: Turlach, B., Venables, W., & Wright, S. (2005). Simultaneous variable selection. Technometrics, 47, 349--363.
• 20: Yuan, M., & Lin, Y. (2006). Model selection and estimation in regression with grouped variables. J. Royal Statistical Society Series B, 68, 49--67.
• 21: Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. Proc. of Intl. Conf. on Machine Learning (pp. 928--936).

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.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
      G.1.6 Optimization
          Subjects: Gradient methods

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Management, Performance, Theory