Seminar • Algorithms and Complexity • Causal Structure Learning and Online Algorithms with ML Advice

Please note: This seminar will take place in DC 1304 and online.

Themis Gouleakis, Senior Research Fellow
National University of Singapore

The enormous success of the field of machine learning in recent years and its ability to make accurate predictions using data has also influenced research in other areas. In this talk, we will explore such settings where “machine learned advice” can be exploited.

We first introduce the problem of active causal structure learning with advice. In the typical well studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) G∗ while minimizing the number of interventions made. In our setting, we are additionally given side information about G∗ as advice, e.g., a DAG G purported to be G∗ . We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. When the advice is a DAG G, we design an adaptive search algorithm to recover G∗ whose intervention cost is at most O(max{1, log ψ}) times the cost for verifying G∗ ; here, ψ is a distance measure between G and G∗ that is upper bounded by the number of variables n, and is exactly 0 when G = G∗ . Our approximation factor matches the state-of-the-art for the advice-less setting.

Another area of theoretical computer science that could benefit from that is online algorithms, where the goal is to exploit the ability of machine learning algorithms to make predictions of future input to the algorithm. The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from the worst-case. Often this is not an issue with machine learning approaches, which shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. We will also discuss recent results in this context for the Online Traveling Salesperson Problem (OLTSP) with predictions.

To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom at https://uwaterloo.zoom.us/j/93032855786.