Common answer to Reviewers
Dear Reviewers,
We are grateful for your time, effort and the accurate reviews of our work. Thank you for acknowledging the novelty of the paper and paying attention to its strong parts. We upload a common answer to all of you and afterwards reply to each of the Reviewers individually. We hope that our replies will convince you to reconsider your scores.
The issues raised cover paper contribution and numerical experiments.
**Paper contribution**.
Reviewers **Rp6n** and **ieaZ** claim that the algorithm is a combination of existing methods and Reviewer **qaH7** asks to highlight the paper's contribution.
Indeed, we do use APAPC and (nested) Chebyshev acceleration together with the special problem reformulation (10), which include the decentralized-friendly reformulation of the coupled constraints and the augmented Lagrangian trick to induce the strong convexity. However, all these elements were not yet ready to be combined together: a nontrivial analysis was required to determine the strong convexity parameter of the reformulated objective on the necessary subspace (Lemma 1) and to derive the upper bound on the condition number of the matrix $B^TB$ (Lemma 2), as we need precise estimates for this quantities in terms of $\kappa_W$ and $\kappa_A$ (which are the initial assumptions) to derive the optimal convergence rates. One should also take into account that although the proof of Lemma 2 looks compact, it was tricky to obtain, especially because we did not know what the "correct" value of $\kappa_{\mathbf B}$ would be (for instance, what the "correct" form of Assumption 2 would be), as neither precise upper complexity bounds nor lower bounds were available before our work. In other words, it was impossible to obtain our main results using the analysis of previous works, and derivations of our results required new ideas.
Concluding, for the first time in the subfield of smooth and strongly convex distributed optimization with coupled constraints, we simultaneously develop both a state-of-the-art optimal algorithm and corresponding lower complexity bounds. This "resolves" this relatively small, yet important, subfield to a significant extent. We thank you for raising a question on contribution. A corresponding clarification will be made in the revised version of the work.
**Numerical experiments**.
Reviewers **qaH7** and **HQPK** insist on including more experiments for different setups, including vertical federated learning (VFL) and decentralized optimization without coupled constraints, reviewer **Rp6n** says that the simulations are too trivial. We agree that the experiments in our paper are simple. However, we respectfully disagree that these experiments are *too* trivial. That is, the main purpose of these experiments is to demonstrate that the proposed theoretical results do not contradict our theory. The quadratic optimization problems serve this purpose very well because we have control over all the parameters of the problem, such as condition numbers. Our experiments align perfectly with the theory, demonstrating significantly improved convergence rates compared to the existing state of the art, as suggested by the theory.
We would also like to note that it is standard and common practice for strong theoretical papers published in top venues, such as ICLR, to have small *illustrative* experiments or not to have any experiments whatsoever. Application to more complex VFL scenarios is an interesting direction, however, we think it requires a separate study because of implementation details. At the same time, we compare our method to EXTRA (for consensus optimization) and find that our method outperforms EXTRA (we used linear regression setup similar to (22) with ring graph on 5 nodes, $d=10$, $\kappa_f = 10^4$ and Laplacian of the full graph on 5 nodes to represent the consensus constraints as coupled constraints). The plots can be found at https://ibb.co/gj1Tdck.
**Reduction to consensus optimization**.
The Reviewers are interested how our approach can be used for consensus optimization, i.e. decentralized optimization without additional affine constraints. Reviewer **Rp6n** is interested whether a theoretically optimal reduction may be done, while Reviewer **qaH7** asks for a numerical comparison with consensus optimization methods. In the personal answer to Reviewer **Rp6n**, we hypothesize that optimal complexity for decentralized optimization cannot be achieved directly from our approach. We do not see this as a problem of our method, since our algorithm is used for a more general problem class. We also carry out additional numerical experiments and verify that our method is competitive and even outperforms the decentralized optimization algorithm EXTRA proposed by Reviewer **qaH7** (see plots at https://ibb.co/gj1Tdck).