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

Haoran Sun; Mingyi Hong

doi:10.1109/ACSSC.2018.8645279

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

Haoran Sun, Mingyi Hong

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 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 language	English (US)
Title of host publication	Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	38-42
Number of pages	5
ISBN (Electronic)	9781538692189
DOIs	https://doi.org/10.1109/ACSSC.2018.8645279
State	Published - Jul 2 2018
Event	52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 - Pacific Grove, United States Duration: Oct 28 2018 → Oct 31 2018

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
Volume	2018-October
ISSN (Print)	1058-6393

Conference

Conference	52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018
Country/Territory	United States
City	Pacific Grove
Period	10/28/18 → 10/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.

Publisher link

10.1109/ACSSC.2018.8645279

Find It

Find It at U of M Libraries

Cite this

Sun, H., & Hong, M. (2018). Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms. In M. B. Matthews (Ed.), Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 (pp. 38-42). Article 8645279 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2018.8645279

Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms. / Sun, Haoran; Hong, Mingyi.
Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018. ed. / Michael B. Matthews. IEEE Computer Society, 2018. p. 38-42 8645279 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2018-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sun, H & Hong, M 2018, Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms. in MB Matthews (ed.), Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018., 8645279, Conference Record - Asilomar Conference on Signals, Systems and Computers, vol. 2018-October, IEEE Computer Society, pp. 38-42, 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018, Pacific Grove, United States, 10/28/18. https://doi.org/10.1109/ACSSC.2018.8645279

Sun H, Hong M. Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms. In Matthews MB, editor, Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018. IEEE Computer Society. 2018. p. 38-42. 8645279. (Conference Record - Asilomar Conference on Signals, Systems and Computers). doi: 10.1109/ACSSC.2018.8645279

Sun, Haoran ; Hong, Mingyi. / Distributed Non-Convex First-Order optimization and Information Processing : Lower Complexity Bounds and Rate Optimal Algorithms. Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018. editor / Michael B. Matthews. IEEE Computer Society, 2018. pp. 38-42 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

@inproceedings{38ff6aa4ce4e408ea375a0265aad47f2,

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

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.",

author = "Haoran Sun and Mingyi Hong",

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: {\textcopyright} 2018 IEEE.; 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018 ; Conference date: 28-10-2018 Through 31-10-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1109/ACSSC.2018.8645279",

language = "English (US)",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE Computer Society",

pages = "38--42",

editor = "Matthews, {Michael B.}",

booktitle = "Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018",

}

TY - GEN

T1 - Distributed Non-Convex First-Order optimization and Information Processing

T2 - 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018

AU - Sun, Haoran

AU - Hong, Mingyi

N1 - 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.

PY - 2018/7/2

Y1 - 2018/7/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85062956351&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062956351&partnerID=8YFLogxK

U2 - 10.1109/ACSSC.2018.8645279

DO - 10.1109/ACSSC.2018.8645279

M3 - Conference contribution

AN - SCOPUS:85062956351

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 38

EP - 42

BT - Conference Record of the 52nd Asilomar Conference on Signals, Systems and Computers, ACSSC 2018

A2 - Matthews, Michael B.

PB - IEEE Computer Society

Y2 - 28 October 2018 through 31 October 2018

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this