Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning

In this paper, we use tools from rate-distortion theory to establish new upper bounds on the generalization error of statistical distributed learning algorithms. Specifically, there are K clients whose individually chosen models are aggregated by a central server. The bounds depend on the compressibility of each client's algorithm while keeping other clients' algorithms un-compressed, and leveraging the fact that small changes in each local model change the aggregated model by a factor of only 1K. Adopting a recently proposed approach by Sefidgaran et al., and extending it suitably to the distributed setting, enables smaller rate-distortion terms which are shown to translate into tighter generalization bounds. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error of the distributed setting decays faster than that of the centralized one with a factor of Op a logpKqKq. This finding is validated also experimentally. A similar conclusion is obtained for a multiple-round federated learning setup where each client uses stochastic gradient Langevin dynamics (SGLD). Notation. Random variables, their realizations, and their domains are denoted respectively by upper-case, lower-case, and calligraphy fonts, e.g., X, x, and X . Their distributions and expectations are denoted by P X and ErXs. The random variable X is called σ-subgaussian if for all t P R, ErexpptpX ´ErXsqqs ď exppσ 2 t 2 2q, e.g., if X P ra, bs, then X is b´a 2 -subgaussian. A vector of m P N numbers (or random variables) px 1 , . . . , x m q are denoted by either x 1:m or tx i u m i"1 , depending on the context, and the vector px 1 , . . . , x i´1 , x i`1 , . . . , x m q is denoted by x 1:mzi . Similarly for n, m P N, a vector px 1,1 , . . . , x 1,m , x 2,1 , . . . , x 2,m , x n,1 , . . . , x n,m q is denoted by x 1:n,1:m or tx i,1:m u iPrns , or tx 1:n,j u jPrms , where rns " t1, . . . , nu. Parts of our results are stated in terms of information-theoretic quantities: for random variables X and Y , we denote the differential entropy of X by hpXq, the conditional differential entropy of X given Y by hpX|Y q, and the mutual information between them by IpX; Y q. Moreover, the Kullback-Leibler (KL) divergence between distributions Q and P is denoted by D KL pQP q. For more details, we refer the reader to [42, 43] . Preliminaries and problem setup For convenience, we start with a brief review of the standard (centralized) statistical learning setup together with a few definitions and recent results associated with it. Let the input data Z be distributed according to an unknown distribution µ over the data space Z. A training dataset S " pZ 1 , . . . , Z n q " µ bn consists of n samples tZ i u generated independently each according to µ.