Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis

DOI10.1007/S11228-020-00570-0zbMATH Open1487.90643arXiv1810.10051OpenAlexW3129000167MaRDI QIDQ2116020FDOQ2116020

Xiangfeng Wang, Jane J. Ye, Xiaoming Yuan, Jin Zhang, Shangzhi Zeng

Publication date: 15 March 2022

Published in: Set-Valued and Variational Analysis (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

alternating direction method of multipliersproximal gradient methoderror boundvariational analysiscalmnesslinear convergence

Mathematics Subject Classification ID

Nonsmooth analysis (49J52) Set-valued and variational analysis (49J53) Methods of reduced gradient type (90C52)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Nearly unbiased variable selection under minimax concave penalty
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Variational Analysis
• Introductory lectures on convex optimization. A basic course.
• Adaptive restart for accelerated gradient schemes
• Title not available (Why is that?)
• A coordinate gradient descent method for nonsmooth separable minimization
• Title not available (Why is that?)
• 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
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality
• Implicit Functions and Solution Mappings
• Strongly Regular Generalized Equations
• Some continuity properties of polyhedral multifunctions
• Title not available (Why is that?)
• On the Calmness of a Class of Multifunctions
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
• Lipschitz Behavior of Solutions to Convex Minimization Problems
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• Stability Theory for Systems of Inequalities. Part I: Linear Systems
• On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs
• Error bounds and convergence analysis of feasible descent methods: A general approach
• Calmness of constraint systems with applications
• Lipschitz and Hölder stability of optimization problems and generalized equations
• Optimality Conditions for Disjunctive Programs Based on Generalized Differentiation with Application to Mathematical Programs with Equilibrium Constraints
• Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
• Necessary Optimality Conditions for Optimization Problems with Variational Inequality Constraints
• Constraint Qualifications and Necessary Optimality Conditions for Optimization Problems with Variational Inequality Constraints
• Second-order growth, tilt stability, and metric regularity of the subdifferential
• New Constraint Qualifications for Mathematical Programs with Equilibrium Constraints via Variational Analysis
• Proximal-point algorithm using a linear proximal term
• Subgradient Criteria for Monotonicity, The Lipschitz Condition, and Convexity
• A proximal-gradient homotopy method for the sparse least-squares problem
• On directionally dependent subdifferentials
• Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems
• From error bounds to the complexity of first-order descent methods for convex functions
• Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
• A unified approach to error bounds for structured convex optimization problems
• On Lipschitzian properties of implicit multifunctions
• Constrained Minima and Lipschitzian Penalties in Metric Spaces
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems
• Local Linear Convergence of ISTA and FISTA on the LASSO Problem
• Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems
• Partial Error Bound Conditions and the Linear Convergence Rate of the Alternating Direction Method of Multipliers
• Title not available (Why is that?)
• Directional Quasi-/Pseudo-Normality as Sufficient Conditions for Metric Subregularity
• Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
• Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems

Cited In (5)

• An Inexact Uzawa Algorithmic Framework for Nonlinear Saddle Point Problems with Applications to Elliptic Optimal Control Problem
• Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems
• 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
• Perturbed Fenchel duality and first-order methods

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)