Revisit of Estimate Sequence for Accelerated Gradient Methods

Bingcong Li, Mario Coutiño, Georgios B. Giannakis

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Abstract

In this paper, we revisit the problem of minimizing a convex function f(x) with Lipschitz continuous gradient via accelerated gradient methods (AGM). To do so, we consider the so-called estimate sequence (ES), a useful analysis tool for establishing the convergence of AGM. We develop a generalized ES to support Lipschitz continuous gradient on any norm, given the importance of considering non-Euclidian norms in optimization. Traditionally, ES consists of a sequence of quadratic functions that serves as surrogate functions of f(x). However, such quadratic functions preclude the possibility of supporting Lipschitz continuous gradient defined w.r.t. non-Euclidian norms. Hence, an extension of such a powerful tool to the non-Euclidian norm setting is so much needed. Such extension is accomplished through a simple yet nontrivial modification of the standard ES. Further, our analysis provides insights of how acceleration is achieved and interpretability of the involved parameters in ES. Finally, numerical tests demonstrate the convergence benefits of taking non-Euclidean norms into account.
Original languageEnglish
Title of host publicationICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
Subtitle of host publicationProceedings
PublisherIEEE
Pages3602-3606
Number of pages5
ISBN (Electronic)978-1-5090-6631-5
ISBN (Print)978-1-5090-6632-2
DOIs
Publication statusPublished - 2020
EventICASSP 2020: IEEE International Conference on Acoustics, Speech and Signal Processing - Barcelona, Spain
Duration: 4 May 20208 May 2020

Conference

ConferenceICASSP 2020
CountrySpain
CityBarcelona
Period4/05/208/05/20

Keywords

  • Nesterov's accelerated gradient method
  • estimate sequences
  • gradient descent
  • optimization

Fingerprint

Dive into the research topics of 'Revisit of Estimate Sequence for Accelerated Gradient Methods'. Together they form a unique fingerprint.

Cite this