NeurIPS 2017poster57 citations
Online Learning with a Hint
Ofer Dekel, arthur flajolet, Nika Haghtalab, Patrick Jaillet
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.
BibTeX
@inproceedings{NIPS2017_22b1f2e0,
author = {Dekel, Ofer and flajolet, arthur and Haghtalab, Nika and Jaillet, Patrick},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Online Learning with a Hint},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/22b1f2e0983160db6f7bb9f62f4dbb39-Paper.pdf},
volume = {30},
year = {2017}
}