Distributed Saddle-Point Problems Under Similarity
Distributed Saddle-Point Problems Under Similarity
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Aleksandr Beznosikov;G. Scutari;A. Rogozin;A. Gasnikov
中科院分区：
文献类型：
--
作者：
Aleksandr Beznosikov;G. Scutari;A. Rogozin;A. Gasnikov
我们研究了两种类型网络上的（强）凸-（强）凹鞍点问题（SPPs）的求解方法-主/工人（因此集中）架构和网格（因此分散）网络。由于统计数据相似或其他原因，假设每个节点的局部函数相似。我们为解决SPP的相当一般的一类算法建立了较低的复杂性界限。我们表明，在$\Omega\big(\Delta\cdot \delta/\mu\cdot \log (1/\varepsilon)\big)$轮通信中，在主/工人网络上实现了给定的次最优性$\epsilon>0$，其中$\delta>0$测量局部函数的相似性程度，$\mu$是它们的强凸性常数，$\Delta$是网络的直径。在网状网络上，较低的通信复杂性边界为$\Omega\big(1/{\sqrt{\rho}} \cdot {\delta}/{\mu}\cdot\log (1/\varepsilon)\big)$，其中$\rho$是用于相邻节点之间通信的八卦矩阵的（标准化）特征。然后，我们提出了匹配两种类型网络的下界的算法（直到对数因子）。我们评估了所提出的算法在鲁棒逻辑回归问题上的有效性。
We study solution methods for (strongly-)convex-(strongly)-concave Saddle-Point Problems (SPPs) over networks of two type - master/workers (thus centralized) architectures and meshed (thus decentralized) networks. The local functions at each node are assumed to be similar, due to statistical data similarity or otherwise. We establish lower complexity bounds for a fairly general class of algorithms solving the SPP. We show that a given suboptimality $\epsilon>0$ is achieved over master/workers networks in $\Omega\big(\Delta\cdot \delta/\mu\cdot \log (1/\varepsilon)\big)$ rounds of communications, where $\delta>0$ measures the degree of similarity of the local functions, $\mu$ is their strong convexity constant, and $\Delta$ is the diameter of the network. The lower communication complexity bound over meshed networks reads $\Omega\big(1/{\sqrt{\rho}} \cdot {\delta}/{\mu}\cdot\log (1/\varepsilon)\big)$, where $\rho$ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. We then propose algorithms matching the lower bounds over either types of networks (up to log-factors). We assess the effectiveness of the proposed algorithms on a robust logistic regression problem.