Path Length Bounds for Gradient Descent and Flow

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 $\mathcal{O}(1/c)$; (b) under the Polyak-Kurdyka-Lojasiewicz (PKL) condition, $\zeta$ is at most $\mathcal{O}(\sqrt{\kappa })$, where $\kappa$ is the condition number, and at least $\tilde{\Omega }(\sqrt{d}\wedge {\kappa }^{1/4})$; (c) for quadratics, $\zeta$ is $\Theta (\min \{\sqrt{d},\sqrt{\log \kappa }\})$ and in some cases can be independent of $\kappa$; (d) assuming just convexity, $\zeta$ can be at most $2^{4d\log d}$; (e) for separable quasiconvex functions, $\zeta$ is $\Theta (\sqrt{d})$. 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.

55 pages. Accepted for publication at the Journal of Machine Learning Research (JMLR, 2021)

References in corpus (2)

• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

Cited by in corpus (4)

• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Dimension-Free Bounds on Chasing Convex Functions
• Linear Convergence of the Subspace Constrained Mean Shift Algorithm: From Euclidean to Directional Data