acceptodds
Under review as a conference paper at ICLR 2027

Communication-Efficient Distributed Coordinate-Descent Methods

Abstract

We propose a distributed block-coordinate method, where coordinates are partitioned across clients and communication is the main bottleneck. Each client performs multiple local updates between communication rounds to approximately solve a local problem, using Gradient Descent or an accelerated version as local solvers for efficiently minimizing the gradient norm of the local problem. We introduce cross-coupling , which measures how far is from a fully separable function, with when is fully separable. For nonconvex but coordinate-wise convex functions and for convex functions, we establish communication complexity bounds proportional to . Under a Polyak–Łojasiewicz condition, our method converges linearly. We compare our method with baselines and explain when it is more communication efficient. We also develop an accelerated version; for convex objectives, it achieves a communication complexity bound proportional to . Alongside communication complexity, we bound local computation for each problem class. We also introduce a line search method that automatically estimates the constant in an efficient way resulting in strong practical performance. Finally, we show that the proposed accelerated method is optimal (in terms of communication complexity) by establishing a lower bound valid for any first-order oracle distributed coordinate-descent method.

Primary area:
optimization
Keywords:
coordinate descent, distributed coordinate descent, parallel coordinate descent, communication-efficient distributed optimization, optimal communication complexity, model-parallel, accelerated proximal methods

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6PBDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies minimizing an objective ff in the distributed setting where communication is the main bottleneck. The authors propose a distributed block-coordinate descent method, where coordinates are partitioned across clients and each client can only query the partial gradient of its own block.

The main new object is the cross-coupling constant MM, the smallest constant with ∑i∣∇if(x+P−ih)−∇if(x)∣2≤M2∣h∣2\sum_i\\|\nabla_i f(x+P_{-i}h) - \nabla_i f(x)\\|^2 \leq M^2\\|h\\|^2. It is 00 for separable ff and gives a separable upper bound on ff (Eq. 4). Minimizing this bound yields the main algorithm, PiCS, where each client inexactly solves a proximal subproblem on its block with the other blocks frozen, with regularization λ≥2M\lambda \geq 2M or a doubling line search.

The paper proves O(M/ε2)O(M/\varepsilon^2) rounds for ε\varepsilon-stationarity for coordinate-wise convex ff, O(MD02/ε)O(MD_0^2/\varepsilon) rounds for convex ff, a linear rate under PL condition, O(R0M/ε)O(R_0\sqrt{M/\varepsilon}) rounds for the accelerated A-PiCS, and a matching Ω(RM/ε)\Omega(R\sqrt{M/\varepsilon}) lower bound for two clients and linear-span procedures.

Local GD and AGD solvers are analyzed. Bounds are compared with GD, CD variants, Hydra, DBCD and FedBCD. Experiments use logistic regression on LIBSVM with two workers, plus appendix runs on line search, sparse data and a ResNet34 without the proximal term.

Critical strengths
  1. From what I checked, the theoretical analysis is complete and correct. One descent inequality gives the nonconvex, convex and PL rates. A standard Nesterov potential gives the accelerated rate
  2. A computable structural measure. M is exact for quadratics, at most L for convex smooth f, and has a clean GLM bound. It gives a clear statement of when local steps should help.
Critical weaknesses
  1. Limited novelty beyond the cross-coupling constant: the proposed method, PiCS, builds on a standard idea, with the main novelty lying in the cross-coupling constant MM and its role in the convergence guarantees. At each round, every client approximately solves a Jacobi block proximal-point subproblem. The multiple local steps are simply the inner solver for this inexact proximal step, rather than a distinct algorithmic contribution. The local oracle complexities reported in Table 1 support this interpretation. The accelerated variant also appears to follow a standard estimate-sequence argument. In particular, inequality (8) has the form of a standard inequality for a proximal step. A-PiCS can therefore be viewed as an accelerated inexact proximal-point method using a block-Jacobi step as its proximal oracle. Overall, the main contribution appears to be the introduction of MM, its Hessian-based characterization, and the resulting explicit convergence rates in terms of MM. The proofs themselves seem largely standard.

  2. Baseline selection and comparison: the parameter choices in Table 1 make most of the baselines reduce to gradient descent. For example for PCDM, nice sampling with τ=n\tau=n updates every block in each round, recovering GD. The DBCD and Hydra configurations likewise reduce to full-step GD. The claimed improvement largely comes down to comparing MM with the smoothness-related constants appearing in these GD baselines. GCD and RCDM seem to update only one block per round and are not designed for the setting considered here. Moreover, the comparisons do not include an accelerated baseline, making it difficult to assess the benefits of the proposed method relative to existing accelerated approaches.

