关于 Agnostic 学习的近似弹性、单调性和复杂性

May, 2014

关于 Agnostic 学习的近似弹性、单调性和复杂性

Approximate resilience, monotonicity, and the complexity of agnostic learning

Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer

TL;DR研究了布尔函数的近似弹性和同一分布下概念类的不可知学习的关系，最终提出了单调布尔函数的近似鲁棒函数存在性和构造方法，结合特征推断了对单调函数散族不可知学习的几乎最优下界。

Abstract

A function $f$ is $d$-resilient if all its Fourier coefficients of degree at most $d$ are zero, i.e., $f$ is uncorrelated with all low-degree parities. We study the notion of $\mathit{approximate}$ $\mathit{resilience}$ of Boolean functions, where we say that $f$ is $\alpha$-approximately $d$-resilient if $f$ is $\alpha$-close to a $[-1,1]$-valued $d$-resili

approximate resilience agnostic learning concept classes monotone boolean functions resilient functions

发现论文，激发创造

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

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

Apr, 2023

韧性单调子模函数最大化

本研究关注机器学习、优化和控制中的鲁棒优化问题，在面临多种故障或攻击时，提出了首个可扩展的曲率相关算法，用于近似求解单调子模目标函数，保证了优秀的逼近性能，并使用实验证明了该算法的有效性。

Mar, 2017

弹性：在任意异常值存在情况下进行学习的标准

引入鲁棒性标准使属性的计算更加稳健，包括鲁棒分布学习、鲁棒估计碰巧矩阵模型和鲁棒均值估计，提供新的信息论和算法结果。

Mar, 2017

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

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

Sep, 2023

确定性系统中基于函数逼近的无神论 Q 学习：逼近误差和样本复杂度的严格界限

研究了确定性系统中基于函数逼近的 agnostic Q-learning 问题，并提出了一种新颖的递归算法，证明了采用该算法可以找到最优策略，同时满足多项约束条件。

Feb, 2020

分布无关可靠学习

研究可靠的不可知学习框架中的问题，使用单边多项式逼近可学习可靠分类器和构建适当的单边多项式逼近来学习大多数时完全可靠，这些算法还满足强属性效率属性并提供样本复杂度和运行时间之间的平滑折衷。

Feb, 2014

关于强鲁棒分类的困难程度

本文研究了机器学习模型对抗攻击的容易受攻击性问题，并从计算学习理论的角度探究了鲁棒学习的可行性和计算复杂度，并给出了相应的计算困难性证明。

Sep, 2019

多项式阈值函数可测学习

该研究论文介绍了可测试学习的概念，并研究了在测试者接受标准高斯数据的情况下，多项式阈值函数的可测试学习。研究结果表明，任意常数阶的多项式阈值函数在多项式时间内可以以超出误差 ε 的程度可测试地学习，与测试属性的典型模型相匹配。同时，该研究证明了直接证明可测试学习（而非愚弄测试者）的方法在多项式阈值函数上是行不通的。

Jun, 2024

分布式学习能力与稳健性

对于分布学习问题，我们研究了可学习性和鲁棒（或不可知）可学习性之间的关系，发现与其他学习设置（例如函数类的 PAC 学习）相反，概率分布类的可实现学习性并不意味着其不可知可学习性。我们进一步研究了什么样的数据损坏可以破坏分布类的可学习性以及该可学习性对于怎样的损坏是鲁棒的。结果表明，概率分布类的可实现学习性仅对加性损坏具有鲁棒性，而不具备对减性损坏的鲁棒性。我们还探索了与压缩方案和差分隐私可学习性相关的含义。

Jun, 2024

二次型 Littlewood-Offord 问题的弹性

我们研究高维数据的统计弹性，结果提供敌对噪声对二次 Radamecher 混沌的反集中性质的影响估计量，其中 M 是一个固定的（高维）矩阵，ξ 是一个符合射线混合向量。具体而言，我们研究了 ξ 可以承受多少敌对符号翻转而不会 “膨胀”σ 为上证∈RP {ξTMξ=x}，从而使原始分布变得更 “粒状” 和带有对这个分布的敌对偏差。我们的结果提供了二次和双线性 Rademacher 混乱的统计弹性下界估计，这些下界在关键范围内被证明是渐近紧密的。

Feb, 2024