Asynchronous parallel stochastic frameworks with convergence guarantee for solving large-scale fixed point problems

在过去二十年中，许多领域的数据集规模迅速增长。在机器学习的许多应用中，存在大量的训练数据集，并且数据集可以被收集并存储在不同的位置。从这些数据集中学习模型对算法的计算、内存和数据传输提出了很高的要求。异步并行算法通过高性能计算和减少通信和空闲时间来解决这些大规模问题。与同步并行算法相比，异步并行算法的性能有了很大的提高，特别是在核数较多的情况下。然而，对这些算法的收敛性和收敛速度的理论分析还处于探索阶段. 在这项提案中，PI将开发快速和强大的通用异步并行随机框架，具有可证明的收敛性，用于解决在许多领域都有应用的大规模不动点问题。一个目标是开发异步随机算法，找到一个零点的随机算子，一个随机算子和一个确定性算子的总和，以及两个随机算子的总和，并显示这些算法的收敛性。另一个目标是耦合到这些异步随机算法的坐标更新，并显示其收敛性。最后一个目标是实现这些算法，并开发软件来帮助没有并行计算知识的人运行异步算法。求解不动点问题的研究是由各种计算科学和工程中的问题所激发的，它的发展通过提供快速和鲁棒的算法而使所有这些领域受益。受拟议工作影响的领域包括机器学习、优化、最优控制、统计、金融、信号和图像处理、压缩传感以及涉及大数据集和分布式数据的其他研究领域。

In the last two decades, the size of data sets in a large number of areas has grown quickly. In many applications of machine learning, there are massive amounts of training data sets and the data sets may be collected and stored at different locations. Learning a model from these data sets imposes high demands for computation, memory, and data transfer on algorithms. Asynchronous parallel algorithms are applied to solve these large-scale problems via high performance computing and reduced communication and idle time. The performance of asynchronous parallel algorithms is improved largely comparing to synchronous parallel algorithms, especially when the number of cores is large. However, theoretical analysis on the convergence and convergence rates of these algorithms still investigation. In this proposal, the PI will develop fast and robust generic asynchronous parallel stochastic frameworks with provable convergence for solving large-scale fixed point problems that have applications in a large number of areas. One objective is to develop asynchronous stochastic algorithms for finding a zero point of a random operator, the sum of a random operator and a deterministic operator, and the sum of two random operators and show the convergence of these algorithms. Another objective is to couple coordinate updates into these asynchronous stochastic algorithms and show their convergence. The last objective is to implement these algorithms and develop software to help people without knowledge about parallel computing run asynchronous algorithms. The research in solving fixed point problems is motivated by problems in various computational sciences and engineering, and its development benefits all these fields by providing fast and robust algorithms. Areas impacted by the proposed work include machine learning, optimization, optimal control, statistics, finance, signal and image processing, compressive sensing, as well as other lines of research involving large data sets and distributed data.