高维多指标模型中弱可学习性的基本限制
单指标模型是高维回归问题,根据未知的一维投影通过非线性、潜在非确定性的变换,标签与输入相关,涵盖了广泛的统计推断任务,提供了在高维领域研究统计和计算权衡的丰富模版。我们证明了在统计查询(SQ)和低次多项式(LDP)框架内计算高效算法所需的样本复杂度最低为 Ω(d^k/2),其中 k 是与模型关联的 “生成” 指数,我们明确定义了这个指数。此外,通过使用部分跟踪算法建立的匹配上界证明了这个样本复杂度也是充分的。因此,我们的结果表明,在 SQ 和 LDP 类中,只要 k>2,计算与统计之间存在明显的差距。为了完成这个研究,我们提供了具有任意大生成指数 k 的平滑和 Lipschitz 确定的目标函数的示例。
Mar, 2024
神经网络通过高维嘈杂的数据识别低维相关结构,我们对其工作原理的数学理解仍然有限。本文研究了使用基于梯度的算法训练的两层浅层神经网络的训练动态,并讨论了它们在具有低维相关方向的多指标模型中学习相关特征的方式。
May, 2024
通过研究在浅层神经网络中使用梯度下降方法的稀疏高维函数,展示了它们在线性模型之外进行特征学习的能力。本研究扩展了这一框架,探索了高斯设置以外的情景,并通过假设在高维情形下可以有效地恢复未知方向。
Jul, 2023
针对模型类如何拟合标记数据的问题,我们提出了一种计算学习能力的方法,可以使用较小的数据量得出精确结果。该方法也适用于二元分类问题,并在多种真实和合成数据集上得到了验证。
May, 2018
传统的监督学习模型中,学习器的目标是基于一些类别中最适应的概念,通过学习任意分布的示例,输出一个与之相差不超过 epsilon 的假设。本研究引入了平滑分析框架,要求学习器只需与对小的随机高斯扰动具有鲁棒性的最佳分类器竞争,从而提供了广泛的学习结果。此类别包括依赖于低维子空间(即多索引模型)和具有有界高斯曲面积的概念。有趣的是,我们的分析还为传统的非平滑框架(如学习边际)提供了新的结果。特别地,在时间复杂度为 k ^poly(log(k)/(epsilon * gamma))的算法中,我们首次获得了关于 k 半空间求交的无偏学习算法,这里 gamma 是边际参数。在之前的工作中,最优的运行时间复杂度是指数级的(Arriaga 和 Vempala,1999 年)。
Jul, 2024
本文研究了梯度下降算法在光滑内核中的应用限制,提出了基于特征向量预处理的 EigenPro 迭代优化算法,通过注入小规模二阶信息以改善此限制,从而实现更好的收敛性能。
Mar, 2017
本文通过一次性的方法在神经网络中学习高准确度的线、曲线、和单纯形来寻找各种应对方法,达到了独立训练网络套索并在训练成本上类似的计算成本,增加了分类器的鲁棒性和准确性。
Feb, 2021
我们研究了数据分类问题,探究了机器学习模型的特征空间几何形态、数据分布结构和泛化能力之间的关系,发现非线性特征转换对于将原始数据映射至高维甚至无限维空间对模型的泛化能力有重要影响。
Nov, 2022
近期的学习研究显示,学习问题的可学习性可能是不可判定的,或者与标准集合论的 ZFC 公理无关。此外,这些问题的可学习性可能不是有限特性:简单来说,通过检查问题的有限投影无法检测出可学习性。然而,学习理论在定义学习的维度时充斥着只考虑问题的有限限制的概念,即具有有限特性的性质。如何调和这些结果呢?具体而言,哪些学习问题容易受到逻辑不可判定性的影响,哪些问题可以用有限特性来解决?我们证明了具有测度损失的监督学习的困难可以通过有限特性来精确描述。尤其是我们证明了学习一个假设类的样本复杂度可以通过检查其有限投影来判断。对于广泛类别的适当损失函数的可实现和了解学习,我们证明了一个确切的紧致性结果:一个类别在具有给定样本复杂度时可以学习,仅当其所有有限投影也是如此。对于具有不适当损失函数的可实现学习,我们证明了样本复杂度的确切紧致性可能会失败,并提供了样本复杂度相差 2 倍的相匹配上下界。我们猜想对于了解学习的情况可能存在更大的差距。我们技术工作的核心是一个关于变量分配的紧致性结果,它在保持函数类别在目标值以下方面具有广泛的兴趣,该结果推广了霍尔(Hall)经典匹配定理,可能具有独立的兴趣。
Feb, 2024
探讨了通过简单的 Hebbian 学习算法分离高维数据集中的非高斯分量的情况,介绍了该算法适用于学习 Stiefel 流形的自然梯度变体,并研究了大输入维度下两种算法的参数轨迹。
Sep, 2003