Analysis of Gradient Descent with Varying Step Sizes using Integral Quadratic Constraints
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909606502989824 |
|---|---|
| author | Padmanabhan, Ram Seiler, Peter |
| author_facet | Padmanabhan, Ram Seiler, Peter |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_00644 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Analysis of Gradient Descent with Varying Step Sizes using Integral Quadratic Constraints Padmanabhan, Ram Seiler, Peter Optimization and Control Systems and Control 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. |
| title | Analysis of Gradient Descent with Varying Step Sizes using Integral Quadratic Constraints |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2210.00644 |