在数据可子采样的前提下，实现高隐私低误差的二阶矩估计。
A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
- 基于子采样性设计递归算法框架，满足零集中差分隐私。
- 在最坏输入下仍能保持二阶矩估计精度，误差可控在(1±γ)内。
- 适用于含异常值的数据分布，适合隐私敏感场景使用。
我们研究了差分隐私下的二阶矩估计问题，提出一种新算法，在数据满足子采样性假设时，即使面对最坏情况输入，也能实现强隐私-效用权衡。称一个输入为$(m,α,β)$-子采样可处理，若随机抽取大小为$m$（或更大）的子样本，以至少$1-β$的概率保留原二阶矩矩阵的谱结构，相对误差在$1±α$范围内。基于此，我们构建了一个类似Kamath等（2019）的递归算法框架，满足零集中差分隐私（zCDP），且以高概率保证二阶矩估计精度在任意因子$(1±γ)$内。进一步证明，该算法可用于近似分布$τ$的二阶矩矩阵，即使输入中存在显著比例的异常值。
原文摘要 · Abstract (English)
We study the problem of differentially private second moment estimation and present a new algorithm that achieve strong privacy-utility trade-offs even for worst-case inputs under subsamplability assumptions on the data. We call an input $(m,α,β)$-subsamplable if a random subsample of size $m$ (or larger) preserves w.p $\geq 1-β$ the spectral structure of the original second moment matrix up to a multiplicative factor of $1\pm α$. Building upon subsamplability, we give a recursive algorithmic framework similar to Kamath et al 2019, that abides zero-Concentrated Differential Privacy (zCDP) while preserving w.h.p. the accuracy of the second moment estimation upto an arbitrary factor of $(1\pmγ)$. We then show how to apply our algorithm to approximate the second moment matrix of a distribution $\mathcal{D}$, even when a noticeable fraction of the input are outliers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。