本地差分隐私下如何进行变点检测？

在没有可信第三方时定位单个变点

论文研究离线参数化变点检测：一批 n 个独立观测最初来自已知分布 P0，在某个未知位置 k* 切换为另一个已知分布 P1，分析者需要估计这次切换发生在哪里。“离线”指整批数据一次性可用，“参数化”指两个分布都事先完全给定。真实变点被视为固定的未知量，不为其设定先验分布。

关键在于本地差分隐私（LDP）。每个数据持有者不再把原始值交给可信第三方，而是先用自己的 ε-LDP 机制对观测做随机化，再共享出去。分析者只能看到加噪后的输出，以及由此诱导出的分布 Q0 和 Q1，却仍要恢复变点位置。隐私参数 ε 控制这一权衡：ε 越小，隐私越强，输出噪声越大。

精度用 (α, β)-精度衡量：在所有可能的真实变点位置上取最坏情况，估计值与真实位置相差超过容差 α 的概率必须不超过 β。这与在线监测中的检测延迟是不同的问题，论文的保证应按此理解——固定的一批数据、一个变点，以及在选定容差下的错误概率。

Chernoff 信息决定定位精度上限

核心量是 Chernoff 信息 I_ch(P0, P1)，它衡量两个分布在误报与漏检之间取最优指数权衡时可被区分的程度。论文证明了有限样本极小极大下界：即使在非隐私情形下，任何估计器——无论是否随机化，包括允许判定“无变点”的估计器——都无法以优于由 I_ch 决定的指数来定位。

该下界通过把 Le Cam 两点方法推广到多个候选假设，再用指数倾斜细化指数得到。一个残余项刻画了在倾斜分布下对数似然比围绕其均值的波动。在隐私情形下，同类下界对每个 ε-LDP 机制都成立，只是 Chernoff 信息改为在诱导输出分布 Q0 与 Q1 之间计算。

这是论文的概念支点：隐私不只是加噪声，它压缩了两个阶段的可区分性，而这种压缩正是限制定位精度的原因。作者用无穷阶 Rényi 散度与 Jeffreys–Rényi 散度的强数据处理不等式（SDPI）系数来刻画这种压缩，并证明这些系数可以通过只考虑共同支撑至多含两个符号的输入分布对来计算。

无隐私时似然比估计器接近最优

论文分析的估计器会扫描每个候选位置 k，计算从 k 起往后所有观测的对数似然比，然后报告使该比值最大的位置。这是经典 CUSUM 方法的离线版本。作者用鞅方法为这个广义似然比检验（GLRT）推导出以 I_ch 表示的有限样本精度界，并表明它显著优于此前对同一估计器的保证。

比较上下界可知，GLRT 在主导定位误差指数上渐近最优，差距至多为两倍。这个两倍是论文明确给出的具体差距，并非声称精确最优。作者还给出了用最小 Kullback–Leibler 散度和对数似然比敏感度表示的另一种保证，使与先前工作的比较更直接，也把分析与隐私压缩结果联系起来。

两种机制分别覆盖低隐私与高隐私

以诱导出的 Chernoff 信息为指导，论文设计了两种 LDP 机制。聚合随机化回答（ARR）按似然比相等把观测分组，并在组内应用随机化回答；由此得到的 ARR-CPD 算法在 ε 足够大（即低隐私）时，在所有 ε-LDP 机制中使诱导 Chernoff 信息最大。二元机制（BM）把每个观测映射为两个符号之一，在 ε 足够小（即高隐私）时同样使该信息最大。

有限样本保证重现了这一排序：高隐私时 BM-CPD 的界更小，低隐私时 ARR-CPD 的界更小。论文对这一点很谨慎：该比较针对的是上界，而给这些上界排序的充分区间未必与各机制达到 Chernoff 最优的区间重合。作者明确指出，这些比较本身并不能确定实际定位误差的排序。

隐私代价约为 tanh⁻²(ε/2) 量级

把上下界结合起来，可以得到关于隐私指数代价的双边结论。该代价定义为非隐私与隐私情形下极小极大定位误差指数之比，其取值被限制在 max(1, 1/(2c²)) 与 4 I_ch(P0,P1) / (c² d²_TV(P0,P1)) 之间，其中 c = tanh(ε/2)，d_TV 是 P0 与 P1 之间的全变差距离。

因此，对固定分布而言，该代价在所有 ε > 0 上为 Θ(tanh⁻²(ε/2))，当 ε → 0 时为 Θ(ε⁻²)。通俗地说，把隐私从中等强度收紧到接近零，会使可达到的误差指数按 ε 的平方退化。该界还表明代价取决于两个分布相距多远：全变差距离较小的分布要付出更大的乘性代价。

合成实验印证理论界与机制切换

实证评估使用合成数据，n = 2000 个观测，真实变点位于第 1000 个位置，主要设定采用截断泊松分布，附录中还有 Bernoulli、二项、截断几何和高斯等情形。每个错误概率由 10,000 次蒙特卡洛重复估计，标准误至多 0.005，相对于图中呈现的趋势很小。

图中把经验错误概率与理论上下界随容差 α 的变化作比较，并在固定 α = 5 时与隐私参数 ε 作比较。经验曲线跟随理论界，机制切换也如预测出现：低隐私时 ARR-CPD 表现更好，高隐私时 BM-CPD 表现更好。另有一张图描绘隐私指数代价随 ε 的变化，阴影区域标出双边界允许的范围。

这些都是在合成分布上的模拟，而非在真实数据流上的部署。它们印证了理论并展示了机制分区，但没有检验算法面对模型设定错误、未知分布参数或多个变点时的表现——这些都在论文设定的范围之外。

保证的适用范围与边界

结果适用于独立观测序列中恰好一个变点的离线定位，且变化前后分布均已知并完全给定。下界对所有可能随观测而变的 ε-LDP 机制以及所有估计器一致成立，这正是隐私代价结论有力的原因。分析还假设数据在候选集合中恰好含有一个真实变点。

实际解读是选择适用区间，而不是推荐单一算法。如果隐私预算宽松，ARR-CPD 是在该区间内诱导 Chernoff 信息最大的机制；如果预算紧张，则由 BM-CPD 接手。阈值并非通用常数——论文的排序条件取决于分组数 r 和 ε，而给上界排序的充分区间未必与 Chernoff 最优区间一致。对固定的一对分布而言，最具决策意义的数字仍是 tanh⁻²(ε/2) 这一缩放关系：它告诉你在做出任何算法选择之前，随着 ε 缩小会牺牲多少定位精度。

本文引用的文献