Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper analyses a variant of generalized federated averaging ([Wang et al.](https://arxiv.org/abs/2107.06917)) with partial worker participation and asynchrony in the stateful (i.e., the worker specific data can be saved on the server) and stateless settings, which characterize cross-silo and cross-device federated learning ([Kairouz et al.](https://arxiv.org/abs/1912.04977?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%253A+arxiv%252FQSXk+%2528ExcitingAds%2521+cs+updates+on+arXiv.org%2529)) respectively. Specifically for each global update, the server uses fresh gradients from $m$ out of $M$ machines, where each machine can make some local SGD updates starting from a stale global iterate (i.e., the gradients are delayed). This setting is termed *anarchic federated learning* (AFl) when the workers can have an arbitrary number of local steps and gradient delays.

The authors first provide a lower bound for convergence to a first-order stationary point in the AFL setting. Then they upper bound the convergence of their algorithms in the stateful and stateless setting when the local updates and delay are bounded. Under some regimes, and assumptions on the worker sampling and delay distribution, a linear convergence speed-up can be shown w.r.t. the number of machines ($m$ for the stateless setting and $M$ for the stateful setting). Some experiments are provided to measure the effect of the anarchic worker behavior.    
main_review: ## Convergence results

1) Why can't assumption 3 be relaxed to bound the heterogeneity only at any stationary point of $f$, i.e., $\|\|\nabla f_i(x^\star) - \nabla f(x^\star)\|\|^2 = \|\|\nabla f_i(x^\star)\|\|^2 \leq \sigma_G^2$, such as in [this work](https://arxiv.org/pdf/2006.04735.pdf)? This kind of an assumption better captures the heterogeneity of workers and is useful in understanding interpolation problems (c.f., [this work](https://arxiv.org/abs/2106.02720)). Regardless it should be clarified what are $x_k$'s in assumption 2 and 3, and assumption 3 needs an expectation because $x_k$'s are random variables(?). 

2) There is no need to introduce $G$ in Theorem 1, instead just say that it is valid for any level of heterogeneity characterized by $\sigma_G$. Moreover, **the theorem is very vaguely stated and in a sense wrong**. 

    - What do you mean by "any AFL algorithm"? Is SGD on each machine initialized at $0$ with a zero learning rate, not an AFL algorithm? That gets to the stationary point of the lower bound function exactly in zero steps! You need to give a lower bound for every optimization algorithm, for any setting of initialization and hyper-parameters (c.f., the [lower bounds here](https://arxiv.org/pdf/2006.04735.pdf) and in the references therein). 
    - Also, you allow for an arbitrary number of local steps on each machine i.e., $K=\infty$, so that you can ignore the $\epsilon$ in the lower bound proof. This is not the assumption under which you analyze your algorithms, so it is incorrect to use this lower bound to claim that the results are tight in $\sigma_G$. In fact, if one assumes that worker step-size is small and $K, \tau < \infty$ then that would allow for a more optimistic lower bound, and a better baseline for your upper bounds. In that case, $\epsilon$ will depend on the $\eta, K, \tau$ like it should.  
    - And what does it mean that the theorem holds for non-iid FL? The [lower bound here](https://arxiv.org/pdf/2006.04735.pdf) is already smaller than $\sigma_G^2$ (albeit for the convex setting, which is fine because your function is convex as well)! 

3) In corollary 1, I do not buy that there should be a $\sigma_G^2$ term. This is because I don't believe the lower bound in Theorem 1 for the reasons stated above. With a small enough client step-size, it should be possible to have a decaying term w.r.t. $\sigma_G$. 

4) You discuss in detail how it is important to improve the dependence on systems heterogeneity in the current federated learning guarantees. As an idea, anarchic federated learning sounds very enticing, but the result in theorem 3 is not AFL, it is just uniform partial client participation. Thus the theoretical result falls short of giving any novel insights. 
    - We already have results, in the setting where the local updates are non-uniform but bounded, and when the gradient updates are delayed (asynchronous updates). How is your result not just a combination of both of them? I was hoping your analysis doesn't require these boundedness assumptions. What is worse is that the dependence is somewhat worse here. For instance, the effect of delay has already been captured in [this paper](https://arxiv.org/pdf/1909.05350.pdf) (it has a $\tau$ dependence vs your $\tau^2$), and it has even been improved to depend on $\tau_{avg}$ instead of depending on the worst delay in [this paper](https://arxiv.org/pdf/2106.11879.pdf). The latter is very significant, especially in actual anarchic federated learning, where some workers might participate very intermittently, but others might not. If the dependence on $\tau$ can't be avoided, it should at least have been reduced to $\tau_{avg}$. 
    - Finally, how is this rate equivalent to the rate provided in the Scaffold paper in the non-iid FL setting? Their leading term is $1/\sqrt{mKT}$ which is better than your $1/\sqrt{mT}$ term. It is both **incorrect and misleading to assume that $K$ is a constant** and not a lever we'd like to move to see how the rate changes!  

5) I think it is indeed interesting to see a speedup in terms of $M$ instead of $m$ in corollary 3. In my opinion, this was the most interesting result in the paper. Overall, I think the paper can improve its writing to remove the focus from Theorem 1, 2 and instead direct it to the improved results for partial client sampling with asynchrony in theorem 3 and 4 (of course while improving upon the dependencies I point out above). 

