Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a decentralized adaptive method for distributed deep learning, termed DAG-Adam. Convergence results are provided for smooth non-convex objectives under a bounded gradient assumption. Numerical experiments are conducted on Image Classification (CIFAR10, ImageNet-1k) and Language Modelling (fine-tuning pre-trained BERT models on SQuAD).
main_review: Strengths:
I found this paper very interesting, and have been long awaiting progress on the topic of adaptive decentralized optimization for deep learning. Traditional gossip-based methods performing consensus on the parameters cannot be naively applied to adaptive gradient methods, such as Adam, because of the non-linearity in the gradient update (e.g., dividing by the square-root of the second moment buffer), which breaks traditional proofs and significantly degrades performance in practice compared to centralized learning (e.g., see [a]). This paper is very important and contributes to an emerging literature. In particular, to realize the benefits of decentralized (gossip-based) optimization for deep learning, one must develop strategies suited for adaptive gradient methods, especially since many popular deep learning tasks seem to only work with adaptive methods, such as language models and the new swath of image-based methods relying on Vision Transformer architectures.

This paper also shows a very good familiarity with related work. Despite my current rating, I strongly support this paper, and thus will focus on the main issues I observed below so that the authors can address them, and hopefully find their paper accepted at the end of this process.

Weaknesses:
- Proposition 1 is somewhat meaningless… what is relevant here is a lower bound on the squared norm of the sub-optimality of the iterate $x^t_i$ as $t$ goes to infinity. Similarly for Proposition 2.
- Can you clarify the following: Theorem 1 assumes that not just the gradient is bounded, but that the gradient with an additional consensus penalty is bounded?
- In Theorem 1, the language indicates that $x^\star$ is the optimal solution, but note that in the non-convex setting there does not necessarily exist a unique global optimizer.
- Would be interested in seeing the statistical significance of results (across a few seeds) in Table 1 on CIFAR10.
- Why does heterogeneity of data distributions have such a large impact on the final validation performance in Table 1? I would expect the heterogeneity to affect the convergence rate, but not the final validation performance.
- What architecture is used for the Image Classification experiments?
- I don’t find enough evidence to support the fact that adapt-the-combine is the issue preventing convergence. It is quite bizarre to me that there should be a difference in adapt-then-combine compared to combine-then-adapt, since the two are often trivial re-parameterizations for gossip-based methods. For example, consider your case of the adapt-then-combine structure (section 2.2) equation 8. Let z^{t+1}_j = x^{t}_j - \gamma \frac{m^t_j}{\sqrt{v^t_j} + \epsilon} and let x^{t+1}_i = \sum_{j \in N_i} w_{ij} z^{t+1}_j, then the $z$ variable has the same fixed point iteration as equation (16) in your combine-then-adapt setting. To me it seems that the reason your proposed method seems to resolve the obvious issue of adaptive methods with linear consensus updates is that the consensus update is incorporated into the adaptive momentum buffer (i.e., tracking not just moving average of gradients, but also the consensus constraint), as opposed to swapping the order of adapt-then-combine vs combine-then-adapt. On this note, I would urge you to also take a look at the SlowMo work of [b] which incorporates a slow-moving consensus step into the momentum update of decentralized gossip-based methods.
- There might be a problem with Figure 1 since none of the methods convergence to the optimal solution in this strongly-convex case. For logistic regression in particular there isn’t an analytic solution for $x^\star$ so I’m curious how you’re computing it? Moreover, depending on the conditioning, there could be several solutions in the argmax set. I would be interested in seeing the logistic loss plotted instead, and would be particularly interested in seeing the MSE of the variable z (which I mentioned in the bullet above) plotted for the adapt-the-combine methods.
- With respect to the fixed-point iteration on page 4: the condition $f_i(x) \neq f_j(x)$ does not necessarily guarantee $H_i \neq H_j$ unless you make additional assumptions about how f_i and f_j differ. E.g., consider an extreme case where the distribution differences between $D_i$ and $D_j $amount to a constant shift in the expected loss.

[a] Assran et al., Advances in asynchronous parallel and distributed optimization, Proceedings of the IEEE, 2020.

[b] Wang et al., SlowMo: Improving communication-efficient distributed SGD with slow momentum, ICLR, 2019.
summary_of_the_review: In short, I find the paper very well motivated, the problem is very important, authors show a familiarity with related work, and the method is sufficiently novel.

However, I do not find the claims in the paper to be well supported. Specifically, I don’t find enough evidence to support the fact that adapt-then-combine is the issue preventing convergence of previous methods, and that the proposed method resolves this issue by using a combine-then-adapt strategy, especially since:
- with a simple re-parameterization, the proposed method can actually be written as an adapt-then-combine strategy
- propositions 1 and 2 showing issues with adapt-then-combine strategies provide upper bounds, but these are completely uninformative since the relevant quantities should provide a lower bound on the sub-optimality of the iterates with these strategies
It seems to me that the proposed method actually works because of the fact that consensus steps are incorporated into the first/second-order momentum buffers, not because the order of adapt/combine is flipped.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, authors propose the novel modification of Distributed Adam Algorithm that allows heterogeneous data.
main_review: In this paper authors propose to change the order of adaptation and communication in contrast with D-Adam. More precisely, First, in Section $2$, authors consider heterogeneous data as an input of D-Adam algorithm. They show that algorithm can diverge, moreover, under some additional assumptions it is proven to diverge. Another version of distributed Adam QG-DAdam uses another strategy - adapt-then-communicate. This algorithm also cannot converge to the optimum with heterogeneous input. Finally, they discussed the loss of efficiency of recent GT-DAdam in the same setup.
These arguments motivates authors to design the algorithm with communicate-then-adapt. This algorithm is based on the augmented gradient update that allows to interpret it as standard SGD algorithm with the same proof techniques. 

