This is the public, feature-limited version of the conference webpage. After Registration and login please visit the full version.

Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method

Michal Derezinski, Rajiv Khanna, Michael W Mahoney

Oral presentation: Orals & Spotlights Track 24: Learning Theory
on 2020-12-09T18:00:00-08:00 - 2020-12-09T18:15:00-08:00
Poster Session 5 (more posters)
on 2020-12-09T21:00:00-08:00 - 2020-12-09T23:00:00-08:00
Abstract: The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental question in this area is: 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 approximation factor 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.

Pre-recorded Oral Presentation

To ask questions please use rocketchat, available only upon registration and login.

Preview Video and Chat

To see video, interact with the author and ask questions please use registration and login.