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

Apr, 2023

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

Agnostic proper learning of monotone functions: beyond the black-box correction barrier

Jane Lange, Arsen Vasilyan

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

Abstract

We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given $2^{\tilde{O}(\sqrt{n}/\varepsilon)}$ uniformly random examples of an unknown function $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$, our algorithm outputs a hypothesis $g:\{\pm 1\}^n \rightarrow \{\pm 1\}$ that is monotone and $(\mathrm{opt} + \varepsilon)$-close

agnostic learning monotone function sample-efficient algorithm additive error convex optimization

发现论文，激发创造

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

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

May, 2014

单调学习

通过黑盒 Oracle 访问和转换算法 A，提出了将任意学习算法 A 转换为具有类似表现的单调算法的方法，并解决了多个关于单调学习算法的问题。

Feb, 2022

单调函数的自适应逼近

研究了用 GreedyBox 算法逼近单调非减函数的问题，证明了该算法在任何函数上都达到了最优样本复杂度，特别是对于分段平滑的函数，通过简单修改甚至达到了最优的极小最大逼近速率，并进行了数值实验验证。

Sep, 2023

非平凡节省的不可知成员查询学习：新结果和技术

设计剩余计算量较少的算法来解决在不确定学习模型中的问题是一项具有挑战性的任务。本文通过提出多个不确定学习算法，重点是针对大小与计算能力相关的电路的学习，探讨了如何节省计算时间，并在统一分布下进行学习。

Nov, 2023

决策树归纳的可证明保证：零知识条件

该研究的主要关键词有决策树学习、独立设置、单调函数、启发式算法和误差分析。该研究提供了一种基于启发式算法的决策树学习方法，可以在独立设置下优化误差，并取得了匹配近似下限。

Jun, 2020

单调随机优化的半强盗学习

通过提供一种具有与最佳近似算法（在已知分布下）相对于平方根的 T 乘以 log T 束缚的通用在线学习算法，在半探测器环境中解决了在一大类 “单调” 随机问题中对于未知分布是否能够获得良好（近似）算法进行学习的问题。我们的框架适用于随机优化的若干基本问题，如先知不等式、潘多拉盒、随机背包、随机匹配和随机次模优化。

Dec, 2023

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

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

Dec, 2023

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

在罚函数为 $L_2^2$ 的超验模型中，我们研究了学习单指数模型的问题，并提出了一种高效的学习算法，它在一系列分布和广泛类别的单调和 Lipschitz 链函数下，能够以常数因子逼近最优损失。这是第一个高效的常数因子逼近超验学习器，甚至适用于高斯数据和任何非平凡的链函数类别。我们算法与分析的主要技术要素是优化中的一种新概念，我们称之为对齐锐度，这可能具有更广泛的兴趣。

Feb, 2024

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

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

Sep, 2023

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

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

Feb, 2020