Fundamental Limits of Online Learning: An Entropic-Innovations Viewpoint

Abstract--In this paper, we examine the fundamental performance limitations of online machine learning, by viewing th e online learning problem as a prediction problem with causal side information. T owards this end, we combine the entropic analysis from information theory and the innovations appro ach from prediction theory to derive generic lower bounds on the prediction errors as well as the conditions (in terms of, e.g., d irected information) to achieve the bounds. It is seen in general tha t no specific restrictions have to be imposed on the learning algo rithms or the distributions of the data points for the performance b ounds to be valid. In addition, the cases of supervised learning, s emi-supervised learning, as well as unsupervised learning can a ll be analyzed accordingly. We also investigate the implication s of the results in analyzing the fundamental limits of generalizat ion.