ADMM 框架小结

July 07, 2014

ADMM 是这两年很火的一个算法框架。

其主要的提出想法是为了“分布式”的解决一类问题,即: \(min f(x) + g(y) s.t. Ax + By = c\) 是等式约束(不可以是不等式)的最小化加和问题;且此时 f(x) 和 g(y) 是两类性质非常不同的函数,比如 LASSO 中的 1-norm 惩罚和前面的代价函数。

对于这个问题的 augmentated Lagrangian:

\[L_{\rho}(x,z,y)=f(x)+g(z)+y^T(Ax+Bz-c)+(\rho/2)\|Ax+Bz-c\|_2^2\]

和对应的 update rule:

\[x^{k+1}=\arg\min_x L_{\rho}(x,z^k,y^k)\] \[z^{k+1}=\arg\min_z L_{\rho}(x^{k+1},z,y^k)\] \[y^{k+1}=y^k+\rho(Ax^{k+1}+Bz^{k+1}-c)\]

可以看出,上图中的第一个式子和第二个式子是乘子法的一个特殊化;且第一个式子对应的是乘子法中的”x-minimization step”,第二个式子是所谓的“dual update”。

不同的是,乘子法是同时计算并最小化x,z: \((x^{k+1},z^{k+1})=\arg\min_{x,z} L_{\rho}(x,z,y^k)\)

而ADMM中,x,z 是“alternated”计算的,它 decouples x-min step from y-min step。

这里可以看到,augmentated Lagrangian 虽然弱化了乘子法的强假设性,但 x-min step 引入了二次项而导致无法把 x 分开进行求解。所以 ADMM 也是就是期望结合乘子法的弱条件的收敛性以及对偶上升法的可分解求解性。

其实 ADMM 也是一个需要 trick 的框架:

  1. 因为它的缺点是需要非常多步的迭代才能得到相对精确的解,这就好像是一阶算法。

  2. 另外,对 $\rho$ 的选择也很重要,非常影响收敛性;$\rho$ 太大,对于 min (f1+f2) 就不够重视;反之,则对于 feasibility 又不够重视。Boyd et al. (2010) 倒是给了实践中改变 $\rho$ 的策略,可是也没有证明它的收敛性。

Boyd 在其网站上给出了一些例子。总结这里的几个例子,构造 ADMM 的形式,主要思想就是往直前的受约束的凸优化问题靠拢。 (1)对于只有传统损失函数没有正则项的(比如LAD, Huber Fitting),构造出一个 z。 (2)对于有约束的,比如 l1-norm 的约束,则把约束变成 g(x),原始损失函数为 f(x)。若 f(x) 本身没有(比如Basic Pursuit),就构造成带有定义域约束的 f(x)(某种投影);如果有,则就是比较一般化的损失+正则问题,这时候就基本是一个\(f(x)+\lambda\|z\|_1\)的形式。是非常自然的 ADMM。

所以,像广义线性模型和广义可加模型+正则等等都非常适合 ADMM。

Ref:

[1] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, 2010.

[2] S. Boyd. Alternating Direction Method of Multipliers (Slides)

Highway Networks and Deep Residual Networks

Recently, a breakthrough news spread over social networks. In this post, I will explain this ResNet as a special case of Highway Networks, which has been proposed before. Both of the work is amazing and thought-provoking. Continue reading

NIPS 2015 Deep Learning Symposium Part II

Published on January 09, 2016

NIPS 2015 Deep Learning Symposium Part I

Published on December 11, 2015