Efficient and Private Marginal Reconstruction with Local Non-Negativity
Authors: Brett Mullins
Miguel Fuentes
Yingtai Xiao
Daniel Kifer
Cameron N Musco
Daniel Sheldon
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
query release
synthetic data
Primary area: privacy
TL;DR: We propose a novel, scalable method for reconstructing answers to marginal queries. It makes existing mechanisms more scalable, accurate, or both.

Abstract: Differential privacy is the dominant standard for formal and quantifiable privacy and has been used in major deployments that impact millions of people. Many differentially private algorithms for query release and synthetic data contain steps that reconstruct answers to queries from answers to other queries that have been measured privately.  Reconstruction is an important subproblem for such mechanisms to economize the privacy budget, minimize error on reconstructed answers, and allow for scalability to high-dimensional datasets. In this paper, we introduce a principled and efficient postprocessing method ReM (Residuals-to-Marginals) for reconstructing answers to marginal queries. Our method builds on recent work on efficient mechanisms for marginal query release, based on making measurements using a residual query basis that admits efficient pseudoinversion, which is an important primitive used in reconstruction. An extension GReM-LNN (Gaussian Residuals-to-Marginals with Local Non-negativity) reconstructs marginals under Gaussian noise satisfying consistency and non-negativity, which often reduces error on reconstructed answers.  We demonstrate the utility of ReM and GReM-LNN by applying them to improve existing private query answering mechanisms.

Efficient and Private Marginal Reconstruction with Local Non-Negativity
Brett Mullins!
Miguel Fuentes
Yingtai Xiao Daniel Kifer
Cameron Musco?
Daniel Sheldon
University of Massachusetts, Amherst P State University
{bmullins mmfuentes, cmusco, sheldon)@ecs umass edu fyxx5224, (uuk1))00000 @psu edu
Abstract
Differential privacy is the dominant standard for formal and quantifiable privacy and has been used major deployments that impact millions of people. Many differentially private algorithms for query release and synthetic data contain steps that reconstruct answers to queries from answers to other queries that have been measured privately. Reconstruction is an important subproblem for such mecha- nisms to economize the privacy budget, minimize error on reconstructed answers, and allow for scalability high-dimensional datasets. In this paper, we introduce a principled and efficient postprocessing method ReM (Residuals-toe Mosiualls-t---aann (-oMMiaaalls) for reconstructing answers marginal queries. Our method builds on recent work on efficient mechanisms for marginal query release, based on making measurements using a residual querr basis that admits efficient pseudoinversion, which an important primitive used in reconstruction. An extension GReM-LNN (Gaussian Residuals-to- Mo-aainnnss with Local Non-negativity) reconstructs marginals under Gaussian noise satisfying consistency and non-negativity, which often reduces error on reconstructed answers. We demonstrate the utility of ReM and GReM-LNN by applying them to improve existing private query answering mechanisms.
Introduction
Differrnnial privacy is the dominant standard for formal and quantifiable privacy and has been used in major deployments that impact millions of people such as the 2020 US Decennial Census [1]. One of the most fundamental problems in differential privacy is answering workload of linear queries. Linear queries are used for basic descriptive statisties like counts and sums, and as building blocks for more complex tasks. Marginal queries, which describe the frequency distribution of subsets of discrete variables (e-g., income by age and education), are of particular interest as descriptive statistics and for use in downstream tasks like regression analyses.
key subproblem in linear query answering is reconstruction. Given workload of linear queries, most mechanisms select a different set of queries to measure to make the most efficient use of the privacy budget, and then the noisy answers to reconstruct answers to workload queries [2-11]. Effective reconstruction methods can combine information from all noisy measurements to provide mutually consistent answers to workload queries.
Computational complexity a key challenge for reconstruction methods. These methods answer workload queries by-either explicitly exponential the number of variables. To scale to high-dimensional data sets, existing approaches must represent this distribution compactly through some form of parametric representation [8-12], which introduces tradeoffs such as a restricted space data distributions that can be represented [8-
sereiityy-rroossuuutiing data distribution that has size
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

11], non-convex optimization objectives to find the best representation [9-11], or complexity that depends on the measured queries and is still exponential in the worst case [12].
We introduce ReM reconstruct answers workload of marginal queries from noisy measurements of residuals. Residuals are a class of linear queries that are related to marginals, which were recently introduced in the privacy literature [6] but previously studied in statisties [13, 14]. ReM uses compact representation of the data distribution to produce workload answers without exponential complexity in the number of variables. ReM builds on the reconstruction approach of ResidualPlanner [6], which utilizes Kronecker structure to efficiently perform pseudoinverse operations. ReM is flexible framework for performing reconstruction in a broad range of settings and it can be used with a variety of existing query-answering mechanisms. ReM also extends to the common setting of reconstructing answers to marginal queries from a set of noisy marginal measurements with isotropic Gaussian noise. In this case, ReM performs the standard pseudoinverse reconstruction and is the first method to do so efficiently. We also develop GReM-LNN (Gaussian ReM with local non-negativity). an extension that reconstructs marginals satisfying non-negativity, which often reduces error on reconstructed answers.
principled and scalable post-processing method to
We demonstrate the utility of ReM and GReM-LNN by showing that they significantly reduce error and enhance the scalability of existing private query answering mechanisms including ResidualPlan- ner [6] and the multiplicative weights exponential mechanisms (MWEM) [15]. Our code is available at https: : //ggttttttuub wwwm//mmuulinn///oecoooooooaaaee cewuulliss/effciiiii ett.ffffiiiine/e -aweettaaagnaaarnnaaaae reconstructionn.
2 Preliminaries
We consider a sensitive tabular dataset D records x (1)), (N), Each record x = (II,..., ........ xa) consists of d categorical attributes. The ith attribute x; belongs to the finite set X, of size n.. The data universe is X' II X; and has size n = II. n.. The data vector or data distribution E RR is a vector indexed by X' that counts the occurrences of each record in D; it has entries p(xc) = E T[z((0 w/]. Since is exponential in the data dimension d, it is computationally intractable to work directly with data vectors in high dimensions.
2.1 Linear queries, marginals, and residuals
Linear queries are a rich class of statistics that include counts, sums, and averages and are used as building blocks for more complex tasks. A linear query is the sum of real-valued function q: x + R applied to each record in the dataset. We adopt the equivalence that a query is a vector q E R" with answer pp. p. A query matrix workload W is collection of linear queries arranged row-wise in an m x n matrix. The answer to workload W for data vector is given by Wp.
Marginal queries are a common type of linear query for high-dimensional data. They count the number of records that match certain values for subset of the attributes - e.g., the number of people in a dataset with education at least college degree and income $50-$100K, Let S [d] be a subset of attributes and x,, = (xx)iez be the corresponding subvector of a record x. Further, let X, = IIie X and n, Ilie n4- The marginal je, E R has entries (ty(1) Ei= Tpr!" f] that count the number of occurrences in the dataset for each setting & E Xr of the attributes in n Let My E Rmyx* x> be the marginal workload so that μ4 = M.p. As shown in Fig. 1a, M, can be written concisely as Kronecker product over dimensions, with base matrices equal to the identity I E R" x for attributes in y and the all ones vector 1 E R x for attributes not in % Kronecker product matrices multi-dimennional array. In this case M., sums over dimensions of the array representation of p for attributes not in y. We provide brief summary of Kronecker products and their relevant properties in Appendix A.
be understood applying different linear operations along each dimension of
Residual queries are class of linear queries closely related to marginals. They were recently introduced in the privacy literature [6] but previously studied in statistics as variable interactions [13, 14]. For C [d]. the r-reiiulll is obtained from the marginal μ4, by applying differencing operator along each dimension. Let D ((R) be the linear operator that computes successive differences for vectors of length ngg, i.e., (D) = 0,+1 - 2 for i = 1,..., 74 1 an example is shown for nı 3 in Fig. lb. Let D, be the matrix that applies this operation to all attributes in the r-marginal as shown in

---

M,
X
1
KEY 7
Pay
-1
D.
Dio
KET R.
k E
1
D
E l: $
1m
lmm
(a) Marginals
(b) Differencing operator for ktth attribute.
(c) Differencing operator for r-marginal.
(d) Residuals
Figure 1: Kronecker structure of workloads.
Fig. Ic. The residual workload can be written as R, = D,Mr E I where m, = II (nt 1), which has the explicit Kroecker product form shown in Fig. 1d.' With these definitions, if ju, = M,P the r-marginal, the 7-residual a, D, Mr, R. p and can be computed from either μ4, or p.
Residuals and marginals have an intricate structure. The 7-marginal is uniquely determined by the r-residuals for S % i.e., there is an invertible linear transformation between M, and (R-))<+ (a vertical block matrix). Intuitively, a y-residual contains information not contained in the T-marginals for C y. Further, the row spaces of R and R,, are orthogonal for any # r', and the row spaces of M,, and R, are orthogonal when T Z y [6, 13, 14]. Along with Kronecker structure, the orthogonality of residuals the key property we will leverage perform efficient reconstruction.
key advantage of residual workloads that we can work with their pseudoinverses efficiently in certain situations even though they have exponential size. Let Q denote the Moore-Penrose pseudoinverse of Q. The following proposition builds on the reconstruction method in [6] and will be used to reconstruct answers to marginal query M,, from measurements for collection of residuals. Proposition 1. Let Rs (Ry)res be a combined workload of residual queries for all 5 collection S C 2|4,, where the individual matrices R, are stacked vertically. The size of Rs is m n where m = LTES my. Then for any (2r)reS E Rmm and any ", it holds that
D
EET
(K)
M
E TES,TCY
Ag,
where Ay,
X
(Yns)
1x
k kE
for Sy.
$
The matrix A has size n,y X m, and maps from the space of r-residuals to the space of 7-marginals The running time compute 2,, is ((1](n,))
The proof of this result appears in Appendix The analysis of time complexity appears Ap- pendix E.
2.2 Differential Privacy
When releasing the results of any analysis performed on sensitive data, particular care needs to be taken to avoid leaking private information contained the dataset. Differential privacy is mathe- matical criterion that bounds the effect of any individual in the dataset on the output of a mechanism, which is satisfied by adding noise to the computation. This allows for formal quantification of the privacy risk associated with any release of information.
Definition (Differential Privacy; [16)) Let M : X y/ be randomized mechanism. For any neighboring datasets D, D'' that differ by adding or removing at most one record, denoted D ~ D', and all measurable subsets C V: if Pr(M(D) E 5) S exp(e) Pr(M(DD) E 5) + 8, then M satisfies (c, 8) approoximate differential privacy, denoted (c. D)-
A fundamental property of differential privacy relevant to work is the post-processing property, which states that transformations of differentially private outputs that do not access the sensitive dataset 'D maintain their privacy guarantees. Formally:
Proposition 2 PPost-processingg [17]). Let M1 : X + y satisfy (c. ()-D)-DP and f : y + be a randomized algorithm. Then M X + Z fo M1 satisfies (c, 8).B).
The reconstruction methods we propose in this paper are post-processing algorithms that take as input a set of noisy linear query answers and, thus, inherit the privacy guarantees from those noisy answers. Note that the present analysis is largely agnostic the model of differential privacy used.
Note that our matrix D- is slightly different from the operator used in [6] but has the same row space [14].
3

---

We discuss variants of differential privacy and privacy guarantees for query answering in Appendix B.
2.3 Private query answering
In private query answering, we are given a workload of linear queries W E R_=x. We seek to approximate the answers Wy p as accurately as possible while satisfying differential privacy. A general recipe for private query answering is following this recipe such as the various matrix mechanisms [2-6] select and measure a set of queries Q and reconstruct answers to W. Data-dependent mechanisms following this recipe such as MWEM [15] and various synthetic data mechanisms [7. 9, 10, 18, 19] typically maintain model P of the data distribution p that is improved iteratively by repeating the steps of melect-maauur--rccoosttre and adaptively measuring queries that are poorly approximated by the current model p. The key idea is that it is often possible to obtain lower enror by measuring a different set of queries Q than W and then using answers to Q to reconstruct answers for W. In this paper, we focus on the reconstruction subproblem and propose methods applicable to both the data iata-independent and detendetnndnn settings.
www.maaa------oostueee Data Data-independent mechanisms
2.4 Query answer reconstruction
Reconstruction a central subproblem to query answering. Suppose y = Qp + E is the a set of measurements. To reconstruct data distribution, seek P such that Q8 y. One method is to set 9 = Q'y where Q+ is the Moore-Penrose pseudoinverse. This method is used in the matrix mechanism [4] and HDMM [5] but is not tractable in high dimensions. One contribution of our proposed method is to demonstrate that this pseudoinverse reconstruction is tractable when the query matrix Q is set of marginal measurements and & is isotropic Gaussian noise. Other reconstruction methods such as Private-PGM [12] and those used by the mechanisms PrivBayes [8], GEM [9]. RAP [10], and RAP++ [11] represent ş through a parametric representation. These (usually) ensure tractability in high dimensions by using a compact representation, but introduce different tradeoffs. The parametric assumption typically restricts the space of data distributions that can be represented [8- Optimizing over the parameteric representation is often non-convex, potentially leading to suboptimal optimization [9-11]. Private-PGM solves a convex optimization problem and is closest to the methods of this paper. However its complexity depends on the measured queries and still exponential in the worst case [12]; our methods will not have exponential complexity.
We note that all of these above reconstruction methods, and the methods presented in this work, only depend on the dataset through the noisy query answers and, thus, satisfy the same degree of privacy as the answers by the post-processing property of differential privacy (Proposition 2).
3 Efficient Marginal Reconstruction from Residuals
In this section, we discuss methods for reconstructing answers to a workload of marginal queries given measurements of residuals. These methods utilize the structure of marginals and residuals to make reconstruction tractable and minimize error. Let W C 2/d and Mw = (M&)>ew be the combined workload of marginals for all of the attribute sets in W (e.g.. all pairs or triples of attributes). Similarly, let Rş= = (Rt) TEs represent a set of residual queries for all T in a collection S. Our goal is to estimate the marginal query answers Mwp from noisy measurements z Rgp + E.
ResidualPlanner [6] solves this problem elegantly in the matrix mechanism (i.e. data-independent) setting under Gaussian
ResidualPlanner:
Algorithm 1 ResidualPlanner reconstruction
Input:
Marginal workload W.S W measure- ments 2, = R.p ( Σ,) for T E S 1: Reconstruct ja. E.s, A,, for y W
noise. Let W = (r C 7 7 E W) denote the downward closure of W. When S Wt.
the residual queries for S uniquely determine
the marginals for W, i.e., there an invertible linear transformation between Mw and Rs. This yields the reconstruction approach in Alg. 1. We suppose the residual queries R, are measured with Gaussian noise to yield Ey. In Line 1, the marginals are reconstructed by applying the invertible transformation from residuals to marginals. This reconstruction is equivalent to setting م. = M.
where p R5²2 and (2r)res by Proposition 1.

---

The full ResidualPlanner algorithm additionally chooses each Σ, = D. such that the resulting algorithm optimally answers the marginal workload indexed by W minimize error under a natural class of convex loss functions for a given privacy budget [6]. That this can be done efficiently for broad class of error metrics for marginal workloads significant given the computational challenges that are often faced when attempting to optimally select measurements and reconstruct workload answers in high dimensions.
A general approach to reconstruction. We propose a reconstruction algorithm that, like the one in ResidualPlanner, is efficient and principled, but that applies in more general settings. Reconstruction in ResidualPlannee uses the invertible transformation from residuals to marginals. This restricts to the case where the measured queries exactly determine the workload queries in the absence of noise. To address the full range of applications, it is important to address the cases where workload queries are overdetermined, underdetermined, or both.
Our proposed algorithm, ReM, is shown in Alg. 2. Compared ResidualPlanner, the main differences are: (1) the set S of measured residuals arbitrary, (2) resid- ual query can be measured any number of times with any noise distribution, (3) an optimization problem is solved for each to estimate the true residual query answer å, & P. (4) reconstruction uses the es- timated residuals å instead of the noisy measurements 2y. The loss function L, in Line captures how well a, explains the entire set of noisy measurements (Zr,ski=,....k For example,
Algorithm Residualss-uee Mo-Maiaaalltt-aaalalaala (ReM)
Input: Marginal workload W, arbitrary S, measure- ments Zr,i Ryp+ + &r, for r E S, == 1,...,,, where Er,i comes from any noise distribution
Estimate å R.p for T E S by minimizing loss
function (ar)
Reconstruct P ErES::gY ,,, for Y E W
a typical choice is L, = - -E log p(zr, (., = ar), the negative log-likelihood of the measurements.
The following result shows that solving the optimization problems in Line is equivalent to finding compact representation of data distribution P that minimizes a global reconstruction loss and then using P to answer each marginal query.
Theorem 1. Suppose &, minimizes (a(a)) over Th- for each T S and let (â+))res Then Alg. 2 outputs ü., M.P. where R à is global minimizer of the combined loss function Eres (R,p) over I=..
This result is proved (in Appendix D) by showing that R.y o, for all т, and thus ý optimizes each individual loss function I,,, and so must be global minimizer. Proposition then shows that j., M, M, Rgá has the form given in Line 2 of the algorithm.
4 Applications of ReM under Gaussian Noise
In this section, we apply ReM to reconstruct answers to marginal queries in various settings: (1) we reconstruct from residuals measured with Gaussian noise, (2) we reconstruct from marginals measured with isotropic Gaussian noise, and (3) we reconstruct non-negative answers from residuals measured with Gaussian noise.
4.1 Reconstruction under Gaussian noise
An instance of ReM that allows for effi- cient computation is when residuals are measured with Gaussian noise i.e., Z = R,p+ + & where &-, (O, E.,)) and the loss function L, (a,) is the negative -ileeiildhood of the measurements. In this case, & = (âr)res is the maximum likelihood estimate of the residual an- swers a = (a-)res- We refer to this setting as GReM-MLE (Gaussian ReM with Maximum Likelihood Estimation), shown in Alg. 3.
Algorithm Gaussian ReM with Maximum Likelihood Estimation (GReM-MLE)
Input: Marginal
workload W, arbitrary S. measurements 2 R.P + -N(00 E.s) for e S,
i= 1,...,ki
1: Estimate å; = (E,T,)) Σ, Di for E S
2: Reconstruct P. = Eresirgh 2y, for W
5

