Decentralized Optimization with Coupled Constraints

Dear Reviewer,

We are grateful for your review.

Highlight the contribution and Reduction to decentralized optimization.

We compared our method to EXTRA and found that it is competitive and even outperforms EXTRA (see plots at https://ibb.co/gj1Tdck). Please also see the common answer to all reviewers.

Only strongly convex case considered.

In the case of non-strongly convex objectives it is much easier to recover convergence rates which correspond to the classical unconstrained optimization. For example, the $O(1/k)$ rate from [1] can be achieved by considering the simplified version of problem (10) without the augmented Lagrangian term: $F(x) \to \min_{x, y} \quad \text{s.t.} \quad Ax + Wy = b$, reformulating it as the saddle-point problem $\max_z\min_{x,y} F(x) + \langle z, Ax+ Wy - b \rangle$ and applying the Extragradient method (Korpelevich, 1976) to it. There are many results with sublinear convergence rates for this type of problem, therefore we were not interested in the non-strongly convex setup.

In contrast, it is not that easy to achieve linear convergence (which is natural for gradient descent in strongly convex case) for coupled constraints as indicated by lack of such results in the literature. We achieved it by using the augmented Lagrangian trick and deriving the upper bound on the condition number of the matrix $B^TB$ in Lemma 2, which must be expressed in terms of $\kappa_W$ and $\kappa_A$ from the initial assumptions. The approach might seem simple, but it was not on the surface. Also the derivation of the upper bound turned out to be tricky, although the final proof looks pretty compact.

Dear Reviewer,

Thank you for your review and comments.

Incremental contribution.

Please see the common answer to Reviewers.

Vertical federated learning (VFL) and model-partitioned distributed optimization.

In case of VFL linear regression, as described in lines 457-466, we have very simple objective function with $\mu_f = 2\lambda$ and $L_f = 2\lambda + 1$, and all the information from the dataset is moved out to the coupled constraints. Since $\mathbf A_i = \mathbf F_i~\forall i = 2,\ldots,n$ and $\mathbf F_i$ are feature submatrices that can be arbitrary, we can not have any a-priori bound on $\kappa_{\mathbf A}$, because it is the parameter that characterizes all the complexity related to the dataset. As for the comparison with other algorithms for decentralized model-partitioned optimization, to the best of our knowledge, there are not much publications to compare with. This is expected due to the lack of gradient-based decentralized algorithms for coupled constraints. A recent survey on federated learning (FL) [1] includes a review of decentralized algorithms for FL in Section 3.3.3, but none of them deals with vertical FL. There is also a couple of more recent papers on decentralized vertical FL without theoretical guarantees [2], [3], and one paper with a sublinear rate of convergence [4].

[1] Ye, Mang, et al. "Heterogeneous federated learning: State-of-the-art and research challenges." ACM Computing Surveys 56.3 (2023): 1-44.

[2] Celdrán, Alberto Huertas, et al. "De-VertiFL: A Solution for Decentralized Vertical Federated Learning." arXiv preprint arXiv:2410.06127 (2024).

[3] Sánchez Sánchez, Pedro Miguel, et al. "Analyzing the robustness of decentralized horizontal and vertical federated learning architectures in a non-IID scenario." Applied Intelligence (2024): 1-17.

[4] Valdeira, Pedro, et al. "A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning." arXiv preprint arXiv:2309.09977 (2023).

Tuning of $r$ in experiments.

Regularization parameter $r$ is chosen according to theory, therefore, it can be viewed as a part of our algorithm. We did not tune $r$ in the simulations, since it could break the convergence.

Dear Reviewer,

Thank you for positive evaluation of our work!

Lower bounds. The lower bound says that it is not possible to separate condition numbers, at least within the class of vanilla first-order algorithms we considered. This class is a direct extension of the standard classes of algorithms considered for classical optimization by Nesterov [1] and for consensus decentralized optimization by Scaman [2]. It was actually a surprise for us that the communication complexity must depend on $\sqrt{\kappa_{\mathbf A}}$, since initially we were trying to obtain the algorithm with $O(\sqrt{\kappa_f}\sqrt{\kappa_{\mathbf W}}\log(1/\varepsilon))$ bound on the number of communication rounds. For instance, we knew that such separation of $\sqrt{\kappa_{\mathbf A}}$ is indeed achievable in the simpler case of consensus optimization with additional local affine constraints $A x = b$, which are the same for each node. Note that $O(\sqrt{\kappa_f}\sqrt{\kappa_{\mathbf W}}\log(1/\varepsilon))$ communication complexity is the lower bound of (Scaman, 2017) for consensus optimization, and we already knew that we could not eliminate $\sqrt{\kappa_f}$ in our more general setup. In our opinion, the derived bounds are interesting because they highlight the additional complexity brought by coupled constraints. We also do not believe that extending the class of algorithms to allow, for example, the use of the proximal operator of $f_i(x_i)$ will alter the complexity bounds.

Multi-consensus.

In Algorithm 2 of our paper multi-communication along with Chebyshev acceleration can be removed by replacing procedure mulW' (Algorithm 3) with a multiplication by $\mathbf{W}$ and replacing procedure K_Chebyshev (Algorithm 5) with multiplication ${\mathbf A}^\top({\mathbf A} u - {\mathbf b'})$. As a result, only two multiplications by $\mathbf W$ will be performed at each iteration of the method. At the same time, gradient, communication and matrix multiplication complexities of the method will not be separated. In other words, we can come away from multi-consensus at the cost of increased working time (at least, in theory). To the best of our knowledge, multi-consensus is inevitable to reach optimal complexity bounds in gradient computations and communications simultaneously. This is logical, since with single-step consensus each gradient call corresponds to exactly one communication round.

