⚡机器学习⚡交替方向乘数法（Alternating Direction Method of Multipliers，ADMM）

最近研究二次判别分析（Quadratic Discriminant Analysis，QDA），发现运用到了交替方向乘数法（ADMM），就很迷。（关键是太菜）

很多博主都是直接翻译或者搬运的，搜罗且了解了很多相关知识，那就来个大总结及其一些自己的想法吧！

（内力有限，仅供学习交流）

确实很难，理论性很强，没有虚的，阅读完内容需要有“勇气”！

ADMM

背景

咱们先来了解了解，ADMM到底是个什么东西？

交替方向乘数法（Alternating Direction Method of Multipliers），从字面意思上理解，交替方向？是不是很迷？交替计算？交替求解？。。。难道是对偶问题？对偶求解？

先不管了，再看后半句，乘数法？咦~是不是感觉有点熟悉。

la.la.la…Lagrange乘数法？？？

（没错，就是Lagrange，直接干起来，等等，这里只说对了一半，具体咱们下面慢慢道来~）

ADMM是一个不算是太新的算法，其实就是一种求解优化问题的计算框架, 适用于求解分布式凸优化问题，特别是统计学习问题。 ADMM 通过分解协调（Decomposition-Coordination）过程，将大的全局问题分解为多个较小、较容易求解的局部子问题，并通过协调子问题的解而得到大的全局问题的解。

简单的理解就是，整个算法只是整合许多不少经典优化思路，然后结合现代统计学习所遇到的问题，提出了一个比较一般的比较好实施的分布式计算框架。

而他的历史可以追溯到看下面：

ADMM 最早分别由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976年提出，并被 Boyd 等人于 2011 年重新综述并证明其适用于大规模分布式优化问题。由于 ADMM的提出早于大规模分布式计算系统和大规模优化问题的出现，所以在 2011 年以前，这种方法并不广为人知。

作为搞自动化、控制、优化、诊断…的本菜来说，当然是奔着优化求解去学习的。

先来看看一个大佬对目前大数据及其优化的见解，简直是一针见血，说出来我的心声：

业界一直在谈论大数据，对于统计而言，大数据其实意味着要不是样本量增加 n → ∞ n\rightarrow \infty n→∞，要不就是维度的增加 p → ∞ p \rightarrow \infty p→∞，亦或者两者同时增加，并且维度与样本量的增长速度呈线性或者指数型增长。在稀疏性的假设条件下，再加上一些正则性方法，统计学家可以证明各种加penalty的模型所给出的参数估计具有良好的统计性质，收敛速度也有保证，同时还会给出一些比较好的迭代算法，但是，他们并没有考虑真实环境下的所消耗的计算时间。虽然统计学家也希望尽量寻求迭代数目比较少的算法（比如one-step估计），但是面对真实的Gb级别以上的数据，很多时候我们还是无法直接用这些算法，原因是一般的硬件都无法支撑直接对所有数据进行运算的要求。如果想减少抽样误差，不想抽样，又想提高估计的精度，那么还是需要寻求其他思路，结合已有的模型思想来解决这些问题。在目前条件下，并行化、分布式计算是一种比较好的解决思路，利用多核和多机器的优势，这些好算法便可以大规模应用，处理大数据优势便体现出来了。对于统计而言，数据量越大当然信息越可能充分（假设冗余成分不是特别多），因为大样本性质本身就希望样本越多越好嘛。—源自此处

还需要知道的一点，我们都知道搞优化会遇到很多问题，无非是数据量上和维度的变化，关键词大都为：降维，收敛，迭代等等，而这里的ADMM算法不同于那些梯度下降法或其他改进的SGDM、RMSProp、Adam等等更多高级算法，应用的大多为以GB级别的数据量的数据集，如果与SGDM、Adam这些算法在同样的低维数据（这里指的是较GB级别低的）进行比较，收敛速度绝壁没它们好，很慢，实际的收敛速度往往比那些算法慢得多。ADMM的主要应用，主要是在解空间规模非常大的情况下（比如X、Y 都是存储空间上GB的超大规模矩阵），这个时候很多传统的方法不好用，强制需要分块求解，而且对解的绝对精度往往要求也没那么高。所以我觉得这是，需要提前知道的一点。

