Header logo is ei

Matrix Exponential Gradient Updates for On-line Learning and Bregman Projection

2005

Conference Paper

ei


We address the problem of learning a symmetric positive definite matrix. The central issue is to design parameter updates that preserve positive definiteness. Our updates are motivated with the von Neumann divergence. Rather than treating the most general case, we focus on two key applications that exemplify our methods: On-line learning with a simple square loss and finding a symmetric positive definite matrix subject to symmetric linear constraints. The updates generalize the Exponentiated Gradient (EG) update and AdaBoost, respectively: the parameter is now a symmetric positive definite matrix of trace one instead of a probability vector (which in this context is a diagonal positive definite matrix with trace one). The generalized updates use matrix logarithms and exponentials to preserve positive definiteness. Most importantly, we show how the analysis of each algorithm generalizes to the non-diagonal case. We apply both new algorithms, called the Matrix Exponentiated Gradient (MEG) update and DefiniteBoost, to learn a kernel matrix from distance measurements.

Author(s): Tsuda, K. and Rätsch, G. and Warmuth, MK.
Book Title: Advances in Neural Information Processing Systems 17
Journal: Advances in Neural Information Processing Systems
Pages: 1425-1432
Year: 2005
Month: July
Day: 0
Editors: Saul, L.K. , Y. Weiss, L. Bottou
Publisher: MIT Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: Eighteenth Annual Conference on Neural Information Processing Systems (NIPS 2004)
Event Place: Vancouver, BC, Canada

Address: Cambridge, MA, USA
Digital: 0
ISBN: 0-262-19534-8
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{2859,
  title = {Matrix Exponential Gradient Updates for On-line Learning and Bregman Projection },
  author = {Tsuda, K. and R{\"a}tsch, G. and Warmuth, MK.},
  journal = {Advances in Neural Information Processing Systems},
  booktitle = {Advances in Neural Information Processing Systems 17},
  pages = {1425-1432},
  editors = {Saul, L.K. , Y. Weiss, L. Bottou},
  publisher = {MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = jul,
  year = {2005},
  month_numeric = {7}
}