Private Online Prediction from Experts with Small Losses¶

会议: NeurIPS 2026
arXiv: 2610.29575
OpenReview: https://openreview.net/forum?id=oAwj0VxrNb
领域: 其他
关键词: 差分隐私、专家在线预测、低损失遗憾界、收缩飞镖盘算法、AboveThreshold

一句话总结¶

本文提出了首个在遗忘对手下达成 \(\tilde{O}(\sqrt{L^\star})\) 数据依赖型低损失遗憾界的差分隐私专家在线预测算法，在常数隐私预算下几乎匹配非隐私下界，并从理论上证明了在自适应对手下即使 \(L^\star=0\) 也必然承受 \(\tilde{\Omega}(\sqrt{T})\) 遗憾界。

研究背景与动机¶

专家在线预测（Online Prediction from Experts, OPE）是机器学习与在线学习中的经典基础问题。在 \(T\) 轮博弈中，学习者在接收到第 \(t\) 轮损失函数之前，必须先从 \(N\) 个专家中选择一个并承受相应损失，其目标是在回顾视角下使累积损失尽可能贴近最优专家损失 \(L^\star\)，即最小化遗憾值（Regret）。然而，当在线决策涉及金融高频交易记录、医疗健康诊断或个性化敏感推荐等数据流时，算法的动作序列极易逆向泄露各轮损失背后的敏感个体隐私。为此，差分隐私（Differential Privacy, DP）成为量化和保障在线学习隐私的标准数学框架。在传统最坏情况下，已有隐私算法已能达到近乎最优的 \(\tilde{O}(\sqrt{T})\) 遗憾界，几乎完全匹配非隐私环境的下界 \(\Omega(\sqrt{T \log N} + \log N)\)，显示出隐私开销在最坏情况下是可忽略的。

然而，在实际应用（如精准天气预报或特定领域金融预测）中，专家团队往往具备极高先验水准，最优专家的实际累积损失 \(L^\star\) 通常远小于时间总步长 \(T\)（例如 \(L^\star = T^{1/4}\)）。在非隐私设定下，经典乘法权重更新法（Multiplicative Weights, MW）只需将学习率从 \(\sqrt{\ln N / T}\) 激进增大至 \(\sqrt{\ln N / L^\star}\)，便可自适应获得 \(O(\sqrt{L^\star \log N} + \log N)\) 的低损失界；而对于原有的 \(\tilde{O}(\sqrt{T})\) 算法，当 \(L^\star = T^{1/4}\) 时产生的损失可能是最优专家损失的 \(T^{1/4}\) 倍，完全失去了指导意义。在差分隐私约束下，学习率直接控制着采样概率对单条输入数据的敏感度（每个 MW 步骤等价于隐私参数为 \(2\eta\) 的指数机制）：过大的学习率会直接破坏隐私保障。为此，以往所有私有算法都对学习率强加了 \(O(T^{-1/2})\) 或 \(O(T^{-1/3})\) 的全局上限，根本无法自适应到微小损失 \(L^\star\)，使得在差分隐私下能否实现 \(\tilde{O}(\sqrt{L^\star})\) 遗憾界成为长期悬而未决的公开难题。

为了打破学习率与隐私预算之间的天然死锁，必须大幅削减学习者的重新采样更新次数，从而在有限的总隐私预算下释放出更大的单步学习率。核心 idea：将收缩飞镖盘的更新时机延迟至当前选中专家累积足够多的损失，利用 AboveThreshold 私有机制检测损失阈值，并在仅依赖延迟累积损失的数据自适应概率下触发更新，从而在遗忘对手下首次将差分隐私遗憾界收缩至与非隐私界相近的 \(\tilde{O}(\sqrt{L^\star})\)。

方法详解¶

整体框架¶

算法面向 \(T\) 轮序列在线决策。在每一轮 \(t\)，遗忘对手（Oblivious Adversary）预先固定了损失函数序列 \(\ell_1, \dots, \ell_T\)，算法必须在观测到 \(\ell_t\) 之前输出专家 \(i_t \in [N]\)。系统以改进的收缩飞镖盘（Shrinking Dartboard）算法为骨干：如果每一轮都重新按指数权重抽样，隐私预算将被迅速耗尽；但由于两轮之间边缘分布变化微弱，算法可以长期维持原有专家的选择，仅在特定触发条件下以可控概率执行更新。

