Analysis of Gradient Descent with Varying Step Sizes using Integral Quadratic Constraints
Lists
Only you see this
Abstract
In this paper, we present an analysis of the convergence rate of gradient descent with a varying step size, on strongly convex functions. We assume that a line search has been carried out and produces a step size that varies in a known interval. The algorithm is then handled as a linear, parameter-varying (LPV) system. Building on prior work that uses Integral Quadratic Constraints (IQCs) to analyze optimization algorithms, we construct a linear matrix inequality (LMI) condition to numerically obtain convergence rates. For the LPV system, this condition is solved by a gridding approach on the step size interval. Our results indicate that the algorithm converges in a restricted set within the step size interval. Further, when this interval reduces to a point, i.e., when a constant step size is used, the algorithm recovers the gradient rate corresponding to constant step sizes.
BibTeX
@article{padmanabhan2022analysis,
author = {Ram Padmanabhan and Peter Seiler},
title = {{Analysis of Gradient Descent with Varying Step Sizes using Integral Quadratic Constraints}},
journal = {IEEE Trans. Automatic Control},
year = {2022},
}