## Experiments

It is unclear to me what to make of the experiments provided in the main paper. How was the anarchic behavior of the machines emulated in figure 1? It would make sense to bring some of this discussion from the appendix to the main paper. 


***
## Minor comments

1) Linear speed-up is an abused term in FL literature. It would be good to specify somewhere that (i) this is just convergence to a first-order stationary point, which might not completely capture the performance while training neural networks, and (ii) the linear speedup is conditional (even theoretically), i.e., it holds only till the number of machines is not too large (c.f., [this paper](https://arxiv.org/abs/1811.03600)). 

> We count each global model update as one communication round.  

2) We are not in the intermittent communication setting anymore, what does a communication round even mean? Devices are asynchronously pulling and pushing in this model. What does this mean then?  

3) Don't hide the dependence on $L$ and $\sigma_L^2$ in the corollaries. It makes it difficult to compare different terms in convergence with known convergence results. Moreover, it would make more sense to put the relevant baselines in a table to show a direct comparison with non-iid FL rates. It might also save some space.






summary_of_the_review: I don't believe that the provided results or the techniques used in this paper are surprising. The convergence results provided here are not tight in all the constants, and some of the assumptions made to provide those are too restrictive and don't morally allow anarchic behavior. As a result, I am not in favor of accepting this paper in its current state.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a general FL framework, called anarchic federated learning (AFL), that allows voluntary client participation of clients, with individual update steps and delay. Algorithms for both cross-device and cross-silo are presented. Convergence upper bounds and a lower bound are derived. Experimental results are reported to demonstrate the effectiveness of the proposed algorithm. 
main_review: This work is well positioned with the attractive properties of clients being "autonomous" in deciding whether to join the FL in each round. But, fundamentally, the studied FL problem is equivalent to asynchronous FL with random client selection (by the server), because the randomness due to the "free will" of the clients is statistically equivalent to being randomly selected by the server. Then, some additional degrees of freedom are considered, such as having different local steps and different delays. Nevertheless, these freedoms eventually are "masked" by the worse-case representations in Theorem 1, suggesting that it is equivalent to have these participating clients perform $K$ local update steps and delay at $\tau$. Furthermore, these worst cases are over both clients and time, suggesting that they are indeed the "worst" of the entire FL process. This result is quite discouraging. For example, throughout the whole FL process of say 500 rounds, if there is one and only one instance of a client having a large step size or large delay, Theorem 1 says this will dominate the entire convergence, which is counter-intuitive.

I'm willing to give the authors a chance to address these concerns, and I'll be open to adjusting the score accordingly. To me, the work itself is very interesting, but the aforementioned two issues should be addressed.

