- 学习具有低内在维度的概念的平滑分析
传统的监督学习模型中,学习器的目标是基于一些类别中最适应的概念,通过学习任意分布的示例,输出一个与之相差不超过 epsilon 的假设。本研究引入了平滑分析框架,要求学习器只需与对小的随机高斯扰动具有鲁棒性的最佳分类器竞争,从而提供了广泛的 - ICML基于 EM 和 AM 算法的混合线性回归的无知学习
混合线性回归是参数统计学和机器学习领域中一个被广泛研究的问题,本文研究了在没有生成模型的情况下,如何通过异态学习使用期望最大化算法 (EM) 和交替最小化算法 (AM) 进行混合线性回归的参数估计。
- 传导学习是否等同于 PAC 学习?
通过向数据集添加少量样本,我们将依靠 PAC 保证的无偏泛化学习转化为依靠转导保证的无偏泛化学习,从而展示了这些问题的等效性。我们还将所得到的结果扩展到了 agnostic 情况,证明了一种 agnostic 转导学习器可以高效转化为 ag - 高斯数据的统计子群公平性的多项式时间审计
我们研究了具有统计子群公平性概念的分类器稽核问题。在高斯分布和一些先前的工作中,我们采用了一种新的方法来审核均匀半空间子群的统计公平性,并获得了多项式时间逼近方案(PTAS),在通用半空间子群和高斯特征分布条件下,没有密码学假设可以保证任何 - 无知地利用查询学习多索引模型
研究了高斯分布下对于无偏学习任务的查询访问权限的能力。聚焦于多指数模型(MIMs),研究表明查询访问权限在无偏学习 MIMs 方面相对于随机样本具有显著的运行时改进作用。
- 非平凡节省的不可知成员查询学习:新结果和技术
设计剩余计算量较少的算法来解决在不确定学习模型中的问题是一项具有挑战性的任务。本文通过提出多个不确定学习算法,重点是针对大小与计算能力相关的电路的学习,探讨了如何节省计算时间,并在统一分布下进行学习。
- 高效无知学习与平均光滑度
我们研究了分布自由的非参数回归,根据 Ashlagi 等人(2021)提出的一种平均平滑性概念,该概念度量了函数相对于任意未知基础分布的 “有效” 平滑程度。我们提供了分布自由的均匀收敛界限,以及与计算高效的无知学习算法相匹配的采样复杂度。 - 使用全能预测器进行单指数模型的不可知学习
本论文给出了学习任意单指标模型的全新结果,其中所需的激活函数参数满足 Lipschitz 范数和单调性,算法及分析基于 Bregman 距离和匹配损失的联系,同时也对 GLMtron 和逻辑回归等算法在普遍学习场景给出了新的保证。
- 预测、学习、一致收敛和规模敏感维度
提出了一种新的学习算法,利用基于 Vapnik 维度的泛化界限定了算法的误差上界,并根据学习任务的特性使用一种依赖于尺度的维度定义,获得了新的打包数边界和样本复杂度上界,进而得到了一系列关于学习性质和可学性的充分条件和必要条件。
- 单调函数的无偏妥善学习:超越黑盒校正障碍
本论文提出了第一个适用于单调布尔函数的无偏、高效、正确的学习算法,并使用凸优化步骤增进了不正确学习算法。同时,该工作还给出了估计未知函数到单调性的距离的算法,这两个算法的运行时间及假设评估时间为 2^(Õ(√n/ε))
- 高斯边缘下分别学习半空间和 ReLU 的近最优 SQ 下界
该论文研究了在高斯边际下以不可知方式学习半空间和 ReLU 的基本问题,证明了这些问题的统计查询下限。
- 通过函数梯度计算统计查询下限
该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题,给出了统计查询下限。通过梯度提升过程对之前的低界进行放大,对具体问题 ReLU 回归(等同于伪装学习 ReLU),我们证明任何统计查询算法都必须使用至少 2^(n^c) ε 个查询 - 拥有公共数据访问权限的私有学习限制
讨论私人和公共学习示例的差异隐私问题,证明可通过公共样本数为 $d/\alpha$ 和私有标记样本数为 $d/\alpha^2$ 实现平均误差为 $\alpha$ 的 VC-dimension $d$ 假设类别的免疫性学习,提出与之相匹配的 - 不可知论联邦学习
该研究提出了一种基于混合客户端分布的不可知联合学习框架,以增加对客户端的公正性,并给出了一种快速的、随机的最优化算法,以用于其目标下的联合学习。
- 不可知选择性分类主动学习与不一致系数的关系
本研究提出了改进的 PCS 算法 ILESS,它可以在不需要任何假设的情况下实现快速拒绝率,并证明了 Hanneke 不一致系数的多对数界与任何 PCS 学习算法(如 ILESS)存在快速拒绝率以及新的基于不一致性的主动学习算法 Activ - MM量子学习理论概览
本文调查了量子学习理论,描述了准确学习、PAC 学习和精通学习三种学习模型的主要结果,这些学习是使用经典或量子示例的机器学习的理论方面。
- Margin 多类别分类器的 Lp-norm Sauer-Shelah 引理
该研究探讨了在不确定学习框架下,多类别模式分类理论中的一个主要开放问题,即分类器的复杂性如何随类别数目变化。通过使用基于边界的分类器,并结合 Lp - 范数 Sauer-Shelah 引理,建立了一种理论界限,可以在 L∞和 L2 范数下导 - 学习半空间的复杂性理论限制
该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题,证明了最坏情况下的性能和效率的复杂性。
- NIPS基于在线学习的增强框架
通过利用增强学习和在线学习之间的对偶性,提出了一个强大的增强学习框架,开发了多种算法解决了多个实用和理论上有趣的问题,包括稀疏增强、平滑分布增强、识别学习和一些在线学习算法的广义化。
- 关于 Agnostic 学习的近似弹性、单调性和复杂性
研究了布尔函数的近似弹性和同一分布下概念类的不可知学习的关系,最终提出了单调布尔函数的近似鲁棒函数存在性和构造方法,结合特征推断了对单调函数散族不可知学习的几乎最优下界。