Header logo is ei

A scalable trust-region algorithm with application to mixed-norm regression

2010

Conference Paper

ei


We present a new algorithm for minimizing a convex loss-function subject to regularization. Our framework applies to numerous problems in machine learning and statistics; notably, for sparsity-promoting regularizers such as ℓ1 or ℓ1, ∞ norms, it enables efficient computation of sparse solutions. Our approach is based on the trust-region framework with nonsmooth objectives, which allows us to build on known results to provide convergence analysis. We avoid the computational overheads associated with the conventional Hessian approximation used by trust-region methods by instead using a simple separable quadratic approximation. This approximation also enables use of proximity operators for tackling nonsmooth regularizers. We illustrate the versatility of our resulting algorithm by specializing it to three mixed-norm regression problems: group lasso [36], group logistic regression [21], and multi-task lasso [19]. We experiment with both synthetic and real-world large-scale data—our method is seen to be competitive, robust, and scalable.

Author(s): Kim, D. and Sra, S. and Dhillon, I.
Journal: Proceedings of the 27th International Conference on Machine Learning (ICML 2010)
Pages: 519-526
Year: 2010
Month: June
Day: 0
Editors: F{\"u}rnkranz, J. , T. Joachims
Publisher: International Machine Learning Society

Department(s): Empirical Inference
Research Project(s): Optimization and Large Scale Learning
Bibtex Type: Conference Paper (inproceedings)

Address: Madison, WI, USA
Digital: 0
Event Name: 27th International Conference on Machine Learning (ICML 2010)
Event Place: Haifa, Israel
ISBN: 978-1-605-58907-7
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{6519,
  title = {A scalable trust-region algorithm with application to mixed-norm regression},
  author = {Kim, D. and Sra, S. and Dhillon, I.},
  journal = {Proceedings of the 27th International Conference on Machine Learning (ICML 2010)},
  pages = {519-526},
  editors = {F{\"u}rnkranz, J. , T. Joachims},
  publisher = {International Machine Learning Society},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Madison, WI, USA},
  month = jun,
  year = {2010},
  month_numeric = {6}
}