Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods

DOI10.1007/s10208-017-9366-8zbMath1405.90076arXiv1602.02915OpenAlexW3100208521MaRDI QIDQ1785009

Ting Kei Pong, Guoyin Li

Publication date: 27 September 2018

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

convergence ratelinear convergenceKurdyka-Łojasiewicz inequalitysparse optimizationfirst-order methodsLuo-Tseng error bound

Mathematics Subject Classification ID

Convex programming (90C25) Nonconvex programming, global optimization (90C26) Linear programming (90C05)

Related Items

Convergence rate analysis for the higher order power method in best rank one approximations of tensors, Further properties of the forward-backward envelope with applications to difference-of-convex programming, Convergence guarantees for a class of non-convex and non-smooth optimization problems, Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems, Local convergence of the heavy-ball method and iPiano for non-convex optimization, Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints, Tensor Canonical Correlation Analysis With Convergence and Statistical Guarantees, Global convergence of model function based Bregman proximal minimization algorithms, Minimization of $L_1$ Over $L_2$ for Sparse Signal Recovery with Convergence Guarantee, Kurdyka-Łojasiewicz exponent via inf-projection, A forward-backward dynamical approach for nonsmooth problems with block structure coupled by a smooth function, A globally convergent algorithm for nonconvex optimization based on block coordinate update, Difference-of-Convex Algorithms for a Class of Sparse Group $\ell_0$ Regularized Optimization Problems, Quadratic growth conditions and uniqueness of optimal solution to Lasso, The equivalence of three types of error bounds for weakly and approximately convex functions, Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations, Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation, An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis, Error bounds, facial residual functions and applications to the exponential cone, Zero-norm regularized problems: equivalent surrogates, proximal MM method and statistical error bound, Global convergence of the gradient method for functions definable in o-minimal structures, A refined convergence analysis of \(\mathrm{pDCA}_{e}\) with applications to simultaneous sparse recovery and outlier detection, Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients, Proximal linearization methods for Schatten \(p\)-quasi-norm minimization, Joint Reconstruction-Segmentation on Graphs, A Regularized Newton Method for \({\boldsymbol{\ell}}_{q}\) -Norm Composite Optimization Problems, Tensor factorization via transformed tensor-tensor product for image alignment, A proximal subgradient algorithm with extrapolation for structured nonconvex nonsmooth problems, A Subgradient-Based Approach for Finding the Maximum Feasible Subsystem with Respect to a Set, Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems, Convergence of a Class of Nonmonotone Descent Methods for Kurdyka–Łojasiewicz Optimization Problems, Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for \(\boldsymbol{\ell_1}\) -Norm Principal Component Analysis, A globally convergent proximal Newton-type method in nonsmooth convex optimization, Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry, A forward-backward algorithm with different inertial terms for structured non-convex minimization problems, Calculus rules of the generalized concave Kurdyka-Łojasiewicz property, A DCA-Newton method for quartic minimization over the sphere, Fast optimization via inertial dynamics with closed-loop damping, A global two-stage algorithm for non-convex penalized high-dimensional linear regression problems, Convergence rate analysis of proximal iteratively reweighted \(\ell_1\) methods for \(\ell_p\) regularization problems, Proximal gradient method with extrapolation and line search for a class of non-convex and non-smooth problems, On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization, A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection, Convergence Rate Analysis of a Dykstra-Type Projection Algorithm, Retraction-based first-order feasible methods for difference-of-convex programs with smooth inequality and simple geometric constraints, A proximal interior point algorithm with applications to image processing, General Hölder smooth convergence rates follow from specialized rates assuming growth bounds, Error bound and isocost imply linear convergence of DCA-based algorithms to D-stationarity, A new nonconvex approach to low-rank matrix completion with application to image inpainting, Unnamed Item, On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, Local Minimizers of Semi-Algebraic Functions from the Viewpoint of Tangencies, Generalized Subdifferentials of Spectral Functions over Euclidean Jordan Algebras, A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property, Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization, Local linear convergence of an ADMM-type splitting framework for equality constrained optimization, A proximal difference-of-convex algorithm with extrapolation, On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems, Kurdyka-Łojasiewicz property of zero-norm composite functions, Variable smoothing for weakly convex composite functions, On the linear convergence of forward-backward splitting method. I: Convergence analysis, Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method, New analysis of linear convergence of gradient-type methods via unifying error bound conditions, A preconditioned difference of convex algorithm for truncated quadratic regularization with application to imaging, The modified second APG method for DC optimization problems, A dual active set algorithm for optimal sparse convex regression, Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem, An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems, Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems, Convergence rates of forward-Douglas-Rachford splitting method, Analysis and Algorithms for Some Compressed Sensing Models Based on L1/L2 Minimization, Inertial proximal incremental aggregated gradient method with linear convergence guarantees, Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods, A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization, On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint, Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems, Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences, Infeasibility and Error Bound Imply Finite Convergence of Alternating Projections, Nondegeneracy of eigenvectors and singular vector tuples of tensors, On Optimality Conditions for Nonlinear Conic Programming, Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs, The Exact Modulus of the Generalized Concave Kurdyka-Łojasiewicz Property, Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem, Avoiding bad steps in Frank-Wolfe variants, A Stochastic Proximal Alternating Minimization for Nonsmooth and Nonconvex Optimization, First-Order Algorithms for a Class of Fractional Optimization Problems, Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis, Restarting Frank-Wolfe: faster rates under Hölderian error bounds

Uses Software

• iPiano

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• Nearly unbiased variable selection under minimax concave penalty
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• An inertial Tseng's type proximal algorithm for nonsmooth and nonconvex optimization problems
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• Iterative thresholding for sparse approximations
• New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensors
• Convex analysis and nonlinear optimization. Theory and examples.
• A coordinate gradient descent method for nonsmooth separable minimization
• Error bounds and convergence analysis of feasible descent methods: A general approach
• From error bounds to the complexity of first-order descent methods for convex functions
• A unified approach to error bounds for structured convex optimization problems
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions
• Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
• A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion
• iPiano: Inertial Proximal Algorithm for Nonconvex Optimization
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Geometrical interpretation of the predictor-corrector type algorithms in structured optimization problems
• Global Convergence of Splitting Methods for Nonconvex Composite Optimization
• Implicit Functions and Solution Mappings
• Some continuity properties of polyhedral multifunctions
• On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
• Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
• Variational Analysis
• Variational Analysis and Generalized Differentiation I
• On Projection Algorithms for Solving Convex Feasibility Problems
• Active Sets, Nonsmoothness, and Sensitivity
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Error Bounds for Piecewise Convex Quadratic Programs and Applications
• Comments on «Wavelets in statistics: A review» by A. Antoniadis
• Model Selection and Estimation in Regression with Grouped Variables
• Efficient Reconstruction of Piecewise Constant Images Using Nonsmooth Nonconvex Minimization
• Convex analysis and monotone operator theory in Hilbert spaces
• Mathematical Programs with Equilibrium Constraints