PaperlayerView exact revision on arXiv

Source-linked AI summary

Graphical-model based estimation and inference for differential privacy

Ryan McKenna, Daniel Sheldon, Gerome Miklau

arXiv:1901.09136v1cs.LGcs.CRstat.ML

TL;DR

The paper addresses how to estimate new query answers from noisy privacy-preserving measurements when data distributions are high-dimensional. It uses graphical models to perform compact, principled inference over low-dimensional marginals, and reports improved efficiency, accuracy, and scalability across privacy mechanisms, subject to measurement-complexity and algorithm-specific limits.

  • Problem

    Existing inference methods for estimating new queries from noisy measurements are limited in scalability and generality, especially for high-dimensional data.

  • Method

    The paper uses graphical models to represent the data distribution and estimate marginals, avoiding explicit full contingency-table materialization.

  • Results

    The method can improve accuracy for scalable privacy algorithms and enable some previously non-scalable algorithms to run efficiently in high-dimensional settings.

  • Takeaways & Limitations

    Graphical-model inference provides a versatile building block for privacy algorithms using measurements over low-dimensional marginals.

  • Takeaways & Limitations

    Scalability depends on measurement complexity, and high tree-width can make marginal inference computationally difficult.

Abstract

from arXiv · show

Many privacy mechanisms reveal high-level information about a data distribution through noisy measurements. It is common to use this information to estimate the answers to new queries. In this work, we provide an approach to solve this estimation problem efficiently using graphical models, which is particularly effective when the distribution is high-dimensional but the measurements are over low-dimensional marginals. We show that our approach is far more efficient than existing estimation techniques from the privacy literature and that it can improve the accuracy and scalability of many state-of-the-art mechanisms.

1. Introduction

Differential privacy requires careful inference because poorly designed algorithms can incur unnecessary error, especially when estimating new queries from noisy measurements. The paper proposes graphical models as a compact, general foundation for improving inference in privacy algorithms.

  • Motivation: Differential privacy protects individuals, but complex analyses still lack generally error-optimal algorithms.Poor algorithm design can produce substantially greater error than necessary for a given privacy guarantee.
  • Problem: Inference combines noisy measurements to estimate answers to new queries over high-dimensional data.Measurements may cover individual attributes or selected combinations, while new queries can involve many attributes.
  • Existing limitations: Full contingency-table methods become infeasible as dimensionality grows, while factored models impose additional restrictions.The contingency table size is the product of attribute domain sizes; in the example, it would contain 10^19 entries.
  • Graphical-model approach: Graphical models avoid full materialization while retaining broad query-answering ability and compactness for low-dimensional measurements.Their structure is determined by the measurements, so no information is lost relative to a full contingency-table representation.
  • Graphical-model approach: The graphical-model representation corresponds to maximum-entropy selection among distributions minimizing estimation loss.This provides a principled way to choose one distribution when multiple distributions share the same estimated marginals.
  • Scope: The method is designed to be general across loss functions, privacy noise distributions, and primarily linear measurements, with an extension to nonlinear measurements.The approach is intended as a general inference component for privacy algorithms.

2. Background and Problem Statement

The paper formulates inference as estimating workload queries from privately released measurements over attribute marginals. This formulation supports new queries and more accurate answers by combining available measurements while preserving the privacy accounting of the releases.

  • Data representation: The data consists of records over discrete attributes, with a full domain whose size is exponential in the number of attributes.The paper represents the population using a normalized contingency-table probability vector.
  • Queries and marginals: Linear query sets are represented by matrices, and marginal query sets operate on probability vectors restricted to subsets of attributes.A marginal over a subset can be much smaller than the full domain while still defining equivalent queries on the full table.
  • Measurements: Measurements comprise a collection of marginal query sets, each released with its own privacy parameter and noise-addition mechanism.The combined privacy parameter follows from sequential composition across measurement sets.
  • Privacy: Differential privacy is preserved when inference post-processes privately computed measurements without accessing the protected data.The paper’s formulation treats the noisy measurements as given inputs to the estimation procedure.
  • Problem statement: The inference goal is to answer workload queries that may be new or may become more accurate when all available measurements are combined.This separates the measured query sets from the workload ultimately requested by a user.

3. Algorithms for Estimation and Inference

