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.
翻译:在本文中,我们研究预测的基本性能限度,无论有无附带信息。更具体地说,我们从任何预测算法和任何数据分布均适用的预测错误的$mathcal{L ⁇ p$标准中得出一般较低的标准。与此同时,我们结合了信息理论和预测/估计理论的创新分析,将预测/估计理论作为达到极限的条件(例如,直接信息或相互信息)的特征。我们还从预测的角度从附带信息的角度分析在适应(学习)问题时一般化的基本限制以及将累进算法的基本限制作为普遍预测问题来分析这些结果的影响。