MnLargeSymbols’164 MnLargeSymbols’171

# Rate-Distortion Theoretic Bounds on
Generalization Error for Distributed Learning

Milad Sefidgaran${}^{\>\nmid}$, Romain Chor$\>{}^{\nmid}$, Abdellatif
Zaidi$\>{}^{\dagger}$$\>{}^{\nmid}$
∤ Paris Research Center, Huawei Technologies France
† Université Paris-Est, Champs-sur-Marne 77454, France
{milad.sefidgaran2<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

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 $1/K$. 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 $\mathcal{O}(\sqrt{\log(K)/K})$. 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).

##  1 Introduction

A key performance indicator of any stochastic learning algorithm that uses a
given finite set of data points is how well it performs on points that are
outside that set, i.e., unseen data. This is often captured through the so-
called _generalization error_. The questions of what really controls the
generalization error of a given stochastic algorithm, and how to make it
sufficiently small, are still not yet well understood, however. For example,
while classic approaches (1) suggest that algorithms with over-parameterized
models are likely to _overfit_ , it is now known that there exist a few such
ones which do generalize well (2). Common approaches to studying the
generalization error of a statistical learning algorithm often consider the
_effective hypothesis space_ induced by the algorithm, rather than the entire
hypothesis space, or the information leakage about the _training dataset_.
Examples include information-theoretic (mutual information) approaches (3; 4;
5; 6; 7; 8), compression-based approaches (9; 10; 11; 12; 13) and intrinsic-
dimension or fractal based approaches (14; 15; 16). Recently, a novel approach
(17) that generalizes the notion of algorithm compressibility by using lossy
covering from source coding concepts was used to show that the compression
error rate of an algorithm is strongly connected to its generalization error
both in-expectation and with high probability; and, consequently, establish
new rate-distortion-based bounds on the generalization error. The bounds of
(17) were shown to possibly improve strictly upon those of (4; 18) and (8).
The approach also has the advantage to offer a unifying perspective on mutual
information, compressibility, and fractal-based frameworks.

Another major focus of machine learning research over recent years has been
the study of statistical learning algorithms when applied in distributed
(network or graph) settings. In part, this is due to the emergence of new
applications in which resources are constrained, data is distributed or the
need to preserve privacy (19; 20; 21; 22). Reducing the computational
complexity by offloading the model training using algorithms such as
_parallel_ stochastic gradient descent is another reason for the popularity of
these algorithms. Generally, that results in extra communication costs,
however (23; 24; 25; 26; 27). Example such algorithms include the now popular
_Federated Learning_ (28; 29; 30; 31; 32; 33), the _Split Learning_ of (34),
_Group Alternating Direction Method of Multipliers_ (35), and the so-called
_in-network learning_ of (36; 37). Despite its importance, however, little is
known about the generalization guarantees of distributed statistical learning
algorithms. In fact, in the distributed learning setting the technical
challenges are numerous, including the lack of a proper definition of the
generalization error in this case (38; 39). Notable exception works in this
direction include (40) and (41). In (40), information-theoretic upper bounds
on the generalization error of distributed statistical learning algorithms are
obtained merely by viewing the entire distributed system, from the input data
to each (local) algorithm to the output aggregated model, as a single
(centralized) algorithm and applying to it the bounds of (4; 18). While
somewhat useful this, however, has left the difference between the bounds for
the distributed learning setting and their counterparts for the centralized
learning setting implicit in the involved mutual information terms. The
problem of studying the generalization error of distributed statistical
learning algorithms was further studied in the recent (41). Therein, using
results from (18), the authors establish bounds on the expectation of the
generalization error for two special cases. For the first, linear or location
models with Bregman divergence loss, the proposed bound on the generalization
error for the distributed setup (41, Theorem 4) is shown better (i.e.,
smaller) than its counter-part for the centralized learning setting by a
factor of $\mathcal{O}(1/\sqrt{K})$, where $K$ is the number of clients. This
result, however, relies strongly on the assumed linearity of the loss with
respect to the hypothesis. For the second, Lipschitz continuous loss (41,
Theorem 5), similar behavior is shown by reducing the problem to the
centralized case and using the triangle inequality.

In this work, we study the generalization error of distributed statistical
learning algorithms. Essentially we extend suitably the approach of (17) to
establish rate-distortion theoretic upper bounds on the generalization error.
In doing so, we bring the analysis of the distributed architecture of the
learning problem into the bounds. The bounds, which hold with high probability
and in-expectation, allow to only consider the compressibility of each local
algorithm – the latter having an effect with a factor of only $1/K$ on the
aggregated model order-wise. This is shown to result in a more relaxed
distortion criterion for the _local algorithm compressibility_ , smaller rate-
distortion terms; and, in turn, better generalization bounds. Furthermore, we
apply our results to the _distributed support vector machines_ (DSVM). The
obtained bounds suggest that for the non-separable data, the generalization
error of the distributed setting decays faster than that of the centralized
one with a factor of $\sqrt{\log(K)/K}$. We conducted experiments on DSVM that
confirm this finding. We also consider the related Federated learning setting,
and derive bounds on the generalization error in two setups: when each client
applies the _stochastic gradient Langevin dynamics_ (SGLD) method and locally
deterministic algorithms with Lipschitz loss (in Appendix C.1). In all cases,
our bounds suggest a decreasing behavior for the generalization performance as
$K$ grows.

##### Notation.

Random variables, their realizations, and their domains are denoted
respectively by upper-case, lower-case, and calligraphy fonts, _e.g.,_ $X$,
$x$, and $\mathcal{X}$. Their distributions and expectations are denoted by
$P_{X}$ and $\mathbb{E}[X]$. The random variable $X$ is called
$\sigma$-_subgaussian_ if for all $t\in\mathbb{R}$,
$\mathbb{E}[\exp(t(X-\mathbb{E}[X]))]\leq\exp(\sigma^{2}t^{2}/2)$, _e.g.,_ if
$X\in[a,b]$, then $X$ is $\frac{b-a}{2}$-subgaussian. A vector of
$m\in\mathbb{N}$ numbers (or random variables) $(x_{1},\ldots,x_{m})$ are
denoted by either $x_{1:m}$ or $\\{x_{i}\\}_{i=1}^{m}$, depending on the
context, and the vector $(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{m})$ is
denoted by $x_{1:m\setminus i}$. Similarly for $n,m\in\mathbb{N}$, a vector
$(x_{1,1},\ldots,x_{1,m},x_{2,1},\ldots,x_{2,m},x_{n,1},\ldots,x_{n,m})$ is
denoted by $x_{1:n,1:m}$ or $\\{x_{i,1:m}\\}_{i\in[n]}$, or
$\\{x_{1:n,j}\\}_{j\in[m]}$, where $[n]=\\{1,\ldots,n\\}$. 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 $h(X)$,
the _conditional differential entropy_ of $X$ given $Y$ by $h(X|Y)$, and the
mutual information between them by $I(X;Y)$. Moreover, the _Kullback–Leibler_
(KL) divergence between distributions $Q$ and $P$ is denoted by
$D_{KL}(Q\|P)$. For more details, we refer the reader to (42; 43).

##  2 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 $\mu$ over the _data space_ $\mathcal{Z}$. A _training
dataset_ $S=(Z_{1},\ldots,Z_{n})\sim\mu^{\otimes n}$ consists of $n$ samples
$\\{Z_{i}\\}$ generated independently each according to $\mu$. A possibly
stochastic learning algorithm
$\mathcal{A}\colon\mathcal{Z}^{n}\mapsto\mathcal{W}$ (e.g., stochastic
gradient descent) assigns an hypothesis $\mathcal{A}(S)=W$ chosen from the
_hypothesis class_ $\mathcal{W}\subseteq\mathbb{R}^{d}$ to every
$S\in\mathcal{Z}^{n}$. The map $\mathcal{A}$ induces a conditional
distribution $P_{W|S}$ which together with $\mu$ induce the joint dataset-
hypothesis distribution $P_{S,W}=\mu^{\otimes n}P_{W|S}$. The quality of the
prediction is measured using a loss function
$\ell\colon\mathcal{Z}\times\mathcal{W}\mapsto\mathbb{R}^{+}$. The
_generalization error_ of an algorithm $\mathcal{A}$ is defined as
$\operatorname{gen}(s,w)\coloneqq\mathcal{L}(w)-\hat{\mathcal{L}}(s,w)$ where
$\mathcal{L}(w)\coloneq\mathbb{E}_{Z\sim\mu}[\ell(z,w)]$ denotes the
population risk and
$\hat{\mathcal{L}}(s,w)\coloneq\frac{1}{n}\sum_{j\in[n]}\ell(z_{j},w)$ denotes
the empirical risk. Note that the generalization error depends on the loss
function $\ell(z,w)$, underlying distribution $\mu$, the sample size $n$, and
also the learning algorithm $P_{W|S}$. In the binary classification context,
where $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$ and
$\mathcal{Y}=\\{-1,+1\\}$, we often consider the 0-1 loss function
$\ell_{0}(z,w)\coloneqq\mathbbm{1}_{\\{yf(x,w)<0\\}}$, where the sign of
$f(x,w)$, $f\colon\mathcal{X}\times\mathcal{W}\mapsto\mathbb{R}$, is the label
prediction by hypothesis $w$ and $\mathbbm{1}$ is the indicator function. In
this setup, it is common to assess the empirical risk with respect to 0-1 loss
function with margin $\theta\in\mathbb{R}^{+}$ defined as
$\ell_{\theta}(z,w)\coloneqq\mathbbm{1}_{\\{yf(x,w)<\theta\\}}$, while using
0-1 loss function for the population risk evaluation. We denote the
corresponding empirical risk as
$\hat{\mathcal{L}}_{\theta}(s,w)\coloneqq\frac{1}{n}\sum_{j\in[n]}\ell_{\theta}(z_{j},w)$
and the generalization error as
$\operatorname{gen}_{\theta}(s,w)\coloneqq\mathcal{L}(w)-\hat{\mathcal{L}}_{\theta}(s,w)$.

The exact analysis of the generalization error $\operatorname{gen}(S,W)$ seems
out of reach; and, for this reason, as already mentioned upper bounds on it
were developed using an information-theoretic approach. Essentially, such an
approach connects the generalization error of a statistical learning algorithm
$\mathcal{A}$ with the mutual information between the input data sample $S$
and the algorithm output $W=\mathcal{A}(S)$. For details, the reader may refer
to a line of work that was initiated by Russo and Zou (3) and Xu and Raginsky
(4) and since then improved by using various conditional versions of mutual
information. Other approaches rely on the observation that the output $W$ can
be compressible in some suitable sense (9) or the algorithm might generate a
fractal structure (14).

Very recently, an approach (17) that relies on probabilistic
$\epsilon$-covering from source coding concepts was proposed and shown to
possibly improve strictly over the aforementioned, seemingly unrelated,
approaches, while offering a unifying framework to them. The upper bounds of
(17) are rate-distortion theoretic. Specifically, let $\hat{\mathcal{W}}$ be
the alphabet of the _compressed hypothesis_ and
$\hat{\ell}\colon\mathcal{Z}\times\hat{\mathcal{W}}\mapsto\mathbb{R}^{+}$ a
loss function (possibly different from $\ell$). Accordingly, for
$\hat{w}\in\hat{\mathcal{W}}$ and $s\in\mathcal{Z}^{n}$, let
$\operatorname{gen}(s,\hat{w})$ be defined with respect to $\hat{\ell}$. For
every distribution $Q$ defined over $\mathcal{S}\times\mathcal{W}$, the rate-
distortion function with respect to $\hat{\mathcal{W}}$ is defined as

$\displaystyle\mathfrak{RD}(Q,\epsilon)\coloneq$
$\displaystyle\inf\nolimits_{P_{\hat{W}|S}}I(S;\hat{W}),$
$\displaystyle\text{s.t.}\quad\mathbb{E}_{(S,W)\sim
Q}[\operatorname{gen}\left(S,W\right)]-$
$\displaystyle\mathbb{E}_{(S,\hat{W})\sim
Q_{S}P_{\hat{W}|S}}[\operatorname{gen}(S,\hat{W})]\leq\epsilon.$ (1)

where $Q_{S}$ is the $Q$-marginal of $S$, and the infimum is taken over all
Markov kernels (conditional distributions) of a random variable
$\hat{W}\in\hat{\mathcal{W}}$ given $S$. Note that $P_{S,W}$ induced by the
algorithm $\mathcal{A}$ is a particular case of $Q$. In the following, we
shortly discuss the related intuition and concept behind the above terms. The
reader is referred to Appendix A for more details on this.

This rate-distortion function $\mathfrak{RD}(Q,\epsilon)$ is the adaptation of
the rate-distortion function emerged in the lossy source compression context
(44; 42) to stochastic learning algorithms (17). In the lossy source
compression context (44; 42), this function quantifies the fundamental
compression rate of a source $X\sim P_{X}$ to within some desired average
distortion level $\epsilon$. To this end, infinitely many i.i.d. instances of
the source ($\\{X_{i}\\}_{i\in[m]}$, $X_{i}\sim P_{X}$, and
$m\rightarrow\infty$) are compressed (quantized) simultaneously. The joint
compression approach is known as the _block-coding_ technique. In the learning
context, this term quantifies the _lossy algorithm compressibility_ (17), with
the following intuition for the case where $\mathcal{Z}$ and $\mathcal{W}$ are
finite sets. Each $P_{\hat{W}|S}$ denotes a learning algorithm and the
distortion criterion
$\mathbb{E}[\operatorname{gen}(S,W)-\operatorname{gen}(S,\hat{W})]\leq\epsilon$
guarantees that in average the difference between the generalization error of
the original algorithm $P_{W|S}$ and that of the “compressed” algorithm
$P_{\hat{W}|S}$ does not exceed $\epsilon$. The rate-distortion term
$\mathfrak{RD}(P_{S,W},\epsilon)$ quantifies the lossy compressibility of the
algorithm $P_{W|S}$ in the following sense: for large $m\in\mathbb{N}$ and
every admissible $P_{\hat{W}|S}$, a compressed hypothesis space of size
$N_{m}\approx e^{mI(S;\hat{W})}$ can be found such that, with high
probability, for each $m$ i.i.d. instances of the original algorithm $P_{W|S}$
there exists at least one compressed hypothesis for which the difference
between the average generalization error over the $m$ i.i.d. instances of
$P_{W|S}$ at hand and that of the found hypothesis does not exceed $\epsilon$.
Recall the tail bound on the generalization error of (17, Theorem 10).

######  Theorem 1 ((17, Theorem 10) ).

Suppose that the learning algorithm $\mathcal{A}(S)$ induces $P_{S,W}$ and
suppose that for all $\hat{w}\in\hat{\mathcal{W}}$, $\hat{\ell}(Z,\hat{w}$) is
$\sigma$-subgaussian. Then, for any fixed $\epsilon\in\mathbb{R}$ and
$\delta\geq 0$, with probability at least $1-\delta$,
$\operatorname{gen}\left(S,W\right)\leq\sqrt{2\sigma^{2}\left(R_{p}(\delta,\epsilon)+\log(1/\delta)\right)/n}+\epsilon$,
where $R_{p}(\delta,\epsilon)\coloneq\sup\limits_{Q\colon
D_{KL}(Q\|P_{S,W})\leq\log(1/\delta)}\mathfrak{RD}(Q,\epsilon)$ and the
supremum is over all possible distributions over
$\mathcal{S}\times\mathcal{W}$.

