article

Free access

Bundle Methods for Regularized Risk Minimization

Authors:

S.V.N. Vishwanthan,

Quoc V. LeAuthors Info & Claims

The Journal of Machine Learning Research, Volume 11

Pages 311 - 365

Published: 01 March 2010 Publication History

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), Gaussian Processes, Logistic Regression, Conditional Random Fields (CRFs), and Lasso amongst others. This paper describes the theory and implementation of a 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. In addition to the unified framework we present tight convergence bounds, which show that our algorithm converges in O(1/ε) steps to ε precision for general convex problems and in O(log (1/ε)) steps for continuously differentiable problems. We demonstrate the performance of our general purpose solver on a variety of publicly available data sets.

References

[1]

N. Abe, J. Takeuchi, and M. K. Warmuth. Polynomial Learnability of Stochastic Rules with Respect to the KL-Divergence and Quadratic Distance. IEICE Transactions on Information and Systems, 84(3):299-316, 2001.

[2]

G. Amdahl. Validity of the single processor approach to achieving large-scale computing capabilities. In AFIPS Conference Proceedings, volume 30, pages 483-485, 1967.

Digital Library

[3]

M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein, H. Butler, J.M. Cherry, A. P. Davis, K. Dolinski, S. S. Dwight, J. T. Eppig, M. A. Harris, D. P. Hill, L. Issel-Tarver, A. Kasarskis, S. Lewis, J. C. Matese, J. E. Richardson, M. Ringwald, G. M. Rubin, and G. Sherlock. Gene ontology: tool for the unification of biology. the gene ontology consortium. Nature Genetics, 25:25-29, 2000.

[4]

G. Bakir, T. Hofmann, B. Schölkopf, A. J. Smola, B. Taskar, and S. V. N. Vishwanathan. Predicting Structured Data. MIT Press, Cambridge, Massachusetts, 2007.

Digital Library

[5]

O. E. Barndorff-Nielsen. Information and Exponential Families in Statistical Theory. John Wiley and Sons, New York, 1978.

[6]

J. Basilico and T. Hofmann. Unifying collaborative and content-based filtering. In Proceedings of the International Conference on Machine Learning, pages 65-72, New York, NY, 2004. ACM Press.

Digital Library

[7]

A. Belloni. Introduction to bundle methods. Technical report, Operation Research Center, M.I.T., 2005.

[8]

S. Belongie, J. Malik, and J. Puzicha. Matching shapes. In Eighth IEEE International Conference on Computer Vision, Vancouver, Canada, July 2001.

[9]

K. P. Bennett and O. L. Mangasarian. Robust linear programming discrimination of two linearly inseparable sets. Optimization Methods Software, 1:23-34, 1992.

[10]

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, England, 2004.

Digital Library

[11]

J. S. Breese, D. Heckerman, and C. Kardie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, pages 43-52, 1998.

Digital Library

[12]

T. Caetano, L. Cheng, Q. V. Le, and A. J. Smola. Learning graph matching. In Proceedings of the 11th International Conference On Computer Vision, pages 1-8, Los Alamitos, CA, 2007. IEEE Computer Society.

[13]

T. Caetano, J. J. McAuley, L. Cheng, Q. V. Le, and A. J. Smola. Learning graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008. submitted.

Digital Library

[14]

L. Cai and T. Hofmann. Hierarchical document categorization with support vector machines. In Proceedings of the Thirteenth ACM conference on Information and knowledge management, pages 78-87, New York, NY, USA, 2004. ACM Press.

Digital Library

[15]

E. Candes and T. Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203-4215, 2005.

Digital Library

[16]

C. C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.

[17]

O. Chapelle. Training a support vector machine in the primal. Neural Computation, 19(5):1155- 1178, 2007.

Digital Library

[18]

M. Collins, R. E. Schapire, and Y. Singer. Logistic regression, AdaBoost and Bregman distances. In Proceedings of the 13th Annual Conference on Computational Learning Theory, pages 158-169. Morgan Kaufmann, San Francisco, 2000.

Digital Library

[19]

C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20(3):273-297, 1995.

Digital Library

[20]

R. Cowell, A. Dawid, S. Lauritzen, and D. Spiegelhalter. Probabilistic Networks and Expert Sytems. Springer, New York, 1999.

Digital Library

[21]

K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research, 3:951-991, January 2003.

Digital Library

[22]

K. Crammer and Y. Singer. Online ranking by projecting. Neural Computation, 17(1):145-175, 2005.

Digital Library

[23]

N. A. C. Cressie. Statistics for Spatial Data. John Wiley and Sons, New York, 1993.

[24]

