Fundamental computational limits of weak learnability in high-dimensional multi-index models
Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, Florent Krzakala
多索引模型 - 函数仅依赖于其投影在子空间上的非线性变换 - 是使用神经网络研究特征学习的有用基准。 本文研究了本假设类中高效可学习性的理论边界,侧重于用一阶迭代算法弱恢复其低维结构所需的最小样本复杂性,在高维方案中,样本 n=α d 的数量与协方差维度 d 成正比。 我们的发现分为三部分:(i)我们确定在哪些条件下,可以通过任何 α>0; (ii) 单序算法的单步学习一个微不足道的子空间,如果琐碎子空间是空的,我们为一个简单的子空间的存在提供了必要和充分的条件,其中只能在某个样本复杂度 α>α_c 之上学习方向,其中α_c标记了计算阶段的过渡。 在一组有限但有趣的真正困难的方向 - 类似于平价问题 - α_c被发现存在差异。 最后,(iii)我们表明,不同方向之间的相互作用会导致复杂的分层学习现象,当耦合到更容易时,可以依次学习方向。 我们详细讨论了与这些功能相关的大楼梯图片(并将其与原始楼梯进行比较)。 我们的理论建立在一阶迭代方法中近似消息传递的最优性之上,在广泛的算法中划定了基本的可学习性极限,包括受过梯度下降训练的神经网络,我们在此背景下进行了讨论。
Multi-index models - functions which only depend on the covariates through a non-linear transformation of their projection on a subspace - are a useful benchmark for investigating feature learning with neural nets. This paper examines the theoretical boundaries of efficient learnability in this hypothesis class, focusing on the minimum sample complexity required for weakly recovering their low-dimensional structure with first-order iterative algorithms, in the high-dimensional regime where the n...
