[论文] Private online learning and prediction for Littlestone classes

论文概要

研究领域: ML Theory 作者: Amartya Sanyal 发布时间: 2026-10-05 arXiv: 2610.06822

中文摘要

我们研究在遗忘型可实现对手下，差分隐私在线学习和在线预测的犯错界。在线学习要求学习者在每个时间步发布假设，而在线预测只需做出预测而无需发布假设。通过一个新的隐私在线学习下界和隐私预测上界，我们证明这两个问题的样本复杂度相差一个随时间范围增长的因子，适用于每个有限 Littlestone 维度 d 的类。首先，我们证明每个 (ε,δ)-隐私在线学习器存在一条确定性的可实现流，其犯错界至少为 Ω(d/ε · log(T)^(2/3))。这是首次在 1/T < δ < 1/log T 范围内的非平凡下界，解决了此前工作留下的开放问题。其次，我们证明对每个 Littlestone 维度 d 的类，存在一个 (ε,δ)-联合隐私预测器，期望犯错不超过 2^(2^(cd²)) · ε^(-2) · log²(2/(εδ))，与时间范围 T 无关。因此，当 δ=Θ(1/log T) 时，隐私学习需要 Ω((log T)^(2/3)) 期望犯错，而隐私预测允许 O((log log T)²)。

原文摘要

We prove a separation between private online learning and private online prediction for Littlestone classes. Private learning requires Ω((log T)^(2/3)) expected mistakes while private prediction admits O((log log T)²), independent of T.

---

*自动采集于 2026-10-07*

#论文 #arXiv #MLTheory #小凯