论文标题
Massart噪声学习半空间的最佳SQ下限
Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise
论文作者
论文摘要
我们给出了紧密的统计查询（SQ）下限，以在存在Massart噪声的情况下学习半个空间。特别是，假设所有标签都以$η$的概率损坏。我们表明，对于任意$η\，在[0,1/2] $中，每个平方算法实现错误分类误差要比$η$更好地分类错误，需要查询超多个单位的准确性或至少是超级多项式数量的质疑。此外，即使信息从理论上获得最佳错误$ \ mathrm {opt} $与$ \ exp \ left（ - \ log^c（d）\ right）$小的小，其中$ 0 <c <c <c <1 $是任意的绝对常数，并且是nosexpactements的压倒性金额。我们的下限匹配已知的多项式时间算法，在SQ框架中也可以实现。以前，这样的下限仅排除算法达到错误$ \ mathrm {opt} +ε$或错误或错误比$ω（η）$更好，或者，如果$η$接近$ 1/2 $，错误$η-o_η（1）$，在$o_η（1）$中，$o_η（1）$在$ d $中是$ d $ und $ d $ n $ n $ 1/2/$ 1/to $ 1/to $ 1/to $ 1/ 结果，我们还表明，在$（a，α）$ -TSYBAKOV模型中，实现错误分类错误的误差要比$ 1/2 $更好，$ a $ a $ a $ a $ a $ a $ a $ a $ a $。
We give tight statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. In particular, suppose that all labels are corrupted with probability at most $η$. We show that for arbitrary $η\in [0,1/2]$ every SQ algorithm achieving misclassification error better than $η$ requires queries of superpolynomial accuracy or at least a superpolynomial number of queries. Further, this continues to hold even if the information-theoretically optimal error $\mathrm{OPT}$ is as small as $\exp\left(-\log^c(d)\right)$, where $d$ is the dimension and $0 < c < 1$ is an arbitrary absolute constant, and an overwhelming fraction of examples are noiseless. Our lower bound matches known polynomial time algorithms, which are also implementable in the SQ framework. Previously, such lower bounds only ruled out algorithms achieving error $\mathrm{OPT} + ε$ or error better than $Ω(η)$ or, if $η$ is close to $1/2$, error $η- o_η(1)$, where the term $o_η(1)$ is constant in $d$ but going to 0 for $η$ approaching $1/2$. As a consequence, we also show that achieving misclassification error better than $1/2$ in the $(A,α)$-Tsybakov model is SQ-hard for $A$ constant and $α$ bounded away from 1.
