基于交替方向乘子法的非光滑损失坐标优化算法

1、基于交替方向乘子法的非光滑损失坐标优化算法 文章编号：10019081（2013）07191205 doi：10.11772/j.issn.10019081.2013.07.1912 摘 要： 交替方向乘子法（admm）在机器学习问题中已有一些实际应用。针对大规模数据的处理和非光滑损失凸优化问题，将镜面下降方法引入原admm批处理算法，得到了一种新的改进算法，并在此基础上提出了一种求解非光滑损失凸优化问题的坐标优化算法。该算法具有操作简单、计算高效的特点。通过详尽的理论分析，证明了新算法的收敛性，在一般凸条件下其具有目前最优的收敛速度。最后与相关算法进行了对比，实验结果表明该算法在保证解稀疏性

2、的同时拥有更快的收敛速度。 关键词：机器学习；交替方向乘子法；坐标优化；大规模；非光滑损失 中图分类号：tp301 文献标志码：a 英文标题 new coordinate optimization method for nonsmooth losses based on alternating direction method of multipliers 英文作者名 gao qiankun*， wang yujun， wang jingxiao 英文地址（ the 11th department， chinese peoples liberation army officer academy

3、， hefei anhui 230031， china英文摘要） abstract： alternating direction method of multipliers （admm） already has some practical applications in machine learning field. in order to adapt to the largescale data processing and nonsmooth loss convex optimization problem， the original batch admm algorithm was i

4、mproved by using mirror descent method， and a new coordinate optimization algorithm was proposed for solving nonsmooth loss convex optimization. this new algorithm has a simple operation and efficient computation. through detailed theoretical analysis， the convergence of the new algorithm is verifie

5、d and it also has the optimal convergence rate in general convex condition. finally， the experimental results compared with the stateofart algorithms demonstrate it gets better convergence rate under the sparsity of solution. alternating direction method of multipliers （admm） already has some practi

6、cal applications in machine learning problem. in order to adapt to the largescale data processing and nonsmooth loss convex optimization problem， the original batch admm algorithm had been improved by using mirror descent method， and proposed a new coordinate optimization algorithm for solving nonsm

7、ooth loss convex optimization base on it. this new algorithm has a simple operation and efficient computing. through detailed theoretical analysis， it was proved that the convergence of the new algorithm and it also has the optimal convergence rate in general convex condition. finally， the experimen

8、tal results compared with the stateofart algorithms demonstrate it gets better convergence rate under the sparsity of solution. 英文关键词key words： machine learning； alternating direction method of multipliers （admm）； coordinate optimization； largescale； nonsmooth loss 0 引言 当前，在机器学习领域大多机器学习问题1最终可以归结为凸优化

9、问题2进行求解。交替方向乘子法（alternating direction method of multipliers， admm）是一种一阶的对偶凸优化算法，它最早由gabay等3提出。最近几年，该算法由于在众多领域（图像处理、机器学习等）都具有高效的实际应用而越来越受关注4-7。正如文献5中所说，交替方向乘子法“至少是一种可以与许多专业算法相比拼的算法，并且在大多数时候，简单形式的交替方向乘子法就已经足够高效可行”。 经典的凸优化算法还有很多，但是对于大规模机器学习问题，即使计算复杂度很低的一阶批处理算法（如梯度下降、admm等）仍没法快速有效求解甚至无法求解，因为要获得目标函数的一阶信息

10、（梯度）必须遍历所有样本所有维的信息。坐标优化方法8由于一次迭代更新只处理所有样本单维信息，计算与存储的开销大大减少，从而使得快速处理大规模数据成为可能。 但正如文献9中所说针对非光滑损失凸优化问题的坐标优化方法研究还很欠缺，为此本文通过对原admm批处理算法进行改进，得到一种新的求解非光滑损失凸优化问题的坐标优化算法。针对一般凸优化问题，该算法在理论上拥有最优的收敛速度，并且在相关的数值实验中表现优异。 1 基础知识介绍 以二分类机器学习问题为例，对于给定独立同分布的训练样本集s=（x1，y1），（xm，ym）rn-1，+1，其中yi是样本xi的标签，“损失函数+正则化项”的凸优化模型如下：

11、 minw f（w）+g（w）；wrn， f（w）=1mmi=1li（w；xi，yi） g（w）=r（w）（1） f（w）称为损失项，其中每个li（w；xi，yi）是单个样本（xi，yi）所造成的损失，该项控制了训练模型的精度，本文主要考虑非光滑hinge损失：li（w；xi，yi）=max0，1-yiw，xi。g（w）称为正则化项，主要用于避免模型的过拟合提高泛化性，本文主要考虑l1正则化项即r（w）=w11，该正则化项在一定条件下可以保证优化问题解的稀疏性（大多维数为零）。参数是一可调常数，该参数的适当选取可以得到兼有训练精度和泛化能力的模型。 为了适应交替方向乘子法的优化模型5，本文将原

