Antonios Antoniadis

"A Journey into Learning Augmented Algorithms"

The research domain of learning augmented algorithms aims to combine the efficacy of machine learning approaches in handling practical inputs and the performance guarantees offered by traditional worst-case algorithm analysis. For numerous problems, machine learning techniques can readily generate predictions about the structure of the input. Algorithms can leverage these predictions in order to achieve enhanced performance provided that these predictions are sufficiently accurate. Yet, algorithms systems that are based on such predictions, need to also yield a decent performance also in the case that the predictions turn out to be highly inaccurate.
After introducing the area, we present two distinct prediction setups using the illustrative example of metrical task systems (MTS), which generalizes central online problems such as caching, k-server, and convex body chasing. In the first setup, the algorithm receives a single prediction about its expected state, while in the second setup, multiple such predictions are provided in parallel. Leveraging insights from the theory of online algorithms, we develop algorithms that are both consistent and robust. For the first setup, we show that the dependence of our algorithms on the prediction error is best-possible for general MTS, while an exponentially better dependence is possible for caching in particular. For the second setup, we show that our algorithms achieve best-possible performance compared to the optimal in hindsight dynamic combination of the predicted states. In conclusion, we discuss the future prospects of the field and our future endeavors within it.

Termin als Datei downloaden und in den Kalender importieren.