Improved Bounds for the Nyström Method With Application to Kernel Classification

Rong Jin, Tianbao Yang, Mehrdad Mahdavi, Yu-Feng Li, Zhi-Hua ZhouIEEE Trans. Information Theory 2013 · OpenReview

Abstract

We develop two approaches for analyzing the approximation error bound for the Nyström method that approximates a positive semidefinite (PSD) matrix by sampling a small set of columns: one based on a concentration inequality for integral operators, and one based on random matrix theory. We show that the approximation error, measured in the spectral norm, can be improved from $O(N/\sqrt{m})$ to $O(N/m^{1-\rho})$ in the case of large eigengap, where $N$ is the total number of data points, $m$ is the number of sampled data points, and $\rho \in (0, 1/2)$ is a positive constant that characterizes the eigengap. When the eigenvalues of the kernel matrix follow a $p$-power law, our analysis based on random matrix theory further improves the bound to $O(N/m^{p-1})$ under an incoherence assumption. We present a kernel classification approach based on the Nyström method and derive its generalization performance using the improved bound. We show that when the eigenvalues of the kernel matrix follow a $p$-power law, we can reduce the number of support vectors to $N^{2p/(p^2-1)}$, which is sublinear in $N$ when $p > 1+\sqrt{2}$, without seriously sacrificing its generalization performance.

Introduction

Kernel methods, such as Support Vector Machines (SVMs), are cornerstone techniques for non-linear classification and regression. However, their application to large-scale datasets is often hindered by computational complexity. Processing a dataset of $N$ points typically requires handling an $N \times N$ kernel matrix, resulting in $O(N^2)$ space and $O(N^3)$ time complexity. This quadratic growth makes standard kernel methods prohibitive for modern "big data" applications.

The Nyström method has emerged as a popular solution to this scalability bottleneck. By sampling $m$ columns ($m \ll N$) to construct a low-rank approximation of the full kernel matrix, the Nyström method significantly reduces the computational burden. Despite its empirical success, the theoretical understanding of its approximation error has historically been pessimistic. Standard bounds suggested an error rate of $O(N/\sqrt{m})$, implying that a massive number of samples would be required to achieve high accuracy. This paper bridges the gap between theory and practice by providing significantly tighter bounds and demonstrating how these improvements translate to efficient kernel classification.

Theoretical Frameworks for Tighter Bounds

The authors develop two distinct mathematical frameworks to refine the approximation bounds, moving beyond the traditional "square-root" rate.

1. Concentration Inequality of Integral Operators

Rather than treating the kernel as a static matrix, this approach views the kernel as a linear operator in a Reproducing Kernel Hilbert Space (RKHS). By applying concentration inequalities to these operators, the authors demonstrate that the approximation error is sensitive to the "eigengap"—the rate at which the importance of eigenvalues drops off. If a significant eigengap exists, the error bound improves to $O(N/m^{1-\rho})$, where $\rho$ characterizes the gap. This suggests that for matrices with a few dominant components, the Nyström method is far more efficient than previously thought.

2. Random Matrix Theory and Compressive Sensing

For kernels where eigenvalues follow a "p-power law" (decaying at a rate of $k^{-p}$), the authors utilize tools from random matrix theory and compressive sensing. Under an "incoherence" assumption—which ensures that the information is distributed across the eigenvectors rather than concentrated in a few specific data points—they derive an even tighter bound of $O(N/m^{p-1})$. This bound is particularly powerful for smooth kernels where eigenvalues decay rapidly.

Application to Kernel Classification

Building on these improved bounds, the paper proposes a Subspace-Restricted Classification approach. In this model, the classifier's solution is restricted to the subspace spanned by the $m$ sampled Nyström points from the outset. This design ensures that the resulting model is sparse by construction, directly addressing the "support vector proliferation" problem in large-scale SVMs.

The research proves that if the eigenvalues decay fast enough, one can achieve generalization performance comparable to the full kernel method while using a number of support vectors that is sublinear relative to the total dataset size. Specifically, for a kernel following a $p$-power law, the number of support vectors can be reduced to $N^{2p/(p^2-1)}$.

Key Insights and Results

  • Exploiting Skewness: Real-world kernel matrices often exhibit "skewed" eigenvalue distributions. This work mathematically proves that the Nyström method is inherently tuned to exploit this decay, explaining why it outperforms theoretical expectations in practical scenarios.
  • Efficiency Threshold: The analysis identifies a critical threshold for efficiency. When $p > 1 + \sqrt{2}$ (approximately 2.41), the number of support vectors required for high-quality generalization becomes significantly less than $N$. This condition is frequently met in Sobolev spaces where $p$ relates to the smoothness of the underlying function.
  • Bridging the Theoretical Gap: The paper successfully narrows the gap between the known lower bound $\Omega(N/m)$ and the previous upper bound $O(N/\sqrt{m})$, providing a more realistic guarantee for practitioners.

Limitations and Future Directions

While the tighter bounds offer a significant advancement, they rely on the incoherence assumption. In datasets where eigenvectors are highly coherent (i.e., information is localized in a few specific points), uniform sampling may fail to capture the necessary structure, and these bounds may not hold. In such cases, data-dependent sampling strategies, such as those using leverage scores, may be required.

Furthermore, while this study focuses on classification, the improved Nyström bounds have broad implications for other kernel-based tasks, including regression, clustering, and dimensionality reduction. Future work may extend these sublinear guarantees to a wider array of machine learning algorithms.

Summary updated

Abstract

We develop two approaches for analyzing the approximation error bound for the Nyström method that approximates a positive semidefinite (PSD) matrix by sampling a small set of columns, one based on a concentration inequality for integral operators, and one based on random matrix theory. We show that the approximation error, measured in the spectral norm, can be improved from O(N/√m) to O(N/m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-ρ</sup> ) in the case of large eigengap, where N is the total number of data points, m is the number of sampled data points, and ρ ∈ (0, 1/2) is a positive constant that characterizes the eigengap. When the eigenvalues of the kernel matrix follow a p-power law, our analysis based on random matrix theory further improves the bound to O(N/m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p-1</sup> ) under an incoherence assumption. We present a kernel classification approach based on the Nyström method and derive its generalization performance using the improved bound. We show that when the eigenvalues of the kernel matrix follow a p-power law, we can reduce the number of support vectors to N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2p/(p2</sup> - 1), which is sublinear in N when p > 1+√2, without seriously sacrificing its generalization performance.
BibTeX
@article{jin2013improved,
  author = {Rong Jin and Tianbao Yang and Mehrdad Mahdavi and Yu-Feng Li and Zhi-Hua Zhou},
  title = {{Improved Bounds for the Nyström Method With Application to Kernel Classification}},
  journal = {IEEE Trans. Information Theory},
  year = {2013},
  url = {https://openreview.net/forum?id=_Ry_4EbQE6},
}
Figure