Timezone: »
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
-
2023 Poster: (Amplified) Banded Matrix Factorization: A unified approach to private training »
Christopher Choquette-Choo · Arun Ganesh · Ryan McKenna · H. Brendan McMahan · John Rush · Abhradeep Guha Thakurta · Zheng Xu -
2023 Poster: Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy »
Anastasiia Koloskova · Ryan McKenna · Zachary Charles · John Rush · H. Brendan McMahan -
2022 Spotlight: Kernel Interpolation with Sparse Grids »
Mohit Yadav · Daniel Sheldon · Cameron Musco -
2022 Poster: Kernel Interpolation with Sparse Grids »
Mohit Yadav · Daniel Sheldon · Cameron Musco -
2020 Poster: Advances in Black-Box VI: Normalizing Flows, Importance Weighting, and Optimization »
Abhinav Agrawal · Daniel Sheldon · Justin Domke -
2020 Poster: Permute-and-Flip: A new mechanism for differentially private selection »
Ryan McKenna · Daniel Sheldon -
2020 Spotlight: Permute-and-Flip: A new mechanism for differentially private selection »
Ryan McKenna · Daniel Sheldon -
2019 Poster: Divide and Couple: Using Monte Carlo Variational Objectives for Posterior Approximation »
Justin Domke · Daniel Sheldon -
2019 Spotlight: Divide and Couple: Using Monte Carlo Variational Objectives for Posterior Approximation »
Justin Domke · Daniel Sheldon -
2019 Poster: Differentially Private Bayesian Linear Regression »
Garrett Bernstein · Daniel Sheldon -
2018 Poster: Differentially Private Bayesian Inference for Exponential Families »
Garrett Bernstein · Daniel Sheldon -
2018 Poster: Importance Weighting and Variational Inference »
Justin Domke · Daniel Sheldon -
2018 Poster: Inferring Latent Velocities from Weather Radar Data using Gaussian Processes »
Rico Angell · Daniel Sheldon -
2016 Poster: Probabilistic Inference with Generating Functions for Poisson Latent Variable Models »
Kevin Winner · Daniel Sheldon -
2014 Poster: Stochastic Network Design in Bidirected Trees »
Xiaojian Wu · Daniel Sheldon · Shlomo Zilberstein -
2013 Workshop: Machine Learning for Sustainability »
Edwin Bonilla · Thomas Dietterich · Theodoros Damoulas · Andreas Krause · Daniel Sheldon · Iadine Chades · J. Zico Kolter · Bistra Dilkina · Carla Gomes · Hugo P Simao -
2011 Poster: Collective Graphical Models »
Daniel Sheldon · Thomas Dietterich -
2007 Spotlight: Collective Inference on Markov Models for Modeling Bird Migration »
Daniel Sheldon · M.A. Saleh Elmohamed · Dexter Kozen -
2007 Poster: Collective Inference on Markov Models for Modeling Bird Migration »
Daniel Sheldon · M.A. Saleh Elmohamed · Dexter Kozen