---

R, Mr where At T,5 The loss function L- (ar) is a sum of quadratic forms given by (+(a)) = Ex 2r,a) 2,,)) 22, 2r,). In this setting, the optimization problems in Line of Alg. 2 have the closed-form solution & (E; ) "E 2,, Zr, which is form of inverse-variance weighting and can be verified by setting the gradient of the loss function to zero.
GReM-MLE improves computational tractability by reducing Alg. 2 to operations on matrices. Moreover, if the covariances among measurements of residual R,- differ only by a constant for r E S, K where σr,i E R. then å, can be computed as a weighted average given by
ie.. Σ,, 5. K, â o - 2r. All instances of GReM-MLE considered throughout the paper satisfy this assumption of proportional covariances for each S.
4.2 Reconstruction from marginals
common practice in existing mechanisms is to measure marginal queries with isotropic Gaussian noise [4. 9, 11, 18, 20J. In this special case, the measurements can be converted to equivalent set of residual measurements with independent Gaussian noise, allowing us to apply GReM-MLE.
The key observation is that marginal query answer μ4, = Map for attribute set can be used to derive residual answers a, R,p for each T S y via the following Lemma (proved in Appendix D):
Lemma 1. For T C the residual RG can be recovered from the marginal My as
Doy 1
KET
kET
1
k
Whereas Ay, maps answers from residual R, to answers to marginal My. the matrix At., maps answers from marginal My to residual R,. Furthermore, f4,, can be reconstructed from the set of all residuals (a-)rCy, so these residuals carry equivalent information to the marginal. Additionally, when the marginal is observed with isotropic noise y/, M,p + NN independent. As consequence,
(O,,0 o².), the corresponding
noisy residuals +,, measurement into a set of equivalent and independent noisy residual measurements.
decompose noisy marginal
Theorem Let By N(M.P, T² be a noisy marginal measurement with isotropic Gaus- sian noise and let 2r = A for each t S 7. Then noisy residual z, has distribution (BB.D o² D, IIMETNT n1)) and 2, independent of zr' for + T'.
Furthermore, let H. (A+,))sy be the matrix mapping from Vy (Et)rg-- This matrix invertible, which implies that
(og 0²1) log R.p, DDD,D II nk + log det Hyl. KET\T
(1)
TEy
Given collection of noisy marginal measurements, we can apply the above decomposition obtain a set of independent noisy residuals with proportional covariances. To reconstruct marginal answers, we can apply GReM-MLE to the residuals. Alg. 4 shows this decomposition and reconstruction. Equation (1) shows that the noisy residual measurements and noisy marginal measurements are equivalent from the perspective of finding the best data vector p by maximum likelihood, because the log-likelihood of the residual measurements differs from the log- likelihheoood of the marginal measurement by a constant log det H.I that is independent of p. and measurements of marginals are each independent. A maximum likelihood estimate of p from the marginal measurements is given by using the pscudoinverse of the measured workload to map noisy marginal measurements to data vector. The following result shows that the method in Alg. 4 is equivalent answering queries from this maximum likelihood estimate the data vector given the marginal measurements when the marginals are measured with the same noise scale.

---

