Analytical convergence regions of accelerated gradient descent in nonconvex optimization under Regularity Condition

Xiong，Huaqing1; Chi，Yuejie2; Hu，Bin3; Zhang，Wei4

2020-03-01

10.1016/j.automatica.2019.108715

AUTOMATICA   影响因子和分区

0005-1098

1873-2836

There is a growing interest in using robust control theory to analyze and design optimization and machine learning algorithms. This paper studies a class of nonconvex optimization problems whose cost functions satisfy the so-called Regularity Condition (RC). Empirical studies show that accelerated gradient descent (AGD) algorithms (e.g. Nesterov's acceleration and Heavy-ball) with proper initializations often work well in practice. However, the convergence of such AGD algorithms is largely unknown in the literature. The main contribution of this paper is the analytical characterization of the convergence regions of AGD under RC via robust control tools. Since such optimization problems arise frequently in many applications such as phase retrieval, training of neural networks and matrix sensing, our result shows promise of robust control theory in these areas.

Accelerated gradient descent Nonconvex optimization Regularity condition Robust control

SCI ; EI

英语

通讯

National Science Foundation[CNS-1552838] ; Office of Naval Research[N00014-18-1-2142] ; Army Research Office[W911NF-18-1-0303]

Automation & Control Systems ; Engineering

Automation & Control Systems ; Engineering, Electrical & Electronic

WOS:000514216600033

Elsevier Ltd

20195207932045

Cost functions ; Gradient methods ; Learning algorithms ; Machine learning ; Robust control

Automatic Control Principles and Applications:731 ; Optimization Techniques:921.5 ; Numerical Methods:921.6

ENGINEERING

2-s2.0-85076886086

Scopus

1.Department of Electrical and Computer Engineering,The Ohio State University,Columbus,43210,United States
2.Department of Electrical and Computer Engineering,Carnegie Mellon University,Pittsburgh,15213,United States
3.Department of Electrical and Computer Engineering and Coordinated Science Laboratory,University of Illinois at Urbana-Champaign,Urbana,61801,United States
4.Department of Mechanical and Energy Engineering,Southern University of Science and Technology (SUSTech),Shenzhen,518055,China

Xiong，Huaqing,Chi，Yuejie,Hu，Bin,et al. Analytical convergence regions of accelerated gradient descent in nonconvex optimization under Regularity Condition[J]. AUTOMATICA,2020,113.

Xiong，Huaqing,Chi，Yuejie,Hu，Bin,&Zhang，Wei.(2020).Analytical convergence regions of accelerated gradient descent in nonconvex optimization under Regularity Condition.AUTOMATICA,113.

Xiong，Huaqing,et al."Analytical convergence regions of accelerated gradient descent in nonconvex optimization under Regularity Condition".AUTOMATICA 113(2020).