Modern compression methods have found diverse applications in speeding up range of unsupervised tasks like integration, non-parametric hypothesis testing, and MCMC simulations. However, it remains unclear how to extend these recent advancements from the unsupervised learning domain to the supervised learning domain. We make a first step and introduce a meta-algorithm based on Kernel Thinning (KT) of for non-parametric regression. Specifically, we combine two classical algorithms, the Nadaraya-Watson (NW) regression and the Kernel Ridge Regression (KRR), with KT to speed up training/inference time in these problems. We show how distribution compression with KT in each setting reduces to constructing an appropriate kernel, and introduce the Kernel-Thinned NW and Kernel-Thinned KRR estimators. We prove that KT-based regression estimators enjoy significantly superior computational efficiency over the full-data estimators and improved statistical efficiency over i.i.d. subsampling of the training data. We validate our design choices with experiments on both simulated and real-world data.