Privately detecting changes in unknown distributions
Rachel Cummings111School of Industrial and Systems Engineering, Georgia Institute of Technology. Email: {rachelc, yuliia.lut, R.C. supported in part by a Mozilla Research Grant, a Google Research Fellowship, and NSF grant CNS-1850187. Y.L. and W.Z. supported in part by a Mozilla Research Grant, NSF grant CNS-1850187, and two ARC-TRIAD Fellowships from the Georgia Institute of Technology. Much of this work was completed while R.C., Y.L., and W.Z. were visiting the Simons Institute for the Theory of Computing. Sara Krehbiel222Department of Mathematics and Computer Science, Santa Clara University. Email: Supported in part by a Mozilla Research Grant. Much of this work was completed while S.K. was a faculty member at University of Richmond and visiting the Stanford Graduate School of Business. Yuliia Lut Wanrong Zhang
Abstract
The change-point detection problem seeks to identify distributional changes in streams of data. Increasingly, tools for change-point detection are applied in settings where data may be highly sensitive and formal privacy guarantees are required, such as identifying disease outbreaks based on hospital records, or IoT devices detecting activity within a home. Differential privacy has emerged as a powerful technique for enabling data analysis while preventing information leakage about individuals. Much of the prior work on change-point detection—including the only private algorithms for this problem—requires complete knowledge of the pre-change and post-change distributions. However, this assumption is not realistic for many practical applications of interest. This work develops differentially private algorithms for solving the change-point problem when the data distributions are unknown. Additionally, the data may be sampled from distributions that change smoothly over time, rather than fixed pre-change and post-change distributions. We apply our algorithms to detect changes in the linear trends of such data streams. Finally, we also provide experimental results to empirically valida
中文速览
在海量数据流中自动找到"分布发生突变的那一刻"（变点检测，change-point detection）是统计学的经典难题，而当数据涉及病历、家庭行为等隐私信息时，算法还必须满足差分隐私（differential privacy）的严格保护要求。以往唯一的隐私变点检测方法都假设变化前后的数据分布完全已知，这在现实中往往不成立。本文针对分布未知的非参数场景，基于低敏感度的Mann-Whitney秩和统计量，分别为离线和在线两种场景设计了差分隐私算法，并将方法进一步推广到数据均值随时间线性漂移、在某未知时刻改变斜率的"漂移变点"问题。理论分析表明，离线算法的定位误差仅为$O(\epsilon^{-1.01})$、与数据规模无关，在线算法误差仅为$O(\log n)$，大幅优于此前最好的非参数变点估计结果；在股票价格真实数据和高斯模拟数据上的实验也验证了这些结论，说明即使隐私预算$\epsilon$很小，算法仍能准确定位变点，为需要隐私保护的实际数据流监测提供了坚实的理论与算法基础。
原文 arXiv:1910.01327;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1910.01327v2