Numerical experiments.

Thank you for suggesting an experiment with VFL. However, we think that working with more complicated experiments, i.e. neural networks, requires a different study. One of the issues is how to compare different algorithms. Since problem parameters are unknown, it is a separate task to align parameters of different methods. Meanwhile, such alignment is needed if we want to run an experiment supporting at least some theory. Summing up, we believe that it is better to focus on convex optimization in experiments. You can find additional comments in the common answer to Reviewers.

References

[1] Nesterov, Yurii. Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science & Business Media, 2013.

[2] Scaman, Kevin, et al. "Optimal algorithms for smooth and strongly convex distributed optimization in networks." International conference on machine learning. PMLR, 2017.

Dear Reviewer,

Thank you for your review.

Novelty, contribution and additional experiments.

For this part, please see the common answer to all Reviewers.

Can the complexity of Algorithm 2 be reduced to match the optimal complexity of the unconstrained consensus algorithm?

Thank you for the interesting question. $\newcommand{\mA}{{\mathbf A}}$ As we see it, exact reduction is not possible in general. To reduce complexity bounds in Theorem 1 to that of Scaman (2017) we need to eliminate $\sqrt{\kappa_{\mathbf A}}$ from the communication complexity, and this is equivalent to $\kappa_{\mathbf A} = O(1)$. Since the coupled constraints must represent the consensus constraint $x_1 = \ldots = x_n \in \mathbb R^d$, the matrix $\mathbf A' := (\mathbf A_1 \ldots \mathbf A_n)$ is required to have $\ker \mathbf A' = \mathcal L_d$, i.e., $\mathbf A' x = 0 \Leftrightarrow x_1 = \ldots = x_n$ for any $x = \text{col}(x_1, \ldots, x_n)$.