The above bound depends not only $\mathfrak{RD}(P_{S,W},\epsilon)$ but also on
$\mathfrak{RD}(Q,\epsilon)$ terms for all distributions $Q$ that are close
enough to $P$. In other words, to guarantee a good generalization performance,
the compressibility of the algorithm under every such small perturbation of
$P_{S,W}$ needs to be considered.

######  Remark 1.

The reader may notice two (minor) differences between Theorem 1 as stated here
and (17, Theorem 10). First, we here express the rate-distortion terms with
respect to the distortion function
$d(w,\hat{w};s)\coloneqq\operatorname{gen}(s,w)-\operatorname{gen}(s,\hat{w})$
instead of a possibly smaller distortion function
$d^{\prime}(w,\hat{w};s)\coloneqq\inf_{(s^{\prime},w^{\prime})\in\operatorname{supp}(Q)}\operatorname{gen}(s^{\prime},w^{\prime})-\operatorname{gen}(s,\hat{w})$
that was considered in (17), where $\operatorname{supp}(Q)$ denotes the
support of $Q$. Even though the latter could possibly lead to stronger
results, we do not consider it here because it is less amenable to
computations. Second, in Theorem 1 the loss function $\hat{\ell}(z,\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu})$ is allowed to differ
from the original $\ell(z,w)$; and this possibly leads to some (rather small)
improvement of the result of (17, Theorem 10). The mentioned two small
differences, however, do not require any change in the proof of (17, Theorem
10).

######  Remark 2.

Similar to (17, Theorem 10), most of our results that will follow in this
paper require the subgaussianity assumption of the loss function to hold. In
both cases the assumption is used to properly bound the moment generating
function (MGF) of a specific zero-mean random variable using the Hoeffding
inequality (see (17, Section E.6.2) for the details) . Alternatively, this MGF
can be upper bounded using approaches similar to (18).

##### Problem setup.

In this work, we consider a _homogeneous distributed learning_ setup that
exploits the participation of $K$ clients, as described in the following. Each
client $i\in[K]$ has access to a training dataset
$S_{i}=\\{Z_{i,1},\ldots,Z_{i,n}\\}\sim\mu^{\otimes n}$ of size $n$,

Figure 1: The considered distributed setup.

drawn independently of each other and independently of other clients’ training
datasets from the same distribution $\mu$. The local learning algorithm
$\mathcal{A}_{i}$ at each client picks a hypothesis
$\mathcal{A}_{i}(S_{i})=W_{i}\in\mathcal{W}_{i}=\mathcal{W}$ according to
$P_{W_{i}|S_{i}}$. The induced joint distribution of $(S_{i},W_{i})$ is
denoted by $P_{S_{i},W_{i}}$. The server receives the hypotheses $W_{1:K}$ and
picks the hypothesis $\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu$ as

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\coloneq(W_{1}+\cdots+W_{K})/K.$

We denote the distributed learning algorithm as $\mathcal{A}_{1:K}(S_{1:K})$.
It induces the joint distribution $P_{S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}=P_{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu|W_{1:K}}\prod\nolimits_{i\in[K]}P_{S_{i},W_{i}}$, where
$P_{S_{i}}=\mu^{\otimes n}$ and $P_{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu|W_{1:K}}=\mathbbm{1}_{\\{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu=(W_{1}+\cdots+W_{K})/K\\}}$. Similar to (40; 41), the population and
empirical risks are defined as

$\displaystyle\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)\coloneq\mathbb{E}_{Z\sim\mu}[\ell(Z,\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)],\quad\hat{\mathcal{L}}(s_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)\coloneq\frac{1}{K}\sum\nolimits_{i\in[K]}\hat{\mathcal{L}}(s_{i},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu).$ (2)

The main goal of the paper is to upper bound the generalization error
$\operatorname{gen}\left(s_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu\right)\coloneq\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)-\hat{\mathcal{L}}\left(s_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu\right)$ for the
described (one-round) distributed learning setting as well as multi-round
extension of it, i.e., Federated Learning. Results for the latter are stated
in Section 5.

##  3 Information-theoretic bounds on the generalization error

In this section, we establish information-theoretic bounds on the
generalization error of any stochastic distributed learning algorithm defined
as in the previous section. It is important to note that the bounds hold for
$\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu$ being any
stochastic function of $W_{1:K}$. For the ease of the exposition, however, we
only focus on the deterministic average case. The bounds are applied later for
the DSVM and federated SGLD, suggesting a decreasing generalization error
behavior as the number of clients increases.

###  3.1 Tail bound

A trivial approach that was already considered and used in (40) to establish
in-expectation bounds for the problem studied therein consists in thinking of
a distributed learning algorithm that is composed of $K$ local algorithms and
an aggregator at the server as a single centralized algorithm. In other words,
to consider the end-to-end system from the input at each local algorithm to
the final aggregated model $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu$ as $P_{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu|S_{1:K}}$. The idea also
applies to tail bounds. Hence, known tail and in-expectation bounds on the
generalization error of centralized learning algorithms translate trivially
into (generally loose) counter-part bounds for the distributed learning
setting. Accordingly, the next theorem follows easily using the result of the
above Theorem 1.

######  Theorem 2.

Suppose that the distributed learning algorithm $\mathcal{A}_{1:K}(S_{1:K})$
induces $P_{S_{1:K},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}$ and suppose that for all $\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu}\in\hat{\mathcal{W}}$,
$\hat{\ell}(Z,\hat{\mkern 1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}$) is $\sigma$-subgaussian. Then, for any fixed $\epsilon\in\mathbb{R}$
and $\delta\geq 0$, with probability at least $1-\delta$,
$\operatorname{gen}\left(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)\leq\sqrt{2\sigma^{2}\left(R_{p}(\delta,\epsilon)+\log(1/\delta)\right)/(nK)}+\epsilon$,
where $R_{p}(\delta,\epsilon)\coloneq\sup\limits_{Q\colon
D_{KL}(Q\|P_{S_{1:K},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu})\leq\log(1/\delta)}\mathfrak{RD}(Q,\epsilon)$ and the supremum is over
all possible distributions over
$\mathcal{W}\times\prod_{i\in[K]}\mathcal{S}_{i}$.

In the distributed setup, for every $i\in[K]$ only the hypothesis $W_{i}$
depends on the dataset $S_{i}$, which has then the effect with a factor of
$1/K$ on $\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu$. The
result of Theorem 2, however, does not explicitly take the structure of the
distributed learning problem into account and, instead, it considers the joint
compressibility of all local algorithms and $P_{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu|S_{1:K}}$. Thus, the
dependency of the bound on the structure of the problem is considered only
implicitly, via the conditional distribution $P_{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu|S_{1:K}}$. In this work,
we establish an alternate bound that is tailored specifically for the
considered distributed setup. First, for every $i\in[K]$ we let the
_compressed_ hypothesis $\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}$ of $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu$ to depend on both
$S_{i}$ and $W_{1:K\setminus i}$ (recall that $W_{1:K\setminus i}$ is
independent from $S_{i}$). We then establish an upper bound on the
generalization error in terms of the maximum (over all clients $i\in[K]$) of
the minimum achievable compressibility using $P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|S_{i},W_{1:K\setminus i}}$. The advantage can be exemplified as
follows. For $i\in[K]$, consider only compressing the local algorithm
$P_{W_{i}|S_{i}}$ and pick some $\hat{W}_{i}$ while keeping $W_{1:K\setminus
i}$ un-compressed. Let $\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}$ be average of
$\hat{W}_{i}$ and $W_{1:K\setminus i}$. As $\hat{W}_{i}$ has the effect with
factor $1/K$ on $\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}$, in order to meet the distortion constraint
$\mathbb{E}[\operatorname{gen}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)-\operatorname{gen}(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i})]\leq\epsilon$ a
more relaxed distortion criterion would be needed in compressing the local
algorithm $P_{W_{i}|S_{i}}$. More precisely, for example when the loss is
$\mathfrak{L}$-Lipschitz with $L_{2}^{2}$-norm, _i.e.,_
$\left|\ell(z,w)-\ell(z,w^{\prime})\right|\leq\mathfrak{L}\|w-w^{\prime}\|^{2}$,
a local distortion of $K^{2}\epsilon$ results into only $\epsilon$ distortion
in the aggregated model.111For non-Lipschitz losses, such as 0-1 loss, the
analysis is less trivial. An example can be found in Section D.2. Hence, this
translates into smaller rate-distortion terms and, in turn, tighter bounds on
the generalization error.

Now, to formally state the result, we introduce some definitions. Let
$\operatorname{gen}(s_{i},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)\coloneq\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)-\hat{\mathcal{L}}(s_{i},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu)$. Besides, as in the
centralized case, let $\hat{\mathcal{W}}$ be the alphabet of the compressed
hypothesis and
$\hat{\ell}\colon\mathcal{Z}\times\hat{\mathcal{W}}\mapsto\mathbb{R}^{+}$ a
loss function (possibly different from $\ell$). Accordingly, for $\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu}\in\hat{\mathcal{W}}$
and $s\in\mathcal{Z}^{n}$, let $\operatorname{gen}(s,\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu})$ and
$\operatorname{gen}(s_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu})$ be defined similarly
with respect to $\hat{\ell}$. For a distribution $Q$ defined over
$\mathcal{W}\times\prod_{i\in[K]}(\mathcal{S}_{i}\times\mathcal{W}_{i})$, let

$\displaystyle\mathfrak{RD}_{i}(Q,\epsilon)$
$\displaystyle\coloneq\inf_{P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|S_{i},W_{1:K\setminus i}}}I(S_{i};\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}|W_{1:K\setminus
i}),$ (3) $\displaystyle\quad\text{s.t.}\quad\mathbb{E}$
$\displaystyle\left[\operatorname{gen}\left(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)-\operatorname{gen}\left(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\right)\right]\leq\epsilon,$ (4)

where the infimum is taken over all Markov kernels (conditional distributions)
of a random variable $\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\in\hat{\mathcal{W}}$ given $(S_{i},W_{1:K\setminus i})$. Note that
the mutual information and expectations are with respect to
$Q_{S_{i},,W_{1:K\setminus i}}P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|S_{i},W_{1:K\setminus i}}$ and $QP_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|S_{i},W_{1:K\setminus i}}$, respectively, where
$Q_{S_{i},W_{1:K\setminus i}}$ is the $Q$-marginal of $(S_{i},W_{1:K\setminus
i})$.

######  Theorem 3.

Suppose that the distributed learning algorithm $\mathcal{A}_{1:K}(S_{1:K})$
induces $P_{S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}$ and suppose that for
all $\hat{\mkern 1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}\in\hat{\mathcal{W}}$, $\hat{\ell}(Z,\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu}$) is
$\sigma$-subgaussian. Then, for any fixed $\epsilon\in\mathbb{R}$ and
$\delta\geq 0$, with probability at least $1-\delta$,

$\displaystyle\operatorname{gen}\left(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu\right)$
$\displaystyle\leq\sqrt{2\sigma^{2}\left(\max\nolimits_{i\in[K]}R_{p}(\delta,\epsilon,i)+\log(1/\delta)\right)/n}+\epsilon,$
(5) $\displaystyle R_{p}(\delta,\epsilon,i)$
$\displaystyle\coloneq\sup\limits_{Q\colon
D_{KL}(Q\|P_{S_{1:K},W_{1:K}})\leq\log(1/\delta)}\mathfrak{RD}_{i}(Q,\epsilon),$
(6)

where the supremum is over all possible distributions over
$\prod\nolimits_{i\in[K]}(\mathcal{S}_{i}\times\mathcal{W}_{i})$.

The theorem is proved in Appendix D.1. In the binary classification setup, the
result also holds for the margin generalization error
$\operatorname{gen}_{\theta}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ by letting
$\operatorname{gen}_{\theta}\left(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)\coloneqq\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)-\hat{\mathcal{L}}_{\theta}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$.

While the advantage of this result was already stated in part above, it should
be noted that the denominator in the result of Theorem 3 is $n$, rather than
$nK$ in Theorem 2. In fact, none of the two results of Theorem 2 and Theorem 3
outperforms the other in general. For the case of distributed SVM which will
be considered in the next section, it can be shown that the result of Theorem
3 results in a bound that decays with $K$ faster than one that uses Theorem 2.
Moreover, as it will become clearer from the sequel the bounds for DSVM
require a strict lossy compression, i.e., $\epsilon\neq 0$, and do not seem to
be obtainable with a lossless compression framework, illustrating the utility
of our rate-distortion based approach in general.

######  Remark 3.

For the ease of the presentation, the results of this work, including Theorem
3, are stated for the homogeneous case where the underlying data distribution
$\mu_{i}$ is same for all clients. However, the result can be extended
straightforwardly to the heterogeneous case, by considering $S_{i}$ and
$\mathfrak{RD}_{i}(Q,\epsilon)$, $i\in[K]$, with respect to $\mu_{i}$.

###  3.2 In expectation bound

Similar to Theorems 2 and 3, we establish upper bounds on the expectation of
the generalization error of any distributed stochastic learning algorithm.

######  Theorem 4.

Suppose that the distributed learning algorithm $\mathcal{A}_{1:K}(S_{1:K})$
induces $P_{S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}$ and suppose that for
all $\hat{\mkern 1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}\in\hat{\mathcal{W}}$, $\hat{\ell}(Z,\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu}$) is
$\sigma$-subgaussian. Then, for every fixed $\epsilon\in\mathbb{R}$ we have:

$\displaystyle\mathbb{E}$
$\displaystyle\left[\operatorname{gen}\left(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu\right)\right]$
$\displaystyle\leq\frac{1}{n}\min\left\\{\frac{1}{K}\sum_{j\in[n]}\sum_{i\in[K]}\sqrt{2\sigma^{2}\mathfrak{RD}(P_{Z_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu},\epsilon)}+\epsilon,\sum_{j\in[n]}\sqrt{2\sigma^{2}\max_{i\in[K]}\mathfrak{RD}_{i}(P_{Z_{i,j},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu},\epsilon)}+\epsilon\right\\}$ (7)
$\displaystyle\leq\frac{1}{\sqrt{n}}\min\left\\{\sqrt{2\sigma^{2}\mathfrak{RD}(P_{S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu},\epsilon)/K}+\epsilon,\sqrt{2\sigma^{2}\max\limits_{i\in[K]}\mathfrak{RD}_{i}(P_{S_{i},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu},\epsilon)}+\epsilon\right\\}.$ (8)

The first terms of the minimization in (7) and (8) follow easily by an
application similar to in Theorem 2. In particular, setting $\epsilon=0$ in
the first term of the minimization in (7) one recovers the result of (40,
Thoerem 2) under the assumed subgaussianity. The second terms of the
minimization in (7) and (8) are derived in a manner that is essentially
similar to in the proof of Theorem 3. The details are omitted for brevity.

