1. 研究目的与意义（文献综述）

1.1课题研究的目的及意义
大数据的产生和存储给传统的集中式机器学习方法带来了巨大的挑战，首先数据规模太大，已经超出了单一机器的存储上限，单机算法也无法对样本进行有效的处理，然后分布式数据的集中式处理又会带来数据采集上的额外开销。
分布式机器学习是一个随着“大数据”这个概念兴起的，有着“分而治之”的思想，其核心目标就是将原本很复杂的问题逐步拆分成多个小问题，然后将这些小问题在多台计算机上进行并行化处理，通过计算机之间的协作，将各个计算机上的结果综合起来得到最终的结果。
一般地基于不同的分布式优化技术，分布式机器学习算法可以分为三类：
基于随机梯度下降的分布式算法（distributed SGD），基本思路是先计算各个机器中的随机梯度，然后主机接收所有机器的随机梯度来优化整个算法的模型参数
基于牛顿方法的分布式算法，在大规模的一致性优化问题中，分布式牛顿算法利用对偶海森矩阵的稀疏性，彻底改动牛顿步的计算，其中对称对角占优矩阵（symmetric diagnoally dominant matrices, SDD）可以分布式计算牛顿方向
基于交替方向乘子法的分布式算法（Distributed Alternating Direction Method of multipliers,Distributed ADMM）,通过Decomposition coordination过程将原来的大的全局性的问题转化为多个较小的、便于求解的局部子问题，通过协调子问题的解来获得原来全局问题的解
ADMM算法最早是1970s Glowinski和Gabay提出的一种可分离凸优化的方法，ADMM算法主要解决带有等式约束的、有两个变量的目标函数的最小化问题，是一种具有对偶分解法（dual decompostion）的分解性、对偶上升法（dual ascent）的强凸条件下的最优解一致性和多乘子法的（multipliers）算法优越的收敛性。相比于增广拉格朗日乘子法，ADMM最明显的优势就是充分利用目标函数的可分解性，实现交替优化。
非负矩阵分解问题（NMF）又名非负矩阵近似，是多元分析和线性代数算法中的一种，其中，矩阵W被分解为两个矩阵X和Y，并满足三个矩阵都具有非负性，这种非负性使得生成矩阵更容易被检验。由于问题整体上没有精确解，一般地都是在数值上进行近似。
非负矩阵分解问题起源于化学计量学，现在非负矩阵分解广泛应用于天文学，计算机视觉，文本聚类，化学计量学，音频信号处理和推荐系统等领域。

1.2 国内外研究现状
ADMM作为一种分布式算法，广泛地应用于各种优化问题中。例如美国明尼苏达大学的Giannakis教授利用ADMM可以分离的特性，应用于多传感器无线网络中的优化。日本日立Sadara等有将ADMM利用到音频重构上，西安交大的杨彦等将ADMM和压缩感知结合应用到核磁共振图的重构中。ADMM本身作为在凸优化上有很好的性能，例如在多节点协同优化（consensus problem）和共享问题（share problem）上，可以达到1/k的收敛速度。
另外，非负矩阵分解这个问题本身也是很有应用前景的。
在天文学方面，NMF是一种很有前景的方法，作为空间信号降维的引用上。2007年Blanton等首次将NMF方法引入对宇宙观测的不确定性中并发挥出它的优势，之后在2016年被Zhu改进，考虑了缺失数据并进行了并行计算。
在文本信息发掘领域中，一个文本矩阵被不同权重的项构建。一个文本矩阵通过该方法被分解成类别特征矩阵和特征文本矩阵。2013年Arora等已经给出了一种基于NMF方法的多项式时间算法来学习主题模型。这种算法估计主题矩阵满足一种经常在这类问题中存在的离散条件。
分布式优化和NMF算法结合的相关研究在很早之前就有，2010年张寅等提出了一种基于ADMM的NMF方法，在对比同期做LRMC（low rank matrix completion）的算法，在速度和质量上都取得了很好的效果。在2012年印卧涛等提出了基于ADMM的NMFC问题的算法，将LRMC和NMF同时考虑，提出NMFC问题，并给出了NMFC问题下的ADMM算法，取得了相较同期其他算法更好的速度和质量。
分布式计算在处理数据量较大的问题上，有明显的优势，尤其是在现在图像数据越来越大，分辨率越来越大的情况下，分布式计算可以更好地得到应用。而NMF算法在对于具有物理意义的图像、信号等矩阵中，可以充分发挥它的非负性特点，起到更好地降维和重建的功用。

2. 研究的基本内容与方案

2.1研究的基本内容、目标
对于大数据机器学习上遇到的问题，admm是当前给出的三个主流方法中一种。

admm算法体现了“分而治之”的思想，通过拆解大问题为小问题，将成为大数据分析与处理的最有效工具之一。

本次研究的主要内容如下：
1.学习admm算法的基本构成，迭代模式和收敛特点，学习admm凸问题和非凸问题中的应用以及相关的凸优化知识。

3. 研究计划与安排

1-3周：查阅文献，完成开题报告
4-6周：总体设计，完成论文综述
7-10周：设计算法，功能模块设计
11-13周：编码和测试
14-15周：写论文，提交初稿，给老师检查，修改定稿，答辩

4. 参考文献（12篇以上）

[1] boyd s, parikh n, chu e, et al. distributed optimization and statistical learning via the alternating direction method of multipliers[j]. foundations amp; trends in machine learning, 2010, 3(1):1-122.。

[2] xu y, yin w, wen z, et al. an alternating direction algorithm for matrix completion with nonnegative factors[j]. frontiers of mathematics in china, 2012, 7(2):365-384.。

[3] y zhang . an alternating direction algorithm for nonnegative matrix factorization
[4] lee d d. algorithms for nonnegative matrix factorization[j]. advances in neural information processing systems, 2001, 13(6):556--562.
[5] recht b, fazel m, parrilo p a. guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[j]. siam review, 2007, 52(3):471-501.
[6] ma s, goldfarb d, chen l. fixed point and bregman iterative methods for matrix rank minimization[j]. mathematical programming, 2011, 128(1-2):321-353.。