[Colloquium] Machine Learning Seminar: Raman Arora, TTIC

[Liv Leader]

When:     Thursday, January 17th @ 12

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Who:       Raman Arora, TTIC

Title:       Online learning against adaptive adversaries

Abstract: Online learning algorithms are designed to learn even when their
input is generated by an adversary. The widely-accepted formal definition
of an online algorithm's ability to learn is the game-theoretic notion of
regret. However, the standard definition of regret becomes inadequate if
the adversary is allowed to adapt to the online algorithm's actions. In
this talk, I will define an alternative notion of policy regret, which
provides a meaningful way to measure an online algorithm's performance
against adaptive adversaries. I will show that no bandit algorithm can
guarantee a sublinear policy regret against an adaptive adversary with
unbounded memory. On the other hand, for a memory-bounded adversary, I will
present a general technique that converts any bandit algorithm with a
sublinear regret bound into an algorithm with a sublinear policy regret
bound.

This is joint work with Ofer Dekel at MSR and Ambuj Tewari at University of
Michigan.

Host: Samorty Kpotufe, samory at ttic.edu

-- 
Liv Leader
Director of Human Resources and International Affairs

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu
Web-   www.ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130114/f45597f2/attachment.htm