L. Fahrmeir and G. Tutz. Multivariate Statistical Modelling Based on Generalized Linear Models. Springer, 1994.

[25]

R.-E. Fan, J.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: a library for large linear classification. Journal of Machine Learning Research, 9:1871-1874, August 2008.

Digital Library

[26]

S. Fine and K. Scheinberg. Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2:243-264, Dec 2001.

Digital Library

[27]

V. Franc and S. Sonnenburg. Optimized cutting plane algorithm for support vector machines. In A. McCallum and S. Roweis, editors, Proceedings of the International Conference on Machine Learning, pages 320-327. Omnipress, 2008.

Digital Library

[28]

A. Frangioni. Dual-Ascent Methods and Multicommodity Flow Problems. PhD thesis, Dipartimento di Informatica, Universita' di Pisa, 1997. TD 5/97.

[29]

W. Gropp, E. Lusk, and R. Thakur. Using MPI-2. MIT Press, 1999.

[30]

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.

[31]

J. B. Hiriart-Urruty and C. Lemaréchal. Convex Analysis and Minimization Algorithms, I and II, volume 305 and 306. Springer-Verlag, 1993.

[32]

C.-J. Hsieh, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundararajan. A dual coordinate descent method for large-scale linear SVM. In W. Cohen, A. McCallum, and S. Roweis, editors, icml, pages 408-415. ACM, 2008.

Digital Library

[33]

K. Jarvelin and J. Kekalainen. IR evaluation methods for retrieving highly relevant documents. In ACM Special Interest Group in Information Retrieval (SIGIR), pages 41-48, New York, 2002. ACM.

Digital Library

[34]

T. Joachims. A support vector method for multivariate performance measures. In Proceedings of the International Conference on Machine Learning, pages 377-384, San Francisco, California, 2005. Morgan Kaufmann Publishers.

Digital Library

[35]

T. Joachims. Training linear SVMs in linear time. In Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD). ACM, 2006.

Digital Library

[36]

T. Joachims. Making large-scale SVM learning practical. In B. Schölkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods--Support Vector Learning, pages 169-184, Cambridge, MA, 1999. MIT Press.

Digital Library

[37]

T. Joachims, T. Finley, and C.-N. Yu. Cutting-plane traning of structural SVMs. Machine Learning, 76(1), 2009.

Digital Library

[38]

R. Jonker and A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38:325-340, 1987.

Digital Library

[39]

M. I. Jordan. An Introduction to Probabilistic Graphical Models. MIT Press, 2002. To Appear.

[40]

R. M. Karp. An algorithm to solve the m × n assignment problem in expected time O(mn log n). Networks, 10(2):143-152, 1980.

[41]

S. S. Keerthi and D. DeCoste. A modified finite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research, 6:341-361, 2005.

Digital Library

[42]

J. E. Kelly. The cutting-plane method for solving convex programs. Journal of the Society for Industrial and Applied Mathematics, 8(4):703-712, December 1960.

[43]

K. C. Kiwiel. An aggregate subgradient method for nonsmooth convex minimization. Mathematical Programming, 27:320-341, 1983.

Digital Library

[44]

K. C. Kiwiel. Proximity control in bundle methods for convex nondifferentiable minimization. Mathematical Programming, 46:105-122, 1990.

Digital Library

[45]

R. Koenker. Quantile Regression. Cambridge University Press, 2005.

[46]

H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83-97, 1955.

[47]

J. D. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: probabilistic modeling for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning, volume 18, pages 282-289, San Francisco, CA, 2001. Morgan Kaufmann.

Digital Library

[48]

Q. V. Le and A. J. Smola. Direct optimization of ranking measures. Journal of Machine Learning Research, 2007. submitted.

[49]

C. Lemaréchal, A. Nemirovskii, and Y. Nesterov. New variants of bundle methods. Mathematical Programming, 69:111-147, 1995.

Digital Library

[50]

C.-J. Lin, R. C. Weng, and S. S. Keerthi. Trust region newton method for large-scale logistic regression. Journal of Machine Learning Research, 9:627-650, April 2008.

Digital Library

[51]

L. Luk¿an and J. Vl'ek. A bundle-Newton method for nonsmooth unconstrained minimization. Mathematical Programming, 83(3):373-391, 1998.

Digital Library

[52]

O. L. Mangasarian. Linear and nonlinear separation of patterns by linear programming. Operations Research, 13:444-452, 1965.

Digital Library

[53]

D. McAllester. Generalization bounds and consistency for structured labeling. In Predicting Structured Data, Cambridge, Massachusetts, 2007. MIT Press.

[54]

