A frequency-domain analysis of inexact gradient methods

被引:12
作者
Gannot, Oran
机构
关键词
90C25; 93C80; 93D09; 93D05; 68Q25; DISSIPATIVE DYNAMICAL-SYSTEMS; WORST-CASE PERFORMANCE; OPTIMIZATION ALGORITHMS; 1ST-ORDER METHODS; CONVEX; STABILITY;
D O I
10.1007/s10107-021-01665-8
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:975 / 1016
页数:42
相关论文
共 67 条
[1]   A Less Conservative LMI Condition for Stability of Discrete-Time Systems With Slope-Restricted Nonlinearities [J].
Ahmad, N. Syazreen ;
Carrasco, J. ;
Heath, W. P. .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2015, 60 (06) :1692-1697
[2]  
[Anonymous], 2019, ARXIV190809043
[3]  
[Anonymous], 2015, ADV NEURAL INFORM PR
[4]  
[Anonymous], 2015, P 32 INT C MACH LEAR
[5]  
[Anonymous], 2018, ARXIV180512591
[6]  
[Anonymous], 2017, ARXIV170509886
[7]  
[Anonymous], 2018, ARXIV181200146
[8]  
[Anonymous], 2013, CORE DISCUSSION PAPE
[9]  
Arora S., 2015, Track, V40, P113
[10]   Analysis of the Heavy-ball Algorithm using Integral Quadratic Constraints [J].
Badithela, Apurva ;
Seiler, Peter .
2019 AMERICAN CONTROL CONFERENCE (ACC), 2019, :4081-4085