mlsanityData to 7 Oct 2026

Decentralized Optimization with Cross-Coupled Mixed Affine Constraints

arXiv 2609.33021 ↗First posted 26 Sep 2026math.OC cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

27 of 38 references.

References · 27

  1. 2018A Reductions Approach to Fair Classificationcited by 585
  2. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  3. 2020Think Locally, Act Globally: Federated Learning with Local and Global Representationscited by 322
  4. 2020Federated Learning of a Mixture of Global and Local Modelscited by 208
  5. 2017Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryptioncited by 174
  6. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  7. 2022Decentralized Training of Foundation Models in Heterogeneous Environmentscited by 87
  8. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  9. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  10. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  11. 2017Communication-Efficient Algorithms for Decentralized and Stochastic Optimizationcited by 42
  12. 2018Optimal Algorithms for Non-Smooth Distributed Optimization in Networkscited by 41
15 more
  1. 2021BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learningcited by 16
  2. 2021An Optimal Algorithm for Strongly Convex Minimization under Affine Constraintscited by 8
  3. 2016Accelerated gradient sliding for structured convex optimizationcited by 7
  4. 2024On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithmscited by 6
  5. 2019Tracking-ADMM for Distributed Constraint-Coupled Optimizationcited by 5
  6. 2020Recent theoretical advances in decentralized distributed convex optimizationcited by 5
  7. 2017Constraint Coupled Distributed Optimization: a Relaxation and Duality Approachcited by 3
  8. 2024Decentralized Optimization with Coupled Constraintscited by 2
  9. 2022Decentralized Strongly-Convex Optimization with Affine Constraints: Primal and Dual Approachescited by 1
  10. 2023Decentralized optimization with affine constraints over time-varying networkscited by 1
  11. 2023Decentralized Proximal Method of Multipliers for Convex Optimization with Coupled Constraintscited by 1
  12. 2026Decentralized Optimization with Mixed Affine Constraintscited by 1
  13. 2026Optimality in Decentralized Optimization under Bandwidth Constraintscited by 1
  14. 2026A Nesterov-Accelerated Primal-Dual Splitting Algorithm for Convex Nonsmooth Optimizationcited by 1
  15. 2026Sliding Methods for H"older-Smooth Convex--Concave Minimax Optimization with Bilinear Couplingcited by 1

Built on by

Not cited yet.