Decentralized Non-Convex Learning With Linearly Coupled Constraints: Algorithm Designs and Application to Vertical Learning Problem

Motivated by the need for decentralized learning, this paper aims at designing a distributed algorithm for solving non-convex problems with general linear constraints over a multi-agent network. In the considered problem, each agent owns some local information and a local variable for jointly minimizing a cost function, but local variables are coupled by linear constraints. Most of the existing methods for such problems are only applicable for convex problems or problems with specific linear constraints. There still lacks a distributed algorithm for solving such problems with general linear constraints under the nonconvex setting. To tackle this problem, we propose a new algorithm, called prox anal dual consensus (PDC) algorithm, which combines a proximal technique and a dual consensus method. We show that under certain conditions the proposed PDC algorithm can generate an epsilon-Karush-Kuhn-Tucker solution in O (1/epsilon) iterations, achieving the lower bound for distributed non-convex problems up to a constant. Numerical results are presented to demonstrate the good performance of the proposed algorithms for solving two vertical learning problems in machine learning over a multi-agent network.

Automated summary

Motivated by the need for decentralized learning, this paper proposes a distributed algorithm for solving non-convex problems with general linear constraints over a multi-agent network. The proposed prox anal dual consensus (PDC) algorithm combines proximal technique and dual consensus method. Numerical results show the good performance of the proposed algorithms for solving two vertical learning problems in machine learning over a multi-agent network.