Relaxed Marginal Consistency for Differentially Private Query Answering
Authors: Ryan McKenna
Siddhant Pradhan
Daniel Sheldon
Gerome Miklau
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
convex optimization
graphical models
approximate inference
local polytope

Abstract: 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.

Relaxed Marginal Consistency for Differentially Private Query Answering
Ryan McKenna, Siddhant Pradhan, Daniel Sheldon, Gerome Miklau College of Information and Computer Sciences University of Massachusetts
Amherst, MA 01002
{rmckenna, sspradhan, sheldon, miklau)@cs umass edu
Abstract
Many differentially private algorithms for answering database queries involve a step that reconstructs 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 recent approach that uses graphical models to represent the data distribution, with complexity proportional to that of exact marginal inference in graphical model with structure determined by the co-occurrence 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 PRIVA PRIVATE-POO through 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.
Introduction
central problem in the design of differentially private algorithms is answering sets of counting queries from a database. Many proposed algorithms follow the deleettmmasur--rcoonssiii they select a of measurement queries, they privately measure them (using Gaussian or Laplace noise addition), and then they reconstruct the data or query answers from the noisy measurements. When done in a principled manner, the reconstruct phase serves number of critical functions: it combines the noisy evidence provided by the measurement queries, it allows new unmeasured queries to be answered (with no additional privacy cost), and it resolves inconsistencies in the noisy measurements to produce consistent estimates, which often have lower error. In this paper, we propose a novel, scalable, and general-purpose purpose approach to reconstruct step. With a principled approach to this problem, future research can focus on the challenging open problem of query selection.
paradigm:
Most existing general-purpos. methods for reconstruction cannot scale they operate over a vectorized representation of the data, whose size is exponential in the dimension- ality [1-6]. Some special purpose methods exist that have better scalability, but are only applicable within particular mechanism or in certain special cases [7-11, 5, 12-15]. A method, PRIVATE-PGI much of the generality of the general-purpose purpose methods. PRIVATE-PGiE can be used for the recon- struction phase whenever the measurements only depend on the data through its low-dimensional marginals. PRIVATE-PGM avoids the data vector representation in favor of more compact graphical model representation, and was shown to dramatically improve the scalability mechanisms while also improving accuracy [16]. SLLVATE-PGM. was used in the winning entry of the 2018 NIST differential privacy synthetic data contest [17, 18], as well as in both the first and second-place place entry of the follow-up 2020 NIST differential privacy temporal map contest [19, 20].
dinensiinnni data, as
[16], offers the scalability of these special purpose methods and retains
number of popular
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

