A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features
This addresses distributed optimization challenges in machine learning and engineering, such as regression over distributed features, with incremental novelty as it claims to be the first linearly convergent decentralized algorithm for this specific problem class.
The paper tackles the problem of multi-agent optimization with composite objectives involving smooth local functions and a convex non-smooth coupling function, proposing a proximal primal-dual algorithm that achieves linear convergence to the optimal solution under strong convexity conditions.
This work studies multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) function coupling all agents. This scenario arises in many machine learning and engineering applications, such as regression over distributed features and resource allocation. We reformulate this problem into an equivalent saddle-point problem, which is amenable to decentralized solutions. We then propose a proximal primal-dual algorithm and establish its linear convergence to the optimal solution when the local functions are strongly-convex. To our knowledge, this is the first linearly convergent decentralized algorithm for multi-agent sharing problems with a general convex (possibly non-smooth) coupling function.