Littlestone 类的差分隐私在线学习与预测

基于摘要分析。本文研究在 oblivious realisable adversaries（预先固定且可实现的对手）条件下，差分隐私在线学习与在线预测的错误次数界。核心贡献是分别构造在线学习的下界与在线预测的上界，说明对有限 Littlestone dimension 的假设类，逐步公开假设与仅输出预测可能具有随时间长度扩大的复杂度差异。 机制与理论结果：在线学习要求每个时间步发布一个假设，在线预测则只需输出预测。作者报告，对任意 (ε,δ)-private 在线学习器，都存在长度为 T 的确定性可实现数据流，使其期望错误次数满足摘要所称的下界，原文写作 E[M_T] = O((d/ε) log^{2/3} T)，其中 d 为 Littlestone dimension。这里“至少”的下界叙述与 O 记号并不协调，需核对正文，不能直接替作者改成 Ω。作者称该结果覆盖此前未解决的 1/T < δ < 1/log T 范围。 作者另报告，对每个维度为 d 的假设类，存在 (ε,δ)-jointly private 预测器，其期望错误次数至多为 2^{2^{cd²}} ε^{-2} log²(2/(εδ))，c 为绝对正常数；固定隐私参数时，该界不依赖 T。不过，对 d 的双指数依赖可能限制界的实际适用性。摘要进一步在固定假设类、δ = Θ(1/log T) 时比较两类任务；此时隐私参数本身随 T 变化，不能把固定参数下的时间无关性直接理解为该设定下错误次数恒定。 需核对事项：摘要将贡献描述为样本复杂度分离，但给出的具体公式是期望错误次数界；其形式化联系、private 与 jointly private 的定义及比较条件、证明构造和算法计算开销尚未验证。材料未提供 EEG/BCI 实验，也未建立可直接复用的信号解码机制；现实 EEG 中的噪声与分布变化是否满足可实现性条件仍待评估，相关 EEG 工作尚未检索确认。