Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to improve the communication efficiency in decentralized learning. They propose a novel algorithm, DIGEST, which uses local SGD and random walk to reduce communication costs. The random walk communication can be extended to multi-stream. They provide  a standard convergence results and provide empirical evaluation. 
strength_and_weaknesses: Strength:
- The design of DIGEST looks interesting.
- The assumptions and theoretical results seem reasonable.

Weakness:
- It is claimed in page 8 that linear speedup O(1/VT) can be achieved provided $H+E\le O(\sqrt{T/V})$. However, the synchronize interval H can be as large as $2V$ ---- take a chain topology for example. Then the inequality means $T\ge V^3$ where the time for convergence increasings dramatically with the number of nodes. 

- It is unclear from the theoretical results how the graph topology influences the convergence.

- Only simulation experiments are provided.

Minor weakness:
- While it seems true that DIGEST is independent of the non-iidness of data, it is not reflected in the main theorem 4.1 due to the current assumption 4 (bounded second moment). 

- The claim of "time-varying" network topology is not justified in the paper.


clarity,_quality,_novelty_and_reproducibility: ### Clarity
While it is possible to understand the algorithms, the readability can still be improved.

### Novelty
Overall the paper looks novel. There is a somewhat similar work RelaySGD (Vogels et al., 2021) which considers decentralized optimization over a spanning tree with non-iid data. DIGEST additionally considers communication efficiency

Vogels T, He L, Koloskova A, et al. Relaysum for decentralized deep learning on heterogeneous data[J]. Advances in Neural Information Processing Systems, 2021, 34: 28004-28015.
summary_of_the_review: The DIGEST algorithm looks interesting but I still have concerns about the theoretical rates mentioned above. I hope that the authors can address my concerns.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes an alternative approach to Gossip and Random-Walk decentralized algorithms. Synchronous Gossip algorithms require agents to communicate their models to their neighbors and then wait for all of their neighbors' updates before aggregating the updates. This setup has two significant flaws. The first is the large communication overhead. The second is that mismatched computational ability among nodes and communication delays can further increase the convergence time. Asynchronous Gossip algorithms, where nodes communicate without waiting for their neighbors, aim to resolve the second issue. However, the communication overhead issue remains, and the delayed updates require strict assumptions to assure global convergence. Random-walk algorithms operate by having one agent update a global model with its local data and then passing the global data to one of its neighbors to repeat the process. While this approach offers significantly less communication overhead, there is a trade-off in increasing convergence time. 

This paper builds upon random-walk algorithms by having nodes perform local steps instead of idling and by having nodes that receive the global model perform an aggregation step, including the prior local steps. Analysis is performed on this algorithm to show how its convergence and experimental results demonstrate the algorithm's superior performance compared to other decentralized methods in terms of wall-clock time.
strength_and_weaknesses: The strength of this paper is that the proposed algorithm is an intuitive and novel extension of Random-Walk decentralized algorithms. Having agents be active by performing local steps when not hosting the global model limits the downtime of Random-Walk styled algorithms and closely mirrors the plethora of works that incorporate local steps in between gossip communications. The use of local steps in gossip communications has been well-studied empirically to reduce communication costs and the benefits should be transferable to Random-Walk style algorithms.

Unfortunately, the analysis of the algorithm is done using the assumption of bounded gradients (Assumption 4) and that the proportion of data held by each agent relative to the total amount of data is known. The bounded gradient assumption for unconstrained strongly convex minimization cannot be satisfied. This makes the analysis of the algorithm questionable considering the analysis is applied to the strongly convex function class. In addition, using the bounded gradient assumption makes any interpretation of gradient dissimilarity meaningless, as then the following holds

\begin{equation}
    \lVert \nabla f_i (x) - \nabla f_j(y) \rVert \leq \lVert \nabla f_i(x) \rVert + \lVert \nabla f_j(x) \rVert \leq 2G.
\end{equation}

