Privately Learning Markov Random Fields

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.

References in corpus (13)

• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Consistent estimation of the basic neighborhood of Markov random fields
• On Learning Discrete Graphical Models Using Greedy Methods
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models
• Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
• Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
• Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications
• New Oracle-Efficient Algorithms for Private Synthetic Data Release
• A Primer on Private Statistics
• Structure learning of antiferromagnetic Ising models
• Concentration of Multilinear Functions of the Ising Model with Applications to Network Data
• Differentially Private Assouad, Fano, and Le Cam

Cited by in corpus (4)

• CoinPress: Practical Private Mean and Covariance Estimation
• A Primer on Private Statistics
• Robust and Differentially Private Mean Estimation
• Optimal Private Median Estimation under Minimal Distributional Assumptions