On the Complexity of Learning with Kernels

Nicolò Cesa-Bianchi, Yishay Mansour, Ohad Shamir
Proceedings of The 28th Conference on Learning Theory, PMLR 40:297-325, 2015.

Abstract

A well-recognized limitation of kernel learning is the requirement to handle a kernel matrix, whose size is quadratic in the number of training examples. Many methods have been proposed to reduce this computational cost, mostly by using a subset of the kernel matrix entries, or some form of low-rank matrix approximation, or a random projection method. In this paper, we study lower bounds on the error attainable by such methods as a function of the number of entries observed in the kernel matrix or the rank of an approximate kernel matrix. We show that there are kernel learning problems where no such method will lead to non-trivial computational savings. Our results also quantify how the problem difficulty depends on parameters such as the nature of the loss function, the regularization parameter, the norm of the desired predictor, and the kernel matrix rank. Our results also suggest cases where more efficient kernel learning might be possible.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Cesa-Bianchi15, title = {On the Complexity of Learning with Kernels}, author = {Cesa-Bianchi, Nicolò and Mansour, Yishay and Shamir, Ohad}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {297--325}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Cesa-Bianchi15.pdf}, url = {https://proceedings.mlr.press/v40/Cesa-Bianchi15.html}, abstract = {A well-recognized limitation of kernel learning is the requirement to handle a kernel matrix, whose size is quadratic in the number of training examples. Many methods have been proposed to reduce this computational cost, mostly by using a subset of the kernel matrix entries, or some form of low-rank matrix approximation, or a random projection method. In this paper, we study lower bounds on the error attainable by such methods as a function of the number of entries observed in the kernel matrix or the rank of an approximate kernel matrix. We show that there are kernel learning problems where no such method will lead to non-trivial computational savings. Our results also quantify how the problem difficulty depends on parameters such as the nature of the loss function, the regularization parameter, the norm of the desired predictor, and the kernel matrix rank. Our results also suggest cases where more efficient kernel learning might be possible.} }
Endnote
%0 Conference Paper %T On the Complexity of Learning with Kernels %A Nicolò Cesa-Bianchi %A Yishay Mansour %A Ohad Shamir %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Cesa-Bianchi15 %I PMLR %P 297--325 %U https://proceedings.mlr.press/v40/Cesa-Bianchi15.html %V 40 %X A well-recognized limitation of kernel learning is the requirement to handle a kernel matrix, whose size is quadratic in the number of training examples. Many methods have been proposed to reduce this computational cost, mostly by using a subset of the kernel matrix entries, or some form of low-rank matrix approximation, or a random projection method. In this paper, we study lower bounds on the error attainable by such methods as a function of the number of entries observed in the kernel matrix or the rank of an approximate kernel matrix. We show that there are kernel learning problems where no such method will lead to non-trivial computational savings. Our results also quantify how the problem difficulty depends on parameters such as the nature of the loss function, the regularization parameter, the norm of the desired predictor, and the kernel matrix rank. Our results also suggest cases where more efficient kernel learning might be possible.
RIS
TY - CPAPER TI - On the Complexity of Learning with Kernels AU - Nicolò Cesa-Bianchi AU - Yishay Mansour AU - Ohad Shamir BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Cesa-Bianchi15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 297 EP - 325 L1 - http://proceedings.mlr.press/v40/Cesa-Bianchi15.pdf UR - https://proceedings.mlr.press/v40/Cesa-Bianchi15.html AB - A well-recognized limitation of kernel learning is the requirement to handle a kernel matrix, whose size is quadratic in the number of training examples. Many methods have been proposed to reduce this computational cost, mostly by using a subset of the kernel matrix entries, or some form of low-rank matrix approximation, or a random projection method. In this paper, we study lower bounds on the error attainable by such methods as a function of the number of entries observed in the kernel matrix or the rank of an approximate kernel matrix. We show that there are kernel learning problems where no such method will lead to non-trivial computational savings. Our results also quantify how the problem difficulty depends on parameters such as the nature of the loss function, the regularization parameter, the norm of the desired predictor, and the kernel matrix rank. Our results also suggest cases where more efficient kernel learning might be possible. ER -
APA
Cesa-Bianchi, N., Mansour, Y. & Shamir, O.. (2015). On the Complexity of Learning with Kernels. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:297-325 Available from https://proceedings.mlr.press/v40/Cesa-Bianchi15.html.

Related Material