期刊
OPTIMIZATION METHODS & SOFTWARE
卷 36, 期 1, 页码 171-210出版社
TAYLOR & FRANCIS LTD
DOI: 10.1080/10556788.2020.1750013
关键词
Distributed optimization; optimal rates; optimization over networks; convex optimization; primal-dual algorithms
类别
资金
- 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
This study examines dual-based algorithms for distributed convex optimization problems over networks, providing complexity bounds for different cases and proposing distributed algorithms with optimal rates. It focuses on minimizing admissible functions and dual friendly functions, as well as improving the dependency on the parameters of non-dual friendly functions. Numerical analysis of the proposed algorithms is also included.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据