Relaxed Marginal Consistency for Differentially Private Query Answering
This work addresses a bottleneck in private data analysis for high-dimensional databases, offering a practical enhancement to existing methods.
The paper tackled the scalability issue of Private-PGM in differentially private query answering by relaxing consistency constraints, enabling improved scalability or accuracy without compromising privacy.
Many differentially private algorithms for answering database queries involve a step that reconstructs a discrete data distribution from noisy measurements. This provides consistent query answers and reduces error, but often requires space that grows exponentially with dimension. Private-PGM is a recent approach that uses graphical models to represent the data distribution, with complexity proportional to that of exact marginal inference in a graphical model with structure determined by the co-occurrence of variables in the noisy measurements. Private-PGM is highly scalable for sparse measurements, but may fail to run in high dimensions with dense measurements. We overcome the main scalability limitation of Private-PGM through a principled approach that relaxes consistency constraints in the estimation objective. Our new approach works with many existing private query answering algorithms and improves scalability or accuracy with no privacy cost.