知识卡片：Littlestone 类的隐私在线学习与预测

一句话结论

在 oblivious realisable 对手设定下，对每个有限 Littlestone 维 (d) 的类，差分隐私在线学习与差分隐私在线预测的误差代价存在随时域 (T) 增大的分离：前者每步需发布假设，期望错误下界为 (\Omega((d/\varepsilon)(\log T)^{2/3}))；后者只需预测，存在与 (T) 无关的期望错误上界。

事件概述或研究问题

本文研究差分隐私在线学习与在线预测的 mistake bounds。两者区别在于：在线学习要求学习器在每个时间步发布假设；在线预测只要求做出预测，不发布假设。作者要回答：在 oblivious realisable 对手下，这两类问题的样本复杂度是否不同，尤其对有限 Littlestone 维 (d) 的类。

方法/产品要点

• 使用一个新的隐私在线学习下界与一个隐私在线预测上界来建立分离。
• 下界：每个 ((\varepsilon,\delta))-private online learner 都存在一条长度为 (T) 的确定性 realisable 流，使其期望错误满足 (\mathbb{E}[M_T]=\Omega((d/\varepsilon)(\log T)^{2/3}))。
• 该下界是首次覆盖材料所述 (1/T<\delta<1/\log T)) 范围的非平凡下界；该范围在早期工作 [SR22, DSS24, LWY24] 中留开。
• 上界：对每个 Littlestone 维 (d) 的类，存在一个 ((\varepsilon,\delta))-jointly private predictor，其期望错误至多 (2^{2^{c d^2}}\varepsilon^{-2}\log^2(2/(\varepsilon\delta)))，与 (T) 无关，其中 (c>0) 为绝对常数。

主要结果或产业意义

• 对固定有限 Littlestone 维类，当 (\delta=\Theta(1/\log T)) 时，隐私在线学习需要 (\Omega((\log T)^{2/3})) 期望错误；而隐私在线预测可做到 (O((\log\log T)^2))。
• 因此，材料结论是两类问题的样本复杂度/错误界分离，且分离因子随时域 (T) 增长。
• 产业应用、系统实现或实验评估：材料未提供，待核实。

为什么重要

• 理论上，它补足了隐私在线学习在特定 (\delta) 区间的非平凡下界空白，并给出隐私预测的强上界。
• 它区分了“发布假设”的隐私学习与“只做预测”的隐私预测：前者可能需要随 (T) 增长的错误代价，后者则可能不随 (T) 增长。
• 与已有相关卡片的关系：现有卡片（SOAP/Muon、昼夜节律抑郁筛查、4DR360）与本条主题无直接重叠；本条为独立新增，未延续其事实链。

局限与不确定性

• 本卡片仅依据 arXiv 摘要与元数据生成，未获取全文，证明细节、技术假设和完整参数依赖待核实。
• 实验、代码、数据集、应用场景：材料未提供，待核实。
• 作者信息仅见 Amartya Sanyal；同行评审状态、发表会议/期刊、后续版本更新待核实。
• 摘要中区间写法为 (1/T<\delta<1/\log T))，原文括号是否笔误待核实。
• 上界中的双指数因子 (2^{2^{c d^2}}) 对 (d) 的实际影响需要阅读全文确认，待核实。

可用于图书/PPT/简报的角度

• 隐私约束下，“持续发布模型/假设”与“只发布预测”的成本差异。
• 差分隐私、在线学习、在线预测与 Littlestone 维度之间的复杂度理论。
• 从留开区间到非平凡下界：理论下界如何推进问题边界。
• 用 ((\log T)^{2/3}) 对 (O((\log\log T)^2)) 的对比解释隐私在线学习与预测的分离。

原始材料

• 英文标题：Private online learning and prediction for Littlestone classes
• 英文关键词（依据摘要术语整理）：differentially private online learning; online prediction; Littlestone classes; mistake bounds; oblivious realisable adversaries
• arXiv ID：2610.06822v1
• 作者：Amartya Sanyal
• 发布/更新：2026-10-05T17:56:47Z（材料所标）
• 主分类：cs.LG
• 分类：cs.LG, cs.CR, stat.ML
• Abstract URL：https://arxiv.org/abs/2610.06822v1
• PDF URL：https://arxiv.org/pdf/2610.06822v1