Efficient and Private Marginal Reconstruction with Local Non-Negativity

Authors: brett  mullins
miguel  fuentes
yingtai  xiao
daniel  kifer
cameron  musco
daniel  sheldon
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:06:50

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.

Main paper: 
 introduction: 
 Differential 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 a workload of linear queries. Linear queries are used for basic descriptive statistics 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.A key subproblem in linear query answering is reconstruction. Given a 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 use the noisy answers to reconstruct answers to workload queries [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] .Effective reconstruction methods can combine information from all noisy measurements to provide mutually consistent answers to workload queries.Computational complexity is a key challenge for reconstruction methods. These methods answer workload queries by-either explicitly or implicitly-reconstructing a data distribution that has size exponential in 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] [9] [10] [11] [12] , which introduces tradeoffs such as a restricted space of data distributions that can be represented [8- 38th Conference on Neural Information Processing Systems (NeurIPS 2024). 11], non-convex optimization objectives to find the best representation [9] [10] [11] , or complexity that depends on the measured queries and is still exponential in the worst case [12] .We introduce ReM (residuals-to-marginals), a principled and scalable post-processing method to reconstruct answers to a 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 statistics [13, 14] . ReM uses a 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 a 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.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 ResidualPlanner [6] and the multiplicative weights exponential mechanisms (MWEM) [15] . Our code is available at https://github.com/bcmullins/efficient-marginal-reconstruction. 
