An elementary approach to tight worst case complexity analysis of gradient based methods

• 成果类型: Article
• 署名作者: Teboulle, Marc; Vaisbourd, Yakov
• 署名单位: Tel Aviv University; McGill University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01899-0
• 发表日期: 2023
• 页码: 63-96
• 关键词: 1st-order methods; case performance; CONVERGENCE; algorithm; SUM

摘要

This work presents a novel analysis that allows to achieve tight complexity bounds of gradient-based methods for convex optimization. We start by identifying some of the pitfalls rooted in the classical complexity analysis of the gradient descent method, and show how they can be remedied. Our methodology hinges on elementary and direct arguments in the spirit of the classical analysis. It allows us to establish some new (and reproduce known) tight complexity results for several fundamental algorithms including, gradient descent, proximal point and proximal gradient methods which previously could be proven only through computer-assisted convergence proof arguments.