Fast DPP Sampling for Nyström with Application to Kernel Methods

Abstract

The Nyström method has long been popular for scaling up kernel methods. Its theoretical guarantees and empirical performance rely critically on the quality of the landmarks selected. We study landmark selection for Nyström using Determinantal Point Processes (DPPs), discrete probability models that allow tractable generation of diverse samples. We prove that landmarks selected via DPPs guarantee bounds on approximation errors; subsequently, we analyze implications for kernel ridge regression. Contrary to prior reservations due to cubic complexity of DPPsampling, we show that (under certain conditions) Markov chain DPP sampling requires only linear time in the size of the data. We present several empirical results that support our theoretical analysis, and demonstrate the superior performance of DPP-based landmark selection compared with existing approaches.

References in corpus (5)

• Determinantal Processes and Independence
• Fast Randomized Kernel Methods With Statistical Guarantees
• Less is More: Nyström Computational Regularization
• Efficient Sampling for k-Determinantal Point Processes
• Fast Mixing for Discrete Point Processes

Cited by in corpus (21)

• Recursive Sampling for the Nyström Method
• Rates of Convergence for Sparse Variational Gaussian Process Regression
• Efficient Sampling for k-Determinantal Point Processes
• Batched Gaussian Process Bandit Optimization via Determinantal Point Processes
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Convergence of Sparse Variational Inference in Gaussian Processes Regression
• Kronecker Determinantal Point Processes
• Determinantal Point Processes for Mini-Batch Diversification
• Scalable Gaussian Processes on Discrete Domains
• Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes
• Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation
• Flexible Modeling of Diversity with Strongly Log-Concave Distributions
• Quadruply Stochastic Gaussian Processes
• VBALD - Variational Bayesian Approximation of Log Determinants
• DPPNet: Approximating Determinantal Point Processes with Deep Networks
• Variational Gaussian Processes: A Functional Analysis View
• Testing Determinantal Point Processes
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes
• Towards Deterministic Diverse Subset Sampling
• Diverse Online Feature Selection