Privately Learning Markov Random Fields
This work addresses privacy-preserving machine learning for graphical models, providing algorithms and lower bounds that reveal fundamental trade-offs between privacy and learning complexity, which is incremental as it builds on existing differential privacy frameworks.
The paper tackles the problem of learning Markov Random Fields under differential privacy constraints, showing that structure learning with approximate differential privacy maintains logarithmic dependence on data dimensionality, while other settings require polynomial dependence, imposing a strong separation between structure and parameter learning in high-dimensional regimes.
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.