Decision-Theoretic Approaches in Learning-Augmented Algorithms
Time: 14:00 -- Location: bat 650, 445
summary: We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, as well as stochastic measures that allow us to balance the trade-off between the algorithm’s performance and the risk associated with the imperfect oracle. These approaches allow us to quantify the algorithmic performance across the full spectrum of the prediction error, and thus choose the best-possible algorithm within an entire class of otherwise incomparable ones. We apply these techniques to three well-known problems from online decision making, namely ski-rental, 1-max search, and contract scheduling.
Joint work with Spyros Angelopoulos and Christoph Dürr