Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?

Steve Hanneke
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4642-4646, 2021.

Abstract

The open problem asks whether there exists an online learning algorithm for binary classification that guarantees, for all target concepts, to make a sublinear number of mistakes, under only the assumption that the (possibly random) sequence of points X allows that such a learning algorithm can exist for that sequence. As a secondary problem, it also asks whether a specific concise condition completely determines whether a given (possibly random) sequence of points X admits the existence of online learning algorithms guaranteeing a sublinear number of mistakes for all target concepts.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-open-problem-hanneke21b, title = {Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?}, author = {Hanneke, Steve}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {4642--4646}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/hanneke21b/hanneke21b.pdf}, url = {https://proceedings.mlr.press/v134/open-problem-hanneke21b.html}, abstract = {The open problem asks whether there exists an online learning algorithm for binary classification that guarantees, for all target concepts, to make a sublinear number of mistakes, under only the assumption that the (possibly random) sequence of points X allows that such a learning algorithm can exist for that sequence. As a secondary problem, it also asks whether a specific concise condition completely determines whether a given (possibly random) sequence of points X admits the existence of online learning algorithms guaranteeing a sublinear number of mistakes for all target concepts.} }
Endnote
%0 Conference Paper %T Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible? %A Steve Hanneke %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-open-problem-hanneke21b %I PMLR %P 4642--4646 %U https://proceedings.mlr.press/v134/open-problem-hanneke21b.html %V 134 %X The open problem asks whether there exists an online learning algorithm for binary classification that guarantees, for all target concepts, to make a sublinear number of mistakes, under only the assumption that the (possibly random) sequence of points X allows that such a learning algorithm can exist for that sequence. As a secondary problem, it also asks whether a specific concise condition completely determines whether a given (possibly random) sequence of points X admits the existence of online learning algorithms guaranteeing a sublinear number of mistakes for all target concepts.
APA
Hanneke, S.. (2021). Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:4642-4646 Available from https://proceedings.mlr.press/v134/open-problem-hanneke21b.html.

Related Material