Decentralized Optimization with Cross-Coupled Mixed Affine Constraints

Ewsey Obzherin; Ilya Khomchenko; Natalia Shelegeda; Nhat Trung Nguyen; Demyan Yarmoshik; Alexander Rogozin; Alexander Gasnikov

math.OCSep 26, 2026

Decentralized Optimization with Cross-Coupled Mixed Affine Constraints

Authors: Ewsey Obzherin, Ilya Khomchenko, Natalia Shelegeda, Nhat Trung Nguyen, Demyan Yarmoshik, Alexander Rogozin, Alexander Gasnikov

Organizations: Moscow Independent Research Institute of Artificial Intelligence · FusionBrain Lab · Innopolis University

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.

Figures & tables

Work	regime/model	$N_{\nabla}$	affine work (native model)	$N_{\rm comm}$
Salim et al. (2022)	smooth SC, $Kx=b$	$O(T_{\rm sc})$	$O(\chi_{K}T_{\rm sc})$	–
Yarmoshik et al. (2025)	smooth SC, coupled	$O(T_{\rm sc})$	$O(\Lambda_{\rm cpl}T_{\rm sc})$	$O(\Lambda_{\rm cpl}\sqrt{\kappa_{W}}T_{\rm sc})$
Yarmoshik et al. (2026)	smooth SC, mixed	$O(T_{\rm sc})$	$O(\Lambda_{\rm mix}T_{\rm sc})$	$O(\Gamma_{\rm mix}T_{\rm sc})$
This work	smooth SC, CC-MAC	$\mathbf{O(T_{\rm sc})}$	$\mathbf{O(\chi_{\times}T_{\rm sc})}$	$\mathbf{O(\chi_{\times}\sqrt{\kappa_{W}}T_{\rm sc})}$
Yarmoshik et al. (2026)	smooth convex, mixed	$O(T_{\rm cvx}L_{\varepsilon})$	$O(\Lambda_{\rm mix}T_{\rm cvx}L_{\varepsilon})$	$O(\Gamma_{\rm mix}T_{\rm cvx}L_{\varepsilon})$
This work	smooth convex, CC-MAC	$\mathbf{\Theta(T_{\rm cvx})}$	$\mathbf{\Theta(\chi_{\times}T_{\rm cvx})}$	$\mathbf{\Theta(\chi_{\times}\sqrt{\kappa_{W}}T_{\rm cvx})}$

Table 1: Closest first-order comparison in the cited works’ reported resource models. Affine and communication units are model/realization dependent: predecessor rows use their native accounting, whereas our affine entries count normalized stack products and Appendix L expands our solver into raw matrix products and physical rounds. A dash means that the cited work does not give the corresponding decentralized result in that regime.

Figure 1: Full-data a9a on H100 over five feature-partition seeds. Thin traces are individual seeds, shaded regions and dotted boundaries are the empirical min–max interval, and the thick line is the median. Panels use gradient evaluations, native affine products, and physical neighbor rounds; the horizontal dotted line is the

10^{-6}

target.

Figure 2: Full-data mushrooms under the same five-seed protocol and interval convention as Figure 1 . Cross-APAPC and joint APAPC differ only in separate versus joint channel normalization; the remaining curves are common-interface CUDA ports/adaptations detailed in Appendix A .

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
Problem data and canonical reformulation
$n$ , $i$	Number of agents and agent index, $i\in\{1,\ldots,n\}$ .
$x_{i}$ , $z$ , $z_{i}$	Local variable, shared variable, and local copy of the shared variable; $x_{i}\in\mathbb{R}^{d_{i}}$ and $z,z_{i}\in\mathbb{R}^{q}$ .
$d_{i},q,m,p_{i},r_{i}$	Local/shared dimensions, coupled-equality dimension, and row counts of $C_{i},D_{i}$ .
$A_{i},B_{i},b_{i}$ ; $C_{i},c_{i}$ ; $D_{i},e_{i}$	Coupled-equality, local-affine, and shared-variable affine data in ( CC-MAC ).
$\bm{x},\bm{z}$ ; $A,B,C,D$ ; $\bm{b},\bm{c},\bm{e}$	Stacked variables, block-diagonal matrix stacks, and stacked right-hand sides.

