Scale-Free Algorithms for Online Linear Optimization

7 years 1 months ago
Scale-Free Algorithms for Online Linear Optimization
We design algorithms for online linear optimization that have optimal regret and at the same time do not need to know any upper or lower bounds on the norm of the loss vectors. We achieve adaptiveness to norms of loss vectors by scale invariance, i.e., our algorithms make exactly the same decisions if the sequence of loss vectors is multiplied by any positive constant. Our algorithms work for any decision set, bounded or unbounded. For unbounded decisions sets, these are the first truly adaptive algorithms for online linear optimization.
Francesco Orabona, Dávid Pál
Added 15 Apr 2016
Updated 15 Apr 2016
Type Journal
Year 2015
Where ALT
Authors Francesco Orabona, Dávid Pál
Comments (0)