提出高效算法学习鲁棒分类器，确保小扰动下分类结果不变。
Robust learning of halfspaces under log-concave marginals
- 结合多项式回归与噪声敏感性约束的 $oldsymbol{ exttt{l}_1}$ 回归
- 在 $r o 0$ 时边界体积为 $O(r+oldsymbol{ exttt{ε}})$，误差可逼近最优
- 适合关注对抗鲁棒性的机器学习研究者
我们称分类器在范数为 $r$ 的扰动下具有对抗鲁棒性，若以高概率从输入分布中采样点 $x$ 后，其距离 $\le r$ 范围内无异标签点。边界体积定义为点落在不同标签邻域内的概率。本文研究在 $\mathbb{R}^d$ 上服从亚高斯各向同性对数凹分布的输入下，高效学习具有小边界体积的假设函数。线性阈值函数天然具备鲁棒性，边界体积正比于 $r$；多项式回归可高效学习此类函数，输出多项式阈值函数（PTF），但一般情况下边界体积可达 $Ω(1)$，即使 $r \ll 1$。本文提出一种误分类容忍的学习算法，能返回边界体积为 $O(r+\varepsilon)$、半径 $r$ 下的分类器，时间与样本复杂度为 $d^{\tilde{O}(1/\varepsilon^2)}$，与多项式回归持平。算法通过三个新增步骤实现：a) 在噪声敏感性约束下进行 $\ell_1$ 误差回归；b) 结构化划分与取整，同时获得误差 $\textsf{opt} + O(\varepsilon)$ 与噪声敏感性 $O(r+\varepsilon)$；c) 局部修正器将低噪声敏感函数转化为对抗鲁棒函数。
原文摘要 · Abstract (English)
We say that a classifier is \emph{adversarially robust} to perturbations of norm $r$ if, with high probability over a point $x$ drawn from the input distribution, there is no point within distance $\le r$ from $x$ that is classified differently. The \emph{boundary volume} is the probability that a point falls within distance $r$ of a point with a different label. This work studies the task of computationally efficient learning of hypotheses with small boundary volume, where the input is distributed as a subgaussian isotropic log-concave distribution over $\mathbb{R}^d$. Linear threshold functions are adversarially robust; they have boundary volume proportional to $r$. Such concept classes are efficiently learnable by polynomial regression, which produces a polynomial threshold function (PTF), but PTFs in general may have boundary volume $Ω(1)$, even for $r \ll 1$. We give an algorithm that agnostically learns linear threshold functions and returns a classifier with boundary volume $O(r+\varepsilon)$ at radius of perturbation $r$. The time and sample complexity of $d^{\tilde{O}(1/\varepsilon^2)}$ matches the complexity of polynomial regression. Our algorithm augments the classic approach of polynomial regression with three additional steps: a) performing the $\ell_1$-error regression under noise sensitivity constraints, b) a structured partitioning and rounding step that returns a Boolean classifier with error $\textsf{opt} + O(\varepsilon)$ and noise sensitivity $O(r+\varepsilon)$ simultaneously, and c) a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。