论文标题
菜肴：分布式混合原始二重式优化框架以利用系统异质性
DISH: A Distributed Hybrid Primal-Dual Optimization Framework to Utilize System Heterogeneity
论文作者
论文摘要
我们考虑在多代理网络上解决分布式共识优化问题。当前的分布式方法无法捕获代理本地计算能力之间的异质性。我们建议将DISH作为分布式混合二线算法框架来处理和利用系统异质性。具体而言，DISE允许那些具有较高计算能力或更便宜的计算成本的代理商在本地实施牛顿型更新，而其他代理可以采用更简单的梯度型更新。我们表明菜是一个通用框架，包括特殊情况，包括额外的，挖掘和ESOM-0。此外，当所有代理商都同时采用牛顿型更新时，DIS可以通过估计原始和双Hessians来近似牛顿的方法。从理论上讲，我们表明DISE可以达到线性（Q线性）的收敛速率，无论代理对梯度型和牛顿型更新的选择如何，都可以实现强大凸功能的确切最佳解决方案。最后，我们进行数值研究以证明菜肴在实践中的功效。据我们所知，Dish是第一种混合方法，它允许在一般网络拓扑下进行分布式共识优化的异质本地更新，并具有可证明的收敛性和利率保证。
We consider solving distributed consensus optimization problems over multi-agent networks. Current distributed methods fail to capture the heterogeneity among agents' local computation capacities. We propose DISH as a distributed hybrid primal-dual algorithmic framework to handle and utilize system heterogeneity. Specifically, DISH allows those agents with higher computational capabilities or cheaper computational costs to implement Newton-type updates locally, while other agents can adopt the much simpler gradient-type updates. We show that DISH is a general framework and includes EXTRA, DIGing, and ESOM-0 as special cases. Moreover, when all agents take both primal and dual Newton-type updates, DISH approximates Newton's method by estimating both primal and dual Hessians. Theoretically, we show that DISH achieves a linear (Q-linear) convergence rate to the exact optimal solution for strongly convex functions, regardless of agents' choices of gradient-type and Newton-type updates. Finally, we perform numerical studies to demonstrate the efficacy of DISH in practice. To the best of our knowledge, DISH is the first hybrid method allowing heterogeneous local updates for distributed consensus optimization under general network topology with provable convergence and rate guarantees.
