Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: > After the rebuttal: Some of my concerns have been resolved. However, the optimization theory still does not explain why $c_t = 0$ is not the optimal one. Since no theory shows that the generalization error of SA-FL is better than centralized learning. The whole story does not explain the empirical results.

In this paper, the authors study the PAC-learnability of Federated Learning (FL) with or without an auxiliary dataset on the central server. In the regime of FL with an auxiliary dataset on the central server (called SA-FL), they propose a new algorithm called SAFARI in which the central server computes the next round's initial model by both the aggregated model updates from local servers and the model update based on its own dataset.
strength_and_weaknesses: **Strength**:
- This paper provides theoretical guarantees for a Federated Learning framework that has been adopted in practice.
- The ablation study in Section 5 is insightful. 

**Weakness**:

I have several concerns about the theoretical results of this paper. 

Major concerns: 
- In the paragraph below Theorem 2, it says "Note that when $\beta\geq 1$, the first term in Eq. (1) dominates." This is not true unless $n_T + n_S > d_{\mathcal{H}}$. However, we cannot expect $n_T + n_S > d_{\mathcal{H}}$ to hold for FL with deep neural networks. For example, Bartlett et al. [1] show that $d_\mathcal{H} \geq \Omega(WL\log(W/L))$ for ReLU neural networks, where $W$ and $L$ are numbers of parameters and layers, respectively. If $n_T + n_S \leq d_{\mathcal{H}}$, the bound in Theorem 2 becomes vacuous. This should be explicitly mentioned.
- The assumption on "$(\alpha,\beta)$-Positively-Related" does not seem to be mild/natural. The authors did not justify it or give any example to explain when this condition might hold. 
- As far as I can tell, SA-FL degenerates into FL when $n_T = 0$. If we plug $n_T = 0$ into Theorem 2, the result shows that FL is also PAC-learnable under the same assumptions. This seems to contradict the main story of this paper. 
- The authors mention that "For example, it is shown in (Yang et al., 2021a) that more than 30% of clients never participate in FL, while only 30% of the clients contribute to 81% of the total computation even if the server uniformly samples the clients.'' However, this paper does not characterize the generalization bounds for participating and nonparticipating clients separately as suggested in [2]. 
- To ensure convergence, the proposed algorithm SAFARI needs $c_t$ decreases to 0 quickly enough (or even setting $c_t= 0$), which implies that the contribution of the local model updates diminishes to (or is) zero and the algorithm approaches (or is) the centralized training on the auxiliary data. Then, it is not surprising that the convergence guarantee does not depend on heterogeneity. 

Minor concerns:
- There is a $K^2\eta^3$ term in Theorem 4. If we choose $\eta = \frac{1}{\sqrt{KT}}$, the term becomes $K^2 \frac{1}{K^{3/2}T^{3/2}} = \frac{K^{1/2}}{T^{3/2}}$, which does not appear in the convergence rate shown in Corollary 1.
- Why the error bars are not shown in Figure 2?
- Only comparing SAFARI to FedAvg (LocalSGD) is not enough. More modern baselines such as SCAFFOLD (Karimireddy et al. 2019), FedProx (Li et al. 2018), and Nastya (Malinovsky et al. 2022) are needed to be compared with for showing the effectiveness of the proposed algorithm.

[1] Bartlett, Peter L., Nick Harvey, Christopher Liaw, and Abbas Mehrabian. "Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks." The Journal of Machine Learning Research 20, no. 1 (2019): 2285-2301.

[2] Yuan, Honglin, Warren Richard Morningstar, Lin Ning, and Karan Singhal. "What Do We Mean by Generalization in Federated Learning?." In International Conference on Learning Representations. 2021.




clarity,_quality,_novelty_and_reproducibility: **Clarity**:

The structure of this paper is overall easy to follow. However, there are some confusing statements.

- In Definition 1, there is only one argument of $\mathcal{R}_\mathcal{D}(\cdot)$. However, $\mathcal{R}_P(\cdot,\cdot)$ appears in the last line of Theorem 1. 
- Why state "$(\alpha,\beta)$-Positively-Related" as a definition instead of an assumption? It is actually a necessary assumption in Theorem 2. 
- The definition of $\mathcal{R}$ in the proof of Theorem 1 is not consistent with that in Definition 1. 
- Missing reference on Page 17 of the appendix. 

**Reproducibility**: 

