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 with points in order to maintain low regret, but is also penalized for movement by an additional cost for some . Classically, simple algorithms that obtain the optimal 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 . 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 when and regret when .
Chat is not available.