The paper formulates estimation over measured marginals and uses graphical models to recover a tractable, maximum-entropy distribution for answering new queries. Proximal algorithms optimize convex losses over the marginal polytope while avoiding full contingency-table materialization.

  • Optimization Formulation: Prior work estimates a full data distribution before using it to answer new queries.The paper distinguishes estimation of p̂ from inference using p̂ to answer later queries.
  • Optimization Formulation: The loss can depend only on measured marginals, which may be far lower-dimensional than the full probability vector.For linear measurements, the formulation includes L(µ)=||Q_Cµ−y||, and more generally supports losses depending on µ.
  • Optimization Formulation: Direct optimization over the marginal polytope is difficult because its combinatorial constraints are generally not enumerable.After estimating marginals, answering queries outside measured marginals is also unclear without a distributional representation.
  • Graphical Model Representation: The method represents the estimated distribution with an undirected graphical model chosen by a maximum-entropy principle.The graphical model has the measured marginals and provides a tractable representation for answering broader query classes.
  • Estimation Algorithms: Algorithm 2 achieves an O(1/t^2) convergence rate for convex losses with Lipschitz-continuous gradients.It has the same per-iteration complexity as Algorithm 1, requires one MARGINAL-ORACLE call per iteration, and needs the gradient Lipschitz constant.
  • Inference: New queries are answered directly from clique marginals or through variable elimination when they require other marginals.This avoids materializing the full contingency table during inference.

4. Use in Privacy Mechanisms

The graphical-model estimator is incorporated into four privacy mechanisms to address accuracy or scalability bottlenecks. It replaces full-vector or synthetic-data estimation with compact graphical-model representations while preserving the mechanisms’ measurement procedures.

  • Overview: The paper evaluates graphical-model estimation as an improvement to MWEM, PrivBayes, HDMM, and DualQuery.The goal is to improve the accuracy and/or scalability of these state-of-the-art mechanisms.
  • MWEM: MWEM becomes infeasible in high dimensions when it must explicitly represent the data distribution, especially for overlapping measurement subsets.Factored MWEM avoids explicit materialization only for disjoint attribute subsets, whereas the graphical-model update handles complicated overlaps.
  • MWEM: Replacing MWEM’s multiplicative-weights update with Algorithm 2 learns a compact graphical-model representation from accumulated measurements.The resulting representation avoids materializing the full probability vector.
  • PrivBayes: PrivBayes can replace noisy-measurement truncation, normalization, and synthetic-data sampling with graphical-model estimation and inference.The replacement uses an appropriate L1 or L2 loss and answers new queries through graphical-model inference.
  • HDMM: HDMM’s least-squares bottleneck requires materializing the full data vector even when measurements concern low-dimensional marginals.Algorithm 2 instead uses the same L2 loss with a graphical-model representation for such workloads.
  • DualQuery: DualQuery’s sampled measurements can be expressed through a log-likelihood in p and optimized with Algorithm 1 or Algorithm 2.When the workload is expressible through marginals, the log-likelihood depends on the marginal vector instead.

5. Experimental evaluation

Experiments show that PGM-based estimation improves accuracy for scalable privacy mechanisms and makes otherwise infeasible methods practical, while scaling well when measurements induce simple graphical models.

  • Experimental setup: The experiments evaluate four multi-dimensional datasets using workloads formed from 15 three-way sub-workloads, including prefix range queries for discretized numerical attributes.Each dataset contains categorical and numerical attributes, with numerical attributes discretized into 100 bins.
  • Improved accuracy: PGM estimation significantly improves accuracy for PrivBayes and DualQuery across the evaluated datasets.For PrivBayes, workload error reductions include 6× and 7× on Loans and Stroke; DualQuery reductions range from 1.2× to 4.4×.
  • Replacing infeasible estimation methods: PGM estimation makes MWEM and HDMM feasible on datasets where their original representations are too large to maintain in memory.MWEM can run out of memory or time out, while the modified HDMM comparison is substantially worse than PGM estimation.
  • Improved accuracy: HDMM+PGM reduces error relative to HDMM+LLS by 6.6×, 3.2×, 27×, and 6.3× across the four datasets.The reported improvements primarily stem from non-negativity and global consistency.
  • Scalability: PGM scales to datasets with 1000 attributes, whereas MW and LSMR fail beyond datasets with 10 attributes in the reported scalability experiment.PGM scalability primarily depends on measurement complexity rather than domain size.
  • Scalability: PGM's scalability can degrade when the measurement-induced graphical model has high tree-width because exact marginal inference becomes computationally expensive.The paper notes that approximate inference, such as loopy belief propagation, may be used in these cases.

6. Related Work

Related work studies private query release, posterior inference, graphical-model learning, and synthetic-data generation, while this paper uses graphical models to estimate distributions from externally determined measurements.

  • Private query release: Prior work extensively studies the private release of linear query answers.The cited literature spans many mechanisms for releasing statistical and linear queries under differential privacy.
  • Posterior inference: Williams and McSherry infer posterior distributions over model parameters from differentially private algorithm outputs using a known parameterization and prior.Their approach approximates a high-dimensional integral with Markov chain Monte Carlo or bounds from the factored exponential mechanism.
  • Graphical-model learning: Bernstein et al. privately learn parameters of an undirected graphical model whose structure is specified in advance and determines the measurements.In contrast, this paper finds a compact distribution representation from externally determined measurements, with graph structure emerging from those measurements and maximum entropy.
  • Synthetic-data release: Chen et al. privately release synthetic data using undirected graphical models, mutual-information structure selection, measured sufficient statistics, and consistency post-processing.Their mechanism is described as similar to PrivBayes but uses undirected graphical models instead of Bayesian networks.
  • Paper-specific formulation: This paper defines µ(θ) as the marginals of a graphical model with parameters θ, computable with the MARGINAL-ORACLE.

