WNCG alumnus Rajiv Khanna and his colleagues Michal Derezinski and Michael W. Mahoney received the Best Paper Award at NeurIPS 2020. Their winning paper, “Improved Guarantees and a Multiple-Descent Curve for Column Subset Selection and the Nyström Method,” was presented in the conference’s Learning Theory track. The paper was one of three to receive the distinction for 2020.
The award committee chose the winners in a two-stage selection process which considered the research’s impact, creativity, and “potential to endure,” along with its scientific and academic rigor.
The committee’s announcement selecting Derezinski, Khanna, and Mahoney’s paper included the following assessment:
Selecting a small but representative subset of column vectors from a large matrix is a hard combinatorial problem, and a method based on cardinality-constrained determinantal point processes is known to give a practical approximate solution. This paper derives new upper and lower bounds for the approximation factor of the approximate solution over the best possible low-rank approximation, which can even capture the multiple-descent behavior with respect to the subset size. The paper further extends the analysis to obtaining guarantees for the Nyström method. Since these approximation techniques have been widely employed in machine learning, this paper is expected to have substantial impact and give new insight into, for example, kernel methods, feature selection, and the double-descent behavior of neural networks.
Rajiv Khanna is currently a Postdoctoral Researcher with the Foundations of Data Analysis Institute at the University of California, Berkeley. He received his Ph.D. from the University of Texas at Austin in 2018 and was a member of WNCG in Prof. Joydeep Ghosh’s IDEAL Lab.