Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Machine Learning Work Shop - Session 2 - Ofer Dekel - "Online Learning Against Adaptive Adversaries"

Speaker  Ofer Dekel

Affiliation  MSR - Machine Learning Group

Host  Ofer Dekel

Duration  00:27:36

Date recorded  26 October 2012

Most machine learning algorithms rely on the assumption that the data is generated by a stochastic process. Many online learning algorithms go one step further and allow the data to be generated by an oblivious adversary (a.k.a. a non-adaptive or non-reactive adversary). Very little is known about the machine learning scenario where the data is generated by a more powerful adversary, such as a switching-cost adversary, a memory-bounded adversary, or a general adaptive adversary. In this talk, I will describe ongoing efforts to understand what can and cannot be done against these powerful rivals. First, I will define policy-regret, which is a meaningful way of measuring the performance of a learning algorithm in the adversarial setting. Then, I will present the current state-of-the-art upper and lower bounds on policy regret against different adversary types, in the full-information and the bandit-feedback settings.

This talk represents joint work with Ambuj Tewari, Raman Arora, Nicolo Cesa-Bianchi, and Ohad Shamir.

©2012 Microsoft Corporation. All rights reserved.
> Machine Learning Work Shop - Session 2 - Ofer Dekel - "Online Learning Against Adaptive Adversaries"