Privately Learning Markov Random Fields
Huanyu Zhang111Cornell University. Supported by NSF #1815893 and by NSF #1704443. This work was partially done while the author was an intern at Microsoft Research Redmond. Gautam Kamath222University of Waterloo. Supported by a University of Waterloo startup grant. Part of this work was done while supported as a Microsoft Research Fellow, as part of the Simons-Berkeley Research Fellowship program, and while visiting Microsoft Research Redmond. 555These authors are in alphabetical order. Janardhan Kulkarni333Microsoft Research Redmond. Zhiwei Steven Wu444University of Minnesota. Supported in part by the NSF FAI Award #1939606, a Google Faculty Research Award, a J.P. Morgan Faculty Award, a Facebook Research Award, and a Mozilla Research Grant.
Abstract
We consider the problem of learning Markov Random Fields (including the prototypical example, the Ising model) under the constraint of differential privacy. Our learning goals include both structure learning, where we try to estimate the underlying graph structure of the model, as well as the harder goal of parameter learning, in which we additionally estimate the parameter on each edge. We provide algorithms and lower bounds for both problems under a variety of privacy constraints – namely pure, concentrated, and approximate differential privacy. While non-privately, both learning goals enjoy roughly the same complexity, we show that this is not the case under differential privacy. In particular, only structure learning under approximate differential privacy maintains the non-private logarithmic dependence on the dimensionality of the data, while a change in either the learning goal or the privacy notion would necessitate a polynomial dependence. As a result, we show that the privacy constraint imposes a strong separation between these two learning problems in the high-dimensional data regime.
中文速览
马尔可夫随机场（Markov Random Fields，MRF）在医疗和基因数据分析中应用广泛，但在隐私保护约束下如何高效学习这类模型此前并不清楚。研究者系统研究了在差分隐私（differential privacy）约束下学习 MRF 的两个目标——结构学习（只恢复图的边）和参数学习（同时恢复边的权重）——并分别在纯、集中和近似三种差分隐私强度下给出了算法和下界。核心发现是：在无隐私约束时，两个学习目标所需样本量都只与维度 p 呈对数关系；但加入隐私约束后，只有"近似差分隐私 + 结构学习"这一组合能保持对数级样本复杂度，一旦换成参数学习或收紧隐私要求，样本复杂度就会跳升到多项式级别（约 √p），且这一界是紧的。这一结果揭示了隐私约束在高维场景下对不同学习任务施加了本质性的分离，对实际部署隐私保护的图模型学习系统具有重要指导意义。
原文 arXiv:2002.09463;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2002.09463v2