标题： 从NP难性得出的计算统计权衡 显示英文标题

标题： Computational-Statistical Tradeoffs from NP-hardness

摘要： 计算机科学和统计学中的一个核心问题是，高效的算法是否能够达到统计问题的信息理论极限。 在平均情况假设下已经证明了许多计算-统计权衡，但由于统计问题本质上是平均情况的，因此将其建立在标准最坏情况假设上一直是一个挑战。 在PAC学习中，这种权衡首次被研究，问题在于计算效率是否会导致使用比信息理论所必需更多的样本。 我们基于$\mathsf{NP}$硬性获得以下结果： $\circ$在$\mathsf{NP}$需要指数时间的假设下，得到精确的计算统计权衡：对于每个多项式$p(n)$，存在一个$n$变量类$C$，其 VC 维为$1$，使得在时间高效学习$C$的样本复杂度为$\Theta(p(n))$。 $\circ$以学习的角度对$\mathsf{RP}$与$\mathsf{NP}$的特征进行描述：$\mathsf{RP} = \mathsf{NP}$当且仅当每个$\mathsf{NP}$可枚举类在多项式时间内可通过$O(\mathrm{VCdim}(C))$样本进行学习。 正向蕴含自 (Pitt 和 Valiant, 1988) 以来已为人所知；我们证明了反向蕴含。 值得注意的是，我们的所有下界都针对不正确的学习者成立。 这些是首次针对不正确学习多项式大小电路的子类的$\mathsf{NP}$难度结果，绕过了 Applebaum、Barak 和 Xiao (2008) 提出的形式障碍。 显示英文摘要

摘要： A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-statistical tradeoffs have been shown under average-case assumptions, but since statistical problems are average-case in nature, it has been a challenge to base them on standard worst-case assumptions. In PAC learning where such tradeoffs were first studied, the question is whether computational efficiency can come at the cost of using more samples than information-theoretically necessary. We base such tradeoffs on $\mathsf{NP}$-hardness and obtain: $\circ$ Sharp computational-statistical tradeoffs assuming $\mathsf{NP}$ requires exponential time: For every polynomial $p(n)$, there is an $n$-variate class $C$ with VC dimension $1$ such that the sample complexity of time-efficiently learning $C$ is $\Theta(p(n))$. $\circ$ A characterization of $\mathsf{RP}$ vs. $\mathsf{NP}$ in terms of learning: $\mathsf{RP} = \mathsf{NP}$ iff every $\mathsf{NP}$-enumerable class is learnable with $O(\mathrm{VCdim}(C))$ samples in polynomial time. The forward implication has been known since (Pitt and Valiant, 1988); we prove the reverse implication. Notably, all our lower bounds hold against improper learners. These are the first $\mathsf{NP}$-hardness results for improperly learning a subclass of polynomial-size circuits, circumventing formal barriers of Applebaum, Barak, and Xiao (2008).