Decision-Theoretic Approaches in Learning-Augmented Algorithms

-- Georgii Melidi (LIP6)

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

Category: seminars
Tags: Team seminar graphs