Complexity of Decentralized Optimization with Mixed Affine Constraints

This paper considers decentralized optimization of convex functions with mixed affine equality constraints involving both local and global variables. Constraints on global variables may vary across different nodes in the network, while local variables are subject to coupled and node-specific constraints. Such problem formulations arise in machine learning applications, including federated learning and multi-task learning, as well as in resource allocation and distributed control. We analyze this problem under smooth and non-smooth assumptions, considering both strongly convex and general convex objective functions. Our main contribution is an optimal algorithm for the smooth, strongly convex regime, whose convergence rate matches established lower complexity bounds. We further provide optimal and near-optimal methods for the remaining cases.

This paper studies how multiple networked agents can solve optimization problems together without relying on a central coordinator. The problems include both private local variables and shared global variables, with constraints that may differ across agents. Such settings arise in federated learning, multi-task learning, resource allocation, and distributed control. The paper develops algorithms for several convex optimization cases and presents an optimal method for smooth, strongly convex problems, matching the best possible theoretical convergence rate.