Some other comments:
(1) The requirement of having to wait for $m$ local updates is quite restrictive. Since the clients have the freedom to choose not to participate, there is always the chance that less than $m$ clients actually participate. Plus, waiting for $m$ local updates naturally leads to the straggler problem.

(2) On page 6, the authors claimed that only when considering the special case of uniformly distributed delay would we have the case of sampling $m$ clients from $[M]$ without replacement. As stated in my main concern, I do not believe this is the case. Rather, your model, even with non-uniformly distributed delay, is still equivalent to sampling $m$ clients from $[M]$ without replacement.

(3) Following up on (2), Theorem 3 is not well explained. It is unclear why with an additional assumption of uniformly distributed delay, one can improve Theorem 3, which relies only on the worst case delay.

(4) Theorem 2 has a dependence on $\alpha_L$, which scales with $\tau^2$. This term may becoming dominating if $\tau$ is large, as opposed to the $\sigma_G$ term. This is however hidden in Corollary 1, which is worth discussing.

(5) Typo: CS-AFL in page 2 should be AFL-CS. 
summary_of_the_review: As mentioned in the main review, I believe this work has potential and is interesting, but difference to asynchronous FL with random client selection (by the server) and addressing the worst-case behavior that dominates the convergence bounds are the two concerns I have.

========

Post-rebuttal: I have read the authors' responses and some (responses 3 and 4) have clarified confusions I had, which is helpful. The other responses are largely in line with my understanding of the paper. Overall, my review of this paper does not change.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes a different worker-server asynchronous communication pattern in federated learning, designs algorithms for cross-device and cross-silo settings, and analyzes the convergence of the proposed asynchronous schemes in the cases without assumptions on worker participation, and with some assumptions on the distribution of the active workers or bounded delay. It also empirically demonstrates that the asynchronous scheme achieves competitive performance compared with synchronous baselines.
main_review: Advantages:

* It provides convergence guarantees for the proposed asynchronous algorithms in federated settings.

* It also characterizes the lower bound without any assumptions on the client communication pattern, which provides useful reference points on the improvements of the analysis with additional assumptions.

Concerns:

