Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
arXiv:1905.03135
Abstract
We analyse the learning performance of Distributed Gradient Descent in the context of multi-agent decentralised non-parametric regression with the square loss function when i.i.d. samples are assigned to agents. We show that if agents hold sufficiently many samples with respect to the network size, then Distributed Gradient Descent achieves optimal statistical rates with a number of iterations that scales, up to a threshold, with the inverse of the spectral gap of the gossip matrix divided by the number of samples owned by each agent raised to a problem-dependent power. The presence of the threshold comes from statistics. It encodes the existence of a "big data" regime where the number of required iterations does not depend on the network topology. In this regime, Distributed Gradient Descent achieves optimal statistical rates with the same order of iterations as gradient descent run with all the samples in the network. Provided the communication delay is sufficiently small, the distributed protocol yields a linear speed-up in runtime compared to the single-machine protocol. This is in contrast to decentralised optimisation algorithms that do not exploit statistics and only yield a linear speed-up in graphs where the spectral gap is bounded away from zero. Our results exploit the statistical concentration of quantities held by agents and shed new light on the interplay between statistics and communication in decentralised methods. Bounds are given in the standard non-parametric setting with source/capacity assumptions.
References in corpus (12)
- Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
- Geographic Gossip: Efficient Averaging for Sensor Networks
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Communication Complexity of Distributed Convex Learning and Optimization
- Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
- Optimal Rates for Multi-pass Stochastic Gradient Methods
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
- Learning with SGD and Random Features
- Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms
- Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
- Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations