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.

Synopsis:

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