In Appendix C.2, it is shown that under the assumed subgaussianity, the upper
bounds in (41, Theorems 4 & 5) also can be recovered from Theorem 4. The
results of (41) are derived using the stability approach and by applying the
_leave-one-out expansion_ lemma.

##  4 Distributed support vector machines

In this section, we establish upper bounds on the generalization error of
_Support Vector Machines_ (SVM) (45; 46) when applied in a distributed
learning setting. The algorithm is called hereafter as Distributed SVM (DSVM).
SVMs are popular and widely used for binary classification problems. They can
be combined with different kernels in a computationally efficient way (47;
48). An easy application of SVM consists in finding a hyperplane based on a
training dataset that separates the data with the smallest possible average
margin error. Formally, let $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, where
$\mathcal{X}\in\mathbb{R}^{d}$ and $\mathcal{Y}=\\{-1,+1\\}$. The hypotheses
are vectors $w\in\mathbb{R}^{d}$, which represent hyperplanes. For the
simplicity of the exposition, we only consider the case with zero bias. The
hyperplane predicts a label of a data $x$ according to the sign of the inner
product $\langle x,w\rangle$. The 0-1 loss and margin loss functions are thus
defined as $\ell_{0}(z,w)\coloneqq\mathbbm{1}_{\left\\{y\langle
x,w\rangle<0\right\\}}$ and
$\ell_{\theta}(z,w)\coloneqq\mathbbm{1}_{\left\\{y\langle
x,w\rangle<\theta\right\\}}$, respectively. In the distributed learning setup,
each client $i\in[K]$ has access to dataset $S_{i}$ and picks the vector
$W_{i}$; and the server node computes the aggregated model as $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\coloneqq(W_{1}+\ldots+W_{K})/K$ (49). In this section, we study the
generalization gap, which we denote hereafter as
$\operatorname{gen}_{\theta}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$, defined as the
difference between the population risk $\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu)$ calculated using
$\ell_{0}$ and the margin empirical risk
$\frac{1}{K}\sum_{i\in[K]}\hat{\mathcal{L}}_{\theta}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ calculated using
$\ell_{\theta}$. It should be noted that the results of (41, Theorems 4 & 5)
require the loss function to be either a Bregman divergence or Lipschitz of
some order; and, as such, they are not applicable to the DVSM setup that we
consider here. This is because the 0-1 loss function is neither a Bregman
divergence, nor a Lipschitz loss.

######  Theorem 5.

Let $d\in\mathbb{N}^{+}$ and $\mathbb{P}(\|X\|\leq B)=1$ for some $B>0$.
Consider DSVM with $K$ clients each using _any_ arbitrary local learning
algorithm such that $\mathbb{P}(\|W_{i}\|\leq 1)=1$, $i\in[K]$.

  * i)

For any $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\operatorname{gen}_{\theta}\left(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)\leq\mathcal{O}\left(\frac{1}{nK\sqrt{K}}+\sqrt{\frac{\left(\frac{B}{K\theta}\right)^{2}\log(nK\sqrt{K})\log\left(\max\left(\frac{K\theta}{B},2\right)\right)+\log(1/\delta)}{n}}\right).$

  * ii)

Also,

$\displaystyle\mathbb{E}\left[\operatorname{gen}_{\theta}\left(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)\right]\leq\mathcal{O}\left(\frac{1}{nK\sqrt{K}}+\sqrt{\frac{B^{2}\log(nK\sqrt{K})\log\left(\max\left(\frac{K\theta}{B},2\right)\right)}{nK^{2}\theta^{2}}}\right).$

This theorem is proved in Appendix D.2, by bounding the corresponding rate-
distortion terms in Theorem 3 (for the part i.) and in the second term of (8)
(for part ii.). To establish such bounds, we show the existence of a proper
$P_{\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|S_{i},W_{1:K\setminus i}}$ using techniques and results developed
in (48), and in particular by making use of the Johnson-Lindenstrauss
transformation (50).

The above bound on the expectation of the generalization error of the DSVM
decreases with $K$ with a rate of $\log(K)/K$. Moreover, it is important to
note that the in-expectation bound for $K$ clients each having $n$ data
samples is smaller than that of the counterpart centralized learning algorithm
that has $nK$ input data samples by a factor of order
$\mathcal{O}(\sqrt{\log(K)/K})$. This also holds for the tail bound, as long
as $\log(1/\delta)/n$ is not the dominant term in the square root. Note that
in general $\sqrt{\log(1/\delta)/n}$ is very small, corresponding to the
generalization error of an dataset-independent algorithm (4).

######  Remark 4.

The tail bound in Theorem 5 for $K=1$ does not recover the best known upper
bound to the margin generalization error of SVMs. More precisely, for a
centralized setup with dataset of size $nK$, (48, Theorem 2) states

$\displaystyle\operatorname{gen}_{\theta}\left(S,W\right)\leq\mathcal{O}\left(\frac{B^{2}\log(nK)}{nK\theta^{2}}+\sqrt{\frac{\left(\frac{B}{\theta}\right)^{2}\log(nK)+\log(1/\delta)}{nK}\hat{\mathcal{L}}_{\theta}(S,W)}\right).$
(9)

This is particularly important for the separable training dataset, where
$\hat{\mathcal{L}}_{\theta}(s,w)=0$, which makes the bound of order
$\mathcal{O}\left(B^{2}\ln(nK)/(nK\theta^{2})\right)$. For the non-separable
case, this term is asymptotically lower bounded by
$\hat{\mathcal{L}}_{\theta}(W^{*})$, where $W^{*}$ is the optimal population
risk minimizer when $\mu$ is known. However, in the distributed learning
setup, even if $\hat{\mathcal{L}}_{\theta}(s_{i},w_{i})=0$,
$\hat{\mathcal{L}}_{\theta}(s_{i},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu)$ is not necessarily
zero.

######  Remark 5.

The proof of Theorem 5 shows how our generalization bounds exploit the
particular topology of the distributed learning setup. In particular, we show
that for a fixed non-zero distortion level $\epsilon$ in (4) an upper bound on
the rates in (4) scales as ${\mathcal{O}}\big{(}(\log(K)/K)^{2}\big{)}$. When
$\epsilon=0$, a case for which the rate-distortion approach reduces to the
mutual information-based approach (see the discussion right after Theorem 4),
that upper bound scales only as $\mathcal{O}(1)$. In part this explains the
benefits brought up by the rate-distortion approach upon the mutual
information-based one.

##  5 Federated stochastic gradient Langevin dynamics

In this section, we consider a _homogeneous federated learning_ setup, denoted
as FSGLD, where local learning algorithms use _stochastic gradient Langevin
dynamics_ (SGLD) method (51). For the case of the centralized learning
algorithm, (51) has proposed a new tractable upper bound on the generalization
error, that describes well the generalization behavior, by using results of
(18) and by connecting SGLD to the Gaussian channels.

We consider a multiple-round distributed learning algorithm. At beginning of
each round $t\in[T]$, the central server sends the updated hypothesis at the
end of the previous round $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{t-1}\in\mathbb{R}^{d}$
to the clients, where $\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{0}$ is a randomly initialized hypothesis. Then, each client $i\in[K]$
performs locally one iteration of SGLD, as explained later, and outputs
$W_{i,t}$. The central server upon receiving these hypotheses choices, let
$\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t}\coloneqq(W_{1,t}+\cdots+W_{K,t})/K$. The final hypothesis $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu$ is chosen as a
deterministic function of $\\{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{t}\\}_{t\in[T]}$. An
example of such choices is Polyak averaging (52), where $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu\coloneq(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{1}+\cdots+\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{T})/T$.

Now, we explain the local SGLD algorithm applied by each client (53; 54; 51).
Each client $i\in[K]$, partitions its dataset $S_{i}$ into $m$ disjoint mini-
batches $\\{S_{i,1},\ldots,S_{i,m}\\}$, each one having equal size $b$ with
elements $S_{i,j}=\\{Z_{i,j,1},\ldots,Z_{i,j,b}\\}$. Then, client $i$ at round
$t$, by receiving $\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1}$ from the central node, let $W_{i,t}$ be

$\displaystyle W_{i,t}=\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1}-\eta_{t}\nabla_{w}\hat{\ell}(S_{i,j_{t}},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1})+\sqrt{\frac{2\eta_{t}}{\beta_{t}}}V.$

Here, $\eta_{t}$ is the learning rate, $\beta_{t}$ the inverse temperature,
$V$ a $d$-dimensional random variable with distribution
$\mathcal{N}(0,\mathrm{I}_{d})$, where $\mathrm{I}_{d}$ is the $d\times d$
identity matrix, $j_{t}\in[m]$ is the mini-batch index,
$\hat{\ell}\colon\mathcal{Z}\times\mathcal{W}\mapsto\mathbb{R}^{+}$ is a
surrogate loss function, and

$\displaystyle\nabla_{w}\hat{\ell}(S_{i,j_{t}},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1})\coloneqq\frac{1}{b}\sum\nolimits_{l\in[b]}\nabla_{w}\hat{\ell}(Z_{i,j_{t},l},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{t-1}).$

In the following we use the first term of (7) with $\epsilon=0$ (which is
reduced to the upper bound in (40, Thoerem 2)), to derive a bound on the
expectation of the generalization error of FSGLD. Note that the first term of
(7) is established by viewing the whole learning algorithm as a black-box, and
hence it applies for the multiple-round federated learning setup as well, by
considering $S_{1:K}$ as the training dataset and $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu$ as the chosen
hypothesis.

######  Theorem 6.

Suppose that for each $w\in\mathcal{W}$, the loss $\ell(Z,w)$ is
$\sigma$-subgaussian. The expected generalization error of FSGLD is upper
bounded by

$\displaystyle\mathbb{E}\left[\operatorname{gen}\left(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)\right]\leq\frac{\sqrt{2b}\sigma}{2nK\sqrt{K}}\sum_{j\in[m]}\sum_{i\in[K]}\sqrt{\sum_{t\in\mathcal{T}_{i,j}}\beta_{t}\eta_{t}\text{Var}\left(\nabla_{w}\hat{\ell}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{t-1})\right)},$

where the set $\mathcal{T}_{i,j}$ contains the indices $t$ such that $j_{t}=j$
at client $i$, and

$\displaystyle\text{Var}\left(\nabla_{w}\hat{\ell}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1})\right)\coloneqq\mathbb{E}\left[\left\|\nabla_{w}\hat{\ell}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1})-e_{i}\right\|^{2}\right],$

where $e_{i}\coloneqq\mathbb{E}\left[\nabla_{w}\hat{\ell}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{t-1})\right]$.

This result for the case of $K=1$ is reduced in (51, Theorem 1) and it can be
proved for any $K\in\mathbb{N}$ along the same lines of the proof of (51,
Theorem 1). Indeed,

$\displaystyle\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t}=\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1}-\frac{\eta_{t}}{K}\left(\sum_{i\in[K]}\nabla_{w}\hat{\ell}(S_{i,j_{t}},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{t-1})\right)+\frac{1}{\sqrt{K}}\sqrt{\frac{2\eta_{t}}{\beta_{t}}}V^{\prime},$
(10)

where $V^{\prime}$ is a $d$-dimensional random variable with distribution
$\mathcal{N}(0,\mathrm{I}_{d})$. Now, proceeding similar to the proof of (51,
Theorem 1) concludes the result. The reason behind the extra factor
$1/\sqrt{K}$ in the bound is that, when $K$ independent Gaussian noises are
added, their variances are added up linearly with $K$. Thus, while in (10),
the gradient is divided by $K$, the noise term is divided by $\sqrt{K}$, which
results in an extra $\sqrt{K}$ term in the denominator of the upper bound. The
proof is omitted for brevity.

The established bound is decreasing with $K$, as far as the variance of the
gradient with training data size $nK$ is not smaller than the variance of the
gradient with training data size $n$, divided by $K$. Note that the variance
of the gradient is correlated with the _sharpness_ of the loss landscape and
becomes small as the algorithm converges (51).

##  6 Experiments

This section aims at showing, through simulations, the evolution of the
generalization error of the distributed SVM with the number $K$ of clients and
the size $n$ of each individual training dataset. We will provide also
comparison with the centralized setup, having training dataset of size $nk$,
and also with the bounds on the generalization error as predicted by our
analysis. We also provide further experiments and discussions on the
comparison of the empirical and population risks of the distributed and
centralized SVM. The details of the experiments are explained in Appendix B
and here, we discuss our experimental findings.

##### On the generalization error:

Figure 2 shows the evolution of the generalization error (with zero margin) of
the distributed setup ($K$ clients, each having $n$ data samples) as a
function of the number $K$ of used clients for two values of $n$, $n=100$
(Subfigure 2(a)) and $n=300$ (Subfigure 2(b)). Also shown for comparison, the
generalization performance of the associated centralized setup with a dataset
of $nK$ samples.

The figure also depicts the evolution of the bound of our Theorem 5 (computed
using part ii) of the theorem and with the value of the parameter $\theta$ set
to $0.2$). For the centralized learning setting, the theoretical bound is
obtained by applying the result of Theorem 5 (part ii) with the substitution
$K_{c}=1$ and $n_{c}=nK$.

(a) $n=100$

(b) $n=300$

Figure 2: The generalization error for distributed and centralized SVM

Observe that, as predicted by our theoretical analysis of Section4, the system
generalizes better in the distributed setup.

##### On the empirical and population risks:

While considering the empirical risk $\hat{\mathcal{L}}(s_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)\coloneq\frac{1}{K}\sum\nolimits_{i\in[K]}\hat{\mathcal{L}}(s_{i},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu)$ is motivated by
previous works (40; 41), it differs from the average local empirical risks
minimized at clients, _i.e.,_

$\displaystyle\tilde{\mathcal{L}}(s_{1:K},w_{1:K})\coloneq\frac{1}{K}\sum\nolimits_{i\in[K]}\hat{\mathcal{L}}(s_{i},w_{i}).$
(11)

Denote the difference of these empirical risks as

$\displaystyle\Delta\hat{\mathcal{L}}(s_{1:K},w_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)\coloneqq\hat{\mathcal{L}}(s_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)-\tilde{\mathcal{L}}(s_{1:K},w_{1:K}).$ (12)

Then, the population risk can be written as

$\displaystyle\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)=\tilde{\mathcal{L}}(s_{1:K},w_{1:K})+\operatorname{gen}(s_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu)+\Delta\hat{\mathcal{L}}(s_{1:K},w_{1:K},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu).$ (13)

The first term of the RHS of Eq. (13) can be made sufficiently small by
minimizing the local empirical loss at each client. The second term is the
generalization term considered in this paper, which is shown to decrease
faster than the corresponding centralized case. In what follows, we study the
evolution of the last term of the RHS of (13) with $K$.

