On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization

Wenqing Hu; Chris Junchi Li; Xiang Zhou

doi:10.1109/BigData47090.2019.9005621

On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization

Wenqing Hu, Chris Junchi Li, Xiang Zhou

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

3 Citations (Scopus)

Abstract

We study the convergence behavior of a stochastic heavy-ball method with a small stepsize. Under a change of time scale, we approximate the discrete scheme by a stochastic differential equation that models small random perturbations of a coupled system of nonlinear oscillators. We rigorously show that the perturbed system converges to a local minimum in a logarithmic time. This indicates that for the diffusion process that approximates the stochastic heavy-ball method, it takes (up to a logarithmic factor) only a linear time of the square root of the inverse stepsize to escape from all saddle points. This results may suggest a fast convergence of its discrete-time counterpart. Our theoretical results are validated by numerical experiments.

Original language	English
Title of host publication	Proceedings - 2019 IEEE International Conference on Big Data
Editors	Chaitanya Baru, Jun Huan, Latifur Khan
Publisher	IEEE
Pages	94-104
ISBN (Print)	9781728108582
DOIs	https://doi.org/10.1109/BigData47090.2019.9005621
Publication status	Published - Dec 2019
Event	2019 IEEE International Conference on Big Data (Big Data 2019) - Los Angeles, United States Duration: 9 Dec 2019 → 12 Dec 2019

Publication series

Name	Proceedings - IEEE International Conference on Big Data, Big Data

Conference

Conference	2019 IEEE International Conference on Big Data (Big Data 2019)
Place	United States
City	Los Angeles
Period	9/12/19 → 12/12/19

Research Keywords

dissipative nonlinear oscillator
heavy-ball method
non-convex optimization
saddle point
small random perturbations of Hamiltonian systems

Access Output

10.1109/BigData47090.2019.9005621

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Hu, W., Li, C. J., & Zhou, X. (2019). On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization. In C. Baru, J. Huan, & L. Khan (Eds.), Proceedings - 2019 IEEE International Conference on Big Data (pp. 94-104). Article 9005621 (Proceedings - IEEE International Conference on Big Data, Big Data). IEEE. https://doi.org/10.1109/BigData47090.2019.9005621

@inproceedings{b4151dcb317646408acd2f1e3a066823,

title = "On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization",

abstract = "We study the convergence behavior of a stochastic heavy-ball method with a small stepsize. Under a change of time scale, we approximate the discrete scheme by a stochastic differential equation that models small random perturbations of a coupled system of nonlinear oscillators. We rigorously show that the perturbed system converges to a local minimum in a logarithmic time. This indicates that for the diffusion process that approximates the stochastic heavy-ball method, it takes (up to a logarithmic factor) only a linear time of the square root of the inverse stepsize to escape from all saddle points. This results may suggest a fast convergence of its discrete-time counterpart. Our theoretical results are validated by numerical experiments.",

keywords = "dissipative nonlinear oscillator, heavy-ball method, non-convex optimization, saddle point, small random perturbations of Hamiltonian systems",

author = "Wenqing Hu and Li, {Chris Junchi} and Xiang Zhou",

year = "2019",

month = dec,

doi = "10.1109/BigData47090.2019.9005621",

language = "English",

isbn = "9781728108582",

series = "Proceedings - IEEE International Conference on Big Data, Big Data",

publisher = "IEEE",

pages = "94--104",

editor = "Chaitanya Baru and Jun Huan and Latifur Khan",

booktitle = "Proceedings - 2019 IEEE International Conference on Big Data",

address = "United States",

note = "2019 IEEE International Conference on Big Data (Big Data 2019) ; Conference date: 09-12-2019 Through 12-12-2019",

}

Hu, W, Li, CJ & Zhou, X 2019, On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization. in C Baru, J Huan & L Khan (eds), Proceedings - 2019 IEEE International Conference on Big Data., 9005621, Proceedings - IEEE International Conference on Big Data, Big Data, IEEE, pp. 94-104, 2019 IEEE International Conference on Big Data (Big Data 2019), Los Angeles, California, United States, 9/12/19. https://doi.org/10.1109/BigData47090.2019.9005621

On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization. / Hu, Wenqing; Li, Chris Junchi; Zhou, Xiang.
Proceedings - 2019 IEEE International Conference on Big Data. ed. / Chaitanya Baru; Jun Huan; Latifur Khan. IEEE, 2019. p. 94-104 9005621 (Proceedings - IEEE International Conference on Big Data, Big Data).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization

AU - Hu, Wenqing

AU - Li, Chris Junchi

AU - Zhou, Xiang

PY - 2019/12

Y1 - 2019/12

N2 - We study the convergence behavior of a stochastic heavy-ball method with a small stepsize. Under a change of time scale, we approximate the discrete scheme by a stochastic differential equation that models small random perturbations of a coupled system of nonlinear oscillators. We rigorously show that the perturbed system converges to a local minimum in a logarithmic time. This indicates that for the diffusion process that approximates the stochastic heavy-ball method, it takes (up to a logarithmic factor) only a linear time of the square root of the inverse stepsize to escape from all saddle points. This results may suggest a fast convergence of its discrete-time counterpart. Our theoretical results are validated by numerical experiments.

AB - We study the convergence behavior of a stochastic heavy-ball method with a small stepsize. Under a change of time scale, we approximate the discrete scheme by a stochastic differential equation that models small random perturbations of a coupled system of nonlinear oscillators. We rigorously show that the perturbed system converges to a local minimum in a logarithmic time. This indicates that for the diffusion process that approximates the stochastic heavy-ball method, it takes (up to a logarithmic factor) only a linear time of the square root of the inverse stepsize to escape from all saddle points. This results may suggest a fast convergence of its discrete-time counterpart. Our theoretical results are validated by numerical experiments.

KW - dissipative nonlinear oscillator

KW - heavy-ball method

KW - non-convex optimization

KW - saddle point

KW - small random perturbations of Hamiltonian systems

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85081354533&origin=recordpage

U2 - 10.1109/BigData47090.2019.9005621

DO - 10.1109/BigData47090.2019.9005621

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781728108582

T3 - Proceedings - IEEE International Conference on Big Data, Big Data

SP - 94

EP - 104

BT - Proceedings - 2019 IEEE International Conference on Big Data

A2 - Baru, Chaitanya

A2 - Huan, Jun

A2 - Khan, Latifur

PB - IEEE

T2 - 2019 IEEE International Conference on Big Data (Big Data 2019)

Y2 - 9 December 2019 through 12 December 2019

ER -

On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this