Bundle methods for regularized risk minimization

Choon Hui Teo, S. V.N. Vishwanathan, Alex Smola, Quoc V. Le

    Research output: Contribution to journalArticlepeer-review

    173 Citations (Scopus)

    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 1 and L 2 penalties. In addition to the unified framework we present tight convergence bounds, which show that our algorithm converges in O(1/ε) steps to e 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.

    Original languageEnglish
    Pages (from-to)311-365
    Number of pages55
    JournalJournal of Machine Learning Research
    Volume11
    Publication statusPublished - 2010

    Fingerprint

    Dive into the research topics of 'Bundle methods for regularized risk minimization'. Together they form a unique fingerprint.

    Cite this