Minor issues:

The paper contains numerous typos and grammatical errors, e.g. "Here, Here", "We we", "an then", "lustrating", "propse", "statisfied", "is know ,we choose". There are also some section-labeling inconsistencies, e.g., Appendices G and H are both titled "Proofs for Section 7", although Appendix H proves the comparisons in Section 8, and Appendix C.8 is titled "Proof of Section 3".

Questions for authors
  1. PiCS looks like a Jacobi block proximal-point method with an inexact local solver. What does it add beyond known results? If the contribution is the MM-parametrized rates only, the abstract and introduction should say so.
  2. Proposition F.7 is stated without proof or citation. Could the authors add it?
  3. Does anything guarantee that the line-search λt\lambda_t tracks MM? The abstract says the line search automatically estimates the constant MM, but Section 4 only shows λt≤4M\lambda_t \leq 4M and Appendix I says λt/2\lambda_t/2 should not be read as an estimate of MM. Which is intended? Is there any lower bound on accepted λt\lambda_t, which matters for the local-step counts in Section 7?
2 comments

Thank you for your comments. We address them below.

Q1. Contribution beyond Jacobi methods

This comment seems closely related to Reviewer 3uXX's Q1(a), which points to the paper [1], and we assume you have a similar concern as well. We were unaware of [1] and essentially reinvented parts of it. However, we provide explicit convergence rates, extend beyond quadratics, develop an accelerated version, and propose efficient local solvers with complexity guarantees. Please see our response to Reviewer 3uXX's Q1(a) for details.

[1] Deori et al. “Regularized Jacobi Iteration for Decentralized Convex Quadratic Optimization With Separable Constraints.” 2019.

Q3. What the line search guarantees

Thank you for pointing out this ambiguity. The intended meaning was that the line search automatically selects the regularization coefficient without knowing MM, while preserving nearly the same communication complexity guarantees. We establish only an upper bound on the accepted λt\lambda_t. This upper bound is what our communication analysis requires. In fact, if the line search often selects λt\lambda_t much smaller than MM, this is a favorable situation for the algorithm since it automatically accelerates in terms of communication rounds.

However, you are right that small λt\lambda_t can increase local computation, as discussed in Section 7. There is therefore a trade-off: λt\lambda_t should be small to reduce communications, but not too small, so that the regularizer makes each local subproblem easy to solve. Since communication complexity is our primary metric, we allow more local work in exchange for fewer communications. Overall, we do not guarantee a lower bound on λt\lambda_t proportional to MM, but keep it at least as large as the initial value λ^0\hat{\lambda}_0. Developing a more general adaptive strategy to balance communication and local complexities is an interesting direction for future work.

We have clarified the abstract and discussed this trade-off in Section 6, and removed the two appendix figures and associated discussion to avoid ambiguity.

W1. Limited novelty

We agree that the main contribution of our paper is the introduction of the cross-coupling constant MM. However, we believe saying that everything else is of limited novelty would be an oversimplification. The contribution is not simply introducing a new constant, but identifying a useful structural property that admits interesting examples, has a natural Hessian-based characterization, and connects well with existing optimization techniques. In particular, it needs to ensure the key inequalities (7) and (8) required for establishing efficiency guarantees for both basic and accelerated methods. Finding a definition that simultaneously has these properties is, in our opinion, already a nontrivial contribution.

We also view the use of standard optimization tools and ideas as a strength of our paper rather than a limitation. Our goal is not to introduce entirely new optimization machinery, but to show how existing, well-established, techniques can be naturally combined under the proposed cross-coupling assumption to obtain efficient methods with explicit efficiency guarantees. This makes the resulting framework relatively simple and transparent, while demonstrating the usefulness of the proposed assumption. Furthermore, even though the individual components are standard, properly connecting them requires some effort. In particular, we need to verify that all the assumptions required by these components are satisfied, even when several of them are used together, and that the resulting algorithms can be efficiently implemented in the distributed coordinate setting considered in our paper.

W2(a). Baseline choices

In this work, blocks are divided among clients, and all clients can work in parallel at each communication round. We chose PCDM, DBCD, and Hydra as closely related baselines and adapted them to this setting. For PCDM, full sampling (τ=n\tau=n) gives the most favorable communication bound among its sampling choices; choosing fewer blocks does not improve this bound. We agree that GCD and RCDM update only one block per round and were not designed to exploit this distributed setting. As discussed in the introduction, we include them as standard baselines, rather than methods designed specifically for our communication model.

We agree that an accelerated baseline could be useful, but would not change the overall picture: its complexity bounds still depend on local smoothness constants (LiL_i), whereas our accelerated method’s communication bound depends on cross-coupling MM. Thus, the comparison still favors our method when MM is small relative to those constants. We have clarified this in the footnote of Table 1.

Citations, typos, and appendix labels

Thank you. We added the citation for Proposition F.7, now Proposition E.2 in the revised version, and corrected the reported typos and appendix labels.

Thank you for the response and the revisions. My main concern remains the limited novelty. I will raise my score, but I would not object to rejection.

Reviewer_3uXXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper develops two algorithms for distributed coordinate descent and analyzes their communication complexity under a sufficient separability condition controlled by a constant MM. Iteration complexities depend on this constant.

Critical strengths
  1. The paper considers the important and interesting problem of optimization with distributed coordinates across workers. The writing is decent.
  2. The combination consisted by Assumption 3.1 for separability depending on MM, (6) for the gradients, line search to ensure (7) and complexity upper and lower bounds depending on MM seems to be new and non-trivial.
Critical weaknesses
  1. There seems to be important missing references from the paper, please see the questions section for details. The reader might understand that many of the ingredients of the main approach are new, but it seems that all have close precedents. The combination of them seems to be indeed new though.
  2. The validity of the new combination of assumptions is not discussed properly. For instance, matrix factorization is used as a canonical example of Assumption 4.1, but I think it does not satisfy Assumption 3.1. It is unclear to me whether there are interesting functions that satisfy the current combination of assumptions, but not the ones already treated in the literature.
  3. The writeup has many typos and seems to have been finished in rush at certain points.
Questions for authors
  1. The paper "Regularized Jacobi Iteration for Decentralized Convex Quadratic Optimization With Separable Constraints" seems to be using a similar separability condition as Assumption 3.1 but for quadratics. The paper "An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and its Implications to Second-Order Methods" seems to develop an algorithm very similar to your Algorithm 2. Can you comment? Also, I think there should be many papers bounding directly the norm of the odd-diagonal Hessian, instead of using the bound of Assumption 3.1, but this makes them certainly relevant.
  2. Can you design an example of a function that satisfies all the assumptions in the paper and is not included in the assumptions of DBCD and Hydra?

Overall, I have a positive stance for the paper, but if the relationship with related work and validity of assumptions is not cleared up, I cannot recommend acceptance.

1 comment

Thank you for your comments. We address them below.

Q1(a). Regularized Jacobi

Thank you for mentioning this important reference. We read it carefully, and indeed our method has similarities with the regularized Jacobi scheme of [1]. For quadratic functions, we reinvented the same update scheme and a similar assumption on the off-diagonal part of the Hessian without being aware of their work. However, our work can be seen as an extension of their approach: we cover not only quadratic functions but also more general smooth functions, and we provide explicit convergence rates rather than simply proving that the algorithm converges asymptotically. In addition, we provide an accelerated version of the method and a lower bound on communication. Another difference is that our method allows inexact local solves (Algorithm 1, line 5). We also study how to solve these local problems using different local solvers and derive total complexity bounds that account for these local steps. We added the reference [1] and clarified its relation to our work in the Introduction and Sections 3 and 4. [1] Deori et al. “Regularized Jacobi Iteration for Decentralized Convex Quadratic Optimization With Separable Constraints.”

Q1(b). A-HPE and acceleration

Indeed, our Algorithm 2 is closely related to the A-HPE framework [3]. In fact, we were aware of this work but unfortunately forgot to mention it. Thank you for pointing this out. We have now corrected this and added reference [3], along with clarifications on its relation to our algorithm. Please see the text following Algorithm 2 in the revised version. Below we provide a detailed reply. The A-HPE framework can be seen as a generalization of Nesterov's accelerated gradient method in the form introduced in [2]. The basic idea is that Algorithm (4.9) from [2] is actually a generic scheme which can be used to accelerate any "basic method" on the function ff as long as one step of this "basic method", y↦T≡Tλ(y)y \mapsto T \equiv T_{\lambda}(y), ensures a certain inequality: \langle \nabla f(T), y - T \rangle \geq \frac{1}{2 \lambda} \| \nabla f(T) \|^2. \tag{*}

