论文标题
使用积分二次约束分析梯度下降的梯度下降
Analysis of Gradient Descent with Varying Step Sizes using Integral Quadratic Constraints
论文作者
论文摘要
积分二次约束（IQC）的框架用于对具有不同步骤大小的梯度下降进行分析。考虑了两个性能指标：收敛速率和噪声扩增。我们假设步骤大小是通过线路搜索产生的，并且在已知间隔内变化。将算法建模为线性，参数变化（LPV）系统，我们构建了一个参数化的线性矩阵不等式（LMI）条件，该条件证明了算法性能，该算法性能使用多型LPV系统的结果来解决。当步长在限制间隔内时，我们的结果提供了收敛率的保证。此外，当此间隔减少到一个点时，即恒定步长时，我们会恢复现有的速率界限。最后，我们注意到收敛率仅取决于问题的条件数。相比之下，噪声放大性能取决于强凸度和平滑度参数的个体值，并且与固定条件数相反。
The framework of Integral Quadratic Constraints (IQCs) is used to perform an analysis of gradient descent with varying step sizes. Two performance metrics are considered: convergence rate and noise amplification. We assume that the step size is produced from a line search and varies in a known interval. Modeling the algorithm as a linear, parameter-varying (LPV) system, we construct a parameterized linear matrix inequality (LMI) condition that certifies algorithm performance, which is solved using a result for polytopic LPV systems. Our results provide convergence rate guarantees when the step size lies within a restricted interval. Moreover, we recover existing rate bounds when this interval reduces to a single point, i.e. a constant step size. Finally, we note that the convergence rate depends only on the condition number of the problem. In contrast, the noise amplification performance depends on the individual values of the strong convexity and smoothness parameters, and varies inversely with them for a fixed condition number.
