Improved Guarantees and a Multiple-descent Curve for Column Subset Selection and the Nystrom Method (Extended Abstract)

Michal Derezinski, Rajiv Khanna, Michael W. Mahoney

Introduction

In modern machine learning, the challenge of processing massive datasets often necessitates low-rank matrix approximations. While techniques like Principal Component Analysis (PCA) provide optimal approximations, they yield "abstract" features that lack physical interpretability. The Column Subset Selection Problem (CSSP) and the Nyström method address this by selecting a representative subset of actual columns or instances. However, choosing real columns introduces a "cost of interpretability"—the loss in accuracy compared to the optimal singular vectors. Standard theory suggests a worst-case approximation factor of $k+1$ for a subset of size $k$, a bound that is often overly pessimistic in practice. This work bridges the gap by providing tighter, data-dependent guarantees that account for the spectral properties of the data.

Theoretical Framework: Beyond Worst-Case Bounds

The authors leverage Determinantal Point Processes (DPPs), randomized algorithms that favor diverse subset selection, to derive a new "Master Theorem." This theorem provides an upper bound on the approximation factor based on the matrix's stable rank—a measure of its effective dimensionality.

Unlike previous analyses that focused on worst-case scenarios, this framework considers how the approximation factor behaves under specific spectral decay patterns:

  • Polynomial spectral decay: Singular values decrease at a rate of $i^{-p}$.
  • Exponential spectral decay: Singular values decrease at a rate of $(1-\delta)^i$.

For matrices exhibiting polynomial decay, the expected approximation factor is shown to be bounded by a constant, independent of $k$. For exponential decay, the bound scales as $O(1+\delta k)$, which is significantly tighter than the traditional $k+1$ bound.

Figure 1: Theoretical upper and lower bounds compared with experimental results, highlighting the multiple-descent phenomenon where the approximation factor fluctuates with subset size k.

The Multiple-Descent Phenomenon

A central discovery of this research is the "multiple-descent" curve. While increasing the subset size $k$ monotonically reduces the absolute approximation error, the relative error—the approximation factor—does not follow a simple downward trajectory. Instead, it exhibits multiple peaks and valleys.

The authors demonstrate that these peaks align precisely with sharp drops in the singular value spectrum. When data possesses a clear hierarchical structure, selecting a subset size that "misses" a significant spectral drop makes the approximation task harder relative to the optimal PCA approach. Theorem 3 establishes a lower bound, proving that this behavior is an inherent property of CSSP and Nyström tasks rather than an algorithmic artifact.

Empirical Validation

The theoretical predictions are validated using the eunite2001 dataset. By applying a Gaussian Radial Basis Function (RBF) kernel and varying the parameter $\sigma$, the authors manipulate the spectral decay of the kernel matrix.

Figure 4: Empirical results on the eunite2001 dataset. The bottom plot shows spectral decay for different \sigma values, while the top plot shows the corresponding approximation factor. Peaks in the approximation factor align with significant drops in the eigenvalue spectrum.

As shown in the experimental results, the approximation factor displays distinct peaks that correspond to the "steps" in the eigenvalue decay. This confirms that the "shape" of the data's spectrum is the primary driver of the approximation performance.

Conclusion and Future Work

This work provides a more nuanced understanding of matrix approximation by moving beyond pessimistic worst-case bounds. By identifying the multiple-descent phenomenon and its link to spectral decay, it offers practitioners a better way to estimate the cost of interpretability. Future research directions include refining the concentration of measure analysis to remove potential mathematical artifacts and extending these results to provide high-probability bounds for individual algorithm runs.

Summary updated

Abstract

The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing interpretable low-rank approximations of large datasets by selecting a small but representative set of features or instances. A fundamental question in this area is: what is the cost of this interpretability, i.e., how well can a data subset of size k compete with the best rank k approximation? We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees which go beyond the standard worst-case analysis. Our approach leads to significantly better bounds for datasets with known rates of singular value decay, e.g., polynomial or exponential decay. Our analysis also reveals an intriguing phenomenon: the cost of interpretability as a function of k may exhibit multiple peaks and valleys, which we call a multiple-descent curve. A lower bound we establish shows that this behavior is not an artifact of our analysis, but rather it is an inherent property of the CSSP and Nystrom tasks. Finally, using the example of a radial basis function (RBF) kernel, we show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
BibTeX
@inproceedings{derezinski2021improved,
  author = {Michal Derezinski and Rajiv Khanna and Michael W. Mahoney},
  title = {{Improved Guarantees and a Multiple-descent Curve for Column Subset Selection and the Nystrom Method (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/647},
}
Figure