Global convergence of the gradient method for functions definable in o-minimal structures

DOI10.1007/S10107-023-01937-5MaRDI QIDQ6052062zbMATH OpenOpenAlexFDO

Authors Cédric Josz

Publication date 23 October 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.03534

zbMATH Keywords

Kurdyka-Łojasiewicz inequalityMorse-Sard theoremsemi-algebraic geometry

Mathematics Subject Classification ID

Model theory of ordered structures; o-minimality (03C64) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Abstract: We consider the gradient method with variable step size for minimizing functions that are definable in o-minimal structures on the real field and differentiable with locally Lipschitz gradients. We prove that global convergence holds if continuous gradient trajectories are bounded, with the minimum gradient norm vanishing at the rate $o(1/k)$ if the step sizes are greater than a positive constant. If additionally the gradient is continuously differentiable, all saddle points are strict, and the step sizes are constant, then convergence to a local minimum holds almost surely over any bounded set of initial points.

Recommendations

• Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
• On the gradient method in a Hilbert space in the case of nonisolated minima
• Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients
• Gradient Convergence in Gradient methods with Errors
• The method of gradient descent for minimizing non-convex functions

Cites work

• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• A generalization of the Tarski-Seidenberg theorem, and some nondefinability results
• A geometric approach of gradient descent algorithms in linear neural networks
• A new decision method for elementary algebra
• Analysis II
• Asymptotic convergence of nonlinear contraction semigroups in Hilbert space
• Bounding the length of gradient trajectories
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Cauchy and the gradient method
• Certifying the Absence of Spurious Local Minima at Infinity
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• Clarke Subgradients of Stratifiable Functions
• Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning
• Convergence Conditions for Ascent Methods
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Convergence of the Iterates of Descent Methods for Analytic Cost Functions
• Curves of descent
• Decoding by Linear Programming
• Definable Sets in Ordered Structures. I
• Expansions of the real field with power functions
• First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
• First-order methods almost always avoid strict saddle points
• Geometric categories and o-minimal structures
• Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3855514 (Why is no real title available?)
• scientific article; zbMATH DE number 4164577 (Why is no real title available?)
• scientific article; zbMATH DE number 3937151 (Why is no real title available?)
• scientific article; zbMATH DE number 3980094 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 46303 (Why is no real title available?)
• scientific article; zbMATH DE number 3526471 (Why is no real title available?)
• scientific article; zbMATH DE number 1017538 (Why is no real title available?)
• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• scientific article; zbMATH DE number 3238721 (Why is no real title available?)
• scientific article; zbMATH DE number 3307642 (Why is no real title available?)
• scientific article; zbMATH DE number 3313108 (Why is no real title available?)
• scientific article; zbMATH DE number 3371284 (Why is no real title available?)
• scientific article; zbMATH DE number 3381034 (Why is no real title available?)
• scientific article; zbMATH DE number 3398324 (Why is no real title available?)
• scientific article; zbMATH DE number 3052543 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• scientific article; zbMATH DE number 3109695 (Why is no real title available?)
• Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers
• Lectures on convex optimization
• Maximum length of steepest descent curves for quasi-convex functions
• Minimization of functions having Lipschitz continuous first partial derivatives
• Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function
• Nonconvergence to unstable points in urn models and stochastic approximations
• On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method
• On gradients of functions definable in o-minimal structures
• On Steepest Descent
• Path length bounds for gradient descent and flow
• Projections of semi-analytic sets
• Proof of the gradient conjecture of R. Thom.
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Quadratic growth and critical point stability of semi-algebraic functions
• Quasianalytic Denjoy-Carleman classes and o-minimality
• Rectifiability of self-contracted curves in the Euclidean space and applications
• Stochastic subgradient method converges on tame functions
• The elementary theory of restricted analytic fields with exponentiation
• The general theory of relaxation methods applied to linear systems
• The measure of the critical values of differentiable maps
• The method of steepest descent for non-linear minimization problems
• The real field with convergent generalized power series
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Ubiquitous algorithms in convex optimization generate self-contracted sequences
• Un exemple concernant le comportement asymptotique de la solution du problème \(du/dt+\partial\varphi(\mu)\ni=0\)
• Variational Analysis in Sobolev and BV Spaces
• Łojasiewicz inequalities in o-minimal structures

Cited in

(5)

• Gradient descent in the absence of global Lipschitz continuity of the gradients
• Global stability of first-order methods for coercive tame functions
• Singular perturbation in heavy ball dynamics
• Convergence of first-order algorithms with momentum from the perspective of an inexact gradient descent method
• Globally convergent derivative-free methods in nonconvex optimization with and without noise

This page was built for publication: Global convergence of the gradient method for functions definable in o-minimal structures

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