acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Optimization with Cross-Coupled Mixed Affine Constraints

Abstract

We study decentralized optimization with cross-coupled mixed affine constraints, where local and shared variables interact through two affine channels. We show that the intrinsic difficulty of combining separately well-conditioned channels is governed by their Friedrichs angle. This geometry induces a cross-coupling factor that cannot be removed by channelwise preconditioning and governs the additional affine-oracle and communication complexity. We develop an accelerated decentralized method with matching minimax guarantees in the smooth strongly convex regime and extend the framework to smooth and nonsmooth convex objectives. Experiments confirm the predicted dependence on cross-channel geometry and network conditioning.

Primary area:
optimization
Keywords:
decentralized optimization, affine constraints, constrained optimization, Friedrichs angle, preconditioning, communication complexity, minimax complexity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_XWxfOpenReview ↗
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
  1. 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
  1. 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.
  2. The proof is also a little bit hard to follow: In the appendix, many proof steps use expression such as O(..)O(..) and Ω(..)\Omega(..), which is not clear.
Questions for authors

I would like to ask: Would you make the mathematical expressions and proofs clearer?

1 comment
AuthorsOpenReview ↗

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\\|w^k-w^\star\\|\le R_E(1+c/\sqrt{\kappa})^{-k/2} for zero-dual initialization. Here RE2R_E^2 bounds the initial primal–dual energy and c>0c>0 is numerical. Theorem 4.2 uses a primal radius RR and a supplied multiplier budget. After the warm start, kk further steps give

