文章基本信息

标题：Potential-Function Proofs for Gradient Methods
本地全文：下载
作者：Nikhil Bansal ; Anupam Gupta
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2019
卷号：15
页码：1-32
DOI：10.4086/toc.2019.v015a004
出版社：University of Chicago
摘要：This note discusses proofs of convergence for gradient methods (also called “first-order methods”) based on simple potential-function arguments. We cover methods like gradient descent (for both smooth and non-smooth settings), mirror descent, and some accelerated variants. We hope the structure and presentation of these amortized-analysis proofs will be useful as a guiding principle in learning and using these proofs.
关键词：convex optimization; potential functions; amortized analysis