Path Length Bounds for Gradient Descent and Flow

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.