CAREER: Leveraging Sparsity in Massively Distributed Optimization

点击翻译按钮获取中文摘要

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.