Computational Limits of A Distributed Algorithm for Smoothing Spline
Computational Limits of A Distributed Algorithm for Smoothing Spline
复制标题
DOI：
--
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Zuofeng Shang;Guang Cheng
中科院分区：
文献类型：
--
作者：
Zuofeng Shang;Guang Cheng
在本文中，我们将探讨统计与计算的权衡，以解决一个基本的问题，在分布式算法的应用：什么是最小的计算成本，在获得统计最优？在平滑样条设置中，我们观察到部署的机器数量的相变现象，最终成为计算成本的简单代理。具体来说，建立了机器数量的严格上限：当机器数量低于这个上限时，统计最优性（在非参数估计或检验方面）是可以实现的;否则，统计最优性就变得不可能了。这些尖锐的边界部分捕获本文中考虑的分布式算法的内在计算限制，并完全由回归函数的平滑度决定。作为一个侧面的评论，我们认为，样本分裂可以被看作是一种替代形式的正则化，发挥类似的作用，平滑参数。
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 nonparametric 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. 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.