How Many Machines Can We Use in Parallel Computing for Kernel Ridge Regression?
This addresses a fundamental bottleneck in distributed statistical inference for researchers and practitioners, providing theoretical limits that are incremental but with proven optimality in certain scenarios.
The paper tackles the problem of determining the maximum number of machines that can be used in parallel computing for kernel ridge regression without losing optimality in estimation and testing, finding specific ranges for this number and proving these bounds are nearly optimal in key cases like smoothing spline and Gaussian RKHS regression.
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.