Path Length Bounds for Gradient Descent and Flow

2019/08/02 by Chirag Gupta, Sivaraman Balakrishnan, Gupta, Chirag +3 · 2 citations
Computer Science · Engineering · Medicine · #Artificial Intelligence (cs.AI) #Bone and Joint Diseases #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1908.01089

openalex publication_date 2019/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive bounds on the path length ζ 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 ζ is at most O(1/c); (b) under the Polyak-Kurdyka-Lojasiewicz (PKL) condition, ζ is at most O(√κ), where κ is the condition number, and at least \widetildeΩ(√(d) \wedge κ^1/4); (c) for quadratics, ζ is Θ(min\√(d),√(log κ)\) and in some cases can be independent of κ; (d) assuming just convexity, ζ can be at most 2^{4dlog d}; (e) for separable quasiconvex functions, ζ is Θ(√(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.

Citations

• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• A Convergence Theory for Deep Learning via Over-Parameterization
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

• Dimension-Free Bounds on Chasing Convex Functions
• Exploring Weight Importance and Hessian Bias in Model Pruning

Related

• Convexity of Optimization Curves: Local Sharp Thresholds, Robustness Impossibility, and New Counterexamples
• Non-sufficiency of smoothness in the gradient conjecture
• Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions
• Large-time behavior of the H^-m-gradient flow of length for closed plane curves
• A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces