TY - GEN
T1 - A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks
AU - Uribe, Cesar A.
AU - Lee, Soomin
AU - Gasnikov, Alexander
AU - Nedic, Angelia
N1 - Funding Information: The work of A. Nedićand C.A. Uribe is supported by the National Science Foundation under grant no. CPS 15-44953. The work of A. Gasnikov was supported by RFBR 18-29-03071 mk and MD-1320.2018.1. Publisher Copyright: © 2020 IEEE.
PY - 2020/2/2
Y1 - 2020/2/2
N2 - We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum i = 1m fi(z) of functions over in a network. We provide complexity bounds for four different cases, namely: each function fi 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.
AB - We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum i = 1m fi(z) of functions over in a network. We provide complexity bounds for four different cases, namely: each function fi 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.
KW - Distributed optimization
KW - convex optimization
KW - optimal rates
KW - optimization over networks
KW - primal-dual algorithms
UR - http://www.scopus.com/inward/record.url?scp=85097334328&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097334328&partnerID=8YFLogxK
U2 - 10.1109/ITA50056.2020.9244951
DO - 10.1109/ITA50056.2020.9244951
M3 - Conference contribution
T3 - 2020 Information Theory and Applications Workshop, ITA 2020
BT - 2020 Information Theory and Applications Workshop, ITA 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2020 Information Theory and Applications Workshop, ITA 2020
Y2 - 2 February 2020 through 7 February 2020
ER -