Decentralized Optimization with Coupled Constraints

Authors: Demyan Yarmoshik, Alexander Rogozin, Nikita Kiselev, Daniil Dorin, Alexander Gasnikov, Dmitry Kovalev
Primary area: optimization
Keywords: decentralized optimization, convex optimization, affine constraints

Abstract:
We consider the decentralized minimization of a separable objective $\sum_{i=1}^{n} f_i(x_i)$, where the variables are coupled through an affine constraint $\sum_{i=1}^n\left(\mathbf{A}_i x_i - b_i\right) = 0$.
We assume that the functions $f_i$, matrices $\mathbf{A}_i$, and vectors $b_i$ are stored locally by the nodes of a computational network, and that the functions $f_i$ are smooth and strongly convex. 

This problem has significant applications in resource allocation and systems control and can also arise in distributed machine learning.
We propose lower complexity bounds for decentralized optimization problems with coupled constraints and a first-order algorithm achieving the lower bounds. To the best of our knowledge, our method is also the first linearly convergent first-order decentralized algorithm for problems with general affine coupled constraints.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1729348718456

thread_type:
official_review

<thread_object>
creator: reviewer_qah7

<content>
summary:
In this paper, the authors propose an algorithm for decentralized optimization with coupled constrains. Compared by most methods with proximal oracle, it is a first-order approach with a lower computational burden. The algoorithm is motivated on Chebyshev acceleration and Proximal Alternating Predictor-Corrector. The authors also provide the convergence analysis of the proposed algorithm in strongly-convex scenario and also proves that the proposed algorithm can reach the lower bound.

strengths:
1. first order iterations.
2. match the lower bound.
3. suitable for different kinds of problems.

weaknesses:
1. The presentation need to be improved. The contribution of the paper should be highlighted. And maybe it is more friendly for readers if the main algorithm is in Section 4, followed by the introduction of Chebyshev acceleration and Proximal Alternating Predictor-Corrector.

2. It seems that some existing results like [1] do not need the strongly-convex assumption. And the author fails to provide the convergence analysis without strongly-convex assumption.

3.  More experiments should be involved, including more problems with different coupled constraints. Some necessary comparison with algorithms developed for one kinds of constraints, like EXTRA in consensus optimization, should also be taken. 

[1] Distributed Optimization With Coupling Constraints.

[2] EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729675998974

thread_type:
official_review

<thread_object>
creator: reviewer_ieaz

<content>
summary:
This paper studies decentralized optimization with (affine) coupled constraints. This general formulation encompasses different applications, from energy networks to vertical (model-partitioned) federated learning. A complexity lower bound is given for this problem, as well as a matching (and thus optimal) algorithm. Both the algorithm and the lower bound are obtained through a reduction to the standard decentralized case, which is usually solved by introducing coupled constraints (the parameters from different nodes should be equal), and solving the constrained problem with a (primal-)dual approach. As such, the algorithm is based on APAPC (Salim et. al., 2022), and the lower bound directly proceeds from standard lower bounds. Adding extra coupling constraints is extremely natural in this case, and it is not surprising that using the same approach as for decentralized unconstrained optimization leads to similar results. The only care should be taken in how these extra constraints are added to ensure that the right quantities are communicated. Experiments demonstrate the (expected) superiority of the approach.

strengths:
- Tight analysis (optimal algorithm + lower bound) 
- Efficient off-the-shelf algorithm
- Authors clearly state their contributions and how they leverage previous work

I believe the main strength of the paper is that it uses the right tools to close a gap in the existing literature, so that non-experts can then use the algorithms.

weaknesses:
- Rather incremental contribution. All results directly derive from existing ones on the reformulation from (10), which is rather natural (though not straightforward).

In the end, I have mixed feelings about this paper. The contribution is not particularly innovative or technically challenging, but it has the merit of existing, and gives a well-rounded solution to this problem that people can then use. Therefore, I believe it should be published somewhere, though I am not completely sure this is the right venue, which is why I slightly lean towards acceptance. However, I am not too familiar with ICLR standards so I am looking forward to the discussion phase.

questions:
- Could you precise the results obtained on vertical federated learning (giving a simple corollary in some standard specific case for instance) so that people can compare their results directly with yours? Does it just correspond to $\kappa_A = 1$? How does this result compare with existing work in model-partitioned distributed optimization then?  
- Have you tried tuning the value of r in the experiments? What would be the impact?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730297508223

thread_type:
official_review

<thread_object>
creator: reviewer_hqpk