Indeed, as shown in Fig 3, while the considered generalization error decreases
with $K$, the population risk of the centralized setup is smaller than the
distributed setup. Also, the latter decreases more slowly with $K$. This is
caused by the increase of term $\Delta\hat{\mathcal{L}}(S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ with $K$ (note that
this term is zero for the centralized setting). As it will become clearer from
the rest of this section, in the distributed setup the term
$\operatorname{gen}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ decreases with $K$ as
specified by our Theorem 5 and the term
$\Delta\hat{\mathcal{L}}(S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ increases with $K$
(the term
$\tilde{\mathcal{L}}(S_{1:K},W_{1:K})+\operatorname{gen}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ as defined by (11) can
be made negligible for both centralized and distributed settings if local
models are trained well enough, an assumption which will be made throughout
hereafter). For the distributed case, the net effect is a decrease of the
population risk with $K$, but which is slower than in the corresponding
centralized setup. In what follows, we will show that as $K$ becomes large, if
the clients use the same algorithm, i.e., $P_{W_{i}|S_{i}}=P_{W_{1}|S_{1}}$
for all $i\in[K]$, and they are trained well enough to minimize their
respective empirical risks $\hat{\mathcal{L}}(S_{i},W_{i})$ then the
population risk in the distributed case tends to a constant that depends only
on $n$ and the used local algorithms, but not on $K$.

(a) $n=100$

(b) $n=300$

Figure 3: The population risk and empirical risk differences for distributed
and centralized SVM

More formally, fix a training data size $n\in\mathbb{N}$ and suppose that all
clients use the same local learning algorithm
$P_{W_{i}|S_{i}}=P_{W_{1}|S_{1}}$. This empirical risks difference term is
zero for $K=1$, as $\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu=W_{1}$. By increasing $K$, $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu$ departs further from
$W_{i}$. In particular, as $K\rightarrow\infty$, $\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\rightarrow\mathbb{E}_{W_{1}}[W_{1}]$, where the expectation is with
respect to the marginal distribution $P_{W_{1}}$ (induced by
$P_{W_{1}|S_{1}}\mu^{\otimes n}$) and the convergence is almost surely due to
the strong law of large numbers. Note the for a fixed data distribution $\mu$,
the marginal distribution $P_{W_{1}}$ is a function of $n$ and local
algorithms $P_{W_{1}|S_{1}}$. Hence,

$\displaystyle\lim_{K\rightarrow\infty}\Delta\hat{\mathcal{L}}(S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\stackrel{{\scriptstyle
a.s.}}{{=}}$ $\displaystyle\mathbb{E}_{S_{1}\sim\mu^{\otimes
n}}\left[\hat{\mathcal{L}}\left(S_{1},\mathbb{E}_{W_{1}\sim
P_{W_{1}}}[W_{1}]\right)\right]-\mathbb{E}_{(S_{1},W_{1})\sim
P_{S_{1},W_{1}}}\left[\hat{\mathcal{L}}(S_{1},W_{1})\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{Z\sim\mu}\left[\ell\left(Z,\mathbb{E}_{W_{1}\sim
P_{W_{1}}}[W_{1}]\right)\right]-\mathbb{E}_{(S_{1},W_{1})\sim
P_{S_{1},W_{1}}}\left[\hat{\mathcal{L}}(S_{1},W_{1})\right]$ $\displaystyle=$
$\displaystyle\mathcal{L}\left(E_{W_{1}}[W_{1}]\right)-\mathbb{E}_{(S_{1},W_{1})\sim
P_{S_{1},W_{1}}}\left[\hat{\mathcal{L}}(S_{1},W_{1})\right].$ (14)

The above is illustrated in Fig.3, where as visible from therein the
population risk for the distributed setting (as computed experimentally)
approaches the limit given by the RHS of (14) as $K$ gets large.

##  7 Concluding remarks

In this work, we established rate-distortion theoretic tail and in-expectation
bounds on the generalization error of the distributed learning algorithms.
Unlike previous approaches to this problem, our bounds, which are more general
comparatively, are tailored specifically for the distributed setup. In
particular, when applied to distributed SVM and FSGLD our results suggest a
decreasing behavior of the generalization error with respect to the number of
clients. The conducted experiments on DSVM are in accordance with the
analytical results. Also, we partly investigated the evolution of the
population risk with the number of clients and the size of the dataset. The
analysis revealed the presence of a bias term. Possible directions for future
works include (i) further investigation of the effect of the aforementioned
bias term, (ii) study of the tightness of the proposed general bounds
(experimentally), (iii) extension of the results to the setting in which the
data distribution is not identical across the clients or when the training
data samples are not independent, (iv) multiple-round scenarios, and (v) study
of associated computational and communication costs.

## References

  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge University Press, 2014.
  * Zhang et al. [2017] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In _International Conference on Learning Representations_ , 2017.
  * Russo and Zou [2016] Daniel Russo and James Zou.  Controlling bias in adaptive data analysis using information theory.  In Arthur Gretton and Christian C. Robert, editors, _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ , volume 51 of _Proceedings of Machine Learning Research_ , pages 1232–1240, Cadiz, Spain, 09–11 May 2016. PMLR.
  * Xu and Raginsky [2017] Aolin Xu and Maxim Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Harutyunyan et al. [2021] Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan.  Information-theoretic generalization bounds for black-box learning algorithms.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Haghifam et al. [2021] Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Daniel M. Roy.  Towards a unified information-theoretic framework for generalization.  In _Thirty-Fifth Conference on Neural Information Processing Systems_ , 2021.
  * Negrea et al. [2020] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy.  Information-theoretic generalization bounds for sgld via data-dependent estimates, 2020.
  * Steinke and Zakynthinou [2020] Thomas Steinke and Lydia Zakynthinou.  Reasoning about generalization via conditional mutual information.  In Jacob Abernethy and Shivani Agarwal, editors, _Proceedings of Thirty Third Conference on Learning Theory_ , volume 125 of _Proceedings of Machine Learning Research_ , pages 3437–3452. PMLR, 09–12 Jul 2020.
  * Arora et al. [2018] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In _International Conference on Machine Learning_ , pages 254–263. PMLR, 2018.
  * Suzuki et al. [2020] Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura.  Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=ByeGzlrKwH.
  * Hsu et al. [2021] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang.  Generalization bounds via distillation.  In _International Conference on Learning Representations_ , 2021.
  * Barsbey et al. [2021] Melih Barsbey, Milad Sefidgaran, Murat A Erdogdu, Gaël Richard, and Umut Şimşekli.  Heavy tails in SGD and compressibility of overparametrized neural networks.  In _Thirty-Fifth Conference on Neural Information Processing Systems_ , 2021.
  * Kuhn et al. [2021] Lorenz Kuhn, Clare Lyle, Aidan N. Gomez, Jonas Rothfuss, and Yarin Gal.  Robustness to Pruning Predicts Generalization in Deep Neural Networks.  _arXiv:2103.06002 [cs, stat]_ , March 2021.
  * Şimşekli et al. [2020] Umut Şimşekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu.  Hausdorff dimension, heavy tails, and generalization in neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 5138–5151. Curran Associates, Inc., 2020.
  * Birdal et al. [2021] Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Şimşekli.  Intrinsic dimension, persistent homology and generalization in neural networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Hodgkinson et al. [2021] Liam Hodgkinson, Umut Şimşekli, Rajiv Khanna, and Michael W Mahoney.  Generalization properties of stochastic optimizers via trajectory analysis.  _arXiv preprint arXiv:2108.00781_ , 2021.
  * Sefidgaran et al. [2022] Milad Sefidgaran, Amin Gohari, Gaël Richard, and Umut Simsekli.  Rate-distortion theoretic generalization bounds for stochastic learning algorithms.  In _Conference on Learning Theory_ , pages 4416–4463. PMLR, 2022\.
  * Bu et al. [2020] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli.  Tightening mutual information-based bounds on generalization error.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):121–130, May 2020.  ISSN 2641-8770.
  * Verbraeken et al. [2020] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer.  A survey on distributed machine learning.  _ACM Computing Surveys (CSUR)_ , 53(2):1–33, 2020\.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Konečnỳ et al. [2016] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ , 2016.
  * Kasiviswanathan et al. [2011] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  _SIAM Journal on Computing_ , 40(3):793–826, 2011\.
  * Zhao and Zhang [2015] Peilin Zhao and Tong Zhang.  Stochastic optimization with importance sampling for regularized loss minimization.  In Francis Bach and David Blei, editors, _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 1–9, Lille, France, 07–09 Jul 2015. PMLR.
  * Alistarh et al. [2017] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic.  Qsgd: Communication-efficient sgd via gradient quantization and encoding.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Chen et al. [2018] Chia-Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakrishnan.  Adacomp: Adaptive residual gradient compression for data-parallel distributed training.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Liu and Mozafari [2022] Rui Liu and Barzan Mozafari.  Communication-efficient distributed learning for large batch optimization.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 13925–13946. PMLR, 17–23 Jul 2022.
  * Wang et al. [2022] Yujia Wang, Lu Lin, and Jinghui Chen.  Communication-efficient adaptive federated learning.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 22802–22838. PMLR, 17–23 Jul 2022.
  * Yang et al. [2018] Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays.  Applied federated learning: Improving google keyboard query suggestions.  _arXiv preprint arXiv:1812.02903_ , 2018.
  * Kairouz et al. [2019] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D’Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao.  Advances and open problems in federated learning, 2019.  URL https://arxiv.org/abs/1912.04977.
  * Li et al. [2020] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 37(3):50–60, 2020.  doi: 10.1109/MSP.2020.2975749.
  * Reddi et al. [2020] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečnỳ, Sanjiv Kumar, and H Brendan McMahan.  Adaptive federated optimization.  _arXiv preprint arXiv:2003.00295_ , 2020.
  * Karimireddy et al. [2020] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.  Scaffold: Stochastic controlled averaging for federated learning.  In _International Conference on Machine Learning_ , pages 5132–5143. PMLR, 2020.
  * Yuan et al. [2021] Honglin Yuan, Manzil Zaheer, and Sashank Reddi.  Federated composite optimization.  In _International Conference on Machine Learning_ , pages 12253–12266. PMLR, 2021.
  * Gupta and Raskar [2018] Otkrist Gupta and Ramesh Raskar.  Distributed learning of deep neural network over multiple agents.  _Journal of Network and Computer Applications_ , 116:1–8, 2018.
  * Elgabli et al. [2020] Anis Elgabli, Jihong Park, Amrit S Bedi, Mehdi Bennis, and Vaneet Aggarwal.  Gadmm: Fast and communication efficient framework for distributed machine learning.  _J. Mach. Learn. Res._ , 21(76):1–39, 2020.
  * Aguerri and Zaidi [2019] Inaki Estella Aguerri and Abdellatif Zaidi.  Distributed variational representation learning.  _IEEE transactions on pattern analysis and machine intelligence_ , 43(1):120–138, 2019.
  * Moldoveanu and Zaidi [2021] Matei Moldoveanu and Abdellatif Zaidi.  In-network learning for distributed training and inference in networks.  In _2021 IEEE Globecom Workshops (GC Wkshps)_ , pages 1–6. IEEE, 2021\.
  * Yuan et al. [2022] Honglin Yuan, Warren Richard Morningstar, Lin Ning, and Karan Singhal.  What do we mean by generalization in federated learning?  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=VimqQq-i_Q.
  * Mohri et al. [2019] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh.  Agnostic federated learning.  In _International Conference on Machine Learning_ , pages 4615–4625. PMLR, 2019.
  * Yagli et al. [2020] Semih Yagli, Alex Dytso, and H. Vincent Poor.  Information-theoretic bounds on the generalization error and privacy leakage in federated learning.  In _2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_ , pages 1–5, 2020.  doi: 10.1109/SPAWC48557.2020.9154277.
  * Barnes et al. [2022] L. P. Barnes, A. Dytso, and H. V. Poor.  Improved information theoretic generalization bounds for distributed and federated learning.  In _2022 IEEE International Symposium on Information Theory (ISIT)_ , pages 1465–1470, 2022.
  * Cover and Thomas [2006] Thomas M. Cover and Joy A. Thomas.  _Elements of information theory (2. ed.)_.  Wiley, 2006.  ISBN 978-0-471-24195-9.
  * Polyanskiy and Wu [2014] Yury Polyanskiy and Yihong Wu.  Lecture notes on information theory.  _Lecture Notes for ECE563 (UIUC) and_ , 6(2012-2016):7, 2014.
  * Berger [1975] Toby Berger.  _Rate Distortion Theory and Data Compression", bookTitle="Advances in Source Coding_ , pages 1–39.  Springer Vienna, Vienna, 1975.
  * Vapnik [2006] Vladimir Vapnik.  _Estimation of dependences based on empirical data_.  Springer Science & Business Media, 2006.
  * Cortes and Vapnik [1995] Corinna Cortes and Vladimir Vapnik.  Support-vector networks.  _Machine learning_ , 20(3):273–297, 1995.
  * Boser et al. [1992] Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik.  A training algorithm for optimal margin classifiers.  In _Proceedings of the fifth annual workshop on Computational learning theory_ , pages 144–152, 1992.
  * Grønlund et al. [2020] Allan Grønlund, Lior Kamma, and Kasper Green Larsen.  Near-tight margin-based generalization bounds for support vector machines.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 3779–3788. PMLR, 13–18 Jul 2020.
  * Carlsson [2020] Robert Carlsson.  Privacy-preserved federated learning: A survey of applicable machine learning algorithms in a federated environment, 2020.
  * Johnson and Lindenstrauss [1984] William B Johnson and Joram Lindenstrauss.  Extensions of lipschitz mappings into a hilbert space 26.  _Contemporary mathematics_ , 26:28, 1984.
  * Wang et al. [2021] Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon.  Analyzing the generalization capability of sgld using properties of gaussian channels.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 24222–24234. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/cb77649f5d53798edfa0ff40dae46322-Paper.pdf.
  * Polyak and Juditsky [1992] Boris T Polyak and Anatoli B Juditsky.  Acceleration of stochastic approximation by averaging.  _SIAM journal on control and optimization_ , 30(4):838–855, 1992.
  * Gelfand and Mitter [1991] Saul B Gelfand and Sanjoy K Mitter.  Recursive stochastic algorithms for global optimization in r^d.  _SIAM Journal on Control and Optimization_ , 29(5):999–1018, 1991.
  * Welling and Teh [2011] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 681–688. Citeseer, 2011.
  * Csiszàr and Körner [2011] Imre Csiszàr and Jànos Körner.  _Information Theory: Coding Theorems for Discrete Memoryless Systems_.  Cambridge University Press, 2 edition, 2011.
  * Blahut [1972] Richard Blahut.  Computation of channel capacity and rate-distortion functions.  _IEEE transactions on Information Theory_ , 18(4):460–473, 1972.
  * Arimoto [1972] Suguru Arimoto.  An algorithm for computing the capacity of arbitrary discrete memoryless channels.  _IEEE Transactions on Information Theory_ , 18(1):14–20, 1972.
  * El Gamal and Kim [2011] Abbas El Gamal and Young-Han Kim.  _Network Information Theory_.  Cambridge University Press, 2011.
  * Riegler et al. [2018] Erwin Riegler, Helmut Bölcskei, and Günther Koliander.  Rate-distortion theory for general sets and measures.  In _2018 IEEE International Symposium on Information Theory (ISIT)_ , pages 101–105. IEEE, 2018.
  * Marton [1974] Katalin Marton.  Error exponent for source coding with a fidelity criterion.  _IEEE Transactions on Information Theory_ , 20(2):197–199, 1974.
  * Han [2000] Te Sun Han.  The reliability functions of the general source with fixed-length coding.  _IEEE Transactions on Information Theory_ , 46(6):2117–2132, 2000.
  * Iriyama [2005] Kiminori Iriyama.  Probability of error for the fixed-length lossy coding of general sources.  _IEEE Transactions on Information Theory_ , 51(4):1498–1507, 2005.
  * Bakshi and Bansal [2005] Mayank Bakshi and Rakesh K. Bansal.  On error exponent in lossy source coding, 2005.
  * LeCun et al. [2010] Yann LeCun, Corinna Cortes, and CJ Burges.  Mnist handwritten digit database. at&t labs, 2010.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.

Rate-Distortion Theoretic Bounds on
Generalization Error for Distributed Learning

Appendices

The appendices are organized as follows:

  * •

In Appendix A, we briefly recall the main concepts and definitions of the
rate-distortion theory.

  * •

In Appendix B, we provide the details of the considered simulation setups in
our experiments.

  * •

In Appendix C, we present the theoretical results that are not stated in the
main document due to lack of space. The results are on

    * –

the generalization error of deterministic algorithms with Lipschitz loss,

    * –

the comparison of Theorem 4 with results of [Barnes et al., 2022].

  * •

Finally, the proofs of the results are given in Appendix D.

##  Appendix A Background on rate-distortion theory

In this section, we recall the concepts and definitions related to the rate-
distortion theory. We first present a brief review of classic lossy source
coding [Berger, 1975, Csiszàr and Körner, 2011, Polyanskiy and Wu, 2014]. This
will help understand better the adaptation of the concepts to the related
topic of study of algorithm compressibility [Sefidgaran et al., 2022].

###  A.1 Lossy source compression

We start by describing the notion of _lossy compression_ of a source
$X\in\mathcal{X}$ in the information-theoretic context [Berger, 1975, Csiszàr
and Körner, 2011, Polyanskiy and Wu, 2014]. The goal is to compress (or to
quantize) the source $X\in\mathcal{X}$ as $\hat{X}\in\hat{\mathcal{X}}$ such
that i) $\hat{X}$ requires a smaller number of bits to be saved, and ii) from
$\hat{X}$, $X$ (or a desired function of $X$) can be recovered within a
certain allowed level of _distortion_.

To this end, we first fix a proper compressed alphabet $\hat{\mathcal{X}}$ and
consider a suitable distortion function
$d\colon\mathcal{X}\times\hat{\mathcal{X}}\to\mathbb{R}^{+}$, that measures
discrepancies between the symbol $x$ (or a desired function of it) and a
reconstructed version of it. It is assumed that there exists a
$\hat{x}_{0}\in\hat{X}$ such that for every
$\mathbb{E}[d(X,\hat{x}_{0})]<\infty$ [Berger, 1975]. Often the set
$\hat{\mathcal{X}}$ can be chosen to be a subset of $\mathcal{X}$, but it
needs not to be in general.

Next, we explain the compression scheme. A key idea is to encode and
reconstruct block-wise, i.e, the so-called _block-coding_ technique. Let
$X^{m}=(X_{1},\ldots,X_{m})\in\mathcal{X}^{m}$ be a block of $m$ i.i.d.
realizations of the source $X\sim P_{X}$. The _block-coding_ technique
considers the joint compression of any realizations of $x^{m}$ as a
$\hat{x}^{m}=(\hat{x}_{1},\ldots,\hat{x}_{m})\in\hat{\mathcal{X}}^{m}$. The
distortion between two vectors $x^{m}$ and $\hat{x}^{m}$ is given by the
average of the coordinate-wise distortions,

$\displaystyle
d(x^{m},\hat{x}^{m})\coloneqq\frac{1}{m}\sum_{i\in[m]}d(x_{i},\hat{x}_{i}).$
(15)

Now, we define the $(R,\epsilon)$-compressibility of a source $X\sim P_{X}$
with respect to the distortion function $d$, where $R$ is the compression rate
and $\epsilon$ is the maximum allowed distortion value. The source $X$ is said
to be $(R,\epsilon)$-compressible if there exists a sequences of _codebooks_
$\left\\{\mathcal{C}_{m}\right\\}_{m\in\mathbb{N}}$,
$\mathcal{C}_{m}=\left\\{\hat{\mathbf{x}}_{j;m}=(\hat{x}_{j,1},\ldots,\hat{x}_{j,m}),j\in[l_{m}]\right\\}\subseteq\hat{\mathcal{X}}^{m}$,
such that $l_{m}\leq e^{mR}$ and

$\displaystyle\lim_{m\to\infty}\mathbb{P}\left(\min_{j\in[l_{m}]}d(X^{m},\hat{\mathbf{x}}_{j;m})>\epsilon\right)=\lim_{m\to\infty}\mathbb{P}\left(\forall
j\in[l_{m}]\colon d(X^{m},\hat{\mathbf{x}}_{j;m})>\epsilon\right)=0,$ (16)

where $X^{m}\sim{P_{X}}^{\otimes m}$. The $(R,\epsilon)$-compressibility
implies that for $m$ sufficiently large one can find a codebook
$\mathcal{C}_{m}$ such that (i) every element of $\mathcal{C}_{m}$ can be
represented using $mR\log_{2}(e)$ bits and (ii) with high probability, for
every $X^{m}$ there exists at least one element of $\mathcal{C}_{m}$ for which
the distortion from $X^{m}$ does not exceed $\epsilon$. For example
$\epsilon$-net covering can be seen as a special case of the above
compressibility definition with $\mathcal{C}_{m}$ being the $m$-times
Cartesian product of some $\epsilon$-net covering of $\mathcal{X}$. However,
in $\epsilon$-net covering the more stringent condition
$\mathbb{P}\left(\min_{j\in[l_{1}]}d(X,\hat{\mathbf{x}}_{j;1})>\epsilon\right)=0$
is required. This condition yields
$\mathbb{P}\left(\min_{j\in[l_{m}]}d(X^{m},\hat{\mathbf{x}}_{j;m})>\epsilon\right)=0$
for every $m\in\mathbb{N}$, which is a stronger condition than (20). This
explains why the $\epsilon$-net covering number is an upper bound on the
minimum achievable rate $R$.

It turns out [Berger, 1975, Cover and Thomas, 2006, Polyanskiy and Wu, 2014]
that given a distortion threshold $\epsilon$, the fundamental lossy
compression rate $R$ of the source $X\sim P_{X}$ is determined by the rate-
distortion function $\mathfrak{RD}(P_{X},\epsilon)$, defined as

$\displaystyle\mathfrak{RD}(P_{X},\epsilon)\coloneq\inf\limits_{P_{\hat{X}|X}}I(X;\hat{X}),\quad\text{s.t.}\quad\mathbb{E}_{(X,\hat{X})\sim
P_{X}P_{\hat{X}|X}}[d(X,\hat{X})]\leq\epsilon,$ (17)

where the infimum is taken over all possible Markov kernels (conditional
distributions) of a random variable $\hat{X}\in\hat{\mathcal{X}}$ given $X$.

For certain source distributions, closed-form expression of the associated
rate-distortion function can be found explicitly [Berger, 1975, Cover and
Thomas, 2006, Polyanskiy and Wu, 2014]. For example, for a $d$-dimensional
i.i.d. Gaussian vector $X\sim\mathcal{N}(0,\sigma^{2}\mathrm{I}_{d})$, the
rate-distortion function with respect to the squared two-norm $L_{2}^{2}$ is
given by $\frac{d}{2}\log(\max(\sigma^{2}/\epsilon,1))$. Besides, for sources
of finite cardinality alphabets $\mathcal{X}$, the rate-distortion function
can be computed efficiently using the Blahut-Arimoto algorithm [Blahut, 1972,
Arimoto, 1972]. For continuous sources or sources with infinite-sized
alphabets, the rate-distortion function can be estimated by first applying a
suitable (fine) quantization technique [El Gamal and Kim, 2011, Proof of
Theorem 3.6] and then using the Blahut-Arimoto algorithm. For small distortion
levels $\epsilon$, optimal rate-distortion tradeoffs can be estimated using
appropriate (variational) lower-bounds _e.g.,_[Riegler et al., 2018]. Finally,
we mention that for sources with finite-sized sets an easy upper bound on the
rate-distortion function is given by $\log(|\mathcal{X}|)$; whereas for
sources whose support set $\mathcal{X}\subset\mathbb{R}^{d}$ is inside a
$d$-dimensional ball of radius $R$ the function
$\mathfrak{RD}(P_{X},\epsilon)$ with respect to the $L_{2}$ norm is upper
bounded by the $\epsilon$-net covering number of this $d$-dimensional ball.

The rate-distortion formulation in (17) is asymptotic with respect to the
block length $m$; _i.e.,_ as formulated in (20), the probability that there
does not exist a proper $\hat{\mathbf{x}}_{j;m}$ within $\epsilon$ distortion
of $X^{m}$ goes to zero, as $m\to\infty$. This formulation does not require
any condition on the rate of this convergence to zero. Marton [Marton, 1974]
showed that for the finite sets $\mathcal{X}$, to have this probability go
exponentially fast to zero (for large values of $m$), _i.e.,_ at least as fast
as $\delta^{m}$ for some $0<\delta<1$, the needed rate $R$ needs to be at
least as large as $\sup_{Q}\mathfrak{RD}(Q,\epsilon)$, where the supremum is
over all distribution $Q$ defined over $\mathcal{X}$ such that
$D_{KL}(Q\|P_{X})\leq\log(1/\delta)$. As it can be observed, the minimum
needed rate depends not only on the rate-distortion term with respect to the
underlying distribution $P_{X}$ but also with respect to all those
distributions $Q$ that are close to $P_{X}$ in some sense. The result has been
extended to countably infinite and continuous sets in [Han, 2000, Iriyama,
2005, Bakshi and Bansal, 2005].

###  A.2 Lossy algorithm compression

Now, we are ready to present an adaptation of the rate-distortion concept to
the related setting of the study of the compressibility of statistical
learning algorithms which was developed and used for the first time in
[Sefidgaran et al., 2022, Section 3.1]. Such adaptation is also used
extensively in our present work; and, hence, hereafter we provide a short
review for the sake of completeness.

Consider a learning algorithm $\mathcal{A}$ which, for a training data set
$S=\\{Z_{1},\ldots,Z_{n}\\}\in\mathcal{S}=\mathcal{Z}^{n}$ picks a hypothesis
$W\in\mathcal{W}$ according to $P_{W|S}$. Similar to the source coding
context, consider the set $\hat{\mathcal{W}}$ of _compressed hypotheses_ and
the following distortion measure between any $w$ and $\hat{w}$222Observe that
in contrast with classic source coding contexts the distortion measure here
depends not only on the true value of the hypothesis and its estimated fit but
also on the given training data set, its distribution and size $n$ as well as
the considered loss function. Also, the values of the incurred distortion are
allowed to take negative values.

$\displaystyle
d(w,\hat{w};s)\coloneqq\operatorname{gen}(s,w)-\operatorname{gen}(s,\hat{w}).$

In this work, we consider a slightly extended version of the compressibility
framework of [Sefidgaran et al., 2022] by allowing the compressed hypothesis
space to be assessed with respect to a potentially different loss function
$\ell^{\prime}\colon\mathcal{Z}\times\hat{\mathcal{W}}\to\mathbb{R}^{+}$. The
generalization error $\operatorname{gen}(s,\hat{w})$ is then defined with
respect to this loss function. However, all results of [Sefidgaran et al.,
2022] hold trivially for this extended framework as well.

Next, we present an adaptation of the described block coding technique to the
study of the generalization power of statistical learning algorithms. Let
$S^{m}=(S_{1},\ldots,S_{m})$ be a block of i.i.d. training datasets
$S_{i}=\\{Z_{i,1},\ldots,Z_{i,n}\\}\sim\mu^{\otimes n}$, and
$W^{m}=(W_{1},\ldots,W_{m})$ be the block of corresponding chosen hypothesis,
_i.e.,_ $\mathcal{A}(S_{i})=W_{i}$, $i\in[m]$. Similarly, denote the block of
length $m$ of compressed hypothesis $(\hat{w}_{1},\ldots,\hat{w}_{m})$ by
$\hat{w}^{m}$. While in [Sefidgaran et al., 2022], different distortion
functions between $w^{m}$ and $\hat{w}^{m}$ given $s^{m}$ are considered, in
this work we only consider the following distortion function:

$\displaystyle
d(w^{m},\hat{w}^{m};s^{m})\coloneqq\frac{1}{m}\sum_{j\in[m]}d(w_{j},\hat{w}_{j};s_{j}).$
(18)

As in the source coding context, we consider the joint _lossy compression_ of
$(S^{m},W^{m})$ as follows. Fix a _hypothesis book_
$\mathcal{H}_{m}\coloneqq\\{\mathbf{\hat{w}}_{j;m}=(\hat{w}_{j,1},\ldots,\hat{w}_{j,m}),j\in[l_{m}]\\}\subseteq\hat{\mathcal{W}}^{m}$.
For this chosen hypothesis book, the optimal compression scheme
$\hat{\mathcal{A}}^{*}_{m}\colon\mathcal{S}^{m}\times\mathcal{W}^{m}\to\mathcal{H}_{m}$
assigns for every $(s^{m},w^{m})$ the compressed hypothesis vector
$\mathbf{\hat{w}}_{j;m}$, $j\in[l_{m}]$ that has the smallest distortion,
_i.e.,_

$\displaystyle\hat{\mathcal{A}}^{*}_{m}(s^{m},w^{m})=\mathbf{\hat{w}}_{j;m}\quad\text{s.t.}\quad
j=\operatorname{argmin}\limits_{j\in[l_{m}]}d(w^{m},\mathbf{\hat{w}}_{j;m};s^{m}).$

Now, we recall the definition of the algorithm compressibility as given in
[Sefidgaran et al., 2022, Definitions 1 and 8]. The learning algorithm
$\mathcal{A}$ is $(R,\epsilon)$-compressible for some $R\in\mathbb{R}^{+}$ and
$\epsilon\in\mathbb{R}$ if there exists sequences of hypothesis books
$\left\\{\mathcal{H}_{m}\right\\}_{m\in\mathbb{N}}$,
$\mathcal{H}_{m}=\left\\{\hat{\mathbf{w}}_{j;m}=(\hat{w}_{j,1},\ldots,\hat{w}_{j,m}),j\in[l_{m}]\right\\}\subseteq\hat{\mathcal{W}}^{m}$,
such that $l_{m}\leq e^{mR}$ and

$\displaystyle\lim_{m\to\infty}\mathbb{P}\left(\min_{j\in[l_{m}]}d(W^{m},\hat{\mathbf{w}}_{j;m};S^{m})>\epsilon\right)=\lim_{m\to\infty}\mathbb{P}\left(\forall
j\in[l_{m}]\colon d(W^{m},\hat{\mathbf{w}}_{j;m};S^{m})>\epsilon\right)=0,$
(19)

where $(S^{m},W^{m})\sim{P_{S,W}}^{\otimes m}$. Furthermore, for $0<\delta<1$
$\mathcal{A}$ is $(R,\epsilon,\delta)$-exponentially compressible if in
addition to (20) the above conditions, we have

$\displaystyle\lim_{m\to\infty}\left[-\frac{1}{m}\log\left(\mathbb{P}\left(\min_{j\in[l_{m}]}d(W^{m},\hat{\mathbf{w}}_{j;m};S^{m})>\epsilon\right)\right)\right]\geq\log(1/\delta).$
(20)

In [Sefidgaran et al., 2022, Theorems 2 and 9] it is shown that the
generalization error of $\mathcal{A}$ can be upper bounded in terms of the
compressibility parameters of $\mathcal{A}$. Furthermore, in [Sefidgaran et
al., 2022, Theorems 3, 4, and 10] it is shown that the compressibility of the
algorithm, and consequently its generalization error, can be upper bounded in
terms of an adaptation of the rate-distortion function for the learning
algorithm, as stated in (1). Here, we re-state this: for every distribution
$Q$ defined over $\mathcal{S}\times\mathcal{W}$ and every distortion threshold
$\epsilon\in\mathbb{R}$, the rate-distortion function for $\mathcal{A}$ is
defined as

$\displaystyle\mathfrak{RD}(Q,\epsilon)$
$\displaystyle\coloneq\inf\limits_{P_{\hat{W}|S}}I(S;\hat{W}),$ (21)
$\displaystyle\text{s.t.}\quad\mathbb{E}_{(S,W)\sim
Q}[\operatorname{gen}\left(S,W\right)]-$
$\displaystyle\mathbb{E}_{(S,\hat{W})\sim
Q_{S}P_{\hat{W}|S}}[\operatorname{gen}(S,\hat{W})]\leq\epsilon.$ (22)

Here, $Q_{S}$ is the $Q$-marginal of $S$, and the infimum is taken over all
Markov kernels (conditional distributions) of a random variable
$\hat{W}\in\hat{\mathcal{W}}$ given $S$. Note that
$\operatorname{gen}(S,\hat{W})$ is defined with respect to the loss function
$\hat{\ell}(z,\hat{w})$.

Every conditional distribution $P_{\hat{W}|S}$ corresponds to a compressed
learning algorithm that picks a compressed hypothesis
$\hat{W}\in\hat{\mathcal{W}}$ for $S$ according to $P_{\hat{W}|S}$. While this
compressed learning algorithm does not depend directly on $W$, it needs to
satisfy the distortion criterion (22) which clearly depends on $W$.

Finally, suppose that the loss function is Lipschitz, _i.e.,_ there exist some
constant $\mathfrak{L}\in\mathbb{R}^{+}$ and distortion function
$\rho\colon\mathcal{W}\times\hat{\mathcal{W}}\to\mathbb{R}^{+}$ such that for
every $z\in\mathcal{Z}$, $w\in\mathcal{W}$ and $\hat{w}\in\hat{\mathcal{W}}$,
it holds that
$|\ell(z,w)-\hat{\ell}(z,\hat{w})|\leq\mathfrak{L}\rho(w,\hat{w})$. Under this
Lipschitz assumption, in [Sefidgaran et al., 2022, Corollaries 6 and 11] it is
shown that the rate-distortion function (21) can be upper bounded in terms of
the classic rate-distortion function
$\mathfrak{RD}(Q_{W},2\epsilon/\mathfrak{L})$ of $W$ with respect to the
distortion function $\rho$. Here, $Q_{W}$ is the $Q$-marginal of $W$.

##  Appendix B Details of the experiments

In this section, we describe the details of the performed simulations.

###  B.1 Tasks description

In our experiments, we simulate a distributed learning setup on a single
machine, where each “client” is an instance of the SVM model, equipped with a
dataset and a model to train. We iteratively train each client’s model. All
tasks are performed on the same machine and we do not consider any
communication constraint as it is not of interest in this paper. Once all
clients’ models are trained, their weights are averaged and used by another
instance of the SVM model (meant to be the one at the central server). This is
utilized for computing $\hat{\mathcal{L}}_{\theta}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ and
$\mathcal{L}(\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$.
In particular, $\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)$ is estimated using a
test set of fixed size.

For comparison, we also consider the associated centralized learning setup
consisting of a single SVM model that needs to be trained on a dataset $S$ of
size $N=nK$. For the distributed learning setting, the (local) dataset of
client # $i\in[K]$, denoted as $S_{i}$, is composed of $n$ samples that are
drawn uniformly at random from $S$.

Each experiment is repeated $10$ times and only average values are reported.

###  B.2 Datasets

We consider a supervised learning setup, where the task is binary image
classification. More precisely, in our experiment, we train the SVM model to
distinguish digits $1$ and $6$ from the standard MNIST [LeCun et al., 2010].
Similar results, that are not reported here, were obtained for distinguishing
other pairs of digits.

###  B.3 Model

Every client uses SVM with the Gaussian kernel and applies Stochastic Gradient
Descent (SGD) for the optimization.

###  B.4 Training and hyperparameters

All models were trained with the same hyperparameters for up to 200 epochs
until the empirical risk is made smaller than $0.001$. The data is scaled and
normalized to get zero-mean and unit variance. The used training
hyperparameters are listed in Table 1 Note that we chose an adaptive learning
rate, starting from $\eta_{0}$, which is then decreased by $0.2$ if the
training loss does not increase by more than $0.01$ during $10$ epochs.

Hyperparameter | Symbol | Value
---|---|---
Initial learning rate | $\eta_{0}$ | $0.01$
Regularization parameter | $\alpha$ | $0.00001$
Batch size | $b$ | $1$
Kernel parameter | $\gamma$ | $0.01$
Dimension of the kernel feature space | $p$ | $2000$
Table 1: Hyperparameters

###  B.5 Hardware and other resources

We performed our experiments on a server equipped with 56 CPUs Intel Xeon
E5-2690v4 2.60GHz.

The experiments are conducted using Python language. The open source machine
learning library scikit-learn [Pedregosa et al., 2011] is used to implement
SVM. In particular, we use _SGDClassifier_ to implement SGD optimization and
_RBFSampler_ for Gaussian kernel feature map approximation. The code used for
the experiments is available at
https://github.com/RomainChor/DataScience/tree/master/Generalization_NeurIPS2022.

##  Appendix C Other results

Here, we present further analytical results on the generalization error of
distributed learning setups.

###  C.1 Lipschitz loss

Here, we provide an upper bound on the expectation of the generalization error
of a distributed learning algorithm with deterministic local learning
algorithms. This upper bound, proved in Section D.3, has a decreasing behavior
in comparison to the corresponding centralized algorithm.

######  Proposition 1.

Suppose the local learning algorithms
$\mathcal{A}_{i}(S_{i})=W_{i}\in\mathbb{R}^{d}$, $i\in[K]$, are deterministic
with bounded hypothesis variance $\sigma_{W}^{2}$. Moreover, suppose that for
every $w\in\mathcal{W}$, the loss $\ell(Z,w)$ is $\sigma$-subgaussian and
further $\ell(z,w)$ is $\mathfrak{L}$-Lipschitz, _i.e.,_
$\left|\ell(z,w)-\ell(z,w^{\prime})\right|\leq\mathfrak{L}\|w-w^{\prime}\|^{2}$.
Then,

$\displaystyle\mathbb{E}\left[\operatorname{gen}(S_{1:K},\bar{W})\right]\leq\min\left(2\sqrt[3]{\frac{2\mathfrak{L}\sigma^{2}\sigma_{W}^{2}}{nK^{2}}},\frac{2\mathfrak{L}\sigma_{W}^{2}}{K^{2}}\right).$

###  C.2 Comparison with related prior art results

Here, we show that some of the existing results are particular cases of our
established bounds.

####  C.2.1 Comparison with [Yagli et al., 2020]

As we already mentioned in Section 3.2, under the assumed subgaussianity
condition of the loss function our result of Theorem 4 recovers the upper
bound of [Yagli et al., 2020, Theorem 2]. More precisely, this is obtained by
setting $\epsilon=0$ in the first term of the minimization in (7).

####  C.2.2 Comparison with [Barnes et al., 2022]

Hereafter we show that under the assumed subgaussianity condition of the loss
function the upper bounds of [Barnes et al., 2022, Theorems 4 & 5] can be
recovered as special cases, and are subsumed by our Theorem 4. Specifically,
the below is obtained by investigating, and comparing with, the second term of
the minimization in (8).

  * i)

