CAREER: Computational Foundations of Modern Machine Learning

Machine learning is poised to play a central role in various areas of society, including healthcare, transportation, education, and commerce. Despite this immense potential, there are significant gaps in the theoretical understanding of some of the most foundational aspects which are crucial for these modern applications. These applications pose complex requirements, such as memory or space constraints on the learning algorithm and robustness of the learned model to changes in the data distribution. Classical learning theory, however, mainly focuses on more traditionally examined metrics, such as the running time of the learning algorithm and the average error that the model obtains on a test set. Therefore, the goal of this project is to re-examine some of the foundations of learning theory and develop a theory that takes into account modern requirements such as memory efficiency and robustness. In doing this, the project will not only help build a rich algorithmic suite to meet these requirements in practice and hence significantly increase the scope of current applications; it will also develop insights that can guide the understanding of new theoretical angles on learning and computation. In more detail, the project’s objective is to understand the fundamental limits and trade-offs of what is achievable under these contemporary requirements and use this understanding to develop new algorithmic frameworks to meet the requirements. To achieve this, the project will examine if there are inherent trade-offs between the available memory and the best achievable convergence rate for a number of fundamental learning and optimization problems. The project aims to leverage these trade-offs to identify suitable classes of problems where it is possible to achieve the convergence rate of memory-intensive algorithms but with much less memory usage. Finally, the project aims to establish a principled framework that goes beyond the classical training/test paradigm to understand the generalization abilities of learned models, and to develop a toolbox that effectively addresses modern robustness demands. To aid in the translation of theoretical results to practical settings, open-source software will be developed, and algorithms will be evaluated on benchmark datasets. An educational plan is tightly integrated with the research objectives of the project, including outreach activities with high-school students and a collaboration with the Los Angeles County Office of Education. 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.