#sample-complexity

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar, Kevin Tian

本文研究高维差分隐私(DP)下的协方差矩阵估计和主成分分析(PCA)问题,重点关注协方差矩阵的k-行-列稀疏性(k-RCS)假设。在非私有设置中,已知仅需poly(k, log d)个样本即可解决这两个问题。然而,在DP设置下,现有的最好结果(Wang等人,2021)在标准参数化下需要Ω(d)个样本,这产生了维度灾难。本文探究了DP下稀疏协方差估计中这种维度灾难的内在性。在上界方面,作者证明:若额外假设前导特征向量是稀疏的,则PCA可以在poly(k, log d)个样本下实现DP。在下界方面,作者为DP下的稀疏协方差估计和PCA分别建立了poly(d)的下界,从而揭示了当k = polylog(d)时,这两个问题的私有与非私有版本之间存在指数级差距——这是首个在私有高维统计中展示此类分离的结果。此外,该技术足够灵活,能够推导出标准DP PCA(无稀疏假设)的更强下界。本文的理论贡献为理解DP在稀疏高维问题中的样本复杂度提供了重要见解。

💡 推荐理由: 本文首次揭示了差分隐私下稀疏协方差估计和PCA中存在指数级样本复杂度差距,对设计高效DP高维算法具有重要指导意义。

🎯 建议动作: 研究跟进

排序因子: 影响边界/网络设备 (+5) | 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)