[Barnes et al., 2022, Theorem 4]: First, we recall the result. We only focus
on the upper bound in [Barnes et al., 2022, Theorem 4, part ii.] – a similar
analysis follows for the part i of their theorem.

Let for $\mathcal{Z},\mathcal{W}\in\mathbb{R}^{d}$ the loss function
$\ell(Z,w)$ be $\sigma$-subgaussian for every $w\in\mathcal{W}$. Also, similar
to in [Barnes et al., 2022], assume that the loss $\ell(z,w)$ is a Bregman
divergence, _i.e.,_

$\displaystyle\ell(z,w)\coloneqq F(w)-F(z)-\langle\nabla F(z),w-z\rangle,$

for some convex function $F\colon\mathbb{R}^{d}\mapsto\mathbb{R}$. Then, as
per [Barnes et al., 2022], we have

$\displaystyle\mathbb{E}\left[\operatorname{gen}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)\right]\leq\frac{1}{K}\sqrt{\frac{2\sigma^{2}\max_{i\in[K]}I(S_{i};W_{i})}{n}}.$

Hereafter we show that this result can be obtained as a specific case of our
Theorem 4. Specifically, let $\epsilon\coloneqq\max_{i\in[K]}\epsilon_{i}$,
where

$\displaystyle\epsilon_{i}\coloneqq\frac{1}{K}\sqrt{\frac{2\sigma^{2}I(S_{i};W_{i})}{n}},\quad
i\in[K].$