T. P. Minka. A comparison of numerical optimizers for logistic regression. Technical report, Microsoft Research, 2007.

[55]

K.-R. Müller, A. J. Smola, G. Rätsch, B. Schölkopf, J. Kohlmorgen, and V. Vapnik. Predicting time series with support vector machines. In W. Gerstner, A. Germond, M. Hasler, and J.-D. Nicoud, editors, Artificial Neural Networks ICANN'97, volume 1327 of Lecture Notes in Comput. Sci., pages 999-1004, Berlin, 1997. Springer-Verlag.

Digital Library

[56]

J. Munkres. Algorithms for the assignment and transportation problems. Journal of SIAM, 5(1): 32-38, 1957.

[57]

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.

[58]

J. Nocedal and S. J. Wright. Numerical Optimization. Springer Series in Operations Research. Springer, 1999.

[59]

J. B. Orlin and Y. Lee. Quickmatch: a very fast algorithm for the assignment problem. Working Paper 3547-93, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA, March 1993.

[60]

A. Rahimi and B. Recht. Random features for large-scale kernel machines. In J. C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20. MIT Press, Cambridge, MA, 2008.

[61]

N. Ratliff, J. Bagnell, and M. Zinkevich. Maximum margin planning. In Proceedings of the International Conference on Machine Learning, July 2006.

Digital Library

[62]

N. Ratliff, J. Bagnell, and M. Zinkevich. (online) subgradient methods for structured prediction. In Eleventh International Conference on Artificial Intelligence and Statistics (AIStats), March 2007.

[63]

G. Rätsch, S. Sonnenburg, J. Srinivasan, H. Witte, K.-R. Müller, R. J. Sommer, and B. Schölkopf. Improving the Caenorhabditis elegans genome annotation using machine learning. PLoS Computational Biology, 3(2):e20 2007.

[64]

B. Schölkopf, J. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson. Estimating the support of a high-dimensional distribution. Neural Computation, 13(7):1443-1471, 2001.

Digital Library

[65]

H. Schramm and J. Zowe. A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM Journal of Optimization, 2:121- 152, 1992.

Digital Library

[66]

F. Sha and F. Pereira. Shallow parsing with conditional random fields. In Proceedings of HLTNAACL, pages 213-220, Edmonton, Canada, 2003. Association for Computational Linguistics.

Digital Library

[67]

S. Shalev-Schwartz and N. Srebro. SVM optimization: inverse dependence on training set size. In W. Cohen, A. McCallum, and S. Roweis, editors, Proceedings of the International Conference on Machine Learning. Omnipress, 2008.

Digital Library

[68]

S. Shalev-Shwartz and Y. Singer. Online learning meets optimization in the dual. In H.U. Simon and G. Lugosi, editors, Computational Learning Theory (COLT), LNCS. Springer, 2006. extended version.

Digital Library

[69]

S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: primal estimated sub-gradient solver for SVM. In Proceedings of the International Conference on Machine Learning, 2007.

Digital Library

[70]

Q. Shi, L. Wang, L. Cheng, and A. J. Smola. Discriminative human action segmentation and recognition using semi-markov model. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, 2008.

[71]

V. Sindhwani and S. S. Keerthi. Large scale semi-supervised linear SVMs. In SIGIR '06: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pages 477-484, New York, NY, USA, 2006. ACM Press.

Digital Library

[72]

A. J. Smola, S. V. N. Vishwanathan, and Q. V. Le. Bundle methods for machine learning. In D. Koller and Y. Singer, editors, Advances in Neural Information Processing Systems 20, Cambridge MA, 2007. MIT Press.

[73]

I. Takeuchi, Q. V. Le, T. Sears, and A. J. Smola. Nonparametric quantile estimation. Journal of Machine Learning Research, 7, 2006.

Digital Library

[74]

B. Taskar, C. Guestrin, and D. Koller. Max-margin Markov networks. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16, pages 25-32, Cambridge, MA, 2004. MIT Press.

[75]

C.-H. Teo, Q. V. Le, A. J. Smola, and S. V. N. Vishwanathan. A scalable modular convex solver for regularized risk minimization. In Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD). ACM, 2007.

Digital Library

[76]

R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Section B (Statistical Methodology), 58:267-288, 1996.

[77]

I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6:1453-1484, 2005.

Digital Library

[78]

V. Vapnik, S. Golowich, and A. J. Smola. Support vector method for function approximation, regression estimation, and signal processing. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems 9, pages 281-287, Cambridge, MA, 1997. MIT Press.

[79]

E. Voorhees. Overview of the TREC 2001 question answering track. In TREC, 2001.

[80]

