分布式并行技术是解决大规模数据处理的有效途径。交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)是求解分布式优化的通用并行算法框架,它为大规模机器学习中的一致性问题和共享问题提供了解决方案,通过将原始任务...
详细信息
分布式并行技术是解决大规模数据处理的有效途径。交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)是求解分布式优化的通用并行算法框架,它为大规模机器学习中的一致性问题和共享问题提供了解决方案,通过将原始任务分解成多个子问题并行处理,最后协调各个子问题的解得到全局的解。在设计分布式ADMM并行算法时,主要存在数据并行和模型并行两种并行模式。数据并行应用广泛且易于实现,但对于高维数据,模型并行相比于数据并行能够减少计算量,因此,针对不同的问题需要选择合适的并行模式。同时,在分布式环境中,ADMM算法节点间的通信开销花费比较大,且在实际应用中分布式ADMM算法也存在收敛速度慢等问题。本文的主要工作集中在以下几点:1)针对分布式ADMM算法的特点以及主从通信结构在多核集群的运行环境中存在的通信瓶颈问题,设计一种新的基于分层的通信结构,提高算法的通信效率。2)通过分析全局一致性ADMM算法(基于数据并行模式)子问题求解对算法收敛速度的影响,结合分层通信结构,设计了一种动态调度ADMM子问题优化算法的策略。同时,从算法的收敛条件出发,将初始残差和对偶残差作为每次调度时选择最优算法的判断依据并设计了基于此的两种不同的动态调度算法。实验结果表明动态调度策略能够加快算法的收敛速度。3)根据对基于特征划分的经验最小化问题的分析,将其结合共享优化问题(数据和特征都可划分),提出一种基于特征的分布式并行ADMM共享算法(基于模型并行模式)求解高维度模型。通过对高维数据按照特征划分成多个低维度的数据,同时将高维模型相应划分成多个子模型,再分配到多个节点并行处理,减少高维数据带来的计算开销。本文给出了算法的收敛性和迭代复杂度分析并通过实验验证了算法的性能。本文在上海大学自强4000集群系统上对并行算法进行测试。测试结果显示分层通信结构可以有效减少算法的通信开销,使用动态调度的策略对子问题进行求解可以加快算法的收敛速度,基于特征的分布式并行ADMM算法在求解高维度模型时可以在精度损失允许的范围内提高算法的收敛速度,同时减少算法的运行时间。
暂无评论