本文讨论最小二乘拟合问题的并行优化方法，对突破大数据环境下机器学习的计算瓶颈有重要帮助和启示。提出的最大分划松弛交替方向乘子法（MS-RADMM）算法，是对交替方向乘子法（ADMM）的一个有趣扩展。MS-RADMM算法在超限学习机（ELM）中的应用，从算法并行结构角度为ELM的并行实现提供一条有效途径。原文链接：/stamp/stamp.jsp?tp=&arnumber=8789676最小二乘拟合问题广泛存在于机器学习、统计分析、信号处理、最优控制等研究和应用领域。用于训练单隐层前馈神经网络（SLFN）的ELM算法，其核心步骤之一是随机产生并固定隐层神经元，之二是求解输出权矩阵优化的最小二乘问题。基于逆矩阵的最小二乘解，使ELM算法高效并易于实现。
但是在大数据环境下，最小二乘拟合问题的求解，仍然面临计算负担过重的挑战。以下文章从并行优化角度出发，应用具有天生并行结构的ADMM方法，提出最小二乘拟合问题的MS-RADMM算法，具有高度的并行性和可扩展性。
ADMM是求解大规模优化问题的一个强有力工具。通过模型分划，ADMM把一个优化问题分解为规模相对较小且可并行执行的多个子问题。论文提出，对最小二乘拟合问题
进行优化模型的最大分划，使每个子问题只含一个优化变量，得到如下最大分划ADMM （MS-ADMM）算法。
MS-ADMM算法的每个迭代步，对变量的更新都可标量化，即可按标量分量同时分别进行。这个标量化特性，使算法具有极高的并行性。若有足够多得处理器来并行更新每个迭代步的所有标量分量，算法的单次循环计算复杂度是M和N的一次方。
论文还提出了一种新的松弛技术，以加速算法的收敛。将这种松弛技术与MS-ADMM结合后，得到MS-RADMM算法。该算法也包含x-更新、y-更新、z-更新和u-更新等4个迭代步，其中的y-更新、z-更新和u-更新与MS-ADMM算法一样，但对x-更新做了如下修改：
论文应用线性系统理论和矩阵谱分析理论，建立了MS-RADMM算法收敛的充分必要条件和线性收敛率，并得到了最优收敛率及对应的算法参数。
将MS-RADMM算法应用到训练SLFN的RELM，即用MS-RADMM求解正则化最小二乘问题
为验证算法性能，在下表的10个基准数据集上进行实验：
在Gisette数据集上，MS-RADMM算法、MS-ADMM算法及最速下降法的收敛曲线如下图。可见，算法是线性收敛的，且比MS-ADMM和最速下降法收敛快。
Gisette数据集上，MS-RADMM算法（C++实现）在有不同数目计算核心的计算机上获得的加速比，与计算核心数的关系接近线性关系，表明算法优良的并行性。
在10个基准数据集上，MS-RADMM获得的训练和测试精度，与基于矩阵逆的方法得到的结果非常接近。
在MATLAB环境下做了GPU加速实验。GPU加速后，MS-RADMM算法的计算时间接近基于矩阵逆的方法，随着数据集规模的增大，计算时间有可能少于基于矩阵逆的方法。
在10个数据集上，MS-RADMM获得的GPU加速比都超过了50，而基于矩阵逆的方法只有10左右，进一步表明MS-RADMM算法具有优良的并行性。
目前的ELM，其目标函数是无约束二次型的，有基于矩阵逆的高效求解方法。当目标函数不是无约束二次型时，基于矩阵逆的方法将失效，这时MS-RADMM算法将更有其用武之地。
