Scale-Free Algorithms for Online Linear Optimization
This addresses the need for more flexible and adaptive algorithms in online optimization, particularly for unbounded decision sets, representing a novel advancement rather than an incremental improvement.
The paper tackles the problem of online linear optimization by designing algorithms that achieve optimal regret without requiring prior knowledge of loss vector norms, achieving this through scale invariance and working for both bounded and unbounded decision sets, with the result being the first truly adaptive algorithms for unbounded sets.
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.