Also, let $\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}$ be a constant. Thus,
$\mathbb{E}[\operatorname{gen}(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i})]=0$ and
$I(S_{i};\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{i}|W_{1:K\setminus i})=0$. We have,

$\displaystyle\mathbb{E}\Big{[}\operatorname{gen}$ $\displaystyle(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)-\operatorname{gen}(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i})\Big{]}$
$\displaystyle=$ $\displaystyle\mathbb{E}_{(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\sim P_{S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}}\left[\operatorname{gen}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\right]$
$\displaystyle=$ $\displaystyle\mathbb{E}_{(S_{i},\tilde{S}_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\sim P_{S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}P_{\tilde{S}_{i}}}\left[\hat{\mathcal{L}}(\tilde{S}_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)-\hat{\mathcal{L}}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{j\in[n]}\mathbb{E}_{(Z_{i,j},\tilde{Z}_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\sim P_{Z_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}P_{\tilde{Z}_{i,j}}}\left[\ell(\tilde{Z}_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)-\ell(Z_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\frac{1}{n}\sum_{j\in[n]}\mathbb{E}_{(Z_{i,j},\tilde{Z}_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\sim P_{Z_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}P_{\tilde{Z}_{i,j}}}\left[\langle\nabla F(Z_{i,j}),\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu-
Z_{i,j}\rangle-\langle\nabla F(\tilde{Z}_{i,j}),\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu-\tilde{Z}_{i,j}\rangle\right]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$
$\displaystyle\frac{1}{n}\sum_{j\in[n]}\mathbb{E}_{(Z_{i,j},\tilde{Z}_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\sim P_{Z_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}P_{\tilde{Z}_{i,j}}}\left[\langle\nabla
F(Z_{i,j}),\frac{W_{i}}{K}-Z_{i,j}\rangle-\langle\nabla
F(\tilde{Z}_{i,j}),\frac{W_{i}}{K}-\tilde{Z}_{i,j}\rangle\right]$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}$
$\displaystyle\frac{1}{n}\sum_{j\in[n]}\mathbb{E}_{(Z_{i,j},\tilde{Z}_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\sim P_{Z_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}P_{\tilde{Z}_{i,j}}}\left[\langle\nabla
F(Z_{i,j}),\frac{W_{i}}{K}\rangle-\langle\nabla
F(\tilde{Z}_{i,j}),\frac{W_{i}}{K}\rangle\right]$ $\displaystyle=$
$\displaystyle\frac{1}{nK}\sum_{j\in[n]}\mathbb{E}_{(Z_{i,j},\tilde{Z}_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\sim P_{Z_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}P_{\tilde{Z}_{i,j}}}\left[\langle\nabla
F(Z_{i,j}),W_{i}\rangle-\langle\nabla F(\tilde{Z}_{i,j}),W_{i}\rangle\right]$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}$
$\displaystyle\frac{1}{K}\mathbb{E}\left[\operatorname{gen}(S_{i},W_{i})\right]$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}$
$\displaystyle\frac{1}{K}\sqrt{\frac{2\sigma^{2}I(S_{i};W_{i})}{n}}$
$\displaystyle=$ $\displaystyle\epsilon_{i},$

where $\tilde{S}_{i}\coloneqq\\{\tilde{Z}_{i,1},\ldots,\tilde{Z}_{i,n}\\}$ and
$P_{\tilde{S}_{i}}=\mu^{\otimes n}$ which is identical to $P_{S_{i}}$, $(a)$
holds since the loss is a Bregman loss and by using that
$\mathbb{E}[F(Z_{i,j})]=\mathbb{E}[F(Z^{\prime}_{i,j})]$, $i\in[K],j\in[n]$,
$(b)$ holds since $\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu=(W_{1}+\cdots+W_{K})/K$ and $Z_{i,j}$ is independent of $W_{1:K\setminus
i}$, and hence distributions of $(Z_{i},W_{1:K\setminus i})$ and
$(\tilde{Z}_{i},W_{1:K\setminus i})$ are identical, $(c)$ holds since the
marginal distributions of $Z_{i,j}$ and $\tilde{Z}_{i,j}$ are identical, $(d)$
follows by straightforward algebra using the fact that the loss is a Bregman
loss, and finally $(e)$ is due to [Xu and Raginsky, 2017, Theorem 1].

Moreover,

$\displaystyle\mathfrak{RD}_{i}(P_{S_{i},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu},\epsilon)$
$\displaystyle\leq I(S_{i};\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{i}|W_{1:K\setminus
i})=0.$

Now, using the second term of the minimization in (8) completes the proof.

  * ii)

[Barnes et al., 2022, Theorem 5]: First, we recall the result. Suppose that
$\mathcal{Z},\mathcal{W}\in\mathbb{R}^{d}$, for every $w\in\mathcal{W}$, the
loss function $\ell(Z,w)$ is $\sigma$-subgaussian, and the loss is a Lipschitz
continuous function of $w$ with respect to $L_{2}$-norm, _i.e.,_

$\displaystyle\big{|}\ell(z,w)-\ell(z,w^{\prime})\big{|}\leq
c\|w-w^{\prime}\|,\quad\forall z\in\mathcal{Z},w,w^{\prime}\in\mathcal{W},$

for some constant $c>0$. Moreover, suppose that for every $i\in[K]$,

$\displaystyle\mathbb{E}\left[\|W_{i}-\mathbb{E}[W_{i}]\|\right]\leq\sigma_{W},$

where the expectations are with respect to the marginals $P_{W_{i}}$. Then, as
per [Barnes et al., 2022] we have

$\displaystyle\mathbb{E}\left[\operatorname{gen}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)\right]\leq\frac{2c\sigma_{W}}{K}.$ (23)

We show that this result too can be obtained as a special case of the bound of
our Theorem 4. Specifically, for every $i\in[K]$ let

$\displaystyle\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\coloneqq\frac{\mathbb{E}[W_{i}]+\sum_{j\neq i}W_{j}}{K}.$

Hence $I(S_{i};\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{i}|W_{1:K\setminus i})=0$. This, we have

$\displaystyle\mathbb{E}\Big{[}\operatorname{gen}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)-\operatorname{gen}(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})\Big{]}\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
2c\mathbb{E}\left[\|\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu-\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\|\right]$ $\displaystyle=$
$\displaystyle\frac{2c}{K}\mathbb{E}\left[\|W_{i}-E[W_{i}]\|\right]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\frac{2c\sigma_{W}}{K}\eqqcolon\epsilon,$

where $(a)$ holds by the assumed Lipschitzness of the loss function and $(b)$
follows by using (23).

Moreover,

$\displaystyle\mathfrak{RD}_{i}(P_{S_{i},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu},\epsilon)$
$\displaystyle\leq I(S_{i};\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{i}|W_{1:K\setminus
i})=0.$

Finally, using the second term of the minimization in (8) completes the proof.

##  Appendix D Proofs

Here, we state the proofs of the results in the main text and the appendices.

###  D.1 Proof of Theorem 3

###### Proof.

Similar to [Sefidgaran et al., 2022, Theorem 9], we use a technique, known as
_block-coding_ in information theory. Consider $m\in\mathbb{N}$ independent
realizations of the datasets and also hypotheses choices
$\left\\{\left\\{S_{i,j},W_{i,j}\right\\}_{i\in[K]},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{j}\right\\}_{j\in[m]}$,
_i.e.,_ $S_{i,j}\coloneqq\\{Z_{i,j,1},\ldots,Z_{i,j,n}\\}$,
$Z_{i,j,l}\sim\mu$, independent of other
$\left\\{Z_{i^{\prime},j^{\prime},l^{\prime}}\right\\}_{(i^{\prime},j^{\prime},l^{\prime})\neq(i,j,l)}$,
$W_{i,j}$ is chosen according to $P_{W_{i}|S_{i}}(w_{i,j}|S_{i,j})$, and
$\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j}\coloneqq(W_{1,j}+\cdots+W_{K,j})/K$. Fix $\epsilon\in\mathbb{R}$ and
$\delta\in\mathbb{R}^{+}$. Let
$\Delta_{i}\coloneqq\sqrt{2\sigma^{2}\left(R_{p}(\delta,\epsilon,i)+\log(1/\delta)\right)/n}+\epsilon$
and $\Delta\coloneqq\max\nolimits_{i\in[K]}\Delta_{i}$. We consider the
probability that the generalization error for all $j\in[m]$ instances of the
algorithm $\mathcal{A}_{1:K}(S_{1:K})$ being greater than $\Delta$, and upper
bound this by the probability that average of them being greater than
$\Delta$. Then, we relate this to the sum of $K$ terms, each only depending on
the training dataset of the client $i\in[K]$. Specifically, we have

$\displaystyle\mathbb{P}\left(\operatorname{gen}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\geq\Delta\right)^{m}$
$\displaystyle=\mathbb{P}\left(\forall
j\in[m]\colon\operatorname{gen}(S_{1:K,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{j})\geq\Delta\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{1}{mK}\sum\limits_{i\in[K]}\sum\limits_{j\in[m]}\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})-\hat{\mathcal{L}}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{j})\geq\Delta\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}K\max_{i\in[K]}\mathbb{P}\left(\frac{1}{m}\sum\limits_{j\in[m]}\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})-\hat{\mathcal{L}}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})\geq\Delta_{i}\right),$ (24)

