Convex Games in Banach Spaces
Abstract Consider the setting of (adversarial) online convex optimization: an adversary and a learner (or optimizer) interact in a game with T rounds. At round t, the learner has to choose a point x_t, the adversary then responds with a convex function f_t and the learner suffers f_t(x_t). The goal of the learner is to minimize its regret: a quantity that measures the "displeasure" or regret the learner feels, in hindsight, because of not knowing the future and thus behaving sub-optimally.
We study such games in arbitrary Banach spaces and connect them to the geometry of Banach spaces, specifically to the so-called "Martingale type" of the Banach space. It turns out that the behavior of martingale difference sequences in the Banach space completely characterizes the ability of the learner to minimize its regret. Time permitting, I will also talk about explicit learner strategies for minimizing regret.
(Joint work with Karthik Sridharan)
Dr. Ambuj Tewari obtained his MA in Statistics and PhD in Computer Science from UC Berkeley in 2005 and 2007 respectively. He was a Research Assistant Professor at Toyota Technological Institute at Chicago (TTIC) from 2008 to 2010. He recently joined UT Austin where he's working as a post-doctoral fellow with Professors Inderjit Dhillon and Pradeep Ravikumar. His research revolves around issues in decision making in probabilistic or adversarial environments. This includes problems like classification, regression, matrix learning, ranking, bandit problems, and reinforcement learning.