Decentralized optimization tackles linked constraints for faster results
Decentralized Optimization with Cross-Coupled Mixed Affine Constraints
Machine Learning
Summary
This paper looks at how to solve optimization problems spread across many computers that share information with each other. The challenge is that certain types of constraints connect the data in complicated ways, which makes the problem harder to solve efficiently. The authors find a geometric measure called the Friedrichs angle that explains why some problems are inherently tougher. They design a faster method that takes this complexity into account and prove it is as good as possible in some cases. Tests show the method performs as predicted based on the problem’s geometry and network setup.
What this means in practice
- •For distributed machine learning teams: Improve coordination algorithms where models must satisfy complex interdependent constraints across nodes.
- •For networked control engineers: Design control policies that optimize performance under tightly coupled restrictions shared across multiple devices.
Authors
Ewsey Obzherin, Ilya Khomchenko, Natalia Shelegeda, Nhat Trung Nguyen, Demyan Yarmoshik, Alexander Rogozin, Alexander Gasnikov
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.