【EPFL博士论文】统计学习问题的基本限制:块模型和神经网络，183页pdf

本论文聚焦于两个选定的学习问题：1）图模型上的统计推断；2）神经网络上的梯度下降，共同的目标是定义和分析表征基本限制的度量。

在论文的第一部分，我们考虑了图上的自旋同步问题，该问题包括基于图边缘上它们的交互的噪声观察来重构图顶点上的n个独立自旋的向量。特别是，我们考虑了带擦除（BEC）边信息的同步模型，在这些模型中，一小部分节点的自旋被揭示，并研究了这样的边信息如何影响远距离位点上的自旋的相关性。我们表明，在树上，当边缘观察给出的远距离位点上的自旋几乎是独立的时，那么给出边缘观察和边信息的自旋仍然几乎是独立的。我们推测这对任何图都适用。另一方面，（Kanade等人，2014）推测，在正规树和Galton-Watson树上，只要揭示了任何小部分节点标签，无穷深度处的边界就无法检测到根位，即使在重构范围内也是如此。我们解释了这如何用于计算具有两个对称社区的稀疏随机块模型（SBM）的极限熵。最后，我们表明，后一推测不适用于每一棵树。

在论文的第二部分，我们考虑了用全连接神经网络上的梯度下降（GD）学习布尔目标函数的问题。我们引入了一个概念，即神经网络在初始化时与目标函数之间的“初始对齐”（INAL），并证明如果网络和目标在初始时没有显著的INAL，那么在具有i.i.d. 高斯初始化的全连接网络上的带噪声梯度下降无法在多项式时间内学习目标。我们表明，对于用相关性损失训练的有限深度网络，结果可以扩展到布尔输入之外。此外，我们证明，在相似的设置中，泛化误差可以用目标函数的噪声稳定性来下界，支持了（Zhang等人，2021）提出的一个推测。

然后，我们展示，在分布转换设置中，当数据扣留对应于冻结单一特征时，泛化误差在几个相关架构上都承认布尔影响的紧密特征。这一点在线性模型上得到了证明，并在其他模型，如MLP和Transformers上得到了实验支持。特别是，这提出了这样一个假设，对于这些架构和学习逻辑函数，GD倾向于对低度表示有一个隐性偏好。

最后，我们考虑了一种‘课程学习’（CL）策略，用于学习二进制字符串上的k奇偶校验。我们表明，一个明智的训练样本选择，涉及两个或更多的产品分布，允许在d^O(1)时间内用GD训练的全连接神经网络学习k奇偶校验。我们进一步表明，对于另一类函数，即‘汉明混合’，涉及有界数量的产品分布的CL策略不是有益的。