∣wk−w⋆∣≤20/3,R(1+124κ)−k/2.\\|w^k-w^\star\\|\le \sqrt{20/3}\\,R\left(1+\frac{1}{24\sqrt{\kappa}}\right)^{-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 178R2178R^2 and 80R280R^2, 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\chi_\times=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.

Reviewer_21weOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies decentralized optimization with cross-coupled mixed affine constraints (CC-MAC), where local and shared variables interact through two affine channels. For two pre-specified constraint channels, this paper uses their Friedrichs angle to describe the degree remaining after normalization, which leads to a cross-coupling factor that cannot be eliminated by preprocessing within each fixed channel. This factor is the key to analyzing the additional affine-oracle and communication complexity. Cross-APAPC combines existing accelerated methods for affine-constrained optimization, channel normalization, and neighbor-based communication implementations, analyzing gradient evaluations, affine operations, and communication costs. This paper also proposes a smooth convex method combined with feasibility repair, eliminating a multiplicative logarithmic factor related to target accuracy, and provides an extension for the nonsmooth case.

Critical strengths

Geometric analysis under a fixed channel decomposition is a meaningful theoretical contribution. It applies classical subspace angle theory to canonical CC-MAC channels, distinguishing between ill-conditioning within individual channels and interactions between channels, and clearly differentiating between exact and approximate coincidence. The optimal preprocessing result within channels (Theorem E.2, under nonredundancy assumptions), and its relationship with resource complexity help explain why individually well-conditioned channels may still be difficult to process after combination.

The smooth convex extension provides a contribution beyond the strongly convex construction. By retaining the dual state across continuation stages and applying polynomial feasibility repair, the proposed method removes an additional multiplicative logarithmic factor in the target accuracy while controlling both objective suboptimality and feasibility, extending the resource-based perspective beyond the strongly convex setting.

Critical weaknesses
  1. The applicability of strongly convex optimality and the significance of fixed-channel decomposition still require further clarification. Theorem 4.1 assumes an upper bound RER_E for the initial primal-dual energy, which is not equivalent to an upper bound for the initial distance from the primal iterate to a primal solution. Theorem 4.2 and the lower bound for physical communication in Appendix I retain the radius factor dependent on instance parameters and have not yet established a uniform product lower bound at a fixed absolute accuracy for problem classes where only the initial primal radius is controlled. The paper explicitly acknowledges these limitations, but they still restrict the completeness of the strongly convex optimality results. Can the upper and lower bounds of various resources be compared over the same instance class and initialization assumptions?

  2. The practical necessity of retaining the prescribed channel decomposition. In the VFL benchmark presented in this paper, changing the allocation coefficients satisfying ∑iαi=1\sum_i\alpha_i=1 does not alter the learning objective or feasible set, while the uniform choice αi=1/n\alpha_i=1/n makes the two canonical channels orthogonal, thus yielding χ×=1\chi_\times=1. Therefore, the current experiments mainly demonstrate the geometric effects under specified representations and do not fully explain why real-world learning tasks require retaining a large cross factor. The experiments with high cross-factors demonstrate the algorithm's sensitivity to the chosen representation, but do not prove that solving the original learning task necessarily involves this additional difficulty. The questions are: why must practical applications use a more poorly conditioned representation, or what costs are involved in replacing such a representation?

  3. The writing of the paper needs to be improved.

  • The attribution of technical contributions should be clarified more clearly. The core content of this paper comprises several layers: describing CC-MAC using two constraint channels; normalizing the channels separately and then characterizing the joint condition number through the angle between the channel subspaces; substituting the condition number into an affine constraint acceleration method and distinguishing between different resources; achieving decentralized computation through a localization construction; and designing continuation and feasibility repair in the smooth convex case. The novelty of these contents varies. The key questions to answer are: which difficulties are specific to CC-MAC, and which conclusions can be directly obtained from existing methods and classical geometric results?

  • The description of the contribution needs to be carefully considered. For example, the first contribution "A genuinely cross-coupled decentralized model," doesn't explain the practical significance or the reasons for proposing it. This paragraph reads more like an introduction to the work itself than a contribution.

  • Many sentences merely state the location of the conclusions in the appendix, without explaining their significance. For example, Section 3 relies on proposition C.2, lemma C.4, proposition D.3, and theorems D.1/E.2 within a very short exposition. This section defines the Friedrichs angle and the cross factor, gives the condition number identity in equation (7), and states the optimality under channelwise preprocessing. However, readers still need to search through several appendices to piece together the conditions for these conclusions and their inferences.

Questions for authors
  1. The relationship between the geometric results and those in Jha (2026) requires further clarification. This paper has already pointed out the differences between the two works in terms of problem structure and oracle, but Jha's Example 3.10 and Proposition 5.7 also directly discuss well-conditioned local constraints with joint geometric ill-conditioning, and the geometric factor that remains after optimizing the matrix representations while keeping each local set fixed. In the shared variable affine constraint subclass, k2k_2 in Appendix G of this paper coincides with the matrix conditioning parameter in Jha's Proposition 5.7. It will be better to compare the connections and differences between these results and Theorem E.2 of this paper, and clarify the new content of the geometric analysis itself.

  2. Appendix A states that the direct smooth-convex ϵ\epsilon-sweep and normalization ablation configurations are included in the artifact. The smooth convex method and related ablation options are already in the code. However, the submitted configs directory only contains two configuration files for strongly convex experiments. I suggest the authors can conduct additional experiments about the smooth convex cases.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 21we (Equivalent Reformulations and Distributed Costs)

Dear Reviewer 21we,

We appreciate your recognition of the fixed-channel geometry and the log-free smooth-convex extension. We revised Sections 1–3 and added controlled comparisons to clarify when the representation matters.

When does rewriting help? Yarmoshik et al. (ICML 2026), §6 asked whether rewriting can reduce complexity and proposed shared variables in aggregate equalities, which CC-MAC permits. Uniform VFL allocation gives χ×=1\chi_\times=1, so that sweep isolates sensitivity to the split. For consistent shared equalities, Proposition B.1 constructs an exact rewrite with χ×=1\chi_\times=1 while retaining the objective's curvature bounds. In a sparse chain, different eliminations preserve locality or make gradients dense. Radial dispatch motivates a physical split.

Appendix B.4 compares the original split and two rewrites in 120 runs on full covtype and epsilon with constructed calibration constraints, at equal original-variable accuracy. With 128 agents and mostly free-direction coupling, the shared basis cuts modeled rounds by a factor of 8.7 versus local elimination on both datasets. Including setup and recovery, traffic drops from 6.49M to 1.66M scalars on covtype and rises from 259.33M to 312.17M on epsilon, where setup alone costs 254.51M. Finding the best rewrite over all admissible representations remains open.

Theorem 4.1 assumes a primal–dual energy bound. Theorem 4.2 uses a warm start and matches gradient and normalized-affine orders on a common primal-radius class with a fixed multiplier budget and spectral certificates. The radius-explicit round result also assumes a graph-local realization and block-preserving access.

We credit classical angle geometry and Salim et al.’s APAPC. Jha’s Example 3.10 illustrates near-redundancy. In Proposition 5.7 the optimal shared-affine matrix ratio is the reciprocal of the set gap. For two virtual sets with nonzero disjoint normal spaces, the reciprocal gap minus one is χ×2\chi_\times^2. Theorem 3.1 characterizes sharp separate preprocessing of the fixed CC-MAC stack, including intersections, with resource bounds under matrix access.

Appendix F.5 and the replication supplement now cover 128 smooth-convex runs. Single regularization uses fewer operations at the tested checkpoints. Theorem 5.1 gives log-free worst-case accuracy dependence for continuation.

If the revision resolves these points, we would welcome an upward reassessment of the score.

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

The paper studies decentralized optimization with local variables xix_i and a shared variable zz coupled by one aggregate affine equality and by node-wise affine constraints (CC-MAC). The constraints reduce to two affine channels. After separate whitening the joint operator has condition number (1+cF)/(1−cF)(1+c_F)/(1-c_F), with cFc_F the Friedrichs cosine of the row spaces, and no channelwise preconditioning can do better. Cross-APAPC, APAPC with a Chebyshev correction on the normalized stack, uses O(κflog⁡)O(\sqrt{\kappa_f}\log) gradients and O(χ×κflog⁡)O(\chi_\times\sqrt{\kappa_f}\log) normalized affine calls, with matching lower bounds for both. A continuation scheme gives log-free smooth-convex bounds and a sliding variant covers the nonsmooth case. Experiments on vertically partitioned ridge regression (LIBSVM, 8 or 16 agents) show near-unit scaling exponents in χ×\chi_\times and, on a9a, about six times fewer normalized affine calls and neighbor rounds than joint normalization.

Critical strengths
  1. The separation between within-channel conditioning and the cross-channel factor is proven sharp on both sides. Theorem E.2 shows that χ×2\chi_\times^2 is the infimum of the stacked condition number over all channelwise preconditioners, and Theorem I.1 embeds a path instance into a one-agent CC-MAC problem to get a matching Ω(κfχ×log⁡(1/ε))\Omega(\sqrt{\kappa_f}\chi_\times\log(1/\varepsilon)) affine-call lower bound. This answers the question the paper poses, namely what separate normalization can and cannot buy.

  2. The scoping is explicit. The body states what is not proven (no uniform communication lower bound in the strongly convex case, no cross-dependent nonsmooth lower bound, no wall-clock claim), and the protocol in Appendix A (FP64, deterministic runs, every seed plotted, raw and normalized ledgers reported side by side) makes the numbers checkable. The log-free smooth-convex continuation in Appendix J, with its retained-dual warm start and weighted output repair, is a clean technical piece.

Critical weaknesses
  1. The abstract and the contribution list say the method has matching minimax guarantees in the smooth strongly convex regime. The body supports less. Theorem 4.2 states that the communication lower bound is radius-explicit and is not promoted to a uniform Ω(ΞΩlog⁡(1/ε))\Omega(\Xi\sqrt{\Omega}\log(1/\varepsilon)) equality at fixed absolute accuracy, and Theorem 4.1 is stated in terms of a supplied primal-dual energy RER_E while Appendix I says that the energy-controlled upper class of Theorem 4.1 and the primal-radius-normalized hard families are not silently identified. Table 1 lists the strongly convex row with OO and only the convex row with Θ\Theta, which agrees with the body but not with the abstract. Either prove the communication lower bound in the same radius convention as Theorem 4.1, or rewrite the abstract so it says what Theorem 4.2 gives: matching orders for gradients and normalized affine calls only.

  2. The controlled experiment does not test the theory independently of the implementation's own bookkeeping. In Figure 3 the Chebyshev degree is N=⌈λ+/λ−⌉N = \lceil\sqrt{\lambda_+/\lambda_-}\rceil with λ−=a/(3Ξ2)\lambda_- = a/(3\Xi^2) (Appendix H.2) and the graph-filter degree is set from κW\kappa_W (Appendix G), so the number of normalized affine calls per outer iteration is proportional to Ξ\Xi by construction. The slopes 0.99 and 0.98 mostly confirm that choice. The sweep could also show whether the outer iteration count stays flat in χ×\chi_\times, but I did not find that number for the sweep. Every benchmark is also ridge regression, so all gradients are affine, and only the Cross-versus-Joint pair is a controlled comparison. I would want the outer iteration count across the sweep, a run with NN below the certified degree, and one nonquadratic objective such as logistic regression.

Questions for authors
  1. What exactly is joint APAPC? Which polynomial degree does its joint normalizer use, how is its certificate obtained, and how is one normalized affine call counted for it, so that 800 versus 4750 on a9a is a like-for-like comparison?

  2. How were the spectral certificates of Assumption 1 and the bound Ξ≥χ×\Xi \ge \chi_\times obtained for the LIBSVM runs, and was any central computation on the full feature matrix involved, in particular for rcv1 with 47,236 features?

  3. In Theorem 5.1 the upper-bound constants grow with log⁡Bcont\log B_{\mathrm{cont}} through (91) and (95), and BcontB_{\mathrm{cont}} itself grows with Λˉ\bar{\Lambda}. Is the Θ\Theta to be read with Λˉ\bar{\Lambda}-dependent constants, and is anything claimed uniformly in Λˉ\bar{\Lambda}?

1 comment
AuthorsOpenReview ↗

Response to Reviewer fCyR (Complexity Guarantees and Experimental Validation)

Dear Reviewer fCyR,

Thank you for noting the sharp distinction between within-channel and cross-channel conditioning. We clarify the initialization assumptions and add the outer-convergence tests you suggested.

Optimality. Theorem 4.1 uses a primal–dual energy bound. The warm-started Theorem 4.2 matches bounds on a common class with primal radius RR, multiplier budget σ∣λ⋆∣≤c0LR\sigma\\|\lambda^\star\\|\le c_0LR, and the stated spectral certificates. Gradient and normalized-affine orders match. The radius-explicit physical-round result assumes the block-preserving local model and a supplied O(κW)O(\sqrt{\kappa_W})-round realization. The smooth-convex upper constants may depend on c0c_0 and the fixed certificate constants (Theorem 5.1, Appendix D.2).

Experiments. The earlier slopes partly reflect the prescribed degrees. Section 6 and Appendix F.4 now separate outer steps, affine work, and disagreement products. The 162-run sweep reports ridge and logistic outer counts across angles. The 720-run path/ring sweep had median paired outer-count ratio one per dataset. At fixed endpoints, halving the degree increased median outer steps by 18–26% and reduced forward feature products by 35–40%. All 54 six-method logistic runs reached the common target.

Joint and spectral setup. Raw Joint applies APAPC to the original stack (Appendix F.1). On a9a and mushrooms, the outer degrees are 10 for Raw Joint and 2 for Cross, whose first-channel normalizer has degree 24. A direction is one stack application or adjoint. At matched accuracy on a9a, Cross/Raw Joint use 1,600/9,500 directions, or 80,000/19,000 constituent channel actions. Identical normalized stacks and parameters give identical iterates (18 paired runs). LIBSVM endpoints used a heuristic 1.02-padded power estimate. For rcv1, we streamed sparse block products centrally without forming a dense Gram matrix. The allocation-derived cosine is a ceiling absent a rank check. Appendix F.1 gives a separate two-pass norm bound, and Appendix C charges certificate aggregation to setup.

Reformulation. Appendix B takes up the open question in Yarmoshik et al. (ICML 2026), §6. At matched original-variable accuracy, we compare the original split and two exact rewrites, counting setup, solve, and recovery.

If the revised guarantees and added comparisons address your concerns, we would be grateful if you would consider raising your rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.