NeurIPS 2020

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

Meta Review

The paper gives improved approximation guarantees for the column subset selection problem (CSSP) and the Nystrom’s method for low-rank approximation of large datasets. The analysis reveals a multiple descent phenomenon which authors argue is real and not an artifact of their analysis. The paper is written clearly, and the results and insights in the paper are compelling. Overall, a good paper. Accept!