Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We extend the well-known BFGS quasi-Newton method and its limited-memory variant LBFGS to the optimization of non-smooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: The local quadratic model, the identification of a descent direction, and the Wolfe line search conditions. We apply the resulting subLBFGS algorithm to L₂-regularized risk minimization with binary hinge loss, and its direction-finding component to L₁-regularized risk minimization with logistic loss. In both settings our generic algorithms perform comparable to or better than their counterparts in specialized state-of-the-art solvers.

REFERENCES

• 1: Galen Andrew , Jianfeng Gao, Scalable training of L¹-regularized log-linear models, Proceedings of the 24th international conference on Machine learning, p.33-40, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273501]
• 2: A. Belloni. Introduction to bundle methods. Technical report, Operation Research Center, M.I.T., 2005.
• 3: M. Haarala. Large-Scale Non-smooth Optimization. PhD thesis, University of Jyväskylä, 2004.
• 4: J. Hiriart-Urruty and C. Lemaréchal. Convex Analysis and Minimization Algorithms, I and II, volume 305 and 306. Springer-Verlag, 1993.
• 5: 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]
• 6: L. Lukšan , J. Vlček, Globally convergent variable metric method for convex nonsmooth unconstrained minimization, Journal of Optimization Theory and Applications, v.102 n.3, p.593-613, Sept. 1999 [doi>10.1023/A:1022650107080]
• 7: A. Nedich and D. P. Bertsekas. Convergence rate of incremental subgradient algorithms. In S. Uryasev and P. M. Pardalos, editors, Stochastic Optimization: Algorithms and Applications, pages 263--304. Kluwer Academic Publishers, 2000.
• 8: J. Nocedal and S. J. Wright. Numerical Optimization. Springer Series in Operations Research. Springer, 1999.
• 9: Choon Hui Teo , Alex Smola , S. V.N. Vishwanathan , Quoc Viet Le, A scalable modular convex solver for regularized risk minimization, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281270]
• 10: F. Vojtěch and S. Sonnenburg. Optimized cutting plane algorithm for support vector machines. Technical Report 1, Fraunhofer Institute FIRST, December 2007. http://publica.fraunhofer.de/documents/N-66225.html.
• 11: J. Yu, S. V. N. Vishwanathan, S. Günter, and N. N. Schraudolph. A quasi-Newton approach to non-smooth convex optimization. Technical Report arXiv:0804.3835, April 2008. http://arxiv.org/pdf/0804.3835.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
      G.1.6 Optimization
          Subjects: Quadratic programming methods

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Design, Theory