Gain with no Pain: Efficient Kernel-PCA by Nystr\"om Sampling

Achieving good statistical accuracy under budgeted computational resources is a central theme in modern machine learning (Bottou and Bousquet, 2008). Indeed, the problem of understanding the interplay and tradeoffs between statistical and computational requirements has recently received much attention. Nonparametric learning, and in particular kernel methods, have provided a natural framework to pursue these questions, see e.g.(Musco and Musco, 2017; Rudi et al., 2015; Alaoui and Mahoney, 2014; Bach, 2013; Calandriello et al., 2018; Orabona et al., 2008). On the one hand, these methods are developed in a sound mathematical setting and their statistical properties are well studied. On the other hand, from a numerical point of view, they scale poorly to large scale problems, and hence improved computational efficiency is of particular interest. While initial studies have mostly focused on approximating kernel matrices (Drineas and Mahoney, 2005; Gittens and Mahoney, 2013; Jin et al., 2013), recent results have highlighted the importance of considering downstream learning tasks, if the interplay between statistics and computation is of interest.