在本地差分隐私下，设计新算法提升专家预测的准确性和隐私保护。
Prediction with Expert Advice under Local Differential Privacy
- 利用隐私诱导的有限切换行为实现更强隐私放大，无性能损失。
- 提出可私密选择复杂学习算法的专家方法，且不增加隐私开销。
- 实验证明新算法比经典方法和中心化隐私算法快1.5至3倍。
我们研究在本地差分隐私（LDP）约束下的经典专家建议预测问题。首先证明经典算法天然满足LDP，随后设计两种新算法：RW-AdaBatch和RW-Meta。RW-AdaBatch利用LDP带来的有限切换特性，实现随数据难度增强的隐私放大，类似离线学习中的随机洗牌模型；基于随机游走理论，证明该改进几乎无效用代价。RW-Meta则提出一种通用方法，在隐私保护下从非平凡学习算法中选择专家，且在LDP下无额外隐私成本。此前工作仅考虑数据无关专家。我们还推导出后悔界，其与专家间独立性成反比。分析结合真实医院新冠数据评估：在预测每周报告最高患者密度医院的任务上，RW-Meta相比经典基线和最先进的中心化差分隐私算法提升1.5至3倍。
原文摘要 · Abstract (English)
We study the classic problem of prediction with expert advice under the constraint of local differential privacy (LDP). In this context, we first show that a classical algorithm naturally satisfies LDP and then design two new algorithms that improve it: RW-AdaBatch and RW-Meta. For RW-AdaBatch, we exploit the limited-switching behavior induced by LDP to provide a novel form of privacy amplification that grows stronger on easier data, analogous to the shuffle model in offline learning. Drawing on the theory of random walks, we prove that this improvement carries essentially no utility cost. For RW-Meta, we develop a general method for privately selecting between experts that are themselves non-trivial learning algorithms, and we show that in the context of LDP this carries no extra privacy cost. In contrast, prior work has only considered data-independent experts. We also derive formal regret bounds that scale inversely with the degree of independence between experts. Our analysis is supplemented by evaluation on real-world data reported by hospitals during the COVID-19 pandemic; RW-Meta outperforms both the classical baseline and a state-of-the-art \textit{central} DP algorithm by 1.5-3$\times$ on the task of predicting which hospital will report the highest density of COVID patients each week.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。