为实现对 \(L^\star\) 的依赖，算法将更新决策显式与当前专家的累积损失挂钩。具体而言，系统维护一个 AboveThreshold 机制实例，实时累加当前专家自上次更新判定以来所承受的损失 \(q_t\)。当累积损失突破设定阈值 \(\tau\) 时，AboveThreshold 输出 \(\top\)；随后算法计算一个截断累积损失 \(r_u\)，并以 \(1 - e^{-\eta r_u}\) 的概率触发全局专家重采样（重采样遵循标准指数机制分布），否则继续沿用原专家；若累计重采样次数达到理论上限 \(V\) 则强制冻结。在 \(L^\star\) 未知的情形下，系统进一步通过外层加倍技术（Doubling Trick）构造分段探测机制，实现无先验知识下的自适应运行。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：轮次 t，损失序列与当前专家 i_{t-1}"] --> B["AboveThreshold 监测当前专家区间累积损失"]
    B -->|未超阈值| C["保持原有专家决策 i_t = i_{t-1}"]
    B -->|超阈值 ⊤| D["计算截断区间损失并以自适应概率决定重采样"]
    D -->|伯努利判定维持| C
    D -->|判定重采样且 v < V| E["指数机制全量重采样新专家 i_t 并累加计数 v"]
    D -->|更新次数耗尽 v ≥ V| C
    C --> F["输出 i_t，观测 \ell_t 并承受损失"]
    E --> F
    F --> G["加倍技术（Doubling Trick）自适应更新 L* 估计区间"]

关键设计¶

1. AboveThreshold 驱动的自适应延迟触发机制：用隐私检测解耦时间步长

在原有的隐私收缩飞镖盘算法（如 Asi 等人 2023, 2024 的工作）中，为了满足差分隐私，算法不得不强行在每一轮以独立于数据的固定概率（至少 \(\tilde{\Omega}(T^{-1/3})\)）进行额外更新。这种强制探测机制直接将总更新次数与时间范围 \(T\) 牢牢绑定，迫使单步学习率 \(\eta\) 必须受限于 \(\tilde{O}(T^{-1/3})\)，从而导致其遗憾界不可避免地包含 \(\tilde{O}(T^{1/3})\)，在 \(L^\star < T^{2/3}\) 时完全失效。

本文的设计彻底摒弃了每轮固定概率探测的做法，转而将更新判定完全推迟到当前专家出现实质性损失之后。具体而言，算法维持一个参数为 \(\varepsilon_1\)、阈值为 \(\tau\) 的 \(\mathsf{AboveThreshold}\) 机制实例，连续追踪当前区间内选中专家的累积损失查询：

\[ q_t \equiv \sum_{s=t_{u-1}}^{t-1} \ell_s(i_{t-1}) \]

由于单个损失函数在相邻输入序列中仅在至多一个时间步不同，任何单一区间内的查询序列全局敏感度严格不超过 1。利用 \(\mathsf{AboveThreshold}\) 的稀疏向量技术特性，在输出首个 \(\top\) 信号终止前，整个查询序列仅消耗单份隐私预算 \(\varepsilon_1\)。这确保了在专家表现良好（损失微弱）的漫长区间内，算法零隐私代价地保持决策，从而将有效触发轮次从 \(T\) 彻底压缩为与专家实际损失直接关联的稀疏离散事件。

2. 截断累积损失与隐私重采样门控：在数据自适应概率下保持隐私有界

当 \(\mathsf{AboveThreshold}\) 发出 \(\top\) 信号后，算法必须决定是继续保留当前专家还是全量重新采样。如果直接以精确的累积损失构建转移概率，由于损失取值敏感，概率之比可能在相邻数据集上发生剧烈波动。为兼顾隐私性与分布无偏性，算法设计了下界截断的区间有效损失指标：

\[ r_u \leftarrow \max\left(\frac{1}{e^{\varepsilon_2}-1}, \sum_{s=t_{u-1}}^{t-1} \ell_s(i_{t-1})\right) \]

