标题： 带有随机分类噪声的多类线性分类的统计查询 hardness 显示英文标题

标题： Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise

摘要： 我们研究了在无分布假设的PAC模型中带有随机分类噪声（RCN）的多类线性分类（MLC）任务。 具体来说，学习者会得到一组带标签的例子$(x, y)$，其中$x$是从$R^d$上未知分布中抽取的，并且标签是由一个带有RCN的多类线性分类器生成的。 也就是说，标签$y$根据一个已知的噪声矩阵$H$（具有非负分离$\sigma: = \min_{i \neq j} H_{ii}-H_{ij}$）以概率$H_{ij}$从$i$翻转到$j$。 目标是最小化0-1误差来计算一个假设。 对于只有两个标签的特殊情况，已有工作给出了达到最优误差的多项式时间算法。 令人惊讶的是，即使对于三个标签，关于此任务的复杂性也知之甚少。 作为我们的主要贡献，我们证明了当存在三个或更多标签时，MLC（多标签分类）与RCN（相关噪声）的复杂性变得截然不同。 具体来说，我们证明了这个问题在统计查询（SQ）下有超多项式下界。 更详细地说，即使对于三个标签和常数分离，我们也给出了任何实现最优误差的SQ算法复杂性的超多项式下界。 对于更多的标签数量和更小的分离，我们甚至展示了即使是为了实现接近最优损失的任意常数因子近似或者甚至优于平凡假设的目标，也有超多项式SQ下界。 显示英文摘要

摘要： We study the task of Multiclass Linear Classification (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specifically, the learner is given a set of labeled examples $(x, y)$, where $x$ is drawn from an unknown distribution on $R^d$ and the labels are generated by a multiclass linear classifier corrupted with RCN. That is, the label $y$ is flipped from $i$ to $j$ with probability $H_{ij}$ according to a known noise matrix $H$ with non-negative separation $\sigma: = \min_{i \neq j} H_{ii}-H_{ij}$. The goal is to compute a hypothesis with small 0-1 error. For the special case of two labels, prior work has given polynomial-time algorithms achieving the optimal error. Surprisingly, little is known about the complexity of this task even for three labels. As our main contribution, we show that the complexity of MLC with RCN becomes drastically different in the presence of three or more labels. Specifically, we prove super-polynomial Statistical Query (SQ) lower bounds for this problem. In more detail, even for three labels and constant separation, we give a super-polynomial lower bound on the complexity of any SQ algorithm achieving optimal error. For a larger number of labels and smaller separation, we show a super-polynomial SQ lower bound even for the weaker goal of achieving any constant factor approximation to the optimal loss or even beating the trivial hypothesis.