<content>
summary:
This paper studies the task of decentralized optimization under the coupled constraints setting. This setting is quite general, which recovers a wide range of existing problems such as the consensus problem, optimal exchange problem, etc. Using a multi-communication subroutine, the paper proposed a dual-loop algorithm that provably converges with fast and tight convergence guarantees.

strengths:
The authors provided a solid discussion on the related literature, which clearly explained the relative position of this paper with respect to multiple approaches in the prior works. The introduction also was able to convince me the generalizability and significance of this work.

The theoretical results offered by the authors, if correct, is tight and optimal.

The connection between FL and decentralized optimization has long been established. The coupled constraints setting considered in this paper can be a good starting point for technical understanding of VFL.

weaknesses:
Although the upper bounds and lower bounds are provided in this paper and is shown to be tight. The lower bounds is only applicable to a narrow class of algorithms represented by the proposed algorithm. There are other class of algorithms which could have been discussed.

The proposed algorithm uses a multi-communication algorithm in a dual-loop approach, where a subproblem must be solved with communication. Although the process is accelerated such that it is optimal, there exist studies in the decentralized consensus literature that utilize tools such as gradient tracking, ADMM, etc., and prove convergence with single-loop algorithms. This is also preferable in practice since the communication bottleneck is more apparent for modern optimization tasks. 

A more complex experiment with real data and even neural networks would be appreciated for VFL. Though it is understandably omitted since it would not satisfy any of the technical assumptions, it would still be nicer to see.

questions:
Currently, the lower bound is based on the algorithmic structure of the proposed algorithm, where the communication round lower bound is dependent on all three condition numbers. Is there a way to get an algorithm that only requires operations that only depend on their own respective condition number?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730388751154

thread_type:
official_review

<thread_object>
creator: reviewer_rp6n

<content>
summary:
This paper studies decentralized optimization with constraints. It establishes the lower bound for this problem, and develops algorithms to attain such lower bound. The main idea is to transform the original constrained decentralized problem into (20), and then rely on the algorithm APAPC to develop the optimal algorithm. Numerical algorithms are established to validate the theoretical findings.

strengths:
This paper is well-written and presents several key strengths:

1. The reformulation from problem (1) to problem (20) is novel and insightful, providing a strong foundation for the development of an optimal algorithm.

2. It establishes the first lower bound for decentralized optimization under affine constraints.

3. The paper also develops an algorithm that attains this lower bound, demonstrating both the tightness of the bound and the optimal complexity of the proposed algorithm.

weaknesses:
However, this paper has several notable weaknesses:

1. The novelty is limited. The core idea for constructing the optimal algorithm draws heavily from the APAPC algorithm (Salim et al. 2022a) and Chebyshev acceleration, a common technique in accelerated algorithms for unconstrained decentralized optimization. The authors combine these two techniques to create the proposed algorithm.

2. Another concern is the practical applicability of the proposed algorithm. While it achieves theoretical optimality, it is significantly more complex to implement than existing baselines. As shown in Algorithms 2-5, the proposed algorithm consists of multiple algorithmic blocks and introduces numerous hyperparameters—such as ρ, ν, δ, and p—that require tuning. These factors collectively detract from its practical value.

3. The numerical experiments are too trivial.

questions:
1. As noted in the introduction, unconstrained consensus optimization is a special case of problem (1). For this special case, can the complexity of Algorithm 2 be reduced to match the optimal complexity of the unconstrained consensus algorithm in (Scaman et al., 2017)?

2. In the simulation section, how do you tune the hyperparameters?

3. The simulation results appear somewhat limited. It is difficult to observe whether the complexity scales proportionally with $\sqrt{\kappa_f}$, $\sqrt{\kappa_A}$, and $\sqrt{\kappa_W}$, as established by Theorem 1. It would be beneficial to empirically validate the complexity of the proposed algorithm, particularly with respect to $\kappa_f$, $\kappa_A$, and $\kappa_W$.

4. It is recommended to evaluate the algorithm using more real-world datasets and more complex experiments, such as logistic regression.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733305290988

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common answer to Reviewers

comment:
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).
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper addresses decentralized optimization of a separable objective with affine coupled constraints, relevant to resource allocation, systems control, and distributed machine learning. It establishes lower complexity bounds and proposes a first-order algorithm that achieves these bounds, with linear convergence for general affine constraints—marking a first in this setting.

Most of the reviewers believe that the paper makes substantial contributions, and the AC also agrees with this assessment.