CAREER: Scalable Optimization for Data Science: Complexity and Structure

Large-scale optimization has become a pervasive feature of our daily lives. Optimization algorithms empower most of the data science and machine learning technologies currently used for decision-making in several sectors, such as healthcare, energy, transportation, manufacturing, and finance. Despite its widespread adoption, there are still significant gaps between theory and practice in optimization. In some sectors, simple heuristics, e.g., stochastic gradient descent, yield incredibly effective results while lacking basic theoretical guarantees. Meanwhile, other sectors rely on traditional algorithms, e.g., interior point methods, that have strong guarantees but struggle to scale to contemporary problem sizes. The goal of this project is to advance the state of the art of optimization theory and algorithms to tackle the unique challenges posed by modern data science problems. This award integrates research efforts with activities that broaden STEM participation and expand educational opportunities; these include mentoring high school students through the Johns Hopkins Center for Educational Outreach, advising diverse group of graduate students, developing novel courses on the practice and theory of data science, and disseminating methods via open-source software to encourage broad adoption. To achieve its research goal, this CAREER award will develop novel tools to analyze the computational and statistical complexity of off-the-shelf heuristics that perform well even in nonconvex, nonsmooth settings. Capitalizing on these insights, the project will design new algorithmic solutions that circumvent the computational pitfalls of traditional methods. The guiding principle to tackle these challenges will be structure. On the one hand, although nonconvex, nonsmooth problems appearing in applications are known to be NP-hard, this notion only captures worst-case complexity. In practice, many problems enjoy additional benign geometric structure, enabling simple heuristics to succeed. On the other hand, this project will leverage the inherent structure of problems to design faster, parallelizable algorithms that can fully utilize modern machine learning infrastructure. These algorithms will be evaluated on optimization formulations from various applications spanning X-ray crystallography, phase space tomography, and recommendation systems. 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.