Understanding the Theoretical Generalization Performance of Federated Learning

Thank you for your review. We have addressed the concerns in the following clarification and incorporated related discussions into the paper, with the main changes highlighted in blue text.

the contribution beyond existing results is unclear; relevant related work is not discussed

General Response about contribution: We appreciate the author’s comments on numerous existing papers in online learning, model averaging, and classic convex optimization. However, it is essential to highlight that federated learning constitutes an independent subarea due to its intricate interplay between heterogeneous data and local update steps throughout the learning process. The distinctive settings of federated learning, characterized by the diversity of data sources and the incorporation of local update steps, differ significantly from other contexts. Our objective is to explicitly quantify the influence of data heterogeneity, local update steps, and the total number of communication rounds on the generalization performance of FL. This area remains under-explored in federated learning. More specifically:

1). The unique setting of federated learning in deep learning (over-parameterization) is significantly different compared to works in online learning, model averaging, and classic convex optimization [2, 5, 8, 9, 10, 13].

2). While many works study the convergence of federated learning, including those mentioned by the reviewer [4, 7, 11, 12, 14, 15], our focus is on generalization.

3). The only paper mentioned by the reviewer that includes generalization analysis is [6]. This generalization extends from centralized learning using the Probably Approximately Correct (PAC) framework, which falls into the first class of related works in our paper. Please see Page 1 in our paper (“From a theoretical perspective, there has been relatively limited studies in addressing this question. We can categorize existing explorations into two classes. The first line of work employs the traditional analytical tools from statistical learning, such as the “probably approximately correct” (PAC) framework. These works focus on the domain changes due to the data and system heterogeneity…”). However, it's important to note that these works, including [6], do not provide an explicit relationship showing how critical factors in FL, such as the local update process, the number of communication rounds, and data heterogeneity, collectively affect FL's generalization. In other words, existing works have not fully explored the influence of these factors on the generalization performance of FL, which is the primary goal of our paper.

Related works: We appreciate the reviewer’s comment for various previous works studying the convergence of federated learning, and we will include them in the revision for a self-contained introduction of federated learning. It is essential to note, however, that our primary emphasis lies on the generalization of federated learning, for which we have meticulously presented an in-depth exploration of related works in our submission.

there are no experiments (e.g., on simulated data) to evaluate the tightness of the bounds

Response: Our Figs. 1, 2, and 3 are the numerical results for three cases to verify our three theorems. As shown in these figures, each marker is the average of 20 simulation runs and the curves are theoretical values from corresponding theorems. All these experiments show the tightness of our theoretical results.

the results are presented in a convoluted and unintelligible way with an unnecessary function $\mathcal{F}$ that hides the actual result and is not interpretable to me

Response: We explain the meaning of $\mathcal{F}$ in Section 2.5. In short, $\mathcal{F}$ corresponds to the general-term formula for a linear recurrence relation. Notice that we consider FL in multiple rounds, which is essentially a recurrence relation. Meanwhile, to help the readers understand our results, we provide expressions of the results in the simple case that does not contain $\mathcal{F}$.

the proofs provided in the Appendix are not well presented

Response: Thanks for your comments. However, it is unclear to us which parts of the proofs in the Appendix the reviewer referred to are not well presented. We would highly appreciate it if the reviewer can pinpoint to a certain proof, and we would be more than happy to make improvements.

Thank you for your review. We have addressed the concerns in the following responses and incorporated related discussions into the paper, with the main changes highlighted in blue text.

1. The model, i.e. the consideration of a linear model with i.i.d. Gaussian data, is very simple and unrealistic. However, as mentioned by the authors, this is now a commonly used model as a first step in understanding the theory. 2. In particular, there is an inherent alignment between empirical risk and generalization error in the considered setup. That is, they are somehow simultaneously minimized, which is in sharp contrast to most real-world scenarios. In fact, throughout the paper, the authors study "model error," a quantity that one would also study for empirical risk. For this reason, I am not sure if the findings on generalization behavior using this setup can be extended or useful for realistic setups.

Response: Thanks for your insightful comments regarding our model setting. For better readability, we also structure our response to your question accordingly as follows:

Simultaneously minimized risk and generalization erros: We respectfully disagree that both empirical risk and the generalization error are simultaneously minimized. In the cases of $K=1$ and $K<\infty$, the empirical risk is not minimized because the SGD/GD update is stopped after K steps (i.e., early stop). In the case of $K=\infty$, the empirical risk is minimized but the generalization error is not, since Eq. (6) suggests a zero empirical risk but the generalization error shown by Theorem 3 is still positive.

“Model error”: As we explained in the footnote of Page 4, the model error is equal to the expected test error for noise-free test data. This quantity is widely used to indicate the generalization performance in a linear model setup.

3. In addition, the authors stated that the model error can be shown to be equal to the expected test error for noise-free data. What happens if the data is not noise free? (I guess this is the interesting case, right?). How does the "model error" relate to the generalization performance in this case?

Response: Thanks for your question. The difference in the expected test error between the case of noise-free test data and the case of noisy test data is only the noise level (a constant that is irrelevant to the learning process). In the revision, we added Lemma 6 to make this claim rigorous.

4. Continuing the point 2, a good “generalization bound” typically decreases with the total number of used symbols (here, it would be $m\times n \times t$ at the end of iteration $t$, in the simple case). How does the provided bounds behave with these quantities?

