Timezone: »

Relaxed Marginal Consistency for Differentially Private Query Answering
Ryan McKenna · Siddhant Pradhan · Daniel Sheldon · Gerome Miklau

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @

Many differentially private algorithms for answering database queries involve astep that reconstructs a discrete data distribution from noisy measurements. Thisprovides consistent query answers and reduces error, but often requires space thatgrows exponentially with dimension. PRIVATE-PGM is a recent approach that usesgraphical models to represent the data distribution, with complexity proportional tothat of exact marginal inference in a graphical model with structure determined bythe co-occurrence of variables in the noisy measurements. PRIVATE-PGM is highlyscalable for sparse measurements, but may fail to run in high dimensions with densemeasurements. We overcome the main scalability limitation of PRIVATE-PGMthrough a principled approach that relaxes consistency constraints in the estimationobjective. Our new approach works with many existing private query answeringalgorithms and improves scalability or accuracy with no privacy cost.

Author Information

Ryan McKenna (University of Massachusetts, Amherst)
Siddhant Pradhan (University of Massachusetts, Amherst)
Daniel Sheldon (University of Massachusetts Amherst)
Gerome Miklau (University of Massachusetts, Amherst)

More from the Same Authors