随后从伯努利分布 \(Z_u \sim \mathsf{Ber}(e^{-\eta r_u})\) 中抽样：若 \(Z_u = 1\) 则令 \(i_t \leftarrow i_{t-1}\) 继续沿用；若 \(Z_u = 0\) 且未达更新上限 \(V\)，则从指数加权概率分布中重新采样专家并使计数器 \(v \leftarrow v+1\)。论文严密证明了在相邻序列下，由于 \(r_u\) 下界被严格限制在 \(1/(e^{\varepsilon_2}-1)\) 之上且两序列间的绝对差值至多为 1，满足不等式：

\[ \frac{1 - e^{-\eta r_j}}{1 - e^{-\eta r'_j}} \le \frac{\min(r_j, r'_j) + |r_j - r'_j|}{\min(r_j, r'_j)} \le e^{\varepsilon_2} \]

从而使得这一连串伯努利随机变量 \(Z_u\) 在并发组合视角下的总隐私泄漏被严密控制在 \(\max(\eta, \varepsilon_2)\) 之内。同时，论文通过构造精巧的势函数 \(\Phi_t = \sum_{i=1}^N e^{-\eta \sum_{s=1}^{t-1} \ell_s(i)}\)，证明了在全过程结束时，实际发生的全量重采样总次数 \(v_T\) 依高概率（至少 \(1-\beta_2\)）被控制在 \(71(\ln N + \eta L^\star + 1) + 280\ln(1/\beta_2)\) 之内，从理论上杜绝了因频繁重采样导致的隐私预算超支。

3. 加倍技术（Doubling Trick）消除先验：自适应未知的最优专家累积损失

在实际任务启动前，最优专家的最终损失 \(L^\star\) 是未知且不可预测的。如果无法预知 \(L^\star\)，算法便无法在初始时刻直接设定最优学习率 \(\eta = \tilde{\Theta}(1/\sqrt{L^\star})\) 和重采样次数上限 \(V = \tilde{\Theta}(\sqrt{L^\star})\)。

