Computational Limits of A Distributed Algorithm for Smoothing Spline

作者：Shang Zuofeng^*; Cheng Guang

来源：Journal of Machine Learning Research, 2017, 18: 1.

• divide-and-conquer
• computational limits
• smoothing spline
• splitotic theory

In this paper, we explore statistical versus computational trade-off to address a basic question in the application of a distributed algorithm: what is the minimal computational cost in obtaining statistical optimality? In smoothing spline setup, we observe a phase transition phenomenon for the number of deployed machines that ends up being a simple proxy for computing cost. Specifically, a sharp upper bound for the number of machines is established: when the number is below this bound, statistical optimality (in terms of non parametric estimation or testing) is achievable; otherwise, statistical optimality becomes impossible. These sharp bounds partly capture intrinsic computational limits of the distributed algorithm considered in this paper, and turn out to be fully determined by the smoothness of the regression function. We name the asymptotic analysis on such split-and aggregation estimation/inference as "splitotic" theory. As a side remark, we argue that sample splitting may be viewed as an alternative form of regularization, playing a similar role as smoothing parameter.

• 出版日期2017