CAREER: Leveraging Sparsity in Massively Distributed Optimization

该项目开发了基于Frank-Wolfe算法的新型并行优化技术，以前所未有的规模实现了对计算机科学、工程和运筹学具有关键意义的几个问题的大规模并行化。大规模并行处理这类问题可以对学术界和工业界产生重大的实际影响。使用Apache Spark作为开发平台，该项目开发的算法可以在数百台机器和数千个cpu上实现、部署和评估。马萨诸塞州绿色高性能计算中心（Massachusetts Green High Performance Computing Center， MGHPCC）以及云服务（如Amazon Web services和谷歌云平台）被用于此部署，展示了所开发算法的可伸缩性以及它们对商业集群环境的适用性。教育活动与该研究议程紧密结合，包括由首席研究员使用MGHPCC作为计算平台开发的课程，以及与东北大学STEM教育中心联合开发的外展活动。这项研究提高了我们对形式条件的认识和理解，在这些条件下，问题可以通过Frank-Wolfe算法的map-reduce实现大规模并行化。该项目利用了Frank-Wolfe优化问题所表现出的稀疏性属性，从而通过map-reduce操作实现了它们的并行化。除了定制的、特定于问题的实现之外，该项目还确定了问题（或问题类别）的正式、结构属性，在这些属性下，通过map-reduce进行大规模并行化是可能的。使用Frank-Wolfe作为并行化的构建块，无论是在凸优化还是在次模块化最大化设置中，都是变革性的。在后一种情况下，它相当于并行化的非组合方法，获得与串行算法相同的近似保证。

This project develops novel parallel optimization techniques based on the Frank-Wolfe algorithm, enabling the massive parallelization, at an unprecedented scale, of several problems of key significance to computer science, engineering, and operations research. Massively parallelizing such problems can have a significant practical impact on both academia and industry. Using Apache Spark as a development platform, algorithms developed by the project can be implemented, deployed and evaluated over hundreds of machines and thousands of CPUs. The Massachusetts Green High Performance Computing Center (MGHPCC) as well as cloud services, such as Amazon Web Services and the Google Cloud Platform, are leveraged for this deployment, demonstrating both the scalability of developed algorithms as well as their applicability to commercial cluster environments. Educational activities are closely integrated with this research agenda, including a course developed by the principal investigator using MGHPCC as a computing platform, and outreach activities developed jointly with Northeastern University's Center for STEM Education.This research advances our knowledge and understanding of the formal conditions under which problems can be massively parallelized via map-reduce implementations of the Frank-Wolfe algorithm. The project leverages sparsity properties that optimization problems exhibit under Frank-Wolfe, thereby enabling their parallelization via map-reduce operations. Beyond tailored, problem-specific implementations, the project identifies formal, structural properties of problems (or, classes of problems) under which such massive parallelization via map-reduce is possible. The use of Frank-Wolfe as a building block for parallelization, both in convex optimization but also in submodular maximization settings, is transformative. In the latter case, it amounts to a non-combinatorial approach for parallelization, attaining the same approximation guarantee as serial algorithms.