preliminaries: 
 We consider a sensitive tabular dataset D of records x (1) , . . . , x (N ) . Each record x = (x 1 , . . . , x d ) consists of d categorical attributes. The ith attribute x i belongs to the finite set X i of size n i . The data universe is X = d i=1 X i and has size n = i n i . The data vector or data distribution p ∈ R n is a vector indexed by X that counts the occurrences of each record in D; it has entries p(x)= N i=1 I[x (i) = x].Since n is exponential in the data dimension d, it is computationally intractable to work directly with data vectors in high dimensions.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 a real-valued function q : X → R applied to each record in the dataset. We adopt the equivalence that a query is a vector q ∈ R n with answer q ⊤ p. A query matrix or workload W is a collection of m linear queries arranged row-wise in an m × n matrix. The answer to workload W for data vector p is given by W p.Marginal queries are a common type of linear query for high-dimensional data. They count the number of records that match certain values for a subset of the attributes -e.g., the number of people in a dataset with education at least a college degree and income $50-$100K. Let γ ⊆ [d] be a subset of attributes and x γ = (x i ) i∈γ be the corresponding subvector of a record x. Further, let X γ = i∈γ X i and n γ = i∈γ n i . The marginal µ γ ∈ R nγ has entries µ γ (t) =N i=1 I[x (i) γ = t]that count the number of occurrences in the dataset for each setting t ∈ X γ of the attributes in γ. Let M γ ∈ R nγ ×n be the marginal workload so that µ γ = M γ p. As shown in Fig. 1a , M γ can be written concisely as a Kronecker product over dimensions, with base matrices equal to the identity I k ∈ R n k ×n k for attributes in γ and the all ones vector 1 ⊤ k ∈ R 1×n k for attributes not in γ. Kronecker product matrices can be understood as applying different linear operations along each dimension of a multi-dimensional array. In this case M γ sums over dimensions of the array representation of p for attributes not in γ. We provide a brief summary of Kronecker products and their relevant properties in Appendix A.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 τ ⊆ [d], the τ -residual is obtained from the marginal µ τ by applying a differencing operator along each dimension. Let D (k) be the linear operator that computes successive differences for vectors of length n k , i.e., (D (k) v) i = v i+1 -v i for i = 1, . . . , n k -1; an example is shown for n k = 3 in Fig. 1b . Let D τ be the matrix that applies this operation to all attributes in the τ -marginal as shown in Fig. 1c . The residual workload can be written as R τ = D τ M τ ∈ R mτ ×n where m τ = i∈τ (n i -1), which has the explicit Kroecker product form shown in Fig. 1d . 1 With these definitions, if µ τ = M τ p is the τ -marginal, the τ -residual is α τ = D τ µ τ = R τ p and can be computed from either µ τ or p.Residuals and marginals have an intricate structure. The γ-marginal is uniquely determined by the τ -residuals for τ ⊆ γ, i.e., there is an invertible linear transformation between M γ and (R τ ) τ ⊆γ (a vertical block matrix). Intuitively, a γ-residual contains information not contained in the τ -marginals for τ ⊂ γ. Further, the row spaces of R τ and R τ ′ are orthogonal for any τ ̸ = τ ′ , and the row spaces of M γ and R τ are orthogonal when τ ̸ ⊆ γ [6, 13, 14] . Along with Kronecker structure, the orthogonality of residuals is the key property we will leverage to perform efficient reconstruction.A key advantage of residual workloads is 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 a marginal query M γ from measurements for a collection of residuals. Proposition 1. Let R S = (R τ ) τ ∈S be a combined workload of residual queries for all τ in a collection S ⊆ 2 [d] , where the individual matrices R τ are stacked vertically. The size of R S is m × n where m = τ ∈S m τ . Then for any z = (z τ ) τ ∈S ∈ R m and any γ, it holds thatM γ R + S z = τ ∈S,τ ⊆γ A γ,τ z τ , where A γ,τ := d k=1      D + (k) k ∈ τ 1 /n k 1 k k ∈ γ \ τ 1 k / ∈ γ for τ ⊆ γ.The matrix A γ,τ has size n γ × m τ and maps from the space of τ -residuals to the space of γ-marginals.A γ,τ z τ is O(|γ|n γ ).The proof of this result appears in Appendix C. The analysis of time complexity appears in Appendix E.When releasing the results of any analysis performed on sensitive data, particular care needs to be taken to avoid leaking private information contained in the dataset. Differential privacy is a mathematical 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 1. (Differential Privacy; [16] ) Let M : X → Y be a randomized mechanism. For any neighboring datasets D, D ′ that differ by adding or removing at most one record, denoted D ∼ D ′ , and all measurable subsetsS ⊆ Y: if Pr(M(D) ∈ S) ≤ exp(ϵ) • Pr(M(D ′ ) ∈ S) + δ, then M satisfies (ϵ, δ)-approximate differential privacy, denoted (ϵ, δ)-DP.A fundamental property of differential privacy relevant to our 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 (Post-processing; [17] ). Let M 1 : X → Y satisfy (ϵ, δ)-DP and f : Y → Z be a randomized algorithm. Then M :X → Z = f • M 1 satisfies (ϵ, δ)-DP.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 to the model of differential privacy used.We discuss variants of differential privacy and privacy guarantees for query answering in Appendix B.In private query answering, we are given a workload of linear queries W ∈ R m×n . We seek to approximate the answers W p as accurately as possible while satisfying differential privacy. A general recipe for private query answering is select-measure-reconstruct. Data-independent mechanisms following this recipe such as the various matrix mechanisms [2] [3] [4] [5] [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 a model p of the data distribution p that is improved iteratively by repeating the steps of select-measure-reconstruct 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 error 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-independent and data-dependent settings.Reconstruction is a central subproblem to query answering. Suppose y = Qp + ξ is the a set of measurements. To reconstruct a data distribution, we seek p such that Qp ≈ y. One method is to set p = 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 a 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 p 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] [9] [10] [11] . Optimizing over the parameteric representation is often non-convex, potentially leading to suboptimal optimization [9] [10] [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 is 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). 
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 ⊆ 2 [d] and M W = (M γ ) γ∈W 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 S = (R τ ) τ ∈S represent a set of residual queries for all τ in a collection S. Our goal is to estimate the marginal query answers M W p from noisy measurements z = R S p + ξ.Input: Marginal workload W, S = W ↓ , measurements z τ = R τ p + N (0, Σ τ ) for τ ∈ S 1: Reconstruct μγ = τ ⊆γ A γ,τ z τ for γ ∈ W ResidualPlanner. ResidualPlanner [6] solves this problem elegantly in the matrix mechanism (i.e. data-independent) setting under Gaussian noise. Let W ↓ = {τ ⊆ γ : γ ∈ W} denote the downward closure of W. When S = W ↓ , the residual queries for S uniquely determine the marginals for W, i.e., there is an invertible linear transformation between M W and R S . This yields the reconstruction approach in Alg. 1. We suppose the residual queries R τ are measured with Gaussian noise to yield z τ . In Line 1, the marginals are reconstructed by applying the invertible transformation from residuals to marginals. This reconstruction is equivalent to setting μγ = M γ p where p = R + S z and z = (z τ ) τ ∈S by Proposition 1.The full ResidualPlanner algorithm additionally chooses each Σ τ = σ 2 τ D τ D ⊤ τ such that the resulting algorithm optimally answers the marginal workload indexed by W to minimize error under a natural class of convex loss functions for a given privacy budget [6] . That this can be done efficiently for a broad class of error metrics for marginal workloads is 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 ResidualPlanner 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. 3) an optimization problem is solved for each τ to estimate the true residual query answer ατ ≈ R τ p, (4) reconstruction uses the estimated residuals ατ instead of the noisy measurements z τ . The loss function L τ (α τ ) in Line 2 captures how well α τ explains the entire set of noisy measurements {z τ,i } i=1,...,kτ . For example, a typical choice is L τ (α τ ) = -kτ i=1 log p(z τ,i |R τ p = α τ ), the negative log-likelihood of the measurements.The following result shows that solving the optimization problems in Line 1 is equivalent to finding a compact representation of a data distribution p that minimizes a global reconstruction loss and then using p to answer each marginal query. Theorem 1. Suppose ατ minimizes L τ (α τ ) over R mτ for each τ ∈ S and let α = (α τ ) τ ∈S . Then Alg. 2 outputs μγ = M γ p, where p = R + S α is a global minimizer of the combined loss functionτ ∈S L τ (R τ p) over R n .This result is proved (in Appendix D) by showing that R τ p = ατ for all τ , and thus p optimizes each individual loss function L τ , and so must be a global minimizer. Proposition 1 then shows that μγ = M γ p = M γ R + S α has the form given in Line 2 of the algorithm.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 considerations. • The conference expects that many papers will be foundational research and not 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 correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
applications of rem under gaussian noise: 
 In this section, we apply ReM to reconstruct answers to marginal queries in various settings: ( = R τ p + N (0, Σ τ,i ) for τ ∈ S, i = 1, . . . , k τ 1: Estimate ατ = i Σ -1 τ,i -1 i Σ -1 τ,i z τ,i for τ ∈ S 2: Reconstruct μγ = τ ∈S:τ ⊆γ A γ,τ ατ for γ ∈ WAn instance of ReM that allows for efficient computation is when residuals are measured with Gaussian noise i.e., z τ,i = R τ p + ξ τ,i where ξ τ,i ∼ N (0, Σ τ,i ) and the loss function L τ (α τ ) is the negative log-likelihood of the measurements. In this case, α = (α τ ) τ ∈S is the maximum likelihood estimate of the residual answers α = (α τ ) τ ∈S . We refer to this setting as GReM-MLE (Gaussian ReM with Maximum Likelihood Estimation), shown in Alg. 3.The loss function L τ (α τ ) is a sum of quadratic forms given by Lτ (α τ ) = kτ i=1 (α τ - z τ,i ) ⊤ Σ -1 τ,i (α τ -z τ,i ).In this setting, the optimization problems in Line 1 of Alg. 2 have the closed-form solution ατ =i Σ -1 τ,i -1 i Σ -1 τ,i z τ,i, which is a 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 τ ∈ S, i.e., Σ τ,i = σ 2 τ,i K τ where σ τ,i ∈ R, then ατ can be computed as a weighted average given by ατ = ( i σ -2 τ,i ) -1 i σ -2 τ,i z τ,i . All instances of GReM-MLE considered throughout the paper satisfy this assumption of proportional covariances for each τ ∈ S.A common practice in existing mechanisms is to measure marginal queries with isotropic Gaussian noise [4, 7, 9, 11, 18, 20] . In this special case, the measurements can be converted to an equivalent set of residual measurements with independent Gaussian noise, allowing us to apply GReM-MLE.The key observation is that a marginal query answer µ γ = M γ p for attribute set γ can be used to derive residual answers α τ = R τ p for each τ ⊆ γ via the following Lemma (proved in Appendix D): Lemma 1. For τ ⊆ γ, the residual R τ can be recovered from the marginal M γ asR τ = A + γ,τ M γ where A + γ,τ = d k=1    D (k) k ∈ τ 1 T k k ∈ γ \ τ 1 k / ∈ γ .Whereas A γ,τ maps answers from residual R τ to answers to marginal M γ , the matrix A + γ,τ maps answers from marginal M γ to residual R τ . Furthermore, µ γ can be reconstructed from the set of all residuals (α τ ) τ ⊆γ , so these residuals carry equivalent information to the marginal. Additionally, when the marginal is observed with isotropic noise as y γ = M γ p + N (0, σ 2 γ I), the corresponding noisy residuals A + γ,τ z τ are independent. As a consequence, we can decompose a noisy marginal measurement into a set of equivalent and independent noisy residual measurements. Theorem 2. Let y γ ∼ N (M γ p, σ 2 I) be a noisy marginal measurement with isotropic Gaussian noise and let z τ = A + γ,τ y γ for each τ ⊆ γ. Then noisy residual z τ has distributionN (R τ p, σ 2 D τ D ⊤ τ k∈γ\τ n k ) and z τ is independent of z τ ′ for τ ̸ = τ ′ . Furthermore, let H γ = (A + γ,τ) τ ⊆γ be the matrix mapping from y γ to (z τ ) τ ⊆γ . This matrix is invertible, which implies thatEQUATIONGiven a collection of noisy marginal measurements, we can apply the above decomposition to 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-likelihood of the marginal measurement by a constant log | det H γ | that is independent of p, and measurements of marginals are each independent. A maximum likelihood estimate of p from the marginal measurements y is given by using the pseudoinverse of the measured workload to map noisy marginal measurements to a data vector. The following result shows that the method in Alg. 4 is equivalent to answering queries from this maximum likelihood estimate of the data vector given the marginal measurements when the marginals are measured with the same noise scale.Input: Marginal workload W, measured marginals multiset Q, measurements y = (y γ ) γ∈Q wherey γ = M γ p + N (0, σ 2 I) for γ ∈ Q Output: Marginal answers (M γ M + Q y) γ∈W 1: Initialize S = ∅ and k τ = 0 for all τ ▷ Track measured residuals, lazy data structure for k τ 2: for γ ∈ Q do 3: for τ ⊆ γ do 4: S = S ∪ {τ }, k τ ← k τ + 1 5: z τ,kτ = A + γ,τ y γ ▷ Extract residual measurement from y γ 6: σ 2 τ,kτ = σ 2 k∈γ\τ n k ▷ Compute noise scale 7: Σ τ,kτ = σ 2 τ,kτ D τ D ⊤ τ ▷ Proportional covariance return GReM-MLE(W, S, z) where z = (z τ,i : τ ∈ S, i = 1, . . . , k τ )Theorem 3 (Efficient pseudoinversion of marginal query matrix). Let M Q = (M γ ) γ∈Q be the query matrix for a multiset Q of marginals and let y = (y γ ) γ∈Q be corresponding noisy marginal measurements withy γ = M γ p + N (0, σ 2 I). Let S = {τ ⊆ γ : γ ∈ Q} and for each τ ∈ S let γ τ,i be the ith marginal in Q containing τ . Let z τ,i = A + γτ,i,τ y γτ,i be the residual measurement obtained from γ τ,i and let Σ τ,i = σ 2 τ,i D τ D ⊤ τ be its covariance where σ 2 τ,i = σ 2 k∈γτ,i\τ n k .Then, given any workload of marginal queries W, for each γ ∈ W, the marginal reconstruction μγ obtained from Algorithm 3 on these residual measurements is equal toM γ M + Q y.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 3 in Appendix D.It is often possible to improve accuracy of a differentially private mechanism by forcing its outputs to satisfy known constraints [4, 10, 21] . For our problem, true marginals are non-negative, so it is desirable to enforce non-negativity in their private estimates. To enforce non-negativity, instead of solving the separate problems in Line 1 of Alg. 2, we solve the following combined problem over the full vector α = (α τ ) τ ∈W ↓ of residuals:EQUATIONReconstruction of marginals then proceeds as in Line 2 of Alg. 2. The constraints in Eq. ( 2) ensure that the reconstructed marginals will be non-negative. We refer to this as local non-negativity, since this problem solves for a data distribution p that is non-negative for marginals in W rather than a data distribution with non-negative entries.A natural setting to apply local non-negativity to ReM is under Gaussian noise with covarianceΣ τ,i = σ 2 τ,i D τ D ⊤ τ and σ 2 τ,i ∈ 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) solves Eq. ( 2) for L τ (α τ ) = kτ i=1 (α τ -z τ,i ) ⊤ K -1 τ,i (α τ -z τ,i ) and K τ,i = 2 |τ | D τ D ⊤ τ .In the GReM-LNN setting, Eq. ( 2) is an convex program with linear constraints. Our implementation solves this problem using a 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 L τ (α τ ), adopting 2 |τ | rather than Gaussian noise scale σ 2 τ,i is a heuristic that weights lower degree residual queries such as 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 σ 2 τ,i obtained from both ResidualPlanner and the marginal decomposition in Theorem 2 weights higher degree residual queries more than lower degree residuals. When enforcing local non-negativity, it is beneficial for reducing reconstruction error to 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.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 R τ is measured once, given by z τ , for each τ ∈ S. Recall from Proposition 1 that computing A γ,τ z τ takes O(|γ|n γ ) time. This operation maps from the space of τ -residuals to γ-marginals. To reconstruct an answer to the marginal query M γ , we apply the invertible transformation from residuals to marginals by summing over contributions for each τ ⊆ γ to yield μγ = τ ∈S:τ ⊆γ A γ,τ z τ . In the worst case, this requires computing A γ,τ z τ for 2 |γ| residuals. Then the running time of reconstructing an answer to marginalM γ is O(|γ|n γ 2 |γ| ). If W is a workload of marginals, then reconstructing answers to each γ ∈ W is O( γ∈W |γ|n γ 2 |γ| ).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 ε > 0, reconstructing an answer to M γ is o(n 1+ε γ ) as n i → ∞ for some i ∈ γ. Method Running Time GReM-MLE(W, S, z) O( γ∈W |γ|n γ 2 |γ| ) EMP(W, Q, y) O( γ∈W |γ|n γ 2 |γ| ) One Round of GReM-LNN(W, S, z) O( γ∈W |γ|n γ 2 |γ| ) 