Algorithm 4 Efficient Marginal Pseudoinversion (EMP)
Input: Marginal workload W, measured marginals multiset Q measurements (By)EER where 8/ M&p +N I for y E
Output: Marginal answers (M,M
1: Initialize
and k, = 0 for all T
> Track measured residuals, lazy data structure for kG
2: for E Q do
3:
for C do
4:
S = SU
hor ki +1
5:
2r,k, Atr
Extract residual measurement from Y/ >> Compute noise scale
6:
o = 0² IIKE n2
7: Σy - D.D.T
Proportional covariance
return GReM-MLE(W, S, 2) where 2 = (Zr, 1 1,..-
Theorem 3 (Efficient pseudoinversion of marginal query matrix), Let Me = (Mx)xeQ be the query matrix for multiset Q of marginals and let y = (37)rEQ be corresponding noisy marginal measurements with 1/y Map (O0 I²I). Let S S= (T Y7:7 E Q) and for each E S let Tir,i be the ith marginal in containing т. Let žr,; A - be the residual meusurement obtained from "rr and let Dr, = or, D. be its covariance where o² o² IIEE...>> AA any workload of marginal queries W, for each 7 W, the marginal reconstruction j.y obtained from Algorithm 3 on these residual measurements is equal Myy.
7kk "
Then, given
This result can be generalized to allow for differing noise scales between marginal measurements. We prove this result and discuss the generalized form of Theorem in Appendix D.
4.3 Reconstruction with local non-negativity
often possible to improve accuracy differentially private mechanism by forcing outputs to satisfy known constraints [4, 10, 21]. For our problem, true marginals are non-negative, so it is desirable to enforce non-nege non-negativity in their private estimates. To enforce non-negativity, instead of solving the separate problems in Line of Alg. 2, we solve the following combined problem over the full vector a = rew) of residuals:
min Σ (Ir) TES
An 20, Vy W.
Reconstruction of marginals then proceeds as in Line 2 of Alg. 2. The constraints in Eq. (2) ensure that the reconstructed marginals will be non negatvvaeee.. We refer to this as local non-negativiry since this problem solves for a data distribution that nen-negative for marginals in W rather than data distribution with non-negative entries.
A natural setting to apply local non-negativity ReM is under Gaussian noise with covariance Er, Dr Dr D. and of E R. Recall that marginals measured with isotropic Gaussian noise
decompose into residuals with the above covariance structure. Our proposed application of local non-negativity in the Gaussian noise setting GReM-LNN (Gaussian ReM with local non-negativity)
2r.,) K (a, 2r,1) and K = 2 D, D.T. In the GReM-LNN setting, Eq. (2) is an convex program with linear constraints. Our implementation solves this problem using scalable dual ascent algorithm (described in Appendix F) but could be solved in principle using standard optimizers, given sufficient resources [22]. With respect to the loss function (,,r,, adopting 2|rl rather than Gaussian noise scale o² a heuristic that weights lower degree residual queries such the total query and 1-way residuals more heavily than higher degree queries such as 3-way residuals. In contrast, using the Gaussian noise scale o² obtained from both ResidualPlanme and the marginal decomposition in Theorem weights higher degree residual
solves Eq. (2) for I., (a,) Σx=
7

---

queries more than lower degree residuals. When enforcing local non-negativiy,, it is beneficial for reducing reconstruction error allocate more weight to residuals that affect more marginals through reconstruction. The present choice of weights 2 for GReM-LNN, however, remain a heuristic. We discuss this point further in Section 6.
4.4 Computational Complexity
We summarize the complexity results in Table 1. Formal statements and proofs appear in Appendix E. Let S be the set of measured residuals. To understand the results, suppose that R2 is measured once, given by Zr, for each т E S. Recall from Proposition 1 that computing 2, takes ((1)))) time. This operation maps from the space of r-residuals to 7-marginals. To reconstruct an answer to the marginal query My, we apply the invertible transformation from residuals to marginals by summing over contributions for each 7 y to yield ü. = Eres:ry A,, Zr. In the worst case, this requires computing Ay,r for 2/ residuals. Then the running time of reconstructing an answer to marginal My is (Irl,, 211)) If W is a workload of marginals, then reconstructing answers to each 7 E W oeE,ew 22 The following result shows that the complexity of reconstructing an answer to marginal M, is almost linear with respect to domain size.
Theorem 4. For O, reconstructing an answer to M, o(n as n, + 0o for some i E 7.
Method
Running Time
GReM-MLE(W, S,
0 new 2/1)
EMP(W, Q, y)
O ///12,
One Round of GReM-LNN(W, S)
OlE 2/,1)
Table I: Summary of Complexity Results
GReM-MLE, given in Alg. 3, consists of two steps: estimating residual answers á, from residuals answers ž for = 1,...,k, k and each т E S, and reconstructing answers to marginal workload W. Recall that we suppose that covariance is proportional among measurements of a given residual RG, so &, can be computed in closed-form as a weighted average in O(n,) time. Then GReM- MLE takes O(E,ew 2/ time. The efficient marginal pseudoinversion, given in Alg. 4, first decomposes marginals and then applies GReM-MLE. Computing A takes ((17(n)) time, so the running time of decomposing the marginal measurements is OEΣ l1/m, where Q is the set of marginals measured with isotropic Gaussian noise. Then the efficient marginal pseudoinversion is OEE h/1m, Additionally, round of GReM-LNN, given in Alg. 6, is OEE hl1,)
Experiments
In this section, we measure the utility of GReM-MLE and GReM-LNN by incorporating them as post-processing step into two mechanisms for privately answering marginals: (1) ResidualPlanner [6], and (2) a data-dependent mechanism we call Scalable MWEM. Both mechanisms measure queries with Gaussian noise and reconstruct answers to all thy marginals for the given data domain. For the ResidualPlanner experiment, we measure residuals for all subsets of three or fewer attributes with Gaussian noise scales determined by ResidualPlanner For the Scalable MWEM experiment, we measure the total query and a subset of the 3-way marginals in the data domain with isotropic Gaussian noise and reconstruct answers to all 3-ways marginals using the efficient marginal pseudoinversion in Alg. 4. We fully describe Scalable MWEM in Appendix G.
We compare average f error with respect to the reconstructed marginals of the base mechanism to post-processing with GReM-LNN and two heuristics that enforce non-negatyvity by truncating negative values to zero (Trunc) and truncating to zero then rescaling (Trunc+Rescales For the Scalable MWEM experiment, we additionally compare well-studied reconstruction mechanism Private- PGM [12]. We run these methods on four datasets of varying size and scale, Titanic [23], Adult [24].

---

Titanic
Adult
10a
Average Workload Error (t,)
10a
10
10
Salary
Nist-Taxi
10a
10a
10P
10-1
10
10"
10a
10-1
10a
10A
ResidualPlanner
Trunc
ReMM-LNN
Figure 2: Average & workload error on all 3-way marginals across five trials and privacy budgets e E {0.1, 0.31, 3,166,, 10} and ā = 1 x 10 for ResidualPlanner.
Salary [25], and Nist-Taxi [26], and various practical privacy regimes, E {0.1, (,3,, 1,3.16 and x 10-3 For each setting, we run five trials and report the average error of each method as well as minimum/maximmm bands. Additional details are provided in Appendix H.
10}
5.1 ResidualPlanner Results
Fig. 2 displays results for the ResidualPlanner experiment. Across all privacy budgets and datasets considered, GReM-LNN significantly reduces workload error on the reconstructed marginals com- pared to ResidualPlanner. Averaging over all settings and trials, GReM-LNN reduces ResidualPlanner workload error by factor of 44.0x. With respect to the heuristic methods, GReM-LNN reconstructs marginals with lower error than Trunc across all privacy budgets and datasets. Except at the highest privacy regime considered (e = 0.1) on Titanic and Salary, GReM-LNN yields lower error than Trunc+Rescale. Averaging over all settings and trials, GReM-LNN has lower workload error by factor of 17.6x compared to Trunc and 3.2x compared to Rescae. Note that GReM-MLE omitted from Fig. since ResidualPlanner is the maximum likelihood reconstruction for its measure- ments. Appendix reports results for this experiment with respect to le workload error, which are consistent with the present findings.
5.2 Scalable MWEM Results
Fig. 3 displays results for the Scalable MWEM experiment for rounds of measurements. Observe that Scalable MWEM runs for the settings considered, which would be infeasible for the original MWEM mechanism due to large data domains. Of all methods considered, Private-PGM. yields the greatest reduction in workload error in settings where it ran; however, Private-PGM failed due to exceeding memory resources (20 GB) at 30 rounds on Adult, Salary, and Nist-Taxi in all trials. In Appendix I, we report the settings in which Private-PGM successfully ran across 10, 20, and 30 rounds of Scalable MWEM.
With respect to GReM-LNN, the findings from the prior experiment agree with the present results. Across all privacy budgets and datasets considered, GReM-LNN significantly reduces workload етгог on the reconstructed marginals compared to Scalable MWEM. Averaging over all settings and trials, GReM-LNN reduces Scalable MWEM workload error by a factor of 12.3x. Averaging over all settings and trials, GReM-LNN has lower workload enror by factor of 1.1x compared to Reunc+ Note that we suppress results for Trunc due space. Appendix reports results for this experiment with respect to E workload error, which are consistent with the present findings.

---

Titanic
Adult
10a
Average Workload Error (2,)
101
10
Salary
Nist-Taxi
10a
10
10c
10-4
10"
10a
10-1
10a
10
Trucc+Rescale
GReM-LNN
Private-PGM
Figure 3: Average & workload error on all 3-way marginals across five trials and privacy budgets e E (0.1, 1,3.16, 10} and d = 1 x 10-9 for Scalable MWEM with 30 rounds of measurements.
6 Discussion
We develop ReM, a method for reconstructing answers to marginal queries that scales to large data domains. We also introduce tractable method to incorporate local non-negativvty that significantly improves reconstruction quality. Finally, we show that ReM can be used to improve the existing query answering mechanisms ResidualPlanney and scalable version of MWEM.
Limitations. Many data-dependent query answering mechanisms also generate synthetic data. In some cases, practitioners utilize these mechanisms primarily in order to use the synthetic data for downstream tasks such as training a machine learning model [8]. For those users, the fact that ReM does not generate synthetic data would be an important limitation. A broader limitation, which common to many methods in this field, is lack of support for continuous data. Marginal and residual queries are only defined on discrete domains so continuous attributes need to be discretized.
Future Work and Broader Impacts. While developing effective algorithms for preaeccirre data analysis is generally beneficial, it is known that these methods can lead to unfair outcomes [29]. One direction for future work is to further understand the fairness properties of the methods we present and how to mitigate any undesirable outcomes. Another direction for future work is further understanding the weighting scheme used in GReM-LNN to apply local non-negativity. Preliminary experiments show that weighting lower-order residual queries more highly in the loss function yields reconstructed answers with lower workload error as well as faster and more reliable convergence of the optimization routine. In general, the relationship between residual weights in the loss function, optimizer convergence, and reconstruction quality is not well understood.
Acknowledgments and Disclosure of Funding
This work supported by the National Science Foundation under grants CNS-2317232 (Kifer); CCF-2046235 (Musco); and 1744949 and DB1-2210979 (Sheldon).
and
References
[1] John M Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, et al. The 2020 census disclosure avoidance system topdown algorithm. Harvard Data Science Review, 2022.
10

---

[2] 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 JJGMOD-SIGACT-SIGAAN
symposium on Principles of database systems, pages 123-134. ACM, 2010. doi: 10.1 14/0
[3] Chao Li and Gerome Miklau. An adaptive mechanism for accurate query answering under differential privacy. PVLDB,
2012.
[4] Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24(6):757-71,, 2015. doi: 00007//00778-005--09988..
[5] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavaijhala. Optimizing error of high-dimensional statistical queries under differential privacy. Proceedings of the VLDB Endowment, (1(10): 111111201111911 2018. doi: (0.14778/323/5513323 1769.
[6] Yingtai Xiao, Guanlin He, Danfeng Zhang, and Daniel Kifer. An optimal and scalable matrix mechanism for noisy marginals under convex loss functions. Advances in Neural Information Processing Systems, 36, 2024.
[7] Ryan McKenna, Brett Mullins, Daniel Sheldon, and Gerome Miklau, Aim: An adaptive and iterative mechanism for differentially private synthetic data Proc. VLDB Endow, 15(11): 2599-2612, Jul 2022. ISSN 2150-8097. doi: 1011478/551199.351181 URL https: / //doi. org/10...11.
[8] Jun Zhang, Graham Cormode, Cecilia M. Procopiue, Divesh Srivastava, and Xiaokui Xiao. Privbayes: Private data release via bayesian networks. ACM Transactions on Database Systems (TODS), 42(4):251111 2017. doi: 10. 155/3134444 URL, https://///di org/ 1145/ 3134428.
[9] Terrance Liu, Giuseppe Vietri. and Steven Wu. Iterative methods for private synthetic data: Unifying framework and new methods. A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[10] Sergul Aydore, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Ankit Siva. Differentially private query release through adaptive projection. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 457- 467. PMLR, 18-24 Jul 2021. URL ptttps://proceedingg html.
mlr press press/v139 vvt.v/v1////////// h1139//yyoe211.....
[11] Giuseppe Vietri, Cedric Archambeau, Sergul Aydore, William Brown, Michael Kearns, Aaron Roth, Ankit Siva, Shuai Tang, and Steven Z Wu. Private synthetic data for multitask learning and marginal queries. Advances in Neural Information Processing Systems, 35:18282-18 18295, 2022.
[12] 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, 2019. URL http:://ttcce/e
mlr www.:mml..p.s.... prt.ess/v/7/nnccmmaaa htt////cenn19... html.
[13] IN Darroch and TP Speed. Additive and multiplicative models and interactions. The Annals of Statistics, pages 724-733 1983.
[14] Stephen E. Fienberg and Alessandro Rinaldo. Computing maximum likelihood estimates in log-linear models. Technical report, Technical Report 835, Department Statistics, Carnegie Mellon University, 2006.
[15] Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher
J. C. Burges, Léon Bottou, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems
2012. Proceedings of meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 2348-2356. 2012. URL https: /twpe//ee/o........//ooep.cessep wwwpeediinnnnnuuiiiing nwwrinsuu.... ctt.isss..pp...pe.cco..oeeeeeeec cttccc//pppae/e pptpp///p12//aaaaaa D0B8-330445cdd77caffaaa332288883 Abstract.

---

[16] Cynthia Dwork, Frank McSherry Kobbi Nissim, and Adam Smith. Calibrating noise to sensitiv- ity in private data analysis. In TCC, pages 265-284, 2006. doi: 10.29012/jpe.v7133 v.3..400.
[17] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Found. and Trends in Theoretical Computer Science, 2014. doi: 10.1561/0400000442
[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, 1 11(3), 2021.
[19] Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. Data synthesis via differentially private markov random fields. Proceedings of the VLDBB Endowment, 14(11):2190-220) 2021.
[20] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Hdmm: Opti- mizing error of high-ding dimensionl statistical queries under differential privacy. arXiv preprint arXiv:2106. 12118, 2021.
[21] 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 on Theory of computing, pages 351-360, 2013.
[22] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[23] Thomas Cason Frank E. Harrell Jr. Encyclopedia titanica.
[24] Ron Kohavi et al. Scaling up the accuracy of naive- classifiers: A decision-tre tree hybrid. In Kdd, volume 96, pages 202-207, 1996.
[25] Michael Hay, Ashwin Machanavajihala, Gerome Miklau, Yan Chen, and Dan Zhang. Principled evaluation of differentially private algorithms using dpbench. In Proceedings of the 2016 International Conference on Management of Data, pages 139-154, 2016.
[26] Gregoire Lothe, Christine Task, Slavitt Isaac, Nicolas Grislain, Karan Bhagat, and Gary Howarth. Sdnist: Benchmark data and evaluation tools for data synthesizers. 2021.
[27] Lucas Rosenblatt, Xiaoyan Liu, Samira Pouyanfar, Eduardo de Leon, Anuj Desai, and Joshua Allen. Differentially private synthetic data: Applied evaluations and enhancements. arXiv preprint wrXiv:2011.055371 2020.
[28] Yuntao Du and Ninghui Li. Towards principled assessment of tabular data synthesis algorithms. arXiv preprint arXiv:2402.06806 2024.
[29] David Pujol, Ryan McKenna, Satya Kuppam, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. Fair decision making using prrtecy-protected data. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 189-199, 2020.
[30] Brigitte Plateau. On the stochastic structure of parallelism and synchronization models for dis- tributed algorithms. In Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systems, pages 147-154, 1985.
[31] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016. doi: 10. 10.10077977--3662-5568 1-4_24.
[32] Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differ- ential privacy. In NewrIPS, 2020. URL https://proceeeddnggg wwwpiiiinnnnnn.uuineeeeeee 0aat//8888.adda00000082855552111
www.nuue...ppappeeeeeeeeee cccpappr//02// html.
[33] Yingtai Xiao, Zeyu Ding, Yuxin Wang, Danfeng Zhang, and Daniel Kifer. Optimizing fitness- for-use of differentially private linear queries. Proceedings of the VLDB Endowment, 14(10): 1730-1742, 2021.
[34] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, 2007. doi: 10.1 00.114//09023662200222
12

---

[35] Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analyties. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 421 457, 2021. URL htll.httss://proee http:p::///poreeeess.......... pres.press/veee www.ll..preee/e///eeeeeeeee wet11///e//21aaa.aaaaaaa html.
[36] Jerzy Baksalary and Oskar Maria Baksalary. Particular formulae for the moore moore-penrose inverse of columnwise partitioned matrix. Linear algebra and its applications, 421(1):16 2007.
13

---

A Kronecker Products
Kronecker products are convenient way represent highly structured matrices. Let A be an
d1,1
d1,na
X matrix A =
and B be x matrix. Then the Kronecker ama
amail
01 B
a1,a, B
product of A with is an Malhi X Ratty matrix given by A & B
Oma.1
Kronecker products provide a compact representation of matrices by representing exponentially-many entries of @ B with linearly-many entries in and B. For the Kronecker product of a sequence of matrices A A1.-.-3 Ad, the notation
A A Aa
The Kronecker product is associative, so pairwise products can be taken in any order.
Kronecker products additionally possess useful algebraic properties. Let (-) denote Moore-Penross pseudoinverse.
Proposition 3. (Kronecker Product Properties) Let A 8 1is A, and B 0 Bj. Then the following properties hold:
1. A 2 0-=1 AT.
A 8 1
If A; and B; are compatible for multiplication for 1,...,d, d, then AB Di A,B.
There efficient algorithms for matrix-vector multiplication utilizing Kronecker structure such as Alg. 5. Let i A, be Kronecker structured matrix where A, matrix of size a; b, so that A has size a x with I and b = I b;.
Algorithm 5 Kronecker Matrix- Vector Product [20, 30]
Input: Matrix A 8 -1 A,, vector a, b SHAPE( A,)
I b; 21
for i = l...., E do
RRESHAPE(Z,, t/b.)
r r =r/b///;
F4+1 (E
return T8+1
Differential Privacy
Let us begin by introducing useful variant of differential privacy: zero-concentratee differential privacy (zCDP).
Definition Cero-Cooneettrated Differential Privacy: [31]) Let M X + y be a randomized mechanism. For any neighboring datasets p. p.p' that differ by at most one record, denoted p ~ p', and measurable subsets S C ): if (.(M)))) S p7 for all y E (1, 20) where D, the ReReyi divergence between distributions M(p), M(p'), then M satisfies p-ZCDP
While (e, 8D- a more common notion, often more convenient to work with <CDP. There exists conversion from zCDP to (D..
14

---

Proposition 4 (zCDP to DP Conversion; [32]). If mechanism M satisfies p-zCDP, then M satisfies (C,6)-DP for any and mina>1 exp((a-1)(o
Next, we introduce two building block mechanisms. An important quantity in analyzing the privacy of a mechanism sensitivity. The & sensitivity of a function : X' + given by As(f) maXp=p' [1](p) f(x'))lx If ff is clear from the context, we write Åk.
Proposition 5 (zCDP of Gaussian mechanism; [31]). Let W be an m X workload. Given data vector p. the Gaussian mechanism adds i.i.d. Gaussian noise to Wp with scale parameter a i.e. M(p) = Wp + o (W (O, where I is the m x m identity matrix. Then the Gaussian Mechanism satisfies 2n 2 -CCDP.
Proposition (zCDP of correlated Gaussian mechanism; [33]). Let W be an workload. Given data vector the correlated Gaussian mechanism adds Gaussian noise to W p with covariance matrix E i.e., M(p) = Mp (N0, Σ). The correlated Gaussian mechanism satisfies 3 2zZCPP where Y is the largest diagonal element of M M.
Proposition 7 (zCDP of exponential mechanism; [34, 35)). Let 0 and Score, X + R. be a quality score of candidate r E R for data vector p. Then the exponential mechanism outputs candidate r E R according to the following distribution: Pr(M(p) = r) o exp ( Score,(p))
The exponential mechanism satisfies -2CDP.
Adaptive composition and post-processing are two important properties of differential privacy that allow to construct complex mechanisms from the above building blocks. Let us state these results for zCDP.
Proposition (zCDP Properties; [31, 35]). zCDP satisfies these two properties of differential privacy:
1. (Adaptive Composition) Let M, X - V1 satisfy Pı-ZCDP and M2 : X x V - V/2 satisfy
P2-zCDP. The mechanism p - M2(p,Mi(p)) satisfies (pi P2)-xCDP.
(Post-processing) Let Mi + satisfy p-zCDP and f y - Z a randomized algorithm. Then M: X Z f MM satisfies p-zCDP.
C Relationship between Marginals and Residuals
In this section, we prove Proposition I, which provides relationship between marginals and residuals. Before proving this result, let us consider residual workloads well the subtraction matrix D(ay-
Let us state some properties of residuals.
Proposition 9 (Residual Properties; [6, 13, 14]). Let Q be the set of all tuples of altributes for given data universe X.
1. R2 is an m, X matrix with full row rank.
Ry Rl are mutually orthogonal for T + i.e. R2 RT 0.
3. Rr, Mf are mutually orthogonal for & r' i.e. R, 0.
(Ry)re spans R".
Lemma Data vector p E R can be decomposed uniquely as follows: p Ereg RT vy for
e, E m..
Proof. Let Pr R$ R.p be the projection of p onto the row-space of R,. By Proposition p p= E Let U, Rm- be such that p- = R. Ur. Since R, full row rank, vy is unique. O
Now, us consider Diy Recall that D(a) an ni
x ni matrix given by
-1 1
0
0
D(g)
1
15

---

The pseudoinverse of (a)) is known in closed-for
n2
7k
2
1
7kk
2
1
D (R)
1
7
-1
-2
(mi 1)
=(/ms)(lauu ny Ck),
T&k 17
T2p
where uk
and Cs. is the vg x n
lower triangular matrix of ones.
Continuing the example from Fig. 1,
1
0
1 -1 1
D(1)
1 -1
3
3-1
-
Proposition 1. Let Rs (Re fres be a combined workload of residual queries for all 5 in collection S C 2/4,, where the individual mulrices Rr are stacked vertically, The size of Rs is where m = Eres my. Then for any (2+)rES E R.m and any 7,, holds that
D
KET
My Σ
where Ay, =
X
(P/ne)
1x
k E
for T En.
TES,TE7
k: 7
The matrix A has size Thy my and maps from the space of T-residuals to the spuce of -mmarginals. The rumning time to compute 2 is ((r(nn))
Proof of Proposition I. First note that R is the pseudoinverse of a block matrix. general the pseudoinverse of vertical block matrix involves the pseudoinverse of each block multiplied by projection matrix [36]. this case each block a residual query, as discussed Proposition 9, these query matrices are mutually orthogonal so the pseudoinverse R has the form (Rt) (Rt) Here, the combined query matrix Rs constructed by stacking the blocks R, vertically and the combined pseudoinverse R stacks the blocks R, horizontally. Given this block structure of R we can write
R 2
Σ R$ TES
M, M,
(3)
Another relevant property of residual queries given in Proposition that R.M for & r'. When we drop these orthogonal queries from the summation, we get R5 ErES.rsy M, 2r. When computing the product M,, R, several properties of Kronecker products given Proposition 3 relevant. The first is that (A 2 B)+ AA+ B+. Applying this property gives
Dt
KET &
R
The next property is that when when A and B both have compatible Kronecker structure, AB X A; Both M., and RT have compatible Kronecker structure so we can write
DD Ig
KET
(k)
M.R.
(1I)²
KET
(5)
k=1
1 (II)
k
16

---

To evaluate this, notice that (1 the equation above we get
1x
= 1 and 1 (12/ng) = 1. Plugging this into
d
D
KET
=
-
1x/TER
k kE> k
(6)
A=1
Finally, this gives the full result that R3 Eres,rcy A
We prove the time complexity result for 2, in Appendix E.
D ReM Proofs
In this section, we prove results related to ReM from Sections and 4.
Theorem 1. Suppose & minimizes (ac,) over R for each E and let (ât)res- Then Alg. outputs P.y = M, where = Rg is a global minimizer of the combined loss function ErEs Ly (R.p) over IR".
Proof.
Suppose å minimizes L, for all and let R2āā. Then for any p E R
IL-(RD)) LR
I.((ā)) S 5.>ss<nn II-(RD))
TES
TES
TES
TES
We will justify Equality (*) below. The inequality holds because à, minimizes T.y Thus, Equation (7)
shows that minimizes the combined loss Eres L, p).
To justify Equality (+), first observe that Rs Rsllzā á because Rs has full row rank and thus RsR = I. We can Rs has full row rank by Proposition 9: each block of rows corresponding to residual has full row rank and these blocks are orthogonal. The equality R2 R, â å, is obtained by selecting the block of rows corresponding residual from the equality Rs Rš â.
Lemma 1. For T C the residual R2 can be recovered from the marginal My as
D(t
KET
Rg = Mr where A
k E
1
k & ?
Proof of Lemma J. Recall that we defined A,, = M, R Then A = R2 M Observe the following:
D DIyjIR
KET
A+ At. M,
k Ik
k kE
1=1
1
ko k& ?
D(s) EET T
1
Rr
Theorem 2. Let Vy N(M,p,o' be noisy marginal measurement with isotropic Gaus- sian noise and let Zr = At,, for each t S 7. Then noisy residual žy has distribution N(R.p, D, IREAr my) and 2, is independent of 2 for $ T'.
17

---

Furthermore, let H = (A be the matrix mapping from By to (2+)+ This matrix is invertible, which implies that
log LygN o
LoggN(2 Rip, DDDD II ns + log det Hyy KEYAT
(1)
Proof of Theorem 2. Since yr NM, 021) and ār -/r, standard properties of normal distributions give that 2, M. 0² A (A By Lemma 1, the mean equal R. p. as stated. For the covariance
DiRyDis (K)
EET 1e kE
A (A
1 1k
k 847
Dis)
D
EET
II ni KEY
1
k $
D,D, II n
KEY\E
SO the covariance is o² DDD IK 7k. stated.
For # r' the vectors 2y and 2,r are jointly normal with covariance (A We will show that A (A.,.r) T is matrix of zeros, the covariance matrix is identically zero and the vectors are independent. By the Kronecker structure,
Doa D DON)aE 1
KeTRT kET
(K)
A (A+
7,77)
KET
Arn 1
k k (TUT)
&
Observe that Dis) 1 = 0 is a vector of zeros because the rows of D(k) sum to zero, and similarly 1. DT, is a row vector of zeros. Thus, any k in the symmetric difference (T' (T) (T) (r \ \r) will contribute an all zeros matrix to the Kronecker product and cause matrix. But there must be at least one the symmetric difference because * r'. This proves that the covariance matrix is identically zero, as desired.
to be an all zeros
We will next show that the mapping H,y invertible. H,, is a matrix with blocks A for each t C 7, stacked vertically, and n, = I ng columns. From the definition the block A we can see has mh = I (ni - 1) rows and of full row rank because D(k) is a full rank matrix with nig 1 rows and the other matrices in the Kronecker product have only one row. We showed above that (A ) = 0 for r * T', which means that the blocks of H,, have mutually orthogonal rows, and combined with the fact that each block has full row rank this means that H,, has rank equal to the total number of rows. This number of rows is Σrg₁ m. Σrsr likr (nq - 1) = IIkey Thk nyy
which equals the number of columns, and therefore H, invertible?
Now, given what we have shown so far, we will write two different expressions for the log- ogg-robbbbility density function log (z)) where (z.) First, we have already derived the joint multivariate distribution of z, which, due to independence, has log-density
logp=(z)= = Σ log. log.V(2r o D.
II mk RETRT
+5x
"To see that E,cy IL, (n - IukE observe that n,, = IINe, counts the number of ways to
map each & 7 to value i (1...., nu ). Equivalently, we may consider selecting subset 7 S 7, assigning each & E r to the value 1, and then assigning each & & to one of the remaining values in {2...., nx The number of ways to do this is Erg, Ilaer (n= 1) IIxey n4.
18

---

Second, because H. for the multivariate normal random variable yy, the change of variable formula for probability densities gives that
log (z(2) = logN((s: Myp, o²1) log det Hyl-
Equating these two expressions gives Equation (I), which completes the proof.
Theorem 3 (Efficient pseudoinversion of marginal query matrix). Let Me (M,) be the query matrix for multiset Q of marginals and let = (U>)ee be corresponding noisy marginal measurements with Yy Mrp + (O, o I²)). Let S = (T 7 E 2} and for each T let "tr be the ith marginal in Q containing Let Zr, A A., be the residual measurement obtained from "Fr, and let Er,, = D,, be its covariance where o².; = o² IIKETE.. 7g. Then, given any workload of marginal queries W, for each y E W, the marginal reconstruction (ay obtained from Algorithm 3 on these residual measurement is equal to My
Proof. By standard properties of the pseudoinverse, Myy is the unique vector that minimizes SE(p) || 21l and is in the span of Mo. We will show that the vector R & satisfies both properties, where à (år)res is constructed in Algorithm 3, and thus Rğā May. Then, by Proposition 1, the reconstructed marginal (a in Algorithm is equal to M, a and hence also equal to M. Mo as claimed.
We will first show Rğā minimizes SE(p). Observe that the SE(p) is equivalent to the negative log- likelihood (p) of the marginal measurements y:
SE(p) Mop y11
= Σ |M,P- - 1:11 7EQ
-20² Σ No, + const.
7EQ
= 20 C, (p) + const.
Therefore SE(p) and (p) have the same minimizers. Then, by Theorem 2,
Cy(p) =
- log (W
Σ
log log.N(At. R.P, o² II ny D,D.)) const. kEA
rS
log ( R.P, D.DDD..) + const.
Cx(p)
where in the final line we rearranged terms using the notation of the theorem statement.
Therefore, SE(p), and (p) all have the same minimizers.
Furthermore, (p) decomposes over residual measurements as (p) = Eres (R,, where [.,(,,) Σ log log.N ar, term separately. Algorithm finds å, minimize I., (a,, for each r E S using inverse variance weighting. Then, by Theorem the vector R is a minimizer of (p),, and therefore also minimizer of SE(p).
Therefore, Theorem allows us to minimize each
remains to show that Ršā E row(Me). This is true because Ry E col(R = row row(Rs) S r.. The final inclusion is true by Lemma 1, since for each 7 E S we have R2 = A M, for some Q.
In fact row(Hs) row(MQ) but only need the inclusion.
19

---

Let us now discuss generalization of Theorem 3 to the case where noise scales vary across marginal measurements.
Let Me rE be the query matrix for multiset Q of marginals and let y (Un)ee be corresponding noisy marginal measurements with 1/- = Map + ( o²I). Define the scaled query matrix for Q as Ve = (V>)eE where Vy
Theorem 5.
1 M, and the scaled marginal 0y
measurements as = (14) where E, - Let = IT E7: E 2} and for each T E S let "r, be the ith marginal in 2 containing T. Let ZT, = - be the residual measurement obtained from "tr,i and let Σ,,; = D. be its covariance where o²,, = o² "INE Tik- Then, given any workload of marginal queries W. each y E W, the marginal reconstruction P4y obtuined from Algorithm 3 on these residual measurements is equal to M,V.
The result follows due to the following Lemma, which shows that V is an MLE for p given the noisy marginal measurements y.
Lemma 3. Let M = (May Yブ-1 be the query matrix for marginals Q= (7i,....77. which may include duplicates, and let y = (yr;)r=1 be corresponding noisy marginal measurements with 00, I)
I). Define the scaled query matrix as VQ = (Vn,)ī== where Va, 1 _M,,, 1
3r; =
ong and the scaled marginal measurements as (u=)) where Un, oag Dr:" Then V0+ u a MLE of with respect to noisy measurements y.
Proof. The log- likelikeliood of data vector p under noisy marginal measurement yhy can be written as M1 + Cx2
Cy., (p)
20 ||
where Cy2 is a constant. Since the noisy marginal mcasurements are independent, the log- likeliidd of data vector p under noisy marginal measurements is given by
2, - 1 Σ o2
10,, - My, +
j=1
where e a constant. The vector á is an MLE of p under noisy marginal measurements y if and only if f minimizes the loss function
(p(
Σ
1
Mr,p112
02
j=1
-(21)
2
Uou -
Mr.
P
Trys
0
j=1
||
V
||0
Vopl2-
Since v0 e minimizes (p),, is an MLE of p under noisy marginal measurements y.
E
Computational Complexity
In this section, we analyze the computational complexity of applications of ReM under Gaussian noise. We state and prove the results discussed in Section 4.4. Let us first prove two useful lemmas regarding the time complexity of Alg 5 for multiplying the Kronecker matrix A = Ø A, by vector Recall that A, has size 0; b; and A has size a x with I a, and b I b.
Lemma 4. At iteration i, Alg. 5 has the following time complexity:
(a) if A is arbitrary matrix, iteration i takes O aj Ih bn) time.
20

---

(b) A; D then iteration i takes O O aj -h bn) time, where b, =
(c) if A. = Dayy. then iteration i takes O(I) 0, 1hh bn) time, where O; = n2
Proof. At iteration i of Alg. 5, A, is multiplied by a matrix Z with size bj (II 1 bn). Then each row in A; requires b; [[]= -
aj II bm) = (II)=i ay Ih bR) scalar multiplications. Since A; has o; rows, this yields (II) IIh=;bb) bn) multiplications over all rows. This proves (a).
Suppose A; (iyy Recall that Diy (1/n))(lug nk.C). We claim that computing (()) for any vector takes ((us) time. C&U is cumulative sum of the elements of and un is dot product, both of which take ((nx) time compute. The remaining steps cost 2(nz. - 1) multiplications and nig -1 sums. Thus each column of Z can be multiplied by A; in O(na) time. Since Z has (IT a Im= bn) columns, computing A,Z takes (b, (b. aj II bs)) OII Suppose A, = (nyy For vector u. Day is the difference consecutive elements of v, which takes (mx) time to compute. Thus each column of can be multiplied by A with n - operations.
1 0z II. b bk) time, where b; n 1. This proves (b).
Since Z has (IT)=] oj Ih bn) columns, computing A,Z takes O II [[ aj IT bx)) O 03
I1 bx) time, where a, ni - 1. This proves (c).
Lemma 5. The following hold for Alg. 5:
(a) If a; by and either A, (ik) b, 1 i .,...,............... l, then Alg. takes O(a E) time.
(b) Ifa: by and either A, (()) or a; 1 1,..., ,, then Alg. 5 takes O E) time.
Proof. Applying Lemma 4, if A; = Dity then iteration i takes O aj Ih bn) time, and, b, = 1, then iteration takes O Ih 6n) time. We can bound these terms by (II =1 a4)) = (a). Summing over all iterations of Alg. 5 yields O a) = O(a E). This proves (a).
A; = (a). then iteration is OII,,- aj Ih bn) by Lemma 4 (c). If a; = 1, then iteration
i ( aj bx) by Lemma (a). We can bound these terms by ( bn)) = O Summing over all l iterations Alg. 5 yields O 6) = O(b E). This proves (6).
Theorem 6. Let W be workload of marginals. Then
(a) Reconstructing an answer to marginal Ma for E W takes O (1r (/11)) time.
(b) The time required for reconstructing an answer to marginal My, for E W is o( any > 0 as n. + 30 for some T..
(c) GReM-MLE(W,, S, takes O(E 2111,2171) time.
(d) EMP(W, Q. y) takes OlE 22112221) time.
(e) GReM-LNN(W, z) takes O O 2111) time per round.
Proof. Let us first consider the running time of A 2r for some C Recall that A,r can be written follows:
Dt (1)
KET
Ar,
(Von)
k kEY
KEY
Since Ay.r satisfies the conditions of Lemma 5 and has n, rows, computing A,, takes ((1(mn)) time. Recall from Proposition that reconstructing answer to marginal M, is given by
21

---

Eresirst Ay, The number of terms in the summation is at most 2hl, so the total running time reconstructing an answer to My (11l),,)1))) This proves (a).
For (b), let > O and consider the following quotient:
17| 2/1
2/m 2/
17/n
ny
Il, nf
Taking the limit as + co, the quotient tends to zero and we obtain the desired result.
With GReM-MLE, each residual query R S have multiple measurements yr,1, M, but with proportional covariances. For each T E S, we combine the measurements using inverse variance weighting obtain Üt,, We then reconstruct the marginals M, for 7 E W using the residual answers & for S. By (a), the running time is OEΣ 17/m22177). This proves (c).
The efficient marginal pseudoinversion, given in Alg. 4, first decomposes marginals and then applies GReM-MLE. Let Q be the multiset of measured marginals and W be the workload of marginals to answer. Let W denote the downward closure of W. We assume that Q is consists of elements of IN and each E W appears in Q at most b times. For each Y E Q, we decompose the marginal measurements into residual measurements by computing A for each
7. By Lemma (b), computing A M/, takes ((71/n)) time. Then the running time of decomposing the marginal measurements is O (111,,211)) From (c). the running time of GReM-MLE is eeEn 211, Given that the running time of decomposition is most multiple of the running time of GReM-MLE, +fEne 2/1))) This proves (d).
Let us turn to the rumning time of GReM-LNN, Let W be the downward closure of workload W. The dual ascent algorithm for GReM-LNN (Alg. 6) consists of three steps each round requiring matrix multiplications: computing à for S, computing å,, for unmeasured T' E W S, and reconstructing answers to marginals M,, for E W.
First consider the case where E S. Recall that in this case à, = +Ehn Kit) ' (E Ki,
Σn AT 7.5 >n) where Kr,; = =.? We can rewrite á, follows:
-1
(
Eo 42
Σ 72
Σoz2yr: 72r
+
D.
D.
Σ D A. 422
The left summand requires no matrix multiplications and does not depend on X. Then computing
A Xy takes ((7(nz)) time. The right summand is obtained by computing , Xoy for each 2 Then computing a, for r E S takes O h (2)) time.
Now consider the case where Wt S. Then á -A/2) Arrr) -E AT Ay. As with 1.r
the prior case, the desired term requires computing AT, Aoy for each 2 т. Then computing å for E Wt \ S is O(
Combing these results, computing & for W is O(E Σ each E W, there are 2/ terms in the summation. By indexing the summation in terms of we obtain that computing answers marginals My for 7 W. By (a), the running time is O hlm,) This proves (e).
Observe that for
O(E, ln/m,,2//) The remaining step GReM-LNN is to reconstruct
GReM-LNN Implementation
Recall that GReM-LNN solves the following convex program:
min ΣΣ (a, 2n,i) T (ar zr,)) s.t. Σ
An 20, Vyw
(8)
TES
T
22

---

Algorithm 6 GReM-LNN Dual Ascent
Input: Marginal workload W, residual workload S, residual mcasurements 2, rounds T, step size s,
Lagrangian initialization A, regularization weight 1)
1: Initialize xy = À for Y E W
2: fort = 1,..., do
3: Set ae (E K7s) -1 (E K7, Enzr ArrdNN for
4: a, = - 1/22 Arr)) (E>2 ATr for W w8
5: Calculate (4y (ax) = EF Ay for y WW
6:
Update X, min + (a)(a) fory EW
for K,,; = 2/7 D.D Observe that the program in Eq. only depends on unmeasured residuals in W through the local non- non-negannnne negativity constraint. To make this problem more tractable and the solution more stable, we introduce regularization term limit the contribution of unmeasured residuals to reconstructed marginals:
min
Σ
E(a, (ar - 2,,,) K7 (ar - 27,)+ +
Σ NEWEIS
|
TES
(9)
S.C. Σ
Ar 20, Vy EW
Note that the introduction the regularization term in Eq. (9) is only relevant the underdetermined case, since, otherwise, W C S. To solve the program in Eq. (9), we use an iterative dual ascent algorithm described in pseudocode in Alg. 6.
Let us now show that Alg. 6 is correctly specified. Let us denote the objective as f(a) = || and the constraint as u(a)
Eres Ete, (ar 2r,1) K (ar zr,i) + 1 Evewass
(a>(a))eew= = =EErs a 2 Then the Lagrangian function is given by
((a,A)= [(a) + m(aa
= -Σ>
(ar - zn,)
K (e 27,) +
Σ PEWAS
A1 +
Σ XT 7EW
Σ +
AgreK
TES 1=1
where A = new is the dual variable or Lagrangian multiplier and is constrained such that À 0. The dual function is given by g()) = min, L(a, A) and the dual problem is given by max g(A). Under suitable regularity conditions, the optimal value of the dual problem is equivalent the optimal value of the primal problem. We can solve both by maximizing the dual function to obtain X and then minimizing the Lagrangian E(a,A*) with respect to obtain a".
We can solve for each a; in closed form for E WN Minimizing the Lagrangian L(a, X*) with respect to corresponds to minimizing an unconstrained quadratic objective and can be solved separately for each r. To see this, let us fix À and solve for the critical point of L(a, A). If E S, then gradient of L with respect a, is given by
k
V C(a
Σ K - -2,)
72T
Setting this to zero and solving for a; yields
h-_
K T. Zz,
Σ A.pA.)).
1=
1=1
72
23

---

return noisy answers ((n))ew, noisy measurements, y Algorithm 7 Scalable MWEM
Input: Marginal workload W, privacy budget (e, 6), initialization parameter a
1: Choose p such that mina>1 exp((a-I(ax-e)) (1 2)² =
2: Set o². 2ap (1-a)p
3: Initialize measurements y (Mp + Eo) with Eo ~ -N(0,, o) and multiset Q = (0)
4: Initialize new = EMP(W, 2,
5: for = .,..., T do
6: Select " with the exponential mechanism using
(-=aee budget according to 22
Score(p; 7: Y) 1I i Vy E W
7: Measure y/, -M & where & _N 22) and set Q U th}
8: Reconstruct (Å-)zew = EMP(W, 2,y)
Now, suppose T E W \ S. Then gradient of L with respect to or is given by
Va, f(,, A) 2na, ATr + Σ A Ayrd
Setting this to zero and solving for a² yields
of = -/27 A AT ATT
Σ A.T ATTA,)" 72
To update A, we set X = min(A + 41((a)), ),00
0} where 1 > 0 is the step size. This can be seen as projected gradient ascent on g(A) since ula") VxL(a", A) Vxg(A).
G Scalable MWEM with pseudoinverse reconstruction
The multiplicative weights exponential mechanism (MWEM) [15] is a canonical data-dependent mechanism that maintains model p of the data distribution p that is improved iteratively by adaptively measuring marginal queries that are poorly approximated by the current model p. MWEM has served as the foundation for many related data-dependent mechanisms. A limitation of MWEM-style algorithms is that representing P. even implicitly, does not scale to high-dimensions without adopting parametric assumptions. In this section, we propose an MWEM-styl Myyylee algorithm called Scalable MWEM (Alg. 7) that employs standard reconstruction approach, the pseudoinverse of the measured marginal queries, but scales to high-dimensional data domains.
data domains
In general, the pseudoinverse is infeasible as reconstruction method for large data domains. Com- puting the pseudoinverse Q+ of arbitrary query matrix Q scales exponentially in the number of attributes and linearly in size of the data vector. Morcover, even storing the reconstructed data vector á Q* y from noisy answers y memory presents limitation in practice. Scalable MWEM overcomes this computational hurdle by measuring marginals with isotropic noise and utilizing the efficient marginal pseudoinverse (Alg. 4).
Scalable MWEM initializes by using predetermined fraction of the privacy budget to measure the total query i.e. the O-way marginal that counts the number of records in the dataset. Let W be a workload of marginals e.g. all 3-way marginals. Then, for a fixed number of rounds, Scalable MWEM privately selects marginal 7 W that is poorly approximated by the pseudoinverse of the current measurements using the exponential mechanism. The selected marginal is measured with isotropic Gaussian noise and utilizes the efficient marginal pseudoinverse reconstruct answers to marginals in W. Being a full query answering mechanism rather than just reconstruction method, let us show that Scalable MWEM satisfies differential privacy.
Theorem 7. Scalable MWEM satisfies (c, 6DP
24

---

Proof. We will refer to Algorithm 7 as M. Note that M selects a parameter such that 5 minay1 exp((a-1(a0=e)) (1 (1-1) " By proposition 4, it suffices show that M satisfies p-zCDP, then it also satisfies (e, O)DP. In the initialization step, M measures Mep with the Gaussian mechanism using the noise scale o 2ap' The query Map is the total query. so it has an E sensitivity of and therefore by proposition 5, this measurement satisfies 1 202 ap-zCDP.
-
2
In each round, MM runs the exponential mechanism such that it satisfies (1-a)e zCDP. Also in each round, M runs the Gaussian mechanism measure marginal query with noise scale x² (1-a)p" All marginal queries have an &g sensitivity of so again by proposition this measurement (1-a)p -zCDP. By the adaptive composition result given in proposition 8, the overall () p-zCDP and also (e, 0)-P.
isfies 2n 2T
mechanism satisfies ap T( T (- 2T
H Experiment Details
Datasets. In general, we follow the preprocessing steps described in [7]. All attributes in the datasets discrete. We identify the data domain inferring the possible values for each attribute from the observed values for each attribute.
Titanic [23] contains 9 attributes, 1, 303 records, and has data vector size 8.9 x 10 Adult [24] contains 14 attributes, 48, 842 records, and has data vector size 9.8 x 1017 Salary [25] contains attributes, 727
727 records, and has data vector size 1.3 1013 Nist-Taxi [26] has 10 attributes, 223,55 551 records, and has data vector size 1.9 x 10
Compute Environment. All experiments were run on an internal compute cluster with two CPU cores and 20GB of memory.
GReM-LNN Hyperparameterr. For the ResidualPlanner experiments Section 5.1, we set the hyperparameters follows: the maximum number of rounds T 4000, the Lagrangian initialization parameter À = 1,, and the step size & = 0.1. For the Scalable MWEM experiments in Section 5.2, set the hyperparameters
follows: the maximum number of rounds T 1000, the Lagrangian initialization parameter X = -1, the step size 8 0.02, and regularization weight = 40. For all experiments, Alg. 6 fails, we divide the step size by v10 and rerun until convergence. We additionally impose time limit of 24H on given run of Alg. 6.
I Additional Experiments
In this section, we detail additional experimental results. For the ResidualPlanner experiment, we report l2 workload error for the reconstruction methods. For the Scalable MWEM experiment, we report & workload error for the reconstruction methods as well as whether or not Private-PGM successfully ran across various settings.
25

---

1.1
Additional ResidualPlanner Experiments
Titanic
Adult
101
10
Average Workload Error (12)
10 1
10
10-3
Salary
Nist-Taxi
10
100
10-1
10
10-3
10-1
10
10
10
10"
10
E
-
ResidualPlanner
X
Trunc
....
Frunc+Rescall
GReM-LNN
Figure 4: Average l workload error on all 3-way marginals across five trials and privacy budgets C (0.1,0.31 1,3.16, 10) and 5 10 99 for ResidualPlanner.
26

---

1.2
Additional MWEM Experiments
Titanic
Adult
10a
Average Workload Error (22)
100
10
Salary
Nist-Taxi
10
10
10-1
10-1
10"
10a
10-2
10
10a
E
Scalable MWEM
Trunc+ Rescale
GReM-LNN
Private-PGM
Figure 5: Average l workload error on all 3-way marginals across five trials and privacy budgets (0.1, 1, 1,1.16 10) and 5 10-9 for Scalable MWEM with 30 rounds of measurements.
Dataset
Rounds
Trials Total
Trials Completed
Trials >24H
Trials Out-of-Memory
Titanic
10
25
25
20
25
25
0
30
25
25
Adult
10
25
0
25
0
20
30
25
0
0
25
Salary
10
25
11
14
0
20
25
25
30
25
0
0
25
Nist-Taxi
10
20
25
0
0
25
30
25
Table 2: Completion results of rumning Private-PGM by setting for the Scalable MWEM experiment.
Failure is broken down by exceeding the 24H time limit or exceeding the available memory (20GB).
27

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract claims that the ReM and ReM-LNN methods are efficient and can be used to improve existing mechanisms. In the body of the paper we explain why the methods are efficient and provide empirical results showing that the methods can be run on large datasets and do in fact improve existing mechanisms.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have a paragraph in the discussion section dedicated to discussing the limitations of the work. We discuss how the limitations of the methods presented in this paper compare to the limitations of the related methods that we compare against.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
28

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our paper includes several theorhetical results, each of which is given with full set assumptions. The proofs are all complete and correct, they are provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide clear descriptions of the methods proposed in the paper and also provide code that can be used to reproduce the results in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
29

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The anonymized code has been submitted as zipp file along with the paper submission. Upon acceptance, we will make the code publicly available on GitHub.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
cessinnnolcyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. httppbulccgguudessssseepepeeeeee httgg/dddde//eeuumiiieeeeeeeeeee https//oooduuuiissioiiiiooo
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetalls
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the experiments section we present the key details such as the data citations, privacy parameters, and target workload. All other experimental details are provided in Appendix H.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In the experiments section, we explain that all experiments were run for trials and that we present average error along with minimum/maximum error bands.
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We give the details for the compute environment in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / hwt.rppp...cppbii//..eiiiieeeeee itthei/ccehhhcccccccleeeeeeee
Answer: [Yes]
Justification: We have reviewed the ethics guidelines and can confirm that our research practices conform those standards.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiciio))
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: the discussion section, we include a paragraph titled "Future Work and Broader Impacts" that discusses potential negative socictal impacts of the work performed.
31

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We do not release any data models. We do not believe that algorithm for private query answering have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-uss should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We utilize data that has been previously released for the purpose of academic use, in all cases we cite the relevant papers that introduce the datasets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
32

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddatases has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pa se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The anonymous code provide time of submission is well documented, it does not currently include license but at the time that the code is made public on GitHub will include license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codd/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do conduct any experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not conduct any experiments with human subjects or any experiments that are otherwise subject to IRB review.
Guidelines:
33

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "j2vPy02b7i", "reviewer": "Reviewer_hTTb", "summary": "The paper introduces ReM method for efficiently reconstructing answers to marginal queries with differential privacy. This aim is to minimize the error and allow scalability to high-dimensional datasets. As an extension, this paper also proposes ReM-LNN which ensures that the reconstructed marginals are non-negative, which further reduces error. The effectiveness of these methods is demonstrated by comparing them with existing private query-answering mechanisms like ResidualPlanner and MWEM.", "questions": "The proposed method claims to be scalable. I am wondering how the time complexity of the dual ascent algorithm used for solving (1) compares with other methods, especially how it scales with the dataset.", "limitations": "The limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well-written. The comparisons with prior works are adequately addressed. The proposed method is novel and practical.", "weaknesses": "It is not clear how to apply the reconstructed marginal queries in practical settings. For example, Private-PGM is able to generate synthetic datasets for further downstream ML tasks. However, the proposed method is not able to generate synthetic datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing feedback on our paper and suggesting improvements to clarify the presentation. Below, we address various concerns raised in the review.\n\nPrivate query answering is valuable in its own right outside of its application for synthetic data generation. Much work in differential privacy has focused on minimizing error for query answering while satisfying differential privacy. For example, for a fixed privacy budget and target workload of queries, matrix mechanisms minimize error --- often $L_2$ error --- with respect to the output answers. The original matrix mechanism [0] can answer arbitrary linear queries but is inefficient, HDMM [1] restricts to highly structured linear queries such as marginals and range queries and is more scalable than the original matrix mechanism, and ResidualPlanner [2] efficiently answers marginal queries. ReM is a generalization of the reconstruction step of ResidualPlanner.\n\nThank you for your questions about time complexity. Please see the global response for time complexity results, which we will add to the paper. \n\nSince the submission of the paper, we have been working to improve the dual ascent algorithm in practice by incorporating line search over the step size $t$ in Line 6 of Algorithm 4. This reduces the number of rounds of dual ascent until convergence.\n\n[0] Li, Chao, et al. \"The matrix mechanism: optimizing linear counting queries under differential privacy.\" The VLDB journal 24 (2015): 757-781 \n\n[1] McKenna, Ryan, et al. \"Optimizing Error of High-Dimensional Statistical Queries Under Differential Privacy.\" Journal of Privacy and Confidentiality 13.1 (2023).\n\n[2] Xiao, Yingtai, et al. \"An optimal and scalable matrix mechanism for noisy marginals under convex loss functions.\" Advances in Neural Information Processing Systems 36 (2024).", "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": "", "extra_scores": {}}, {"review_id": "fxNpR9GuBP", "reviewer": "Reviewer_a9Gz", "summary": "Matrix mechanisms are a foundational class of methods in differential privacy for efficiently answering large sets of marginal queries on tabular data. However, matrix mechanisms infamously suffer in high-dimensional data domains, where memory and compute explode. Significant efforts have been made to overcome this hurdle including the HDMM, the Private-PGM, and recently, the ResidualPlanner. \n\nThis paper generalizes the residual decomposition techniques of ResidualPlanner to be far more effective and usable. They authors demonstrate how to answer arbitrary workloads of queries from arbitrary sets of residuals in a principled loss-minimizing way. They then extend this technique to offer non-negativity (when marginals cannot be negative-valued), and demonstrate how to apply it for the canonical MWEM mechanism. \n\nThe show the significantly improved error of their reconstructions over a variety of baselines including the original ResidualPlanner. Their method is only improved on by Private-PGM, which suffers heavily from memory blow-up (in my own experience as well).", "questions": "See two questions in weaknesses section.", "limitations": "I think the authors’ treatment of limitations covers most bases I would consider.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The methods demonstrated in this paper constitute a significant improvement to the state of the art in a foundational problem in Differential Privacy. They take the clever concepts of residual-based high-dimensional reconstruction and make them practical across a wide range of settings. They demonstrate how these methods can be used for canonical mechanisms and a significant improvement in utility on standard datasets/tasks.", "weaknesses": "There is a lot of technical content in this paper, which is challenging to get through in 9 pages. The writing could have been organized differently to help the reader gain intuition on how this method improves the state of the art. It took me a few reads. \n\nFor instance, it is clear to me that the fundamental challenge is the computational intractability of the pseudoinverse, and that residual workloads help solve this. I still do not have great intuition on how residual workloads make this improvement. Perhaps I’m slow on this point, but it feels like it should be illuminated more prominently since it is central to the problem. Granted, residual workloads were introduced in a prior work. \n\nAnother confusion: a major asset of ReM when it is introduced is that a given residual can be queried multiple times and then more accurately estimated with MLE. It was not clear to me why one would want to measure a single residual multiple times. Later in the scalable MWEM section, I could see how a residual would be queried multiple times as it appears in multiple marginals, but I was not sure if that’s the only reason. I think the motivation behind ReM could be described differently, perhaps even starting with something the reader knows (MWEM) and then showing how ReM and grem-lnn come to the rescue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing feedback on our paper and suggesting improvements to clarify the presentation. \n\nIn the revision, we will do our best to improve readability of the paper and better motivate residual queries in Section 2.1. \n\nRegarding why there might be multiple measurements of the same residual, please see the global response.", "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": "", "extra_scores": {}}, {"review_id": "U114rICK00", "reviewer": "Reviewer_r5Ym", "summary": "The paper studies the problem of reconstructing a data distribution from noisy measurements of a set of carefully selected marginal queries and using the reconstructed data distribution to answer a set of workload queries. The difficulty in the problem lies in the high dimensionality of the data distribution, which in turn requires measuring and inverting an exponential number of queries in the worst case. In this paper, the authors propose to \n1. translate the marginal workload queries to their equivalent residual queries representation, and compute their noisy measurements\n2. exploiting the structure of residual query matrix to perform efficient pseudoinverse via Kronecker product\n3. perform reconstruction via an optimization problem that has solution $=$ the product of pseudoinverse matrix and noisy measurements, where additional non-negativity constraints on the solution are enforced as post-processing\n\n Compared to prior approaches for marginal reconstruction, the proposed approaches enjoy improved efficiency as the Kronecker product matrix is efficiently invertible. The technique of converting the query matrix to its residual representation is further extended to the MWEM algorithm to allow efficient computation and representation of reconstructed marginals under the high-dimensional data. Experiments confirm that the proposed reconstruction and scalable MWEM algorithms allow improved query-answering performance when used on top of existing mechanisms that are solely based on noisy measurements rather than reconstructed data distribution.", "questions": "1. Why would not the proposed algorithms have exponential complexity (weakness 1)? And how does this relate to the known hardness results (weakness 2)?\n\n2. Could the authors explain more about the lack of comparison with other reconstruction methods (weakness 3)?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- An interesting idea of using the residual basis of query matrix to efficiently represent and compute pseudoinverse matrix for marginal reconstruction. \n- Based on the observation, two interesting new algorithms are proposed: efficient marginal reconstruction both via reconstructing data distribution, and scalable MWEM on high-dimensional data via residual computation and representation of marginal queries.\n- Strong experimental performance when used as post-processing mechanisms on top of existing query-answering mechanisms that are solely based on noisy measurements rather than reconstructed data distribution.", "weaknesses": "1. One concern is regarding the discussion of computation complexity of the proposed method. The main advantage of the proposed algorithms is that they \"will not have exponential complexity\" (line 46). However, as the proposed algorithms still involve some enumerating operations on all possible attribute subsets (e.g., lines 9-11 in algorithm 3), it is not immediately clear why they \"will not have exponential complexity\". It would also be helpful if the authors could clarify what they mean by exponential complexity.\n\n2. Relevant to the previous question, there are well-known hardness results of generating synthetic data under differential privacy [a], that talk about the necessity of exponential runtime for accurate reconstruction of data distribution. Such lower bounds should be discussed in detail to understand the results of this paper, in terms of the saved computation complexity.\n\n3. The comparison is mainly done with regard to Residual planner [6] and PGM [12], while several other reconstruction methods such as PrivBayes [8], GEM [9], RAP [10], and RAP++ [11] are not considered in the comparison. Such comparisons are useful for understanding the performance of the proposed reconstruction algorithm, and for understanding the contributions of the paper. Alternatively, it would be useful if the authors could further clarify why such algorithms are not considered in the comparison.\n\n\n[a] Ullman, Jonathan, and Salil Vadhan. \"PCPs and the hardness of generating private synthetic data.\" Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing feedback on our paper and suggesting improvements to clarify the presentation. Below, we address various concerns raised in the review.\n\nRegarding time complexity, please see the global response for specific running time bounds, which we will include in the revised paper. Regarding ``exponential complexity'', we will also clarify this. Our goal is to bound the running time of the reconstruction problem in terms of the size of its own inputs and outputs. The inputs are the noisy residual measurements, and the outputs are the reconstructed marginals. The results we state in the global response show that our algorithms take time that is polynomial (and subquadratic) in these size parameters, and thus avoid exponential complexity. As a concrete example, suppose the workload is all 2-way marginals over $d$ attributes, all attributes have domain size $m$, and the measurements are taken from ResidualPlanner. Then the input size and output size are both ${d \\choose 2} m^2$. Our methods are polynomial (subquadratic) in ${d \\choose 2} m^2$ (and thus in $d$ and $m$), while a method that reconstructs the full data vector will take $\\Omega(m^d)$ time. \n\nThank you for the comment about hardness results. We will add a discussion of complexity results to our paper. Briefly, the theorem of Ullman and Vadhan [a] does not apply because our mechanism does not output a synthetic data set. Indeed, as noted by Vadhan [b], ''the requirement that the mechanism produces a synthetic dataset cannot be removed'' from this hardness result. This is because the class of queries used in the result (two-way marginals) can be answered with vanishing error in polynomial time by a mechanism (e.g., the Laplace mechanism) that directly answers the queries without producing synthetic data. We will also add a discussion of other computational hardness results for query answering. In general, these results rely on worst-case query classes constructed from cryptographic primitives and not natural query classes such as marginals, so we don't expect them to apply to our practical use cases. Vadhan [b] highlights it as an open problem to give query-answering hardness results for natural query classes.\n\nRegarding comparisons, our goal in this paper is to study the reconstruction subproblem and develop general-purpose solutions. Among the alternative algorithms, only Private-PGM is a self-contained reconstruction method. The other algorithms (PrivBayes, RAP, GEM, etc.) are full query-answering or synthetic data mechanisms, which include some approach to reconstruction in the context of their mechanism. In several cases, such as RAP, a generic reconstruction approach can be extracted. RAP uses a neural network to represent the solution space and gradient descent variants to train it. However, to the best of our knowledge, due to the parametric modeling assumptions of these mechanisms, reconstruction requires solving a non-convex optimization problem. Thus the final result will be dependent both on how well the data distribution meets the parametric modeling assumptions, and on how well one is able to solve the non-convex optimization problem in practice. For the purpose of studying reconstruction in a self-contained manner, we choose in this paper to restrict to Private-PGM, which is the only other method that is general purpose and has predictable output due to solving a convex optimization problem to optimality. In-depth empirical comparisons of different reconstruction methods in the context of full mechanisms, including the impacts of non-convexity, etc., is an interesting avenue for future work.\n\n[a] Ullman, Jonathan, and Salil Vadhan. \"PCPs and the hardness of generating private synthetic data.\" Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.\n\n[b] Vadhan, Salil. The Complexity of Differential Privacy. In: Lindell, Y. (eds) Tutorials on the Foundations of Cryptography. Information Security and Cryptography. Springer, 2017.", "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": "", "extra_scores": {}}, {"review_id": "u73mXOslIs", "reviewer": "Reviewer_JUY8", "summary": "This paper introduces residuals-to-marginals (ReM), a novel approach to constructing marginals from input data residuals while maintaining differential privacy. ReM operates by first estimating true residuals from noisy ones, then transforming these estimates into target marginals. The authors propose two variants of ReM: ReM-LNN, which enhances accuracy by enforcing non-negativity constraints on the resulting marginals, and GReM-MLE, a more efficient version for scenarios involving Gaussian noise injection to residuals, leveraging a closed-form solution. The paper also presents an extension of ReM that incorporates the MWEM. This extension identifies residuals that are useful for marginal construction, offering an end-to-end solution when residual choices are not predetermined. Experimental results demonstrate that ReM significantly reduces errors compared to baseline methods in constructing differentially private marginals. ReM also demonstrates good scalability, whereas PrivatePGM, a baseline method, failed to run for large data domains.", "questions": "1. Please include the derivation of L_tau in Line 216, Page 5. It appears to represent the probability of generating y_{tau, i} given alpha, over the randomness of Gaussian noise. Additionally, please provide a detailed argument for the closed-form solution mentioned in Line 218.\n\n2. Could you clarify why \"when the marginal is observed with isotropic noise, the corresponding noisy residuals are independent\"? (Line 239, Page 6)", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper presents ReM, a new approach to constructing marginals from residuals. \n\n2. ReM reduces errors compared to some baseline methods. \n\n3. ReM can be applied as a post-processing method to improve the accuracy of some other methods.", "weaknesses": "1. The paper compares ReM against MWEM and Private-PGM [12], but omits the state-of-the-art methods such as AIM [7] and PrivMRF [19]. Both AIM and PrivMRF have been demonstrated to significantly outperform MWEM and Private-PGM. As a consequence, it is unclear whether ReM really advances the state of the art.\n\n2. It would be helpful to explicitly define k_tau in Line 1 of Algorithm 2. I do not see where this paper defines k_tau. It seems that for each attribute set tau, the algorithm injects noise k_tau times, resulting in k_tau marginals, ranging from y_{tau, 1} to y_{tau, k_r}. Why is it necessary to inject noise multiple times for each marginal?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing feedback on our paper and suggesting improvements to clarify the presentation. Below, we address various concerns raised in the review.\n\nSince ReM is a reconstruction method, the appropriate comparison is not with full end-to-end synthetic data or query answering mechanisms such as AIM and PrivMRF but rather with the reconstruction methods these mechanisms use. \nBoth AIM and PrivMRF use Private-PGM as part of their reconstruction steps, and we include Private-PGM in our experiments.\nRegarding Scalable MWEM, we use this end-to-end mechanism to choose which marginals to measure but compare Scalable MWEM's reconstruction method (discussed in Appendix D) to ReM with Local Non-negativity (GReM-LNN) and Private-PGM in our experiments.\n\nReM takes an arbitrary number $k_\\tau$ of measurements of each residual $R_\\tau \\in \\mathcal{S}$ as input. We will be more explicit about $k_\\tau$ when it is introduced in the text on Line 189. \n\nRegarding why a residual query might be measured multiple times, please see the global response.\n\nThe loss function $L_\\tau$ from Line 216 comes from using the negative log-likelihood as the loss function (as described in Line 190) for the noise model described in Lines 212 and 213, i.e., with $k_\\tau$ independent Gaussian random variables $y_{\\tau, i}$ with covariance $\\Sigma_{\\tau, i}$, so that\n$$\nL_\\tau(\\alpha_\\tau) = -\\sum_{i=1}^{k_\\tau} \\log p(y_{\\tau, i} | R_\\tau p = \\alpha_{\\tau})\n$$\nwith $p(y_{\\tau,i} | R_\\tau p = \\alpha_\\tau) = \\mathcal{N}(y_{\\tau,i}; \\alpha_\\tau, \\Sigma_{\\tau,i})$.\nWe solve for $\\hat \\alpha_\\tau$ in closed-form by finding the critical point of $L_\\tau$. In the revision, we will include the derivation of the closed-form solution to $\\hat \\alpha_\\tau$ in an appendix. \n\nLines 238-240 are an informal statement of Theorem 2. To clarify this, we will specify that $z_\\tau$ is a ''noisy residual'' in the statement of Theorem 2.", "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": "", "extra_scores": {}}]

Author rebuttal:
Below, we address two concerns raised in the reviews: time complexity and natural cases where multiple residuals are measured.

Regarding time complexity, let $\gamma, \tau$ be tuples of attributes and suppose each attribute has domain size $m$. Then an answer to marginal $M_\gamma$ has size $m^{|\gamma|}$. Reconstructing an answer to marginal $M_\gamma$ from a set of residuals using GReM is $\mathcal{O}(| \gamma | \cdot m^{|\gamma| + 1} \cdot 2^{|\gamma| - 1})$. 
This running time is subquadratic with respect to output size $m^{|\gamma|}$.
This can be verified by observing that $\Big( \frac{| \gamma | m^{|\gamma| + 1} 2^{|\gamma| - 1}}{m^{2|\gamma|}} \Big) \rightarrow 0$ as either $m$ or $|\gamma|$ grow arbitrarily large.
As a pre-processing step, we only store one combined ``measurement'' per residual in the downward closure of the workload. After this pre-processing step, the input size is no more than the output size. Therefore, the reported running time bounds are in terms of the output size only.

For the dual ascent algorithm in GReM-LNN, one round has time complexity $\mathcal{O}(| \mathcal{W} | \cdot | \gamma^* | \cdot m^{|\gamma^*| + 1} \cdot 2^{|\gamma^*| - 1} )$ where $\mathcal{W}$ is the workload of marginals to answer and $\gamma^*$ is the largest tuple of attributes in $\mathcal{W}$. 
This running time is linear with respect to the number of marginals in the marginal workload $\mathcal{W}$ and subquadratic with respect to the size of the largest reconstructed marginal $M_\gamma$.

Consider the workload of all $k$-way marginals over a data domain with $d$ attributes. Reconstructing all marginals in this workload using GReM is $\mathcal{O}(k d^k m^{k+1} 2^{k-1})$. 
Since $k$ appears only as an exponent or multiplicative term, reconstruction is not exponential in any size parameter other than the size of the marginals, for which we expect exponential scaling.
Similarly, for GReM-LNN, each round of dual ascent is $\mathcal{O}(k d^k m^{k+1} 2^{k-1})$. 
In many use cases, only 3-way or smaller marginals are measured.

In the revision, we will include these time complexity results in the main text as well as proofs in an Appendix.

Regarding multiple measurements of the same residual, there are several reasons we might encounter this. First, some state of the art mechanisms regularly measure the same query multiple times. A good example is AIM, which has a budget annealing process that allows it to measure queries more accurately in later rounds. Because of this it will often take repeated measurements of the same marginal at decreasing noise levels. 
Another reason for measuring a residual query multiple times is the conversion from marginal measurements to residual measurements. Synthetic data mechanisms like AIM and PrivMRF select marginals to measure with isotropic Gaussian noise. 
In Theorem 2, we show how to convert such a marginal measurement into an equivalent set of residual measurements. When using this conversion within such a mechanism that selects marginals, a residual will be measured each time a marginal that contains it is selected. 
We will include this motivation earlier in the paper to better understand the problem setting.

Meta-review: The paper proposes a more efficient method for reconstructing marginal query answers from privately released residuals. This is an important step in several private query release algorithms. Some details about running time bounds need to be clarified in the final version. Otherwise, this is an original contribution making an advance on an important problem.
Decision: Accept (poster)