Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?
This addresses a foundational theoretical gap in online learning for researchers, but it is incremental as it frames existing challenges without new solutions.
This paper poses an open problem about whether an online learning algorithm exists that guarantees a sublinear number of mistakes for binary classification under minimal assumptions, specifically when such learning is possible for a given sequence of points, and also asks if a concise condition can determine this possibility.
This 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.