论文标题
随机链接并加强信息理论泛化范围
Stochastic Chaining and Strengthened Information-Theoretic Generalization Bounds
论文作者
论文摘要
我们提出了一种新方法，将链接技术与信息理论措施结合使用，以绑定机器学习算法的概括误差。与Asadi等人先前提出的基于度量空间的层次分区的确定性链接方法不同，我们提出了一种随机链接方法，该方法用从连续的精炼源编码中借来的抽象的马尔可夫模型代替了分层分区。这种方法比确定性的链接具有三个好处：1）公制空间不一定是界限，2）随后的分析促进以产生更明确的约束； 3）进一步的机会，通过消除分区的几何刚度来优化绑定。拟议的方法包括传统的链条作为特殊情况，因此也可以利用任何确定性的链式结构。我们使用估计高斯平均值和相位检索的问题来说明这些好处。对于前者，我们得出了一个界限，该结合对先前的结果提供了订单改进，而对于后者，我们提供了一个随机链，该链允许对链接参数进行优化。
We propose a new approach to apply the chaining technique in conjunction with information-theoretic measures to bound the generalization error of machine learning algorithms. Different from the deterministic chaining approach based on hierarchical partitions of a metric space, previously proposed by Asadi et al., we propose a stochastic chaining approach, which replaces the hierarchical partitions with an abstracted Markovian model borrowed from successive refinement source coding. This approach has three benefits over deterministic chaining: 1) the metric space is not necessarily bounded, 2) facilitation of subsequent analysis to yield more explicit bound, and 3) further opportunity to optimize the bound by removing the geometric rigidity of the partitions. The proposed approach includes the traditional chaining as a special case, and can therefore also utilize any deterministic chaining construction. We illustrate these benefits using the problem of estimating Gaussian mean and that of phase retrieval. For the former, we derive a bound that provides an order-wise improvement over previous results, and for the latter we provide a stochastic chain that allows optimization over the chaining parameter.
