Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work considers decentralized online learning in the asynchronous setup. Precisely, the learners do not make predictions at the same time and both the local updates and message transmissions incur delays. To account for this situation, the authors propose to index the time by two types of events: predictions and updates. Under this framework, an asynchronous push-sum algorithm is studied and its regret bound is established. The experiments do not only demonstrate the benefit of asynchronous method but also investigate several design choices of the algorithm.
main_review: This work makes an important step towards a better understanding of the asynchronous online optimization problem. Indeed, I agree with the authors that a complete description of an asynchronous online learning framework is inherently more intriguing than its offline couterpart, and the methodology considered in the paper paves the way for future research that tackle similar problems.

The algorithm itself is very similar to the original push-sum method, but the analysis in the new framework also turns out to be challenging. Moreover, I also find the papers to be well-written and easy to follow, despite the complexity of the underlying setup.

One potential concern is that the online learning part seems to be missing from the experimental section. In fact, it is not specified how the loss sequence is generated and how and when a learner is selected for making a prediction. Without the latter information, I do not really know what time measures in Figure 1. Moreover, how can we ensure that this difference is caused by the implementation of the algorithms? As for the losses, I imagine that samples are sampled uniformly at random. Indeed, stochastic optimization is frequently viewed as a special case of online learning (notably through online-to-batch conversion), but these experiments do not justify the choices to focus on the online framework. Similarly, the authors plot the average loss and not the (average) regret for the experiments.

Other remarks:

1. Pointing the readers to appendix B at the bottom at page 5 can be helpful, since, as claimed by the authors, the feasibility of the methods is not that immediate. Similarly, pointing the readers to the appendix for the complete pseudo-code can also be helpful.

2. With Assumption 1, I believe it always holds $D^{proc}\le\Gamma_{d}T$.

3. $\boldsymbol{\hat{g_t}}$
depends on the choice of $j$ and I recommend explicating this in the notation (such as $\hat{\boldsymbol{g}}_{j,t}$).

4. Adding dashed lines in Figure 1 can help illustrate the fact that the two algorithms achieve the same average loss.

5. [Hsieh et al. 2020](https://arxiv.org/abs/2012.11579) also studies asynchronous decentralized online optimization, though through a totally different approach. I suggest the authors include it in related work.
limitations_and_societal_impact: The limitations are discussed in the conclusion. Another limitation that I find about this work is that the learners cannot make predictions when they are occupied by the computation of the gradients. This is slightly different from the usual delayed online learning setup [Quanrud and Khashabi 2015](https://papers.nips.cc/paper/2015/file/72da7fd6d1302c0a159f6436d01e9eb0-Paper.pdf).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, authors propose asynchronous algorithm for convex optimization in decentralized distributed model. In contrast with other algorithms, the averaging procedure is asymmetric that leads to faster convergence comparing to the synchronous updates.
main_review: In this paper, authors consider distributed decentralized model with asynchronous communication between nodes. However, in this setup there is no one to one correspondence between nodes and loss functions.
First, authors explain their framework that is following: 1) some learner(node) is selected to predict with its own predictions. 2) some loss function is sent to the learner to calculate the gradient. 3) learner shares its update with some of the neighbors. 4) then all learners, who are not busy (see calculating the gradient) are performing the model averaging.

This setup allows to solve the common problem of synchronous algorithms, when some machine can be slow and all the others should wait for it to finish to perform their updates.

Then authors present the weighted projected online gradient descent that is based on the push-sum communications: instead of using doubly stochastic gossip matrix for averaging only the column stochasticity is required. 

Then authors describe the main contribution of the work; however it is hard to follow since there is no algorithm in the paper. Furthermore, I was lost in the theoretical result.

In the experimental part, authors provide the comparison of the symmetric and push-sum algorithm that proves the interest of push-sum algorithm for big delays that makes the asymmetric gossiping more robust. However, I think that this comparison is not good enough and some other algorithms should be added. Furthermore, some additional figures were provided to show the dependence of the efficiency of the push-sum algorithm of network size, network topology, and delays. Actually, I missed the message of these plots since I find these comparisons quite useless. Moreover, these plots are not colorblind-friendly so it was impossible for me to read them.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an asynchronous decentralized learning protocol. The motivation is to remove the need for computation nodes to synchronize broadcasting their local models (e.g., to a server), which improves efficiency and brings the setting closer to practical scenarios. The main contributions include (1) an event indexing system; (2) an projection scheme to ensure weight aggregation does not exit the feasibility region; (3) an instantaneous averaging scheme that aggregates neighboring models as soon as each node goes idle and (4) a regret bound analysis.
main_review: --Clarity
The paper is clearly written although the descriptions can be a little dense. In my opinion, some diagrams would help to explain the details more efficiently. Minor questions:

1. Is line 5 in Protocol 1 supposed to be outside the if/else block? Else, how does learner i_t gets picked to perform local update?
2. For the averaging scheme after line 139, does the order of broadcasted copies matter? For instance, when we do pairwise naive averaging, the result would be different from one-shot naive averaging, e.g., (a/2 + b/2)/2 + c/2 != (a + b + c)/3
3. Seems like a typo in line 203 with the update for y_i, which I think should be y_i \leftarrow \gamma_i y_i
4. What exactly does it mean by "adversarially chosen by the environment"? 

--Significance & Originality
I think the problem is important and the solution is well designed. However, I feel like the related work (Appendix) could be more extensive in reviewing other lines of works. Explicitly:
1. It seems that the related work section only focuses on decentralized literature. I believe a fair review has to include asynchronous centralized learning too.
2. When it was claimed that the event indexing system is superior because it "takes both prediction and local update into account", what are previous indexing systems designed to achieve and what exactly is the implication of this innovation? Also, apart from the computation delay, why do we have to index prediction events if they do not make any weight update? Can't they be modeled under the message delay component?
3. It was claimed that the weighted projection & instantaneous model averaging component makes the analysis more complex. To me, this feels like a consequence of incorporating these designs, rather than a contribution. 

--Quality
The strength of this paper is the thorough theoretical treatment. I find both the main results and the remark (line 256-268) very insightful. One thing I find somewhat unintuitive is that to achieve sublinear regret bound, the learning rate is set to \eta = (mF/2G)\mathcal{O}(T^{-1/2}), which seems excessively large on scenarios with massive number of nodes. How would this affect the quality of local update in practice? 

Regarding experiments: I find the overall quality of the empirical study somewhat disappointing for many reasons:
1. Why is there no classification error plot? I only see average loss plots, for which the loss value does not seem to improve much (i.e. on the order of 0.00x).
2. No error bar on the average plot. It would be interesting to see if different nodes have similar learning pattern, which is implied by the regret bound holding universally on every reference learner.
3. Not enough comparison to existing methods. The proposed method is only compared with its own counterpart, which doesn't say much. I think it needs to be compared with several methods from synchronous decentralized online learning as well as asynchronous federated learning to verify all the claims. 

---- Post-rebuttal review ----

Thanks for the detailed answers. Most of my concerns have been clarified and I will upgrade my score. I would still recommend the authors to acquire more benchmarks to improve the empirical study section.
limitations_and_societal_impact: The author did not discuss any broader impact of this work, but I believe there is no potential negative impact to society.
review_title: null

Meta-review: The reviewers agree that this generally a good paper although not entirely without (minor) flaws. Please take the reviewers comments in consideration when preparing a revision. The answers provided by the authors were given due consideration. 
Decision: Accept (Poster)