<div dir="ltr"><div dir="ltr">Hi all — please join us this <b>Wednesday at 12pm</b> for the last theory lunch of the year! Details below:<div><br></div><div><div>***<br><b>Date: </b>December 4, 2024, 12pm<br><b>Location: </b>JCL 390<br><br><b>Title: </b>Replicable Online Learning<br><br><b>Speaker: </b>Saba Ahmadi (TTIC)<br><br><b>Abstract:</b> In this talk, I discuss the concept of algorithmic replicability introduced by Impagliazzo et al.'22 in an online setting. In our model, the input sequence received by the online learner is generated from time-varying distributions chosen by an adversary (obliviously). Our objective is to design low-regret online algorithms that with high probability, produce the exact same sequence of actions when run on two independently sampled input sequences generated as described above. We refer to such algorithms as adversarially replicable. Our model generalizes to capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses. I discuss adversarially replicable online learning algorithms for online linear optimization and the experts problem that achieve sub-linear regret. Finally, I briefly discuss some further extensions and lower bounds on the regret that any replicable online algorithm must incur.</div><br>Based on joint work with Siddharth Bhandari and Avrim Blum.</div></div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div>