Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks

We thank the reviewer for the time, effort, and feedback. Below, we provide our detailed response to the review.

Weaknesses

I believe that adding (even a small) simulation example showcasing the proposed algorithm's performance on a relevant problem would greatly improve the paper.

Thank you for the suggestion. We are currently working on the basic experiments and will try to include them in the revised version of the paper.

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.

We will try to provide an additional explanation of the algorihtm development with references to the corresponding algorithmic lines in the revised version of the paper by shortening Section 1.2, or by using an additional page if the paper is accepted.

Finally, there are a few small typos that should be corrected.

Thank you for finding the typos. We have corrected them as follows:

• changed $\mathbb{1}_p = (1,\ldots,1)^\top$;
• added missing initializations on line 1 of Algorithm 1:
  • added explicit initialization $\overline{y}^0 = y^0$ and $\overline{z}^0 = z^0$ (note that $\overline{y}^0$ and $\overline{z}^0$ are not used eventually due to line 4 and the fact that we use $\alpha_0 = 1$);
  • added explicit initialization $x^{-1} = \tilde{x}^0 = x^0$ and annotated corresponding transitions after line 765;
• fixed the sign of $\langle x_a^K,z \rangle$ on line 657 and after, and fixed the sign in equation (87);
• replaced $x^*$ with $w^*$ on lines 692-693;
• we use the notation $\mathbf{W}_k$ when $k$ is the iteration number, and $\mathbf{W}(\tau)$ when $\tau$ is the continuous time, which is mentioned on line 6 of Algorithm 1;
• in the first equation of Appendix E.6:
  • $y^{k+1}$ after (b) is a typo and is replaced with $y^k$;
  • (d) indeed does not use line 7 of Algorithm 1, it is just an algebraic transformation;
• fixed the third sum after line 773.

Questions

Why does (57) not change in Part(ii) (line 591)? I believe the result is correct, but I am not sure whether this statement is true.

There is indeed a small inaccuracy on line 591. Similarly to part(i) and due to Lemma 2 equation (57) will change to the following:

and the rest of the proof remains unchanged, including the last step:

We added this clarification to the proof. Thank you for noticing this.

Limitations

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.

We will try to add an appropriate discussion on the restrictiveness and the possibility of relaxing the assumptions. For instance, Assumption 5 can be relaxed to a more general joint spectrum property (Nedic et al., 2017), and a corresponding extension of our results would be trivial. Assumption 2 can probably be relaxed too, if we replace the subgradient method with some adaptive method like Adagrad [1].

[1] Duchi, John, Elad Hazan, and Yoram Singer. "Adaptive subgradient methods for online learning and stochastic optimization." Journal of machine learning research 12.7 (2011).

We thank the reviewer for the time, effort, and feedback. Below, we provide our detailed response to the review.

Weaknesses and Questions

The paper can be quite dense and while the authors provide slight intuition about the proof sketch in the main paper, most of the actual paper lies in the appendix which can make it quite inaccessible.

Would it be possible to make the main paper less dense and focus more on guiding the user through the intuition of the proofs?

Thank you for the suggestion. For the proof of lower bounds, the main theoretical ideas are listed on lines 204-223. We will try to enrich this part by adding a more detailed explanation of how to "assemble" these ideas into the final proof in the revised version of the paper. For the proof of algorithm convergence, the main algorithmic components are listed on lines 282-296. We will try to provide an informal explanation of how these components work from a theoretical perspective and how to obtain the final proof using them, with appropriate references to the lemmas in the appendix. We will try to obtain additional space for these changes, perhaps by shortening some parts of the introduction (as suggested by Reviewer 3roP), or by using an extra page if the paper is accepted.

We thank the reviewer for the time, effort, and feedback. Below, we provide our detailed response to the review.

Weaknesses

One minor weakness might be a lack of numerical experiments validating the convergence rate of the proposed algorithm. Nonetheless, I think it is not a big issue for a theory paper.

Thank you for the suggestion. We are currently working on the basic experiments and will try to include them in the revised version of the paper.

Questions

Why does the objective in eq (1) have a quadratic regularization?

We decided to use an explicit regularizer because it allows for a cleaner transition from the original problem (1) to the saddle-point reformulation (14). Note that any strongly convex finite-sum optimization problem can be presented in the form of equation (1). In the case of a non-strongly convex problem, we use the standard regularization technique, which allows the reduction of convex problems to strongly convex ones (see, for instance, [1]). We describe this in Appendix D.3. We will try to add this clarification to the main part of the paper in the revised version.

[1] Allen-Zhu, Zeyuan, and Elad Hazan. "Optimal black-box reductions between optimization objectives." Advances in Neural Information Processing Systems 29 (2016).

The theorem 1 and 2 state lower bounds of execution times but the authors interpret these results as communication and computation bounds. I wonder can you make this argument formal in the classical definition of communication complexity (Yao, 1979) and computation complexity (Papadimitriou, 2003).

Unfortunately, to the best of our knowledge, the vast majority of results in the optimization literature are provided in terms of limited computation models, for instance, black-box optimization procedures [2] (similar to what we use in the paper), or polynomial time methods [3]. Note that the latter is significantly different from the classical notion of polynomial time algorithms. The important aspect is that we need to obtain very refined results, rather than classical polynomial or exponential complexity, which is, in some sense, similar to the complexity results obtained for sorting algorithms in the comparison tree model, or for matrix multiplication algorithms in terms of algebraic complexity. Another potential issue is that our results depend not on the size of the input, but rather on the internal properties of the problem such as Lipschitz constants, network condition numbers, etc. Thus, making the arguments of Theorems 1 and 2 in terms of classical computation models may be difficult, at least within the limited author response period. However, this would be an interesting direction for future research.

[2] Nesterov, Yu E. "Introductory Lectures on Convex Optimization. A Basic Course." (2004).

[3] Nemirovski, Arkadi. "Interior point polynomial time methods in convex programming." Lecture notes 42.16 (2004): 3215-3224.

We thank the reviewer for the time, effort, and appreciation of the theoretical results of our paper.