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.

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

References in corpus (9)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• More Adaptive Algorithms for Adversarial Bandits
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods

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