确实，这个算法很难理解，公式也很难，不敢保证，我能将其解释清楚，抱着互相学习的态度写这篇Blog！（望各位大佬批评指正）

具体结构，从ADMM需要用到的背景知识、ADMM原理、具体应用这几块进行解释。

下面咱们从基本框架结构入手吧~

背景知识

《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》文章中提到了一些预备知识，学过最优化或最优估计等优化课程的童鞋应该能够很快能够理解，对偶问题若很陌生的小伙伴，可以补充补充相关的知识。

先来了解一些基本算法思想吧~

对偶上升

对于凸函数的优化问题，对偶上升法核心思想就是引入一个对偶变量，然后利用交替优化的思路，使得两者同时达到optimal。

读到这里，让我们想起咱们的主题，“交替方向”，是不是有点感觉了。

对于凸函数，我们只需要知道，凸优化问题有一个良好的性质即：局部最优解便是全局最优解

对凸函数有不解的地方，可看这位大佬的博客。

一个凸函数的对偶函数其实就是原凸函数的一个下界，因此可以证明一个较好的性质：在强对偶性假设下，即最小化原凸函数（primal）等价于最大化对偶函数（dual），两者会同时达到optimal。这种转化可以将原来很多的参数约束条件变得少了很多，以利于做优化。具体表述如下：

min ⁡ f ( x ) s . t . A x = b \begin{array}{l} \min \quad f(x) \\s.t.\quad A x=b \end{array} minf(x)s.t.Ax=b​

其中的s.t.约束项，有些地方可能写成“ A x + B z = C Ax+Bz=C Ax+Bz=C”的形式，原理都是一样的，只是多了一个变量而已，不用过于担心，理解到整个算法的思路就好。(先不透露为什么会出现这个公式，哈哈哈哈)

对于对偶问题有所不解的，可以简单理解成为原函数是Y关于X的函数，那么对偶的函数则为X关于Y的函数，这样理解是不是更容易一点呢。

其中 f ( x ) f(x) f(x)为目标函数也即是凸函数，然后拉格朗日干起来，则为：

L ( x , y ) = f ( x ) + y T ( A x − b ) L(x, y)=f(x)+y^{T}(A x-b) L(x,y)=f(x)+yT(Ax−b)

其中 y T y^{T} yT为拉格朗日乘子，对偶的 L ( x , y ) L(x,y) L(x,y)函数为：

g ( y ) = inf ⁡ x L ( x , y ) = − f ∗ ( − A T y ) − b T y g(y)=\inf _{x} L(x, y)=-f^{*}(-A^{T}y)-b^{T}y g(y)=xinf​L(x,y)=−f∗(−ATy)−bTy

对于上式， inf ⁡ \inf inf 代表的是一个下界，之所以用下确界而不是用min，可能是因为有些函数没有极值（定义域取不到），但有一个下确界。

而 y y y 相对于原 L ( x , y ) L(x,y) L(x,y)函数来说，是拉格朗日乘子的对偶变量（这里表现为矩阵的转置）

