[Theory] UC Theory seminar

[Alexander Razborov via Theory]

Note non-standard day and location!

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Thursday, November 7, 3:30pm
Location: Crerar 298

SPEAKER: Khashayar Gatmiry (MIT)

TITLE: Computing Optimal Regularizers for Online Linear Optimization 

ABSTRACT: Follow-the-Regularized-Leader (FTRL) algorithms are a popular class of
learning algorithms for online linear optimization (OLO) that
guarantee sub-linear regret, but the choice of regularizer can
significantly impact dimension-dependent factors in the regret bound.
We present an algorithm that takes as input convex and symmetric
action sets and loss sets for a specific OLO instance, and outputs a
regularizer such that running FTRL with this regularizer guarantees
regret within a universal constant factor of the best possible regret
bound. In particular, for any choice of (convex, symmetric) action set
and loss set we prove that there exists an instantiation of FTRL which
achieves regret within a constant factor of the best possible learning
algorithm, strengthening the universality result of Srebro et al.,
2011.
Our algorithm requires preprocessing time and space exponential in the
dimension d of the OLO instance, but can be run efficiently online
assuming a membership and linear optimization oracle for the action
and loss sets, respectively (and is fully polynomial time for the case
of constant dimension d). We complement this with a lower bound
showing that even deciding whether a given regularizer is
α-strongly-convex with respect to a given norm is NP-hard.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241031/70b23515/attachment.html>