No submitted code.
summary_of_the_review: This paper is the first to establish some theoretical guarantees of a practically used framework called server-aided federated learning (SA-FL). However, the concerns in the "Strength And Weaknesses" section make me unsure about the contributions of this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work theoretically analyzes that conventional Federated Learning (FL), heterogeneous and arbitrary client participation, is not Probably Approximately Correct (PAC) learnable. And then explore the reason and the fact that the server-aided federated learning (SA-FL) framework uses an auxiliary server dataset to reduce the distribution deviation induced by partial client participation (I will abbreviate it as PP), leading to the PAC-learnability. Besides, an algorithm SAFARI is proposed, which guarantees convergence. Ablation studies on MNIST and CIFAR10 verify the efficiency of the proposed algorithm. 
strength_and_weaknesses: Strength:
1. This paper theoretically proves conventional FL under the heterogeneous and arbitrary client participation setting is not PAC-learnable even in the limit of infinitely many data samples and training iterations. This could be a very interesting exploration. 
2. Based on conventional FL, SA-FL is theoretically analyzed and shown to be PAC-learnable under a few strong assumptions. 
3. SAFARI algorithm is proposed for handling SA-FL and achieves almost the same convergence rate as the state-of-the-art conventional FL algorithm under particular conditions. 

Concerns:
1. It's unclear whether the Assumption. 1 (noise condition) holds on real datasets, which may have very large noise. E.g., it would be interesting if some real example could be shown that the noise condition is satisfied. 
2. It's unclear whether different training protocols influence performance in SA-FL. Given client-distributed dataset $S_D$ with cardinality $n_S$ and server-persisted dataset $T$ with cardinality $n_T$, whether different training strategies affect the robustness and convergence? More concretely, will the following two strategies lead to the same behavior? a) using $S_D$ as a whole for fixed iterations $T^d>0$ and then consider $T$ only (without future averaging) for the following interactions; b) same as above but after $T^d$, do more averaging. What if $T^d=0$?
3. More comprehensive experiments should be provided. In Tab. 1 and Tab. 2 in the main content, only the "improvement" of SAFARI over FedAvg and SGD is provided; I'm curious about the absolute performance. Are SAFARI, FedAvg, and SGD fine-tuned? How are the hyper-parameters selected? Besides, I checked Fig. 4 in the appendix, e.g., (d), SAFARI is always no better than SGD; more analysis should be provided. 
4. Seversize data size seems to be too large. MNIST and CIFAR10 both have 60K images, and in this paper, 50-1000 data size from the distribution $p$ is selected; it seems the proportion is too large and not representative in practice. I believe SA-FL/FL is similar to the difference between few-shot learning and zero-shot learning, but only 1, 2, or at most 10 samples per class are provided for the latter. I'm concerned with the performance of a smaller server data size, which is more practical and interesting. 
5. In Sec. 5, "to simulate data heterogeneity, distribute the data into each client evenly." I'm unsure if each client has the same data distribution in this setting. What if a different and more heterogeneous data-splitting scheme is applied? Since this paper mainly focuses on the heterogeneous data setting, this should be more carefully considered. 

Additional comment:
1. Regarding the difference between FL and SA-FL, the authors may illustrate it with zero-shot and few-shot learning, which is almost the same case. This could be an interesting thinking perspective. 
clarity,_quality,_novelty_and_reproducibility: Clarity:
This paper is easy to follow, and the key idea is successfully conveyed. 

Quality:
The writing quality is good.

Novelty:
The theoretical analysis of conventional FL lower bound and SA-FL PAC-learnability is novel. The proposed algorithm SAFARI is novel but a bit intuitive. 

Reproducibility:
The illustration of Alg. 1 is almost clear. Lack of experimental details, and possibly there are some issues in the experimental design (concerns above). No code is provided.  
summary_of_the_review: This work is an interesting paper that theoretically explores partial client participation in federated learning. The theories are inspiring, but more comprehensive experiments should be conducted. I would like to increase my score if the above concerns are resolved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper is about dealing with partial participation in federated learning. Indeed, in the heterogeneous setting, there is a drift in the obtained solution if not all clients participate. the authors study this discrepancy and propose new algorithms to mitigate it. They consider the idea of sever-aided federated learning (SA-FL), which is to equip the server with a small auxiliary dataset that approximately mimics the population distribution. They provide new results on SA-FL and propose a new algorithm, called SAFARI, which handles partial participation and is communication-efficient.
strength_and_weaknesses: The paper provides interesting theoretical insights about heterogeneity and the important challenge of partial participation in FL.

