Path length bounds for gradient descent and flow

MaRDI QIDQ4998970zbMATH OpenFDO

Authors Chirag Gupta, Sivaraman Balakrishnan, Aaditya Ramdas

Publication date 9 July 2021

Full work available at URL https://arxiv.org/abs/1908.01089, https://jmlr.csail.mit.edu/papers/v22/19-979.html

zbMATH Keywords

condition numberoptimizationPolyak-Kurdyka-Łojasiewicz functionsself-contracted curvestrajectory analysis

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Conditions for linear convergence of the gradient method for non-convex optimization
• Bounding the length of gradient trajectories
• Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
• Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity

Cites work

• 10.1162/153244302760200704
• A Nearly-Linear Bound for Chasing Nested Convex Bodies
• Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions
• Convex optimization: algorithms and complexity
• Convex regions on the n-dimensional spherical surface
• First-order methods almost always avoid strict saddle points
• Forward stagewise regression and the monotone lasso
• scientific article; zbMATH DE number 3371284 (Why is no real title available?)
• scientific article; zbMATH DE number 3084780 (Why is no real title available?)
• Maximum length of steepest descent curves for quasi-convex functions
• On gradients of functions definable in o-minimal structures
• On lower complexity bounds for large-scale smooth convex optimization
• Rectifiability of self-contracted curves in the Euclidean space and applications
• Self-contracted curves are gradient flows of convex functions
• Self-contracted curves have finite length
• Self-contracted curves in Riemannian manifolds
• Some methods of speeding up the convergence of iteration methods
• Statistical guarantees for the EM algorithm: from population to sample-based analysis
• The landscape of empirical risk for nonconvex losses
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks

Cited in

(5)

• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Ubiquitous algorithms in convex optimization generate self-contracted sequences
• Global convergence of the gradient method for functions definable in o-minimal structures
• The slope robustly determines convex functions
• Path Length Bounds for Gradient Descent and Flow

Describes a project that uses

Uses Software

• GeoGebra

This page was built for publication: Path length bounds for gradient descent and flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4998970)