This inequality has the interpretation that TT is an approximate solution of the proximal-point subproblem min⁡x[fλ(x)≡f(x)+λ2∥x−y∥2],\min_x \Bigl[ f_{\lambda}(x) \equiv f(x) + \frac{\lambda}{2} \| x - y \|^2 \Bigr],

in the sense that (∗)(*) is equivalent to \| \nabla f_{\lambda}(T) \| \leq \lambda \| y - T \|. \tag{**}

This is exactly the inequality used in [3]. In our case, the "basic method" is our Algorithm 1 for which inequality (∗)(*) is indeed satisfied; see Lemma 5.1 in our paper (20λ20\lambda instead of 2λ2\lambda is just a change of notation). As such, our accelerated Algorithm 2 can be seen as both an extension of Nesterov's gradient method from [2] and a particular case of the A-HPE framework [3]. However, we personally prefer to present it as the former because [2] historically precedes [3], and the A-HPE framework is mostly used for second- and higher-order methods, with parts of the analysis in [3] redundant for first-order methods. In contrast, the analysis in [2] is more concise, less technical, and translates directly to other first-order methods such as our "basic method" (Algorithm 1). [2] Yurii Nesterov. “Gradient methods for minimizing composite functions.” [3] Monteiro and Svaiter. “An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order Methods.”

Q2. DBCD and Hydra’s assumptions

At a high level, all the methods (our method, DBCD and Hydra) provide convergence guarantees for the same class of functions: convex functions with Lipschitz gradient. However, the efficiency guarantees for the methods are expressed in terms of different constants parameterizing this function class: our method uses the cross-coupling constant MM and block Lipschitz constants LiL_i, DBCD uses LiL_i and the function's "separability degree" ω\omega, while Hydra uses the function's smoothness constant LL and ω\omega. For convex functions, any of these assumptions implies Lipschitz smoothness of the objective (bounded Hessian) and vice versa.

Nevertheless, in terms of communication complexity, our method is never worse than the other methods, and can be significantly more efficient in favorable situations. Consider a fully separable function f(x)=∑ifi(xi)f(x)=\sum_i f_i(x_i) with LiL_i-smooth components. Then M=0M=0, and our method requires only one communication round. In contrast, DBCD and Hydra perform only one gradient step per block per round, requiring as many rounds as the gradient steps needed for the “worst” block. Our method performs multiple local steps per round, making its communication complexity proportional to MM, which can be close to zero for nearly separable problems.

Matrix factorization, typos, and presentation

Thank you. The matrix-factorization example does not satisfy Assumption 3. We removed it and corrected the reported typos in the revised version.

Reviewer_o6S8OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a communication-efficient distributed coordinate descent method, where the coordinate blocks are partitioned across the clients. It introduces a cross-coupling MM to measure the degree of interaction among the coordinate blocks and then proposes PiCS, which allows the clients to perform multiple local updates between communication rounds by approximately solving the regularized local subproblems. Specifically, a larger MM indicates a stronger dependence among coordinate blocks and therefore requires stronger proximal regularization to constrain local updates, while also corresponding to a higher communication complexity. This paper establishes the communication complexity bounds that scale with MM for different classes of objectives, and further develops an accelerated variant that matches the derived communication lower bound up to constants. An adaptive line-search strategy is introduced to handle the case where MM is unknown, and experiments evaluate the practical performance of the proposed methods.

Critical strengths
  1. This paper introduces a cross-coupling measure MM to characterize the degree of interaction among coordinate blocks, and develops the proposed PiCS framework consistently around this quantity.

  2. For the quadratic objectives, this paper establishes an exact connection between the cross-coupling measure MM and the spectral norm of the block off-diagonal part of the Hessian. And it further proves that MM-dependent communication complexity guarantees for several objective classes, including the coordinate-wise convex, convex and PL objectives. The proposed accelerated PiCS achieves a communication complexity that matches the derived lower bound up to constant factors.

Critical weaknesses

The main experiments focus primarily on the LIBSVM classification problems, while the ResNet34 experiment does not include the explicit proximal term. Consequently, a stronger empirical evidence on the realistic large-scale neural-network or the distributed learning tasks would further demonstrate the practical relevance of the proposed framework.

