Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity

DOI10.1090/S0002-9947-09-05048-XzbMath1202.26026arXiv0802.0826MaRDI QIDQ3566718

Jérôme Bolte, Olivier Ley, Aris Daniilidis, Laurent Mazet

Publication date: 8 June 2010

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

global convergence; convex functions; Łojasiewicz inequality; gradient method; metric regularity; proximal method; talweg; gradient inequalities; subgradient curve

Mathematics Subject Classification ID

49J52: Nonsmooth analysis

37N40: Dynamical systems in optimization and economics

26D10: Inequalities involving derivatives and differential and integral operators

03C64: Model theory of ordered structures; o-minimality

Related Items

A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function, Sweeping by a tame process, Stochastic Methods for Composite and Weakly Convex Optimization Problems, Accelerated Methods for NonConvex Optimization, First Order Methods Beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems, A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems, Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano, Gradient stability of high-order BDF methods and some applications, A new approach to the proximal point method: convergence on general Riemannian manifolds, An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions, Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity, An inertial Tseng's type proximal algorithm for nonsmooth and nonconvex optimization problems, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function, A generalized inexact proximal point method for nonsmooth functions that satisfies Kurdyka Łojasiewicz inequality, Nonlinear error bounds via a change of function, Stability of saddle points via explicit coderivatives of pointwise subdifferentials, Bounding regions to plane steepest descent curves of quasiconvex families, Dual descent methods as tension reduction systems, A block coordinate variable metric forward-backward algorithm, The proximal alternating iterative hard thresholding method for \(l_0\) minimization, with complexity \(\mathcal{O}(1/\sqrt{k})\), An attention algorithm for solving large scale structured \(l_0\)-norm penalty estimation problems, Continuous dynamics related to monotone inclusions and non-smooth optimization problems, Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions, Convergence rate analysis for the higher order power method in best rank one approximations of tensors, A note on the Douglas-Rachford splitting method for optimization problems involving hypoconvex functions, Local convergence of the heavy-ball method and iPiano for non-convex optimization, A simplified view of first order methods for optimization, A family of functional inequalities: Łojasiewicz inequalities and displacement convex functions, Approaching nonsmooth nonconvex optimization problems through first order dynamical systems with hidden acceleration and Hessian driven damping terms, From error bounds to the complexity of first-order descent methods for convex functions, A globally convergent algorithm for nonconvex optimization based on block coordinate update, A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem, Rate of convergence to equilibrium and Łojasiewicz-type estimates, Extragradient method in optimization: convergence and complexity, Learning in games with continuous action sets and unknown payoff functions, Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis, On definable multifunctions and Łojasiewicz inequalities, A block coordinate variable metric linesearch based proximal gradient method, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Approaching nonsmooth nonconvex minimization through second-order proximal-gradient dynamical systems, Rectifiability of non Euclidean planar self-contracted curves, Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions, Kurdyka-Łojasiewicz property of zero-norm composite functions, Maximum time step for the BDF3 scheme applied to gradient flows, Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization, Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method, A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization, On the convergence to equilibria of a sequence defined by an implicit scheme, Curiosities and counterexamples in smooth convex optimization, A control-theoretic perspective on optimal high-order optimization, Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-Łojasiewicz condition, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, Avoiding bad steps in Frank-Wolfe variants, Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis, Convergence results of a new monotone inertial forward-backward splitting algorithm under the local Hölder error bound condition, Quantitative analysis of a subgradient-type method for equilibrium problems, A survey on some recent developments of alternating direction method of multipliers, Convergence of proximal splitting algorithms in \(\operatorname{CAT}(\kappa)\) spaces and beyond, Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems, Non-convex split Feasibility problems: models, algorithms and theory, A gradient-type algorithm with backward inertial steps associated to a nonconvex minimization problem, Shape turnpike for linear parabolic PDE models, Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization, Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality, Structured sparsity promoting functions, Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems, Necessary conditions for linear convergence of iterated expansive, set-valued mappings, An augmented Lagrangian proximal alternating method for sparse discrete optimization problems, Local convergence of the Levenberg-Marquardt method under Hölder metric subregularity, A new proximal iterative hard thresholding method with extrapolation for \(\ell _0\) minimization, Using Landweber iteration to quantify source conditions -- a numerical study, Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods, Rectifiability of self-contracted curves in the Euclidean space and applications, Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, On damped second-order gradient systems, Set regularities and feasibility problems, First-order methods almost always avoid strict saddle points, Every ordinary differential equation with a strict Lyapunov function is a gradient system, Hölder metric regularity of set-valued maps, Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure, New convergence results for the inexact variable metric forward-backward method, Optimal non-asymptotic analysis of the Ruppert-Polyak averaging stochastic algorithm, Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry, On the uniqueness of Schwarzschild-de Sitter spacetime, Polyak-Łojasiewicz inequality on the space of measures and convergence of mean-field birth-death processes, An abstract convergence framework with application to inertial inexact forward-backward methods, ŁOJASIEWICZ-TYPE INEQUALITIES AND GLOBAL ERROR BOUNDS FOR NONSMOOTH DEFINABLE FUNCTIONS IN O-MINIMAL STRUCTURES, Evaluation Complexity for Nonlinear Constrained Optimization Using Unscaled KKT Conditions and High-Order Models, Hölder-Like Property and Metric Regularity of a Positive-Order for Implicit Multifunctions, An Alternating Semiproximal Method for Nonconvex Regularized Structured Total Least Squares Problems, Energy stable and convergent finite element schemes for the modified phase field crystal equation, Convergence Results for Projected Line-Search Methods on Varieties of Low-Rank Matrices Via Łojasiewicz Inequality, A proximal algorithm with quasi distance. Application to habit's formation, The Kurdyka–Łojasiewicz–Simon inequality and stabilisation in nonsmooth infinite-dimensional gradient systems, Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems, Separation of real algebraic sets and the Łojasiewicz exponent, The Kurdyka–Łojasiewicz Inequality as Regularity Condition, Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints, On steepest descent curves for quasi convex families in Rn, Variable Metric Forward-Backward Algorithm for Composite Minimization Problems, A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization, A Stochastic Proximal Alternating Minimization for Nonsmooth and Nonconvex Optimization, Bounding the length of gradient trajectories, An inertial proximal alternating direction method of multipliers for nonconvex optimization, Convex-Concave Backtracking for Inertial Bregman Proximal Gradient Algorithms in Nonconvex Optimization, Error bound conditions and convergence of optimization methods on smooth and proximally smooth manifolds, Error bounds revisited, Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization, A continuous dynamical splitting method for solving ‘strongly+weakly’ convex programming problems, The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates, CONVERGENCE TO EQUILIBRIUM FOR A TIME SEMI-DISCRETE DAMPED WAVE EQUATION, Convergence of Inexact Forward--Backward Algorithms Using the Forward--Backward Envelope, A second-order dynamical approach with variable damping to nonconvex smooth minimization, Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings, The Boosted Difference of Convex Functions Algorithm for Nonsmooth Functions, Modern regularization methods for inverse problems, A Proximal Minimization Algorithm for Structured Nonconvex and Nonsmooth Problems, An Inertial Newton Algorithm for Deep Learning, Kurdyka–Łojasiewicz–Simon inequality for gradient flows in metric spaces, Convergence Analysis of Douglas--Rachford Splitting Method for “Strongly + Weakly” Convex Programming, A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima, Oriented distance point of view on random sets, Generalized Momentum-Based Methods: A Hamiltonian Perspective, Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences, On Optimality Conditions for Nonlinear Conic Programming, The Exact Modulus of the Generalized Concave Kurdyka-Łojasiewicz Property, Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem, Examples of Pathological Dynamics of the Subgradient Method for Lipschitz Path-Differentiable Functions, Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations, Global convergence of the gradient method for functions definable in o-minimal structures, Fast convergence of inertial dynamics with Hessian-driven damping under geometry assumptions, Bernstein-Remez inequality for algebraic functions: a topological approach, Coercivity and generalized proximal algorithms: application -- traveling around the world, A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization, A convex function satisfying the Łojasiewicz inequality but failing the gradient conjecture both at zero and infinity, First order inertial optimization algorithms with threshold effects associated with dry friction, Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality, A forward-backward algorithm with different inertial terms for structured non-convex minimization problems, Calculus rules of the generalized concave Kurdyka-Łojasiewicz property, Fast optimization via inertial dynamics with closed-loop damping

Cites Work