Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: For a heterogeneous distributed optimization setting in which data of different characteristics is available to different workers, the paper proposes the usage of the latest reported updates from workers when unavailable. As claimed in the paper, this amends the bias introduced when utilizing only data from available workers (as in the previous state of the art methods), improves the convergence bounds for convex and non-convex smooth optimization settings, and does not require up-front knowledge of the workers-unavailability statistics.
main_review: Well written paper, clearly presenting the state of the art and the problems addresses by the proposed approach. The proposed algorithm nevertheless, although claimed to be adaptive, requires upfront knowledge of the smoothness and strong convexity ($L$ and $\mu$ respectively), or searching for the correct values (i.e., to set the learning rate). Finally, although illustrating the superiority of the proposed methods over state of the art, the experimental section seems somewhat limited. To gain more confidence in the method and the related bounds, such experiments should have been run over several meta-parameters and unavailability schemes, datasets and model types.

A few comments and questions:
The results presented in the introduction (lines 63, 64) use notation yet to be defined. 
The notion of a communication round (as first mentioned in the introduction - line 48) is not reflected in Algorithm 1. E.g., how is the set of active devices determined? is there a watchdog/timeout to be employed? when is a 'round' declared? what if an update arrives later, out of the round (that is, a combination of the delayed setup and 'our setup' of Figure 1)?
Typos? - founded (line 119), till (line 124).

  
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies federated learning setup where clients might participate and drop out from the training arbitrarily. Broadly speaking, this is partial participation setup for FL, where there is no direct control on device availability. For such a setup, this paper designs MIFA algorithm, which stores latest gradients from devices and does not wait for strugglers during the training. The method is analyzed for strongly convex and non-convex cases with an additional (weak) assumption on device participation.
main_review: Partial participation (PP) is one of the characterizing aspects of federated learning (FL) as clients participate during the training only when they are available. Prior works usually model PP by assuming that a small portion of the devices (generated randomly) are available for the training. However, this ignores possibilities that some (or most and maybe even all) selected devices will be off, and in such case the ongoing communication round is failed. To overcome device unavailability, this work designs MIFA algorithm, which tracks the latest gradient information from each device and, in case of strugglers, updates the global model using stale gradient information of unavailable clients. This approach of handling device unavailability seems interesting.

Any explanation on why $b = 40(L/\mu)^{1.5}$ form is needed in Assumption 4 ? While the number of inactive rounds grow as ${\cal O}(t)$, it seems to grow slowly because of the value $b$.

The discussion in lines 252-262 are not completely fair comparison against FedAvg/SCAFFOLD, since $\frac{S}{N}\frac{1}{p_{\min}}$ iterations for FedAvg/SCAFFOLD are an extra waiting time, but for MIFA it is a normal iteration with communication rounds. In this context, are those waiting rounds counted in the experiments with FedAvg ?

Why the case that all devices are active is referred to as degenerated in line 66 ?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The article introduces a new algorithm called MIFA (Memory-augmented Impatient Federated Averaging) for Federated learning with arbitrary device participation. They derive theoretical guarantees in terms of average convergence of the algorithm, which are proved minimax for strongly and non strongly convex smooth losses. Numerical experiments illustrate the empirical behaviour of the method in comparison to a baseline FL algorithm.
main_review: The paper is sound, well written and clear, the theoretical results are also precise.  My one main concern is about the novelty of the setting, as detailed below. 
- The authors claim that existing methods only consider delayed responses of devices rather than full drop out, but I am not sure it is true. There are several FL algorithms, more recent thatn FedAvg, which handle partial participation of devices, including with missing devices (see, e.g. [1] and [2]), and I am not sure whether the setting you describe is really new. Please clarify.
- It is a bit frustrating that the obtained theoretical rates are not compared qualitatively to existing work. 
- It is also a bit frustrating that the method is empirically challenged only with FedAvg, when many algorithms have been proposed since then, including with partial device participation (see references [1] and [2]).


[1] Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, Peter Richtarik (2021). MARINA: Faster Non-Convex Distributed Learning with Compression. ICML.
[2] [1]Philippenko, C. and Dieuleveut, A., “Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees”, <i>arXiv e-prints</i>, 2020.

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper tries to overcome the challenge of federated learning that devices may drop out of the training process arbitrarily ( which doesn't follow any known or unknown distribution). This paper proposes the Memory-augmented Impatient Federated Averaging (MIFA) algorithm and provides its theoretical analysis under arbitrary device unavailability. Experiments have been done to show the advantages of the proposed method. 
main_review: Originality:  The assumption on the device availability ( similar to Assumption 4 and 8) has been widely used in the theoretical analysis for asynchronous algorithms. It is new to see the assumption is used in FL to analyze arbitrary device unavailability. 

Quality:  The submission technically sound and the claims are well supported by theoretical analysis and experimental results.  Theoretical analyses with convex and nonconvex functions are provided. This is a complete piece of work. 


Clarity: The submission is clearly written and well organized. 

Significance:  The analysis with assumption 4 is new and significant to federated learning. 
limitations_and_societal_impact: Given assumption 4, we have $\tau_{max, T} =O(T)$, So, in Theorem 5.1, there is a constant term $A_1/\mu^2$. It means the MIFA converges to the optimal solution with a constant error term, right? Similarly,  Proposition 5.1 has the same question.

In the experiment section, the initial learning rate only uses 0.1 and the weight delay only checks 0.001.  So, the comparison of performance among all methods may be unfaired.  It is better to check other learning rates and weight delays, and select the best performance for each method. 

In Figure 2(a-d), FedAvg-IS always gives the best performance in terms of communication round, rather than the proposed MIFA method. Instead of using communication round, the authors may want to show running time, since the intuitive advantage of the proposed method MIFA (or "asynchronous method") is the better running time since it doesn't need to wait for unavailable devices.
review_title: null

Meta-review: The authors focus on addresses some new challenges in Federated Learning. In particular they focus on the effect of straggler devices that may dropout which severely affect convergence of popular FL baselines. To ovecome this challenge they propose a new algorithm called Memory-augmented Impatient Federated Averaging (MIFA). The authors claim that their approach avoids the latency of inactive devices and can effectively correct for such gradient bias by using memorized updates from devices. The authors also show that this approaches achieve a minimax optimal convergence rate for non-i.i.d. data in certain cases. They also corroborate their theoretical findings with a variety of experiments. Most reviewers thought the paper was well written with a clearly presented approach to tackle a well motivated problem. The reviewers raised a variety of technical concerns some of which were addressed during the rebuttal. The conclusion of the discussion was that while the paper is not extremely novel/original and falls into the marginal category is a solid contribution and merits acceptance. I agree with this assessment and recommend acceptance with the condition that the authors clearly address the valid concerns raised by the reviewers.
Decision: Accept (Poster)