2017/12/01 by César A. Uribe, Soomin Lee, Uribe, César A. +5 · 3 citations
Computer Science · Engineering · #Computational Complexity (cs.CC) #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (stat.ML) #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1712.00232
openalex publication_date 2017/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the optimal convergence rate for distributed convex optimization problems in networks. We model the communication restrictions imposed by the network as a set of affine constraints and provide optimal complexity bounds for four different setups, namely: the function F(\xb) \triangleq ∑i=1mfi(\xb) is strongly convex and smooth, either strongly convex or smooth or just convex. Our results show that Nesterov's accelerated gradient descent on the dual problem can be executed in a distributed manner and obtains the same optimal rates as in the centralized version of the problem (up to constant or logarithmic factors) with an additional cost related to the spectral gap of the interaction matrix. Finally, we discuss some extensions to the proposed setup such as proximal friendly functions, time-varying graphs, improvement of the condition numbers.