现在我们来看我们的原问题（Primal）的对偶(Dual）函数：

max ⁡ y g ( y ) \max_y \quad g(y) ymax​g(y)

在强对偶的假设下，原问题和对偶问题的解都是一样的，同时达到最优。

什么是强对偶性？就是指原问题的解与对偶问题的解是相同的，也即是： x ∗ = y ∗ x^{*}=y^{*} x∗=y∗

知道了原问题和对偶的解都是最优解，那么我们是不是可以从对偶问题入手，找到对偶问题的最优解 y ∗ y^{*} y∗，这样就能对应的求得原问题的解 x ∗ x^{*} x∗,

x ∗ = arg ⁡ min ⁡ x L ( x , y ∗ ) x^{*}=\arg \min_{x} L(x, y^{*}) x∗=argxmin​L(x,y∗)

arg 是变元（即自变量argument）的英文缩写。

arg min 就是使后面这个式子达到最小值时的变量的取值>

arg max 就是使后面这个式子达到最大值时的变量的取值

假如 g ( y ) g(y) g(y)可求其导数，那么利用梯度上升法，交替更新参数，使得同时收敛到最优。迭代如下：

x k + 1 : = arg ⁡ min ⁡ x L ( x , y k ) ( x − 最 小 化 步 ) y k + 1 : = y k + α k ∇ g ( y ) = y k + α k ( A x k + 1 − b ) ( 对 偶 变 量 更 新 , α k 是 步 长 ) x^{k+1}:=\arg \min _{x} L\left(x, y^{k}\right) \quad(x -最小化步 ) \\ y^{k+1}:=y^{k}+\alpha^{k} \nabla g(y)=y^{k}+\alpha^{k}\left(A x^{k+1}-b\right) \quad (对偶变量更新, \alpha^{k} 是步长 ) xk+1:=argxmin​L(x,yk)(x−最小化步)yk+1:=yk+αk∇g(y)=yk+αk(Axk+1−b)(对偶变量更新,αk是步长)

由于以上需要的 f ( x ) 、 α f(x)、\alpha f(x)、α条件都非常的苛刻，难以满足其要求，一般应用中都不会用到对偶上升法。

对偶分解

虽然对偶上升的方法有所缺陷，导致我们在实际操作中会遇到重重困难。

但是世界万物都是存在着两面，有其弊也有其利，就如下面的太极双鱼图

那么，我们可以利用其优秀的一面，当目标函数 f f f 是可分的（separable）时候（参数亦或feature可分），整个问题可以拆解成多个子参数问题，分块优化后汇集起来整体更新。

这也就是快接近咱们的主题了，分布式凸优化问题。

我们可以分块，然后并行化处理。

由此，我们可分离的目标函数为：

min ⁡ f ( x ) = ∑ i = 1 N f i ( x i ) s . t . A x = ∑ i = 1 N A i x i = b \min \quad f(x)=\sum_{i=1}^{N} f_{i}\left(x_{i}\right) \\ s.t. \quad Ax=\sum_{i=1}^{N}A_ix_i=b minf(x)=i=1∑N​fi​(xi​)s.t.Ax=i=1∑N​Ai​xi​=b

其中，对 A A A矩阵按照列分开。 x = ( x 1 , x 2 , . . . , x N ) ， A x=(x_1,x_2,...,x_N)，A x=(x1​,x2​,...,xN​)，A 可分解为 A = ( A 1 , A 2 , . . . , A N ) A=(A_1,A_2,...,A_N) A=(A1​,A2​,...,AN​)。

现在，拉格朗日干起来，得到了：

L ( x , y ) = ∑ i = 1 N L i ( x i , y ) = ∑ i = 1 N ( f i ( x i ) + y T A i x i − ( 1 / N ) y T b ) L(x, y)=\sum_{i=1}^{N} L_{i}\left(x_{i}, y\right)=\sum_{i=1}^{N}\left(f_{i}\left(x_{i}\right)+y^{T} A_{i} x_{i}-(1 / N) y^{T} b\right) L(x,y)=i=1∑N​Li​(xi​,y)=i=1∑N​(fi​(xi​)+yTAi​xi​−(1/N)yTb)

由此，可以得知，当程序迭代优化很多次的时候，其中 x x x最小化步长，可拆分为多个子问题来进行并行运算（注意这里的拆分并行和神经网络中批量化Batch_size不同，不会前后影响，如改变 W ^ \hat W W^后批量Normalization会改变 Z Z Z的值，在这里不会），同时也由于是强对偶关系，对偶变量更新不变这对于多特征任务时是很有用的。

x i k + 1 : = arg ⁡ min ⁡ x L i ( x i , y k ) ( 多 个 x i 并 行 最 小 化 步 ) y k + 1 : = y k + α k ∇ g ( y ) = y k + α k ( A x k + 1 − b ) ( 汇 集 整 体 的 x , 然 后 对 偶 变 量 更 新 ) x_{i}^{k+1}:=\arg \min _{x} L_{i}\left(x_{i}, y^{k}\right) \quad\left(\right. 多个 x_{i} 并行最小化步) \\ y^{k+1}:=y^{k}+\alpha^{k} \nabla g(y)=y^{k}+\alpha^{k}\left(A x^{k+1}-b\right) \quad( 汇集整体的 x , 然后对偶变量更新 ) xik+1​:=argxmin​Li​(xi​,yk)(多个xi​并行最小化步)yk+1:=yk+αk∇g(y)=yk+αk(Axk+1−b)(汇集整体的x,然后对偶变量更新)

对偶分解是非常经典的优化方法，可追溯到1960年代。这种思想对后面的分布式优化方法影响较大，比如近期的graph-structure优化问题。（具体可自行查询一下下）

增广的拉格朗日乘数法

增广的拉格朗日乘数法，说到这里，可就太熟悉了，无非就是加上各种惩罚项，L0、L1、L2正则化，lasso套索、岭回归等等。故，在我们上面的 L ( x , y ) L(x,y) L(x,y)拉格朗日项后面加上惩罚项，搞机器学习的都知道，增加惩罚项或正则化，目的是为了扩大我们的约束条件，让一些噪声或者不够到约束的值能够融入进去，SVM的软间隔就是一个很好的例子，具体可自行了解，这里就不扩展开来了。

反正，记住一点即可：增加惩罚项，扩大约束条件的容纳范围，放松假设条件。

可使其收敛的更快。

那么，增加惩罚项的拉格朗日项为：

L ρ ( x , y ) = f ( x ) + y T ( A x − b ) + ρ 2 ∥ A x − b ∥ 2 2 L_{\rho}(x, y)=f(x)+y^{T}(A x-b)+\frac{\rho}{2}\|A x-b\|_{2}^{2} Lρ​(x,y)=f(x)+yT(Ax−b)+2ρ​∥Ax−b∥22​

其中，最后加了的L2正则化，二范数，也就是岭回归优化项就是惩罚项。 ρ \rho ρ 则为我们的松弛因子（惩罚系数），用于更加精细的调节扩大的范围边界。

我们可以将其等价为优化的目标函数形式：

min ⁡ f ( x ) + ρ 2 ∥ A x − b ∥ 2 2  s.t.  A x = b \begin{array}{lc} \min & f(x)+\frac{\rho}{2}\|A x-b\|_{2}^{2} \\ \text { s.t. } & A x=b \end{array} min s.t. ​f(x)+2ρ​∥Ax−b∥22​Ax=b​

我们增加的惩罚函数的好处是为了让对偶函数

g ρ ( y ) = inf ⁡ x L ρ ( x , y ) g_{\rho}(y)=\inf _{x} L_{\rho}(x, y) gρ​(y)=xinf​Lρ​(x,y)

更具有可导性，更新参数的计算过程和对偶上升的一致。除最小化 x x x的时候加上惩罚项：

x k + 1 = arg ⁡ min ⁡ x L ρ ( x , y k ) y k + 1 = y k + ρ ( A x k + 1 − b ) \begin{aligned} x^{k+1} &=\arg \min _{x} L_{\rho}\left(x, y^{k}\right) \\ y^{k+1} &=y^{k}+\rho\left(A x^{k+1}-b\right) \end{aligned} xk+1yk+1​=argxmin​Lρ​(x,yk)=yk+ρ(Axk+1−b)​

由于我们更新的 x 、 y x、y x、y参数中都包含有惩罚项，其中 y y y的更新参数中， α \alpha α步长则变为了惩罚项中的松弛因子 ρ \rho ρ，由此原函数 f ( x ) f(x) f(x)则不需要满足严格凸函数的限制了，在此条件下其对偶函数和原函数也能同时达到最优求解。

解除严格凸函数的限制的任务已经完成了，但是同时又存在另外一个问题，当增加惩罚项后，其平方项写成矩阵形式无法是用之前那种分块形式的，因此，在更新 x x x最小化时，无法做到并行优化多个 x i x_i xi​参数，关于新的问题的解决办法，ADMM则杀出重围了！！！

ADMM算法原理

在上述的层层递进的方法中，你是否也发现了其中的奥秘，对偶上升法解决了可分解性问题，增广乘子法解决了严格的凸函数限制条件，增强了收敛性。那么是否，我们可以将二者集合在一起，取其各自的优点呢？

答案当然是肯定的，那就是ADMM算法，同时解决了将原函数进行分解和扩展函数的约束范围问题。使得 f ( x ) f(x) f(x)能够适应于更多的更广泛的约束条件求解问题。

结合两者的优点，就有了下式目标函数：

min ⁡ f ( x ) + g ( z ) s . t . A x + B z = c \begin{array}{lc} \min & f(x)+g(z) \\ s . t . & A x+B z=c \end{array} mins.t.​f(x)+g(z)Ax+Bz=c​

从中，我们可以看出，优化后的目标函数增加了新的变量 g ( z ) g(z) g(z)，约束条件则增加了 B z Bz Bz，可以看出，我们将原 X X X分解了，原始变量和目标函数都拆分开了，对于原论文中的解释，感觉有一些蹊跷。但简单的理解就是将最初的原始变量就拆分为 x x x和 z z z两个变量，这样在后面的优化求解中，就不需要在融合到一起，最后求解出来也是两个值，也即是从一开始就将其分解开来。保证了前面优化过程的可分解性。

紧接着，我们的增广拉格朗日项：

L ρ ( x , z , y ) = f ( x ) + g ( z ) + y T ( A x + B z − c ) + ( ρ / 2 ) ∥ A x + B z − c ∥ 2 2 L_{\rho}(x, z, y)=f(x)+g(z)+y^{T}(A x+B z-c)+(\rho / 2)\|A x+B z-c\|_{2}^{2} Lρ​(x,z,y)=f(x)+g(z)+yT(Ax+Bz−c)+(ρ/2)∥Ax+Bz−c∥22​

和上面的增广拉格朗日一样，只不过增加了新的变量 z z z而已。

于是ADMM的优化就变成了如下序贯型迭代（这正是被称作alternating direction交替方向的缘由）：

x k + 1 = arg ⁡ min ⁡ x L ρ ( x , z k , y k ) z k + 1 = arg ⁡ min ⁡ z L ρ ( x k + 1 , z , y k ) y k + 1 = y k + ρ ( A x k + 1 + B z k + 1 − c ) \begin{aligned} x^{k+1} &=\arg \min _{x} L_{\rho}\left(x, z^{k}, y^{k}\right) \\ z^{k+1} &=\arg \min _{z} L_{\rho}\left(x^{k+1}, z, y^{k}\right) \\ y^{k+1} &=y^{k}+\rho\left(A x^{k+1}+B z^{k+1}-c\right) \end{aligned} xk+1zk+1yk+1​=argxmin​Lρ​(x,zk,yk)=argzmin​Lρ​(xk+1,z,yk)=yk+ρ(Axk+1+Bzk+1−c)​

可以看出，每次迭代分为三步：

1. 求解与 x x x 相关的最小化问题，更新变量 x x x
2. 求解与 z z z 相关的最小化问题，更新变量 z z z
3. 更新对偶变量 u u u

ADMM名称中的“乘子法”是指这是一种使用增广拉格朗日函数（带有二次惩罚项）的对偶上升（Dual Ascent）方法，而“交替方向”是指变量 x 和 z 是交替更新的。两变量的交替更新是在 f ( x ) f(x) f(x)或 g ( z ) g(z) g(z)可分时可以将优化问题分解的关键原因。

到此，通过以上的内容来理解“交替方向乘数法（ADMM）”是不是就豁然开朗了许多，开篇说很难，其实是不是并没有那么的难。

其实，还有一个更为简洁的缩放形式（Scaled form），令 u = ( 1 / ρ ) y u = (1/\rho)y u=(1/ρ)y，也就是对对偶变量做了缩放处理，对 A x + B z = c Ax+Bz=c Ax+Bz=c进行配方，得

x k + 1 = arg ⁡ min ⁡ x L ρ ( x , z k , y k ) = arg ⁡ min ⁡ ( f ( x ) + ( ρ / 2 ) ∥ A x + B z k − c + u k ∥ 2 2 ) z k + 1 = arg ⁡ min ⁡ z L ρ ( x k + 1 , z , y k ) = arg ⁡ min ⁡ ( g ( z ) + ( ρ / 2 ) ∥ A x k + 1 + B z − c + u k ∥ ) u k + 1 = u k + A x k + 1 + B z k + 1 − c \begin{array}{l} x^{k+1}=\arg \min _{x} L_{\rho}\left(x, z^{k}, y^{k}\right)=\arg \min \left(f(x)+(\rho / 2)\left\|A x+B z^{k}-c+u^{k}\right\|_{2}^{2}\right) \\ z^{k+1}=\arg \min _{z} L_{\rho}\left(x^{k+1}, z, y^{k}\right)=\arg \min \left(g(z)+(\rho / 2)\left\|A x^{k+1}+B z-c+u^{k}\right\|\right) \\ u^{k+1}=u^{k}+A x^{k+1}+B z^{k+1}-c \end{array} xk+1=argminx​Lρ​(x,zk,yk)=argmin(f(x)+(ρ/2)∥∥​Ax+Bzk−c+uk∥∥​22​)zk+1=argminz​Lρ​(xk+1,z,yk)=argmin(g(z)+(ρ/2)∥∥​Axk+1+Bz−c+uk∥∥​)uk+1=uk+Axk+1+Bzk+1−c​

当然，写成这种形式有利于后面简化优化问题，也可不作任何的处理。

具体应用

大佬回答及点评

ADMM( Alternating Direction Method of Multipliers)算法是机器学习中比较广泛使用的约束问题最优化方法，它是ALM算法的一种延伸，只不过将无约束优化的部分用块坐标下降法（block coordinate descent，或叫做 alternating minimization）来分别优化。产生这种方法主要是为了弥补二次惩罚的缺点。

在一些问题当中，用二次惩罚来近似约束问题在最优点附近需要惩罚项的系数趋近于无穷，而这种要求会使得海森矩阵很大，因此近似的目标函数很不稳定。为了解决这个问题，引入了线性逼近的部分，通过线性项系数不断的接近最优解（对偶上升），使得在二次惩罚项的系数很小的情况下，也能得到满足要求精度的解。ADMM目前是比较成熟，比较受欢迎的约束问题最优化通用框架。（引用源自知乎大佬）

在这里，关于知乎大佬的回答，我说两句。从上面的对偶上升，我们发现了可以解决分解性问题，通过交替更新 x 、 y x、y x、y参数，但实际的 f ( x ) f(x) f(x)是很难满足，故将加入新变量 g ( z ) g(z) g(z)来提前分解原始变量，这样就解决了第一个问题；同时又引入了增广的拉格朗日乘数法，也即增加惩罚项，来改进扩大其求解范围，使得 f ( x ) f(x) f(x)的约束更小，适应性更好。

受约束的凸优化问题

一般的受约束的凸优化问题可以写成如下形式：

min ⁡ f ( x )  s.t  x ∈ C \begin{array}{ll} \min & f(x) \\ \text { s.t } & x \in \mathcal{C} \end{array} min s.t ​f(x)x∈C​

可将此类型写成ADMM形式，增加新变量，以分解原始变量：

min ⁡ f ( x ) + g ( z )  s.t  x − z = 0 \begin{array}{l} \min \quad f(x)+g(z) \\ \text { s.t } \quad x-z=0 \end{array} minf(x)+g(z) s.t x−z=0​

相应的增广拉格朗日项为：

L ρ ( x , z , u ) = f ( x ) + g ( z ) + ( ρ / 2 ) ∥ x − z + u ∥ 2 2 L_{\rho}(x, z, u)=f(x)+g(z)+(\rho / 2)\|x-z+u\|_{2}^{2} Lρ​(x,z,u)=f(x)+g(z)+(ρ/2)∥x−z+u∥22​

其中的 g g g 函数即 C C C 的示性函数，上述是scaled形式，那么具体算法就是:

x k + 1 = arg ⁡ min ⁡ ( f ( x ) + ( ρ / 2 ) ∥ x − z k + u k ∥ 2 2 ) z k + 1 = Π C ( x k + 1 + u k ) u k + 1 = u k + x k + 1 − z k + 1 \begin{aligned} x^{k+1} &=\arg \min \left(f(x)+(\rho / 2)\left\|x-z^{k}+u^{k}\right\|_{2}^{2}\right) \\ z^{k+1} &=\Pi_{\mathcal{C}}\left(x^{k+1}+u^{k}\right) \\ u^{k+1} &=u^{k}+x^{k+1}-z^{k+1} \end{aligned} xk+1zk+1uk+1​=argmin(f(x)+(ρ/2)∥∥​x−zk+uk∥∥​22​)=ΠC​(xk+1+uk)=uk+xk+1−zk+1​

示性函数，顾名思义，是表示自变量性态的一个函数。

统计学习中的应用

统计学习问题也是模型拟合问题（我们知道有拟合和过拟合），可表示为：

min ⁡ l ( D , d , z ) + r ( z ) \min l(D,d,z)+r(z) minl(D,d,z)+r(z)

• 其中， z ∈ R n z\in R^{n} z∈Rn代表待学习的参数
• D ∈ R m × m D\in R^{m\times m} D∈Rm×m是模型的输入数据集
• d ∈ R m d\in R^{m} d∈Rm是模型的输出数据集
• l : R m × n × R m × R n l:R^{m\times n}\times R^{m} \times R^{n} l:Rm×n×Rm×Rn是损失函数
• r : R n → R r:R^{n}\rightarrow R r:Rn→R是正则化项
• m m m代表的是数据的个数， n n n表示的是特征的个数

1. 对于带L1正则化项的线性回归（Lasso），其平方损失函数为

   l ( D , d , z ) = ( 1 / 2 ) ∥ D z − d ∥ 2 2 l(D, d, z)=(1 / 2)\|D z-d\|_{2}^{2} l(D,d,z)=(1/2)∥Dz−d∥22​

2. 对于逻辑回归（Logistic Regression），其极大似然损失函数为

   l ( D , d , z ) = 1 T ( log ⁡ ( exp ⁡ ( D z ) + 1 ) − D z d T ) l(D, d, z)=\mathbf{1}^{T}\left(\log (\exp (D z)+\mathbf{1})-D z d^{T}\right) l(D,d,z)=1T(log(exp(Dz)+1)−DzdT)

3. 对于线性支持向量机（Linear Support Vector Machine），其合页（Hinge）损失函数为

   l ( D , d , z ) = 1 T ( 1 − D z d T ) + l(D, d, z)=\mathbf{1}^{T}\left(\mathbf{1}-D z d^{T}\right)_{+} l(D,d,z)=1T(1−DzdT)+​

将训练数据在其原始样本M维度下将其划分为N块：

D = ( D 1 ⋮ D N ) , d = ( d 1 ⋮ d N ) D=\left(\begin{array}{c} D_{1} \\ \vdots \\ D_{N} \end{array}\right), d=\left(\begin{array}{c} d_{1} \\ \vdots \\ d_{N} \end{array}\right) D=⎝⎜⎛​D1​⋮DN​​⎠⎟⎞​,d=⎝⎜⎛​d1​⋮dN​​⎠⎟⎞​

由此我们可得到分块的目标函数来实现分布式计算：

min ⁡ ∑ i = 1 N l i ( D i , d i , x i ) + r ( z ) s . t . x i − z = 0 ( i = 1 , 2 , . . . , N ) \min \quad \sum_{i=1}^{N} l_i(D_i,d_i,x_i)+r(z) \\ s.t. \quad x_i-z=0 \quad (i=1,2,...,N) mini=1∑N​li​(Di​,di​,xi​)+r(z)s.t.xi​−z=0(i=1,2,...,N)

相应的简洁迭代更新 D 、 d 、 x D、d、x D、d、x的计算方式为：

x i k + 1 : = arg ⁡ min ⁡ x i ( l i ( D i , d i , x i ) + ( ρ / 2 ) ∥ x i − z k + u i k ∥ 2 2 ) z k + 1 : = arg ⁡ min ⁡ z ( r ( z ) + ( N ρ / 2 ) ∥ z − x ˉ k + 1 − u ˉ k ∥ 2 2 ) u i k + 1 : = u i k + x i k + 1 − z k + 1 \begin{array}{l} x_{i}^{k+1}:=\arg \min _{x_{i}}\left(l_{i}\left(D_{i}, d_{i}, x_{i}\right)+(\rho / 2)\left\|x_{i}-z^{k}+u_{i}^{k}\right\|_{2}^{2}\right) \\ z^{k+1}:=\arg \min _{z}\left(r(z)+(N \rho / 2)\left\|z-\bar{x}^{k+1}-\bar{u}^{k}\right\|_{2}^{2}\right) \\ u_{i}^{k+1}:=u_{i}^{k}+x_{i}^{k+1}-z^{k+1} \end{array} xik+1​:=argminxi​​(li​(Di​,di​,xi​)+(ρ/2)∥∥​xi​−zk+uik​∥∥​22​)zk+1:=argminz​(r(z)+(Nρ/2)∥∥​z−xˉk+1−uˉk∥∥​22​)uik+1​:=uik​+xik+1​−zk+1​

（完结撒花❀）

个人见解

最后说两句，虽然优化算法千千万，在不同时期，随着科技的发展与进步，老的算法暂时过时，新的算法逐步崛起，但终归要落实到实际应用当中才是真正的好算法，并不是说一味的提高求解速度，提高精度，有些时候成本会很高，有些时候老的算法会被拾起成为yyds，新的算法未必就好。终究说来，希望能够有更多更实际应用范围更加广泛的优化算法逐步崛起吧~

Reference

• http://maths.nju.edu.cn/~hebma/slides/20C.pdf
• https://www.zhihu.com/question/36566112/answer/79535746
• http://shijun.wang/2016/01/19/admm-for-distributed-statistical-learning/
• http://www-scf.usc.edu/~yuhao/journal/SimpleParallel-SIOPT-2017.pdf
• Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends® in Machine Learning, 2011, 3(1): 1-122.
• Eckstein J, Yao W. Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives[J]. Pac. J. Optim., 2014.
• Lusk E, Huss S, Saphir B, et al. MPI: A Message-Passing Interface Standard Version 3.1[J], 2015.
• Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

❤坚持读Paper，坚持做笔记，坚持学习❤！！！

⚡To Be No.1

⚡⚡哈哈哈哈

学习DeepLearning坚持！30天计划！！！

打卡 第 5 /30 Day!!!

⚡创作不易⚡，过路能❤关注、收藏、点个赞❤三连就最好不过了

ღ( ´･ᴗ･` )

❤

『

When you think your life sucks, just think to yourself about how many people have it worse.

』