Online Algorithms with Machine Learned Advice.

Abstract: Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only to benefit from good predictions but also to achieve a decent performance when the predictions are inadequate.

 

Assume that you are given some (machine-learned) information regarding an online problem. It would be desirable to design an online algorithm that incorporates this information in order to on one hand obtain an improved approximation guarantee in case the machine-learned information is accurate, but on the other hand not lose too much over the approximation guarantee of the best classical online algorithm for the problem in case the information is highly inaccurate.

 

In this talk we present online algorithms augmented by machine learned advice for two classes of problems:

1) Metrical task systems (MTS). This is a broad class of online problems including caching, k-server and convex body chasing.  We present algorithms for general MTS as well as improved algorithms for caching specifically. In order to make the algorithms robust, we  utilize classical results from the theory of online algorithms. Our algorithms are not only of theoretical interest but also perform well on real-world datasets.

 

2) Online selection problems. Here the goal is to select a set of elements arriving online that maximizes a given objective function. We illustrate the concepts behind our algorithms by using the classical secretary problem, and discuss some extensions to other online selection problems such as online bipartite matching.

 

Date: Jul 22, 2020 at 14:00:00 h
Venue: Modalidad Vía Online.
Speaker: Antonios Antoniadis
Affiliation: University of Cologne
Coordinator: José Zamora & José Verschae
More info at:
Event website
Abstract:
PDF

Posted on Jul 20, 2020 in ACGO, Seminars