For simplicity, let $d=1$, so all $\mA_i$ are column vectors. Natural examples of suitable matrices $\mathbf A'$ are incidence matrices of connected undirected graphs and their Laplacian matrices since $\ker \mA' = \mathcal L_1$. By the definition of the incidence matrix, the numerator of $\kappa_\mA$ is $L_\mA = \max_{i=1\ldots n}\sigma^2_{\max}(\mA_i) = \|\mA_i\|^2_2 = d_{\max}$, where $d_{\max}$ is the maximum degree of a vertex in the graph. Next, in the denominator we have $\mu_\mA = \frac1n\lambda_{\min^+}(\sum_{i=1}^n \mA_i \mA_i^\top)$. Note that $\sum_{i=1}^n \mA_i \mA_i^\top = \mA' \mA'^\top$, thus $\frac1n\lambda_{\min^+}(\sum_{i=1}^n \mA_i \mA_i^\top) = \frac1n\lambda_{\min^+}(\mA' \mA'^\top) = \frac1n\sigma_{\min^+}^2(\mA') = \frac1n\lambda_{\min^+}(\mA'^\top \mA') = \frac1n\lambda_{\min^+}(\mathbf L),$ where $\mathbf L = \mA'^\top \mA$ is the Laplacian matrix of the same graph. Now, substituting this in the definition of $\kappa_\mA$, and using a common fact that $\lambda_{\max}(\mathbf L) \leq 2 d_{\max}$, we obtain $\kappa_\mA = \frac{n d_{\max}}{\lambda_{\min^+}(\mathbf L)} \geq \frac{n \lambda_{\max}(\mathbf L)}{2\lambda_{\min^+}(\mathbf L)} \geq \frac n2$. Similar calculations lead to the same $\kappa_\mA = \Omega(n)$ bound in the case then $\mA'$ is taken to be the Laplacian matrix of a connected graph.

Therefore, using incidence matrix of any connected graph as $\mA'$ we have $\kappa_\mA = \Omega(n)$, what increases the number of communications by the factor of $\sqrt n$, comparing with the optimal convergence rates of Scaman. This is the additional price one need to pay for considering general coupled constraints instead of consensus constraints. This is typical for optimization: e.g., optimal algorithms for smooth (non-strongly) convex minimization have $O( 1/{k^2})$ convergence rates, while optimal algorithms for the more general class of smooth convex-concave saddle point problems only have $O(1/k)$ convergence when applied to minimization problems.

Parameter tuning.

The parameter values for all algorithms were chosen using the formulas from the papers to match the theoretically allowed ranges. Using the linear regression setup allowed us to calculate the parameter values analytically, so we did not use any black-box parameter tuning procedures

Dependence on condition numbers $\kappa_f, \kappa_{\mathbf A}, \kappa_{\mathbf W}$.

The dependence on $\kappa_{\mathbf A}$ and $\kappa_{\mathbf W}$ is quite clear from the theoretical analysis. When a matrix $\mathbf M$ is replaced with a Chebyshev polynomial of degree $\sqrt{\kappa_{\mathbf M}}$, the condition number of the resulting matrix becomes $O(1)$. This effectively removes its influence on the iteration complexity of the algorithm. Since the degree of the polynomial is explicitly defined, we know exactly how many matrix multiplications are required at each iteration.

Conversely, the analysis of Nesterov's acceleration is notoriously non-intuitive, making it much harder to track the algorithm's complexity dependence with respect to $\kappa_f$. We conducted an additional experiment to validate that the number of gradient calls, $N$, is $O(\sqrt{\kappa_f})$. We used a consensus optimization linear regression setup similar to (22) with a ring graph on 5 nodes, $d=10$, and the Laplacian of the full graph on 5 nodes to represent the consensus constraints as coupled constraints. By varying $\kappa_f$ from $10^2$ to $10^6$, we counted the number of gradient calls required to achieve $\|x^k - x^*\|^2 \leq 10^{-5}$. We then used scipy.stats.linregress to estimate the parameter $\alpha$ in the dependence $N \approx c \kappa_f^\alpha$ using a log-log scale: $\log N \approx \log c + \alpha \log\kappa_f$. We obtained LinregressResult(slope=0.496, intercept=2.018, rvalue=0.998, pvalue=3.343e-11, stderr=0.0105, intercept_stderr=0.098), where the slope corresponds to $\alpha$, and the intercept corresponds to $\log c$. The plot is available at https://ibb.co/jVJSQZZ. We observe that the estimated value of $\alpha = 0.496$ is very close to the theoretical value $\alpha=0.5$.