Graduate School and Research Center in Digital Sciences

Preconditioning Kernel matrices

Cutajar, Kurt; Osborne , Michael; Cunningham, John; Filippone, Maurizio

ICML 2016, International Conference on Machine Learning, June 19-24, 2016, San Francisco, USA

The computational and storage complexity of kernel machines presents the primary barrier to their scaling to large, modern, datasets. A common way to tackle the scalability issue is to use the conjugate gradient algorithm, which relieves the constraints on both storage (the kernel matrix need not be stored) and computation (both stochastic gradients and parallelization can be used). Even so, conjugate gradient is not without its own issues: the conditioning of kernel matrices is often such that conjugate gradients will have poor convergence in practice. Preconditioning is a common approach to alleviating this issue. Here we propose preconditioned conjugate gradients for kernel machines, and develop a broad range of preconditioners particularly useful for kernel matrices. We describe a scalable approach to both solving kernel machines and learning their hyperparameters. We show this approach is exact in the limit of iterations and outperforms state-of-the-art approximations for a given computational budget.

Document Arxiv Bibtex

Title:Preconditioning Kernel matrices
City:San Francisco
Department:Data Science
Eurecom ref:4891
Copyright: © 2016 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+4891, year = {2016}, title = {{P}reconditioning {K}ernel matrices}, author = {{C}utajar, {K}urt and {O}sborne , {M}ichael and {C}unningham, {J}ohn and {F}ilippone, {M}aurizio}, booktitle = {{ICML} 2016, {I}nternational {C}onference on {M}achine {L}earning, {J}une 19-24, 2016, {S}an {F}rancisco, {USA}}, address = {{S}an {F}rancisco, {UNITED} {STATES}}, month = {06}, url = {} }
See also: