首个多项式时间算法，能在数据污染下准确学习超立方体上的半空间。
A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
- 提出新算法，不依赖连续分布的结构特性
- 误差仅随噪声率η的常数次方增长，与ε无关
- 适用于离散分布，对从业者更实用
我们给出首个在超立方体均匀分布下，针对数据污染情况学习半空间的全多项式时间算法。该算法在任意篡改比例的样本和标签攻击下，仍能实现$η^{O(1)}+ε$的误差上界，其中η为噪声率。此前二十年的研究均无法在离散分布上获得此类保证，或依赖连续分布的反集中性质，且存在$1/ε$的超多项式依赖。本工作通过引入新型广义线性模型学习方法，仅需激活函数李普希茨常数的多对数依赖，避免了传统分析路径。研究揭示：在离散分布上进行监督学习的难度远低于以往认知。
原文摘要 · Abstract (English)
We give the first fully polynomial-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube in the presence of contamination, where an adversary may corrupt some fraction of examples and labels arbitrarily. We achieve an error guarantee of $η^{O(1)}+ε$ where $η$ is the noise rate. Such a result was not known even in the agnostic setting, where only labels can be adversarially corrupted. All prior work over the last two decades has a superpolynomial dependence in $1/ε$ or succeeds only with respect to continuous marginals (such as log-concave densities). Previous analyses rely heavily on various structural properties of continuous distributions such as anti-concentration. Our approach avoids these requirements and makes use of a new algorithm for learning Generalized Linear Models (GLMs) with only a polylogarithmic dependence on the activation function's Lipschitz constant. More generally, our framework shows that supervised learning with respect to discrete distributions is not as difficult as previously thought.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。