where $(a)$ holds since $\Delta\geq\Delta_{i},i\in[K]$ and using the fact that
for every pair of random variables $(X,Y)\in\mathbb{R}^{2}$ and constants
$(c_{1},c_{2})\in\mathbb{R}^{2}$ it holds that $\mathbb{P}(X+Y\geq
c_{1}+c_{2})\leq\mathbb{P}(X\geq c_{1})+\mathbb{P}(Y\geq c_{2})$. Now, use the
following claim the proof of which will follow,

$\displaystyle\mathbb{P}\Big{(}\frac{1}{m}\sum\nolimits_{j\in[m]}\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})-\hat{\mathcal{L}}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})\geq\Delta_{i}\Big{)}\leq\delta^{m},\qquad\text{for
every}\>\>i\in[K].$ (25)

Combining this claim with (24) and taking the $m^{th}$ root of both sides, we
get $\mathbb{P}\left(\operatorname{gen}(S_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)\geq\Delta\right)\leq\delta e^{\log(K)/m}$. Finally, letting
$m\rightarrow\infty$ completes the proof. Observe that the effect of
considering $m$ independent instances helped to diminish the effect of the
multiplicative term $K$, and hence avoiding to have the failure probability as
$K\delta$, rather than $\delta$. It remains to show that (25) holds.

Fix $i\in[K]$. The rest of the proof is as follows. First, we show that
$\frac{1}{m}\sum\nolimits_{j\in[m]}\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})-\hat{\mathcal{L}}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{j})$ corresponds to the
generalization error of an algorithm, which is a concatenation of $m$ i.i.d.
instances of another algorithm. Then, using results of [Sefidgaran et al.,
2022], we establish a rate-distortion theoretic bound on the generalization
error of this concatenated algorithm. The rest of proof follows by showing
that the rate-distortion function of the concatenated algorithm (with
parameters $\epsilon$ and $\delta^{m}$) is not bigger than the sum of the
rate-distortion functions of each instances (with parameters $\epsilon$ and
$\delta$). A similar relation is known in the lossy source compression
context, and here we show this hereafter for the adaptation of the rate-
distortion functions for statistical leaning algorithms.

Formally, let $\mathbf{S}\coloneqq\left\\{S_{i,j}\right\\}_{j\in[m]}$ with
$S_{j}\coloneqq S_{i,j}$, $\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}\coloneqq\left\\{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{j}\right\\}_{j\in[m]}$,
and $\mathbf{U}\coloneq\left\\{W_{1:K\setminus i,j}\right\\}_{j\in[m]}$ with
$U_{j}\coloneqq W_{1:K\setminus i,j}$. Note that $\mathbf{U}$ is independent
of $\mathbf{S}$ and $P_{\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu|\mathbf{S},\mathbf{U}}}=\prod_{j\in[m]}P_{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu{j}|S_{i,j},W_{1:K\setminus i,j}}$. Finally, for
$\mathbf{z}\coloneq(z_{1},\ldots,z_{m})\in\mathcal{Z}^{m}$, define
$\ell(\mathbf{z},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu})\coloneq\frac{1}{m}\sum_{j\in[m]}\ell(z_{j},\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern 1.5mu_{j})$. Now, consider a
learning algorithm that has access to the dataset $\mathbf{S}$ and the
randomness $\mathbf{U}$ and picks the hypothesis $\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}$according to
$P_{\mathbf{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}|\mathbf{S},\mathbf{U}}$. Then,
$\operatorname{gen}\left(\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}\right)=\frac{1}{m}\sum_{j\in[m]}\mathcal{L}(\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})-\hat{\mathcal{L}}(S_{i,j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{j})$. Hence, showing
(25) is equivalent to showing
$\mathbb{P}\left(\operatorname{gen}(\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu})\geq\Delta_{i}\right)\leq\delta^{m}$. Using [Sefidgaran et al., 2022,
Extended Theorem 10 in Appendix D.2.] we get

$\displaystyle\mathbb{P}\left(\operatorname{gen}\left(\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}\right)\geq\sqrt{\frac{2\sigma^{2}\left(R(\delta^{m},\epsilon)+\log(1/\delta^{m})\right)}{mn}}\right)\leq\delta^{m}.$

where $R(\delta^{m},\epsilon)\coloneqq\sup\limits_{Q\colon
D_{KL}\left(Q\|P_{\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu},\mathbf{U}}\right)\leq\log(1/\delta^{m})}\inf\limits_{P_{\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu}|\mathbf{S},\mathbf{U}}}I\left(\mathbf{S};\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu}|\mathbf{U}\right)$ and the infimum is over all Markov kernels
$P_{\hat{\mkern 1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu}|\mathbf{S},\mathbf{U}}$ such that

$\displaystyle\mathbb{E}\left[\operatorname{gen}(\mathbf{S},\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu)-\operatorname{gen}(\mathbf{S},\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu})\right]\leq\epsilon.$ (26)

Note that as explained in Remark 1 (and as noted in [Sefidgaran et al., 2022,
Equation (49)]), the above constraint is stronger than the one needed in
[Sefidgaran et al., 2022, Extended Theorem 10], and hence it is valid.
Moreover, note that the denominator in the square root is $mn$, as
$\mathbf{S}$ is composed of $mn$ independent samples. More precisely,
considering the second proof of [Sefidgaran et al., 2022, Extended Theorem 10
in Appendix D.2.] for $\operatorname{gen}(\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu})$,
“$\operatorname{gen}(\hat{W}_{2},S)$” in the paragraph before $(64)$ in
[Sefidgaran et al., 2022] would be the sum of $mn$ i.i.d. variables. Now,

$\displaystyle\mathbb{P}\left(\operatorname{gen}\left(\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}\right)\geq\Delta_{i}\right)$
$\displaystyle=\mathbb{P}\left(\operatorname{gen}\left(\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}\right)\geq\sqrt{\frac{2\sigma^{2}\left(mR_{p}(\delta,\epsilon,i)+\log(1/\delta^{m})\right)}{mn}}\right)$
$\displaystyle\leq\mathbb{P}\left(\operatorname{gen}\left(\mathbf{S},\mathbf{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}\right)\geq\sqrt{\frac{2\sigma^{2}\left(R(\delta^{m},\epsilon)+\log(1/\delta^{m})\right)}{mn}}\right)\leq\delta^{m},$

where the last step holds by the next lemma the proof of which is deferred to
Appendix D.4.

######  Lemma 1.

$R(\delta^{m},\epsilon)\leq mR_{p}(\delta,\epsilon,i)$.

This completes the proof of Theorem 3. ∎

###  D.2 Proof of Theorem 5

###### Proof.

We establish a proof based on Theorem 3. First, note that for binary
classification problem we have $\sigma=1$. Then, we use the following claim,
the proof of which will follow: for every $m\in\mathbb{N}$ and non-negative
triplet $(c_{1},c_{2},\nu)\in\mathbb{R}^{3}$ it holds that

$\displaystyle R_{p}(\delta,\epsilon,i)\leq m\log((c_{2}+\nu)/\nu),$ (27)

where

$\displaystyle\epsilon\coloneqq
8e^{-\frac{m}{7}\left(\frac{K\theta}{4B}\right)^{2}}+\frac{2m\nu^{m}}{\sqrt{\pi}}e^{-\frac{(m+1)}{2}\left(\frac{K\theta}{4c_{1}\nu
B}\right)^{2}}+4e^{-0.21m(c_{1}^{2}-1)}+4e^{-0.21m(c_{2}^{2}-1)}.$ (28)

This claim together with Theorem 3 imply that with probability at least
$1-\delta$ we have

$\displaystyle\operatorname{gen}_{\theta}\left(S_{1:K},W\right)\leq\sqrt{\frac{2m\log(c_{2}/\nu+1)+2\log(1/\delta)}{n}}+\epsilon.$

Letting $m=\lceil
112\left(\frac{B}{K\theta}\right)^{2}\log(nK\sqrt{K})\rceil$,
$c_{1}=c_{2}=\sqrt{\frac{K^{2}\theta^{2}}{20B^{2}}+1}$, $\nu=1/(2c_{1})$
completes the proof of part (i). The proof of the part (ii) follows similarly.

Now, we proceed to show the inequality (27). We show that under any
distribution $Q$ defined over
$\mathcal{W}\times\prod\nolimits_{i\in[K]}(\mathcal{S}_{i}\times\mathcal{W}_{i})$,
there exist proper choices of $P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|S_{i},W_{1:K\setminus i}}$ and 0-1 loss function
$\hat{\ell}(z,\hat{\mkern 1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}_{i})$ such that

$\displaystyle I\left(S_{i};\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}|W_{1:K\setminus
i}\right)$ $\displaystyle\leq m\log((c_{2}+\nu)/\nu)$ (29)
$\displaystyle\mathbb{E}\left[\operatorname{gen}_{\theta}\left(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)-\operatorname{gen}\left(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}\right)\right]$
$\displaystyle\leq\epsilon,$ (30)

where $\operatorname{gen}(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i})$ is computed based
on $\hat{\ell}(z,\hat{\mkern 1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}_{i})$. We borrow some ideas and results from [Grønlund et al., 2020]
and use them in a new context to show the claim. In particular, similar to
[Grønlund et al., 2020] we make use of Johnson-Lindenstrauss transformation
[Johnson and Lindenstrauss, 1984] to make the _compression_ in a space that
has a smaller dimension. More specifically, fix $i\in[K]$ and a matrix
$\mathsf{A}\in\mathbb{R}^{d\times m}$. Also, let
$\hat{\mathcal{W}}=\mathbb{R}^{d(K-1)+m}$ and denote each $\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}_{i}\in\hat{\mathcal{W}}$ as $\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}_{i}\coloneqq(\hat{w}_{i,1},\ldots,\hat{w}_{i,K})$, where
$\hat{w}_{i,j}\in\mathbb{R}^{d}$ for $j\neq i$ and
$\hat{w}_{i,i}\in\mathbb{R}^{m}$. First, define the loss function as

$\displaystyle\hat{\ell}(z,\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}_{i})\coloneqq\mathbbm{1}_{\left\\{y\llangle x,\hat{\mkern
1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}<\theta/2\right\\}},\quad\text{where}\quad\llangle
x,\hat{\mkern 1.5mu\overline{\mkern-1.5muw\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}\coloneqq\frac{\langle\mathsf{A}x,\hat{w}_{i,i}\rangle+\sum_{j\neq
i}\langle x,\hat{w}_{i,j}\rangle}{K}.$

Next, we define a proper choice of $P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|S_{i},W_{1:K\setminus i}}$. We impose the Markov chain
$S_{i}-W_{1:K}-\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}$, and define $P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}|W_{1:K}}$ as
follows. For $j\neq i$, we let $\hat{W}_{i,j}\coloneqq W_{j}$, and if
$\|\mathsf{A}W_{i}\|\leq c_{2}$, we choose $\hat{W}_{i,i}$ uniformly over the
$m$-dimensional ball around $\mathsf{A}W_{i}$ with radius $\nu$. Otherwise, we
choose $\hat{W}_{i,i}$ uniformly over the $m$-dimensional ball around the
origin $(0,\ldots,0)\in\mathbb{R}^{m}$ with radius $\nu$. This gives

$\displaystyle I\left(S_{i};\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}|W_{1:K\setminus
i}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}I\left(W_{i};\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}|W_{1:K\setminus
i}\right)=h(\hat{W}_{i,i})-h(\hat{W}_{i,i}|W_{i})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\log\left(\text{Vol}_{m}(c_{2}+\nu)\right)-\log\left(\text{Vol}_{m}(\nu)\right)=m\log((c_{2}+\nu)/\nu),$

