New Probabilistic Bounds on Eigenvalues and Eigenvectors of Random Kernel Matrices

Nima Reyhani, Hideitsu Hino, Ricardo Vigario
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:693-700, 2011.

Abstract

Kernel methods are successful approaches for different machine learning problems. This success is mainly rooted in using feature maps and kernel matrices. Some methods rely on the eigenvalues/eigenvectors of the kernel matrix, while for other methods the spectral information can be used to estimate the excess risk. An important question remains on how close the sample eigenvalues/eigenvectors are to the population values. In this paper, we improve earlier results on concentration bounds for eigenvalues of general kernel matrices. For distance and inner product kernel functions, e.g. radial basis functions, we provide new concentration bounds, which are characterized by the eigenvalues of the sample covariance matrix. Meanwhile, the obstacles for sharper bounds are accounted for and partially addressed. As a case study, we derive a concentration inequality for sample kernel target-alignment.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-reyhani11a, title = {New Probabilistic Bounds on Eigenvalues and Eigenvectors of Random Kernel Matrices}, author = {Reyhani, Nima and Hino, Hideitsu and Vigario, Ricardo}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {693--700}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/reyhani11a/reyhani11a.pdf}, url = {https://proceedings.mlr.press/r9/reyhani11a.html}, abstract = {Kernel methods are successful approaches for different machine learning problems. This success is mainly rooted in using feature maps and kernel matrices. Some methods rely on the eigenvalues/eigenvectors of the kernel matrix, while for other methods the spectral information can be used to estimate the excess risk. An important question remains on how close the sample eigenvalues/eigenvectors are to the population values. In this paper, we improve earlier results on concentration bounds for eigenvalues of general kernel matrices. For distance and inner product kernel functions, e.g. radial basis functions, we provide new concentration bounds, which are characterized by the eigenvalues of the sample covariance matrix. Meanwhile, the obstacles for sharper bounds are accounted for and partially addressed. As a case study, we derive a concentration inequality for sample kernel target-alignment.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T New Probabilistic Bounds on Eigenvalues and Eigenvectors of Random Kernel Matrices %A Nima Reyhani %A Hideitsu Hino %A Ricardo Vigario %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-reyhani11a %I PMLR %P 693--700 %U https://proceedings.mlr.press/r9/reyhani11a.html %V R9 %X Kernel methods are successful approaches for different machine learning problems. This success is mainly rooted in using feature maps and kernel matrices. Some methods rely on the eigenvalues/eigenvectors of the kernel matrix, while for other methods the spectral information can be used to estimate the excess risk. An important question remains on how close the sample eigenvalues/eigenvectors are to the population values. In this paper, we improve earlier results on concentration bounds for eigenvalues of general kernel matrices. For distance and inner product kernel functions, e.g. radial basis functions, we provide new concentration bounds, which are characterized by the eigenvalues of the sample covariance matrix. Meanwhile, the obstacles for sharper bounds are accounted for and partially addressed. As a case study, we derive a concentration inequality for sample kernel target-alignment. %Z Reissued by PMLR on 04 October 2026.
APA
Reyhani, N., Hino, H. & Vigario, R.. (2011). New Probabilistic Bounds on Eigenvalues and Eigenvectors of Random Kernel Matrices. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:693-700 Available from https://proceedings.mlr.press/r9/reyhani11a.html. Reissued by PMLR on 04 October 2026.

Related Material