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

Haoran Sun, Mingyi Hong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationConference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Pages38-42
Number of pages5
ISBN (Electronic)9781538692189
DOIs
StatePublished - Feb 19 2019
Event52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 - Pacific Grove, United States
Duration: Oct 28 2018Oct 31 2018

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
Volume2018-October
ISSN (Print)1058-6393

Conference

Conference52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
CountryUnited States
CityPacific Grove
Period10/28/1810/31/18

Bibliographical note

Funding Information:
This work was supported in part by the National Science Foundation under Grants CMMI-1727757

Funding Information:
H. Sun and M. Hong are with the Department of Electrical and Computer Engineering (ECE), University of Minnesota, Minneapolis, MN 55414, USA. Email: {sun00111,mhong}@umn.edu This work was supported in part by the National Science Foundation under Grants CMMI-1727757, and in part by the Air Force Office of Scientific Research under Grant 15RT0767.

Publisher Copyright:
© 2018 IEEE.

Fingerprint Dive into the research topics of 'Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms'. Together they form a unique fingerprint.

Cite this