experiments: 
 In this section, we measure the utility of GReM-MLE and GReM-LNN by incorporating them as a 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 three-way 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 ℓ 1 error with respect to the reconstructed marginals of the base mechanism to post-processing with GReM-LNN and two heuristics that enforce non-negativity by truncating negative values to zero (Trunc) and truncating to zero then rescaling (Trunc+Rescale). For the Scalable MWEM experiment, we additionally compare to a well-studied reconstruction mechanism Private-PGM [12] . We run these methods on four datasets of varying size and scale, Titanic [23] , Adult [24] , Salary [25] , and Nist-Taxi [26] , and various practical privacy regimes, ϵ ∈ {0.1, 0.31, 1, 3.16, 10} and δ = 1 × 10 -9 . For each setting, we run five trials and report the average error of each method as well as minimum/maximum bands. Additional details are provided in Appendix H.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 compared to ResidualPlanner. Averaging over all settings and trials, GReM-LNN reduces ResidualPlanner workload error by a factor of 44.0×. 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 (ϵ = 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 a factor of 17.6× compared to Trunc and 3.2× compared to Trunc+Rescale. Note that GReM-MLE is omitted from Fig. 2 since ResidualPlanner is the maximum likelihood reconstruction for its measurements. Appendix I reports results for this experiment with respect to ℓ 2 workload error, which are consistent with the present findings.Fig. 3 displays results for the Scalable MWEM experiment for 30 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 error 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.3×. Averaging over all settings and trials, GReM-LNN has lower workload error by a factor of 1.1× compared to Trunc+Rescale. Note that we suppress results for Trunc due to space. Appendix I reports results for this experiment with respect to ℓ 2 workload error, which are consistent with the present findings.  
discussion: 
 We develop ReM, a method for reconstructing answers to marginal queries that scales to large data domains. We also introduce a tractable method to incorporate local non-negativity that significantly improves reconstruction quality. Finally, we show that ReM can be used to improve the existing query answering mechanisms ResidualPlanner and a 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 [27, 28] . For those users, the fact that ReM does not generate synthetic data would be an important limitation. A broader limitation, which is 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 privacy-preserving 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.Kronecker products are a convenient way to represent highly structured matrices. Let A be anm a × n a matrix A =    a 1,1 • • • a 1,na . . . . . . a ma,1 • • • a ma,na    and B be a m b × n b matrix. Then the Kronecker product of A with B is an m a m b × n a n b matrix given by A ⊗ B =    a 1,1 B • • • a 1,na B . . . . . . a ma,1 B • • • a ma,na B   .Kronecker products provide a compact representation of matrices by representing exponentially-many entries of A ⊗ B with linearly-many entries in A and B. For the Kronecker product of a sequence of matrices A 1 , . . . , A d , we use the notationd i=1 A i = A 1 ⊗ • • • ⊗ A dThe Kronecker product is associative, so pairwise products can be taken in any order.Kronecker products additionally possess useful algebraic properties. Let (•) + denote Moore-Penrose pseudoinverse.Proposition 3. (Kronecker Product Properties) Let A = d i=1 A i and B = d j=1 B j .Then the following properties hold:1. A ⊤ = d i=1 A ⊤ i . 2. A + = d i=1 A + i . 3. If A i and B i are compatible for multiplication for i = 1, . . . , d, then AB = d i=1 A i B i .There are efficient algorithms for matrix-vector multiplication utilizing Kronecker structure such as Alg. 5. Let A = ℓ i=1 A i be a Kronecker structured matrix where A i is a matrix of size a i × b i so that A has size a × b with a = Input: Matrix A = ℓ i=1 A i , vector x a i , b i = SHAPE(A i ) r = ℓ i=1 b i x 1 = x for i = 1, . . . , ℓ do Z = RESHAPE(x i , b i , r /bi) r = r • ai /bi x i+1 = RESHAPE(A i Z, r, 1) return x ℓ+1Let us begin by introducing a useful variant of differential privacy: zero-concentrated differential privacy (zCDP). Definition 2. (Zero-Concentrated Differential Privacy; [31] ) Let M : X → Y be a randomized mechanism. For any neighboring datasets p, p ′ that differ by at most one record, denoted p ∼ p ′ , and all measurable subsets S ⊆ Y: if D γ (M(p)||M(p ′ )) ≤ ργ for all γ ∈ (1, ∞) where D γ is the γ-Renyi divergence between distributions M(p), M(p ′ ), then M satisfies ρ-zCDP.While (ϵ, δ)-DP is a more common notion, it is often more convenient to work with zCDP. There exists a conversion from zCDP to (ϵ, δ)-DP.Proposition 4 (zCDP to DP Conversion; [32] ). If mechanism M satisfies ρ-zCDP, then M satisfies (ϵ, δ)-DP for any ϵ > 0 and δ = min α>1 exp((α-1)(αρ-ϵ))α-11 -1 α α .Next, we introduce two building block mechanisms. An important quantity in analyzing the privacy of a mechanism is sensitivity. The ℓ k sensitivity of a function f :X → R is given by ∆ k (f ) = max p∼p ′ ∥f (p) -f (p ′ )∥ k . If f is clear from the context, we write ∆ k .Proposition 5 (zCDP of Gaussian mechanism; [31] ). Let W be an m × n workload. Given data vector p, the Gaussian mechanism adds i.i.d. Gaussian noise to W p with scale parameter σ i.e., M(p) = W p + σ∆ 2 (W )N (0, I), where I is the m × m identity matrix. Then the Gaussian Mechanism satisfies 1 2σ 2 -zCDP. Proposition 6 (zCDP of correlated Gaussian mechanism; [33] ). Let W be an m × n workload. Given data vector p, the correlated Gaussian mechanism adds Gaussian noise to W p with covariance matrix Σ i.e., M(p) = M p + N (0, Σ). The correlated Gaussian mechanism satisfies γ 2 -zCDP where γ is the largest diagonal element of M ⊤ Σ -1 M . Proposition 7 (zCDP of exponential mechanism; [34, 35] ). Let ϵ > 0 and Score r : X → R be a quality score of candidate r ∈ R for data vector p. Then the exponential mechanism outputs a candidate r ∈ R according to the following distribution: Pr(M(p) = r) ∝ exp ϵ 2∆1 Score r (p) . The exponential mechanism satisfies ϵ 2 8 -zCDP.Adaptive composition and post-processing are two important properties of differential privacy that allow us to construct complex mechanisms from the above building blocks. Let us state these results for zCDP. Proposition 8 (zCDP Properties; [31, 35] ). zCDP satisfies these two properties of differential privacy:1. (Adaptive Composition) Let M 1 : X → Y 1 satisfy ρ 1 -zCDP and M 2 : X × Y 1 → Y 2 satisfy ρ 2 -zCDP. The mechanism p → M 2 (p, M 1 (p)) satisfies (ρ 1 + ρ 2 )-zCDP. 2. (Post-processing) Let M 1 : X → Y satisfy ρ-zCDP and f : Y → Z be a randomized algorithm. Then M : X → Z = f • M 1 satisfies ρ-zCDP.In this section, we prove Proposition 1, which provides a relationship between marginals and residuals. Before proving this result, let us consider residual workloads as well as the subtraction matrix D (k) .Let us state some properties of residuals. Proposition 9 (Residual Properties; [6, 13, 14] ). Let Ω be the set of all tuples of attributes for a given data universe X .1. R τ is an m τ × n matrix with full row rank.2. R τ , R τ ′ are mutually orthogonal for τ ̸ = τ ′ i.e. R τ R ⊤ τ ′ = 0. 3. R τ , M τ ′ are mutually orthogonal for τ ̸ ⊆ τ ′ i.e. R τ M ⊤ τ ′ = 0. 4. (R τ ) τ ∈Ω spans R n .Lemma 2. Data vector p ∈ R n can be decomposed uniquely as follows:p = τ ∈Ω R ⊤ τ v τ for v τ ∈ R mτ . Proof. Let p τ = R + τ R τ p be the projection of p onto the row-space of R τ . By Proposition 9, p = τ ∈Ω p τ . Let v τ ∈ R mτ be such that p τ = R ⊤ τ v τ . Since R τ is full row rank, v τ is unique. Now, let us consider D + (k) . Recall that D (k) is an n k -1 × n k matrix given by D (k) =     1 -1 0 • • • 0 0 1 -1 • • • 0 . . . . . . . . . . . . 0 • • • • • • 1 -1     .The pseudoinverse of D (k) is known in closed-form:D + (k) = 1 n k       n k -1 n k -2 • • • 1 -1 n k -2 • • • 1 -1 -2 • • • 1 . . . . . . . . . -1 -2 • • • -(n k -1)       = ( 1 /n k )(1 k u ⊤ k -n k C k ),whereu k =     n k -1 n k -2 . . . 1     and C k is the n k × n k -1 lower triangular matrix of ones.Continuing the example from Fig. 1 ,D (k) = 1 -1 0 0 1 -1 D + (k) = 1 3 2 1 -1 1 -1 -2 . Proposition 1. Let R S = (R τ ) τ ∈Sbe a combined workload of residual queries for all τ in a collection S ⊆ 2 [d] , where the individual matrices R τ are stacked vertically. The size of R S is m × n where m = τ ∈S m τ . Then for any z = (z τ ) τ ∈S ∈ R m and any γ, it holds thatM γ R + S z = τ ∈S,τ ⊆γ A γ,τ z τ , where A γ,τ := d k=1      D + (k) k ∈ τ 1 /n k 1 k k ∈ γ \ τ 1 k / ∈ γ for τ ⊆ γ.The matrix A γ,τ has size n γ × m τ and maps from the space of τ -residuals to the space of γ-marginals.The running time to compute A γ,τ z τ is O(|γ|n γ ).Proof of Proposition 1. First note that R + S is the pseudoinverse of a block matrix. In general the pseudoinverse of a vertical block matrix involves the pseudoinverse of each block multiplied by a projection matrix [36] . In this case each block is a residual query, as discussed in Proposition 9, these query matrices are mutually orthogonal so the pseudoinverse R + S has the form (R + τ ) T τ ∈S . Here, the combined query matrix R S is constructed by stacking the blocks R τ vertically and the combined pseudoinverse R + S stacks the blocks R + τ horizontally. Given this block structure of R + S we can writeEQUATIONAnother relevant property of residual queries given in Proposition 9 is that R τ M ⊤ τ ′ = 0 for τ ̸ ⊆ τ ′ . When we drop these orthogonal queries from the summation, we getM γ R + S z = τ ∈S,τ ⊆γ M γ R + τ z τ .When computing the product M γ R + τ , several properties of Kronecker products given in Proposition 3 are relevant. The first is that (A ⊗ B) + = A + ⊗ B + . Applying this property givesEQUATIONThe next property is that when when A and B both have compatible Kronecker structure, AB = i A i B i . Both M γ and R + τ have compatible Kronecker structure so we can writeEQUATION)To evaluate this, notice that(1 T k ) + = 1 k (1 T k 1 k ) -1 = 1 k /n k and 1 ⊤ k (1 k /n k ) = 1.EQUATIONFinally, this gives the full result that M γ R + S z = τ ∈S,τ ⊆γ A γ,τ z τ .We prove the time complexity result for A γ,τ z τ in Appendix E.In this section, we prove results related to ReM from Sections 3 and 4. Theorem 1. Suppose ατ minimizes L τ (α τ ) over R mτ for each τ ∈ S and let α = (α τ ) τ ∈S . Then Alg. 2 outputs μγ = M γ p, where p = R + S α is a global minimizer of the combined loss functionτ ∈S L τ (R τ p) over R n .Proof. Suppose ατ minimizes L τ for all τ and let p = R + S α. Then for anyEQUATIONWe will justify Equality (⋆) below. The inequality holds because ατ minimizes L τ . Thus, Equation (7) shows that p minimizes the combined loss τ ∈S L τ (R τ p).To justify Equality (⋆), first observe that R S R + S α = α because R S has full row rank and thus R S R + S = I. We can see R S has full row rank by Proposition 9: each block of rows corresponding to one residual has full row rank and these blocks are orthogonal. The equality R τ R + S α = ατ is obtained by selecting the block of rows corresponding to residual τ from the equality R S R + S α = α.Lemma 1. For τ ⊆ γ, the residual R τ can be recovered from the marginal M γ asR τ = A + γ,τ M γ where A + γ,τ = d k=1    D (k) k ∈ τ 1 T k k ∈ γ \ τ 1 k / ∈ γ . Proof of Lemma 1. Recall that we defined A γ,τ = M γ R + τ . Then A + γ,τ = R τ M + γ .Observe the following:A + γ,τ M γ = d k=1    D (k) I k k ∈ τ 1 ⊤ k I k k ∈ γ \ τ 1 • 1 ⊤ k k / ∈ γ = d k=1 D (k) k ∈ τ 1 ⊤ k k / ∈ τ = R τTheorem 2. Let y γ ∼ N (M γ p, σ 2 I) be a noisy marginal measurement with isotropic Gaussian noise and let z τ = A + γ,τ y γ for each τ ⊆ γ. Then noisy residual z τ has distributionN (R τ p, σ 2 D τ D ⊤ τ k∈γ\τ n k ) and z τ is independent of z τ ′ for τ ̸ = τ ′ .Furthermore, let H γ = (A + γ,τ ) τ ⊆γ be the matrix mapping from y γ to (z τ ) τ ⊆γ . This matrix is invertible, which implies thatEQUATIONProof of Theorem 2. Since y τ ∼ N (M γ p, σ2 I) and z τ = A + γ,τ y τ , standard properties of normal distributions give that z τ ∼ N (A + γ,τ M γ p, σ 2 A + γ,τ (A + γ,τ ) ⊤ ). By Lemma 1, the mean is equal to R τ p, as stated. For the covarianceA + γ,τ (A + γ,τ ) ⊤ =      D (k) D ⊤ (k) k ∈ τ 1 ⊤ k 1 k k ∈ γ \ τ 1 k / ∈ γ = k∈γ\τ n k • d k=1 D (k) D ⊤ (k) k ∈ τ 1 k / ∈ τ = D τ D ⊤ τ k∈γ\τ n k so the covariance is σ 2 D τ D ⊤ τ k∈γ\τ n k , as stated.For τ ̸ = τ ′ the vectors z τ and z τ ′ are jointly normal with covariance σ 2 A + γ,τ (A + γ,τ ′ ) ⊤ . We will show that A + γ,τ (A + γ,τ ′ ) ⊤ is a matrix of zeros, so the covariance matrix is identically zero and the vectors are independent. By the Kronecker structure,A + γ,τ (A + γ,τ ′ ) ⊤ = d k=1              D (k) D ⊤ (k) k ∈ τ ∩ τ ′ 1 ⊤ k D ⊤ (k) k ∈ τ ′ \ τ D (k) 1 k k ∈ τ \ τ ′ 1 ⊤ k 1 k k ∈ γ \ (τ ∪ τ ′ ) 1 k / ∈ γObserve that D (k) 1 k = 0 is a vector of zeros because the rows of D (k) sum to zero, and similarly1 ⊤ k D ⊤ (k)is a row vector of zeros. Thus, any k in the symmetric difference (τ ′ \ τ ) ∪ (τ \ τ ′ ) will contribute an all zeros matrix to the Kronecker product and cause A + γ,τ (A + γ,τ ′ ) ⊤ to be an all zeros matrix. But there must be at least one k in the symmetric difference because τ ̸ = τ ′ . This proves that the covariance matrix is identically zero, as desired.We will next show that the mapping H γ is invertible. H γ is a matrix with blocks A + γ,τ for each τ ⊆ γ, stacked vertically, and n γ = k∈γ n k columns. From the definition of the block A + γ,τ , we can see it has m τ = k∈τ (n k -1) rows and is of full row rank because D (k) is a full rank matrix with n k -1 rows and the other matrices in the Kronecker product have only one row. We showed above that A + γ,τ (A + γ,τ ′ ) ⊤ = 0 for τ ̸ = τ ′ , 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 τ ⊆γ m τ = τ ⊆γ k∈τ (n k -1) = k∈γ n k = n γ , which equals the number of columns, and therefore H γ invertible. 2 Now, given what we have shown so far, we will write two different expressions for the log-probability density function log p z (z) where z = (z τ ) τ ⊆γ . First, we have already derived the joint multivariate distribution of z, which, due to independence, has log-densitylog p z (z) = τ ⊆γ log N z τ R τ p, σ 2 D τ D ⊤ τ k∈γ\τ n k .Second, because z = H γ y γ for the multivariate normal random variable y γ , the change of variable formula for probability densities gives thatlog p z (z) = log N (y γ |M γ p, σ 2 I) -log | det H γ |.Equating these two expressions gives Equation ( 1), which completes the proof.Theorem 3 (Efficient pseudoinversion of marginal query matrix). Let M Q = (M γ ) γ∈Q be the query matrix for a multiset Q of marginals and let y = (y γ ) γ∈Q be corresponding noisy marginal measurements with y γ = M γ p + N (0, σ 2 I). Let S = {τ ⊆ γ : γ ∈ Q} and for each τ ∈ S let γ τ,i be the ith marginal in Q containing τ . Let z τ,i = A + γτ,i,τ y γτ,i be the residual measurement obtained from γ τ,i and let Σ τ,i = σ 2 τ,i D τ D ⊤ τ be its covariance where σ 2 τ,i = σ 2 k∈γτ,i\τ n k . Then, given any workload of marginal queries W, for each γ ∈ W, the marginal reconstruction μγ obtained from Algorithm 3 on these residual measurements is equal toM γ M + Q y.Proof. By standard properties of the pseudoinverse, M + Q y is the unique vector that minimizes SE(p) = ∥M Q p -y∥ 2 2 and is in the row span of M Q . We will show that the vector R + S α satisfies both properties, where α = ( ατ ) τ ∈S is constructed in Algorithm 3, and thus R + S α = M + Q y. Then, by Proposition 1, the reconstructed marginal μγ in Algorithm 3 is equal to M γ R + S α and hence also equal to M γ M + Q y, as claimed. We will first show R + S α minimizes SE(p). Observe that the SE(p) is equivalent to the negative log-likelihood L y (p) of the marginal measurements y:SE(p) = ∥M Q p -y∥ 2 2 = γ∈Q ∥M γ p -y γ ∥ 2 2 = -2σ 2 γ∈Q log N (y γ |M γ p, σ 2 I) + const. = 2σ 2 L y (p) + const.Therefore SE(p) and L y (p) have the same minimizers.Then, by Theorem 2,L y (p) = γ∈Q -log N (y γ |M γ p, σ 2 I) = γ∈Q τ ⊆γ -log N (A + γ,τ y τ | R τ p, σ 2 k∈γ\τ n k • D γ D ⊤ γ ) + const. = τ ∈S kτ i=1 -log N (z τ,i | R τ p, σ 2 τ,i D γ D ⊤ γ ) Lz(p) + const.where in the final line we rearranged terms using the notation of the theorem statement.Therefore, SE(p), L y (p) and L z (p) all have the same minimizers.Furthermore, L z (p) decomposes over residual measurements asL z (p) = τ ∈S L τ (R τ p) where L τ (α τ ) = kτ i=1 -log N (z τ,i | α τ , σ 2 τ,i D γ D ⊤ γ ). Therefore, Theorem 1 allows us to minimize each term separately. Algorithm 3 finds ατ to minimize L τ (α τ ) for each τ ∈ S using inverse variance weighting. Then, by Theorem 1, the vector R + S α is a minimizer of L z (p), and therefore also a minimizer of SE(p). 3 The final inclusion is true by Lemma 1, since for each τ ∈ S we havethat R + S α ∈ row(M Q ). This is true because R + S α ∈ col(R + S ) = row(R S ) ⊆ row(M Q ).R τ = A + γ,τ M γ for some γ ∈ Q. (b) if A i = D + (k) , then iteration i takes O i-1 j=1 a j ℓ h=i b h time, where b i = n k -1. (c) if A i = D (k) , then iteration i takes O i j=1 a j ℓ h=i+1 b h time, where a i = n k -1.Proof. At iteration i of Alg. 5, A i is multiplied by a matrix Z with size bi × i-1 j=1 a j ℓ h=i+1 b h . Then each row in A i requires b i i-1 j=1 a j ℓ h=i+1 b h = i-1 j=1 a j ℓ h=i b h scalar multiplications.Since A i has a i rows, this yields i j=1 a j ℓ h=i b h multiplications over all rows. This proves (a).Suppose A i = D + (k) . Recall that D + (k) = ( 1 /n k )(1 k u ⊤ k -n k C k ).We claim that computing D + (k) v for any vector v takes O(n k ) time. C k v is a cumulative sum of the elements of v and u ⊤ k v is a dot product, both of which take O(n k ) time to compute. The remaining steps cost 2(n k -1) multiplications and n k -1 sums. Thus each column of Z can be multiplied by Proof. Let us first consider the running time of A γ,τ z τ for some τ ⊆ γ. Recall that A γ,τ can be written as follows:A i in O(n k ) time. Since Z has i-1 j=1 a j ℓ h=i+1 b h columns, computing A i Z takes O b i i-1 j=1 a j ℓ k=i+1 b k = O i-1 j=1 a j ℓ k=i b k time, where b i = n k -1. This proves (b). Suppose A i = D (k) . For vector v, D (k) v is the difference of consecutive elements of v, which takes O(n k ) time to compute. Thus each column of Z can be multiplied by A i with n k -1 operations. Since Z has i-1 j=1 a j ℓ h=i+1 b h columns, computing A i Z takes O a i i-1 j=1 a j ℓ k=i+1 b k = O i j=1 a j ℓ k=i+1 b k time, where a i = n k -1. This proves (c).If A i = D (k) , then iteration i is O i j=1 a j ℓ h=i+1 b h by Lemma 4 (c). If a i = 1, then iteration i is O i-1 j=1 a jA γ,τ := k∈γ D + (k) k ∈ τ 1 /n k 1 k k ∈ γ \ τSince A γ,τ satisfies the conditions of Lemma 5 and has n γ rows, computing A γ,τ z τ takes O(|γ|n γ ) time. Recall from Proposition 1 that reconstructing an answer to marginal M γ is given by τ ∈S,τ ⊆γ A γ,τ y τ . The number of terms in the summation is at most 2 |γ| , so the total running time of reconstructing an answer to M γ is O(|γ|n γ 2 |γ| ). This proves (a).For (b), let ϵ > 0 and consider the following quotient:|γ|n γ 2 |γ| |γ|n 1+ϵ γ = 2 |γ| n ϵ γ = 2 |γ| i∈γ n ϵ i .Taking the limit as n i → ∞, the quotient tends to zero and we obtain the desired result.With GReM-MLE, each residual query R τ , τ ∈ S can have multiple measurements y τ,1 , . . . , y τ,kτ but with proportional covariances. For each τ ∈ S, we combine the measurements using inverse variance weighting to obtain ατ . We then reconstruct the marginals M γ for γ ∈ W using the residual answers ατ for τ ∈ S. By (a), the running time is O( γ∈W |γ|n γ 2 |γ| ). 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 a consists of elements of W ↓ and each γ ∈ W ↓ appears in Q at most b times. For each γ ∈ Q, we decompose the marginal measurements into residual measurements by computing A + γ,τ y γ for each τ ⊆ γ. By Lemma 5 (b), computing A + γ,τ y γ takes O(|γ|n γ ) time. Then the running time of decomposing the marginal measurements is O( γ∈Q |γ|n γ 2 |γ| ). From (c), the running time of GReM-MLE is O( γ∈W |γ|n γ 2 |γ| ). Given that the running time of decomposition is at most a multiple of the running time of GReM-MLE, O( γ∈W |γ|n γ 2 |γ| ). This proves (d).Let us turn to the running 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 τ ′ ∈ W ↓ \ S, and reconstructing answers to marginals M γ for γ ∈ W.First consider the case where τ ∈ S. Recall that in this case ατ =kτ i=1 K -1 τ,i -1 kτ i=1 K -1 τ,i y τ,i + γ⊇τ A T γ,τ λ γ , where K τ,i = σ 2 τ D τ D T τ .We can rewrite ατ as follows:ατ = γ⊇τ σ -2 τ -1 γ⊇τ σ -2 τ y τ,i + γ⊇τ σ -2 τ D τ D T τ γ⊇τ A T γ,τ λ γ .The left summand requires no matrix multiplications and does not depend on λ. Then computing A T γ,τ λ γ takes O |γ|n γ ) time. The right summand is obtained by computing A T γ,τ λ γ for each γ ⊇ τ . Then computing ατ for τ ∈ S takes O( γ⊇τ |γ|n γ ) time.τ ∈ W ↓ \ S. Then α = -( 1 /2)(A T τ,τ A τ,τ ) -1 γ⊇τ A T γ,τ λ γ .As with the prior case, the desired term requires computing A T γ,τ λ γ for each γ ⊇ τ . Then computing ατ forτ ∈ W ↓ \ S is O( γ⊇τ |γ|n γ ).Combing these results, computing ατ for τ ∈ W ↓ is O( τ ∈W ↓ γ⊇τ |γ|n γ ). Observe that for each γ ∈ W, there are 2 |γ| terms in the summation. By indexing the summation in terms of γ, we obtain that computing α is O( γ∈W |γ|n γ 2 |γ| ). The remaining step of GReM-LNN is to reconstruct answers to marginals M γ for γ ∈ W. By (a), the running time is O( γ∈W |γ|n γ 2 |γ| ). This proves (e).Recall that GReM-LNN solves the following convex program:EQUATIONInput: Marginal workload W, residual workload S, residual measurements z, rounds T , step size s, Lagrangian initialization λ, regularization weight η 1: Initialize λ γ = λ for γ ∈ W 2: for t = 1, . . . , T do3: Set α τ = kτ i=1 K τ,i -1 ( kτ i=1 K -1 τ,i y τ,i -γ⊇τ A ⊤ γτ λ γ ) for τ ∈ S 4:Setα τ = -1 /2η A ⊤ τ τ A τ τ -1 ( γ⊇τ A ⊤ γτ λ γ ) ⊤ for τ ∈ W ↓ \ S 5: Calculate µ γ (α) = τ ⊆γ A γτ α τ for γ ∈ W 6:Updateλ γ = min{λ γ + sµ γ (α),0} for γ ∈ W for K τ,i = 2 |τ | D τ D T τ .Observe that the program in Eq. 8 only depends on unmeasured residuals in W ↓ through the local non-negativity constraint. To make this problem more tractable and the solution more stable, we introduce a regularization term to limit the contribution of unmeasured residuals to reconstructed marginals:EQUATIONNote that the introduction the regularization term in Eq. ( 9) is only relevant to the underdetermined case, since, otherwise, W ↓ ⊆ 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 asf (α) = τ ∈S kτ i=1 (α τ -z τ,i ) ⊤ K -1 τ,i (α τ -z τ,i ) + η ν∈W ↓ \S ∥A νν α ν ∥ 2 2and the constraint as µ(α) = (µ γ (α)) γ∈W = ( τ ⊆γ A γτ α τ ) γ∈W ≥ 0. Then the Lagrangian function is given byL(α, λ) = f (α) + λ ⊤ µ(α) = τ ∈S kτ i=1 (α τ -z τ,i ) ⊤ K -1 τ,i (α τ -z τ,i ) + η ν∈W ↓ \S ∥A νν α ν ∥ 2 2 + γ∈W λ ⊤ γ τ ⊆γ A γτ α τwhere λ = (λ γ ) γ∈W is the dual variable or Lagrangian multiplier and is constrained such that λ ≤ 0.The dual function is given by g(λ) = min α L(α, λ) and the dual problem is given by max λ≤0 g(λ).Under suitable regularity conditions, the optimal value of the dual problem is equivalent to the optimal value of the primal problem. We can solve both by maximizing the dual function g to obtain λ * and then minimizing the Lagrangian L(α, λ * ) with respect to α to obtain α * .We can solve for each α * τ in closed form for τ ∈ W ↓ . Minimizing the Lagrangian L(α, λ * ) with respect to α corresponds to minimizing an unconstrained quadratic objective and can be solved separately for each τ . To see this, let us fix λ and solve for the critical point of L(α, λ). If τ ∈ S, then gradient of L with respect to α τ is given by∇ ατ L(α, λ) = kτ i=1 K -1 τ,i (α τ -z τ,i ) + γ⊇τ A ⊤ γτ λ γ .Setting this to zero and solving for α * τ yieldsα * τ = kτ i=1 K -1 τ,i -1 kτ i=1 K -1 τ,i z τ,i - γ⊇τ A ⊤ γτ λ γ .Input: Marginal workload W, privacy budget (ϵ, δ), initialization parameter α1: Choose ρ such that min α>1 exp((α-1)(αρ-ϵ)) α-1 1 -1 α α = δ 2: Set σ 2 0 , σ 2 = 1 2αρ , T (1-α)ρ 3: Initialize measurements y = {M ∅ p + ξ 0 } with ξ 0 ∼ N (0, σ 2 0 I) and multiset Q = {∅} 4: Initialize (μ γ ) γ∈W = EMP(W, Q, y) 5: for t = 1, . . . , T do 6:Select γ t with the exponential mechanism using (1-α)ρ 2T budget according to Score(p, γ, Y ) = ∥M γ p -μγ ∥ 1 ∀γ ∈ W 7: Measure y t = M γt p + ξ t where ξ t ∼ N (0, σ 2 I) and set Q = Q ∪ {γ t } 8:Reconstruct (μ γ ) γ∈W = EMP(W, Q, y) return noisy answers (μ γ ) γ∈W , noisy measurements y Now, suppose τ ∈ W ↓ \ S. Then gradient of L with respect to α τ is given by∇ ατ L(α, λ) = 2ηα ⊤ τ A ⊤ τ τ A τ τ + γ⊇τ A ⊤ γτ λ γ .Setting this to zero and solving for α * τ yieldsα * τ = -1 /2η A ⊤ τ τ A τ τ -1 γ⊇τ A ⊤ γτ λ γ ⊤ .To update λ, we set λ * = min{λ + tµ(α * ), 0} where t > 0 is the step size. This can be seen as projected gradient ascent on g(λ) since µ(α * ) = ∇ λ L(α * , λ) = ∇ λ g(λ).The multiplicative weights exponential mechanism (MWEM) [15] is a canonical data-dependent mechanism that maintains a 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-dimensional data domains without adopting parametric assumptions. In this section, we propose an MWEM-style algorithm called Scalable MWEM (Alg. 7) that employs a standard reconstruction approach, the pseudoinverse of the measured marginal queries, but scales to high-dimensional data domains.In general, the pseudoinverse is infeasible as a reconstruction method for large data domains. Computing the pseudoinverse Q + of an arbitrary query matrix Q scales exponentially in the number of attributes and linearly in size of the data vector. Moreover, even storing the reconstructed data vector p = Q + y from noisy answers y in memory presents a 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 a predetermined fraction of the privacy budget to measure the total query i.e. the 0-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 a marginal γ ∈ 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 to reconstruct answers to marginals in W. Being a full query answering mechanism rather than just a reconstruction method, let us show that Scalable MWEM satisfies differential privacy. Theorem 7. Scalable MWEM satisfies (ϵ, δ)-DP.Proof. We will refer to Algorithm 7 as M. Note that M selects a parameter ρ such that δ = min α>1 exp((α-1)(αρ-ϵ)) α-11 -1 α α . By proposition 4, it suffices to show that M satisfies ρ-zCDP, then it also satisfies (ϵ, δ)-DP. In the initialization step, M measures M ∅ p with the Gaussian mechanism using the noise scale σ 2 o = 1 2αρ . The query M ∅ p is the total query, so it has an ℓ 2 sensitivity of 1 and therefore by proposition 5, this measurement satisfies 1 2σ 2 o = 2αρ 2 = αρ-zCDP. In each round, M runs the exponential mechanism such that it satisfies (1-α)ρ 2T -zCDP. Also in each round, M runs the Gaussian mechanism to measure a marginal query with noise scale σ 2 = T (1-α)ρ . All marginal queries have an ℓ 2 sensitivity of 1 so again by proposition 5, this measurement satisfies1 2σ 2 o = (1-α)ρ2T -zCDP. By the adaptive composition result given in proposition 8, the overall mechanism satisfies αρ + T ( (1-α)ρ 2T + (1-α)ρ 2T ) = ρ-zCDP and also (ϵ, δ)-DP.Datasets. In general, we follow the preprocessing steps described in [7] . All attributes in the datasets are discrete. We identify the data domain by inferring the possible values for each attribute from the observed values for each attribute.Titanic [23] contains 9 attributes, 1, 304 records, and has data vector size 8.9 × 10 7 . Adult [24] contains 14 attributes, 48, 842 records, and has data vector size 9.8 × 10 17 . Salary [25] contains 9 attributes, 135, 727 records, and has data vector size 1.3 × 10 13 . Nist-Taxi [26] has 10 attributes, 223, 551 records, and has data vector size 1.9 × 10 13 .Compute Environment. All experiments were run on an internal compute cluster with two CPU cores and 20GB of memory.GReM-LNN Hyperparameters. For the ResidualPlanner experiments in Section 5.1, we set the hyperparameters as follows: the maximum number of rounds T = 4000, the Lagrangian initialization parameter λ = -1, and the step size s = 0.1. For the Scalable MWEM experiments in Section 5.2, we set the hyperparameters as follows: the maximum number of rounds T = 1000, the Lagrangian initialization parameter λ = -1, the step size s = 0.02, and regularization weight η = 40. For all experiments, if Alg. 6 fails, we divide the step size by √ 10 and rerun until convergence. We additionally impose a time limit of 24H on a given run of Alg. 6.In this section, we detail additional experimental results. For the ResidualPlanner experiment, we report ℓ 2 workload error for the reconstruction methods. For the Scalable MWEM experiment, we report ℓ 2 workload error for the reconstruction methods as well as whether or not Private-PGM successfully ran across various settings. 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 no 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 a 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: We do not release any data or 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 no such risks.• Released models that have a high risk for misuse or dual-use 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 a best faith effort. 12. Licenses for existing assets Question: 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? 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 use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-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 creators. 
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 we provide at time of submission is well documented, it does not currently include a license but at the time that the code is made public on GitHub it will include a license. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model 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 is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.Note that our matrix Dτ is slightly different from the operator used in[6] but has the same row space[14].To see that τ ⊆γ k∈τ (n k -1) = k∈γ n k , observe that nγ = k∈γ n k counts the number of ways to map each k ∈ γ to a value i ∈ {1, . . . , n k }. Equivalently, we may consider selecting a subset τ ⊆ γ, assigning each k ∈ τ to the value 1, and then assigning each k / ∈ τ to one of the remaining values in {2, . . . , n k }. The number of ways to do this is τ ⊆γ k∈τ (n k -1) = k∈γ n k .In fact row(RS ) = row(MQ) but we only need the inclusion. 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: The limitations are adequately addressed.
paper_summary: paper_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. 

This 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. 

The 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).
strength_weakness: strength_weakness: 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. 

For 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. 

Another 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.
questions: questions: See two questions in weaknesses section.
limitations: limitations: I think the authors’ treatment of limitations covers most bases I would consider.
paper_summary: paper_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 
1. translate the marginal workload queries to their equivalent residual queries representation, and compute their noisy measurements
2. exploiting the structure of residual query matrix to perform efficient pseudoinverse via Kronecker product
3. 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

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

2. 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.

3. 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.


[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.
questions: 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)?

2. Could the authors explain more about the lack of comparison with other reconstruction methods (weakness 3)?
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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?
questions: 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.

2. Could you clarify why "when the marginal is observed with isotropic noise, the corresponding noisy residuals are independent"? (Line 239, Page 6)
limitations: limitations: Yes.

Comments: comment: Thank you for addressing my question. My score remains unchanged.
I'm glad to hear the paper motivation will be revised. The examples of repeated measurements of a single residual in the global response clarified things for me.