Algorithms are ubiquitous in modern society and integral to the economy. Whether finding optimal assignments of packages and operators to planes, trucks, and ships, or translating between different languages, the problems solved become larger and more challenging every day. Crucially enabling such developments are advances in artificial intelligence. There are often different approaches for solving the same type of problem, and they are often synergistic -- where one fails, another performs well. AI techniques in this project allow the best approach for a given problem to be chosen automatically. This research will allow for such choices to be made more robustly even in difficult circumstances, resulting in improved performance and reduced effort to deploy AI in practical systems. Ultimately, the project will make it easier for humans to develop high-performance AI systems.
Algorithm selection is the process of automatically matching synergistic algorithmic choices to the specific properties of a problem in order to achieve optimal performance. Current methods for making such choices over available algorithms are often limited in applicability by the hardware on which the algorithms were benchmarked, the resource limits imposed on runs, and subject to bias caused by performance fluctuations in randomized algorithms. In many cases, these issues are caused by reliance on brittle performance measures, limiting practical application in academia and industry. This project aims to address these limitations in three ways. First, it will define a notion of robustness to guide algorithm selection, and identify properties of algorithms, experimental setups, and computational environments that affect robustness. Second, it will develop specific performance measures informed by this definition of robustness, and which are portable across different hardware platforms. Third, it will mitigate the impact of brittle performance measures through new approaches to building performance models based on machine learning. The project will result in the dissemination of shared data and benchmarks to the broader AI community, for example through the Algorithm Selection Library (ASlib).
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.
