Abstract

This open problem asks whether there exists an online learning algorithm forbinary classification that guarantees, for all target concepts, to make asublinear number of mistakes, under only the assumption that the (possiblyrandom) sequence of points X allows that such a learning algorithm can existfor that sequence. As a secondary problem, it also asks whether a specificconcise condition completely determines whether a given (possibly random)sequence of points X admits the existence of online learning algorithmsguaranteeing a sublinear number of mistakes for all target concepts.

 

Quick Read (beta)