Adaptive Scale-Invariant Online Algorithms for Learning Linear Models

Michal Kempka, Wojciech Kotlowski, Manfred K. Warmuth
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3321-3330, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kempka19a, title = {Adaptive Scale-Invariant Online Algorithms for Learning Linear Models}, author = {Kempka, Michal and Kotlowski, Wojciech and Warmuth, Manfred K.}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3321--3330}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/kempka19a/kempka19a.pdf}, url = {https://proceedings.mlr.press/v97/kempka19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Adaptive Scale-Invariant Online Algorithms for Learning Linear Models %A Michal Kempka %A Wojciech Kotlowski %A Manfred K. Warmuth %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-kempka19a %I PMLR %P 3321--3330 %U https://proceedings.mlr.press/v97/kempka19a.html %V 97 %X 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.
APA
Kempka, M., Kotlowski, W. & Warmuth, M.K.. (2019). Adaptive Scale-Invariant Online Algorithms for Learning Linear Models. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3321-3330 Available from https://proceedings.mlr.press/v97/kempka19a.html.

Related Material