Summary
This paper studies the problem of decentralized optimization for non-smooth convex opjectives and time-varying networks. The paper introduces an algorithm to solve this problem together with matching lower bounds on the required communication and subgradient computations, thereby proving that the proposed algorithm is optimal in this sense.
Strengths
The paper is very well written and explains the concepts used in this work very clearly. Furthermore, the paper solves a relevant research question by proposing an optimal algorithm together with matching lower bounds. The results and proofs established in this paper seem to be correct.
Weaknesses
In my experience, optimization algorithms can sometimes yield unsatisfactory performance despite having good theoretical guarantees. Therefore, I believe that adding (even a small) simulation example showcasing the proposed algorithm's performance on a relevant problem would greatly improve the paper.
Furthermore, while the paper is generally very well written, the algorithm could be explained a little bit better. Even just mentioning which lines of the algorithm correspond to which step in lines 282 - 296 would greatly help a reader who is not necessarily familiar with each of the references. In exchange, I believe that the justification for considering convex cost functions (Section 1.2) could be shortened.
Finally, there are a few small typos that should be corrected:
I think that $\mathbf{1}_p$ should be defined as $(1,\dots,1)^\top$; Algorithm 1 requires an initialization for $\bar{z}^0$ and $\bar{y}^0$, and in the proofs (e.g., after line 765) you need to define w.l.o.g. that $\tilde{x}^0 = x^{-1}$; in line 657, I think you should have $+\langle x_a^K,z \rangle$ and you need to flip the sign in (87); in lines 692-693, the function $F(x)$ maps from $(\mathbb{R}^n)^d$, i.e., the argument should be $w^*$ instead of $x^*$; in Appendix E.3, E.4, and E:5, you previously used the notation $W(k)$ instead of $W_k$; in the first equations of Appendix E.6 (after (b)), I believe it should be $y^k$ instead of $y^{k+1}$, which is corrected in the next equation, and I do not see why you need line 7 of Algorithm 1 for (d); after line 773, there should be $k$ instead of $K$ in the third sum.
Limitations
I do not fully agree with the authors' answer to Question 2 in the NeurIPS Checklist, as limitations of the presented results and avenues for future research are not clearly discussed in the paper. More specifically, the authors only provide the required assumptions, but do not discuss whether these assumptions are restrictive in certain scenarios (except for Assumption 1) and whether these assumptions could be relaxed in future work.