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

Feb 19, 2026

Adaptive Decentralized Composite Optimization via Three-Operator Splitting

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.

Xiaokai Chen, Ilya Kuruzov, Gesualdo Scutari

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

Decentralized Optimization Nonsmooth Convex Optimization

Ask PDF

Jun 3, 2026

Near-Optimal Decentralized Stochastic Convex Optimization over Networks

We study decentralized stochastic smooth convex optimization, where

M

workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of

N

gradient samples while still preserving the centralized

O(1/\sqrt N)

statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to

\smash{M\lesssim \sqrtρ\,N^{3/4}}

workers, where

ρ

is the spectral gap of the gossip network, improving the best prior maximal scaling of

\smash{M\lesssim ρ\sqrt N}

. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.

Nitai Kluger, Amit Attia, Tomer Koren

Blavatnik School of Computer Science, Tel Aviv University · Google Research Tel Aviv

Stochastic Optimization Convergence Accelerated Gradient Methods Decentralized Optimization

Ask PDF

Jul 2, 2026

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

In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods.

Siyuan Zhang, Nachuan Xiao, Xin Liu

Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Nonsmooth Convex Optimization Decentralized Optimization

Ask PDF

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