[Theory] [Theory Lunch] Saba Ahmadi, Wednesday, 12/4 12-1pm, JCL 390

[Gabe Schoenbach via Theory]

Hi all — please join us this *Wednesday at 12pm* for the last theory lunch
of the year! Details below:

***
*Date: *December 4, 2024, 12pm
*Location: *JCL 390

*Title: *Replicable Online Learning

*Speaker: *Saba Ahmadi (TTIC)

*Abstract:* 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.

Based on joint work with Siddharth Bhandari and Avrim Blum.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241202/1d315b74/attachment.html>