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

arXiv: https://arxiv.org/abs/1801.07226 · HTML: https://mlsanity.com/paper/1801.07226/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2018.

## Built on by (most cited first, 22 of 22)

- [On the Optimality of Misspecified Spectral Algorithms](https://mlsanity.com/paper/2303.14942/) (2023)
- [On the Optimality of Misspecified Kernel Ridge Regression](https://mlsanity.com/paper/2305.07241/) (2023)
- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [On the Saturation Effect of Kernel Ridge Regression](https://mlsanity.com/paper/2405.09362/) (2024)
- [Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms](https://mlsanity.com/paper/2405.14778/) (2024)
- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)
- [Optimal Convergence Rates for Neural Operators](https://mlsanity.com/paper/2412.17518/) (2024)
- [Sobolev Norm Learning Rates for Conditional Mean Embeddings](https://mlsanity.com/paper/2105.07446/) (2021)
- [On the Impacts of the Random Initialization in the Neural Tangent Kernel Theory](https://mlsanity.com/paper/2410.05626/) (2024)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning](https://mlsanity.com/paper/2401.02734/) (2024)
- [Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfer](https://mlsanity.com/paper/2501.10870/) (2025)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2506.16283/) (2025)
- [Spectral Algorithms on Manifolds through Diffusion](https://mlsanity.com/paper/2403.03669/) (2024)
- [Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operators](https://mlsanity.com/paper/2603.00971/) (2026)
- [Decentralized Online Learning for Random Inverse Problems Over Graphs](https://mlsanity.com/paper/2303.11789/) (2023)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2308.15434/) (2023)
- [FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch](https://mlsanity.com/paper/2409.15216/) (2024)
- [Towards a Statistical Understanding of Neural Networks: Beyond the Neural Tangent Kernel Theories](https://mlsanity.com/paper/2412.18756/) (2024)
- [Self-Regularized Learning Methods](https://mlsanity.com/paper/2603.17160/) (2026)
- [Large Dimensional Kernel Ridge Regression: Extending to Product Kernels](https://mlsanity.com/paper/2605.14524/) (2026)
- [Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees](https://mlsanity.com/paper/2608.25513/) (2026)

## Abstract (arXiv)

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.