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

用于解决大规模不动点问题的具有收敛保证的异步并行随机框架

• 批准号: 1621798
• 负责人: Ming Yan
• 金额: $ 15万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1621798&HistoricalAwards=false
• 关键词: Asynchronous; parallel; stochastic; frameworks; convergence

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.

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