半空间学习单项式是困难的

Dec, 2010

Agnostic Learning of Monomials by Halfspaces is Hard

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

TL;DR该研究证明了在符合某些要求的示例分布下，多项式的弱会混淆学习几乎不可能，即使在输出更大的概念类的假设的情况下也是如此，这种难度结果从某种程度上包括以前的研究结果，包括最近的对单项式和半空间的适当学习的难度结果。

Abstract

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\eps)$ of the examples, it is np-hard to find a halfspace that is correct on $(1/2+\eps)$ of the examples, for a

learning theory monomials halfspaces np-hard label cover

发现论文，激发创造

学习半空间的复杂性理论限制

该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题，证明了最坏情况下的性能和效率的复杂性。

May, 2015

半空间对抗性鲁棒适当学习的复杂性（不知情噪音）

我们研究了在分布无关的对抗性健壮 PAC 模型中半空间的计算复杂度，重点研究了 L_p 扰动。我们提出了一种计算有效的学习算法和一种几乎匹配的计算难度结果。我们发现的一个有趣的含义是，L_∞扰动的情况被证明比 2≤p<∞的情况更加计算上困难。

Jul, 2020

学习半空间交集的改进难度结果

通过与半空间和所谓的并行煎饼分布的新颖联系，我们以统一的方式获得了较强（而且令人惊讶地简单）的在不适当的情况下学习半空间交集的下界，这是过去几年强大的高维统计学中许多下界构造的核心，我们还给出了统计查询框架下的无条件难度结果。

Feb, 2024

在图中学习单调半空间的高效算法

学习图上的顶点的二元分类器，特别关注具有特定抽象意义的凸分区类作为分类器，通过多项式时间算法和结构洞见，以及与底层图的关联进行学习，进行了有关监督学习、在线学习和主动学习中的凸分区类的研究和结果验证。

May, 2024

非凸 SGD 学习带有对抗标签噪声的半空间

研究学习同质半空间的非说服学派问题，证明对于一类结构化分布，包括对数凹分布，在误分类误差 O（opt）+eps 下，非凸 SGD 有效地收敛到解决方案。相比之下，证明优化任何凸代理本质上会导致 ω（opt）的误分类误差，即使在高斯边际分布下。

Jun, 2020

一种对半空间进行不可知学习的 PTAS 算法

本文提出了一个以多项式回归和定位技术相结合的算法，用于在 d - 球上均匀分布的情况下，实现对零时最佳半空间分类器的确定性多项式近似方案（PTAS），误差保证为 opt 的 (1+μ)+ε 倍，并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。

Oct, 2014

具备 Massart 噪声的半空间分布无关 PAC 学习

研究分布无关的半空间在 Massart 噪声下的拟准确性学习问题，给出了一个计算复杂度为多项式时间且误分类错误率为 η+ε 的算法。

Jun, 2019

测试者学习半空间的通用算法

本研究提出了一种普适性的半空间测试学习算法，它可以在所有满足 Poincaré 不等式的分布上获得较小误差，具体实现是使用 sum-of-squares 算法检查分布的超对称性。

May, 2023

学习高斯半空间问题中随机分类噪声的近最优界

研究使用高斯分布下随机分类噪声学习半空间的问题，证明算法和统计查询下限，在此基本问题中，存在令人惊讶的信息计算差距，给出了正面的结果和近乎匹配的复杂度，并展示了算法的复杂度下界

Jul, 2023

具有恶意噪声的半空间属性高效学习：近似最优标签复杂度和噪声容错性

研究如何在噪音下进行有效的学习，在保证计算效率的前提下设计了一种主动学习算法，并根据半空间的结构进行加权和风险最小化等方法的技术优化，解决了恶意噪声等问题并且具有良好的属性效率和样本复杂度。

Jun, 2020