NeurIPS 2021poster31 citations
A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
Jongmin Lee, Chanwoo Park, Ernest K. Ryu
Abstract
Since Nesterov's seminal 1983 work, many accelerated first-order optimization methods have been proposed, but their analyses lacks a common unifying structure. In this work, we identify a geometric structure satisfied by a wide range of first-order accelerated methods. Using this geometric insight, we present several novel generalizations of accelerated methods. Most interesting among them is a method that reduces the squared gradient norm with $\mathcal{O}(1/K^4)$ rate in the prox-grad setup, faster than the $\mathcal{O}(1/K^3)$ rates of Nesterov's FGM or Kim and Fessler's FPGM-m.
accelerationconvex optimizationEuclidean geometrygradient normsmall gradientsmaking gradients smallcomposite optimizationOGMFISTAOGM-Gpotential function-basedLyapunov analysiscomplexity bounds
BibTeX
@inproceedings{
lee2021a,
title={A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast},
author={Jongmin Lee and Chanwoo Park and Ernest K. Ryu},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=tTeJejS8vte}
}