Perturbation Techniques for Convergence Analysis of Proximal Gradient Method and Other First-Order Algorithms via Variational Analysis

Wang, Xiangfeng1; Ye, Jane J.2; Yuan, Xiaoming3; Zeng, Shangzhi3; Zhang, Jin4

2021

10.1007/s11228-020-00570-0

Set-Valued and Variational Analysis   影响因子和分区

1877-0533

1877-0541

Wedevelopnew 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.

Calmness Error bound Proximal gradient method Linear convergence Variational analysis Alternating direction method of multipliers

SCI ; EI

英语

通讯

NSFC[11871279,11971090] ; General Research Fund from Hong Kong Research Grants Council[12302318] ; National Science Foundation of China[11971220] ; Guangdong Basic and Applied Basic Research Foundation[2019A1515011152]

Mathematics

Mathematics, Applied

WOS:000612573400001

SPRINGER

20221111795141

Web of Science

1.East China Normal Univ, Sch Comp Sci & Technol, Shanghai, Peoples R China
2.Univ Victoria, Dept Math & Stat, Victoria, BC, Canada
3.Univ Hong Kong, Dept Math, Hong Kong, Peoples R China
4.Southern Univ Sci & Technol, Natl Ctr Appl Math Shenzhen, SUSTech Int Ctr Math, Dept Math, Shenzhen, Peoples R China

Wang, Xiangfeng,Ye, Jane J.,Yuan, Xiaoming,et al. Perturbation Techniques for Convergence Analysis of Proximal Gradient Method and Other First-Order Algorithms via Variational Analysis[J]. Set-Valued and Variational Analysis,2021,30:39-79.

Wang, Xiangfeng,Ye, Jane J.,Yuan, Xiaoming,Zeng, Shangzhi,&Zhang, Jin.(2021).Perturbation Techniques for Convergence Analysis of Proximal Gradient Method and Other First-Order Algorithms via Variational Analysis.Set-Valued and Variational Analysis,30,39-79.

Wang, Xiangfeng,et al."Perturbation Techniques for Convergence Analysis of Proximal Gradient Method and Other First-Order Algorithms via Variational Analysis".Set-Valued and Variational Analysis 30(2021):39-79.