Decentralised Learning with Random Features and Distributed Gradient Descent
Decentralised Learning with Random Features and Distributed Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Dominic Richards;Patrick Rebeschini;L. Rosasco
中科院分区：
文献类型：
--
作者：
Dominic Richards;Patrick Rebeschini;L. Rosasco
我们研究了具有隐式正则化和随机特征的分布式梯度下降在同质环境中的泛化性能，其中代理网络被给予独立于相同未知分布采样的数据。除了减少内存占用之外，随机特征在这种情况下特别方便，因为它们提供了跨代理的通用参数化，可以克服以前实现去中心化核回归的困难。在标准源和容量假设下，我们为每个代理的预测性能建立了高概率界限，作为步长、迭代次数、通信矩阵的逆谱间隙和随机特征数量的函数。通过调整这些参数，我们获得了相对于网络中样本总数而言最小最大最优的统计率。该算法在内存成本方面比单机梯度下降提供了线性改进，并且当代理在网络大小和逆谱间隙方面持有足够的数据时，任何网络拓扑的计算运行时间都可以线性加速。我们提出的模拟显示了随机特征、迭代和样本的数量如何影响预测性能。
We investigate the generalisation performance of Distributed Gradient Descent with Implicit Regularisation and Random Features in the homogenous setting where a network of agents are given data sampled independently from the same unknown distribution. Along with reducing the memory footprint, Random Features are particularly convenient in this setting as they provide a common parameterisation across agents that allows to overcome previous difficulties in implementing Decentralised Kernel Regression. Under standard source and capacity assumptions, we establish high probability bounds on the predictive performance for each agent as a function of the step size, number of iterations, inverse spectral gap of the communication matrix and number of Random Features. By tuning these parameters, we obtain statistical rates that are minimax optimal with respect to the total number of samples in the network. The algorithm provides a linear improvement over single machine Gradient Descent in memory cost and, when agents hold enough data with respect to the network size and inverse spectral gap, a linear speed-up in computational runtime for any network topology. We present simulations that show how the number of Random Features, iterations and samples impact predictive performance.