Nov, 2010

私密发布合取和统计查询障碍

PDF
TL;DR本研究提出了两个结果，第一个结果说明了在 Kearns' SQ 模型中，对一组统计查询 C 生成错误率较小的所有答案需要的统计查询次数是对偶学习复杂度；第二个结果能高效地解决问题，只要能够通过子模函数描述 C 的答案集。这两个结果对隐私保护数据分析产生了积极的应用，使其得到了重大进展。
statistical querieslearning complexitysubmodular functionprivacy-preserving data analysisdifferentially private algorithm
发现论文，激发创造
  • 统一 (量子) 统计和参数化 (量子) 算法

    从评估查询中学习的问题以及其对线性函数类的查询复杂性进行了研究，从而在量子学习和量子机器学习领域建立了统一的视角。

    Oct, 2023

  • 非交互式数据库隐私的学习理论方法

    论文证明，私人发布用于大量查询的合成数据库是可能的，但仅针对离散领域，并提供了一种新的数据隐私概念：分布隐私。

    Sep, 2011

  • 差分隐私矩阵机制下查询集的最优误差

    研究了通过矩阵机制方法，针对支持一组特定数量的问题而调整的合成数据集，在差分隐私下生成合成数据的方法及其对解析一组线性计数查询的困难度的影响，发现查询量的难度与行列式物理特性相关。

    Feb, 2012

  • 双重查询：针对高维数据的实用私有查询发布

    提出了一种实用的差分隐私算法，可以回答高维数据集上的大量查询，并将计算困难的步骤封装为一个简洁定义的整数规划问题，以实现高效的回答。通过在 Netflix 数据集上的实验，证明了该算法的精度和隐私性定理，并提出了比现有技术显著改进的方案。

    Feb, 2014

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

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

    Nov, 2016

  • SHIQ 描述逻辑的联合查询回答

    本文研究 DL 中具有传递性角色的联接查询的可决定性和复杂度问题，并证明了在 SHIQ 中允许传递性角色的联接查询有一个完美的单指数时间算法及共 NP 复杂性。

    Oct, 2011

  • 递归机制：向节点差分隐私和不受限连接迈进 [完整版本，草稿 0.1]

    本文提出了一种新的差分隐私机制，该机制支持对敏感数据库上通过一些关系代数计算的结果的线性统计量进行近似，并且支持不受限制的连接操作，其误差边界大致与查询的经验灵敏度成正比，对于任何一种子图，本文提供了能够实现节点差分隐私的第一种解决方案。

    Apr, 2013

  • 交互式数据分析中的虚假发现预防是困难的

    论文表明，在自适应环境下，维护统计查询的计算有效性和正确性是计算难度的源泉，这对现今大型协作研究环境中防止错误发现的挑战具有本质性质。

    Aug, 2014

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

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

    Aug, 2016

  • 通过自适应投影实现差分隐私查询发布

    提出了一种新的算法，用于发布对包括 k 路边际在内的非常大量的统计查询回答，该算法采用连续松弛的投影机制，使其在隐私数据集上回答查询并尝试找到最接近噪声回答的合成数据集，并通过不断适应地发现在其（松弛的）合成数据上具有高误差的查询，以达到节省隐私预算的目的，通过使用 ML 优化技术和工具，该方法在许多情况下优于现有算法。

    Mar, 2021