Timezone: »

 
Poster
Online Learning with a Hint
Ofer Dekel · arthur flajolet · Nika Haghtalab · Patrick Jaillet

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #56
in Posters Wed »

We study a variant of online linear optimization where the player receives a hint about the loss function at the beginning of each round. The hint is given in the form of a vector that is weakly correlated with the loss vector on that round. We show that the player can benefit from such a hint if the set of feasible actions is sufficiently round. Specifically, if the set is strongly convex, the hint can be used to guarantee a regret of O(log(T)), and if the set is q-uniformly convex for q\in(2,3), the hint can be used to guarantee a regret of o(sqrt{T}). In contrast, we establish Omega(sqrt{T}) lower bounds on regret when the set of feasible actions is a polyhedron.

Keywords: Learning Theory · Online Learning
[ Paper] 

Author Information

Ofer Dekel (Microsoft Research)
arthur flajolet (MIT)
Nika Haghtalab (Carnegie Mellon University)
Patrick Jaillet (MIT)

More from the Same Authors