A.1. Proximal Algorithm Derivation

The proximal derivation applies mirror descent to the convex estimation problem and uses negative entropy to turn each update into marginal inference in a graphical model.

  • A.1. Proximal Algorithm Derivation: Mirror descent updates the data model by minimizing the loss gradient plus a Bregman-distance penalty over the marginal polytope.The loss is convex, and the Bregman distance is defined using a strongly convex, continuously differentiable function ψ.
  • A.1. Proximal Algorithm Derivation: Choosing ψ = −H, the negative entropy, transforms the mirror descent update into an optimization involving graphical-model parameters.The derivation uses ∇H(µt) = −θt to rewrite the update in terms of θt and the loss gradient.
  • A.1. Proximal Algorithm Derivation: Optimization over the marginal polytope reduces to computing marginals of a graphical model with parameters θt −ηt∇L(µt).Belief propagation or another MARGINAL-ORACLE can perform the required marginal inference.

A.2. Accelerated Proximal Algorithm Derivation

The accelerated proximal derivation follows the same general strategy as the proximal method and solves its required subproblem with the MARGINAL-ORACLE.

  • A.2. Accelerated Proximal Algorithm Derivation: The accelerated proximal algorithm is derived by adapting Algorithm 3 from Xiao (2010) to this inference setting.Its fourth step requires solving an optimization problem specific to the paper’s graphical-model formulation.
  • A.2. Accelerated Proximal Algorithm Derivation: The optimization problem required by the accelerated method is solved using the MARGINAL-ORACLE.The oracle supplies the marginal computations needed by the algorithm.

A.3. Direct Optimization

The direct method optimizes graphical-model parameters through marginal inference and supports factored queries, but its objective is generally nonconvex in those parameters and lacks a global-convergence guarantee.

  • A.3. Direct Optimization: The direct method estimates θ̂ by reformulating the constrained problem as unconstrained optimization over graphical-model parameters.It evaluates the loss through µ(θ), computed with a MARGINAL-ORACLE, and uses automatic differentiation through the full computation.
  • A.3. Direct Optimization: L-BFGS is used for the smooth L2-loss direct optimization problem.The method can apply many optimizers because the reformulated problem provides gradients of the loss.
  • A.3. Direct Optimization: The direct objective is not generally convex in θ, so convergence to the global minimum of the original convex problem is not guaranteed.This issue can occur even for L2 loss, although the authors did not observe convergence problems in their experiments.
  • Factored Query Inference: The query-answering algorithm augments the graphical model with query factors and uses variable elimination to marginalize the original variables.The output size is not necessarily exponential in d because factor matrices may have only one row, such as for marginalization.
  • Factored Query Inference: Factored query matrices represent queries as products of per-attribute factors and can encode marginals, multivariate CDFs, range queries, and distribution compression.Their rows are indexed by vectors z, with Q(z,x) defined as the product of the factor entries; equivalently, Q = Q1 ⊗· · ·⊗Qd.

C.2. Linear measurements with unequal noise

Unequal measurement noise is handled by rescaling queries and answers before applying standard losses, while the broader inference procedures use marginal or likelihood computations implemented through graphical-model oracles.

  • C.2. Linear measurements with unequal noise: When Laplace noise scales differ, rescaling each query and answer by 1/b_i equalizes the effective noise scale.The transformation replaces Q with DQ and y with Dy, where Dii = 1/b_i; the same idea applies to normal noise.
  • DualQuery: DualQuery computes workload-query answers, samples observations from intermediate distributions, and adds selected records to construct a synthetic database.The procedure is parameterized by workload queries and hyper-parameters including s, T, η, ϵ, and δ.
  • DualQuery: The DualQuery loss is the negative log likelihood of its output given candidate marginals and is differentiated with automatic differentiation.Evaluating the loss is expensive because it largely simulates DualQuery, but it omits the most computationally expensive record-selection step.

D.1. L1 vs. L2 Loss

The experiment compares L1 and L2 minimization across L1 loss, L2 loss, and workload error. L1 minimization favors L1 loss, while L2 minimization achieves lower workload error, which can worsen with excessive iterations.

  • L1 minimization produces lower L1 loss but higher L2 loss than L2 minimization.The difference is small for L1 loss and larger for L2 loss.
  • L2 minimization results in lower workload error than L1 minimization on the evaluated workload.
  • 0.066 minimum workload error increased to 0.084 at the end, with the increase beginning after about 200 iterations.The authors interpret this pattern as suggesting over-fitting, but stopping at the minimum requires access to the true data.
Loading 1901.09136v1…