How Many Machines Can We Use in Parallel Computing for Kernel Ridge Regression?

2018/05/25 by Liu, Meimei, Shang, Zuofeng, Cheng, Guang
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1805.09948

Abstract

This paper aims to solve a basic problem in distributed statistical inference: how many machines can we use in parallel computing? In kernel ridge regression, we address this question in two important settings: nonparametric estimation and hypothesis testing. Specifically, we find a range for the number of machines under which optimal estimation/testing is achievable. The employed empirical processes method provides a unified framework, that allows us to handle various regression problems (such as thin-plate splines and nonparametric additive regression) under different settings (such as univariate, multivariate and diverging-dimensional designs). It is worth noting that the upper bounds of the number of machines are proven to be un-improvable (upto a logarithmic factor) in two important cases: smoothing spline regression and Gaussian RKHS regression. Our theoretical findings are backed by thorough numerical studies.

Related

• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• WONDER: Weighted one-shot distributed ridge regression in high dimensions
• Multi-Layer Kernel Machines: Fast and Optimal Nonparametric Regression with Uncertainty Quantification
• Optimal Rates of Distributed Regression with Imperfect Kernels
• Distributed Kernel Ridge Regression with Communications