GNSD: A Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization

Songtao Lu; Xinwei Zhang; Haoran Sun; Mingyi Hong

doi:10.1109/DSW.2019.8755807

GNSD: A Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization

Songtao Lu, Xinwei Zhang, Haoran Sun, Mingyi Hong

Electrical and Computer Engineering

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

63 Scopus citations

Abstract

In the era of big data, it is challenging to train a machine learning model on a single machine or over a distributed system with a central controller over a large-scale dataset. In this paper, we propose a gradient-tracking based nonconvex stochastic decentralized (GNSD) algorithm for solving nonconvex optimization problems, where the data is partitioned into multiple parts and processed by the local computational resource. Through exchanging the parameters at each node over a network, GNSD is able to find the first-order stationary points (FOSP) efficiently. From the theoretical analysis, it is guaranteed that the convergence rate of GNSD to FOSPs matches the well-known convergence rate \mathcal{O}\left( {1/\sqrt T } \right) of stochastic gradient descent by shrinking the step-size. Finally, we perform extensive numerical experiments on computational clusters to demonstrate the advantage of GNSD compared with other state-of-the-art methods.

Original language	English (US)
Title of host publication	2019 IEEE Data Science Workshop, DSW 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	315-321
Number of pages	7
ISBN (Electronic)	9781728107080
DOIs	https://doi.org/10.1109/DSW.2019.8755807
State	Published - Jun 2019
Event	2019 IEEE Data Science Workshop, DSW 2019 - Minneapolis, United States Duration: Jun 2 2019 → Jun 5 2019

Publication series

Name	2019 IEEE Data Science Workshop, DSW 2019 - Proceedings

Conference

Conference	2019 IEEE Data Science Workshop, DSW 2019
Country/Territory	United States
City	Minneapolis
Period	6/2/19 → 6/5/19

Bibliographical note

Funding Information:
†equal contribution. The authors of this paper have been supported by NSF grants CMMI-1727757, CCF-1526078, an AFOSR grant 15RT0767, and a Digital TechnologyInitiative Seed Grant from the Digital Technology Center at University of Minnesota.

Publisher Copyright:
© 2019 IEEE.

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Keywords

Stochastic
decentralized
gradient tracking
neural networks
nonconvex optimization

Publisher link

10.1109/DSW.2019.8755807

Find It

Find It at U of M Libraries

Cite this

