Nov, 2016

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

PDF
TL;DR本文提出了一种统计查询下限技术，用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题，并得出了样本复杂度和计算复杂度之间存在的超多项式差距，同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。
statistical query lower boundsgaussian mixture modelsrobust learningmoment-matching techniquehigh-dimensional testing
发现论文，激发创造
  • 学习有界协方差高斯混合模型的 SQ 下界

    本论文研究了学习具有相同未知有界协方差矩阵的分离高斯混合模型的复杂性，证明了该问题的任何统计查询算法至少需要 d 的阶次 1/ε 的复杂度，这为已知算法的最佳性提供了证据。

    Jun, 2023

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

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

    Mar, 2024

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

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

    Oct, 2023

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

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

    Jun, 2020

  • 非高斯分量分析基于更弱假设的 SQ 下界

    我们研究了统计查询模型下非高斯成分分析（NGCA）的复杂性，并证明了在满足匹配矩条件下的近乎最优统计查询下界，推广到隐含子空间的设置，并获得了近乎最优统计查询下界，适用于一系列具体估计任务。

    Mar, 2024

  • 混合模型、鲁棒性和平方和证明

    本文基于 Sum of Squares 方法，探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法，进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计，我们的方法多次突破优化算法的极限。

    Nov, 2017

  • 统计查询复杂度的一般特征描述

    本论文提出了一种新的概念 "统计维数" 来刻画使用 SQ 算法求解样本复杂分布下的一般问题的复杂度，并且首次精确地表征出查询容差的必要性，具有在学习理论和算法优化方面的广泛应用。

    Aug, 2016

  • 学习高斯半空间问题中随机分类噪声的近最优界

    研究使用高斯分布下随机分类噪声学习半空间的问题，证明算法和统计查询下限，在此基本问题中，存在令人惊讶的信息计算差距，给出了正面的结果和近乎匹配的复杂度，并展示了算法的复杂度下界

    Jul, 2023

  • 高斯边缘下分别学习半空间和 ReLU 的近最优 SQ 下界

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

    Jun, 2020

  • 统计查询算法与低阶检验几乎等效

    本文研究在高维假设检验中的受限计算模型，特别是统计查询框架和低次多项式，在测试问题上的表现。主要结果表明，在测试问题的温和条件下，这两类算法在能力上基本等效，并提供了有限制的统计查询下界和植入团问题的几个变种。

    Sep, 2020