In Theorem $1$, authors present the theoretical result for their algorithm that converges: with the constant learning rate the augmented gradient converges to 0; with $\gamma = 1/\sqrt{T}$ the global average of iterates converges to the stationary point.

Finally, in the experiments authors compare their algorithm with different modifications of DAdam (that diverge) and Distributed SGD and shows that in practice their algorithm also makes sence. 

summary_of_the_review: I want to thank authors for their work. The heterogeneous input is very important and I think that the adaptation of Adaptive Distributed Adam to it is an important step. 
The only thing I am curios is the following: how do authors propose to calculate the global average and how long will it take in the end of the algorithm to calculate it? 
Furthermore, I think that this result can be extended to the case when instead of weighted update with neighbors we select every neighbor with some probability and communicate only among them. This can save a lot of communication cost and make an algorithm even faster.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new variant to decentralized Adam with a strategy called Communicate Then Adapt. The paper provides analysis and toy example to illustrate why a traditional Adam would fail to converge to the exact solution, and provide experiments on CV/NLP tasks to substantiate the theory.
main_review: On one hand, I think the idea of DAG-Adam looks interesting, as it requires no additional computation -- just a reordering on the adapting and communication, the algorithm is guaranteed to converge to the exact solution on strongly convex problems. However, in terms of the correctness and insights, I have three main concerns:

- Both proposition 1 and 2 are shown in terms of the $O(\cdot)$, which does not really substantiate the claim "DAdam cannot converge to $x^*$" since 1) $a=O(\cdot)$ means $a\leq C\cdot$ for some constant $C$, but $a$ can be arbitrarily small; 2) With no lower bound, it's hard to argue a $O(\cdot)$ is tight, so it's possible that the extra term $G^2/\epsilon^2$ is incurred by a loose analysis. I think the only way to substantiate the claim is to derive a lower bound.

- The idea of DAG-Adam, different from the DSGD which directly follows from the update rule, requires an additional hyperparameter $\nu$. This essentially seems to reduce the mixing time of the original communication matrix $W$ -- which is straightforward to verify by Equation (13). This may be unfair in the comparison to other algorithms -- it is possible that DAdam can perform equally good if the mixing matrix there is also tuned by $\nu$. So I think more illustration is need there, especially in the experiments.

- The paper provides empirical studies on multiple tasks, including image classification and BERT finetuning. However, it's not clear to me how these results interact with the main theorem. As these are non-convex, and there is no $x^*$ anymore, it's unclear whether these improvement comes from the strategy of "Communicate Then Adapt", or just the fact that gradient tracker is used/mixing matrix is tuned. On a side note, I recommend the authors to include std for each table, as the results are pretty close.
summary_of_the_review: Please refer to the main review. I'd be happy to increase my score if these concerns are properly addressed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper developed a new decentralized adaptive gradient descent method to address the data heterogeneity problem. The motivation is clear and the experimental results show improvement over existing methods. However, the theoretical analysis is not  solid. 
main_review: Pros:
1. The motivation is clear. It shows why existing methods do not converge to the stationary point. 

2. The extensive experiments can support the superiority of this new method. 

Cons:

1. The novelty is not significant. It is an extension of (Yuan et al., 2016) to the adaptive gradient. 

2. This method can only converge to the neighborhood of the stationary point. However, existing methods can converge to the stationary point.

3. $\beta_2$ is lower bounded. It is not very reasonable. $\epsilon$ should be very small. Then, this lower bound is very large. 
It conflicts with the common practice that $\beta_2=0.1$ or $\beta_2=0.01$. Thus, this convergence rate is problematic. 

4. How is $\beta_1$? Is there any constraint for $\beta_1$?

5. Which value is used for $\beta_2$ in the experiment?

5. Which value is used for $\epsilon$ in the experiment? Typically, $\epsilon$ should be very small, e.g., $1e-7$. According to Theorem 1, $v$ should be smaller than $\epsilon$. But it looks $v$ is large in the experiment. Thus, I don't think the hyperparameters in Theorem 1 are reasonable. 
 
summary_of_the_review: The problem studied is interesting. But the method is not novel and the theoretical analysis is not solid.
review_title: null

Meta-review: The paper proposes a ''communicate-then-adapt'' framework for decentralized optimization, with both theoretical and empirical analysis. The reviewers' main concern is the comparison in theory with prior methods like the GT-DAdam. The convergence to a stationary point of GT-DAdam seems to be faster than the proposed method in the important non-convex optimization. The reviewers are not convinced by the strong claim that ''communicate-then-adapt'' is better than ''adapt-then-communicate'' as such ''adapt-then-communicate'' method can also achieve same or better rates, possibly with less hyper-parameter tuning. I would suggest the authors to make more proper comparison with related methods.
Decision: Reject