- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This work focused on decentralized optimization with local and shared variables presented by two groups of affine equality constraints. It used the angle between the constraints to measure the difficulty to solve the two groups together. This work proposed Cross-APAPC as an accelerated algorithm and provided convergence guarantees for it.
Critical strengths
- The constraints are explained by geometric meanings: It use the angle between two constraint directions to describe the difficulty and it helps a lot to explain.
Critical weaknesses
- The theoretical presentation is a little bit difficult to follow: The main text introduces many operators and condition numbers, while the convergence guarantees are mainly presented as asymptotic complexity bounds. A direct error bound may make the results easier to understand.
- The proof is also a little bit hard to follow: In the appendix, many proof steps use expression such as and , which is not clear.
Questions for authors
I would like to ask: Would you make the mathematical expressions and proofs clearer?
Response to Reviewer XWxf (Direct Error Bound and Proof Clarity)
Dear Reviewer XWxf,
We are grateful for your observation that the Friedrichs cosine provides a geometric explanation for the difficulty of solving the two constraint channels jointly. In response to your comments on clarity, we put the definitions and assumptions before the results and added experiments that illustrate what the bounds count.
Sharp conditioning for fixed channels. Section 3 explains how the angle between the row spaces controls the normalized stack. Theorem 3.1 gives the best condition number attainable by separate preprocessing, including for intersecting row spaces.
Explicit error bounds. Theorem 4.1 gives ∣wk−w⋆∣≤RE(1+c/κ)−k/2 for zero-dual initialization. Here RE2 bounds the initial primal–dual energy and c>0 is numerical. Theorem 4.2 uses a primal radius R and a supplied multiplier budget. After the warm start, k further steps give
∣wk−w⋆∣≤20/3,R(1+24κ1)−k/2.
Theorem 5.1 removes the extra accuracy logarithm in the smooth-convex regime. Algorithm 2 makes the schedule explicit. Appendix D.2 bounds the two transition energies by 178R2 and 80R2, and Appendix D.3 derives the finite-chain tail used in the lower bounds.
What changes when we rewrite the problem? We take up the open question of Yarmoshik et al. (ICML 2026), §6. For consistent shared equalities, Proposition B.1 constructs a curvature-preserving rewrite with χ×=1. Appendix B.4 compares the original formulation, local elimination, and the shared basis at equal accuracy in the original variables. The comparison charges setup and recovery. At 128 agents with mostly free-direction coupling, the shared basis reduces modeled rounds by a factor of 8.7 versus local elimination on both covtype and epsilon, but raises total traffic on epsilon. A better cross factor can come with a higher setup cost. Choosing a globally optimal rewrite remains open.
The new logistic and graph experiments illustrate why Table 1 counts gradients, affine directions, and neighbor rounds separately. In the path/ring sweep, the median paired outer-iteration ratio was one on each dataset, while disagreement products changed.
Your feedback helped us make the main results easier to find and verify. If the revision resolves your concerns, we would appreciate your considering a higher rating.