Questions for authors
  1. Different coordinate blocks may exhibit substantially different degrees of coupling. Can the authors discuss why a global MM is preferable to the block-specific measures MiM_i or pairwise measures MijM_{ij}?

  2. More generally, would it be possible to extend PiCS to exploit the heterogeneous coupling structures, allowing different blocks to use the different proximal regularization strengths or local computation/communication schedules?

1 comment

Thank you for taking the time to review our work. We address your comments below.

Q1. Global versus block-specific coupling

Different coordinate blocks may exhibit substantially different degrees of coupling. Can the authors discuss why a global MM is preferable to the block-specific measures MiM_i or pairwise measures MijM_{ij}?

Q2. Exploiting heterogeneous coupling

More generally, would it be possible to extend PiCS to exploit the heterogeneous coupling structures, allowing different blocks to use the different proximal regularization strengths or local computation/communication schedules?

Thank you for your suggestion. We agree that using pairwise coupling can generally be beneficial and see this as an interesting direction for future research.

One approach to address this could be replacing the standard Euclidean norm which is currently used in our method with a more general Euclidean norm induced by a matrix WW, which would better take into account heterogeneous coupling degrees. This would change both the coupling constant MM and the distance DD in the convergence bound of our method: they will now be measured with respect to the WW-norm. By choosing WW properly, we could significantly improve the efficiency of our method. For example, in the convex setting, the communication complexity would be something like O(MWDW2ϵ)O(\frac{M_W D_W^2}{\epsilon}) which could be significantly smaller than the current O(MD2ϵ)O(\frac{M D^2}{\epsilon}), where MM and DD are measured with respect to the standard Euclidean norm.

We decided, however, not to do it in the current paper for a couple of reasons. First, we wanted to keep the presentation as simple as possible to not distract the reader from many other important concepts with extra technical details. Second, using a WW-induced norm would raise the natural question of how to select WW, which is difficult to answer in full generality and requires extra assumptions on the problem's structure. On the one hand, WW should incorporate as much information as possible about the interaction of different components with each other. But, on the other hand, it should remain relatively simple so that each "local" subproblem could be solved efficiently.

Thank you again for raising this point. We have added a paragraph discussing this in the Conclusion section.

W1. Practical evidence and the ResNet34 experiment

The main experiments focus primarily on the LIBSVM classification problems, while the ResNet34 experiment does not include the explicit proximal term. Consequently, a stronger empirical evidence on the realistic large-scale neural-network or the distributed learning tasks would further demonstrate the practical relevance of the proposed framework.

Thank you for pointing this out. The proximal term was not included in the older version of the paper, and we forgot to update this experiment. This is now fixed: we have updated the ResNet34 experiment to include the proximal term in the revised paper. Thank you for this suggestion.

Comments on the paper

1 comment

We thank all the reviewers for their time and effort spent on reviewing our work and for their valuable comments and suggestions. We have prepared a revised version of the paper addressing the reviewers' concerns and incorporating several additional improvements to the clarity of presentation. Please see the updated version of the paper where we have highlighted all changes relative to the original submission in blue. We provide detailed responses to each reviewer's questions and comments separately. In addition, we would like to briefly summarize a few points raised by reviewers that we believe deserve particular attention.

  1. Relation to regularized Jacobi methods. Our method has similarities with the regularized Jacobi scheme of Deori et al. [1]. For quadratic functions, we reinvented the same update scheme and a similar assumption on the off-diagonal part of the Hessian without being aware of their work. However, our work extends beyond quadratic functions, provides explicit convergence rates rather than asymptotic convergence alone, and includes an accelerated version and a communication lower bound. We also allow inexact local solves and analyze their computational complexity.
  2. Novelty and the use of known methods. The contribution is not simply introducing a new constant, but identifying a useful structural property that admits interesting examples, has a natural Hessian-based characterization, and connects well with existing optimization techniques. We view the use of standard optimization tools as a strength rather than a limitation: they can be naturally combined under the proposed cross-coupling assumption to obtain efficient methods with explicit efficiency guarantees.
  3. Practical relevance. We agree that further practical applications would be interesting to explore. The focus of this paper is to establish theoretical foundations, with guarantees on communication complexity and local computation. We view these results as a first step toward developing and understanding practical variants of the method. Extending the experiments to larger-scale neural networks and distributed learning tasks would be a valuable next step.

[1] Luca Deori, Kostas Margellos, and Maria Prandini. “Regularized Jacobi Iteration for Decentralized Convex Quadratic Optimization With Separable Constraints.” IEEE Transactions on Control Systems Technology, 27(4):1636–1644, 2019.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.