2022/06/27 by Pradeep, Aditya, Nachum, Ido, Gastpar, Michael · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2206.13257
We prove that every online learnable class of functions of Littlestone dimension d admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of such a globally stable algorithm is large yet finite, roughly exponential in d. We also show there is room for improvement; for a canonical online learnable class, indicator functions of affine subspaces of dimension d, the information complexity can be upper bounded logarithmically in d.