Timezone: »
We consider online learning with linear models, where the algorithm predicts on sequentially revealed instances (feature vectors), and is compared against the best linear function (comparator) in hindsight. Popular algorithms in this framework, such as Online Gradient Descent (OGD), have parameters (learning rates), which ideally should be tuned based on the scales of the features and the optimal comparator, but these quantities only become available at the end of the learning process. In this paper, we resolve the tuning problem by proposing online algorithms making predictions which are invariant under arbitrary rescaling of the features. The algorithms have no parameters to tune, do not require any prior knowledge on the scale of the instances or the comparator, and achieve regret bounds matching (up to a logarithmic factor) that of OGD with optimally tuned separate learning rates per dimension, while retaining comparable runtime performance.
Author Information
Michal Kempka (Poznan University of Technology)
Wojciech Kotlowski (Poznan University of Technology)
Manfred K. Warmuth (UC Santa Cruz & Google Inc.)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Oral: Adaptive Scale-Invariant Online Algorithms for Learning Linear Models »
Thu Jun 13th 04:40 -- 05:00 PM Room Room 102
More from the Same Authors
-
2017 Poster: Consistency Analysis for Binary Classification Revisited »
Krzysztof Dembczynski · Wojciech Kotlowski · Sanmi Koyejo · Nagarajan Natarajan -
2017 Talk: Consistency Analysis for Binary Classification Revisited »
Krzysztof Dembczynski · Wojciech Kotlowski · Sanmi Koyejo · Nagarajan Natarajan