Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering

2019/05/15 by Fernandez, Manuel, Woodruff, David P., Yasuda, Taisuke
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1905.06394

Abstract

We present tight lower bounds on the number of kernel evaluations required to approximately solve kernel ridge regression (KRR) and kernel k-means clustering (KKMC) on n input points. For KRR, our bound for relative error approximation to the minimizer of the objective function is Ω(nd_eff^λ/ε) where d_eff^λ is the effective statistical dimension, which is tight up to a log(d_eff^λ/ε) factor. For KKMC, our bound for finding a k-clustering achieving a relative error approximation of the objective function is Ω(nk/ε), which is tight up to a log(k/ε) factor. Our KRR result resolves a variant of an open question of El Alaoui and Mahoney, asking whether the effective statistical dimension is a lower bound on the sampling complexity or not. Furthermore, for the important practical case when the input is a mixture of Gaussians, we provide a KKMC algorithm which bypasses the above lower bound.

Related

• On the optimality of kernels for high-dimensional clustering
• Off-the-grid: Fast and Effective Hyperparameter Search for Kernel Clustering
• Kernel Ridge Regression via Partitioning
• A Randomized Approach to Efficient Kernel Clustering
• Kernel k-Means, By All Means: Algorithms and Strong Consistency