[Theory] UC Theory Seminar: a reminder

[Alexander Razborov via Theory]

Khashayar Gatmiry
Massachusetts Institute of Technology
 
 
 
Thursday, November 7, 2024 at 3:30pm
Location: John Crerar Library 298
 
 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/20241106/7b629ec9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 46166 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241106/7b629ec9/attachment-0001.png>