为此，算法在外层构建了基于加倍迭代的包装架构。系统将全流程划分为若干阶段 \(k=1, 2, \dots, K\)。在阶段 \(k\) 中，设置当前累积损失估计值 \(L' = 3 \cdot 2^k \alpha\)（其中 \(\alpha = \frac{16(\ln T + 2\ln(2T))}{\varepsilon}\)），并独立启动该阶段的底层预测算法实例 \(\mathsf{Alg}\)。同时，外层并行动用一个独立的 \(\mathsf{AboveThreshold}\) 实例，实时监控最优专家在该阶段内的累积损失 \(q_t \equiv \min_{i\in[N]} \sum_{s=b_k}^t \ell_s(i)\) 是否突破阈值 \((3 \cdot 2^k - 2)\alpha\)。一旦超出阈值，立即终止当前实例并将 \(k \leftarrow k+1\) 进入下一阶段。基于并行组合（Parallel Composition）与基础组合定理，由于各阶段损失子序列互不相交，算法在完全不需要任何 \(L^\star\) 先验的前提下，严格保持了 \((\varepsilon, \delta)\)-差分隐私，且总阶段数至多为 \(O(\log(1 + L^\star))\)，几何级数求和后的总遗憾值依然严密保持在 \(\tilde{O}(\sqrt{L^\star})\)。

损失函数 / 训练策略¶

本方法为纯在线博弈算法，不涉及离线参数反向传播。在各阶段 \(k\) 内部，算法的运行参数配置策略如下：

隐私预算分配：将总预算平均分配至检测模块与更新机制，令 \(\varepsilon_1 = \varepsilon_2 = \varepsilon/3\)。
检测阈值设定：为确保 \(\mathsf{AboveThreshold}\) 在全 \(T\) 轮中的联合准确度，阈值设置为 \(\tau = \frac{8(\ln T + 2\ln(2T))}{\varepsilon_1} + \frac{1}{e^{\varepsilon_2}-1}\)。
学习率自适应选取：
- 在纯差分隐私（Pure DP, \(\delta=0\)）下，设 \(\eta = \min\left(\frac{\varepsilon}{1278\ln N + 1296}, \frac{\varepsilon}{5040\ln T}, \sqrt{\frac{\varepsilon}{1278 L'}}, \sqrt{\frac{\varepsilon\ln N}{L' \ln T}}\right)\)。
- 在近似差分隐私（Approximate DP, \(\delta>0\)）下，利用高级组合定理（Advanced Composition）将学习率进一步放大至 \(\eta_3 = \max\left(\sqrt{\frac{\varepsilon}{1278 L'}}, \frac{\varepsilon^{2/3}}{(184032 L' \ln(3/\delta))^{1/3}}\right)\)，从而换取更紧致的遗憾界。
重采样上限防护：设置 \(V = \lceil 71(\ln N + \eta L' + 1) + 280\ln T \rceil\)，保证在最坏分布偏移下算法的硬性隐私保障依然绝对成立。

实验关键数据¶

该论文为纯理论创新工作，未提供经验合成或真实数据集的数值仿真代码与实验图表。依据理论计算与极值分析，论文在主定理与下界定理中确立了完备的理论界限。

主实验（理论遗憾界与不同隐私保证对比）¶

下表展示了本文在遗忘对手模型下取得的理论预期遗憾界，并与既往差分隐私专家在线预测代表性算法进行了严格对比：

方法	隐私保证类型	理论期望遗憾界（对 \(T, L^\star, N, \varepsilon\) 的依赖）	低损失区间适用性 (\(L^\star \ll T\))
Asi et al. (COLT 2023) [3]	Pure \(\varepsilon\)-DP	\(\tilde{O}\left(\frac{\sqrt{T}\log N}{\varepsilon}\right)\)	劣（即使 \(L^\star=0\) 仍需 \(\Omega(\sqrt{T})\) 遗憾）
Asi et al. (NeurIPS 2024) [4]	Approx. \((\varepsilon, \delta)\)-DP	\(O(\sqrt{T\log N}) + \tilde{O}\left(\frac{T^{1/3}\log N}{\varepsilon^{2/3}}\right)\)	劣（下限被 \(T^{1/3}\) 截断，无法自适应极小损失）
Asi et al. (ICML 2023) [2]	Pure / Approx. DP	\(\tilde{O}\left(1 + L^\star\right)\) （可实现向不可实现拓展）	次优（关于 \(L^\star\) 为线性依赖，非紧界）
本文 (Theorem 1.1)	Pure \(\varepsilon\)-DP	\(\tilde{O}\left(\sqrt{\frac{L^\star \log N}{\varepsilon}} + \frac{\log^2 N + \log N\log T}{\varepsilon}\right)\)	优（首个达 \(\tilde{O}(\sqrt{L^\star})\) 纯隐私界）
本文 (Theorem 1.2)	Approx. \((\varepsilon, \delta)\)-DP	\(O\left(\sqrt{\frac{L^\star\log N\log T}{\varepsilon}} + \log N \min\left(\frac{(L^\star\log(1/\delta))^{1/3}}{\varepsilon^{2/3}}, \sqrt{\frac{L^\star}{\varepsilon}}\right)\right) + \tilde{O}(\iota_2)\)	最优（逼近非隐私最优界 \(O(\sqrt{L^\star\log N})\)）
非隐私理论下界 (Cesa-Bianchi et al. [5])	无隐私限制	\(\Omega(\sqrt{L^\star \log N} + \log N)\)	理论基准极限

消融实验（对手模型与机制边界理论消融）¶

下表对不同对手对抗模型及关键机制设定的理论可行性与遗憾极限进行了消融对比：

机制 / 假设配置	对手类型	最优专家累积损失 \(L^\star\)	理论最小期望遗憾界	理论结论与性质说明
完整方案（AboveThreshold + 延迟收缩飞镖盘）	遗忘对手 (Oblivious)	任意 \(L^\star \ge 0\)	\(\tilde{O}\left(\sqrt{L^\star}\right)\)	隐私开销极小，近乎恢复无隐私最优率
移除遗忘假设（直接面对自适应对手）	自适应对手 (Adaptive)	\(L^\star = 0\) (完全可实现)	\(\tilde{\Omega}\left(\min\left(T, \frac{\sqrt{T}}{\varepsilon\log T}\right)\right)\)	理论断裂（Theorem 1.3）：自适应下不可能达到 \(o(\sqrt{T})\)
传统纯 DP 面对自适应对手 (Asi et al. [3])	自适应对手 (Adaptive)	\(L^\star = 0\)	\(\Omega(T)\)	纯隐私在自适应下出现灾难性线性遗憾
固定采样概率更新（无 AboveThreshold 延迟）	遗忘对手 (Oblivious)	任意 \(L^\star \ge 0\)	\(\tilde{\Omega}(T^{1/3})\)	独立采样率被迫下界约束，阻碍学习率放大

关键发现¶

遗忘对手与自适应对手的理论鸿沟：在遗忘对手下，差分隐私算法能够以极微小的对数多项式开销近乎无损地匹配非隐私低损失界 \(\tilde{O}(\sqrt{L^\star})\)；但在自适应对手下，定理 1.3 证明了即便利用户拥有完美的 \(L^\star=0\) 专家，任何满足近似 \((\varepsilon, \delta)\)-DP 的算法仍必然遭受 \(\tilde{\Omega}(\sqrt{T})\) 的遗憾，揭示了对抗性反馈与差分隐私在在线决策中不可调和的内在冲突。
高阶项与隐私参数的渐近权衡：在常数隐私预算下，本算法的界完全被主项 \(\sqrt{L^\star}\) 主导；然而若 \(L^\star\) 趋于常数极小值，次要项 \(\iota_1, \iota_2\)（与 \(\log^2 N\) 及 \(\log T\) 成正比）将作为可加性“启动代价”浮现，其数量级恰好与此前针对纯可实现情景（\(L^\star=0\)）的理论界相吻合。

亮点与洞察¶

用 AboveThreshold 重塑收缩飞镖盘的更新时机：传统方法通过无条件注入纯随机更新来掩盖数据依赖的更新偏置，代价是平摊了过多无意义的隐私损耗；本文将判断当前专家是否失效转化为单一低敏感度流式查询，用极小的隐私预算买到了长时间“静默期”，极大保留了隐私预算。
在线条件下的泊松采样隐私放大分析：为了证明自适应对手下的下界，论文通过在每轮以概率 \(q\) 进行伯努利丢弃（Poisson Subsampling），巧妙建立了在线场景下的隐私放大引理（Lemma C.4），成功将离线子采样技巧扩展至具有历史依赖的交互式在线博弈。
从理论向高频敏感流式预测迁移的潜力：该算法中的延迟检测与双重加倍调度架构具有很强的普适性，可以自然迁移至带差分隐私约束的在线广告投放、自适应路由以及传感器异常监控系统中。

局限与展望¶

遗忘对手的强假设局限：算法的 \(\tilde{O}(\sqrt{L^\star})\) 强保证严格依赖于损失序列预先固定、不受自身历史预测影响的假设。在博弈论或有竞争对手动态响应的市场环境中，对手往往具备自适应能力，此时下界表明该优势荡然无存。
在大损失区间的常数劣势：当最优专家损失非常大（如 \(L^\star = \Theta(T)\)）时，本算法给出的界相比 Asi 等人 (2023, 2024) 的界分别多了额外的 \(\sqrt{\varepsilon\log T/\log N}\) 或 \(O(\sqrt{\log T/\varepsilon})\) 对数乘性因子。
计算复杂度与高频决策时延：虽然每步更新判定仅需累加标量，但在加倍机制跨越时需要瞬时重置并遍历计算所有专家的指数权重分布，对于具有数百万级海量专家的超大规模系统，维护状态转移仍具一定工程开销。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破私有在线学习中低损失边界的理论瓶颈，核心技巧融合极其优雅。
实验充分度: ⭐⭐⭐☆☆ 纯理论推导工作，数学证明详实闭环，但无经验合成或真实环境仿真实验。
写作质量: ⭐⭐⭐⭐⭐ 论文动机清晰明确，从简单辅助算法到加倍机制层层递进，定理证明严谨明了。
价值: ⭐⭐⭐⭐☆ 解决了差分隐私在线学习领域的关键理论遗留问题，为敏感数据下的在线自适应决策奠定了坚实理论基石。