Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms

By Haoran Sun, Mingyi Hong. 2018

72 citations recorded by the source corpus.

Consider a distributed non-convex optimization problem, in which a number of agents connected by a network $\mathcal{G}$ collectively optimize a sum of smooth and non-convex local objective functions. We address the following important question: For a class of unconstrained problems, if only local gradient information is available, what is the fastest rate that distributed algorithms can achieve, and how to achieve those rates. We perform a lower bound analysis for a class of first-order distributed methods which only utilizes local gradient information. We show that in the worst-case it takes at least $\mathcal{O}(1/\sqrt{\xi(\mathcal{G})}\times L/\epsilon)$ iterations to achieve certain $\epsilon$-solution, where $\xi(\mathcal{G})$ represents the spectrum gap of the graph Laplacian matrix, and L is some Lipschitz constant. Further, for a general problem class, we propose rate-optimal methods whose rates match the lower bounds (up to a polylog factor). To the best of our knowledge, this is the first time that lower rate bounds and optimal methods have been developed for distributed non-convex optimization problems.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, background): “Recently, there have been some works which study non-convex decentralized consensus optimization and establish convergence to a stationary point (Zeng and Yin, 2018; Hong et al., 2017, 2018; Sun and Hong, 2018; Scutari et al., 2017; Scutari and Sun, 2018; Jiang et al., 2017; Lian et al., 2017a).”
Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “On a complete graph, the communication complexity of Walkman is O ( ln(2) n ) , whereas, according to [42] , the better communication complexity between D-GPDA and xFILTER is O ( n(2) ) .”
FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (2020, methodology): “1 The proof is related to techniques developed in classical and recent works that characterize lower bounds for first-order methods in centralized [20, 21] and decentralized [22, 23] settings.”