Discerning the Linear Convergence of ADMM for Structured Convex Optimization through the Lens of Variational Analysis
Discerning the Linear Convergence of ADMM for Structured Convex Optimization through the Lens of Variational Analysis
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Xiaoming Yuan;Shangzhi Zeng;Jin Zhang
中科院分区：
文献类型：
--
作者：
Xiaoming Yuan;Shangzhi Zeng;Jin Zhang
尽管文献丰富，交替方向乘子法（ADMM）的线性收敛性尚未得到充分理解，即使是凸的情况下。例如，ADMM的线性收敛可以在统计、机器学习和相关领域的广泛应用中凭经验观察到，而现有的理论结果似乎过于严格而无法满足或过于模糊而无法检查，因此ADMM为什么对这些应用执行线性收敛似乎仍然不清楚。本文利用变分分析的透镜，在凸优化的背景下，系统地研究了ADMM的局部线性收敛性。我们表明，ADMM的局部线性收敛性可以保证没有强凸性的目标函数，以及系数矩阵的满秩假设，或全多面体假设的次微分;它是可能的，以辨别局部线性收敛的各种具体的应用，特别是对一些代表性的模型中出现的统计学习。我们使用一些变分分析技术，并进行了分析，在最一般的近端版本的ADMM与福廷和Glowinski的较大的步长，使所有主要的变体的ADMM在文献中已知的覆盖。
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.