A long-standing question in theoretical computer science is to offer analysis tools for improving performance on typical everyday, non-worst-case instances. A recent model addressing this goal is the algorithms-with-predictions model: each problem instance comes with a possibly error-prone prediction, and the worst-case running time is given as a function of the error in that prediction. This model reflects how recent advances in machine learning are able to make reasonably good predictions on practical ‒ even very complex ‒ datasets.

The algorithms-with-predictions model has been used to give strong approximation-ratio guarantees for fundamental online algorithms like scheduling and caching. How to leverage predictions to speed up running time of offline algorithms and data structures has received less attention.

This Dagstuhl Seminar aims to bring together researchers from the data structures, combinatorial optimization and learned predictions communities to address the challenges of adopting learned predictions for improving running time guarantees. Ideal outcomes include the development of new beyond-worst-case data structures and algorithms, a formal framework to model and analyze predictions, and improved heuristics that bring theory closer to practice.

This seminar will specifically focus on developing foundations for: (1) learned predictions for data structure design, and (2) learned predictions for offline optimization.

Learned Predictions for Data Structure Design. There is strong empirical evidence that augmenting worst-case data structures with machine-learned advice leads to improved running times. These results showcase the potential of learned data structures. This seminar will focus on how to theoretically understand the power and limitations of predictions through the algorithms-with-predictions model. This model has the potential to fundamentally change how the community thinks about designing worst-case data structures ‒ by leveraging predictions that are learnable, incur minimal overhead, and deliver significant speedups on most datasets while simultaneously being robust towards adversarial inputs.

Learned Predictions for Offline Optimization. Traditional running time analysis assumes that problems are solved from scratch. However, algorithms are often run on different data sets over time. These prior runs can encode information that can be used to improve run times in the future. An intuitive approach to speed up an algorithm is to start with some previously computed solution, referred to as a warm start.

Warm-start algorithm design is not new and is commonly used by heuristics. However, most prior work on this topic is empirical. There is a need for a theoretical foundation of warm-start heuristics via the algorithms-with-predictions model.

There has been some preliminary work in the community toward this goal which showcases the potential of the area and serves as a proof-of-concept for other researchers. In particular, recent results show that warm-start can lead to faster algorithms speeding up the Hungarian algorithm for computing weighted bipartite matching. This has since been extended for other graph algorithms. The area of warm-start algorithm design has the potential to grow into an area as deep and interesting as the line of work using predictions online in the competitive analysis model. This seminar will bring together researchers from this area and organize sessions and discussions that build toward this vision.

Creative Commons BY 4.0

Inge Li Gørtz, Benjamin J. Moseley, Shikha Singh, and Sergei Vassilvitskii