Timezone: »

 
Poster
Online Linear Optimization with Many Hints
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1025
in Poster Session 4 »
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.

Author Information

Aditya Bhaskara (University of Utah)
Ashok Cutkosky (Boston University)
Ravi Kumar (Google)
Manish Purohit (Google)

More from the Same Authors