Fundamental Limits of Prediction, Generalization, and Recursion: An Entropic-Innovations Perspective
This provides theoretical foundations for understanding prediction limits across machine learning, but is incremental in combining existing information-theoretic and innovations approaches.
The paper derives fundamental lower bounds on prediction error norms that apply to any algorithm and data distribution, and characterizes conditions to achieve these bounds using information-theoretic measures. It also extends these results to analyze generalization limits in learning problems and recursive algorithms.
In this paper, we examine the fundamental performance limits of prediction, with or without side information. More specifically, we derive generic lower bounds on the $\mathcal{L}_p$ norms of the prediction errors that are valid for any prediction algorithms and for any data distributions. Meanwhile, we combine the entropic analysis from information theory and the innovations approach from prediction/estimation theory to characterize the conditions (in terms of, e.g., directed information or mutual information) to achieve the bounds. We also investigate the implications of the results in analyzing the fundamental limits of generalization in fitting (learning) problems from the perspective of prediction with side information, as well as the fundamental limits of recursive algorithms by viewing them as generalized prediction problems.