Response: Thanks for your question. It appear sthat there are some misunderstandings in here. First, we want to clarify that our characterization of the generalization error is not a bound. Rather, it is the exact value of the expected generalization error. The correctness of our characterization is also validated by Figs. 1-3 that analytical values perfectly match simulation values. Second, the expressions in Theorems 1~3 contain $m$, $n$, and $t$ explicitly. For example, in Eq. (14), both H and G have $mn$ in their denominator and thus decrease with respect to $mn$. When the learning rate is small, we have $H<1$, which suggests the first term of Eq. (14) also decreases with $t$. The second term of Eq. (14) (noise term) increases with $t$ due to the accumulation of the noise effect over time.

5. It was observed and partially shown in previous papers (e.g. Gu et al. 2022 or arXiv:2306.05862) that the generalization error of the federated learning is smaller than that of centralized one (i.e. if we keep $m\times n$ fixed). Do authors observe similar phenomena using these theoretic results?

Response: Thanks for your question. Yes, we do observe similar phenomena in the case of $K=\infty$. As mentioned in our Insight 4, compared to the centralized one, the “null risk” can be alleviated and can achieve a smaller generalization error.

Thank you for your review. We have addressed the concerns in the following clarification and incorporated related discussions into the paper, with the main changes highlighted in blue text.

A major concern is the parameter defined by Equation (3). It does not seem like a suitable measurement for heterogeneity. Consider the case where $w_{(i), t} = w_{(j),t} = w^* + v$ with $\Vert v \Vert$ very large. In this case, all agents’ ground truth are the same, i.e. the data are homogeneous. However, the level of heterogeneity is very large by the definition in the paper.

Response: Thanks for the comments. We note, however, that if every agent shares a very large and common $v$, then this quantity $v$ should be considered part of $w^*$ to accommodate such bias. Indeed, the choice of $w^*$ depends on all $w_{(i),t}$ (e.g., their average). In general, $w^*$ should be regarded as the “largest” overlapped part of $w_{(i),t}$. Therefore, our measurement for heterogeneity is still suitable.

Is there a reference for Equation (25)?

Response: Thanks for your question. Yes, Eq. (25) can be found in [R1] (with changes of notations). Eq. (25) is also a special case of Eq. (23) in our Theorem 3 by letting $m=1$ and $t=1$.

[R1] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167–1180, 2020.

We appreciate the reviewer's feedback. We would like to point out that the concerns are mostly due to misunderstanding and we have made corresponding modifications to the paper, which are highlighted in blue text in the revision. Our response is outlined below.

The paper claims to be general enough to provide results for the non-stationary setting. However, it is unclear if measuring the distance from w^* is useful in the non-stationary setting. In particular, it is never discussed what w^* is and why the machines would want to recover it in a general setting, as opposed to minimizing regret with respect to a fixed best model in hindsight. Due to this reason, it seems that the simple setting for presenting results, where w^* is the average optimum of different machines, is the only reasonable setting. As a result, the generality of the results in this paper is not very useful, without further motivation.

Response: Thanks for your comments and suggestions. While letting $w^*$ be the average of different machines seems to be the most reasonable choice, there are some other possibilities in reality. For example, we may want to let $w^*$ to be the “smallest” (in certain criteria such as l2 norm) among different machines when the whole system’s performance depends on the machine with the smallest $w$.

There are some issues even if we consider all the results in the simple setting. In the most challenging setting, that is, for a general $K<\infty, \bar{||\gamma||}^2$ is conveniently assumed to be zero. This implies that all the machines have the same optimum as w^*. We already know the min-max optimal algorithms for quadratic functions in the homogeneous setting due to Woodworth et al.. Thus, theorem 2 is not interesting. Similarly, Theorem 1 is not interesting as without any local update steps, there is no consensus error, and the update looks exactly like the mini-batch SGD update on the averaged objective across the machines. Resultwise, insights 1-3 are not interesting either. Finally, Theorem 3 is interesting but it is very easy to obtain using standard arithmetic.

Response: Thanks for your comments. It appears that there are some misunderstandings. First, our paper focuses on offering a theoretical understanding of the generalization performance of FL, not min-max optimal algorithms for quadratic functions. Second, Theorem 2 not only provides the results for the simple setting but also provides the general results with heterogeneity and non-stationarity. Third, we believe that results in Theorem 3 are non-trivial and the key part of the proof is Eqs. (78)~(80), which depends on our Lemma 5. The proof of Lemma 5 is complex and novel, which by no means can be obtained by standard arithmetic. We also use Figure 4 to give a geometric interpretation of the proof.

Overall, I do not believe this paper is novel enough, and adds to the existing theory of local update methods.

Response: We would like to clarify and highlight that the main contribution and novelty of this paper is to derive exact expressions (instead of upper or lower bounds) of the generalization performance of FL for various settings of $K$, which provide meaningful insights. To the best of our knowledge, our work is the first of its kind in literature. That being said, we would highly appreciate it if the reviewer provides pointers to existing works that we are unaware of, and we would be happy to include and compare them in the revision of this paper.

Questions: How are the step sizes tuned in all the experiments? In particular, in Figure 2, are step sizes tuned separately for each experiment?

Response: Thanks for the question. The (fixed) step sizes are set to 0.02 in all experiments.

(23) also has null risk, depending on the order of taking limits. For instance if $p\to\infty$ before $t\to\infty$, then there is a residual null risk. As a result, Insight 4 seems wrong. Figure 3 also seems to show this. What is the insight here then?

Response: Thanks for your question. Again, it appears that there are some misunderstandings in how to interpret Insight 4. We note that Insight 4 only says the null risk is alleviated (not completely removed) by using more communication rounds and we explicitly discuss the issue of the speed w.r.t. $t$ and $p$ in the paragraph below Eq. (25). Hope this clarifies the confusion.