Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms

Abstract

We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), with mini-batches and multi-passes over the data. We show that optimal generalization error bounds can be retained for distributed SGM provided that the partition level is not too large. We then extend our results to spectral-regularization algorithms (SRA), including kernel ridge regression (KRR), kernel principal component analysis, and gradient methods. Our results are superior to the state-of-the-art theory. Particularly, our results show that distributed SGM has a smaller theoretical computational complexity, compared with distributed KRR and classic SGM. Moreover, even for non-distributed SRA, they provide the first optimal, capacity-dependent convergence rates, considering the case that the regression function may not be in the RKHS.

53 pages

Cited by in corpus (8)

• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• Kernel Conjugate Gradient Methods with Random Projections
• Towards Sharp Analysis for Distributed Learning with Random Features
• Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces
• Sobolev Norm Learning Rates for Conditional Mean Embeddings
• Generalization Properties of hyper-RKHS and its Applications
• Online nonparametric regression with Sobolev kernels