LEAPS-MPS: Modernizing Frank-Wolfe Splitting Algorithms

Optimization algorithms are used every day in defense, healthcare infrastructure, social media, and industry. For instance, to "train" an artificial intelligence (AI) model means to "apply an optimization algorithm." This project seeks to develop and analyze a promising new class of optimization algorithms: "Frank-Wolfe splitting algorithms" (FWSAs). FWSAs have the potential to allow for faster training, lower energy costs, and reduced computational requirements over current state-of-the-art methods. Furthermore, these cost-saving improvements compound as problems get larger. This project will study foundational principles underlying FWSAs, possible modern improvements, and potential limitations. Undergraduate student researchers trained in this program will be equipped to succeed in cutting-edge technical careers in the American workforce. In recent years, Frank-Wolfe methods have received increasing levels of attention due to the reduced computational resources required in solving Frank-Wolfe subproblems: Particularly in high dimensional settings, for many constraints that arise in applications, Frank-Wolfe subproblems are significantly easier to solve when compared to other constrained optimization subproblems, e.g., projection subproblems. This project will analyze and derive new Frank-Wolfe methods for solving the "splitting problem," which has many applications across engineering and the sciences. Since Frank-Wolfe splitting algorithms (FWSAs) are new, they currently lack many of the modern flexibilities (e.g., adaptiveness, stochasticity, and block-iterativeness) that other algorithm classes possess. The goal of this project is to address this gap by developing modernized FWSAs with the aforementioned flexibilities, proving they converge, and demonstrating their utility in computational experiments. This project has the potential to make previously-intractable problems solvable with simpler tools on a larger scale. Software involving the newly-developed algorithms will be made available in a free, open-source format. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.