Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
From MaRDI portal
Publication:2116020
Abstract: We develop new perturbation techniques for conducting convergence analysis of various first-order algorithms for a class of nonsmooth optimization problems. We consider the iteration scheme of an algorithm to construct a perturbed stationary point set-valued map, and define the perturbing parameter by the difference of two consecutive iterates. Then, we show that the calmness condition of the induced set-valued map, together with a local version of the proper separation of stationary value condition, is a sufficient condition to ensure the linear convergence of the algorithm. The equivalence of the calmness condition to the one for the canonically perturbed stationary point set-valued map is proved, and this equivalence allows us to derive some sufficient conditions for calmness by using some recent developments in variational analysis. These sufficient conditions are different from existing results (especially, those error-bound-based ones) in that they can be easily verified for many concrete application models. Our analysis is focused on the fundamental proximal gradient (PG) method, and it enables us to show that any accumulation of the sequence generated by the PG method must be a stationary point in terms of the proximal subdifferential, instead of the limiting subdifferential. This result finds the surprising fact that the solution quality found by the PG method is in general superior. Our analysis also leads to some improvement for the linear convergence results of the PG method in the convex case. The new perturbation technique can be conveniently used to derive linear rate convergence of a number of other first-order methods including the well-known alternating direction method of multipliers and primal-dual hybrid gradient method, under mild assumptions.
Recommendations
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Convergence analysis of perturbed feasible descent methods
- Perturbed Fenchel duality and first-order methods
- Error stability properties of generalized gradient-type algorithms
- Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method
Cites work
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 1113627 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A coordinate gradient descent method for nonsmooth separable minimization
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A proximal-gradient homotopy method for the sparse least-squares problem
- A unified approach to error bounds for structured convex optimization problems
- Adaptive restart for accelerated gradient schemes
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
- Calmness of constraint systems with applications
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Constrained Minima and Lipschitzian Penalties in Metric Spaces
- Constraint Qualifications and Necessary Optimality Conditions for Optimization Problems with Variational Inequality Constraints
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
- Deep learning
- Directional quasi-/pseudo-normality as sufficient conditions for metric subregularity
- Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis
- Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
- Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Error bounds, quadratic growth, and linear convergence of proximal methods
- From error bounds to the complexity of first-order descent methods for convex functions
- Implicit Functions and Solution Mappings
- Introductory lectures on convex optimization. A basic course.
- Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems
- Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems
- Lipschitz Behavior of Solutions to Convex Minimization Problems
- Lipschitz and Hölder stability of optimization problems and generalized equations
- Local Linear Convergence of ISTA and FISTA on the LASSO Problem
- Nearly unbiased variable selection under minimax concave penalty
- Necessary Optimality Conditions for Optimization Problems with Variational Inequality Constraints
- New constraint qualifications for mathematical programs with equilibrium constraints via variational analysis
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- On Lipschitzian properties of implicit multifunctions
- On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs
- On directionally dependent subdifferentials
- On the Calmness of a Class of Multifunctions
- Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints
- Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal-point algorithm using a linear proximal term
- Second-order growth, tilt stability, and metric regularity of the subdifferential
- Some continuity properties of polyhedral multifunctions
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- Stability Theory for Systems of Inequalities. Part I: Linear Systems
- Strongly Regular Generalized Equations
- Subgradient Criteria for Monotonicity, The Lipschitz Condition, and Convexity
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- Variational Analysis
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems
Cited in
(8)- Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems
- An inexact Uzawa algorithmic framework for nonlinear saddle point problems with applications to elliptic optimal control problem
- Level-set subdifferential error bounds and linear convergence of Bregman proximal gradient method
- The equivalence of three types of error bounds for weakly and approximately convex functions
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- On growth error bound conditions with an application to heavy ball method
- Perturbed Fenchel duality and first-order methods
- Stability analysis of split equality and split feasibility problems
This page was built for publication: Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2116020)
