Paper Info
Title
Stability-Based Generalization Analysis of Distributed Learning Algorithmsfor Big Data.
Abstract
As one of the efficient approaches to deal with big data, divide-and-conquer distributed algorithms, such as the distributed kernel regression, bootstrap, structured perception training algorithms, and so on, are proposed and broadly used in learning systems. Some learning theories have been built to analyze the feasibility, approximation, and convergence bounds of these distributed learning algorithms. However, less work has been studied on the stability of these distributed learning algorithms. In this paper, we discuss the generalization bounds of distributed learning algorithms from the view of algorithmic stability. First, we introduce a definition of uniform distributed stability for distributed algorithms and study the distributed algorithms’ generalization risk bounds. Then, we analyze the stability properties and generalization risk bounds of a kind of regularization-based distributed algorithms. Two generalization distributed risks obtained show that the generalization distributed risk bounds for the difference between their generalization distributed and empirical distributed/leave-one-computer-out risks are closely related to the size of samples <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> and the amount of working computers <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(m/{n}^{1/2})$ </tex-math></inline-formula> . Furthermore, the results in this paper indicate that, for a good generalization regularized distributed kernel algorithm, the regularization parameter <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\lambda $ </tex-math></inline-formula> should be adjusted with the change of the term <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$m/{n}^{1/2}$ </tex-math></inline-formula> . These theoretic discoveries provide the useful guidance when deploying the distributed algorithms on practical big data platforms. We explore our theoretic analyses through two simulation experiments. Finally, we discuss some problems about the sufficient amount of working computers, nonequivalence, and generalization for distributed learning. We show that the rules for the computation on one single computer may not always hold for distributed learning.
Year
DOI
Venue
2020
10.1109/TNNLS.2019.2910188
IEEE transactions on neural networks and learning systems
Keywords
DocType
Volume
Stability analysis,Computers,Big Data,Kernel,Approximation algorithms,Training,Distributed algorithms
Journal
31
Issue
ISSN
Citations 
3
2162-237X
3
PageRank 
References 
Authors
0.38
2
3
Name
Order
Citations
PageRank
Xinxing Wu16818.44
Junping Zhang2117359.62
Fei-Yue Wang35273480.21