Online Learning Without Prior Information

Ashok Cutkosky, Kwabena Boahen
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:643-677, 2017.

Abstract

The vast majority of optimization and online learning algorithms today require some prior information about the data (often in the form of bounds on gradients or on the optimal parameter value). When this information is not available, these algorithms require laborious manual tuning of various hyperparameters, motivating the search for algorithms that can adapt to the data with no prior information. We describe a frontier of new lower bounds on the performance of such algorithms, reflecting a tradeoff between a term that depends on the optimal parameter value and a term that depends on the gradients’ rate of growth. Further, we construct a family of algorithms whose performance matches any desired point on this frontier, which no previous algorithm reaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-cutkosky17a, title = {Online Learning Without Prior Information}, author = {Cutkosky, Ashok and Boahen, Kwabena}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {643--677}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/cutkosky17a/cutkosky17a.pdf}, url = {https://proceedings.mlr.press/v65/cutkosky17a.html}, abstract = {The vast majority of optimization and online learning algorithms today require some prior information about the data (often in the form of bounds on gradients or on the optimal parameter value). When this information is not available, these algorithms require laborious manual tuning of various hyperparameters, motivating the search for algorithms that can adapt to the data with no prior information. We describe a frontier of new lower bounds on the performance of such algorithms, reflecting a tradeoff between a term that depends on the optimal parameter value and a term that depends on the gradients’ rate of growth. Further, we construct a family of algorithms whose performance matches any desired point on this frontier, which no previous algorithm reaches.} }
Endnote
%0 Conference Paper %T Online Learning Without Prior Information %A Ashok Cutkosky %A Kwabena Boahen %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-cutkosky17a %I PMLR %P 643--677 %U https://proceedings.mlr.press/v65/cutkosky17a.html %V 65 %X The vast majority of optimization and online learning algorithms today require some prior information about the data (often in the form of bounds on gradients or on the optimal parameter value). When this information is not available, these algorithms require laborious manual tuning of various hyperparameters, motivating the search for algorithms that can adapt to the data with no prior information. We describe a frontier of new lower bounds on the performance of such algorithms, reflecting a tradeoff between a term that depends on the optimal parameter value and a term that depends on the gradients’ rate of growth. Further, we construct a family of algorithms whose performance matches any desired point on this frontier, which no previous algorithm reaches.
APA
Cutkosky, A. & Boahen, K.. (2017). Online Learning Without Prior Information. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:643-677 Available from https://proceedings.mlr.press/v65/cutkosky17a.html.

Related Material