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$标准中得出一般较低的标准。与此同时,我们结合了信息理论和预测/估计理论的创新分析,将预测/估计理论作为达到极限的条件(例如,直接信息或相互信息)的特征。我们还从预测的角度从附带信息的角度分析在适应(学习)问题时一般化的基本限制以及将累进算法的基本限制作为普遍预测问题来分析这些结果的影响。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【CIKM2020】神经逻辑推理,Neural Logic Reasoning
专知会员服务
49+阅读 · 2020年8月25日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年5月31日
Arxiv
0+阅读 · 2021年4月2日
Inductive Relation Prediction by Subgraph Reasoning
Arxiv
11+阅读 · 2020年2月12日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
【CIKM2020】神经逻辑推理,Neural Logic Reasoning
专知会员服务
49+阅读 · 2020年8月25日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Arxiv
0+阅读 · 2021年5月31日
Arxiv
0+阅读 · 2021年4月2日
Inductive Relation Prediction by Subgraph Reasoning
Arxiv
11+阅读 · 2020年2月12日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
Top
微信扫码咨询专知VIP会员