Feb, 2024

通过对齐锐度强大地学习单指数模型

PDF
TL;DR在罚函数为 $L_2^2$ 的超验模型中，我们研究了学习单指数模型的问题，并提出了一种高效的学习算法，它在一系列分布和广泛类别的单调和 Lipschitz 链函数下，能够以常数因子逼近最优损失。这是第一个高效的常数因子逼近超验学习器，甚至适用于高斯数据和任何非平凡的链函数类别。我们算法与分析的主要技术要素是优化中的一种新概念，我们称之为对齐锐度，这可能具有更广泛的兴趣。
single-index models$l_2^2$ losslearning algorithmagnostic modelalignment sharpness
发现论文，激发创造
  • 通过锐度方法强化单个神经元的学习

    研究单个神经元面对对抗标签噪声情况下的 $L_2^2$ 损失学习问题。提出了一种高效算法，适用于广泛的激活函数族，包括 ReLU，并在远比之前工作更微弱的分布假设下近似最优 $L_2^2$ 误差，关键在于优化理论中局部误差界的一种新颖联系。

    Jun, 2023

  • 使用全能预测器进行单指数模型的不可知学习

    本论文给出了学习任意单指标模型的全新结果，其中所需的激活函数参数满足 Lipschitz 范数和单调性，算法及分析基于 Bregman 距离和匹配损失的联系，同时也对 GLMtron 和逻辑回归等算法在普遍学习场景给出了新的保证。

    Jun, 2023

  • 线性样本复杂度下的单指数模型无偏主动学习

    对单指数模型进行主动学习方法的研究，证明了在已知或未知函数情况下，通过统计杠杆得分采样，采集约 O (d) 个样本即可学习出接近最优的单指数模型，且适用于拟合偏微分方程等科学机器学习应用。这种方法无需对数据分布进行假设，在挑战性的对手学习环境中表现出鲁棒性。

    May, 2024

  • 无知地利用查询学习多索引模型

    研究了高斯分布下对于无偏学习任务的查询访问权限的能力。聚焦于多指数模型（MIMs），研究表明查询访问权限在无偏学习 MIMs 方面相对于随机样本具有显著的运行时改进作用。

    Dec, 2023

  • 学习高斯单指标模型的计算复杂性

    单指标模型是高维回归问题，根据未知的一维投影通过非线性、潜在非确定性的变换，标签与输入相关，涵盖了广泛的统计推断任务，提供了在高维领域研究统计和计算权衡的丰富模版。我们证明了在统计查询（SQ）和低次多项式（LDP）框架内计算高效算法所需的样本复杂度最低为 Ω(d^k/2)，其中 k 是与模型关联的 “生成” 指数，我们明确定义了这个指数。此外，通过使用部分跟踪算法建立的匹配上界证明了这个样本复杂度也是充分的。因此，我们的结果表明，在 SQ 和 LDP 类中，只要 k>2，计算与统计之间存在明显的差距。为了完成这个研究，我们提供了具有任意大生成指数 k 的平滑和 Lipschitz 确定的目标函数的示例。

    Mar, 2024

  • Q - 聚合最优学习

    研究具有强凸和 Lipschitz 损失的一般监督学习问题，研究模型选择集成问题。证明了 Q-aggregation 过程将产生期望和高概率上都满足最优 Oracle 不等式的估计器。

    Jan, 2013

  • 单调函数的无偏妥善学习：超越黑盒校正障碍

    本论文提出了第一个适用于单调布尔函数的无偏、高效、正确的学习算法，并使用凸优化步骤增进了不正确学习算法。同时，该工作还给出了估计未知函数到单调性的距离的算法，这两个算法的运行时间及假设评估时间为 2^(Õ(√n/ε))

    Apr, 2023

  • 高效无知学习与平均光滑度

    我们研究了分布自由的非参数回归，根据 Ashlagi 等人（2021）提出的一种平均平滑性概念，该概念度量了函数相对于任意未知基础分布的 “有效” 平滑程度。我们提供了分布自由的均匀收敛界限，以及与计算高效的无知学习算法相匹配的采样复杂度。我们的结果表明，最近对于可实现的平滑函数学习所获得的保证可以转移到无知设置中。在我们的证明的核心，我们根据函数类的夹逼熵建立了函数类的均匀收敛速率，这可能具有独立的研究意义。

    Sep, 2023

  • 预测、学习、一致收敛和规模敏感维度

    提出了一种新的学习算法，利用基于 Vapnik 维度的泛化界限定了算法的误差上界，并根据学习任务的特性使用一种依赖于尺度的维度定义，获得了新的打包数边界和样本复杂度上界，进而得到了一系列关于学习性质和可学性的充分条件和必要条件。

    Apr, 2023

  • 超越高斯数据的单指数模型

    通过研究在浅层神经网络中使用梯度下降方法的稀疏高维函数，展示了它们在线性模型之外进行特征学习的能力。本研究扩展了这一框架，探索了高斯设置以外的情景，并通过假设在高维情形下可以有效地恢复未知方向。

    Jul, 2023