On Lower Bounds for Statistical Learning Theory
On Lower Bounds for Statistical Learning Theory
复制标题
论统计学习理论的下界
作者：
Po
近年来，信息论工具在统计机器学习中发挥着越来越普遍的作用。除了开发高效、计算上可行的算法来分析复杂数据集之外，确定此类算法是否是“最优”的具有理论上的重要性，因为没有其他算法可以导致更小的统计误差。本文对用于推导估计和学习的信息论下界的各种技术进行了调查。我们重点关注多臂老虎机的参数和函数估计、社区恢复和在线学习的设置。一个共同的主题是，通过将统计学习问题与信道解码问题联系起来来建立下界，其中可以导出涉及信息论量（例如互信息、总变异距离和 Kullback-Leibler 散度）的下界。最后，我们讨论了如何使用信息论量来衡量从因果关系到医学成像等机器学习应用中的独立性，并提到以数据驱动的方式有效估计这些量的技术。
In recent years, tools from information theory have played an increasingly prevalent role in statistical machine learning. In addition to developing efficient, computationally feasible algorithms for analyzing complex datasets, it is of theoretical importance to determine whether such algorithms are “optimal” in the sense that no other algorithm can lead to smaller statistical error. This paper provides a survey of various techniques used to derive information-theoretic lower bounds for estimation and learning. We focus on the settings of parameter and function estimation, community recovery, and online learning for multi-armed bandits. A common theme is that lower bounds are established by relating the statistical learning problem to a channel decoding problem, for which lower bounds may be derived involving information-theoretic quantities such as the mutual information, total variation distance, and Kullback–Leibler divergence. We close by discussing the use of information-theoretic quantities to measure independence in machine learning applications ranging from causality to medical imaging, and mention techniques for estimating these quantities efficiently in a data-driven manner.
通过消息传递进行子矩阵定位
影响因子：
6
作者：
Hajek, Bruce;Wu, Yihong;Xu, Jiaming
通讯作者：
Xu, Jiaming