SAFARI converges sublinearly to a neigborhood of a stationary point. 
I have a question: in Assumption 3: what is partial at the end? In any case, the bounded gradient assumption is restrictive and there seems to be no way to study linear convergence under strong convexity, for instance, since this is not compatible with this assumption.
clarity,_quality,_novelty_and_reproducibility: The paper is well written.
summary_of_the_review: The paper provides some new insights on partial participation, which is a timely and important problem in modern distributed learning settings. It is nice to obtain theoretical findings on SA-FL, which was so far heuristic.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors consider FL problem in the scenario where some nodes do not participate in the learning and provide a theory that analysis this scenario. Moreover, the authors consider SA-FL: the server takes part in the optimization process to mitigate the corruption from partial participation of the nodes.
strength_and_weaknesses: Before I start, I should acknowledge that I'm not an expert in statistical learning theory, so in this part of the paper, I can easily miss some important things. I am closer to the theory of optimization methods.

The first part is devoted to the statistical learning theory of FL under the partial participation setting. The motivation is clear and very important. In the beginning, the authors prove the "Impossibility Theorem" which is very interesting. It states the vanilla FedAvg will fail under the authors' setting. So that is why the authors analyze the idea of SA-FL.

From this point, I see the first weakness that I would like the authors to clarify:

1. The server has access to the dataset $T.$ So, in total, we have access to the dataset $Q = D \cup T.$ Not going into the details, the motivation of SA-FL is based on two assumptions: Assumption 1 and Definition 4, which introduce some similarity between datasets $Q$ and $P.$ The main motivation of the paper is to consider the case when $D \neq P.$ But from the assumption intuitively the authors require that $D \approx P.$ Moreover, is it possible to provide the "Impossibility Theorem" under these assumptions? The assumptions can be too strong.
2. Theorem 3: the assumption $\varepsilon_P(h^*_Q) \leq O(A(...))$ seems to be strong. They say that the optimal hypothesis from $Q$ is almost the optimal hypothesis from $P.$

In total, the statistical part I would evaluate with "marginally above the acceptance threshold."

Now, I move to Section 4.
The authors provide the SAFARI algorithm that has the following weaknesses:
1. From Theorem 4, it is clear that we have to take $c_t = 0$ to get the best convergence rate. It is not clear why we should take $c_t > 0.$
2. In line 3, the algorithm samples nodes uniformly. The main idea of the paper is to consider the setting with more complex samplings such that some nodes do not participate!
3. In line 10, the algorithm calculates gradients of the full function $F!$ The main point of FL is that server does not have access to $F!$ In the proof, the authors use the fact that $E_T \nabla F(x, \xi^0) = \nabla F(x) = E_P \nabla F(x, \xi).$ But in the previous section, the authors say that the server has access only to a small subset $T = (\xi^0_i)_i^k,$ so $E_T \nabla F(x, \xi^0) = \frac{1}{k} \sum_i \nabla F(x, \xi^0_i)$ and, in general, it does not equal to  $\nabla F(x).$ All it means is that the server has access to the function $F.$

Theoretically, the SAFARI algorithm does not solve the main problem of the paper.

clarity,_quality,_novelty_and_reproducibility: .
summary_of_the_review: The statistical part (Section 3) of the paper seems to be solid. However, I have some questions about Assumption 1 and Definition 4 that are not fully justified.

At the same time, the optimization part (Section 4) is weak and does not provide a method that would solve the main problem.

Section 3 seems to be somewhere between "marginally above the acceptance threshold" and "accept, good paper." But Section 4 definitely should be improved.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors study the PAC-learnability of Federated Learning (FL) with or without an auxiliary dataset on the central server. In the regime of FL with an auxiliary dataset on the central server (called SA-FL), they propose a new algorithm called SAFARI in which the central server computes the next round's initial model by both the aggregated model updates from local servers and the model update based on its own dataset.

The structure of this paper is easy to follow.

Weaknesses: 

- The optimization theory in this paper does not explain why $c_t = 0 is not the optimal choice. This is a major issue since this choice is the one used in standard literature. Since no theory shows that the generalization error of SA-FL is better than centralized learning, the paper story does not explain the empirical results.
- As an extensive and detailed discussion with one of the reviewers showed, the paper contains a large number of issues with notation, clarity and mathematical rigour. These are major issues that require a major revision of the paper.


Unfortunately, any single one of these two issues is enough for me to clearly recommend a rejection.
justification_for_why_not_higher_score: Fatal issues, lack of rigour. Result does not improve on standard approaches.
Decision: Reject