Jun, 2020

通过函数梯度计算统计查询下限

PDF
TL;DR该研究首次为关于高斯边缘任意非多项式激活函数的伪装学习问题，给出了统计查询下限。通过梯度提升过程对之前的低界进行放大，对具体问题 ReLU 回归（等同于伪装学习 ReLU），我们证明任何统计查询算法都必须使用至少 2^(n^c) ε 个查询，从而阐述了与真实价值的学习问题不同的情况，我们的结果排除了一般（相对于关联）SQ 学习算法，这在实值学习问题中是不寻常的。同时我们将两种常见的学习模型，即伪装学习和概率概念之间得到了最好的规约。
agnostic learningnon-polynomial activationrelu regressionstatistical-query algorithmsq dimension
发现论文，激发创造
  • 高斯边缘下分别学习半空间和 ReLU 的近最优 SQ 下界

    该论文研究了在高斯边际下以不可知方式学习半空间和 ReLU 的基本问题，证明了这些问题的统计查询下限。

    Jun, 2020

  • 高维高斯分布和高斯混合模型的鲁棒估计的统计查询下限

    本文提出了一种统计查询下限技术，用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题，并得出了样本复杂度和计算复杂度之间存在的超多项式差距，同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。

    Nov, 2016

  • 使用梯度下降法学习单层神经网络的超多项式下界

    利用梯度下降证明了学习单层神经网络的第一个超多项式下限，它包括使用小批量的梯度下降，需要锐利的激活函数和适用于特定查询的以前结果。与以前的结果不同，我们的结果适用于包括 ReLU 和 sigmoid 在内的广泛激活类别，并且围绕一种新型神经网络的结构构建。

    Jun, 2020

  • 学习截断高斯分布的统计查询下界

    在截断设置下，通过统计查询 (SQ) 下界和超多项式的信息计算差，我们研究了估计截断恒等协方差高斯分布的均值问题。

    Mar, 2024

  • 一层隐藏层神经网络的梯度下降：多项式收敛和 SQ 下界

    研究神经网络在激活层和输出加权和层下的训练复杂性，并在高斯分布条件下证明 GD 收敛于最好逼近目标函数的多项式的最小误差，并发现 GD 在发现低频傅立叶分量之前要先发现高频分量。

    May, 2018

  • 学习线性分类器混合模型的 SQ 下界

    学习高斯协变量下的线性分类器混合问题，主要结果是一个统计查询（SQ）下界暗示已知算法对于该问题基本上是最佳的，甚至对于均匀混合的特殊情况。

    Oct, 2023

  • 一层 ReLU 网络的 PAC 学习算法和 SQ 下界

    本论文研究了具有 $k$ 个隐藏单元的一层 ReLU 网络在高斯边缘下学习的问题，并提出了适用于正系数情况的首个多项式时间算法，解决了此前在 $k≤3$ 情况下无多项式时间算法的开放性问题。然而，对于具有任意实系数的一层 ReLU 网络的 PAC 学习问题，则证明了一个统计查询下界，说明其难以在多项式时间内得到解决。

    Jun, 2020

  • 关于学习 ReLU 及高斯边缘的时间 / 准确性权衡

    本文探讨如何在高斯分布下计算最适合的 ReLU 模型，证明了学习受高斯边缘影响下的 ReLU 模型的难点，并提出了一种利用噪声半空间学习算法的近似最优解法。

    Nov, 2019

  • 基于 ReLU 的回归近似方案

    本文提出一种基于分布函数采样数据的 ReLU 回归算法并给出了第一个可行的常数近似算法，同时该算法适用于所有对数凸分布。通过更加复杂的技术，我们还能够获得任何次高斯分布的多项式时间逼近方案。

    May, 2020

  • 神经网络在信息论极限附近通过梯度下降学习低维多项式

    通过 SGD 优化的两层神经网络可学习任意多项式链接函数的单指数目标函数，并具有与信息理论界限相匹配的样本和运行时间复杂度。

    Jun, 2024