- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies minimizing an objective 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 , the smallest constant with . It is for separable and gives a separable upper bound on (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 or a doubling line search.
The paper proves rounds for -stationarity for coordinate-wise convex , rounds for convex , a linear rate under PL condition, rounds for the accelerated A-PiCS, and a matching 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
- 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
- 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
-
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 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 , its Hessian-based characterization, and the resulting explicit convergence rates in terms of . The proofs themselves seem largely standard.
-
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 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 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
- 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 -parametrized rates only, the abstract and introduction should say so.
- Proposition F.7 is stated without proof or citation. Could the authors add it?
- Does anything guarantee that the line-search tracks ? The abstract says the line search automatically estimates the constant , but Section 4 only shows and Appendix I says should not be read as an estimate of . Which is intended? Is there any lower bound on accepted , which matters for the local-step counts in Section 7?
2 comments
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.
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 M, while preserving nearly the same communication complexity guarantees. We establish only an upper bound on the accepted λt. This upper bound is what our communication analysis requires. In fact, if the line search often selects λt much smaller than M, this is a favorable situation for the algorithm since it automatically accelerates in terms of communication rounds.
However, you are right that small λt can increase local computation, as discussed in Section 7. There is therefore a trade-off: λ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 proportional to M, but keep it at least as large as the initial value λ^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 M. 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) 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 (Li), whereas our accelerated method’s communication bound depends on cross-coupling M. Thus, the comparison still favors our method when M 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.