CAREER: Algorithmic foundations for practical acceleration in computational sciences

William Marsh Rice University, Houston TX

Investigators

Abstract

Non-convex optimization lies at the heart of many engineering applications with far-reaching societal impacts, especially through the wave that machine learning/artificial intelligence triggers: physics, healthcare, biology, software engineering, chemistry and materials science, among other areas. However, given the lack of theory, practitioners often simply follow trial-and-error procedures, leading to heuristics. Characterizing when heuristics turn out to be provable algorithms is one pressing need for the scientific community, and indeed society as a whole. The goal of the proposal is to build algorithmic foundations, along with theory, that accelerate problem solving in such scenarios. This constitutes the design of fast algorithms as an active research area in machine learning, information processing, and optimization research. Understanding how remarkable performance is obtained using efficient algorithms is of ultimate significance towards practical and safely applicable learning. The difficulty/risk of this research lies exactly in the non-convex nature of the tasks, where existing knowledge does not lead to a deeper understanding. The aim is to provide methodologies that perform faster and better in practical settings, as well as introduce theory that justifies their performance. Given the difficulty and diversity of the task, the PI will focus on three research areas: i) faster convergence in structure-rich problems, with a special focus on matrix-factorized machine learning problems; ii) algorithmic acceleration in more general non-convex scenarios, with a special focus on (shallow) neural network architectures; and iii) acceleration techniques in modern ML systems, such as pruning techniques, distributed protocols and hyperparameter tuning. The objectives mentioned above complement each other: their combination results in a unified mathematical framework that will provide insights on why and how several non-convex tools work in ML and optimization research. The PI will study and analyze algorithms with applications in text analytics, image classification, and practical hard combinatorial problems, among others. The proposed research will analyze ideas beyond classical momentum in non-convex scenarios, such as algorithmic implicit regularization, hyper-parameter tuning, deep matrix factorization, proximal point algorithms and robustness, and lottery-ticket hypotheses, just to name a few. The long-term goal is the rigorous characterization of practical methods in non-convex settings, with the hope that they could potentially turn into a technology for designing faster and better algorithms. 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.