Collaborative Research: AF: Small: Foundations of Algorithms Augmented with Predictions

The ability to process and use information to make better decisions is driving breakthroughs in science and engineering, and they are being materialized in business. Machine learning is one of the central forces behind such revolutionary progress. For example, machine learning is often used to make predictions for uncertain information such as traffic in a road network or consumer demand for an online business. Unfortunately, machine learning is imperfect and commonly error-prone. The goal of this project is to design efficient decision-making algorithms that result in solutions that are both high-quality and robust to error in the predictions. The investigators of this project will organize a workshop to disseminate research findings to the community. The research will be incorporated into courses and the investigators will develop an undergraduate degree program on the intersection of business and machine learning. This project will develop the foundations of augmenting decision-making algorithms with error-prone machine-learned predictions. The project’s goal is to develop algorithms that break through worst-case analysis barriers with high-quality predictions and have graceful degradation in quality as the error in the predictions grows. The algorithms developed will use predictions to improve the worst-case running time and better cope with uncertainties in the future input. The predictions used will be grounded in computational learning theory and be shown to be efficiently learnable. The project has the following goals. The project will (1) investigate using predictions to improve the running time of algorithms for problems of fundamental importance such as matchings and flows; (2) use predictions to give algorithms information about uncertain inputs for online problems and investigate various measures to better gauge the prediction quality; and (3) develop a theory for which parameters can be efficiently learned. 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.