Federated Learning, Lessons from Generalization Study: Communicate Less, Learn More

We thank the reviewer for the time spent on our paper and their interest in our results.

1. Please refer to our response to all reviewers.

2. Note that the case $R=1$ is not the centralized learning algorithm, but the "one-shot" FL, where only one aggregation is performed. Indeed, in this case we obtain the best generalization performance, intuitively, since "the variance of the model" becomes small after one aggregation of the independent models. In contrast, it is hardly possible to minimize the empirical risk using only a single aggregation step. Therefore, $R=1$ is rarely the optimal value of $R$ when considering the population risk. In principle, there is a trade-off between the generalization error and the empirical error, as can be explicitly observed in Figure 3.

• Regarding further experiments: We would like first to reiterate that the presented experiments on FSVM mainly aim at validating the behavior suggested by our Theorem 4, \ie that the generalization error of FSVM might increase with $R$. The additional experiments on neural networks are meant to suggest that this behavior may hold in other setups. It should be remarked that the experiment on ResNet-56, presented in the Section 5 of the paper, was reproduced for different sets of hyperparameters, giving similar results. As a complement, we added the reproduced experiments for two different values of the learning rate in Appendix E.6. Finally, we agree that extensive exploration of the influence of optimization hyperparameters on the generalization error as a function of $R$ is indeed an interesting question. We believe however, it is beyond the scope and motivation of this work and therefore left for future work.

We thank the reviewer for the time spent on our paper and their interest in the results.

• Regarding $P_{\mathbf{S},\mathbf{W}}$: The reviewer's understanding is correct. It is a probability distribution over $\mathcal{W}^{(K+1)R}$. We agree with the reviewer that $\bigotimes$ is a more accurate notation, that is used in the new version.

• Regarding the setup: Please refer to the response to all reviewers.

• Regarding the aggregation: First, we mention that there exists a recurrent typo in some of the bounds: $\overline{W}^{[r-1]}$ should be read as $\overline{W}^{(r-1)}$, which is corrected in the new version. We are deeply sorry for this. Now, concerning the question of the reviewer (by considering $\overline{W}^{(r-1)}$): The aggregation function is deterministic. This means that once $W_{[K]}^{(r-1)}$ is known, then $\overline{W}^{(r-1)}$ is deterministic. However, in general, $W_{[K]}^{(r-1)}$ are random due to the randomness in the way the mini-batches $\beta_{k,r,t}$ are picked from $S_k^{(r)}$, for all clients/rounds/iterations and also due to initialization randomness. Hence, $\overline{W}^{(r-1)}$ is also a random variable. Now, regarding the cost of expectation, we agree that if expectation were need to be taken with respect to $\overline{W}^{[r-1]}$, it would be costly. However, we only need to consider the expectation with respect to $\overline{W}^{(r-1)}$. If we now consider, for example, the approach of Wang et al. ("PAC-Bayes Information Bottleneck", ICLR 2022) on estimating the mutual information or KL divergence terms, then this means that we need an extra bootstrapping phase for $\overline{W}^{(r-1)}$. An initial idea is to aggregate a subset of the clients' models $\{W_k^{(r-1)}\}_{k \in [K]}$, drawn uniformly at random, and repeat the process a number of times. This is in the same spirit as the bootstrapping (for other variables) in Wang et al. This further investigation, which is indeed interesting, is left for future work.

• Regarding $\mathcal{G}_{**S**}^{\delta}$: We apologize for omitting the definition of $\mathcal{G}_{**S**}^{\delta}$ (that contains $\nu_{\mathbf{S}}$) in the proof of Theorem 1, which happened after reorganization of that proof. We have added this in the new version.

