机器学习中的交替方向乘子法

第1章绪论 优化是信号处理、机器学习等需要做数学建模的研究领域的支撑技术.AAAI会士、华盛顿大学教授P.Domingos曾提出如下著名的公式[17]: 机器学习=表示+优化+评估， 可见优化在机器学习中的重要性. 除了应用广泛的无约束优化问题(可参见文献[56])，很多数学模型也可以被建模成或重写成带约束的优化问题.约束可以为数学模型增加更多的先验知识(例如非负性、有界性等)，也可以为了方便求解而引入(例如使用辅助变量).交替方向乘子法(ADMM)是求解带约束问题的有力工具，包括经典的线性等式约束、目标函数可分离的问题和一般的非线性或不等式约束的问题.受限于熟悉程度，本书主要介绍机器学习界研究的ADMM. 1.1机器学习中的带约束优化问题举例 我们给出三个可以使用ADMM求解的代表性机器学习问题.**个是经典的鲁棒主成分分析(RPCA)模型[10]，第二个是分布式优化中应用广泛的一致性(Consensus)模型，第三个是非负矩阵填充模型[94]. RPCA模型[10]将一个观测矩阵分解成一个低秩矩阵和一个稀疏矩阵，该模型可以建模成如下带线性约束、目标函数可分离的凸优化问题: (1.1) 其中表示核范数，定义为矩阵奇异值之和，表示.1范数à，定义为矩阵元素绝对值之和，这两个范数分别是秩函数和范数的凸松弛.在实际应用中，观测矩阵M可能被噪声污染.相应地，我们可以改为求解如下问题: (1.2) 其中统一表示矩阵的弗罗贝尼乌斯(Frobenius)范数和向量的欧几里得(Euclid)范数.在某些实际应用中，的维度可能很大，因此计算它的奇异值分解见定义不可行.为了节省计算时间，人们常将低秩矩阵分解成两个小得多的矩阵的乘积，并求解如下替代问题: (1.3) 这是因为.另一方面，有时我们想直接使用秩函数和.范数，而不是它们的凸松弛，因此会求解如下非凸问题: (1.4) 问题(1.1)和(1.2)分别是具有两个变量块和三个变量块的凸优化问题，而问题(1.3)和(1.4)是非凸问题.所有这些问题都可以使用相应形式的ADMM求解，并保证一定的收敛性. 第二个例子是一致性问题[8].我们希望在分布式环境下*小化m个函数的和，问题描述如下 (1.5) 其中个节点构成了一个连通无向网络，由于存储限制或隐私考虑，局部函数的信息只能由节点获得，其他节点无法获得.当网络有一个中心节点时，我们可以将上述问题重写成如下等式约束的*优化问题: 其中中心节点负责更新，其他工作节点负责更新.当网络没有中心节点时，我们无法使用约束，这是由于现在我们没有一个中心节点来计算.在这种情况下，如果网络中的一条边连接了节点和，我们可以把这条边关联一个变量.于是问题(1.5)就可以重写成如下*优化问题: 其中E表示边的集合.上述两个问题都可以使用ADMM有效求解(分别见6.1节和6.2节). 第三个例子是非负矩阵低秩填充模型[94]，该模型在降维、文本挖掘、协同过滤、聚类等问题中应用广泛.该模型描述如下 (1.6) 其中b是矩阵X中被噪声污染的观测数据;Ω是矩阵中被观测到的元素的位置的集合;PΩ是一个线性映射，它从矩阵中选择位置在集合Ω中的元素.直接求解上述问题不太容易，我们可以通过引入辅助变量Y和e重写为下述问题 (1.7) 其中χ为指示函数: 重写之后的问题(1.7)可以使用多变量块ADMM有效求解. 1.2ADMM的代表性工作综述 ADMM首先由Glowinski和Marrocco[28]以及Gabay和Mercier[24]在20世纪70年代中期提出.ADMM原来在机器学习领域并不受关注，直到人们在2010年左右使用它来求解低秩问题，例如RPCA[10]和低秩表示模型[60]，那时稀疏和低秩学习是机器学习的研究热点.较早的工作包括文献[10，55，58，60，83].Boyd等的教程[8]对ADMM在机器学习领域的推广也起到了很大作用. ADMM在求解凸问题时的收敛性被很多人证明，例如Gabay[22]以及Eckstein和Bertsekas[19].但是其收敛速度一直悬而未决，直到He和Yuan[38]于2012年使用变分不等式证明了遍历意义下(也就是考虑迭代序列的平均)的收敛速度，其中k表示迭代次数.为了使ADMM的子问题容易求解，很多人通过线性化增广项以及光滑目标函数将ADMM扩展到线性化版本，见文献[31，58，79，89]等.一些研究者(见文献[73]和[52])将线性化ADMM和Nesterov加速结合.但是对于一般凸的问题，收敛速度并没有提升，仍然是O(1/k).若假设光滑性和强凸性，则可以得到更快的收敛速度.与遍历意义下的收敛速度相比，人们可能对非遍历意义下(即*后一次迭代点)的收敛速度更感兴趣.非遍历意义下的收敛速度首先由He和Yuan[39]于2015年给出，之后由Davis和Yin[14]于2016年扩展.他们证明了对一般凸问题ADMM具有O(1/√k)的收敛速度，Davis和Yin[14]进一步证明了这个速度是紧的.ADMM*初是用来求解两个变量块的问题的，即变量被分成两组，每一组中的变量同时更新，但是机器学习中的很多模型都有多块变量.将两变量块ADMM直接套用在多变量块凸优化问题上的做法在实践中很常见，并且在某些问题上看起来是有效的，例如文献[83]，但这么做是否会收敛并不清楚.Chen等[13]首先举出了反例，证明了将两变量块ADMM直接应用到多变量块凸问题上不一定能收敛.因此，为了保证收敛，我们需要做一些调整，例如添加高斯回代(GaussianBackSubstitution)[33]或收缩步骤(ContractiveStep)[32]或使用并行分裂(ParallelSplitting)[34，57，61]等à.ADMM*初是用来求解带线性约束的凸优化问题的，为了更广泛地应用，一些研究者将它扩展到更一般的约束，包括线性等式约束、线性不等式约束和非线性约束，见文献[26].基于学习的ADMM是近来一个很有意思的研究课题，它将迭代算法看作一个结构化的深度神经网络，通过松弛ADMM中的参数为可学习的，从而使得算法更适合于特定的数据或问题，见文献[92，96].但是基于学习的ADMM目前尚不成熟，只有文献[92]给出了一些理论分析. 非凸ADMM作为近年来的研究热点之一，已被很多人研究(见文献[7，43，47，51，90])，特别是使用布雷格曼距离的邻近ADMM[87].Zhang和Luo[99]提出了另一个邻近ADMM，它使用了到所有历史迭代的指数平均的布雷格曼距离，而不是到前一次迭代.上述工作用于求解带线性约束的非凸问题.另一方面，Gao等[25]提出了一个求解多线性约束问题的非凸ADMM，这类问题在机器学习中有着广泛的应用，例如非负矩阵分解[30]、RPCA[10]和训练神经网络[54，85].求解带一般非线性甚至非凸约束的问题的ADMM的研究要少得多，相关工作主要集中在增广拉格朗日法(AugmentedLagrangianMethod)，见文献[76]及其中的参考文献. 在机器学习和统计学中，目标函数多是期望形式，随机变量与数据样本关联.这时，我们一般使用随机算法*小化期望形式的目标函数，即每次迭代只随机选择一个或多个样本作为全样本下的对应量的估计进行计算，因此极大地减少了计算量.随机ADMM较早的工作有文献[72]和[82]等，当目标函数是凸函数时，随机ADMM具有O(1/√k)的收敛速度.Azadi等[4]进一步将随机ADMM与Nesterov加速相结合，同样给出了O(1/√k)的收敛速度.另一方面，当目标函数是有限个子函数的平均但函数的个数不是太多时，方差缩减(VarianceReduction，VR)是控制随机梯度的方差并加速算法收敛的有效技术(例如，见文献[15，48，77]).方差缩减技术被Zhong和Kwok[101]及Zheng和Kwok[100]等扩展到随机ADMM，并得到了O(1/k)的遍历意义下的收敛速度.Fang等[20]和Liu等[63]进一步将方差缩减和Nesterov加速结合，在适当条件下得到了在阶上更快的收敛速度.在非凸优化中，随机ADMM同样有人研究[44].近来Huang等[45]和Bian等[6]使用另一种被称为随机路径积分差分估计子(StochasticPath-IntegratedDifferentialEstimatoR，SPIDER)[21]的强有力的方差缩减技术，无论目标函数是有限个子函数的和还是无限个的，都能得到更快的收敛速度. 在分布式优化中使用ADMM求解具有中心节点的一致性问题可以追溯到20世纪80年代[5]，详细描述可见文献[8].当求解一致性问题的分布式网络没有中心节点时，Shi等[81]证明了ADMM等价于线性化增广拉格朗日法(LinearizedAugmentedLagrangianMethod).一般来说，ADMM不是求解无中心分布式优化问题的首选，人们更倾向于原始-对偶算法[50]、线性化增广拉格朗日法[1，80]、梯度跟踪(GradientTracking)法[68，75，93]等.异步是实用分布式优化中的热点课题.Wei和Ozdaglar[91]使用随机ADMM建模异步，即每次迭代随机激活部分节点.Chang等[11，12]给出了一个求解中心化一致性问题的完全异步的ADMM，并给出了收敛性和收敛速度分析.文献[91]和[11，12]主要研究中心化分布式优化中的异步ADMM，关于无中心分布式优化中的异步ADMM的研究相对来说要少得多. 1.3关于本书 在前面一节，我们简要介绍了ADMM的代表性工作.在接下来的章节，我们将详细介绍ADMM及其在不同设定下的各种变种，包括求解凸优化问题的确定性ADMM(第3章)、非凸优化问题的确定性ADMM(第4章)、随机优化问题中的ADMM(第5章)和分布式优化问题中的ADMM(第6章).为了内容的完备性，我们基本上都给出了每个算法的收敛性及收敛速度证明.因为时间有限，也为了保持本书中各个算法之间的差异性(以免读者感到厌烦)，我们并没有介绍前面一节中所有的代表性算法. 本书作为ADMM部分*新进展的有用的参考资料，可作为相关专业的研究生教学参考书，也可供对机器学习和优化感兴趣的研究人员阅读参考. 第2章ADMM的推导 本章将分别从拉格朗日视角和算子分裂视角推导ADMM，前者提供了更多有用的背景和动机. 2.1从拉格朗日视角推导ADMM 我们首先简要介绍两个基于拉格朗日函数的算法，然后导出ADMM. 2.1.1对偶上升法 考虑如下带线性等式约束的凸优化问题 (2.1) 其中f(x)是正常(Proper，见定义A.25)、闭(Closed，见定义A.12)的凸函数(见定义A.4)à.我们可以使用对偶上升法求解该问题.引入拉格朗日函数(见定义A.17): 其中λ是拉格朗日乘子.问题(2.1)的对偶函数(见定义A.18)为 (2.2) 其中f( )表示f( )的共轭函数(见定义A.16).对偶函数d(λ)是凹函数(见定义A.5)并且其定义域为D={λ|d(λ)>-∞}.对偶问题(见定义A.19)定义为 (2.3)