* The proposed algorithms are very similar to those proposed in this paper (https://arxiv.org/abs/2106.06639, Federated Learning with Buffered Asynchronous Aggregation).  Although the paper I mentioned lets the server sample clients asynchronously, algorithmically looks like these two works are doing the same thing. I understand the submission is more general and improves the analysis in certain ways (e.g., without bounded gradient), but the main algorithms and some motivation are largely overlapping. It would be very helpful to clarify the major differences, if there are any.

* I am confused by the difference and the motivation for two variants designed for cross-device and cross-silo settings. (1) I think the server in both settings is assumed to be powerful in terms of memory and computation. Can the work give some references on why the server is assumed to have no historical information of the works? (2) The submission assumes uniform arrival for cross-device FL, and bounded delay for cross-silo FL. They both control the staleness of the model updates (to make sure the global model some device starts from is not too stale compared with the current global model for aggregation). Both of them are reasonable for cross-silo FL; and hence, to me, there isn’t a clear mapping between which setting is more compatible with which assumption. 

* I think one motivation for asynchronous training is that it leads to faster convergence (empirically) in the presence of stragglers. This point should be validated empirically (by simulating systems heterogeneity, for example). 

* In practice, the delays may be unbounded (e.g., when each device only participates once or twice during the training); so the two assumptions can be too strong.

Minor:

* Why does the lower bound also hold for FedAvg (described in Remark 1)? Under proper step-sizes, there is usually no constant error term.


* The last paragraph in Section 3 (1) spends much text highlighting that AFL is a general computing architecture. But this (using any local solver with different hyperparameters, allowing for device-specific local steps) is not a unique property of AFL, and lots of previous federated optimization methods also support this. 

* At the end of the first paragraph of related work (Sec 2), I don't think calling server-centric synchronous algorithms are not easy to implement is accurate or justified.

* The phrase 'general worker information arrival process' appears for the first time in the abstract, which is a bit abrupt and unclear---what is a worker information arrival process? general in what sense? 

* The empirical evaluation does not describe how the stragglers are simulated precisely. For example, the starting points of the clients uniformly sampled (or sampled in a biased way) correspond to which time stamp? Does the 'bias sampling' scheme (described in the appendix) correspond to the bounded delay case?
summary_of_the_review: I think studying asynchronous and device-centric communication in the context of FL is definitely interesting, and I feel the algorithms and the analysis in the paper are correct and solid. My major concerns are the first three points in the 'concerns' part of my comments, especially the differences between the submission and that related work.

====update====

I have read the authors' responses. However, I don't think the differences from the previous work (https://arxiv.org/abs/2106.06639) are significant. My concerns regarding the uniform arrival and bounded delay assumptions in federated learning, the experiments, etc remain. Therefore, I do not think this submission in its current form is ready for publication and I retain my original score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In order to address the issues of FedAvg (e.g. straggler, waste computation, slow convergence), this paper proposes a new federated training scheme "anarchic federated learning" (AFL) as an alternative. Instead of uniformly sampling participant clients, AFL let all workers to decide their number of local steps, when to communicate, and their step-sizes / batch sizes. The authors established a theoretical convergence rate of AFL and show that it recovers the rate of FedAvg under the assumption of uniform distributed arrival of worker information and bounded maximum delay and local steps. The authors also provides empirical evaluations on some experiments to demonstrate that

main_review: The overall idea of AFL is interesting and the theoretical results of AFA-CD and AFA-CS look reasonable. However, I found the following issues regarding AFL concerning. I hope the authors can address them in the rebuttal.

- The convergence rate of AFA-CD can be bad under the general worker information arrival process (truly anarchic). Take the equation in Corollary 1 for example, by the definition of $\tau$ and $K$, they can be as large as $O(T)$ if a few workers set their delay and local steps to be so. The algorithm 2 and 3 provides no guarantee that such delayed gradient will be rejected. That is, if a client starts local steps from $t=0$ and decide to submit its update at $T$, which is the *complete freedom* stated in the paper, algorithm 2 and 3 will incorpoate this update and ruin the training.

- The assumption of uniform distributed arrival of worker information is not realistic. The participants of cross-device federated learning have various computational power and communication frequency, etc.
So this assumption is most likely not true. It means in reality, AFL cannot achieve the same performance as FedAvg as FedAvg can enforce uniform sampling of clients.

- The assumption of bounded maximum delay and local steps is contrary to the "anarchic". In addition, the worker learning rate $\eta_L$ depends on the maximum delay. It can not be decided under the truly anarchic case.

- AFL is much more vulnerable to attacks than FedAvg. As the worker has the freedom to choose when to join training, the chance of attacker updates being incorporated in the aggregatrion is drastically increased by simply being eager to communicate to the server. This makes AFL vulnerable to backdoor/Byzantine attacks even if there is only a small percent of attackers. On the other hand, the FedAvg uniformly sample the clients and have a low chance of selecting many attackers.

### Typos
- Page 1, "stragglers (i.e. show workers)" => "slow workers"
- Page 2, "Clearly, AFL has a much lower sever-worker coordination" => "server-worker"
- Page 4, "Although the sever in cross-silo" => "server"

======

Post-rebuttal: I have read the authors' rebuttal and found them addressed my concerns so I decide to raise the score to 6.


summary_of_the_review: The anarchic federated learning is vulnerable to attacks and can be slower than FedAvg because of unbounded delay, local steps, and heterogeneity of clients.
review_title: null

Meta-review: This paper on 'anarchic' federated learning (FL) envisions an FL framework where edge clients can act independently instead of their participation being controlled by a central server. The idea is certainly promising, however, the reviewers pointed out the following main issues:
1) Technical gaps in the theoretical analysis need to be addressed
2) Bounded delay assumptions are too strong and are mismatching with the 'anarchic' goal of the framework
3) The linear speed-up claim should be better explained and justified.
The paper generated lots of post-rebuttal discussions. However, the concerns about the theoretical analysis still remain, and therefore I recommend rejection. I hope the authors will take these constructive comments into account when revising the paper.
Decision: Reject