NeurIPS 2020poster19 citations
Online Linear Optimization with Many Hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
Abstract
We study an online linear optimization (OLO) problem in which the learner is provided access to $K$ ``hint'' vectors in each round prior to making a decision. In this setting, we devise an algorithm that obtains logarithmic regret whenever there exists a convex combination of the $K$ hints that has positive correlation with the cost vectors. This significantly extends prior work that considered only the case $K=1$. To accomplish this, we develop a way to combine many arbitrary OLO algorithms to obtain regret only a logarithmically worse factor than the minimum regret of the original algorithms in hindsight; this result is of independent interest.
BibTeX
@inproceedings{NEURIPS2020_6c250b59,
author = {Bhaskara, Aditya and Cutkosky, Ashok and Kumar, Ravi and Purohit, Manish},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {9530--9539},
publisher = {Curran Associates, Inc.},
title = {Online Linear Optimization with Many Hints},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/6c250b592dc94d4de38a79db4d2b18f2-Paper.pdf},
volume = {33},
year = {2020}
}