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

Huaqing Xiong, Yuejie Chi, Bin Hu, Wei Zhang

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Article number108715
JournalAutomatica
Volume113
DOIs
StatePublished - Mar 2020

Fingerprint

Robust control
Control theory
Cost functions
Learning algorithms
Learning systems
Neural networks

Keywords

  • Accelerated gradient descent
  • Nonconvex optimization
  • Regularity condition
  • Robust control

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this

Analytical convergence regions of accelerated gradient descent in nonconvex optimization under Regularity Condition. / Xiong, Huaqing; Chi, Yuejie; Hu, Bin; Zhang, Wei.

In: Automatica, Vol. 113, 108715, 03.2020.

Research output: Contribution to journalArticle

@article{3261e250082f4b3f825adbac2c40c851,
title = "Analytical convergence regions of accelerated gradient descent in nonconvex optimization under Regularity Condition",
abstract = "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.",
keywords = "Accelerated gradient descent, Nonconvex optimization, Regularity condition, Robust control",
author = "Huaqing Xiong and Yuejie Chi and Bin Hu and Wei Zhang",
year = "2020",
month = "3",
doi = "10.1016/j.automatica.2019.108715",
language = "English (US)",
volume = "113",
journal = "Automatica",
issn = "0005-1098",
publisher = "Elsevier Limited",

}

TY - JOUR

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

AU - Xiong, Huaqing

AU - Chi, Yuejie

AU - Hu, Bin

AU - Zhang, Wei

PY - 2020/3

Y1 - 2020/3

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

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

KW - Accelerated gradient descent

KW - Nonconvex optimization

KW - Regularity condition

KW - Robust control

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

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

U2 - 10.1016/j.automatica.2019.108715

DO - 10.1016/j.automatica.2019.108715

M3 - Article

AN - SCOPUS:85076886086

VL - 113

JO - Automatica

JF - Automatica

SN - 0005-1098

M1 - 108715

ER -