While PRIVATE-POO PAANTE--GMMI is far more scalable than operating over vector representation of the data, it is still limited. In particular, its required memory and rumtime depend on the structure of the underlying graphical model, which in turn is determined by which marginals the mechanism depends on. When the mechanism depends on a modest number of carefully chosen marginals, PRIVATE-PGM extremely efficient. But, as the number of required marginals increases, the underlying graphical model becomes intractably large, and PRIVATE-PGM eventually fails to run. This is due to the inherent hardness of exact marginal inference in a graphical model.
In this paper, we overcome the scalability limitations of PRIVATE-PGIA by proposing natural relaxation of the estimation objective that enforces specified local consistency constraints among marginals, instead of global ones, and can be solved efficiently. Our technical contributions may be of broader interest. We develop an efficient algorithm to solve a generic convex optimization problem over the local polytope of a graphical model, which uses a body of prior work on generalized belief propagation [21-31] and can scale to problems with millions of optimization variables. We also propose a variational approach to predict "out-of-model" marginals given estimated pseudo-marginals, which gives completely variational formulation for both estimation and inference: the results are invariant to optimization details, including the approximate inference methods used as subroutines.
Our new approach, PRIVATE-PGM, but can be deployed in far more settings, allowing effective reconstruction to be performed without imposing strict constraints on the selected measurements. We show that APPGM permits efficient reconstruction for HDMM [32], while also improving its accuracy, allows MWEM [5] to scale to far more measurements, and improves the accuracy of FEM [33].
(APPGM), offers many of the same benefits as
2 Background
We first review background on our data model, marginals, and differential privacy, following [16].
Data Our input data represents population of individuals, each contributing a single record x (21,-..,Ta) where x; is the 8th attribute belonging to a discrete finite domain 52 of n, possible values. The full domain is Ω II P2 and its size = II n, is exponential in the number of attributes. A dataset X consists of m such records X = (x(1)
(m)) is often convenient to work with an alternate representation of X: the data vector or data distribution p is a vector of length n, indexed by x E Ω such that p(x) counts the fraction of individuals with record equal to x. That is, m Em ((x = x). Vx E Ω where T(.}} is an indicator function.
p(x) = 1
When dealing with high ligh-dimensional data, it is common to work with marginals defined over subset of attributes. Letr S [d] be a region or clique that identifies a subset of attributes and, for x E Ωt let x, = (zi)ier be the sub-vector of x restricted to r. Then the marginal vector (or simply "marginal on r"") p4.. defined by:
Marginals
1
Hy (x,,) =
m Σ T(x xx), Vx, E E = SQ.
(1)
iEr
This marginal is the data vector on the sub-domain Ω, corresponding to the attribute set r. Its size ny : [0,1 = Il ni, which exponential in |r| but may considerably smaller than n. A marginal on can be computed from the full data vector or the marginal for any superset of attributes by summing over variables that are not in r. We denote these (linear) operations by M, and Pa so μ, M,p P. Ps-rr, for any r C We will also consider vectors μ that combine marginals for each region in a collection C, and let Mc be the linear operator such that = (Hy)rec = Mcp.
Differential Privacy Differential privacy protects individuals by bounding the impact any one individual can have on the output an algorithm.
Definition (Differential Privacy [34]), A randomized algorithm A satisfies (e, 8)ddifferentia privacy if. for any input X, any X' E nbrs (X),, and any subset of outputs S S Range(AA),
Pr[A(X) S < exp(e) Pr(A(X') E 6
Above, nbrs( (X denotes the set of datasets formed by replacing any (()) E X with an arbitrary new record (+) E Ω. When ò = 0 we say A satisfies e-differential privacy.

---

3 Private-PGM
In this section we describe PRIVATE-PGM. [16], general-purpose reconstruction method applied to differentially private measurements of discrete dataset. There are two steps to PRIVATE-PGM: (I) estimate a representation of the data distribution given noisy measurements, and (2) infer answers to new queries given the data distribution representation.
In particular, suppose an arbitrary 6) differrentialyy private algorithm is run on discrete dataset with data vector Po, where A only depends Po through its low-dimensional marginals Ho = McPo for some collection of cliques C. The sample y ~ A(H²) typically reveals noisy high-level aggregate information about the data. PRIVATE-PGGM will first estimate compact representation of a distribution p that explains y well, and then answer new queries using p.
PRIVATE-PGM first estimates data vector by finding p to solve the inverse problem minp L(Mcp), where L(u) is convex loss function that measures how well I explains the observations y. Since L ((Mp)) only depends on p through its marginals, it is clear we can find the optimal marginals by instead solving the following problem.
Estimation: Finding Data Distribution Representation
Problem 1 (Convex Optimization over the Marginal Polytope). Given clique set C and convex loss function L(n), solve
ja argmin L(p),
MEM(C)
where M(C) {u= 3 s.t. Mep p} the set of realizable marginals, known as the marginal polytope Cf [35].
The solution to this problem gives marginals that are consistent with some underlying data vector and, therefore, typically provide better estimate of the true marginals than y. In the general case, the loss function L can simply be set to the negative log likelihood, i... L(μ) = - log Pr[ Pr[A(() y). however other choices are also possible. As concrete motivating application, consider the where the mechanism A adds Gaussian noise directly to the data marginals 14g, i.e., A(Ho) = where y, oo, + (0, o² In,.). In this case, the log-likelihood is proportional to the squared
Euclidean distance and gives the loss function L(p)= = || y12.. so the problem at hand is an L2 focuses on convex loss functions, but the
minimization problem. The theory for PRIVATE- algorithms are also used to seek local minima of Problem I when L is non-convex.
Graphical models solve Problem 1 and how to recover full data vector from fa. PRIVATE-PGM addresses both with graphical models. A graphical model with clique set C is distri- bution over f2 where the unnormalized probability is a product of factors involving only subsets of variables, one for each clique in C. It has the form
Two remaining issues are how to
Algorithm PROX- -GM [16]
Input: Convex loss function L(μx Output: Marginals ja, parameters
Ô = 0
for 1, 1..... ., do
p MARGINAL-ORACEEE ORACLE(() 0 0 n VL())
(x
7 exp Σ E rEc
1
return ja. θ
The real numbers (x,) are log-potentials or parameters. The full parameter vector (0, (x,))rec tween these two vectors is central to graphical models [35]:
(x.))), x.eet. matches the marginal vector μ in size and indexing, and the relationship be-
A parameter vector 0 determines unique marginal vector M4 M(C), defined as μe McPe- the marginals of Pa. Marginal inference is the problem of (efficiently) computing Po from O. can be solved exactly by algorithms such as variable elimination or belief propagation with junetion tree [36]. We denote by MARGINAT-ORACLLE an algorithm that outputs Ho on input
For every μ E M(C) with positive entries, there unique distribution pe the family of graphical models with cliques C that has marginals μ. and has maximum entropy among all distributions with marginals μ.
For mechanisms with continuous output values, interpret this as negative log-density.

---

ABCD
DE
ABC
AD
BCD
DE
ABC
AD
BCD
DE
(a) Junction Tree
(b) Factor Graph
(c) Saturated Region Graph
Figure 1: Comparison of different region graph structures defined over a domain with attributes {A. D, that support the cliques C = {[A, (4. D), C, D), (D,
PROX-PGM (Algorithm 1) is a proximal algorithm to solve Problem 1 [16]. It returns marginal vector ja (CC) that minimizes T.( and parameters i such that Pa has marginals ja. The core of the computation is repeated calls to MARGINAL-OORACLE The estimated graphical model Pa has cliques C that coincide with the marginals measured by the privacy mechanism, and has maximum entropy among all distributions whose marginals minimize L(μ). In general, there will be infinitely many distributions that have marginals f (and hence are equally good from the perspective of the loss function L). PRIVATE-PGM chooses the distribution with maximum entropy, which is an appealing way to break ties that falls out naturally from the graphical model.
Inference: Answering New Queries With Pa in hand, PRIVATE- PGM can readily estimate new marginals 14,. There are two separate cases. If r is contained in clique of C, we say is "in-model", and we can readily calculate μe, from the output of FROX-PGM The more interesting case occurs when is out-of-model (is not contained in clique of C): in this case, the standard way compute H4, is to perform variable elimination in the graphical model pa-
that of MARGINAL-ORACIA which depends critically on the structure of the cliques C measured by the privacy mechanism. In general, running time exponential in the treewidth of the graph G induced by attribute co-occurrence within a clique of C. When G is tree-like, PRIVATE-PGM. can be highly efficient and exponentially faster than working with a full data vector. When G is dense, PRIVATE-PGM may fail run due time or memory constraints. This limitation is not specific to the PROX-PGM algorithm: Problem I is as hard as marginal inference, which can be solved by minimizing the (convex) variational free energy over the marginal polytope [36]. A primary difficulty is the intractability of M(C), which is a convex set, but in general requires very large number of constraints to represent explicitly [35]. In two state-of-the oftt---rr--- mechanisms for synthetic data, MST [18] and PrivMRF [20], C was specifically chosen to limit the treewidth and ensure tractability of Private- PGM. In other mechanisms agnostic to the limitations of PRIVATE-PGM, like HDMM and MWEM, the set C can often lead to graphs with intractable treewidths.
Remark 1. The complexity of PRIVATE-PGM depends
4 Our Approach
In this section we describe our approach to overcome the main scalability limitations of PRIVATE- PGM, by introducing suitable approximations and new algorithmic techniques. Our innovations allow us to scale significantly better than PRIVATE-POG PGM with respect to the size Cf A high-level idea is to use approximate marginal inference in the PROX-PG1 algorithm, but doing so naively would make it unclear what, if any, formal problem is being solved. We will develop principled approach that uses approximate inference to exactly solve a relaxed optimization problem.
Region Graphs Central to our approach is the notion of a region graph, which is a data structure that encodes constraints between cliques natural graphical format and facilitates message passing algorithms for approximate marginal inference.
Definition 2 (Region Graph [36]). A region graph G (V, E) is directed graph where every vertex r E V is an attribute clique and for any edge r >> & E ε we have that r 2 8. We say that G supports a clique set C if for every clique r C, there exists some r' E V such that Cr'.
For any region graph, there a corresponding set of constraints that characterize the local polytope of internally consistent pseudo-marginals, defined below.

---

Definition 3 (Local Polytope [36]). The local polytope of pseudo associated with a region graph G = (V,8) is:
[()) T20
1 P.
Vr V Vr +
(2)
The nodes in the region graph correspond to the cliques in the aseudo-marginas vector, while the edges in the region graph dictate which internal consistency constraints we expect to hold between two cliques. These constraints are necessary, but not sufficient, for a given set of geedo-marginale to be realizable, i.e., M(V) S L(G). In the special case when G' is a junction tree, these constraints are also sufficient, and we have M(V) [(G). We use the notation T place of ş to emphasize that T is not necessarily valid marginal vector, even though we will generally treat it as such. This notational choice is standard in the graphical models literature [35]. The general idea is to relax problems involving the intractable marginal polytope to use the local polytope instead, since L(G) is straightforward to characterize using the linear constraints in Equation (2).
Region graphs can encode different structures, including junction trees and factor graphs as special cases. For example, Figure 1 shows three different region graphs that support C [[A, B, C). {A, D}: {B, C, D). DD, E}}. At one extreme is the Junction Tree, shown in Fig- ure la, which obtained by merging cliques (A, [A, and C, into a super-clique {A, B,C,C, C, Here, M(V)- = (G),, and ordinary belief propagation in this graph corresponds to exact marginal inference. At the other end of the extreme the Factor Graph, shown in Figure lb. This graph contains one vertex for every clique E C. plus additional vertices for the singleton cliques. It encodes constraints that all cliques must agree on common one-way marginals. For example, T ABC and TBCD must agree on the shared one-way marginals TB and Tc. but not necessarily on the shared two-way marginal TBC. A natural middle ground is the fully Saturated Region Graph, shown in Figure lc. This graph includes every clique E C as vertex, and includes additional vertices to capture intersections between those cliques. Unlike the factor graph, this graph does require that TABC is consistent with T TBCD with respect to the TBC marginal. Unlike the junction tree, this graph does not require forming super-cliques whose size grow quickly with (C). For more details about the concepts above, please refer to [36, Section 11.3].
The methods we describe in this paper apply for any region graph that supports C. By default, we simply use the fully saturated region graph, which is the smallest region graph that encodes all internal consistency constraints, and can easily be constructed given the cliques [36].
Finding an Approximate Data Distribution Representation We begin by introduc- ing a very natural relaxation of the problem we seek solve.
Estimation:
Problem 2 (Convex Optimization over the Local Polytope). Given a region graph G and a convex loss function L(T) where (Tr)rev, solve:
argmin L(T). TEG(G)
In the problem above, we simply replaced the marginal polytope M(V) from our original problem? with the local polytope C(G). Since this is a convex optimization problem with linear constraints, can be solved with number of general purpose techniques, including interior point and active set methods [37]. However, these methods do nothing to exploit the special structure in the constraint set L(G), and as such, they have trouble running on large-scale problems.
Our first contribution is to show that we can solve Problem 2 efficiently by instantiating FROX-PGM with a carefully chosen approximate marginal oracle. To do so, it is useful to view approximate marginal inference through the lens of the free energy minimization problem, stated below.
Problem 3 (Approximate Free Energy Minimization [36]). Let G be region graph, 0 (0+) be real-valued parameters, and (T) = Erey (TT). where Ky E R. are counting numbers, and HTT,) = =- -xx (x,,,) log T, (x,,) is the Shannon entropy of Tv, solve:
+
-rgmmin - HT(()
TEC(G)
2If G supports C, we can assume without loss of generality that Problem 1 was defined on M(V) instead of M(C). In particular, the loss function L can be written to depend on marginals (Hrr)ev instead of (p,)ree, because the latter can be computed from the former.
5

---

This problem approximates the (intractable) variational free energy minimization problem [35], for which the optimum gives the true marginals of Pp. by using (G) instead of MM(V), and using (T) as an approximation to the full Shannon entropy. Many algorithms for approximate marginal inference can be seen as solving variants of this free energy minimization problem under different assumptions about G and R. [21-31].
Theorem (Algorithm for Approximate Free Energy Minimization [25]). Given region graph G. parameters 0 = (rr),ev, and any positive counting numbers Kor > 0 for r E V, the convex generalized belief propagation (CONvEX- algorithm [25] solves the approximate free energy minimization problem of Problem 3.
CONVEX- GBPP is listed in Appendix A (Algorithm 2) and is message-passing algorithm in the region graph that uses the counting numbers as weights. Importantly, the complexity of CONVEX- GBP depends mainly the size of the largest clique in the region graph. In many cases of practical interest, this will be exponentially smaller in the saturated region graph than in a junction tree.
Theorem 2. When PROX-PGM. uses SONVEX-GBI as the MARGINAL ORACLE (with any positive counting numbers k), solves the convex optimization problem over the local polytope of Problem
This result is remarkable in light of previous work, where different counting number schemes are used with the goal of tightly approximating the true entropy, and form the basis for different approximate inference methods. In our setting, all methods with conver counting numbers are equivalent: they may lead to different parameters 0, but the corresponding pseudo-marging + = CONvEX- (O) invariant. Indeed, the optimal & depends only on the estimation objective L(r) and the structure of the local polytope. We conjecture that similar invariance holds for traditional marginal- learning objectives with approximate inference [38] when message-passing algorithms based on convex free-energy approximations are used as the approximate inference method.
Proof. Since T. is convex function and L is convex constraint set, this problem can be solved with mirror descent [39]. Each iteration of mirror descent requires solving subproblems of the form:
argmin T T VL(T') 1 D(T,T'), T)t
D(T,T') = (TT) - - - (T-r') TV((r')
TEC
Here, D is a Bregman distance measure and v is some strongly convex and continuously differentiable function. Setting & K a negative weighted entropy with any (strongly) convex counting numbers K, we arrive at the following update equation:
argmin VVI(T') + 1
Hx((T) + +T (VH((T))
TEL(G)
argmin T +EL(G)
VTT'') VH*(+') (T(
(algebraic manipulation)
argmin T TEL(G)
(TT' 8¹) (T)
(Lemma I; Appendix A)
= CONVEX-GBP(G, 0- - -1e VL('), k)
(Theorem 1)
Inference: Answering New Queries We now turn our attention to the problem of inference. The central challenge is to estimate out-of-model marginals. Let + and Ô be the estimated pseudo- marginals and corresponding parameters after running PROX-PGM with CONvEX-GBP and region graph G. We have + R Mg. and want an estimate 4, R Po,r where r & V.
CONVEX GBP is the mapping such that + = CONVEX-GBP = Mo- Thus, it is appropriate to use CONVEX-GBP with estimated parameters Ô as the basis for estimating new pseudo-marginals. This requires selecting an expanded region graph G' that supports and new counting number fiy- In Appendix B, we analyze this approach for an idealized setting and find that leads to estimates 4, that maximize the entropy H(f,) subject to f, being consistent with + on overlapping marginals. However, there are two practical difficulties with the idealized setting. First, there may be no +, that is consistent with + on overlapping marginals: this is because + satisfies only local consistency constraints. Second, the idealized case uses K, very close to zero, and CONVEX performs poorly in this case. Instead, we design an optimization algorithm to mimic the idealized setting:

---

0275
Exact
Ener sureec ragae
Exact
Satrrise lagin
Sal araled Region Graph
Saturrate urated Begion Griph
Packer Graph
Pactor Geagh
Nokey Marginals
Ten guaaggati
Number of Mensured Chiques
Namber Meaxured Cliuuss
Nimber of Messured Ciques
(a)
In-Madel Marginals
(b) Out-of-Model Marginals
(c) Scalahility
Figure 2: Comparison between PROX-PGM with exact and approximate inference (for different region graph structures): (a) in-model (measured) marginals, (b) out-of-model
(unmeasured) marginals, and (c) scalability of PROX-PGX vs. number of measured marginals.
Problem 4 (Maximize Entropy Subject to Minimizing Constraint Violation). Ler + (+ (uEE and let r $ V. Solve:
max (++) subject to f, E argmin
Σ T,ES NEV.amur
|P - Pa Pa-touul2
This relaxes the constraint that f, agrees with & on overlapping marginals, to instead minimize the L2 constraint violation. The inner problem is quadratic minimization problem over the probability simplex S. We show in Appendix B that a maximizer of Problem 4 is obtained by solving the inner problem once using entropic mirror descent [39].
The advantages Problem 4 are that it is low-dimensional, only requires information from about attributes that are in solved in parallel for different marginals r, This also gives a fully variational approach: both estimation and inference are fully defined through convex optimization problems that can be solved efficiently, and whose solutions are invariant to details of the approximate inference routines such as counting numbers.
be solved much more quickly than running CONVEX-GBL and can be
5 Experiments
Comparison to PRIVATE-PGM in Simple Mechanism We begin by comparing the accuracy and scalability of APPGM and PRIVATE-PGI, PGM for estimating a fixed workload of marginal queries from noisy measurements of those marginals made by the Laplace mechanism. We use synthetic data control the data domain and distribution (details Appendix C.1) and measure & different 3-way marginals with e = 1, for different settings of k. We run PROX-PGM with different versions of MARGINAL- ORACLE: Exact, Saturated Region Graph, and Factor Graph, where the first corresponds to PRIVATE- PGM, and the latter two to APPGM with the corresponding region graph (Figure 1).
Accuracy. We first show that when exact inference tractable, some accuracy is lost by using approximate inference, but the estimated pseudo-marginals are much better than the noisy ones. We use dight-dimensiona data with nı always tractable, and measure random 3 3-way marginals for from 1 to (3) 56. We then 10000 iterations of PROX-PGM using differing choices for MARGINAL-ORACE on in- and out-of-moddl marginals, averaged over all cliques and across five trials.
ns 4, which is small enough so exact inference is
and report the L, error
In Figure 2a, we see that the error of all PROX- the noisy measurements themselves. Exact PRIVATE-PGMM always has lowest error, followed by Saturated Region Graph, then Factor Graph. This matches expectations: richer region graph structures encode more of the actual constraints and hence provide better error. The trend is similar for out-of-model marginals (Figure 2b). Factor Graph, which only enforces consistency with respect to the one-way marginals, performs poorly unmeasured cliques, while Saturated Region Graph and Exact, which enforce more constraints, do substantially better. The difference between Saturated Region Graph and Exact is smaller, but meaningful.
variants is always lower than the error of
Scalability. Next we consider high-dimensional data and compare the scalability Exact and Saturated Region Graph on 100-dimensional data with n = R100 = 10. We vary & from

---

HDNI (Expected Browr
18
MWEM MI0E Ececi
1:40
FEM
113RMM Enact
113HM Reggion Cragh
Workooeet Eiver
M90723 Ragion Gragh
Workooud inter
TEM
Rag Region Gruph
Wordoad Size
Rounds of MWEM
Spsier
(a) HDMM - FIRE
(b) MWEM - FIRE
(c) FEM ADULT
Figure 3: Three examples of using PROX-PGM. to improve scalability and accuracy of other algo- rithms.
to 10 and calculate the per-iteration time of PROX-PGM." We consider two schemes for selecting measured cliques: random selects triples of attributes uniformly at random, and greedy selects triples to minimize the junction tree size in each iteration. As shown in Figure 2c, Exact handle about 50 random measured cliques or 1000 greedy ones before the per-iteration time becomes too expensive (the growth rate is exponential). In contrast, Saturated Region Graph runs with 10000 measured cliques for either strategy and could run on larger cases (the growth rate is linear).
Improving Scalability and Accuracy in Sophisticated Mechanisms We show next how PROX- PGM can be used to improve the performance of two sophisticated mechanisms for answering complex workloads of linear queries, including marginals. HDMM [32] is a state-of-the that first selects "strategy" set of (weighted) marginal queries to be measured, and then reconstructs answers to workload queries. MWEM [5] is another competitive mechanism that iteratively measures poorly approximated queries to improve a data distribution approximation. In each algorithm, the bottleneck in high dimensions is estimating a data distribution p. which is prohibitive to do explicitly. PRIVATE-PGM can extend each algorithm run in higher dimensions [16]. but still becomes infeasible with enough dimensions and measurements. HDMM is "batch" algorithm and either can or cannot run for particular workload. Because MWEM iteratively selects measurements, even in high dimensions can run for some number of iterations before the graphical model structure becomes too complex. By using APPGM instead, HDMM can run for workloads that were previously impossible, and MWEM can run for any number of rounds. We use the FIRE dataset from the 2018 NIST synthetic data competition [40], which includes 15 attributes and m 300,000 individuals.
algorithm
For HDMM, we consider workloads of k random 3-way marginals, for k = 1, 2, 8, ..... 256, 455, run five trials, and report root mean squared error, the objective function that HDMM optimizes. Figure 3a shows the results. HDMM with a full data vector cannot run for A > 2, but we can still analytically compute the expected error if it were able to run. HDMM + Exact fails to run beyond 16, while HDMM + Region Graph is able to run in every setting, substantially expanding the range of settings in which HDMM can be used. Both variants offer the significant error improvements of PGM-style inference, because they impose non negativiiy constraints that reduce error. For example, when k- 455, there is a 3x reduction in RMSE.
For MWEM, we consider the workload of 2-way marginals, use a privacy budget of 6 = 0.1 per round, and run for may rounds as possible, until MWEM has measured all 2-way marginals or exceeds a generous time/memory limit of 24 hours and 16GB. Figure 3b shows the results. As expected, MWEM+ Exact runs successfully in early iterations, but exceeds resource limits by 35-40 rounds. In comparison, MWEM + Region Graph can run to completion and eventually measure all 2-way marginals. For fixed number of rounds, Exact has lower error, in this case, substantially so, but results are data- deteedenedd (we evaluate with other datasets in Appendix C). The difference can largely be traced to Exact's 's better performance out-of-model cliques. In contrast, HDMM's measurements support all workload queries, so no out-of-moded inference is required, and we see little gap between exact and approximate inference. Improving performance of approximate inference for out-of-model marginals is an area to be considered for future work; see Appendix B.
Additional experiments We also apply APPGM to improve the accuracy of FEM, recent of the-art query-answering mechanism [33]. The setup is similar to the DualQuery experiment in [16]:
Scalability experiments were conducted on two cores of machine with a 2.4GHz CPU and 16 GB of RAM.
8

---

we run FEM to completion to release y, but instead of answering queries directly with y, we use APPGM to estimate geuuo-marginals, from which we compute query answers. This leads a modest enror reduction for all (Figure 3c; details in Appendix C). In Appendix C we also compare PRIVATE-PGM and APPGM directly to a method proposed in PriView [9] for estimating consistent marginals, and find that PGM "GM--aseed methods are more accurate for almost all values of c. We additionally compare PRIVATE- PGM and APPGM to the recent Relaxed Projection method [14], and found that APPGM performs better for > 0.1, although is outperformed for S 0.1.
6 Practical Considerations and Limitations
When using our approach in practice, there are several implementation issues to consider. First note that CONVEX- GBPP is an iterative algorithm that potentially requires many iterations to solve Problem 3, and this marginal inference routine is called within each iteration of PROX-PGM. Our theory requires running CONVEX-GID until convergence, but in practice we only need to run it for fixed number of iterations. In fact, we find that by warm starting the messages in CONVEX-GBI to the values from the previous call, within each outer iteration of PROX- -GM. This approach works remarkably well and makes much faster progress on reducing the objective than using more inner iterations. The main drawback of this is that we can no longer rely on a line search to find an appropriate step size within FROX-PGM, since one iteration of CONVEX- GBP with warm starting is not necessarily descent direction. Using a constant step size works well most of the time, but selecting that step size can be tricky. We utilize simple heuristic that seems to work well in most settings, but may require manual tuning in some cases. Second, we observed that introducing damping into CONVEX-GBP improved its stability and robustness, especially for very dense region graphs. Finally our MWEM experiment revealed that it is better to use PRIVATE- PGM over APPGM in the context of an MWEM-style algorithm, even though -WMTE-PGMM is more limited in the number of rounds can run for. This performance difference can be traced back to our method for out-of oo-medel inference, where utilization of local information only can lead poor estimates. We discuss alternative approaches for this problem in Appendix B.
actually only one inner iteration of CONVEX-GBI
7 Related Work
A number of recent approaches support reconstruction for measurements on high-dimensional data. As part of the PriView algorithm [9], the authors describe a method for resolving inconsistencies in noisy measured marginals, which has since been incorporated into other mechanisms [41, 11, 42, 10]. Like APPGM, their method only guarantees local consistency. In Appendix C, we show empirically that it achieves similar (but slightly worse) error than APPGM. In addition, the method is less general, as measured queries may only be marginals, while APPGM allows an arbitrary convex loss function to be specified over the marginals. This extra generality is critical for integrating with mechanisms like HDMM, FEM, and MWEM when the workload contains more complex linear queries.
In concurrent work, Aydore et al. [14] and Liu et al. [15] proposed scalable instantiations of the MWEM algorithm, both avoiding the data vector representation in favor of novel compact repre- sentations. Although originally described in the context of MWFM-style algorithms, the key ideas presented in these works can be abstracted Specifically, these methods can be seen as alternatives to APPGM for overcoming the scalability limitations of PRIVATE- - each of these methods make different approximations overcome the inherent hardness of Problem 1. A direct comparison between PRIVATE-PGM or APPGM, and these alternatives remains an interesting question for future research.
the more general setting considered in this work.
To avoid the data vector representation, Liu et al. [13] restrict the support of the data vector to the domain elements that appear in public dataset. This is much more scalable, but could result in poor performance if the public domain and the input domain differ substantially.
Lastly, Dwork al. [12] propose an algorithm similar to APPGM. Their approach also projects onto an outer approximation of the marginal polytope, using the Frank Wolfe algorithm. The outer approximation is constructed via geometric techniques and is different from the local polytope we consider. They prove favorable error bounds with polynomial running time, but leave open the implementation and evaluation of their approach. By using the local polytope and message- message-passing algorithms, our method can scale in practice to problems with millions of variables.
9

---

Acknowledgements
This work was supported by the National Science Foundation under grant IIS-1749854, by DARPA and SPAWAR under contract N66001-15-C-4067, and by Oracle Labs, part of Oracle America, through a gift to the University Massachusetts Amherst in support of academic research.
References
[1] Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the twenty-ninth ACM SGGMOD-SIGACT-SIGN ACM, 2010.
symposium on Principles of database systems, pages 123-134.
[2] Jaewoo Lee, Yue Wang, and Daniel Kifer. Maximum likelihood postprocessing for differential privacy under consistency constraints. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 635-644. ACM, 2015.
[3] Dan Zhang, Ryan McKenna, los Kotsogiannis, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. Ektelo: A framework for defining differentially-piie -private computations. In Conference on Management of Data (SIGMOD), 2018.
[4] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium Theory of computing, pages 351-360, 2013.
[5] Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems, pages 2339-2347, 2012.
[6] Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. Privacy, accuracy, and consistency too: holistic solution to contingency table release. In Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SSIAARY symposium Principles of database systems, pages 273-282, 2007.
[7] Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially private histograms through consistency. Proceedings of the VLDB Endowment, (1-2):1021-1033 2010.
[8] Bolin Ding, Marianne Winslett, Jiawei Han, and Zhenhui Li. Differentially private data cubes: optimizing noise sources and consistency. In Proceedings of the 201 ACM SIGMOD International Conference on Management of data, pages 217-228. ACM, 2011.
[9] Wahbeh Qardaji, Weining Yang, and Ninghui Li. PriView: Practical differentially private release of marginal contingency tables. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 1435-1446. ACM, 2014.
[10] Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. PrivSyn: Differentially private data synthesis. In 30th USENIX Security Symposium (USENIX Security 21), 2021.
(11) Zhikun Zhang, Tianhao Wang, Ninghui Li, Shibo He, and Jiming Chen. CALM: Consistent adaptive local marginal for marginal release under local differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 212-229, 2018.
[12] Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrete & Computational Geometry, 53(3):650- 673, 2015.
[13] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Steven Wu. Leverag- ing public data for practical private query release. Proceedings of the 38th International Conference Machine Learning, pages 6968-6977 2021.
10

---

[14] Sergul Aydore, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Ankit Siva. Differentially private query release through adaptive projection. In Proceedings of the 38th International Conference on Machine Learning, pages 457-467, 2021.
[15] Terrance Liu, Giuseppe Vietri, and Zhiwei Steven Wu. Iterative methods for private synthetic data: Unifying framework and new methods. arXiv preprint arXiv:2106.07153 2021.
[16] Ryan McKenna, Daniel Sheldon, and Gerome Miklau, Graphical-model based estimation and inference for differential privacy. In International Conference on Machine Learning, pages 4435 4444. PMLR, 2019.
[17] www.nist.gov. 2018 differential privacy synthetic data challenge. 2018.
URL
tundaag--opporruuttteseppp------ -nn.ooaaiiiiinniiioooiiio www.aaoottiooooii-e---e- challenges-1.
[18] Ryan McKenna, Gerome Miklau, and Daniel Sheldon. Winning the nist contest: A scalable and general approach to differentially private synthetic data. Journal of Privacy and Confidentiality, 2021.
[19] www.nist.gov. 2020 differential privacy temporal map challenge, 2020.
URL
https://www.. nist hia.tt/orrccl//ppeprpppemmaaaaaa
chariieeecallenges// aurrent-and-upcomine ptwp://pepppeaaaaaee/e////000dd0
[20] Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. Data synthesis via differentially private markov random fields. Proceedings of the VLDB Endowment, 14(11):21902D5 2202, 2021.
[21] Tom Heskes. On the uniqueness of loopy belief propagation fixed points. Neural Computation, 16(11):2379-22 2413,, 2004.
[22] Martin J. Wainwright, Tommi S. Jaakkola, and Alan S. Willsky. Tree-reweighted belief propagation algorithms and approximate ML estimation by pseudo-moment matching. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 3, page 3, 2003.
[23] Wim Wiegerinck. Approximations with reweighted generalized belief propagation. In Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), 2005.
[24] Po-Ling Loh and Andre Wibisono. Concavity reweighted kikuchi approximation. In Proceedings of the 27th International Conference on Neural Information Processing Systems- Volume 2, pages 3473-3481, 2014.
[25] Tamir Hazan, Jian Peng, and Amnon Shashua. Tightening fractional covering upper bounds on the partition function for high-order region graphs. Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 356-366, 2012.
[26] Jonathan S Yedidia, William T Freeman, and Yair Weiss. Constructing free-energy approxima- tions and generalized belief propagation algorithms. IEEE Transactions on information theory, 51(7):2222-2312 2005.
[27] Tamir Hazan and Amnon Shashua. Convergent message-passing algorithms for inference over general graphs with convex free energies. In Proceedings of the Twenty-Fourth Conference Uncertainty in Artificial Intelligence, pages 264-273, 2008
[28] Talya Meltzer, Amir Globerson. and Yair Weiss. Convergent message passing algorithms: unifying view. In Proceedings of the Twenty-Fifth Conference on Uncertainty Artificial Intelligence, pages 393-401 2009.
[29] Tom Heskes. Convexity arguments for efficient minimization of the bethe and kikuchi free energies. Journal of Artificial Intelligence Research, 26: 153-199 2006.
[30] Tom Heskes and Onno Zoeter. Generalized belief propagation for approximate inference in hybrid bayesian networks. In International Workshop on Artificial Intelligence and Statistics, pages 132-140. PMLR, 2003.

---

[31] Payam Pakzad and Venkat Anantharam. Estimation and marginalization using the kikuchi approximation methods. Neural Computation, 17(8):1836-187, 2005,
[32] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimizing error of high-dimensional statistical queries under differential privacy. Proceedings of the VLDB Endowment, (1(10): 1206))0:200010000 1219, 2018.
[33] Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu. New oracle-efficient algorithms for private synthetic data release. In International Conference Machine Learning, pages 9765-9774. PMLR, 2020.
[34] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity private data analysis. In Third Theory of Cryptography Conference, 2006.
[35] Martin Wainwright and Michael Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning. 1(1-2):1-305, 2008
[36] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[37] Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[38] Justin Domke. Learning graphical model parameters with approximate marginal inference.
IEEE transactions on pattern analysis and machine intelligence, 35(10):2454-2467, 2013.
[39] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):677175,, 2003.
[40] Diane Ridgeway, Mary Theofanos, Terese Manley, Christine Task, et al. Challenge design and lessons learned from the 2018 differential privacy challenges. 2021.
[41] Rui Chen, Qian Xiao, Yu Zhang, and Jianliang Xu. Differentially private high-dimensional data publication via sampling- based inference. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 129-138. ACM, 2015.
[42] Amrita Roy Chowdhury, Theodoros Rekatsinas, and Somesh Jha. Data-dependent differentially private parameter learning for directed graphical models. In International Conference on Machine Learning, pages 19339-1551. PMLR, 2020.
[43] Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. Dual query: Practical private query release for high dimensional data. In International Conference Machine Learning, pages 1170-1178 PMLR, 2014.
[44] Ninghui Li, Zhikun Zhang, and Tianhao Wang. Dpsyn: Experiences in the nist differential privacy data synthesis challenges. Journal of Privacy and Confidentiality, 11(2), 2021.
12


Reviews:
[{"review_id": "luuujOaNAOP", "reviewer": "Reviewer_E5iH", "summary": "In this paper the authors propose an algorithm for reconstructing data representations from noisy measurements and answering new queries using reconstructed data. Their algorithm, APPGM, builds on a recent method called Private-PGM, a reconstruction method that obtains data representations by solving an optimization problem using graphical models. By relaxing the consistency constraints on overlapping marginals, their algorithm achieves better scalability at the cost of some loss in accuracy.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes an algorithm for reconstructing data representations from noisy measurements and answering new queries using reconstructed data. Such algorithm is part of the popular select-measure-reconstruct paradigm for answering linear queries on private datasets. In such a framework, data analysts carefully choose a set of queries to send to the data owner. The data owner executes those queries on the private dataset and returns the answers with noise instrumented using standard differential privacy mechanisms to protect the privacy of individuals in the dataset. The data analyst then reconstructs (a representation of) the data and resolves any inconsistencies in the noisy measurements. The reconstructed data can be used to obtain more accurate answers to the original queries or answer new queries with no additional privacy cost. \n\nThe proposed APPGM algorithm builds on a recent method called Private-PGM. It has two components, one for reconstructing data and one for answering new queries using reconstructed data. For reconstruction, the authors propose the concept of Region Graph, which leads to pseudo marginals that enforces some but not all internal consistency constraints. The resulting optimization problem can be solved by using existing methods, for example, Prox-PGM with Convex-GBP. For answering new queries, instead of enforcing that the new marginals agree with reconstructed pseudo marginals on overlapping attributes, the authors minimize the L2 norm of constraint violation. By relaxing the consistency constraints, their algorithm achieves better scalability at the cost of some loss in accuracy. \n\n\nStrength: \n+ The concept of Region Graph is novel. It allows various partial consistency constraints to be expressed in a uniform framework. \n\n+ The presentation is clear. The paper did a good job in explaining complex concepts using consistent and sensible mathematical notations. \n\n+ The related work section is comprehensive and includes comparisons to many existing methods in the literature. \n\nWeakness:\n\n- The paper does not contain formal analysis on the loss of accuracy due to relaxation of consistency constraints. As mentioned by the authors, the estimates of out-of-model marginals can be poor in the MWEM experiment. From the graphs, it seems that Private-PGM always outperform APPGM in terms of accuracy when it works. Should one only use APPGM when PPGM fails to run? How large can the drop in accuracy be when both can be applied? \n\n- The paper is not sufficiently self-contained as several important technical details and algorithms are in the supplementary material. As such, it is difficult for reviewers to verify some of the claims in the paper.\n\n\n\nOther Comments:\nIn the experiment (Fig. 2) Private-PGM demonstrates quite different behavior under two clique selection schemes: it can handle many more cliques when they are selected greedily to minimize the junction tree size, compared to when they are selected randomly. Such difference is not present in APPGM. Why is this the case?\n\nTypos:\nLine 14: in the design -> in the design of\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed several limitations when using their method in practice. More discussion on theoretical limitations could be beneficial to potential users of the algorithm.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "aPCu24ik90", "reviewer": "Reviewer_m5oy", "summary": "This paper proposes a new algorithm designed to privately and efficiently answer complex sets of counting queries from a database.\nThe proposed algorithm builds on top of Private-PGM and provides a more scalable way of reconstructing the noisy measurements by relaxing consistency constraints of queries.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Paper is well written and easy to read\n- The experimental results show how the proposed algorithm can improve existing techniques to answer counting queries.\n- The authors might consider the local least square approximation inference step in [0] and show how it compares with the proposed algorithm for large number of queries.\n- How does the proposed algorithm compares against FEM? In the current paper, the authors add the inference step to FEM, but they do not show a straightforward comparison between FEM and APPGM.\n\n\n[0] Ryan McKenna, Daniel Sheldon, and Gerome Miklau. Graphical-model based estimation and404\ninference for differential privacy. In International Conference on Machine Learning\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the proposed algorithm are clearly discussed in the paper ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "_twmVWUncs_", "reviewer": "Reviewer_8W3Z", "summary": "The paper address the problem of answering a complex set of counting queries subject to DP.  They present a basic paradigm that is shared across typical DP approaches: select a set of queries, measure those queries, and reconstruct a dataset from the noisy measurements.  This paper addresses the last phase, where traditional approaches do not scale to large dimensional datasets.  The 2nd phase can easily be done with noise addition mechanisms, e.g. Laplace or Gaussian mechanisms, while the 1st phase is a much more challenging problem that is left open.  The main technical contribution is generalizing Private-PGM (the winning entry in the 2018 NIST DP contest).  Private-PGM suffers from not being scalable in many settings. The new APPGM enjoys many of the benefits of Private-PGM, while also being able to be deployed in more settings.  \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presentation of Private-PGM could be improved.  It is difficult to see the main challenge with Private-PGM, which is the motivation for this work.  The paper presents the optimization problem and the algorithms very succinctly, but this is done with heavy notation.  In the introduction, the reason for Private-PGM not scaling is due to “the graphical model typically becomes dense”, which is impossible to understand without getting into the details.  \n\nThe technical contributions in this work seem very broad and not just specific to DP.  Relaxing the consistency constraints from global to local seems natural and might find other applications.  The experiments are also quite interesting.  Although the results show that using Private-PGM can get much better results than the approximate version (with the Region Graph), there gets to be a point where computational resources will not allow for it to get better.  This is where the power of the approach presented in this work comes through because things like MWEM can run much more rounds and get better accuracy given the same computational resources.  \n\nMinor Comments: \n- What is $s$ and what is P_{s \\to r} in line 74? \n\n\n#### \nUpdate: I have reviewed the author responses and other reviewers comments and will keep my score unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "This paper deals with rigorous notions of privacy.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours"}, "extra_text": {}}, {"review_id": "6XxSySb109t", "reviewer": "Reviewer_85Fd", "summary": "For the problem of differentially privacy query answering, a standard paradigm is select-measure-reconstruct. In most methods, the reconstruction step needs to represent the data in vector form, which is impossible when the data is high dimensional. Private-PGM is an approach that uses a graphical model to represent the data more compactly, and it has been shown to improve the scalability of many popular algorithms while decreasing error. However, Private-PGM works best when the graphical model is sparse, and it becomes very inefficient when the graph is dense, which is due to the hardness of exact marginal inference. Therefore, Private-PGM has limited applications for real-world settings. The authors propose a new algorithm that relaxed the marginal inference step to allow Private-PGM to be adapted to more settings. To prove that their method is more scalable, they used the FIRE dataset, which has 15 attributes and 300K rows. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThis paper provides a technique to make private-pgm more scalable which I believe is a valuable contribution. In particular, they are able to run HDMM with much larger clique feature set without losing much accuracy.  They also show that the their technique can improve scalability of MWEM. However feel that the paper would be stronger if the authors included more comprehensive experiments. Right now the experiments include only one dataset with 15 features.\n\nMinor comments/questions:\n\nCan you obtain better accuracy by running the gradient descent longer or what is the optimization /accuracy trade-off?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously enjoyed this paper. Thanks for the strong submission. 
Decision: Accept (Poster)