Complexity of Decentralized Optimization with Mixed Affine Constraints
Demyan Yarmoshik, Nhat Trung Nguyen, Alexander Rogozin, Alexander Gasnikov · 2026
Read Complexity of Decentralized Optimization with Mixed Affine Constraints by Demyan Yarmoshik, Nhat Trung Nguyen, Alexander Rogozin, Alexander Gasnikov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-04479.txt.
Description
Demyan Yarmoshik's 2026 paper, written with 3 co-authors, studies optimization problems spread across a network of computers. Each node holds part of the problem. Some limits apply to local variables, while others couple variables shared across nodes or differ between nodes.
Such setups appear in federated learning, resource allocation, and distributed control. The authors analyze smooth and non-smooth cases, for both strongly convex and general convex functions. Convex here means the problem has a bowl-like shape with no false low points. Their main result is an optimal algorithm for the smooth, strongly convex case. Its speed matches known lower bounds. They also give near-optimal methods for the remaining cases.
Catalog record
| CREATOR | Demyan Yarmoshik, Nhat Trung Nguyen, Alexander Rogozin, Alexander Gasnikov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 120 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-04479