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