A dual approach for optimal algorithms in distributed optimization over networks

作     者：Uribe, Cesar A. Lee, Soomin Gasnikov, Alexander Nedic, Angelia 

作者机构：MIT Lab Informat & Decis Syst 77 Massachusetts Ave Cambridge MA 02139 USA MIT Inst Data Syst & Soc 77 Massachusetts Ave Cambridge MA 02139 USA Yahoo Res Sunnyvale CA USA Moscow Inst Phys & Technol Dept Math Fdn Control Dolgoprudnyi Russia Inst Informat Transmiss Dolgoprudnyi Russia Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ USA 

出 版 物：《OPTIMIZATION METHODS & SOFTWARE》 (最优化方法与软件)

年 卷 期：2021年第36卷第1期

页      面：171-210页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 

基　　金：National Science Foundation [CPS 15-44953, CCF-1717391] RFBR [18-29-03071, 19-31-51001] Ministry of Science andHigher Education of the Russian Federation Yahoo! Research Faculty Engagement Program 

主　　题：Distributed optimization optimal rates optimization over networks convex optimization primal-dual algorithms 

摘      要：We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum of functions over in a network. We provide complexity bounds for four different cases, namely: each function is strongly convex and smooth, each function is either strongly convex or smooth, and when it is convex but neither strongly convex nor smooth. Our approach is based on the dual of an appropriately formulated primal problem, which includes a graph that models the communication restrictions. We propose distributed algorithms that achieve the same optimal rates as their centralized counterparts (up to constant and logarithmic factors), with an additional optimal cost related to the spectral properties of the network. Initially, we focus on functions for which we can explicitly minimize its Legendre-Fenchel conjugate, i.e. admissible or dual friendly functions. Then, we study distributed optimization algorithms for non-dual friendly functions, as well as a method to improve the dependency on the parameters of the functions involved. Numerical analysis of the proposed algorithms is also provided.