Many areas of machine learning (ML) currently rely on heuristic algorithms with no performance guarantees, and, in fact, the underlying problems are computationally intractable. The proposed project will lead to new machine learning algorithms with provable guarantees. The PIs will leverage theoretical ideas from average case analysis, semi-random models, approximation, solution stability, and approximate linear algebra, and develop new tools and techniques. Benefits from this endeavor will occur across fields. Theoretical computer science will benefit by gaining new problems and research agendas, and further development of algorithmic and mathematical tools. Machine learning will benefit by gaining new models (hopefully, more tractable than the ones currently in use), new modes of thinking, and new algorithms. The task of proving bounds on algorithms will provide insight into when they do or do not work, as well as suggest modifications to existing heuristics.
The project will involve training a new generation of graduate students and postdocs who will be fluent both in theoretical algorithms and machine learning. The PIs gained experience in delivering this kind of training and mentoring during the past couple of years and will continue this, including working with the undergraduate students. The PIs will disseminate the ideas of this project by lecturing, teaching, and creating new course materials, including videos. One specialized workshop will also be organized, devoted to the topics of study. Open-source software implementation will be released based upon any new learning algorithms that are discovered.
