A frequency-domain analysis of inexact gradient methods

• 成果类型: Article
• 署名作者: Gannot, Oran
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01665-8
• 发表日期: 2022
• 页码: 975-1016
• 关键词: dissipative dynamical-systems; worst-case performance; optimization algorithms; 1st-order methods; convex; STABILITY

摘要

We study robustness properties of some iterative gradient-based methods for strongly convex functions, as well as for the larger class of functions with sector-bounded gradients, under a relative error model. Proofs of the corresponding convergence rates are based on frequency-domain criteria for the stability of nonlinear systems. Applications are given to inexact versions of gradient descent and the Triple Momentum Method. To further emphasize the usefulness of frequency-domain methods, we derive improved analytic bounds for the convergence rate of Nesterov's accelerated method (in the exact setting) on strongly convex functions.