G. Wahba. Support vector machines, reproducing kernel Hilbert spaces and the randomized GACV. Technical Report 984, Department of Statistics, University of Wisconsin, Madison, 1997.

[81]

M. J. Wainwright and M. I. Jordan. Graphical models, exponential families, and variational inference. Technical Report 649, UC Berkeley, Department of Statistics, September 2003.

[82]

C. K. I. Williams. Prediction with Gaussian processes: from linear regression to linear prediction and beyond. InM. I. Jordan, editor, Learning and Inference in Graphical Models, pages 599-621. Kluwer Academic, 1998.

Digital Library

[83]

J. Yu, S. V. N. Vishwanathan, S. Günter, and N. N. Schraudolph. A quasi-Newton approach to nonsmooth convex optimization. In A. McCallum and S. Roweis, editors, ICML, pages 1216- 1223. Omnipress, 2008.

Digital Library

[84]

T. Zhang. Sequential greedy approximation for certain convex optimization problems. IEEE Transactions on Information Theory, 49(3):682-691, 2003.

Digital Library

Cited By

Blanchard MZhang JJaillet POh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Memory-constrained algorithms for convex optimizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666392(6156-6189)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666392
Wang PLee CLin C(2021)The common-directions method for regularized empirical risk minimizationThe Journal of Machine Learning Research10.5555/3322706.336199920:1(2072-2120)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3361999
Brust JDi ZLeyffer SPetra C(2021)Compact representations of structured BFGS matricesComputational Optimization and Applications10.1007/s10589-021-00297-080:1(55-88)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s10589-021-00297-0
Show More Cited By

Index Terms

Bundle Methods for Regularized Risk Minimization

Recommendations

Iterative reweighted minimization methods for $$l_p$$lp regularized unconstrained nonlinear programming

In this paper we study general $$l_p$$ l p regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of the first- and second-order stationary points and hence also of local minimizers of the $$l_p$$ l p minimization problems. ...
Decentralized Sparsity-Regularized Rank Minimization: Algorithms and Applications

Given a limited number of entries from the superposition of a low-rank matrix plus the product of a known compression matrix times a sparse matrix, recovery of the low-rank and sparse components is a fundamental task subsuming compressed sensing, matrix ...
$$\ell _p$$ℓp Regularized low-rank approximation via iterative reweighted singular value minimization

In this paper we study the $$\ell _p$$ℓp (or Schatten-p quasi-norm) regularized low-rank approximation problems. In particular, we introduce a class of first-order stationary points for them and show that any local minimizer of these problems must be a ...

Comments

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research

The Journal of Machine Learning Research Volume 11, Issue

3/1/2010

3637 pages

ISSN:1532-4435

EISSN:1533-7928

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Published: 01 March 2010

Published in JMLR Volume 11

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
575
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)12

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Blanchard MZhang JJaillet POh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Memory-constrained algorithms for convex optimizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666392(6156-6189)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666392
Wang PLee CLin C(2021)The common-directions method for regularized empirical risk minimizationThe Journal of Machine Learning Research10.5555/3322706.336199920:1(2072-2120)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3361999
Brust JDi ZLeyffer SPetra C(2021)Compact representations of structured BFGS matricesComputational Optimization and Applications10.1007/s10589-021-00297-080:1(55-88)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s10589-021-00297-0
Liu ZShi XHe LYu DJin HYu CDai HFeng Z(2020)A parameter-level parallel optimization algorithm for large-scale spatio-temporal data miningDistributed and Parallel Databases10.1007/s10619-020-07287-x38:3(739-765)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.1007/s10619-020-07287-x
Chauhan VDahiya KSharma A(2019)Problem formulations and solvers in linear SVMArtificial Intelligence Review10.1007/s10462-018-9614-652:2(803-855)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s10462-018-9614-6
Pillutla KRoulet VKakade SHarchaoui Z(2018)A smoother way to train structured prediction modelsProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327345.3327386(4771-4783)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327345.3327386
Ju XTian Y(2018)A divide-and-conquer method for large scale ź-nonparallel support vector machinesNeural Computing and Applications10.1007/s00521-016-2574-329:9(497-509)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00521-016-2574-3
Shen LLiu WYuan GMa S(2017)GSOSProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305890.3306004(3125-3134)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305890.3306004
Shen LLiu WHuang JJiang YMa SSingh SMarkovitch S(2017)Adaptive proximal average approximation for composite convex minimizationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298483.3298601(2513-2519)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298483.3298601
Guo XWang XLing H(2017)Exclusivity regularized machineProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3172077.3172129(1739-1745)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3172077.3172129
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents