Efficient and Private Marginal Reconstruction with Local Non-Negativity

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.

Strengths

1. This paper presents ReM, a new approach to constructing marginals from residuals. 2. ReM reduces errors compared to some baseline methods. 3. 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. 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

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)

Rating

3

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

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.

Strengths

- An interesting idea of using the residual basis of query matrix to efficiently represent and compute pseudoinverse matrix for marginal reconstruction. - 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. - 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. 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

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)?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

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

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

See two questions in weaknesses section.

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

I think the authors’ treatment of limitations covers most bases I would consider.

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.

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.

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.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitations are adequately addressed.