Skip to yearly menu bar Skip to main content


Poster

Online Learning with a Hint

Ofer Dekel · arthur flajolet · Nika Haghtalab · Patrick Jaillet

Pacific Ballroom #56

Keywords: [ Learning Theory ] [ Online Learning ]


Abstract:

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.

Live content is unavailable. Log in and register to view live content