让机器学习预测更私密，查询越多越省数据
Private Prediction via Shrinkage
- 用收缩策略降低隐私预算消耗，实现高效私密预测
- 1000次查询只需约35个样本，比传统方法快得多
- 适合对隐私要求高且需持续响应的在线场景
我们研究由Dwork和Feldman（COLT 2018）提出的差分隐私预测：算法接收一个带标签的数据集 $S$，随后回答一系列无标签查询，输出结果对 $S$ 保持 $(,δ)$-差分隐私。标准组合机制下，$T$ 次查询的隐私开销为 $√{T}$。本文证明在流式设置下，该依赖可降至关于 $T$ 的多项对数级别。对于任意概念类 $$ 和盲目的在线对手，我们的私密预测器仅需 $|S| = ~{O}(VC()^{3.5}\log^{3.5}T)$ 个标注样本即可回答 $T$ 次查询；对于自适应在线对手及 $^d$ 上的半空间，所需样本量为 $|S| = ~{O}(d^{5.5}\log T)$。
原文摘要 · Abstract (English)
We study differentially private prediction introduced by Dwork and Feldman (COLT 2018): an algorithm receives one labeled sample set $S$ and then answers a stream of unlabeled queries while the output transcript remains $(\varepsilon,δ)$-differentially private with respect to $S$. Standard composition yields a $\sqrt{T}$ dependence for $T$ queries. We show that this dependence can be reduced to polylogarithmic in $T$ in streaming settings. For an oblivious online adversary and any concept class $\mathcal{C}$, we give a private predictor that answers $T$ queries with $|S|= \tilde{O}(VC(\mathcal{C})^{3.5}\log^{3.5}T)$ labeled examples. For an adaptive online adversary and halfspaces over $\mathbb{R}^d$, we obtain $|S|=\tilde{O}\left(d^{5.5}\log T\right)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。