A scalable modular convex solver for regularized risk minimization

ABSTRACT

A wide variety of machine learning problems can be described as minimizing a regularized risk functional, with different algorithms using different notions of risk and different regularizers. Examples include linear Support Vector Machines (SVMs), Logistic Regression, Conditional Random Fields (CRFs), and Lasso amongst others. This paper describes the theory and implementation of a highly scalable and modular convex solver which solves all these estimation problems. It can be parallelized on a cluster of workstations, allows for data-locality, and can deal with regularizers such as l₁ and l₂ penalties. At present, our solver implements 20 different estimation problems, can be easily extended, scales to millions of observations, and is up to 10 times faster than specialized solvers for many applications. The open source code is freely available as part of the ELEFANT toolbox.

REFERENCES

• 1: Gükhan H. Bakir , Thomas Hofmann , Bernhard Schölkopf , Alexander J. Smola , Ben Taskar , S. V. N. Vishwanathan, Predicting Structured Data (Neural Information Processing), The MIT Press, 2007
• 2: S. Balay, K. Buschelman, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, B. F. Smith, and H. Zhang. PETSc users manual. Technical Report ANL-95/11, Argonne National Laboratory, 2006.
• 3: O. E. Barndorff-Nielsen. Information and Exponential Families in Statistical Theory. John Wiley and Sons, New York, 1978.
• 4: K. P. Bennett and O. L. Mangasarian. Robust linear programming discrimination of two linearly inseparable sets. Optim. Methods Softw., 1:23--34, 1992.
• 5: S. Benson, L. Curfman-McInnes, J. Moré, and J. Sarich. TAO user manual. Technical Report ANL/MCS-TM-242, Argonne National Laboratory, 2004.
• 6: Richard H. Byrd , Peihuang Lu , Jorge Nocedal , Ciyou Zhu, A limited memory algorithm for bound constrained optimization, SIAM Journal on Scientific Computing, v.16 n.5, p.1190-1208, Sept. 1995 [doi>10.1137/0916069]
• 7: Lijuan Cai , Thomas Hofmann, Hierarchical document categorization with support vector machines, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031186]
• 8: E. Candes and T. Tao. Decoding by linear programming. IEEE Trans. Info Theory, 51(12):4203--4215, 2005.
• 9: C. Chang and C. Lin. LIBSVM: a library for support vector machines, 2001.
• 10: O. Chapelle. Training a support vector machine in the primal. Technical Report TR.147, Max Planck Institute for Biological Cybernetics, 2006.
• 11: C. Chu, S. Kim, Y. A. Lin, Y. Y. Yu, G. Bradski, A. Ng, and K. Olukotun. Map-reduce for machine learning on multicore. In NIPS 19, 2007.
• 12: Chris Clifton , Murat Kantarcioglu , Jaideep Vaidya , Xiaodong Lin , Michael Y. Zhu, Tools for privacy preserving distributed data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.28-34, December 2002 [doi>10.1145/772862.772867]
• 13: Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.158-169, June 28-July 01, 2000
• 14: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 15: Koby Crammer , Yoram Singer, Online Ranking by Projecting, Neural Computation, v.17 n.1, p.145-175, January 2005 [doi>10.1162/0899766052530848]
• 16: N. A. C. Cressie. Statistics for Spatial Data. John Wiley and Sons, New York, 1993.
• 17: L. Fahrmeir and G. Tutz. Multivariate Statistical Modelling Based on Generalized Linear Models. Springer, 1994.
• 18: S. Fine and K. Scheinberg. Efficient SVM training using low-rank kernel representation. Technical report, IBM Watson Research Center, New York, 2000.
• 19: Shai Fine , Katya Scheinberg, Efficient svm training using low-rank kernel representations, The Journal of Machine Learning Research, 2, 3/1/2002
• 20: Claudio Gentile , Manfred K. Warmuth, Linear hinge loss and average margin, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.225-231, July 1999
• 21: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In A. J. Smola, P. L. Bartlett, B. Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 115--132, Cambridge, MA, 2000. MIT Press.
• 22: J. Hiriart-Urruty and C. Lemaréchal. Convex Analysis and Minimization Algorithms, I and II. 305 and 306. Springer-Verlag, 1993.
• 23: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 24: Thorsten Joachims, A support vector method for multivariate performance measures, Proceedings of the 22nd international conference on Machine learning, p.377-384, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102399]
• 25: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 26: S. Sathiya Keerthi , Dennis DeCoste, A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs, The Journal of Machine Learning Research, 6, p.341-361, 12/1/2005
• 27: R. Koenker. Quantile Regression. Cambridge University Press, 2005.
• 28: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 29: Q. Le and A. Smola. Direct optimization of ranking measures. JMLR, 2007. submitted.
• 30: O. L. Mangasarian. Linear and nonlinear separation of patterns by linear programming. Oper. Res., 13:444--452, 1965.
• 31: Klaus-Robert Müller , Alex J. Smola , Gunnar Rätsch , Bernhard Schölkopf , Jens Kohlmorgen , Vladimir Vapnik, Predicting Time Series with Support Vector Machines, Proceedings of the 7th International Conference on Artificial Neural Networks, p.999-1004, October 08-10, 1997
• 32: B. Schölkopf, J. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson. Estimating the support of a high-dimensional distribution. TR 87, Microsoft Research, Redmond, WA, 1999.
• 33: Bernhard Schölkopf , John C. Platt , John C. Shawe-Taylor , Alex J. Smola , Robert C. Williamson, Estimating the Support of a High-Dimensional Distribution, Neural Computation, v.13 n.7, p.1443-1471, July 2001 [doi>10.1162/089976601750264965]
• 34: Fei Sha , Fernando Pereira, Shallow parsing with conditional random fields, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.134-141, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073473]
• 35: S. Shalev-Shwartz and Y. Singer. Online learning optimization in the dual. In COLT, 2006. extended
• 36: Vikas Sindhwani , S. Sathiya Keerthi, Large scale semi-supervised linear SVMs, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148253]
• 37: Ichiro Takeuchi , Quoc V. Le , Timothy D. Sears , Alexander J. Smola, Nonparametric Quantile Estimation, The Journal of Machine Learning Research, 7, p.1231-1264, 12/1/2006
• 38: B. Taskar, C. Guestrin, and D. Koller. Max-margin networks. In NIPS, pages 25--32, 2004.
• 39: R. Tibshirani. Regression shrinkage and selection via lasso. J. R. Stat. Soc. Ser. B Stat. Methodol., 58:267--288 1996.
• 40: Ioannis Tsochantaridis , Thorsten Joachims , Thomas Hofmann , Yasemin Altun, Large Margin Methods for Structured and Interdependent Output Variables, The Journal of Machine Learning Research, 6, p.1453-1484, 12/1/2005
• 41: V. Vapnik, S. Golowich, and A. J. Smola. Support method for function approximation, regression estimation, and signal processing. In NIPS, pages 281--287, 1997.
• 42: S. V. N. Vishwanathan and A. J. Smola. Fast kernels string and tree matching. In NIPS, pages 569--576, 2003
• 43: C. K. I. Williams, Prediction with Gaussian processes: from linear regression to linear prediction and beyond, Proceedings of the NATO Advanced Study Institute on Learning in graphical models, p.599-621, March 1998, Erice, Italy

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms

Keywords:
algorithms, convexity, optimization