Skip to yearly menu bar Skip to main content


Poster

Power of Hints for Online Learning with Movement Costs

Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit

Keywords: [ Online Learning ] [ Learning Theory and Statistics ]


Abstract: We consider the online linear optimization problem with movement costs, a variant of online learning in which the learner must not only respond to cost vectors ct with points xt in order to maintain low regret, but is also penalized for movement by an additional cost xtxt+11+ϵ for some ϵ>0. Classically, simple algorithms that obtain the optimal T regret already are very stable and do not incur a significant movement cost. However, recent work has shown that when the learning algorithm is provided with weak hint'' vectors that have a positive correlation with the costs, the regret can be significantly improved to log(T). In this work, we study the stability of such algorithms, and provide matching upper and lower bounds showing that incorporating movement costs results in intricate tradeoffs between log(T) when ϵ1 and T regret when ϵ=0.

Chat is not available.