在特定分布的 PAC 模型下,我们针对学习带有 Massart 噪声的半空间问题进行了研究。我们提出了第一种基于 SGD 的、针对广泛分布(包括对数凹分布)的问题求解的计算机高效算法,并解决了先前研究中的一个悬而未决的问题。
Feb, 2020
该论文描述和分析了一种新的算法,通过对零一损失函数的学习,可以对基于核的半空间进行学习。该算法可以在任何分布下学习核为基础的半空间,并且可以在有限的时间 / 样本内达到最优结果。
May, 2010
本文提出了一个以多项式回归和定位技术相结合的算法, 用于在 d - 球上均匀分布的情况下,实现对零时最佳半空间分类器的确定性多项式近似方案(PTAS),误差保证为 opt 的 (1+μ)+ε 倍, 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。
Oct, 2014
在学习分布转移的基本问题中,我们提出了一个新模型,称为可测试学习,可以通过一个相关的测试来得到分类器在测试分布上的性能证明,并证明了对于一些常见概念类别如半空间、半空间的交、决策树等,以及具有低次 $L_2$- 夹逼多项式逼近器的任何函数类别都可以在这个模型下学习。
Nov, 2023
该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题,证明了最坏情况下的性能和效率的复杂性。
May, 2015
针对高斯训练分布的交叉半空间集的可测试学习,证明了一种新的上界算法,能在多项式时间内实现 TDS 学习,且达到精确度 e,扩展了 TDS 学习工具库。
Apr, 2024
研究学习同质半空间的非说服学派问题,证明对于一类结构化分布,包括对数凹分布,在误分类误差 O(opt)+eps 下,非凸 SGD 有效地收敛到解决方案。相比之下,证明优化任何凸代理本质上会导致 ω(opt)的误分类误差,即使在高斯边际分布下。
Jun, 2020
通过与半空间和所谓的并行煎饼分布的新颖联系,我们以统一的方式获得了较强(而且令人惊讶地简单)的在不适当的情况下学习半空间交集的下界,这是过去几年强大的高维统计学中许多下界构造的核心,我们还给出了统计查询框架下的无条件难度结果。
Feb, 2024
研究分布无关的半空间在 Massart 噪声下的拟准确性学习问题,给出了一个计算复杂度为多项式时间且误分类错误率为 η+ε 的算法。
Jun, 2019
该研究论文介绍了可测试学习的概念,并研究了在测试者接受标准高斯数据的情况下,多项式阈值函数的可测试学习。研究结果表明,任意常数阶的多项式阈值函数在多项式时间内可以以超出误差 ε 的程度可测试地学习,与测试属性的典型模型相匹配。同时,该研究证明了直接证明可测试学习(而非愚弄测试者)的方法在多项式阈值函数上是行不通的。
Jun, 2024