Appendix

Table 2: Global and recurring notation.

Figure 3: Controlled full-data scaling on a9a and w8a . Left: normalized affine calls versus the realized cross factor

\chi_{\times}

. Right: physical neighbor rounds versus

\chi_{\times}\sqrt{\kappa_{W}}

. Fits use the nonplateau regime

\chi_{\times}\geq 1.5

; both slopes are statistically consistent with the unit exponents predicted by the theory.

Dataset	$N$	$d$	agents	grad.	norm. aff.	raw aff.	comm.	max err.
a9a	32,561	123	8	145	580	29 000	1 160 [1 160, 1 595]	$3.9\times 10^{-5}$
a9a	32,561	123	16	145	580	29 000	1 740 [1 740, 3 045]	$3.9\times 10^{-5}$
mushrooms	8,124	112	8	110	440	22 000	880 [880, 1 210]	$8.1\times 10^{-5}$
mushrooms	8,124	112	16	145	580	29 000	1 740 [1 740, 3 045]	$5.6\times 10^{-5}$
w8a	49,749	300	8	145	580	29 000	1 160 [1 160, 1 595]	$8.3\times 10^{-5}$
w8a	49,749	300	16	220	880	44 000	2 640 [2 640, 4 620]	$7.9\times 10^{-5}$

Appendix

Table 3: Full-data Cross-APAPC robustness on H100. Brackets denote

[Q_{1},Q_{3}]

; the final column is the worst terminal relative squared error among the corresponding runs.

Figure 4: Full-data a8a with

16

agents on H100. Thin curves are the two feature-partition seeds; the shaded band and dotted boundaries show their empirical min–max range, and the thick curve is the median guide. All six methods reach the

10^{-6}

target. With only two seeds, the band is a descriptive seed interval, not a confidence interval.

Decentralized Optimization

Decentralized optimization develops methods for agents connected by networks to solve shared problems using local data and peer-to-peer communication.

See all 60 papers

Adaptive Decentralized Composite Optimization via Three-Operator Splitting
Feb 19, 2026Xiaokai Chen, Ilya Kuruzov, Gesualdo ScutariDecentralized Optimization Nonsmooth Convex Optimization
Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN 47906 USA
Near-Optimal Decentralized Stochastic Convex Optimization over Networks
Jun 3, 2026Nitai Kluger, Amit Attia, Tomer KorenStochastic Optimization Convergence Accelerated Gradient Methods
Blavatnik School of Computer Science, Tel Aviv University · Google Research Tel Aviv
Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization
Jul 2, 2026Siyuan Zhang, Nachuan Xiao, Xin LiuStochastic Optimization Nonconvex Optimization

Feb 19, 2026J/K move · Enter open · S save

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari

Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN 47906 USA

Decentralized Optimization Nonsmooth Convex Optimization

Open paper AskPDF arXiv

The paper studies decentralized optimization over networks, where agents minimize a sum of {\it locally} smooth (strongly) convex losses and plus a nonsmooth convex extended value term. We propose decentralized methods wherein agents {\it adaptively} adjust their stepsize via local backtracking procedures coupled with lightweight min-consensus protocols. Our design stems from a three-operator splitting factorization applied to an equivalent reformulation of the problem. The reformulation is endowed with a new BCV preconditioning metric (Bertsekas-O'Connor-Vandenberghe), which enables efficient decentralized implementation and local stepsize adjustments. We establish robust convergence guarantees. Under mere convexity, the proposed methods converge with a sublinear rate. Under strong convexity of the sum-function, and assuming the nonsmooth component is partly smooth, we further prove linear convergence. Numerical experiments corroborate the theory and highlight the effectiveness of the proposed adaptive stepsize strategy.

Abstract

Decentralized Optimization

Explore similar work

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

Near-Optimal Decentralized Stochastic Convex Optimization over Networks

Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization