@misc{dekel2017online,
author = {Dekel, Ofer and Flajolet, Arthur and Haghtalab, Nika and Jaillet, Patrick},
title = {Online Learning with a Hint},
year = {2017},
month = {May},
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 ∈ (2,3), the hint can be used to guarantee a regret of o(√T). In contrast, we establish Ω(√T) lower bounds on regret when the set of feasible actions is a polyhedron.},
url = {http://approjects.co.za/?big=en-us/research/publication/online-learning-hint/},
}