• Regarding the subgausiannity: This is a classical property of subgaussian random variables. Borrowing the reviewer's notation, if $X$ is $\sigma_{k,r}$-subgaussian, where $\sigma_{k,r}=\sqrt{\frac{R}{4n}}$, then by Theorem 2.6.IV. of Wainwright, 2019, (available at the link provided below), for any $\lambda_1 \in [0,1)$, $\mathbb{E}\left[e^{\frac{\lambda_1 X^2}{2\sigma_{k,r}^2}}\right]\leq \frac{1}{\sqrt{1-\lambda_1}}$. Now, letting $\lambda_1 =\frac{2n/R-1}{2n/R}=\frac{\lambda}{2n/R}$, we drive that $\mathbb{E}[e^{\lambda X^2}]=\mathbb{E}\left[e^{\frac{\lambda_1 X^2}{2\sigma_{k,r}^2}}\right]\leq \frac{1}{\sqrt{1-\lambda_1}}=\sqrt{2n/R}\leq 2n/R.$ We added the reference in the proof for clarity. Moreover, previously for ease of expositions, we had reported the bound with the term $\log(2n/(R\delta))$ (and also since this term is rarely a dominant term). In the new version, we present them with the slightly tighter bound $\log(\sqrt{2n}/(\sqrt{R}\delta))$, for the clarity of the derivation.

The link: https://www.cambridge.org/core/books/highdimensional-statistics/basic-tail-and-concentration-bounds/30AF7B572184787F4C99715838549721

• Regarding the experiments: Please refer to our response to all reviewers.

Thank you much for the feedback and new comments, which are relevant.

The reviewer is right indeed on that, if one’s focus is only the generalization error then the message would be “just communicate once” (note the minimum value is $R=1$, not $R=0$), which of course would not be reasonable as small values of $R$ may not be enough to drive the empirical risk into a sufficiently small value. We are aware of this; and did exercise caution on this in the exposition at places of the paper. Also, it is precisely for this reason that all the experimental results that we reported we also provide curves on the evolution of the population risk (which is the true right measure of performance). For example, please see Fig. 3(b) where it is clear that the minimum value of population risk is obtained with $R = 100$ (which is way smaller than the optimum choice of $R$ from an empirical risk perspective (which is $R=3600$), and way bigger than the optimum choice of $R$ if we were to base only on generalization error which is $R=1$). Please note that for FSVM too, we did provide curves of empirical and population risks versus $R$; but for lack of space they were deferred to the appendices (see Fig. 4). Observe that as is clear from those curves, $R=1$ is not enough to get the empirical risk small; and, in fact, in that setup the ERM is minimum for $R=15$. The figure also shows that the population risk decreases way less fast than the EMR; and it barely decreases after $R \approx 5$. Other figures in the appendix also convey the same message such as Fig. 5-8. If the reviewer agrees, we can move those to the main body by merging Fig 2 and Fig 4.

We hope this is now clearer. Nonetheless, based on the reviewer suggestion, we will revisit the exposition to make sure that no single sentence in the material may be misleading on this point.

We thank the reviewer for the time spent on our paper and their interest in the problem studied in our paper.

For the responses regarding the raised concerns 1-3, please refer to our response to all reviewers.

4. Using the classic McAllester's PAC Bayes bound has two major shortcomings. First, considering the lossy version of it (which is more general) for FSVM leads to bounds of order $\mathcal{O}\left(\sqrt{\frac{B^2 \log(nK)}{nK\theta^2}}\right)$. This bound does not reflect the effect of the number of clients (since it depends only on $nK$, i.e., the total number of samples available, in contrast to our bound that depends on $nK^2$), nor does it include the effect of the number of rounds. More importantly, considering the entire learning algorithm as a single centralized algorithm and applying McAllester's bound results in a bound that can only be computed when all datasets are available on a server, and also only when the final model $\overline{W}^{(R)}$ is obtained. In contrast, our bound requires only the "local" availability of each client's data in each round, and requires only that client's "local" model at the end of the corresponding round. This is indeed a realistic assumption, and also helpful for "estimating" the total cumulative contributions to the generalization error at each round.

5. We could not unfortunately understand what the reviewer is suggesting. If our interpretation is correct, we recall that each data point is already used in only one local round in our considered setup, since a local dataset is split into $R$ subsets. We would like to kindly ask the reviewer to give us more details about their suggestion.