Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis
Despite the rich literature, the linear convergence of alternating direction method of multipliers (ADMM) has not been fully understood even for the convex case. For example, the linear convergence of ADMM can be empirically observed in a wide range of applications arising in statistics, machine learning, and related areas, while existing theoretical results seem to be too stringent to be satisfied or too ambiguous to be checked and thus why the ADMM performs linear convergence for these applications still seems to be unclear. In this paper, we systematically study the local linear convergence of ADMM in the context of convex optimization through the lens of variational analysis. We show that the local linear convergence of ADMM can be guaranteed without the strong convexity of objective functions together with the full rank assumption of the coefficient matrices, or the full polyhedricity assumption of their subdifferential; and it is possible to discern the local linear convergence for various concrete applications, especially for some representative models arising in statistical learning. We use some variational analysis techniques sophisticatedly; and our analysis is conducted in the most general proximal version of ADMM with Fortin and Glowinski’s larger step size so that all major variants of the ADMM known in the literature are covered.
Hong Kong Research Grants Council ; National Science Foundation of China ; [2019A1515011152]
|WOS Research Area|
Automation & Control Systems ; Computer Science
Automation & Control Systems ; Computer Science, Artificial Intelligence
|WOS Accession No|
|EI Accession Number|
Machine learning ; Variational techniques
|ESI Classification Code|
Artificial Intelligence:723.4 ; Calculus:921.2
|ESI Research Field|
Cited Times [WOS]:21
|Document Type||Journal Article|
|Department||Department of Mathematics|
1.Department of Mathematics,University of Hong Kong,Hong Kong SAR,China
2.Department of Mathematics SUSTech International Center for Mathematics,Southern University of Science and Technology,National Center for Applied Mathematics Shenzhen,Shenzhen, Guangdong,China
|Corresponding Author Affilication||Department of Mathematics; National Center for Applied Mathematics, SUSTech Shenzhen; SUSTech International Center for Mathematics|
Yuan，Xiaoming,Zeng，Shangzhi,Zhang，Jin. Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis[J]. JOURNAL OF MACHINE LEARNING RESEARCH,2020,21.
Yuan，Xiaoming,Zeng，Shangzhi,&Zhang，Jin.(2020).Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis.JOURNAL OF MACHINE LEARNING RESEARCH,21.
Yuan，Xiaoming,et al."Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis".JOURNAL OF MACHINE LEARNING RESEARCH 21(2020).
|Files in This Item:||There are no files associated with this item.|
|Recommend this item|
|Export to Endnote|
|Export to Excel|
|Export to Csv|
|Similar articles in Google Scholar|
|Similar articles in Baidu Scholar|
|Similar articles in Bing Scholar|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.