Distributed Saddle Point Problems for Strongly Concave-Convex Functions
Distributed Saddle Point Problems for Strongly Concave-Convex Functions
复制标题
DOI：
10.1109/tsipn.2023.3317807
复制
发表时间：
2022-02
影响因子：
3.2
通讯作者：
Muhammad I. Qureshi;U. Khan
中科院分区：
文献类型：
--
作者：
Muhammad I. Qureshi;U. Khan
在本文中，我们提出了 GT-GDA，一种分布式优化方法来解决以下形式的鞍点问题： ${\min _{\mathbf {x}} \max _{\mathbf {y}} \lbrace F(\mathbf x,\mathbf y) :=G(\mathbf x) + \langle \mathbf y, \overline{P} \mathbf x \rangle - H(\mathbf y) \rbrace }$，其中函数 $G(\cdot)$、$H(\cdot)$ 和耦合矩阵 $\overline{P}$ 分布在强连接的节点网络上。 GT-GDA是一种一阶方法，利用梯度跟踪来消除节点间数据分布异构造成的不相似性。在最一般的形式中，GT-GDA 包括对局部耦合矩阵的共识，以实现最佳（唯一）鞍点，但代价是增加通信。为了避免这种情况，我们提出了一种更有效的变体 GT-GDA-Lite，它不会产生额外的通信，并分析其在各种场景下的收敛性。我们证明，当 $G$ 光滑且凸、$H$ 光滑且强凸且全局耦合矩阵 $\overline{P}$ 具有满列秩时，GT-GDA 线性收敛到唯一鞍点解。我们进一步描述了 GT-GDA 表现出与网络拓扑无关的收敛行为的机制。接下来我们展示 GT-GDA-Lite 对唯一鞍点周围误差的线性收敛，当耦合成本 ${\langle \mathbf y, \overline{P} \mathbf x \rangle }$ 对于所有节点都是公共的，或者当 $G$ 和 $H$ 是二次的时，该鞍点趋于零。数值实验说明了 GT-GDA 和 GT-GDA-Lite 对于多种应用的收敛特性和重要性。
In this article, we propose GT-GDA, a distributed optimization method to solve saddle point problems of the form: ${\min _{\mathbf {x}} \max _{\mathbf {y}} \lbrace F(\mathbf x,\mathbf y) :=G(\mathbf x) + \langle \mathbf y, \overline{P} \mathbf x \rangle - H(\mathbf y) \rbrace }$, where the functions $G(\cdot)$, $H(\cdot)$, and the coupling matrix $\overline{P}$ are distributed over a strongly connected network of nodes. GT-GDA is a first-order method that uses gradient tracking to eliminate the dissimilarity caused by heterogeneous data distribution among the nodes. In the most general form, GT-GDA includes a consensus over the local coupling matrices to achieve the optimal (unique) saddle point, however, at the expense of increased communication. To avoid this, we propose a more efficient variant GT-GDA-Lite that does not incur additional communication and analyze its convergence in various scenarios. We show that GT-GDA converges linearly to the unique saddle point solution when $G$ is smooth and convex, $H$ is smooth and strongly convex, and the global coupling matrix $\overline{P}$ has full column rank. We further characterize the regime under which GT-GDA exhibits a network topology-independent convergence behavior. We next show the linear convergence of GT-GDA-Lite to an error around the unique saddle point, which goes to zero when the coupling cost ${\langle \mathbf y, \overline{P} \mathbf x \rangle }$ is common to all nodes, or when $G$ and $H$ are quadratic. Numerical experiments illustrate the convergence properties and importance of GT-GDA and GT-GDA-Lite for several applications.