# Path Length Bounds for Gradient Descent and Flow

arXiv: https://arxiv.org/abs/1908.01089 · HTML: https://mlsanity.com/paper/1908.01089/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Aug 2019.

## Built on by (most cited first, 6 of 6)

- [On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias](https://mlsanity.com/paper/2205.09072/) (2022)
- [Accelerating Fair Federated Learning: Adaptive Federated Adam](https://mlsanity.com/paper/2301.09357/) (2023)
- [A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces](https://mlsanity.com/paper/2310.17610/) (2023)
- [Statistical Inference on Gradient Flows](https://mlsanity.com/paper/2606.01257/) (2026)
- [Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence](https://mlsanity.com/paper/2604.17067/) (2026)
- [Architecture-driven Shift: towards a lightweight selector for capturing the trends of logit shift](https://mlsanity.com/paper/2605.27469/) (2026)

## Abstract (arXiv)

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 O(1/c); (b) under the Polyak-Kurdyka-Lojasiewicz (PKL) condition, zeta is at most O(√kappa), where kappa is the condition number, and at least widetildeOmega(√d wedge kappa1/4); (c) for quadratics, zeta is Theta(min√d,√log kappa) and in some cases can be independent of kappa; (d) assuming just convexity, zeta can be at most 24dlog d; (e) for separable quasiconvex functions, zeta is Theta(√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.