Timezone: »

A Parameter-free Hedging Algorithm
Kamalika Chaudhuri · Yoav Freund · Daniel Hsu

Wed Dec 09 07:00 PM -- 11:59 PM (PST) @

We study the problem of decision-theoretic online learning (DTOL). Motivated by practical applications, we focus on DTOL when the number of actions is very large. Previous algorithms for learning in this framework have a tunable learning rate parameter, and a major barrier to using online-learning in practical applications is that it is not understood how to set this parameter optimally, particularly when the number of actions is large. In this paper, we offer a clean solution by proposing a novel and completely parameter-free algorithm for DTOL. In addition, we introduce a new notion of regret, which is more natural for applications with a large number of actions. We show that our algorithm achieves good performance with respect to this new notion of regret; in addition, it also achieves performance close to that of the best bounds achieved by previous algorithms with optimally-tuned parameters, according to previous notions of regret.

Author Information

Kamalika Chaudhuri (UCSD)
Yoav Freund (UC San Diego)
Daniel Hsu (Columbia University)

See <https://www.cs.columbia.edu/~djhsu/>

More from the Same Authors