Learning general halfspaces with general Massart noise under the Gaussian distribution
Learning general halfspaces with general Massart noise under the Gaussian distribution
复制标题
DOI：
10.1145/3519935.3519970
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;D. Kane;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
我们研究了在Massart模型中使用Massart噪声的PAC学习半空间的问题。 [0,1/2]。均质（即，分离的超平面都通过原点），（ii）参数η严格小于1/2，当我们研究一般假设中的任何一个时，都不知道。问题并确定以下内容：[leftmargin = *]对于η<1/2，我们给出了带有样品和计算复杂性doη（log（1/γ））poly（1/є）的一般半空间的学习算法，其中γmaxmax max {є，min {pr [f（x）= 1]，pr [f（x）= -1]}}是目标半空间f的“偏差”。 1/2。使用样品和计算复杂性Oє（1）DO（1/є），即使是同质半空间的均值的算法，该结果是新的上限与DΩ的几乎匹配的SQ下限（log（1/є）），即使对于均匀半空间的特殊情况，我们的结果也可以合理地描述了与一般半空间的复杂性。高斯的边缘。我们的技术依赖于低度多项式的存在（或不存在），其期望将Massart Halfspaces与随机噪声区分开来。
We study the problem of PAC learning halfspaces on ℝd with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the label of each point x with unknown probability η(x) ≤ η, for some parameter η ∈ [0,1/2]. The goal is to find a hypothesis with misclassification error of OPT + є, where OPT is the error of the target halfspace. This problem had been previously studied under two assumptions: (i) the target halfspace is homogeneous (i.e., the separating hyperplane goes through the origin), and (ii) the parameter η is strictly smaller than 1/2. Prior to this work, no nontrivial bounds were known when either of these assumptions is removed. We study the general problem and establish the following: [leftmargin = *] For η <1/2, we give a learning algorithm for general halfspaces with sample and computational complexity dOη(log(1/γ))poly(1/є), where γ max{є, min{Pr[f(x) = 1], Pr[f(x) = −1]} } is the “bias” of the target halfspace f. Prior efficient algorithms could only handle the special case of γ = 1/2. Interestingly, we establish a qualitatively matching lower bound of dΩ(log(1/γ)) on the complexity of any Statistical Query (SQ) algorithm. For η = 1/2, we give a learning algorithm for general halfspaces with sample and computational complexity Oє(1) dO(log(1/є)). This result is new even for the subclass of homogeneous halfspaces; prior algorithms for homogeneous Massart halfspaces provide vacuous guarantees for η=1/2. We complement our upper bound with a nearly-matching SQ lower bound of dΩ(log(1/є) ), which holds even for the special case of homogeneous halfspaces. Taken together, our results qualitatively characterize the complexity of learning general halfspaces with general Massart noise under Gaussian marginals. Our techniques rely on determining the existence (or non-existence) of low-degree polynomials whose expectations distinguish Massart halfspaces from random noise.