Student Probability Seminar
New Potential-Based Bounds for Prediction with Expert Advice
Speaker: Vlad Kobzar, CIMS
Location: Warren Weaver Hall 201
Date: Thursday, December 5, 2019, 12:15 p.m.
We address the classic machine learning problem of online prediction
with expert advice: At each round, the predictor (player) uses guidance
from a collection of experts with the goal of minimizing the difference
(regret) between the player's loss and that of the best performing
expert in hindsight. The experts' losses and gains are determined by the
environment (adversary), possibly in an adversarial manner.
State-of-the art player strategies are based on potential functions that
bound the regret above. On the other hand, state-of-the art adversary
strategies were historically determined by random walk methods.
Although the player and the adversary may use randomization in their
strategies, the deterministic control paradigm fully describes the
expert framework. Accordingly, using verification arguments from
optimal control theory, we view the task of finding better lower and
upper bounds on the value of the game (regret) as the problem of finding
better sub-and supersolutions of certain partial differential equations
(PDEs). These sub-and supersolutions serve as the potentials for player
and adversary strategies, which lead to the corresponding bounds.
To get explicit bounds, we use closed-form solutions of specific PDEs.
Our bounds hold for any fixed number of experts and any time-horizon; in
certain regimes they improve upon the previous state-of-the-art.
This is joint work with Robert Kohn and Zhilei Wang at Courant. A
preprint is available at https://arxiv.org/abs/1911.01641