论文标题
通过功能梯度统计质量质量下限
Statistical-Query Lower Bounds via Functional Gradients
论文作者
论文摘要
我们给出了第一个统计质量质量下限，以不可知地学习有关高斯边缘的任何非物化激活（例如，relu，sigmoid，sign）。对于恢复回归的具体问题（等效地，不可依纳地学习relu），我们表明的任何具有公差的统计 - 查询算法$ n^{ - （1/ε）^b} $必须使用至少$ 2^{n^c}ε$查询，以便某种常数$ b，c> 0 $ n $ n $ nes $ iS $ dimension和dimemension $ disemension和disemension $ n $ dismension和disemension $ iS $两度$ε的差异。我们的结果排除了一般（与关联性）SQ学习算法的一般性，这对于真实评估的学习问题是不寻常的。我们的技术涉及通过Diakonikolas等人“放大”最近的下限的梯度增强程序。 （Colt 2020）和Goel等。 （ICML 2020）在两层神经网络计算的功能的SQ维度上。至关重要的新成分是在增强过程中使用非标准凸功能。这也可以在两个常用的学习模型之间最有可能减少：不可知论的学习和概率概念。
We give the first statistical-query lower bounds for agnostically learning any non-polynomial activation with respect to Gaussian marginals (e.g., ReLU, sigmoid, sign). For the specific problem of ReLU regression (equivalently, agnostically learning a ReLU), we show that any statistical-query algorithm with tolerance $n^{-(1/ε)^b}$ must use at least $2^{n^c} ε$ queries for some constant $b, c > 0$, where $n$ is the dimension and $ε$ is the accuracy parameter. Our results rule out general (as opposed to correlational) SQ learning algorithms, which is unusual for real-valued learning problems. Our techniques involve a gradient boosting procedure for "amplifying" recent lower bounds due to Diakonikolas et al. (COLT 2020) and Goel et al. (ICML 2020) on the SQ dimension of functions computed by two-layer neural networks. The crucial new ingredient is the use of a nonstandard convex functional during the boosting procedure. This also yields a best-possible reduction between two commonly studied models of learning: agnostic learning and probabilistic concepts.
