AF: Small: Algorithms and Data Structures with Predictions

Harvard University, Cambridge MA

Investigators

Abstract

The goal of this project is to develop improved algorithms and data structures for real-world problems by making use of predictions, such as predictions obtained from machine-learning methods. Traditional standard algorithms are analyzed based on worst-case performance; one considers the worst possible running time on the worst possible input. If an algorithm is given a suitable hint, or prediction, such as from a scanner that determines properties of the input, it may be able to avoid the worst case in practice. For example, if an algorithm could predict when people were waiting in line for service who would only need a small amount of time and who would need a long amount of time, it could order people in line to speed up how quickly people were served, avoiding situations where one person held up the entire line of waiting people. Given the general success of machine-learning techniques, bringing machine-learning predictions into standard algorithmic frameworks may yield important gains in real-world performance, while still providing rigorous performance guarantees. Additional components of this project involve developing materials so that the results of this research can be included in computer science courses, incorporating student work in the research, and broadening participation in computing through expanding educational and research opportunities for developing the next generation of researchers. Standard algorithms and data-structure analysis is based on worst-case performance. The idea of using additional information, such as predictions from machine-learning methods, to improve what can be rigorously proved about performance has been only very sparsely studied. Determining how to use such additional information provides a new method of what is commonly called beyond worst-case analysis, which strives to expand algorithmic analysis beyond the traditional worst-case methods. The ultimate goal is to provide frameworks that take advantage of the power of machine learning to provide good predictions based on the input data, while maintaining the advantages of the robustness and theoretical guarantees available from traditional algorithms. In particular, performance should still remain understandable and acceptable even if predictions are wrong; for example, in some settings, a goal could be that performance should never be much worse when using predictions, even if the predictions are provided adversarially. This area of study is intended to shed new light on long-existing algorithms and data structures, as well as require development of new analysis techniques. The investigator believes that algorithms and data structures of this form are likely to become ubiquitous in real-world systems, and thus theoretical understanding of them is important to characterize their risks and rewards. 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.