Large-scale sparse logistic regression

ABSTRACT

Logistic Regression is a well-known classification method that has been used widely in many applications of data mining, machine learning, computer vision, and bioinformatics. Sparse logistic regression embeds feature selection in the classification framework using the l₁-norm regularization, and is attractive in many applications involving high-dimensional data. In this paper, we propose Lassplore for solving large-scale sparse logistic regression. Specifically, we formulate the problem as the l₁-ball constrained smooth convex optimization, and propose to solve the problem using the Nesterov's method, an optimal first-order black-box method for smooth convex optimization. One of the critical issues in the use of the Nesterov's method is the estimation of the step size at each of the optimization iterations. Previous approaches either applies the constant step size which assumes that the Lipschitz gradient is known in advance, or requires a sequence of decreasing step size which leads to slow convergence in practice. In this paper, we propose an adaptive line search scheme which allows to tune the step size adaptively and meanwhile guarantees the optimal convergence rate. Empirical comparisons with several state-of-the-art algorithms demonstrate the efficiency of the proposed Lassplore algorithm for large-scale problems.

REFERENCES

• 1: U. Alon, N. Barkai, D. A. Notterman, K. Gish, S.Ybarra, D.Mack, andA. J. Levine. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays. Cell Biology, 96:6745--6750, 1999.
• 2: Mehdi Poursheikhali Asgary , Samad Jahandideh , Parviz Abdolmaleki , Anoshirvan Kazemnejad, Analysis and identification of β-turn types using multinomial logistic regression and artificial neural network, Bioinformatics, v.23 n.23, p.3125-3130, December 2007 [doi>10.1093/bioinformatics/btm324]
• 3: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 4: Jack R. Brzezinski, Logistic Regression Modeling for Context-Based Classification, Proceedings of the 10th International Workshop on Database & Expert Systems Applications, p.755, September 01-03, 1999
• 5: M. Chang, W. Yih, and C. Meek. A logistic regression model for detecting prominences. In ACM SIGKDD International conference on Knowledge Discovery and Data mining, 1996.
• 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: B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Annals of Statistics, 32(2):407--499, 2004.
• 8: S. Eyheramendy, E. Genkin, W. Ju, D.D. Lewis, and D. Madigan. Sparse bayesian classifiers for text categorization. Technical report.
• 9: J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28:337--407, 2000.
• 10: J. Friedman, T. Hastie, and R. Tibshirani. Regularized paths for generalized linear models via coordinate descent. Technical report, Department of Statistics, Stanford University, 2008.
• 11: W. Fu. Penalized regressions: the bridge versus the lasso. Journal of Computational and Graphical Statistics, 7:397--416, 1998.
• 12: T. R. Golub, D. K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J. P.Mesirov, H. Coller, M. L. Loh, J. R. Downing, M. A. Caligiuri, C. D. Bloomfield, and E. S. Lander. Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. Science, 286:531--537, 1999.
• 13: E.T. Hale, W. Yin, and Y. Zhang. A fixed-point continuation method for l₁-regularized minimization with applications to compressed sensing. Technical report, CAAM TR07-07, 2007.
• 14: Daniel Jurafsky , James H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 15: S. S. Keerthi , K. B. Duan , S. K. Shevade , A. N. Poo, A Fast Dual Algorithm for Kernel Logistic Regression, Machine Learning, v.61 n.1-3, p.151-165, November 2005 [doi>10.1007/s10994-005-0768-5]
• 16: 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
• 17: Balaji Krishnapuram , Lawrence Carin , Mario A. T. Figueiredo , Alexander J. Hartemink, Sparse Multinomial Logistic Regression: Fast Algorithms and Generalization Bounds, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.957-968, June 2005 [doi>10.1109/TPAMI.2005.127]
• 18: Sun-In Lee , Honglak Lee , Pieter Abbeel , Andrew Y. Ng, EfficientL1regularized logistic regression, Proceedings of the 21st national conference on Artificial intelligence, p.401-408, July 16-20, 2006, Boston, Massachusetts
• 19: 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
• 20: J.G. Liao , Khew-Voon Chin, Logistic regression for disease classification using microarray data, Bioinformatics, v.23 n.15, p.1945-1951, August 2007 [doi>10.1093/bioinformatics/btm287]
• 21: Jun Liu , Jieping Ye, Efficient Euclidean projections in linear time, Proceedings of the 26th Annual International Conference on Machine Learning, p.657-664, June 14-18, 2009, Montreal, Quebec, Canada [doi>10.1145/1553374.1553459]
• 22: A. Maghbouleh. A logistic regression model for detecting prominences. In The Fourth International Conference on Spoken Language, 1996.
• 23: T. P. Minka. A comparison of numerical optimizers for logistic regression. Technical report, 2007.
• 24: A. Nemirovski. Efficient methods in convex programming. Lecture Notes, 1994.
• 25: Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2003.
• 26: 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]
• 27: M.Y. Park and T. Hastie. l₁ regularized path algorithm for generalized linear models. Journal of the Royal Statistical Society: Series B, 69:659--677, 2007.
• 28: Simon Perkins , Kevin Lacker , James Theiler, Grafting: fast, incremental feature selection by gradient descent in function space, The Journal of Machine Learning Research, 3, 3/1/2003
• 29: Maureen A. Sartor , George D. Leikauf , Mario Medvedovic, LRpath, Bioinformatics, v.25 n.2, p.211-217, January 2009 [doi>10.1093/bioinformatics/btn592]
• 30: Mark Schmidt , Glenn Fung , Rómer Rosales, Fast Optimization Methods for L1 Regularization: A Comparative Study and Two New Approaches, Proceedings of the 18th European conference on Machine Learning, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74958-5_28]
• 31: S. K. Shevade and S. S. Keerthi. A simple and efficient algorithm for gene selection using sparse logistic regression. Bioinformatics, 19(17):2246--2253, 2003.
• 32: J. Shi, W. Yin, S. Osher, and P. Sajda. A fast algorithm for large scale l₁-regularized logistic regression. Technical report, CAAM TR08-07, 2008.
• 33: M. West, C. Blanchette, H. Dressman, E. Huang, S. Ishida, R. Spang,H. Zuzan, J. A. Olso, J. R. Marks, and J. R. Nevins. Predicting the clinical status of human breast cancer by using gene expression profiles. National Academy of Sciences, 98(20):11462--11467, 2001.
• 34: J. Zhu and T. Hastie. Kernel logistic regression and the import vector machine. Journal of Computational and Graphical Statistics, 14(1):1081--1088, 2001.
• 35: J. Zhu and T. Hastie. Classification of gene microarrays by penalized logistic regression. Biostatistics, 5(3):427--443, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
l₁-ball constraint, adaptive line search, logistic regression, nesterov's method, sparse learning