# Decentralized Optimization with Cross-Coupled Mixed Affine Constraints

arXiv: https://arxiv.org/abs/2609.33021 · HTML: https://mlsanity.com/paper/2609.33021/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 38 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Builds on (most cited first, 27 of 27)

- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Think Locally, Act Globally: Federated Learning with Local and Global Representations](https://mlsanity.com/paper/2001.01523/) (2020)
- [Federated Learning of a Mixture of Global and Local Models](https://mlsanity.com/paper/2002.05516/) (2020)
- [Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption](https://mlsanity.com/paper/1711.10677/) (2017)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Decentralized Training of Foundation Models in Heterogeneous Environments](https://mlsanity.com/paper/2206.01288/) (2022)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning](https://mlsanity.com/paper/2111.04287/) (2021)
- [An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints](https://mlsanity.com/paper/2102.11079/) (2021)
- [Accelerated gradient sliding for structured convex optimization](https://mlsanity.com/paper/1609.04905/) (2016)
- [On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/2411.14601/) (2024)
- [Tracking-ADMM for Distributed Constraint-Coupled Optimization](https://mlsanity.com/paper/1907.10860/) (2019)
- [Recent theoretical advances in decentralized distributed convex optimization](https://mlsanity.com/paper/2011.13259/) (2020)
- [Constraint Coupled Distributed Optimization: a Relaxation and Duality Approach](https://mlsanity.com/paper/1711.09221/) (2017)
- [Decentralized Optimization with Coupled Constraints](https://mlsanity.com/paper/2407.02020/) (2024)
- [Decentralized Strongly-Convex Optimization with Affine Constraints: Primal and Dual Approaches](https://mlsanity.com/paper/2207.04555/) (2022)
- [Decentralized optimization with affine constraints over time-varying networks](https://mlsanity.com/paper/2307.01655/) (2023)
- [Decentralized Proximal Method of Multipliers for Convex Optimization with Coupled Constraints](https://mlsanity.com/paper/2310.15596/) (2023)
- [Decentralized Optimization with Mixed Affine Constraints](https://mlsanity.com/paper/2602.04479/) (2026)
- [Optimality in Decentralized Optimization under Bandwidth Constraints](https://mlsanity.com/paper/2603.20735/) (2026)
- [A Nesterov-Accelerated Primal-Dual Splitting Algorithm for Convex Nonsmooth Optimization](https://mlsanity.com/paper/2604.09245/) (2026)
- [Sliding Methods for H"older-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling](https://mlsanity.com/paper/2608.03846/) (2026)

## Abstract (arXiv)

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.