12、优化问题（1）转换为如下等价双变量优化问题： min f（u）=f（w）+g（z） s.t. w-z=0；wrn，zrn（2） 其中u=（w，z），原交替方向乘子法（admm）第t次迭代更新步骤如下（为可调参数）： wt+1=argminwf（w）+t，w-zt+2w-zt22 zt+1=arg minzg（z）+t，wt+1-z+2wt+1-z22 t+1=t+（wt+1-zt+1）（3） 其中rn为增添的对偶变量。2011年，he等4在理论上证明了式（3）迭代更新所得解最终收敛至优化问题（2）的最优解，且变分不等式收敛速度为o（1/t）。仔细观察式（3），可以看出上述迭代更新过程中w的更新

13、涉及到所有样本信息，因此该算法并不适用于处理大规模数据优化问题。 坐标优化作为处理大规模稀疏数据特别是文本数据的首选算法10，它的思路非常简单，主要是对高维优化问题采取各个击破的方法分而治之，具体的计算步骤就是固定其他维坐标，一次仅对选中的一维坐标进行优化求解。相对于传统的批处理算法，坐标优化每一步迭代仅需要求解单维关于所有样本的优化问题。 2 算法介绍 当优化模型所采用损失项非光滑时，admm算法w的更新就无法用二阶近似展开求解也无法直接采用坐标优化方法求解。为了适应坐标优化方法，本文采用镜面下降（mirror descent）11方法对损失项进行了线性展开，展开后更新形式如下： wt+1=

14、argminwf（wt），w+12tw-wt22+ t，w-zt+2w-zt22（4） 其中：t为迭代步长，f（wt）为损失项当前的（次）梯度。对于hinge损失，其次梯度计算如下： f（wt）=1mmi=1li（wt；xi，yi）； li（wt；xi，yi）=-yixi， yiwt，xi 第7期 高乾坤等：基于交替方向乘子法的非光滑损失坐标优化算法 计算机应用 第33卷 通过该线性展开，损失项重新具有了光滑性并且解向量w的更新每维互相独立，为坐标优化方法的采用提够了方便。本文将坐标优化的思想代入改进后的admm算法得到算法1（j表示相应的维坐标）： 算法1 非光滑admm改进算法。 inpu

15、t initialize w0=0， z0=0， 0=0， t=0 repeat set t0 for j=1 to n wt+1j=argminw（f（wt）j，wj+12twj-wtj22+ tj，wj-ztj+2wj-ztj22） zt+1j=argminz（g（zj）+tj，wt+1j-zj+ 2wt+1j-zj22） t+1j=tj+（wt+1j-zt+1j） end t=t+1 until a stopping condition is satisfied z-zt+1， t+1+t+1-，zt+1-wt+1 所以： f（wt）+g（zt+1）-f（w）-g（z）+t+1-v，g（

16、t+1） wt-wt+1， f（wt） +w-wt+1，1t（wt+1-wt） +z-zt+1， t+1-t+1+t+1-，zt+1-wt+1 又因为： wt-wt+1， f（wt）=1t（wt-wt+1），tf（wt） t2f（wt）22+12twt-wt+122 另一式子开始 w-wt+1，1t（wt+1-wt）=12t（w-wt22 -w-wt+122-wt-wt+122） z-zt+1， t+1-t+1=z-zt+1， （zt+1-zt） =2（z-zt22-z-zt+122-zt-zt+122） 另一个式子起始 zt+1-wt+1， t+1-=1（t-t+1）， t+1- =12（t

17、+1-t+122-t+1-t22） +12（-t22-t+122） 12t+1-t+122+12（-t22 -t+122） =12（zt+1-zt）22+ 12（-t22 -t+122） 综上，可以得到： f（wt）+g（zt+1）-f（w）-g（z）+t+1-v，g（t+1） 12t（w-wt22-w-wt+122） +t2f（wt）22+2（z-zt22-z-zt+122） +12（-t22-t+122） 换行，另一个式子 t-1t=0f（wt）+g（zt+1）-f（w）-g（z）+t+1-v，g（t+1） 120w-w022+t-1t=1w-wt2212t-12t-1 +t-1t=0t2

18、f（wt）22+2z-z022 +12-022 （10） 将t=1/t+1和假设代入式（10）得： t-1t=0f（wt）+g（zt+1）-f（w）-g（z）+t+1-v， g（t+1）12m+12mt-1t=1t+1-t +g2tt=11t+2m+12m12mt +g2（1+t11tdt）+（2+12）m t（12m+g）+（2+12）m tt=1f（ut）-f（u）+t-v，g（t） =f（wt）-f（w0）+t-1t=0f（wt）+g（zt+1）-f（w） -g（z）+（t+1-v）tg（t+1） t（12m+g）+（2+12）m+d 其中f（ut）是凸函数，根据g（t）的定义可知t-v，g（t）也是关于变量t的凸函数，因此： f（）-f（u）+-v，g（）1ttt=1f（ut）-f（u） +（t-v）tg（t） 1tt（12m+g） +（2+12）m+d 证毕。 对于随机坐标优化