Path Length Bounds for Gradient Descent and Flow

MaRDI QIDQ6323131arXivFDO

Authors Chirag Gupta, Sivaraman Balakrishnan, Aaditya Ramdas

Publication date 2 August 2019

Published in arXiv

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

arXiv classification

cs.AIcs.LGmath.OCstat.ML

Abstract: We derive bounds on the path length $zeta$ of gradient descent (GD) and gradient flow (GF) curves for various classes of smooth convex and nonconvex functions. Among other results, we prove that: (a) if the iterates are linearly convergent with factor $(1-c)$, then $zeta$ is at most $mathcalO(1/c)$; (b) under the Polyak-Kurdyka-Lojasiewicz (PKL) condition, $zeta$ is at most $mathcalO(sqrtkappa)$, where $kappa$ is the condition number, and at least $widetildeOmega(sqrtdwedgekapp{a}^{1/4})$; (c) for quadratics, $zeta$ is $Theta(minsqrtd,sqrtlogkappa)$ and in some cases can be independent of $kappa$; (d) assuming just convexity, $zeta$ can be at most $2^{4dlogd}$; (e) for separable quasiconvex functions, $zeta$ is $Theta(sqrtd)$. Thus, we advance current understanding of the properties of GD and GF curves beyond rates of convergence. We expect our techniques to facilitate future studies for other algorithms.

This page was built for publication: Path Length Bounds for Gradient Descent and Flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323131)