Bundle Methods for Regularized Risk Minimization
Choon Hui Teo, S.V.N. Vishwanthan, Alex J. Smola et al. · 2010
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. Ex-amples 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 L1 and L2 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.
Cited by 223 works. doi:10.5555/1756006.1756016
Authors
References
- Support-Vector Networks
- Convex Optimization
- LIBSVM
- Regression Shrinkage and Selection Via the Lasso
- Gene Ontology: tool for the unification of biology
- Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
- The Hungarian method for the assignment problem
- Making Large-Scale SVM Learning Practical
- Numerical optimization
- LIBLINEAR: A Library for Large Linear Classification