在联邦在线预测中，实现差分隐私下客户协作的显著性能提升。
Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups
- 设计新算法 Fed-SVT，支持隐私保护下的客户端协同决策。
- 在低损失专家场景下，实现比单客户端快 m 倍的错误率下降。
- 首次在联邦框架下研究差分隐私的在线专家预测问题，适合隐私计算研究者。
我们研究在差分隐私约束下，面对随机对手和固定对手的联邦在线专家预测问题。目标是在时间跨度 T 内，使 m 个并行客户端的平均遗憾最小化。针对随机对手，提出 Fed-DP-OPE-Stoch 算法，在纯差分隐私和近似差分隐私下均实现每客户端遗憾降低 √m 倍，同时保持对数级通信开销。对于一般固定对手，建立非平凡下界，表明协作无法带来遗憾加速。进一步考虑存在低损失专家的特殊情形，设计新算法 Fed-SVT，证明其在纯和近似差分隐私下均实现比单客户端快 m 倍的遗憾加速，且下界表明该算法近乎最优（仅差对数因子）。实验验证了算法有效性。据我们所知，这是首个研究联邦环境下差分隐私在线专家预测的工作。
原文摘要 · Abstract (English)
We study the problems of differentially private federated online prediction from experts against both stochastic adversaries and oblivious adversaries. We aim to minimize the average regret on $m$ clients working in parallel over time horizon $T$ with explicit differential privacy (DP) guarantees. With stochastic adversaries, we propose a Fed-DP-OPE-Stoch algorithm that achieves $\sqrt{m}$-fold speed-up of the per-client regret compared to the single-player counterparts under both pure DP and approximate DP constraints, while maintaining logarithmic communication costs. With oblivious adversaries, we establish non-trivial lower bounds indicating that collaboration among clients does not lead to regret speed-up with general oblivious adversaries. We then consider a special case of the oblivious adversaries setting, where there exists a low-loss expert. We design a new algorithm Fed-SVT and show that it achieves an $m$-fold regret speed-up under both pure DP and approximate DP constraints over the single-player counterparts. Our lower bound indicates that Fed-SVT is nearly optimal up to logarithmic factors. Experiments demonstrate the effectiveness of our proposed algorithms. To the best of our knowledge, this is the first work examining the differentially private online prediction from experts in the federated setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。