Clearly, the measurement used to gauge the dissimilarity between functions is not refined. In addition, it is quite confusing as to why the bounded gradient assumption is even required. For the i.i.d. case the quantity is unnecessary. For the non-i.i.d. case, non-bias corrected methods uses the average of the norm of the local gradients evaluated at the global solution while bias-corrected methods require no assumptions. Another aspect of the algorithm that is not mentioned as an assumption but should be included is the use of the quantity $\frac{\mathcal{D}_v}{\mathcal{D}}$ which is the proportion of data held by agent $v$. Knowing this quantity is extremely powerful because it allows for decentralized algorithms to account for the data dissimilarity between agents as we know what weight each of the local objective functions contribute towards the global objective function. However, for decentralized algorithms, it is uncommon to possess any global information regarding the data. 

Another aspect of the algorithm that is not well defined is the relationship between the quantity $H$ and $V$ where $H$ is the bound on the interval between two synchronizations and $V$ is the number of agents. In the remark, the authors use the fact that $H + E \leq O (\sqrt{T/V})$. For Random-Walk styled decentralized algorithms, it is intuitive that the interval between two synchronizations increases with the size of the network. To account for this, an increasing number of synchronization streams $R$ would be required therefore increasing the communication cost. However, the relationship between $H$, $R$, and $V$ is not detailed.

Comparing the behavior of the various algorithms under the i.i.d. balanced case makes very little sense as communication is oftentimes much more expensive than local computation. Thus, performing more local computations is always preferred as local computations will inexpensively push all agents towards the global solution. In the non-i.i.d and unbalanced case, it is clear that DIGEST has the best performance. However, it is unclear what hyperparameters are used for the other algorithms. In addition, DIGEST has the benefit of knowing the proportion of data held by each agent. Thus, the validity of these simulations are questionable.
clarity,_quality,_novelty_and_reproducibility: The clarity and quality of the writing of the paper is adequate with minor grammatical errors throughout the paper. The paper is novel in that it combines the use of local steps into Random Walk styled decentralized algorithms. The experiments are not reproducible as the hyperparameters used for the various algorithms in the comparison are not provided. 


summary_of_the_review: The paper proposed a variant of Random-walk decentralized algorithms that have agents perform local steps instead of idling. Convergence analysis and experimental results are provided to show the feasibility of this algorithm. The analysis is questionable due to the use of the bounded gradient assumption in the strongly-convex setting. In addition, the algorithm requires knowledge of the proportion of the data held by each agent. The experiments do not detail the optimization of the various algorithms that are used to compare against the author's proposed algorithm.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new communication efficient decentralized optimization algorithm for stochastic gradient descent. The algorithm still has the comparable convergence rate compared with non communication efficient case. 
strength_and_weaknesses: + The algorithm achieves communication efficiency and fast convergence simultaneously. 
+ Both theoretical analysis and extensive experimental results are presented. 

-  The set of assumptions seems restrictive. 
-  The notation of the algorithm is not easy to follow.
clarity,_quality,_novelty_and_reproducibility: The notation of the paper is not easy to follow.
summary_of_the_review: The paper proposes a new communication efficient decentralized optimization algorithm for stochastic gradient descent. The algorithm still has the comparable convergence rate compared with non communication efficient case. The main concern of the paper is its assumptions seem restrictive.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a decentralized optimization algorithm incorporating local update steps (a la Local SGD) and compressed communication to improve the efficiency of decentralized training. The primary contributions are theoretical, and some experiments/simulations are also included.

The reviews identified several weaknesses, including strong/restrictive assumptions, limited empirical evaluation, and some questions about the practicality of the proposed approach (whether all information needed to implement it in a decentralized way is actually available in practice).
justification_for_why_not_higher_score: Strong assumptions limit the utility of the theoretical contribution.
Motivation around certain aspects of the problem and algorithm formulation could be strengthened (to justify why certain information is available or easily obtainable in a decentralized system).
Experimental evaluation could be expanded to more convincingly illustrate the benefits of the proposed approach.
Decision: Reject