提出新算法，实现自适应对抗下的私有在线学习最优误差
Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
- 设计新算法，解决自适应对手下隐私在线学习的误差瓶颈
- 在可实现与不可知设置下分别达到 $O_d(\log T)$ 和 $\tilde{O}_d(\sqrt{T})$ 误差
- 适用于小 Littlestone 维度的任意概念类，适合隐私敏感场景
我们重新研究了私有在线学习问题：学习者在 $T$ 个时间步中接收数据序列，并需在每一步输出一个假设，整个输出序列需满足差分隐私。先前工作表明，所有有限 Littlestone 维度 $d$ 的概念类在可实现设置下是私有在线可学习的，其算法对盲性对手的错误界为 $O_d(\log T)$。但对自适应对手仅能保证 $\tilde{O}_d(\sqrt{T})$ 的错误界。本文提出新算法，在自适应对手下仍能实现 $O_d(\log T)$ 错误界，填补该差距。进一步研究不可知设置（无数据分布假设），给出通用 Littlestone 类的子线性后悔界 $\tilde{O}_d(\sqrt{T})$，证明其同样可私有在线学习。
原文摘要 · Abstract (English)
We revisit the problem of private online learning, in which a learner receives a sequence of $T$ data points and has to respond at each time-step a hypothesis. It is required that the entire stream of output hypotheses should satisfy differential privacy. Prior work of Golowich and Livni [2021] established that every concept class $\mathcal{H}$ with finite Littlestone dimension $d$ is privately online learnable in the realizable setting. In particular, they proposed an algorithm that achieves an $O_{d}(\log T)$ mistake bound against an oblivious adversary. However, their approach yields a suboptimal $\tilde{O}_{d}(\sqrt{T})$ bound against an adaptive adversary. In this work, we present a new algorithm with a mistake bound of $O_{d}(\log T)$ against an adaptive adversary, closing this gap. We further investigate the problem in the agnostic setting, which is more general than the realizable setting as it does not impose any assumptions on the data. We give an algorithm that obtains a sublinear regret of $\tilde{O}_d(\sqrt{T})$ for generic Littlestone classes, demonstrating that they are also privately online learnable in the agnostic setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。