Lu, S., Zhang, X., Sun, H., & Hong, M. (2019). GNSD: A Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization. In 2019 IEEE Data Science Workshop, DSW 2019 - Proceedings (pp. 315-321). Article 8755807 (2019 IEEE Data Science Workshop, DSW 2019 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DSW.2019.8755807

GNSD: A Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization. / Lu, Songtao; Zhang, Xinwei; Sun, Haoran et al.
2019 IEEE Data Science Workshop, DSW 2019 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2019. p. 315-321 8755807 (2019 IEEE Data Science Workshop, DSW 2019 - Proceedings).

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

Lu, S, Zhang, X, Sun, H & Hong, M 2019, GNSD: A Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization. in 2019 IEEE Data Science Workshop, DSW 2019 - Proceedings., 8755807, 2019 IEEE Data Science Workshop, DSW 2019 - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 315-321, 2019 IEEE Data Science Workshop, DSW 2019, Minneapolis, United States, 6/2/19. https://doi.org/10.1109/DSW.2019.8755807

@inproceedings{32515ff7c2fa4f949aeb2d731d65320e,

title = "GNSD: A Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization",

abstract = "In the era of big data, it is challenging to train a machine learning model on a single machine or over a distributed system with a central controller over a large-scale dataset. In this paper, we propose a gradient-tracking based nonconvex stochastic decentralized (GNSD) algorithm for solving nonconvex optimization problems, where the data is partitioned into multiple parts and processed by the local computational resource. Through exchanging the parameters at each node over a network, GNSD is able to find the first-order stationary points (FOSP) efficiently. From the theoretical analysis, it is guaranteed that the convergence rate of GNSD to FOSPs matches the well-known convergence rate \mathcal{O}\left( {1/\sqrt T } \right) of stochastic gradient descent by shrinking the step-size. Finally, we perform extensive numerical experiments on computational clusters to demonstrate the advantage of GNSD compared with other state-of-the-art methods.",

keywords = "Stochastic, decentralized, gradient tracking, neural networks, nonconvex optimization",

author = "Songtao Lu and Xinwei Zhang and Haoran Sun and Mingyi Hong",

note = "Funding Information: †equal contribution. The authors of this paper have been supported by NSF grants CMMI-1727757, CCF-1526078, an AFOSR grant 15RT0767, and a Digital TechnologyInitiative Seed Grant from the Digital Technology Center at University of Minnesota. Publisher Copyright: {\textcopyright} 2019 IEEE. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 2019 IEEE Data Science Workshop, DSW 2019 ; Conference date: 02-06-2019 Through 05-06-2019",

year = "2019",

month = jun,

doi = "10.1109/DSW.2019.8755807",

language = "English (US)",

series = "2019 IEEE Data Science Workshop, DSW 2019 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "315--321",

booktitle = "2019 IEEE Data Science Workshop, DSW 2019 - Proceedings",

}

TY - GEN

T1 - GNSD

T2 - 2019 IEEE Data Science Workshop, DSW 2019

AU - Lu, Songtao

AU - Zhang, Xinwei

AU - Sun, Haoran

AU - Hong, Mingyi

N1 - Funding Information: †equal contribution. The authors of this paper have been supported by NSF grants CMMI-1727757, CCF-1526078, an AFOSR grant 15RT0767, and a Digital TechnologyInitiative Seed Grant from the Digital Technology Center at University of Minnesota. Publisher Copyright: © 2019 IEEE. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2019/6

Y1 - 2019/6

N2 - In the era of big data, it is challenging to train a machine learning model on a single machine or over a distributed system with a central controller over a large-scale dataset. In this paper, we propose a gradient-tracking based nonconvex stochastic decentralized (GNSD) algorithm for solving nonconvex optimization problems, where the data is partitioned into multiple parts and processed by the local computational resource. Through exchanging the parameters at each node over a network, GNSD is able to find the first-order stationary points (FOSP) efficiently. From the theoretical analysis, it is guaranteed that the convergence rate of GNSD to FOSPs matches the well-known convergence rate \mathcal{O}\left( {1/\sqrt T } \right) of stochastic gradient descent by shrinking the step-size. Finally, we perform extensive numerical experiments on computational clusters to demonstrate the advantage of GNSD compared with other state-of-the-art methods.

AB - In the era of big data, it is challenging to train a machine learning model on a single machine or over a distributed system with a central controller over a large-scale dataset. In this paper, we propose a gradient-tracking based nonconvex stochastic decentralized (GNSD) algorithm for solving nonconvex optimization problems, where the data is partitioned into multiple parts and processed by the local computational resource. Through exchanging the parameters at each node over a network, GNSD is able to find the first-order stationary points (FOSP) efficiently. From the theoretical analysis, it is guaranteed that the convergence rate of GNSD to FOSPs matches the well-known convergence rate \mathcal{O}\left( {1/\sqrt T } \right) of stochastic gradient descent by shrinking the step-size. Finally, we perform extensive numerical experiments on computational clusters to demonstrate the advantage of GNSD compared with other state-of-the-art methods.

KW - Stochastic

KW - decentralized

KW - gradient tracking

KW - neural networks

KW - nonconvex optimization

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

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

U2 - 10.1109/DSW.2019.8755807

DO - 10.1109/DSW.2019.8755807

M3 - Conference contribution

AN - SCOPUS:85069450639

T3 - 2019 IEEE Data Science Workshop, DSW 2019 - Proceedings

SP - 315

EP - 321

BT - 2019 IEEE Data Science Workshop, DSW 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 2 June 2019 through 5 June 2019

ER -

GNSD: A Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization

Abstract

Publication series

Conference

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this