AF: Small: Online Algorithms and Approximation Methods in Learning

University Of Utah, Salt Lake City UT

Investigators

Abstract

Modern machine-learning applications aim to solve difficult computational problems accurately, quickly and at scale. This has led to significant algorithmic challenges that are compounded by practical considerations like robustness to noise and the distributed nature of data. The goal of the project is to develop a formal understanding of when efficient learning is possible, and to develop novel algorithmic insights. The techniques developed in the project will lead to progress in approximation algorithms, optimization, sublinear algorithms, and computational complexity. The project includes a plan to develop courses that teach undergraduate and graduate students to formally reason about machine-learning systems and to understand their power and limitations. The courses will help train the next generation of the workforce, and will be offered at the University of Utah, with much of the material being publicly accessible. The project aims to address two core questions in reasoning about machine learning. The first one is related to the computational hardness of learning problems. For problems such as sparse coding and learning low-depth neural networks, all the known algorithms require strong structural assumptions in order to obtain learning guarantees. The project will study methods (for these and other problems) that enable one to weaken these assumptions, while obtaining weaker yet practically relevant guarantees. The second question is related to learning in online arrival models, motivated by recommender systems and signal processing. Here, many of the known theoretical results fall short when data is noisy or is only partially observed, and the project will develop formal models and algorithmic results for these settings. 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.