where $(a)$ follows by using the Markov chain $S_{i}-W_{1:K}-\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}$ and the data
processing inequality; $(b)$ holds since by using the triangle inequality
$\hat{W}_{i,i}$ is always within the $m$-dimensional ball with radius
$(c_{2}+\nu)$ around the origin $(0,\ldots,0)\in\mathbb{R}^{m}$, the entropy
term $h(\hat{W}_{i,i})$ is maximized by the uniform distribution over the
ball; and $h(\hat{W}_{i,i}|W_{i})=\log\left(\text{Vol}_{m}(\nu)\right)$ since
conditionally given $W_{i}$ the variable $\hat{W}_{i,i}$ is distributed
uniformly over an $m$-dimensional ball with radius $\nu$. Note that here
$\text{Vol}_{m}(r)$ denotes the volume of $m$-dimensional ball with radius
$r$, which is equal to $\frac{\pi^{m/2}r^{m}}{\Gamma(m/2+1)}$ and
$\Gamma(\cdot)$ is the Gamma function. This shows that (29) holds for any
choice of $\mathsf{A}$. Now, we proceed to show that there exists a proper
choice of $\mathsf{A}$ such that (30) also holds, using techniques in
[Grønlund et al., 2020]. Fix a distribution $Q$ such that
$D_{KL}(Q\|P_{S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu})<\infty$. Note that the
expectation in (30) is with respect to $QP_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}|W_{1:K}}$. This
term is bounded in the following lemma, proved in Appendix D.5.

######  Lemma 2.

We have $\mathbb{E}\left[\operatorname{gen}_{\theta}\left(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\right)-\operatorname{gen}\left(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}\right)\right]\leq
D_{\mathsf{A}}$, where

$\displaystyle
D_{\mathsf{A}}\coloneqq\mathbb{E}_{(Z,W_{i},\hat{W}_{i})}\left[\mathbbm{1}_{\left\\{\frac{1}{K}\left|\langle
X,W_{i}\rangle-\langle\mathsf{A}X,\hat{W}_{i}\rangle\right|>\theta/2\right\\}}\right]+\mathbb{E}_{(S_{i},W_{i},\hat{W}_{i})}\left[\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}_{\left\\{\frac{1}{K}\left|\langle
X_{i,j},W_{i}\rangle-\langle\mathsf{A}X_{i,j},\hat{W}_{i}\rangle\right|>\theta/2\right\\}}\right],$

with $(Z,W_{i},\hat{W}_{i})\sim\mu Q_{W_{i}}P_{\hat{W}_{i}|W_{i}}$ and
$(S_{i},W_{i},\hat{W}_{i})\sim Q_{S_{i},W_{i}}P_{\hat{W}_{i}|W_{i}}$.

Next, to show the existence of a proper $\mathsf{A}$ we consider generating it
as in the Johnson-Lindenstrauss transformation [Grønlund et al., 2020]. The
following lemma is proved in Appendix D.6.

######  Lemma 3.

. The expectation of $D_{\mathsf{A}}$, when each entry of the matrix
$\mathsf{A}$ is generated i.i.d. according to $\mathcal{N}(0,1/m)$, is upper
bounded by

$\displaystyle\mathbb{E}_{\mathsf{A}}\left[D_{\mathsf{A}}\right]\leq
8e^{-\frac{m}{7}\left(\frac{K\theta}{4B}\right)^{2}}+\frac{2m\nu^{m}}{\sqrt{\pi}}e^{-\frac{(m+1)}{2}\left(\frac{K\theta}{4c_{1}\nu
B}\right)^{2}}+4e^{-0.21m(c_{1}^{2}-1)}+4e^{-0.21m(c_{2}^{2}-1)}=\epsilon.$

Finally, since the expectation of $D_{\mathsf{A}}$ is upper bounded by
$\epsilon$ there exists at least an $\mathsf{A}\in\mathbb{R}^{d\times m}$ such
that $D_{\mathsf{A}}\leq\epsilon$. Thus, (30) holds by Lemma 2. This completes
the proof of Theorem 5. ∎

###  D.3 Proof of Proposition 1

###### Proof.

Let $V_{i}$ be a $d$-dimensional random variable distributed according to
$\mathcal{N}(0,\sigma_{V}^{2}\mathrm{I}_{d})$, independent of all other random
variables, where $\mathrm{I}_{d}$ is the $d\times d$ identity matrix. Let
$\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\coloneqq\frac{1}{K}\left(\hat{W}_{i}+\sum_{j\neq i}W_{j}\right)$,
where $\hat{W}_{i}\coloneqq W_{i}+V_{i}$. Note that

$\displaystyle\mathbb{E}\left[\operatorname{gen}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)-\operatorname{gen}(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i})\right]\leq
2\mathfrak{L}\mathbb{E}\left[\|\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu-\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\|^{2}\right]=\frac{2\mathfrak{L}\sigma_{V}^{2}}{K^{2}}\eqqcolon\epsilon.$

Hence,

$\displaystyle\mathfrak{RD}_{i}(P_{S_{i},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu},\epsilon)$
$\displaystyle\leq I(S_{i};\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{i}|W_{1:K\setminus i})$
$\displaystyle=I(S_{i};\hat{W}_{i})$
$\displaystyle=I(S_{i};\mathcal{A}_{i}(S_{i})+V_{i})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{2\sigma_{V}^{2}}\text{Var}(W_{i})$
$\displaystyle\leq\frac{\sigma_{W}^{2}}{2\sigma_{V}^{2}},$

where $(a)$ is derived due to [Wang et al., 2021, Lemma 6].

Now, using Theorem 4, we have

$\displaystyle\mathbb{E}\left[\operatorname{gen}(S_{1:K},\bar{W})\right]\leq\sqrt{\frac{\sigma^{2}\sigma_{W}^{2}}{n\sigma_{V}^{2}}}+\frac{2\mathfrak{L}\sigma_{V}^{2}}{K^{2}}.$

Letting
$\sigma_{V}^{2}\coloneqq\sqrt[3]{\frac{\sigma^{2}\sigma_{W}^{2}K^{4}}{4\mathfrak{L}^{2}n}}$
completes the proof.

In a similar way, let $\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\coloneqq\frac{1}{K}\left(\mathbb{E}[W_{i}]+\sum_{j\neq
i}W_{j}\right)$. Then,

$\displaystyle\mathbb{E}\left[\operatorname{gen}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)-\operatorname{gen}(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i})\right]\leq
2\mathfrak{L}\mathbb{E}\left[\|W_{i}-\mathbb{E}[W_{i}]\|^{2}\right]=\frac{2\mathfrak{L}\sigma_{W}^{2}}{K^{2}}\eqqcolon\epsilon.$

Moreover,

$\displaystyle\mathfrak{RD}_{i}(P_{S_{i},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu},\epsilon)$
$\displaystyle\leq I(S_{i};\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{i}|W_{1:K\setminus
i})=0.$

Hence,

$\displaystyle\mathbb{E}\left[\operatorname{gen}(S_{1:K},\bar{W})\right]\leq\frac{2\mathfrak{L}\sigma_{W}^{2}}{K^{2}}.$

∎

###  D.4 Proof of Lemma 1

###### Proof.

Let $Q$ be product of $m$ i.i.d. $Q_{j}$, where $Q_{j}$ is a distribution
defined over $\mathcal{S}\times\mathcal{W}\times\mathcal{U}$. Hence,
$D_{KL}(Q_{j}\|P_{S_{j},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j},U_{j}})=\frac{1}{m}D_{KL}\left(Q\|P_{\mathbf{S},\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu,\mathbf{U}}\right)\leq\log(1/\delta)$. Moreover,

$\displaystyle R(\delta^{m},\epsilon)\leq$
$\displaystyle\sup\limits_{Q_{j}\colon D_{KL}\left(Q_{j}\|P_{S_{j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j},U_{j}}\right)\leq\log(1/\delta)}\inf\limits_{P_{\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu}|\mathbf{S},\mathbf{U}}}I(\mathbf{S};\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern 1.5mu}|\mathbf{U})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\sum_{j\in[m]}\sup\limits_{Q_{j}\colon
D_{KL}\left(Q_{j}\|P_{S_{j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j},U_{j}}\right)\leq\log(1/\delta)}\inf\limits_{P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{j}|S_{j},U_{j}}}I(S_{j};\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{j}|U_{j})$
$\displaystyle=$ $\displaystyle mR_{p}(\delta,\epsilon,i).$

where $(a)$ is deduced to the following claim: under the considered $Q$ (where
$\left\\{(S_{j},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j},U_{j})\right\\}_{j\in[m]}$ are _i.i.d._), to study the infimum, it
is sufficient to consider $\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern 1.5mu}$ that can be
written as $(\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{1},\ldots,\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{m})$, such that $P_{\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu}|\mathbf{S},\mathbf{U}}=\prod_{i\in[m]}P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{j}|S_{j},U_{j}}$ and
$\mathbb{E}\left[\operatorname{gen}(S_{j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})-\operatorname{gen}(S_{j},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{j})\right]\leq\epsilon$. To show this claim, given a $P_{\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu}|\mathbf{S},\mathbf{U}}$, let $\tilde{\mathbf{W}}\coloneqq(\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{1},\ldots,\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{m})$, where
$\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{j}$,
$j\in[m]$ are chosen based on $(S_{j},U_{j})$, according to $P_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{j}|S_{j},U_{j}}\coloneqq P_{\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern 1.5mu}|S_{j},U_{j}}$,
independent of $\\{S_{j^{\prime}},U_{j^{\prime}},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{j^{\prime}}\\}_{j^{\prime}\neq j}$. Then,

$\displaystyle I(\mathbf{S};\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern 1.5mu}|\mathbf{U})=$
$\displaystyle\sum\nolimits_{j\in[m]}I(S_{j};\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu}|\mathbf{U},S_{1:j-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sum\nolimits_{j\in[m]}I(S_{j};\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern 1.5mu}|U_{j})$
$\displaystyle=\sum\nolimits_{j\in[m]}I(S_{j};\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{j}|U_{j})$
$\displaystyle=I(\mathbf{S};\tilde{\mathbf{W}}|\mathbf{U})$

where we define $S_{1:0}\coloneqq\text{Constant}$, $(a)$ is derived since
$H(S_{j}|\mathbf{U},S_{1:j-1})=H(S_{j})$ and $H(S_{j}|\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern
1.5mu},\mathbf{U},S_{1:j-1})\leq H(S_{j}|\hat{\mkern
1.5mu\overline{\mkern-1.5mu\mathbf{W}\mkern-1.5mu}\mkern 1.5mu},U_{j})$. Note
that $\tilde{\mathbf{W}}$ satisfies the constraint (26), and hence for
studying the infimum it is sufficient to consider $\tilde{\mathbf{W}}$.
Finally, due to the symmetry, $\forall j\in[m]$,
$\mathbb{E}\left[\operatorname{gen}(S_{j},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{j})-\operatorname{gen}(S_{j},\tilde{W}_{j})\right]\leq\epsilon$. This
completes the proof. ∎

###  D.5 Proof of Lemma 2

###### Proof.

Let $(Z,\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu,W_{1:K},\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})\sim\mu Q_{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu,W_{1:K}}P_{\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|W_{1:K}}$. Note that since $D_{KL}(Q\|P_{S_{1:K},W_{1:K},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu})<\infty$, then under
$Q$ also $\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu=(W_{1}+\cdots+W_{K})/K$. Hence, we have

$\displaystyle\mathbb{E}_{\overline{W}}\left[\mathcal{L}(\overline{W})\right]=$
$\displaystyle\mathbb{E}_{(Z,\overline{W})}\left[\mathbbm{1}_{\left\\{Y\langle
X,\overline{W}\rangle\leq 0\right\\}}\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{(Z,\overline{W},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\mathbbm{1}_{\left\\{Y\langle X,\overline{W}\rangle\leq
0,Y\llangle X,\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}>\theta/2\right\\}}\right]+\mathbb{E}_{(Z,\overline{W},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\mathbbm{1}_{\left\\{Y\llangle X,\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}\,\leq\theta/2\right\\}}\right]$
$\displaystyle=$ $\displaystyle\mathbb{E}_{(Z,\overline{W},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\mathbbm{1}_{\left\\{Y\langle X,\overline{W}\rangle\leq
0,Y\llangle X,\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}\,>\theta/2\right\\}}\right]+\mathbb{E}_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}}\left[\mathcal{L}\left(\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}\right)\right]$
$\displaystyle\leq$ $\displaystyle\mathbb{E}_{(Z,\overline{W},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\mathbbm{1}_{\left\\{\left|\langle
X,\overline{W}\rangle-\llangle X,\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}\right|>\theta/2\right\\}}\right]+\mathbb{E}_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}}\left[\mathcal{L}\left(\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}\right)\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{(Z,W_{i},\hat{W}_{i})}\left[\mathbbm{1}_{\left\\{\frac{1}{K}\left|\langle
X,W_{i}\rangle-\langle\mathsf{A}X,\hat{W}_{i}\rangle\right|>\theta/2\right\\}}\right]+\mathbb{E}_{\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}}\left[\mathcal{L}\left(\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}\right)\right].$
(31)

Similarly, and by considering $(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu,W_{1:K},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i})\sim\mu
Q_{S_{i},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu,W_{1:K}}P_{\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}|W_{1:K}}$, with $S_{i}=\\{Z_{i,1},\ldots,Z_{i,n}\\}$, we have

$\displaystyle 1-$ $\displaystyle\mathbb{E}_{(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)}\left[\hat{\mathcal{L}}_{\theta}(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu)\right]$
$\displaystyle=$ $\displaystyle\mathbb{E}_{(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu)}\left[\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}_{\left\\{Y_{i,j}\langle
X_{i,j},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\rangle>\theta\right\\}}\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu,\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}_{\left\\{Y_{i,j}\langle
X_{i,j},W\rangle>\theta,Y_{i,j}\llangle X_{i,j},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}\,\leq\theta/2\right\\}}\right]$
$\displaystyle+\mathbb{E}_{(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu,\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}_{\left\\{Y_{i,j}\llangle
X_{i,j},\hat{\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}>\theta/2\right\\}}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu,\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}_{\left\\{Y_{i,j}\langle
X_{i,j},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\rangle>\theta,Y_{i,j}\llangle X_{i,j},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}\,\leq\theta/2\right\\}}\right]+1-\mathbb{E}_{(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\hat{\mathcal{L}}\left(S_{i},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu}_{i}\right)\right]$
$\displaystyle\leq$ $\displaystyle\mathbb{E}_{(S_{i},\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu,\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i})}\left[\frac{1}{n}\sum_{j=1}^{n}\mathbbm{1}_{\left\\{\left|\langle
X_{i,j},\mkern 1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu\rangle-\llangle X_{i,j},\hat{\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu}_{i}\rrangle_{\mathsf{A}}\right|>\theta/2\right\\}}\right]+1-\mathbb{E}_{(S_{i},\hat{\mkern