An Optimal and Scalable Matrix Mechanism for Noisy Marginals under Convex Loss Functions
Authors: Yingtai Xiao
Guanlin He
Danfeng Zhang
Daniel Kifer
Venue: NeurIPS 2023 spotlight (2023)
Keywords: differential privacy
marginals
matrix mechanism
scalability
TL;DR: An optimal and extremely scalable algorithm for differentially private marginals with unbiased noise, exact variance/covariance guarantees and customizable loss function

Abstract: Noisy marginals are a common form of confidentiality-protecting data release and are useful for many downstream tasks such as contingency table analysis, construction of Bayesian networks, and even synthetic data generation. Privacy mechanisms that provide unbiased noisy answers to linear queries (such as marginals) are known as matrix mechanisms.

We propose ResidualPlanner, a matrix mechanism for marginals with Gaussian noise that is both optimal and scalable. ResidualPlanner can optimize for many loss functions that can be written as a convex function of marginal variances (prior work was restricted to just one predefined objective function). ResidualPlanner can optimize the accuracy of marginals in large scale settings in seconds, even when the previous state of the art (HDMM) runs out of memory. It even runs on datasets with 100 attributes in a couple of minutes. Furthermore ResidualPlanner can efficiently compute variance/covariance values for each marginal (prior methods quickly run out of memory, even for relatively small datasets).

An Optimal and Scalable Matrix Mechanism for Noisy Marginals under Convex Loss Functions
Yingtai Xiao Penn State University yxx52240psu. edu
Guanlin He Penn State University
Danfeng Zhang Penn State University dbz5017@psu. edu
Daniel Kifer Penn State University duk170psu. edu
gbh51460psu.
Abstract
Noisy marginals common form of confidentiality-proteee proteecinn data release and are useful for many downstream tasks such as contingency table analysis, construc- tion of Bayesian networks, and even synthetic data generation. Privacy mechanisms that provide unbiased noisy answers to linear queries (such as marginals) are known matrix mechanisms.
We propose ResidualPlanner, matrix mechanism for marginals with Gaussian noise that is both optimal and scalable. ResidualPlanner can optimize for many loss functions that can be written as a convex function of marginal variances (prior work was restricted to just one predefined objective function). ResidualPlanner can optimize the accuracy of marginals in large scale settings seconds, even when the previous state of the art (HDMM) runs out of memory. It even runs on datasets with 100 attributes in a couple of minutes. Furthermore ResidualPlanner can efficiently compute variance/covariance values for each marginal (prior methods quickly run out of memory, even for relatively small datasets).
Introduction
Marginals are tables of counts on of attributes (e.g., how many people there are for each combination of race and gender). They are one of the most common formats for the dissemination of statistical data [8, 2], studying correlations between attributes, and sufficient statistics for loglinear models, including Bayesian networks and Markov random fields. For this reason, a lot of work in the differential privacy literature has considered how to produce set of noisy marginals that is both preccvypres and accurate.
One line of work, called the matrix mechanism [32, 52, 30, 53, 37, 51, 46, 18, 42] designs algorithms noisy answers are
for answering linear queries (such as marginals) so that the privacy-preservinn accurate, unbiased, and have simple distribution (e.g., multivariate normal). These crucial properties allow statisticians to work with the data, model error due to data collection (sampling error) and error due to privacy protections. It enables valid confidence intervals and hypothesis other methods for quantifying the uncertainty of a statistical analysis (e.g.. [20, 29, 50, 25, 26]). Incidentally, sets of noisy marginals are also used to generate differentially private synthetic data (e.g., [54, 4, 41. 10]).
and
For the case of marginals, significant effort has been spent in designing optimal nearly optimal matrix mechanisms for just single objective function (total variance of all the desired marginals) [32, 49, 13, 52, 53, 31, 51] and each new objective function requires significant additional effort [6. 18, 42, 46]. However, existing optimal solutions do not scale and additional effort is needed to design scalable, but suboptimal, matrix mechanisms for marginals [37, 38). This is because prior work used mathematical properties specific to their chosen objective function in order to improve runtime. Furthermore, computing the individual variances of the desired noisy marginals is slow process and more difficult is computing the covariance between cells in the same marginal.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Contributions. Our paper addresses these problems with novel matrix mechanisms called Resid- ualPlanner. can optimize for a wide variety of convex objective functions and return solutions that are guaranteed to be optimal under Gaussian noise. It is highly scalable running in seconds even when other scalable algorithms run out of memory. also efficiently returns the variance and covariances of each cell of the desired marginals. It leverages the following insights. Since a dataset can be represented as a vector x of counts, and since a marginal query on a set A of attributes can be represented matrix QA (with QA being the true answer to the marginal query), we find new linearly independent basis that can parsimoniously represent both a marginal QA and the "difference" between two marginals QA and QA (subspace spanned by the rows of QA that is orthogonal to the rows of .. Using parsimonious linear bases, instead of overparametrized mechanisms, accounts for the scalability. Optimality results from deep analysis of the symmetry that marginals impose on the optimal solution - the same linear basis is optimal for a wide variety of loss functions. Our code is available at https: /et:://gittttt github. com commdkifer Res wwriiiaallaammaaa Panner.
2 Preliminaries
01,1
21,4g
The Kronecker product between a b x l2 matrix V
and an & x l matrix W, denoted by V W, is the kzl x kzl2 matrix that can be represented block matrix form as: W
Plg Ag
k1 W
A dataset D = (r [nn J a collection of records (there is exactly one
P Vel by record for each individual in the dataset). Every record rt contains nt, attributes , All,, and ())
Au,1" An attribute value at for attribute Att, can be each attribute Att, can take values aj a
represented as a vector using one-hot encoding. Specifically, let c( be a row vector of size |Att, with a 1 in component i and 0 everywhere else. In this way c, represents the attribute value a. record r with attributes Att = a; Attt = Attt. (na)
(1)
(2)
(m.) can thus be represented = a...
i2 8 ... ..... Bein. This vector has a in exactly one position and Os everywhere else. The position of the 1 is the index of record With this notation, a dataset D can be represented as a vector x of integers. The value at index i is the number times the record associated with index appears in D. The number of components in this vector is denoted as d = th Att,]. Given a subset of attributes, marginal query on A a table of counts: for each combination of values for the attributes in A, it provides the number of records in 'D having those attribute value combinations. The marginal query can be represented as a Kronecker product QA V1@ V,,, where V; is the row vector of all ones (i.e, 1 I'Au,,) if Att, & A and V, the identity matrix I| if Att, E A. The answer to the marginal query is obtained by evaluating the matrix -vector product A For convenience, the notation introduced in this paper is summarized as table in Section A the supplementary material.
as the Kronecker product es ge,
(1)
EXAMPLE 2.1. As rumning example, consider a dataset in which there are two attributes: Att with values "yes" and "no", and Attz with values "low", "med", "high". The record (no, med) represented by the kron product [o1] [o o] and the marginal query on the set A = Attt,} is represented as (AuC)
[ 11 @ 1 1]. Similarly, the marginal on altribute All2 is represented as
((A)))) [11] X
The query representing all one-way marginals is obtained by stacking
1001
them: Q" iuwway
and Q' !-way x consists of the five query answers (number of records with Att yes, number with Att, no, number with Attz =low, etc.).
((4M))
((A))))
2.1 Differential Privacy
mechanism M an algorithm whose input is dataset and whose output provides privacy protec- tions. Differential privacy is family of privacy definitions that guide the behavior of mechanisms so that they can inject enough noise to mask the effects of any individual. There are many versions of differential privacy that support Gaussian noise, including approximate DP, zCDP, and Gaussian DP.
2

---

DEFINITION 2.2 (Differential Privacy). Let M be mechanism. For every pair of datasets D1. D2 that differ on the presence/absence of a single record and for all (measurable) sets S &rangeMM (M).
If P(M(D)) E E S P(M((D2) E 5) 5)+6 5 then M satisfies -apprrximit differential privacy [17]:
If (P((()) E S)) S (PM(P() E 5)) + n4, where 4 is the cdf of the standard Gaussian distribution, then M satisfies p- u-Gaussian DP [15].
If the Rényi divergence D (M(D:M))MMM))))))
between the output distributions of MM(1)) and M(D2) satisfies Do (MM((i)))M((aa) S pa for all L, then M satisfies p-zCDP [7].
Queries that are linear functions of the data vector x can be answered privately using the linear Gaussian mechanism, which adds correlated Gaussian noise to linear function of x, as follows.
DEFINITION 2.3 (Linear Gaussian Mechanism [46]). Given a m x matrix B and m x m covariance
matrix Σ, the (correlated) linear Gaussian mechanism M is defined as M(x) = Bx + N E). The privacy cost matrix of M is defined as B² E The privacy cost of M, denoted by (M)st(M), is the largest diagonal of the privacy cost matrix and is used to compute the privacy parameters: M scatisfies p-zCDP with p == pcost(M))2 [46], satisfies (e, (..)))pppxximtt DP with 5 = #bV/poostt (M)) c/ c/ (//pcos(MM)) - e < pppost(M)) c/ pcost (this is an increasing function of pcost(M) (51), and satisfies p- p-Gaussian DP with μ Vpcost(M) [15, 46).
The use of a non-diagonal covariance matrix is crucial because it will help simplify the description of provide
the optimal choices of B and Σ. In particular, using non-diagonal covariance allows explicit formulas for the entries of the B matrices. We note that an algorithm M that releases the outputs of multiple linear Gaussian mechanisms Mi....,MM, (with (x) again a linear Gaussian mechanism. It is represented as M* = B x + N N(, E") with the matrix B" obtained by vertically stacking the B, and with covariance E* being block-diagonal matrix where the blocks are the Σ; Its privacy cost (C)))(M") = peost(M,, Mss) is the largest diagonal entry of Σ 11= B 2, BB.
B,x + (O,,,)) ) is
2.2 Matrix Mechanism
The Matrix Mechanism [32, 52, 30, 53, 37, 38, 51, 46, 18, 42] is framework for providing unbiased privacy-pres precccppes answers to a workload of linear queries, represented by a matrix W (so that the true non-private answer to the workload queries is Wx). The matrix mechanism framework consists of 3 steps: select, measure, and reconstruct. The purpose of the select phase is to determine what we add noise to and how much noise use. More formally, when user's preferred noise distribution is Gaussian, the select phase chooses a Gaussian linear mechanism M(x) = Bx + [N Σ) whose noisy output can be used to estimate the true query answer Wx. Ideally, M uses the least amount of noise subject to privacy constraints (specified by privacy definition and settings of its privacy parameters). The measure phase runs the mechanism outputs س = .(x).. The reconstruct step uses w to compute an unbiased estimate of Wx. The unbiased estimate is typically W WBB 'Bj B - where t represents the Moore-Penrose pseudo-inverse. This is the best linear unbiased estimate of Wx that can be obtained from w [32]. This means that the goal of the select step is to optimize the choice of B and Σ so that the reconstructed answer as accurate as possible, subject privacy constraints. Ideally, a user would specify their accuracy requirements using a loss function, but existing matrix mechanisms do not allow this flexibility- they hard-code the loss function. In fact, adding support for new loss function used to require significant research and new optimization algorithms [53, 46, 18] because each new algorithm was customized to specific properties of chosen loss function. On top of this, existing optimal matrix mechanism algorithms do not scale, while scalable matrix mechanisms are not guaranteed to produce optimal solutions [37]. Additionally, the reconstruction phase should also compute the variance of each workload answer. The variances are the diagonals of W(B T BB)tt and making this computation scale is also challenging.
the data produce (noisy) privacy-presse preserving
3

---

3 Additional Related Work
The marginal release mechanism by Barak al. [6] predates the matrix mechanism [32, 52, 30, 53, 13, 43, 37, 51, 46, 18, 42, 38] and adds noise to the Fourier decompasition of marginals. We add noise to a different basis, resulting in the scalability and optimality properties. The SVD bound [31] is a lower bound on total matrix mechanism error when the loss function is the sum of variances. This lower bound is tight for marginals and we use as a sanity check for our results and implementation (note ResidualPlannes provides optimal solutions even when the SVD bound is infeasible to compute).
Alternative approaches to the matrix mechanism can produce privacy preserving marginal query answers that reduce variance by adding bias. This is often done by generating differentially private synthetic data or other such data synopses from which marginals can be computed. State-of-thh art approaches iteratively ask queries and fit synthetic data to the resulting answers [22, 34, 4, 19, 39, 35, 44, 56]. For such mechanisms, it difficult to estimate error of query answer but recently AIM [39] has made progress in upper bounding the error. PGM [41] provides a connection between the matrix mechanism and this line of work, as can postprocess noisy marginals into synthetic data. is a better alternative to sampling synthetic dataset from models fit to carefully chosen marginals [54, 11, 55, 10]. Synthetic data for answering marginal queries can also be created from random projections [48], copulas [33, 3], and deep generative models [23, 1, 35].
With respect to the matrix mechanism, the reconstruction step often one of the bottlenecks to scalability, While PGM [4] provides one solution, another proposal by McKenna et al. [40] is to further improve scalability by sacrificing some consistency (the answers to two different marginals may provide conflicting answers to submarginals they have in common). Work on differential privacy marginals has also seen extensions hierarchical datasets, in which records form meaningful groups that need to be queried. That is, in addition to marginals on characteristics of people, marginals can be computed in different hierarchies such as geographic level (state, county, etc.) and marginals on household composition (or other groupings of people) [2, 28, 36].
4 ResidualPlanner
ResidualPlanner is our proposed matrix mechanism for optimizing the accuracy of marginal queries with Gaussian noise. It is optimal and more scalable than existing approaches. It supports opti- mizing the accuracy of marginals under a wide variety of loss functions and provides exact vari- ances/covariances of the noisy marginals in closed-form. In this section, we first explain the loss functions it supports. We then describe the base mechanisms it uses to answer marginal queries. We next show how to reconstruct the marginal queries from the outputs of the base mechanisms and how to compute their variances in closed form. We then explain how to optimize these base mechanisms for different loss functions. The reason this selection step presented last is because depends on the closed form variance calculations. Then we analyze computational complexity. To aid in understanding, we added a complete numerical run-through of the steps in Section B of the supplementary material. All of our proofs also appear in the supplementary material.
4.1 Loss Functions Supported by ResidualPlanner
The loss functions we consider are generalizations of the sum of variances and max of variances used in prior work. Our more general class of loss functions is based on the following principle: different marginals can have different relative importance but within marginal, its cells are equally important. That is, loss function can express that the two-way marginal on the attribute set [Race, Marital Status] is more important (i.c., requires more accuracy) than the I-way marginal on [EducationLevel), but all cells within the (Race, MaritalStatus) } marginal are equally important. This is a commonly accepted principle for answering differentially private marginal queries (e.g.. [32, 52, 30, 53, 51, 46, 18, 42, 39, 4, 34J) and is certainly true for the 2020 Census redistricting data [2].
Let Wkload = (AI...., A be workload of marginals, where each A, is subset of attributes and represents marginal. E.g., Wklood = (Race, MaritalStatus), [EducationLevel]] consists of 2 marginals, a two-way marginal on Race/MaritalStatus, and a one-way marginal on Education. Let M be a Gaussian linear mechanism whose output can be used to reconstruct unbiased answers to the marginals in W kload. For each A, W Wkload, let V ar Var(A;; M) be the function that returns the

---

variances of the reconstructed answers to the marginal on A;; the output of Var(A;; M) is a vector 2y with one component for each cell of the marginal on A, A loss function L aggregates all of these vectors together: L(v va). We have the following regularity conditions on the loss function.
DEFINITION 4.1 (Regular Loss Funetion). We say the loss function L is regular if: (1) L. convex and continuous; (2) L(v U&) is minimized when all the vs are the 0 vectors; and for any i, permuting just the components of Us does not affect the value of [(v1...., UK). This latter condition just says that cells within the same marginal are equally important.
Loss functions used on prior work are all regular. For example, weighted sum of variances [32, 52, 30, 53, 37, 51] can be expressed as [(V1...., Ug)) = Σ. c, 1y, where the c are the nonnegative weights that indicate the relative importance of the different marginals. Another pop- ular loss function is maximum (weighted) variance [46, 18, 42], expressed as L(v1...., U% max max(e1)
max((y)] }. Thus, the optimization problem that the selection step needs to solve either privacy constrained: minimize loss while keeping privacy cost (defined the end of Section 2.1) below threshold y; or utility constrained: minimize privacy cost such that the loss is at most
Privacy constrained:
arg min L(V ar
s.t. pcost( (M) S Y (1)
Utility constrained:
arg min PC) s.t. L(Var(Ai;:M) MAV SY (2)
We note that regular loss functions cover other interesting cases. For instance, suppose Alicia, Bob, and Carol wish to minimize the sum of variances on their own separate workloads. Taking the max over these three sum-of-variances unhappiness among the three data stakeholders.
the loss function allows the data curator minimize the largest
4.2 Base Mechanisms used by ResidualPlanner
In the most common application setting, the user picks privacy budget, workload of marginals and a loss function L. Based on these choices, a matrix mechanism must decide what linear queries to add noise to and how much noise to add to them. Then it uses those noisy measurements to reconstruct answers to the workload queries. In the case of ResidualPlanner, the linear queries that need noise represented by base mechanisms that are described in this section. Each base mechanism has scalar noise parameter that determines how much noise uses (so optimizing the loss function is equivalent to finding good value for the noise parameter of cach base mechanism). As long the loss function L is regular, we prove that an optimal mechanism can be constructed from the set of base mechanisms that we describe here.
To begin, we define a subtraction matrix Sub,. to be an (m - 1) X m matrix where the first column is filled with 1, entries of the form +1 are -1, and all other entries are O. For example, Sub; = [1-- _ and Sub, = [1 ]. We use these subtraction matrices to define special matrices called residual matrices that are important for our algorithm.
For any subset A C {Ath, Attm.. } of attributes, we define the residual matrix RA as the Kronecker product RA = V1 ... &V n.. where V, = 1" Au. if Att; & A and V; = Sub Am; Att, E A. Continuing Example 2.1, we have Rę = [1 [ [1 1. and R R(au)) [1 -1 Ø 111], and R ((m,)) [11]0|] -1 - and R Attr) =
1 9
Using subtraction matrices, we also define the matrix ΣA as the Kronecker product (Sub Sub/Ame)) and we note that it proportional to RAR Eg defined as 1.
A
Each subset A of attributes can be associated with a "base" mechanism MA that takes as input the data vector and scalar parameter o for controlling how noisy the answer is. MA is defined as:
MA (x) = RAX+ + N(0, ΣA)
(3)
The residual matrices RA used by base mechanisms form a linearly independent basis that compactly represent marginals, the next result shows.
THEOREM 4.2. Let A be a set of attributes and let QA be the matrix representation of the marginal on A. Then the rows of the matrices for all A C A form linearly independent basis of the row space of QA. Furthermore, if A' # A" then RA RAA 0 (they mutually orthogonal).
5

---

REMARK 4.3. To build an intuitive understanding of residual matrices, consider again Example 2.1. Both Rg and Qg are the sum query (marginal on no attributes). The rows of ((A,,,) span the subspace of (Att)) that is orthogonal to Qg (and similarly for (AAt2))) The rows of R, Att,) span the subspace of Q Atta that is orthogonal to both Q Attt and Q (AU2) Hence residual matrix spans the subspace of a marginal that is orthogonal to its marr-nasss
Theorem 4.2 has several important implications. If we define the downward closure of a marginal as the collection of all subsets of the sets in W kload (i.e., closure Wloodd) = {A A' C A for some E Wkloodd) then the theorem implies that the combined rows from {RA A' marginals in the workload. In other words, it is linearly independent bases for the space spanned by the rows of the marginal query matrices QA for A E Wkload. Thus, in order to provide privacy- preserving answers to all of the marginals represented in Wkload, we need all the mechanisms MA for A' closure (W ( kload) any other matrix mechanism that provides fewer noisy outputs cannot reconstruct unbiased answers to the workload marginals. This is proved Theorem 4.4, which also states that optimality is achieved by carefully setting the O noise parameter for each MA.
workload W kload { {A 1, 1..... }
(klladd) forms a linearly independent basis for the
THEOREM 4.4. Given a marginal workload W kload and regular loss function C, suppose the optimization problem (either Equation 1 or 2) is feasible. Then there exist nonnegative constants a for each A E closure(Whdlee kload) (the constants do not depend on the data), such that the optimal linear Gaussian mechanism Mopt for loss function L. releases Mx(x;0%) for all A E closure W (klood). Furthermore, any matrix mechanism for this workload must produce at least this many noise measurements during its selection phase.
Algorithm 1: Efficient implementation of MA(x; = RAX + N(0,0AAA))
1 v < QAx// Evaluate the true marginal
IAmhe A |Attl
3 H X Sub Sub/,n//// // Use implicit representation, don't expand
Att:AA
z (O.. I // independent noise
5 return Hv + o Hz// use kron-product/vectorr multiplication from [37]
MA can be evaluated efficiently, directly from the marginal x on attribute set A, as shown in Algorithm 1. It uses the technique from [37] to perform fast multiplication between a Kronecker product and a vector (so that the Kronecker product does not need to be expanded). It also generates correlated noise from independent Gaussians. The privacy cost pcost (M of each base mechanism MA is also easy to compute and is given by the following theorem.
THROREM 4.5. The privacy cost of MA with noise parameter 0% is + ILAGEA the evaluation of MM given in Algorithm I is correct iee, the output has the distribution N N(RAx, EA).
LAttal=1 TAte. and
4.3
Reconstruction
Next we explain how to reconstruct unbiased answers to marginal queries from the outputs of the base mechanisms and how to compute (co)variances of the reconstructed marginals efficiently, without any heavy matrix operations (inversion,
secudo-inversed etc.). Then, given the closed form expressions for marginals and privacy cost (Theorem 4.5), we will be able to explain in Section 4.4 how to optimize the x parameters of the base mechanisms MA to optimize regular loss functions L.
Since the base mechanisms were built using linearly independent basis, reconstruction is unique - jjust efficiently invert the basis. Hence, unlike PGM and its extensions [41, 40], our reconstruc- tion algorithm does not need solve an optimization problem and can reconstruct each marginal independently, thus allowing marginals to be reconstructed in parallel, or as needed by users. The reconstructed marginals are consistent with each other (any two reconstructed marginals agree on their sub-margun -ub-marginals). Just as the subtraction matrices Sub; were useful in constructing the base mechanisms MA. their pseudo-inverse Sub, useful for reconstructing noisy marginals from the

---

noisy answers of MA. The pseudo-inversen have a closed form. For example Sub, = and Subţ
1 -1
More generally, they expressed follows:
LEMMA 4.6. For any Att, let = Att;). The matrix Sub; has the following block matrix, with dimensions x (E - 1), as its aseudo-inverse (and right inverse): Sub!
1 | 1Z1-1
Each mechanism MA. for A closure W kload), has noise scale parameter a and noisy output that we denote by wA. After we have obtained the noisy outputs WA for all A E closure W kload), we can proceed with the reconstruction phase. The reconstruction of an unbiased noisy answer for any marginal
attribute set A closure ( kload) is obtained using Algorithm 2. We note that to reconstruct a marginal on attribute set A, one only needs to use the noisy answers WA for A' E closure(A) (A). In other words, if we want to reconstruct marginal we only need the outputs of Mg. M(rr.)) ). M[Atta] and M M{Ats [,Att,,Att, no matter how many other attributes are in the data and matter what other marginals in the W kload. We emphasize again, the reconstruction phase does not run the base mechanisms anymore, it is purely post-processing.
attribute
{Att1, Att2),
Algorithm 2: Reconstruct Unbiased Answers to the Marginal on A
Input: Noise scale parameters x and noisy answer vector wA of mechanism MA for every A' closure(A) (A).
Output: q is output as an unbiased noisy estimate of QA q 1-0 0
for each A' closure(A) () do
Sub AAt
if Att; A' if Att, E A/A' if Atl, & A
3
U + V 18 ... V n.y where V,
Att. [1]
q q + // use kron- rron-product/vectorr multiplication from [37]
5 return q
THEOREM 4.7. Given a marginal workload W Wklood and positive numbers 0² for each A E closure(W (Kklodd), let M be the mechanism that outputs {M x A closure(W and let {W
A E closure (Wr kklodd) denote the privacy-preserving noisy answers (e.g.. WA (a(xx0²)) Then for any marginal on an attribule rithm 2 returns the unique linear unbiased estimate of Q (i.e., answers to the marginal query) that be computed from the noisy differentially private answers.
A closure(W) ( (Wkoord) Algo-
The variances Var(A;M) of all the noisy cell counts of the marginal on A is the vector |AHt.--1
whose components are all equal ENCA ENCA(ONIIAEE (IxIIA The covariance between any two noisy answers of the marginal A is ΣNSA (02x SL-AAA [Aue] *ILAAJE(A/A) )
IIAA,,EAAAA") [Ate
TAte.
-1
To see an example of how the choices of the o affect the variance of different marginals, see Section C in the supplementary material.
4.4 Optimizing the Base Mechanism Selection
We now consider how to find the optimal Gaussian linear mechanism M that solves the optimization problems in Equations or 2. Given a workload on marginals Wkload, the optimization involves Var M") for A W Wkload (the variance of the marginal answers reconstructed from the output of M and pcos((M" from which the privacy parameters of different flavors of differential privacy can be computed.
Theorem 4.4 says that M works by releasing MA x for each E closure WaneeeWkloood kload) for appropriately chosen values of o.. The privacy cost pcost(MM) is the sum of the privacy costs of
7

---

the MA. Theorem 4.5 therefore shows that p.ost(.M") is positive linear combination of the values 1 1/02 for A E shows how to represent, for each A E closure (lloadd the quantity "ar(A;M") positive linear combination of a for A' E closure(A) A) S closure ( (akoodd) Therefore, the loss function also convex in the A values.
( (kkoor)(Wklodd) and is therefore convex in the a values. Meanwhile, Theorem 4.7
kload),
Thus the optimization problems in Equations 1 and 2 can be written as minimizing a convex function of the x subject convex constraints. In fact, in Equation 2, the constraints are linear when the optimization variables represent the o and in Equation the constraints are linear when the optimization variables represent the 1/ Furthermore, when the loss function is the weighted sum of variances of the marginal cells. the solution can be obtained in closed form (see supplementary material). Otherwise, we use CVXPY/ECOS [12. 14] for solving these convex optimization problems.
4.5 Computational Complexity
Although the universe size [Att1] x... |Attm.. grows exponentially with the number of attributes, the following theorem shows that the time complexity of ResidualPlanner depends directly on quantities that typically grow polynomially, such as the number of desired marginals and total number of cells in those marginals.
THEOREM 4.8. Let ng be the total number of attributes. Let #cells (A) denote the number of cells in the marginal on attribute set A. Then:
Expressing the privacy cost of the optimal mechanism M as a linear combination of the 1/0² values takes O O(ExeWhlood #cells (A)) total time.
2. Expressing all of the V Var(A: for A E Wklood, can be done in A(EAWWlood #cells(A) (A)) total time.
linear combinations of the o values
Computing all the noisy outputs of the optimal mechanism (i.e., MA(x; for A E closure(W) (W klood)) takes (na Exewkoood EAA,, ([Altg] + +1) total time after the true an- swers have been precomputed (Line I in Algorithm 1). Note that the total number of cells on marginals in W klood is O (EAewklond ILAu, |Att,)).
Reconstructing marginals for all A E W Wkload takes O kload |A] [Al#cells(A))) total time. 5. Computing the vuriance of the cells for all of the marginals for A Wkload can be done in O(ExE #cells( (A) A)) total time.
To get a sense of these numbers, consider a dataset with 20 attributes, each having 3 possible values. If the workload consists of all 3-way marginals, there are 1,140 marginals each with 27 cells so neells = 30, 780. The quantity inside the big-O for the selection step is 1, 459, 200 (roughly the number of scalar multiplications needed). These are all easily manageable on modern computers even without GPUs. Our experiments, under more challenging conditions, run in seconds.
5 Experiments
We next compare the accuracy and scalability of ResidualPlanner against HDMM [38], including variations of HDMM with faster reconstruction phases [41]. The hardware used was an Ubuntu 22.04.2 server with 12 Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz processors and 32GB of DDR4 RAM. We use 3 real datasets to evaluate accuracy and 1 synthetic dataset to evaluate scal- ability. The real datasets are (1) the Adult dataset [16] with 14 attributes, each having domain sizes 100, 100, 100, 99, 85, 42, 16, 15, 9, 7, 6, 5, 2, 2, respectively, resulting in a record domain size of 6.41 10²7; (2) the CPS dataset [9] with 5 attributes, each having domain size 100,50
respectively. resulting in a record domain size of 2.8 10"; (3) the Loans dataset [24] with 12 attributes, each having domain size 101, 101, 101, 101,3, 3. 8, 36, 6, 51, 4, 5, 15, respectively, resulting in record domain size of 8.25 15 The synthetic dataset is called Synth-n". Here d refers to the number of attributes (we experiment from d = 2 to d = 100) and n the domain size of each attribute. The running times of the algorithms only depend on n and d and not on the records in the synthetic data. For all experiments, we set the privacy cost peosl to 1, so all mechanisms being compared satisfy 0.5-2CDP and I-Gaussian DP.
8

---

5.1 Scalability of the Selection Phase
We first consider how long each method takes perform the selection phase (i.e., determine what needs noisy answers and how much noise to use). HDMM can only optimize total variance, which equivalent root mean squared error. For ResidualPlanner variance as objectives (the latter is harder to solve problem). Fach algorithm is run 5 times and the average is taken. Table shows running time results; accuracy results will be presented later.
consider both RMSE and max
Table I: Time for Selection Step in seconds on Synth-n" dataset. = 10 and the number of attributes d varies. The workload consists of all marginals are reported with 2 standard deviations.
3 attributes each. Times for HDMM
HDMM RMSE Objective
ResidualPlanner RMSE Objective
ResidualPlanner
Max Variance Objective
2
0.013 + 0.003 sec
0.001 + 0.0008 sec
0.007 + 0.001 sec
0.065 0.012 sec
0.002 0.0008 sec
0.009 0.001 sec
10
0.639 = 0.059 sec
0.009 + 0.001 sec
0.018 + 0.001 sec
12
4.702 = 0.315 sec
0.015 + 0.001 sec
0.028 0.001 sec
14
46.054 +: 12. sec
0.025 + 0.002 sec
0.041 + 0.001 sec
15
201.485 + 13.697 sec
0.030 0.017 sec
0.050 0.001 see
20
Out of memory
0.079 + 0.017 sec
0.123 + 0.023 sec
30
Out of memory
0.247 0.019 sec
0.461 0.024 sec
50
Out of memory
1.207 + 0.047 sec
4.011 + 0.112 sec
100
Out of memory
9.913 0.246 sec
121.224 + 3.008 see
As we can see, optimizing for max variance more difficult than for RMSE, but ResidualPlanner does it quickly even for data settings too big for HDMM. The runtime of HDMM increases rapidly, while even for the extreme end of our experiments, ResidualPlanner needs just a few minutes.
5.2 Scalability of the Reconstruction Phase
We next evaluate the scalability of the reconstruction phase under the same settings. The reconstruc- tion speed for ResidualPlanner does not depend on the objective of the selection phase. Here we compare against HDMM [38] and version of HDMM with improved reconstruction scalability called HDMM+PGM [38, 41] (the PGM settings used 50 iterations of as the default 1000 was too slow). Since HDMM cannot perform the selection phase after a certain point, reconstruction results also become unavailable, Table shows ResidualPlanner is clearly faster.
estimator,
Table 2: Time for Reconstruction Step in seconds on Synth dataset. n = 10 and the number of attributes d varies. The workload consists of all marginals < 3 attributes each. Times are reported with +2 standard deviations. Reconstruction can only be performed if the select step completed.
d
HDMM
HDMM + PGM
ResidualPlanner
2
0.003 0,0006 see
0.155 0.011 sec
0,005 0.003 sec
6
0.173 + 0.011 sec
4.088 + 0.233 see
0.023 + 0.004 sec
10
Out of memory reconstruction
20.340 + 2.264 see
0.125 0.032 sec
12
Out of memory in reconstruction
39.162 + 1.739 see
0.207 + 0.004 sec
14
Out of memory in reconstruction
69.975 + 4.037 sec
0.330 0.006 sec
15
Out of memory in reconstruction
91.101 + 7.621 sec
0.413 + 0.006 sec
20
N/A (select step failed)
N/A (select step failed)
1.021 0.011 sec
30
N/A (select step failed)
N/A (select step failed)
3.587 + 0.053 sec
50
N/A (select step failed)
N/A (select step failed)
17.029 0.212 sec
100
N/A (select step failed)
N/A (select step failed)
154.538 + 15.045 sec
5.3
Accuracy Comparisons
Since ResidualPlanner is optimal, the purpose of the accuracy comparisons is a sanity check. For RMSE, comparisons the quality ResidualPlanner to the theoretically optimal lower bound, known the SVD bound [31], can be found in the supplementary material in Section (ResidualPlanner

---

matches the lower bound). We note ResidualPlanner can provide solutions even when the SVD bound infeasible to compute.
We also compare ResidualPlanner to HDMM when the user is interested in the maximum variance objective. This just shows that it is important optimize for the user's objective function and that the optimal solution for RMSE (the only objective HDMM can optimize) is not a good general- approximation for other objectives (as shown Table 3), Additional comparisons are provided in the supplementary material.
Table 3: Max Variance Comparisons with ResidualPlanner and HDMM (showing that being restricted to optimizing only RMSE is not good approximation of Max Variance optimization).
Adult Dataset
CPS Dataset
Loans Dataset
Workload
ResPlan
HDMM
ResPlan
HDMM
ResPlan
HDMM
1-way Marginals
12.047
41.772
4.346
13.672
10.640
33,256
2- 2-way Marginals
67.802
599.843
7.897
47.741
52.217
437.478
3-way Marginals
236.843
5675.238
7.706
71.549
156.638
3095.997
< 3-way Marginals
253.605
6677.253
13.216
415.073
180.817
4317.709
Limitations, Conclusion, and Future Work.
In this paper, we introduced ResidualPlanner, matrix mechanism that is scalable and optimal for marginals under Gaussian noise, for a large class of convex objective functions. While these are important improvements to the state of the art, there are limitations.
want marginals. For example, they might want range queries or queries with hierarchies (e.g., how many people drive sedans vs. vans; out of the sedans, how many are red vs. green, etc) [2, 28, 36]. some cases, an attribute might have an infinite domain (e.g., URL) and need to be handled differently [27, 45]. In other cases, the user may want other noise distributions, like the Laplace. These types of queries do not have the same type symmetry as marginals that was crucial to proving the optimality of ResidualPlanner. For these situations, one of the key ideas of ResidualPlanner can be used find a linear basis that compactly represents both the queries and "residual" (information provided by query that is not contained in the other queries). Such feature would result in scalability. is future work determine how to extend both scalability and optimality to such situations. Another limitation is that this work considers the setting where an individual can contribute exactly one (rather than arbitrarily many) records to the dataset.
First, for attributes, user might
Acknowledgments
This work supported by NSF grant 19331666 and gift from Facebook.
10

---

References
[1] Nazmiye Ceren Abay, Yan Zhou, Murat Kantarcioglu, Bhavani Thuraisingham, and Latanya Sweeney. Privacy preserving synthetic data release using deep learning. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018. Dublin, Ireland, September 10-14, 2018, Proceedings, Part I 18, pages 510-526. Springer, 2019.
[2] John M. Abowd, Robert Ashmead. Ryan Cumings-Menonn, Simson Garfinkel, Micah Hei- neck, Christine Heiss. Robert Johns, Daniel Kifer, Philip Leclere, Ashwin Machanava- ijhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. The 2020 census disclosure avoidance system topdown algorithm. Harvard Data Science Re- view, forthcoming. Preprint https: //ww.. census. .ww.suu..ooo/oo.o. gov. hoo/library/workee httpaar//oookkiggppprr//////// papers/2022/ adrm/CED- WP W html.
[3] Hassan Jameel Asghar, Ming Ding, Thierry Rakotoarivelo, Sirine Mrabet, and Mohamed Ali Kaafar. Differentially private release of high-dimensional datasets using the gaussian copula. arXiv preprint 19X2.0/902.0149999 2019.
[4] Sergul Aydore. William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Ankit A Siva. Differentially private query release through adaptive projection. In International Conference on Machine Learning. pages 457-467. PMLR, 2021.
[5] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning,
ICML, 2018.
[6] Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. Privacy, accuracy, and consistency too: holistic solution to contingency table release. In Proceedings of the twenty-sixth ACM SIGMOD-SIGAACT-SIGAR symposium on Principles of database systems, pages 273-282, 2007.
[7] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proceedings, Part I, of the 14th International Conference Theory of Cryptography Volume 9985, 2016.
[8] U.S. Census Bureau. Decennial census: 2010 summary files. https://www.centt gov/
wwwp/cat/deceniie census c00_us_0sss__
[9] U.S. Census Bureau. The current population survey (cps). https httts://www.censst .oraasussooo////
programs- surremaassuurveyaacpcppp html, 2023.
[10] Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. Data synthesis via differentially private markov random fields. Proceedings of the VLDB Endowment, 14(11):110-2202, 2021.
[11] Rui Chen, Qian Xiao, Yu Zhang, and Jianliang Xu. Differentially private high-dimensional data publication via campling-based inference. In Proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pages 129-138, 2015.
[12] Steven Diamond and Stephen Boyd. CVXPY: A eeebedde modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[13] Bolin Ding, Marianne Winslett, Jiawei Han, and Zhenhui Li. Differentially private data cubes: Optimizing noise sources and consistency. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, 2011.
[14] Alexander Domahidi, Eric Chu, and Stephen Boyd. Ecos: An socp solver for embedded systems. In 2013 European control conference (ECC), pages 3071-3076. IEEE, 2013.
[15] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3-37, 2022.
[16] Dheeru Dua and Casey Graff. UCI machine learning repository, 2019.
[17] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. EUROCRYPT, pages 486-503, 2006.
[18] Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mechanisms local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 425-438, 2020.
11

---

[19] Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. Dual query: Practical private query release for high dimensional data, In International Conference Machine Learning, pages 1170-1178 PMLR, 2014.
[20] Marco Gaboardi, Hyun Lim, Ryan Rogers, and Salil Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In International conference on machine learning. pages 21 1112222.. PMLR, 2016.
[21] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
[22] Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. Advances in neural information processing systems, 25, 2012.
[23] James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. In International conference learning representations, 2019.
[24] Kaggle. 8th, 2023.
Loan prediction problem dataset. problem-dataset, 2021. Accessed: May
https: //ww://wwwww..o //wg://w/wwgggleee..... com/
[25] Kazuya Kakizaki, Kazuto Fukuchi, and Jun Sakuma. Differentially private chi-squared test by unit circle mechanism. In International Conference on Machine Learning, pages 1761-1770. PMLR, 2017.
[26] Daniel Kifer and Ryan Rogers. A new class of private chi-square tests. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS, volume 17, pages 991-1000, 2016.
[27] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th international conference World wide web, pages 171-180, 2009.
[28] Yu-Hsuan Kuo, Cho-Chun Chiu, Daniel Kifer, Michael Hay, and Ashwin Machanavajjhala Differentially private hierarchical count-of-counts histograms. arXiv preprint arXiv: /04.v/800.0003 00370, 2018.
[29] Jing Lei. Differentially private m-estimators. Advances in Neural Information Processing Systems, 24, 2011.
[30] Chao Li and Gerome Miklau, An adaptive mechanism for accurate query answering under differential privacy. Proceedings of the VLDB Endowment, 5(6), 2012.
[31] Chao Li and Gerome Miklau. Optimal error of query sets under the differentially-privall matrix mechanism. In Proceedings of the 16th International Conference on Database Theory, pages 272-283, 2013.
[32] Chao Li, Gerome Miklau, Michael Hay, Andrew Mcgregor, and Vibhor Rastogi. The matrix mechanism: Optimizing linear counting queries under differential privacy. The VLDB Journal, 2476)7757-78, December 2015.
[33] Haoran Li, Li Xiong, and Xiaoqian Jiang. Differentially private synthesization of multi- dimensional data using copula functions. In Advances in database technology: proceedings. International conference on extending database technology, volume 2014, page 475. NIH Public Access, 2014.
[34] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Steven Wu. Leveraging public data for practical private query release. In International Conference on Machine Learning. pages 6968 0688.6677.77 PMLR, 2021.
[35] Terrance Liu, Giuseppe Vietri, and Steven Z Wu. Iterative methods for private synthetic data: Unifying framework and new methods. Advances in Neural Information Processing Systems, 34, 2021.
[36] Terrance Liu and Zhiwei Steven Wu. Private synthetic data with hierarchical structure. arXiv preprint arXiv:2206. 2244549200 2022.
[37] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajihala. Optimizing error of bigh-dimensional statistical queries under differential privacy. Proceedings of the VLDB Endowment, 11(10), 2018.
12

---

[38] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Hdmm: Opti- mizing error of -ishesimensioall statistical queries under differential privacy. arXiv preprint arXiv:2106. / 2021.
[39] Ryan McKenna, Brett Mullins, Daniel Sheldon, and Gerome Miklau, Aim: An adaptive and iterative mechanism for differentially private synthetic data. arXiv preprint urXiv:220.112611 2022.
[40] Ryan McKenna, Siddhant Pradhan, Daniel R Sheldon, and Gerome Miklau. Relaxed marginal consistency for differentially private query answering. Advances in Neural Information Pro- cessing Systems, 14:20696-207070 2021.
[41] Ryan McKenna, Daniel Sheldon, and Gerome Miklau, Graphical-moder based estimation and inference for differential privacy. In International Conference on Machine Learning, pages 4435-4444, PMLR, 2019.
[42] Aleksandar Nikolov. New computational aspects of discrepancy theory. PhD thesis, Rutgers Grraeut School-New Brunswick, 2014.
[43] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Priview: practical differentially private release of marginal contingency tables. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 1435-1446, 2014.
[44] Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu. New oracle-efficient algorithms for private synthetic data release. In International Conference on Machine Learning. pages 9765-9774. PMLR, 2020.
[45] Royce Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons- Marengo, and Bryant Gipson. Differentially private sql with bounded user contribution. In Proceedings on Privacy Enhancing Technologies Symposium, 2020.
[46] Yingtai Xiao, Zeyu Ding, Yuxin Wang, Danfeng Zhang, and Daniel Kifer. Optimizing fitness- for-use of differentially private linear queries. In VLDB, 2021.
[47] Yingtai Xiao, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. Answering private linear queries adaptively using the common mechanism. https: attps://arxiv. org/ absp/21..22.2...//// 2022.
[48] Chugui Xu, Ju Ren, Yaoxue Zhang, Zhan Qin, and Kui Ren. Dppro: Differentially private high- dimensional data release via random projection. IEEE Transactions on Information Forensics and Security, 12(12):081133093 2017.
[49] Grigory Yaroslavtsev. Graham Cormode, Cecilia M Procopiuc, and Divesh Srivastava. Ac- curate and efficient private release of datacubes and contingency tables. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 745-756. IEEE, 2013.
[50] Fei Yu, Stephen E Fienberg, Aleksandra B Slavković, and Caroline Uhler. Scalable privacy- preserving data sharing methodology for genome- wide association studies. Journal of biomedi- cal informatics, 50:133-141, 2014.
[51] Ganzhao Yuan, Yin Yang, Zhenjie Zhang, and Zhifeng Hao. Couvex optimization for linear
query processing under approximate differential privacy. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
[52] Ganzhao Yuan, Zhenjie Zhang, Marianne Winslett, Xiaokui Xiao, Yin Yang, and Zhifeng Hao. Low-rank mechanism: Optimizing batch queries under differential privacy. Proc. VLDB Endow., 5(11):13521363, July 2012.
[53] Ganzhao Yuan, Zhenjie Zhang, Marianne Winslett, Xiaokui Xiao, Yin Yang, and Zhifeng Hao. Optimizing batch linear queries under exact and approximate differential privacy. ACM Transactions on Database Systems (TODS), 40(2):1-47, 2015.
[54] Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. Privbayes: Private data release via bayesian networks. ACM Trans. Database Syst., 42(4), oct 2017.
[55] Wei Zhang, Jingwen Zhao, Fengqiong Wei, and Yunfang Chen. Differentially private high- dimensional data publication via markov network. EAI Endorsed Transactions on Security and Safety, 6(19). 2019.
[56] Zhikun Zhang, Tianhao Wang. Jean Honorio, Ninghui Li, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. Privsyn: Differentially private data synthesis. 2021.
13

---

Contents
Introduction
2
Preliminaries
2.1
Differential Privacy
2.2
Matrix Mechanism
3
Additional Related Work
ResidualPlanner
4.1
Loss Functions Supported by ResidualPlanner
4.2
Base Mechanisms used by ResidualPlanner
4.3
Reconstruction
4.4
Optimizing the Base Mechanism Selection
4.5
Computational Complexity
5
Experiments
5.1
Scalability of the Selection Phase
5.2
Scalability of the Reconstruction Phase
5.3
Accuracy Comparisons
Limitations, Conclusion, and Future Work.
10
7
Acknowledgments
10
Table of Notation
15
A Run-through of Residual Planner
15
B.1 A Small Dataset and its Vectorized Representation
15
B.2 The Marginal Workload and its Representation as a Query Matrix.
15
B.3 The Base Mechanisms
18
B.4
Reconstruction
19
B.5
Privacy Cost and Marginal Variances
20
B.6 The Sum-of- Variinnces Loss Function
21
Example Variance Calculations
22
Optimality Proof of ResidualPlanner
23
D.I Notation Review
24
D.2 Permutations
24
D.3 From permutations interpretations
26
The other proofs about base mechanisms
32
14

---

Proofs related to the reconstruction step
34
Computational Complexity Proof's
38
H
Closed Form Solution to the Weighted Sum of Variances Loss
39
Additional Experiments
40
I1 Scalability...
40
I.2 Comparison on Real Datasets.
43
A Table of Notation
B
A Run-through of Residual Planner
In this section, we provide a complete runthrough of ResidualPlanner using small toy dataset.
B.1 A Small Dataset and its Vectorized Representation
In our example, we have dataset with attributes, so n 3. Att takes values 'a' 'b': Attz takes values "y" or 'n'; Attz takes values or 2 or 3.
In this dataset, there are people, and the tabular representation is shown in Table 5. For each attribute, we can one-hot encode its attribute values as row vectors. So, for Att,, the attribute value [0. 1]. For Att2, the attribute value 'y" is encoded as [1, 0J and 'n' is encoded as [0. 1]. For attribute A/t3, the attribute value 'I' is encoded as [1, 0, 0J. the value '2' is encoded [0, 1, 0] and '3' is encoded 0,
'a' is encoded as [1,0] and 'b' is encoded
The kronecker product representation of record is the kronecker product of the one-hot encod- ing of each attributes. So, for example, the record 'an2' is encoded as the kronecker product [1.0) & 00 1, 0j. When this kronecker product is expanded, it has 12 components. One of the contains a and the rest contain O. Thus the expanded kronecker product can be thought of as one-hot encoding of the entire record.
Indeed, in the expanded kronecker product, each dimension of the resulting vector is associated with a record. In table 6, we show the kronecker product representation each record from Table 5. The left column of Table 6 shows the record and its kronecker representation. The next 12 columns show resulting expansion. Each record becomes as 12-dimensional vector and the column labels in Table 6 show which record is associated with which index in the 12-dimensional vector.
The sum of the kron representations of all the records is the data vector x. is again 12-dimensional vector. At each index i, x[i] is the number of people whose record is associated index i. For example, the 5th component is associated with the record 'an2' and there are 2 people with that record. For mathematical convenience, x is treated as a column vector, but for display purposes, in Table 6 it is written row vector.
B.2 The Marginal Workload and its Representation Query Matrix.
For this example, we set the marginal workload to consist of 3 marginals Wkload = [[Att]) (Att), Att2], (Att,, Attz]}
The marginal on attribute set people with Att, a (i.e., 3) and the number with Att, 6 (i.e., 3). This is called one-way marginal. The other marginals are two-way marginals because they involve two attributes. For example, the marginal on A (Attz, Atts} has cells. It represents the number of people for each combination of values for Att and Att3. For example, there are 2 people with Att, = y and Alla = 3.
{AAtt } has only two cells, which correspond to the number of
For each set A, the marginal on those attributes can represented as a matrix QA such that calculating the marginal is equivalent the matrix-vector multiplication QA The construction of
15

---

Table 4: Table of Notation
D:
Dataset 1 record in D
number of attributes each record has 1th attribute.
Att [Atty]
size of the domain of attribute Atty.
d
,,.,, A
possible values (domain) of Altj.
Pua
Number of possible records: d
I
Att
1=1
x:
Representation of 'D as d-dimensional vector counts (e.g., histogram) (Sub)sett of attributes
A:
QA:
Matrix representation of the marginal on A. The counts the marginal are the result of matrix-vector product QAx.
#cells(A):
Number of cells in the marginal on A. Equals IA EA |Atti]
ec
one-hot encoding vector with entry being and the rest O equal e; c,
eif:
1g:
the f-diiensional vector whose entries are all the k x k identity matrix
Ig:
M:
privacy mechanism.
Output of mechanism.
B:
Query matrix of Gaussian linear query mechanism: MM = Bx N(O Covariance matrix.
E:
(M):
Privacy cost of Gaussian linear mechanism M(x) = Bx + (O, Σ). It is defined as the largest diagonal of B S-''.B Differential privacy parameters can be computed from pcost(M)
Wkload:
A workload of marginals. Each element of W kload is set of attributes (representing the marginal on those attributes).
Deeliss
Total number of cells in the marginals in the marginal workload (i.e., the output size).
closure( W kload):
The set all subsets of W kload. Formally defined as {A' A' S A for some W Wloood)
Var(A,M)
When the output of M is used to reconstruct answers to the marginal on A, then Var returns the vector of variances of the marginal cells.
L:
The loss function
The operator that gives the pseudo-inverse of matrix
Submi
An (m - 1) x m subtraction matrix. The first column is filled with 1, entries of the form ( + 1) are -1, and all other entries are Attm. of attributes, RA = V VV Roy Residual matrix. Given a set A C [Att
RA
where V, = 1 Are.) if Att, & A and V, Sub andil Att, E A. The covariance matrix used by the base mechanisms, formed as the kronecker product (ublacc,,uubjAc..
Σx:
Also Eg = 1.
Att.EA
Data-independent noise scale parameter
MA
The base mechanism defined as MM RAX + N(0,02 It uses a data- independent noise parameter o²
WA:
noisy output mechanism MA
the matrix QA is straightforward. It is kronecker product of matrices. Each matrix corresponds to A then the corresponding term is the identity matrix, otherwise is is
an attribute. If the attribute the vector full of ones. For example, Q(Au,) } is kron product of 3 matrices: the first matrix corresponds to All, and is the 2 2 identity matrix. The second matrix is actually the vector full of ones because All is not part of the marginal. This vector has components because Atla has possible values. Similarly, the third matrix is the vector full of ones with 3 components.
16

---

Att
Att2
At13
b
a
b
Table 5: A Toy Dataset D
ay1
oy2
ay3
amL
072
a71
by
by2
by3
5m
bit
mn2:[1.0 1 1,0
0
0
0
0
1
0
0
0
0
bu3: 00, 10.11000 1 0.
0
0
0
0
0
0
0
0
by3: (0. 10 0.0
0
0
an2: 110
0
0
by3: [0.1 0.00.3
Vector of counts
0
0
0
2
0
2
Table Kron product representations or each record and the whole dataset x. Nonzero components shown in bold red.
For the marginals in W kload, these are the the corresponding matrices:
1
0
(Arrs)
1
1
11
0
1
1
1
0
0
0
0 1
0
0
0
0
1
1 0
1
0
<
1
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
Attss
X
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
If we multiply Atttra by the data vector from Table 6, get:
0
0
2
Q (tttrr
O
2
1
Comparing it to the marginals shown in Table 7 we see that it is the flattened version of the marginal. That is, we take the first column of the (All2, Alla) marginal of Table 7, then we put the next column below it, and the third column is placed at the bottom.
17

---

A {Atti}
A (Ath1 Att2)
A
{Att2, Atts)
y
n
1
3
2
0
2
y 0
2
b
3
2
1
0
Table 7:
True answers to the marginal queries in the marginal workload Wkload [[Att]], (Atti, Att2]. {Att2, A
=
B.3 The Base Mechanisms
Recall that workload, the marginals want sewaccypreservinng answers to, is Wkload {{ [Att), {All,, Att2), {Alt2, AM13]] )- Its closure, denoted by ( is all of its subsets. So,
closure (ossureWWload]) { {Attz}, (Att2), {Atts) J. {Att,, Att2), {Atty, Atts}
For each A E closure kloodd)) we need to form a base mechanism MA. Each MA has free free to choose. Each mechanism MA has the form MA (x: o
parameter o that RAX+ + .V (0, AA). That is, on input x, the mechanism multiplies it by a special "residual" matrix RA and then adds correlated Gaussian noise, with mean and with covariance matrix o Ex. The residual and covariance matrices for each base mechanism are shown below.
Mæ:
RØ = [ 1 | 1 1 1 1]
Σg [1]
M(An)::
R(Au1) = [1 -1 | 1 1| 1 11
E(Au)) = -1 -1](1 -1 -1)) [2]
: R(AU)) [ | -1 1 1]
[(tt))) -1 [[[
[2]
-1 -
M (Atts) 1 | 1 |
-1 0 [[
16 - 1) T
[
2
[(U)))
R Attts
= [1 -0 -1 11]
(1 -1 18/ -1 11)((1
-1 -1 -11) =
E {(tt)
1 - =]
M(Attg.Atts)
R AAttt,
1
1
-1
AAttg;Attt))
[1
-1
1
-
[1 -1
1 11 -1 0
111 1 0
1) T
-1
4 2
4
Note that for any A, the residual matrix R. has similar structure QA except that where QA has an identity matrix in its kron product, RA has subtraction matrix (e.g. [] -1] | -1 Meanwhile the covariance matrix ΣA looks like R R except that the vectors full of have been first removed.
18

---

How do we interpret the residual matrices? Well, R2 is the sum query. In fact the matrix vector multiplication Rax gives us the total number of people in the data.
Next, (A tells us the information contained in the marginal on {Ath} } that is not contained in the sum query. If we know the total number of people in the data, then the only new information the marginal gives us is the difference between the number of people with Att = a and the number of people with Att, b. In other words, RiAt, jx this difference. Given this difference, and the total, once can recover the marginal on attribute Att
Similarly, (At))) contains the information in the marginal on {Att2) that is not provided by the sum query. Finally (Atss) contains the information in the marginal on {Alla) not provided in the sum query, which is the number of people with AM3 = minus the number with Al23 = 2, and also the number of people with Att3 = 1 minus the number with Attz = 3. The product R returns those two differences as a vector with two components.
Now, R (Atts,, and R. Atts) are more complicated, but have the same idea. For example, R AAt)) represents new information that the marginal on {All1, All2) provides that is not captures by the sub-marginals (the marginal on {Att1} } and the marginal on [Att2].
In general, the matrix R. represents the new information on that the marginal on A provides, which not captured by the marginals on A', for A' C A (strict subsets).
Now, Theorem 4.2 tells us that if we take all of the rows of all of the residual matrices, they will be linearly independent. Furthermore, given attribute set A, the total number of rows of RA for all A' C A is the number of rows in QA Furthermore, the space spanned by those rows is the same as the space spanned by the rows of QA-
This also means that if we know R for all A' C A then we can figure out QA x (and vice versa).
Now, we want to get privacy-rreserving (noisy) answers to the marginal queries in Wkload = {[Att]], [AMt, Att2]: J: { {Att2, Attz]] that are as accurate as possible subject to privacy constraints. We quantify accuracy using regular (Definition 4.1) loss function (e.g., sum of the variances of the answers to the marginals) and we quantify privacy by setting privacy parameters for either (e, ddddifferential privacy, p-zCDP, or G--aausiin differential privacy.
Theorem 4.4 says that to maximize the accuracy subject to privacy con- straints, we need to take the closure of the workload, closure(W 0. [Att]]. [Att2], [Attt),[AAtt,.. Attz), {Attg, Attz} } and carefully choose positive numbers o² for each A E closure W (Skurrd so that is 6 numbers total. These numbers are chosen without looking at the data (we explain how in Section B.6). Once we have these numbers, we run the mechanisms MA (x:02) and return their outputs. In other words, we must release the outputs of:
Ma(x; a produces I number (a vector with just one component)
MMAun ) (x; o (Au))) produces I number (a vector with just one component)
MMquu)) (x: o (Atts))
produces 1 number vector with just one component)
MMAat)) (x: o7 (Aus))
produces 2 numbers (a vector with 2 components)
MMAu (x; of Aum) - produces number (a vector with component)
MM(Au (x; of Atts) produces numbers (a vector with components)
Which gives us total (noisy) numbers. In fact, any matrix mechanism for this workload must return at least 8 noisy numbers, by Theorem 4.4.
From these outputs, one can reconstruct noisy answers the marginals in W Wklond (actually one can reconstruct noisy answers to any marginal in closure kload)). We show how to do this in Section B.4. Then we show how to compute the privacy cost and variances of the algorithm in Section B.5.
B.4 Reconstruction
Let WA denote the output of MA. Thus, after running
* .Mo(x;o()
19

---

(x:0)
(x;
(XA
MiAtta 0f (Ats)
and M(Aut, (x; of [Atts
have the noisy answers
wig "[Att) "[Atta) ([Ats)s W(Ar)
A(Att
From these noisy answers we can produce noisy answers for any marginal in Wkload or even closure(Wkllodd To reconstruct marginal on A, need W for all A C A-this these vectors represent as many noisy numbers as there are cells in the desired histogram. So, for example, if we want to get noisy answers for the marginal on {Att2, Att3 (which has 6 cells), need to use wp. ) (.tt)). and w Attts (together these w vectors represent a total of noisy numbers).
this is not lot as
In order to reconstruct the marginal on A, Algorithm multiplies each W by a matrix that depends on both A and A'. The algorithm calls this matrix U, but to make the notation precise for this runthrough, we will call it UA-A' (the U matrix that multiplies WAr when reconstructing A). turns out that:
QAX= = Σ UA-X
A'CA
which means that the marginal A could be recreated if know the quantities RA (recall RA are the matrices used to define our base mechanisms). Now, since w is noisy version of RAIx, can get noisy marginal answers by substituting in these noisy values into the above equation.
For example, to reconstruct a noisy answer to the marginal on {Al2,, Alla), we the following:
Noisy Marginal on {Att2, Attz]
(U Atts
+ (U (Att) (Att)) (Atta)
+ (U (Att, (Atta) ) (Attt)
+ (U (At6 (Ate Atts)
where
1/3
1/2
U A
12
2
13
x
1/3
1/2
1/3
1/3
U (dltt,Att)) = Subb
8
l3
1/2
1/2
1/3
1/3
1/3
1/3
U (dtt) =
12 2 (ubby]
1/2
1/2
x
2/3
1/3
1/3
2/3
1/3
1/3
U (Atte (Wt (Atto,AAt) = (ubb² & Subb}
=
-1/2
1/2
8
2/3
1/3
1/3
2/3
Note Subţ and Subj are defined in Lemma 4.6.
B.5 Privacy Cost and Marginal Variances
Recall that for marginal workload W kload, we need to run mechanism MA for each A E closure(W (kodd). Theorem 4.5 shows how to compute the privacy cost peost of each. our running example, this means:
(ooos(MM((x;op oz
20

---

pcost(M(ann) (x; o (Att,)))
of A
moos((MAat)) (x; (x50((AA)))) (Acrs)))
of Arta)
prosi(M (ANCs) (Atts))
(Aetg)
(AUt of Atts
o Pien
and pcost (M (1tt2, A Atta)
of
callo
of Artt))
The total privacy cost is.
2
1
2 [Att.]
2 (Atta)
4 7
(Atta)
Attts
AAts)
Thus this is a symbolic expression in terms of the (currently unknown) noise scale parameters x According Definition 2.3, we can convert the privacy cost the p in p-zCDP by dividing by 2 and we can convert it to the μ from p-Gaussian DP by taking the square root.
For running example, W Wkload {{Attı); }. {Att1, Atty). {Attz, Atty]] }} and express the variance of these marginals (after reconstruction from the noisy WA answers) also terms of the noise scale parameters. We do this with the help of Theorem 4.7.
Marginal on {Att1}. This marginal is reconstructed from the noisy answers wp and (Asss) and so the variance of its cells depends only of and of (AA,,)) Applying Theorem 4.7, get that the variance in each cell of this marginal the same and equals.
* 2 - (oiAN 1
Marginal on {Att1, Attz). This marginal is reconstructed from We, W(At,) ) W(Atts): ) and AUt)) and hence the variance of the cells in the marginal depend on the corresponding noise scale parameters. The cell variance is
2
+
1 - 22
(oiAnE))
1 1 ) (cjAAce..Au)) 22
1
2
22
Marginal on {Att2, Attz). Similarly, this marginal also depends on noise scale parameters
follows:
1
(oiAna))
1 1 (AAss)
( *3 *3* 22
2 1
+
2
0
2 32
+
* 32
*
B.6 The -aariaf-Varianees Loss Function
Now we can express the overall privacy cost symbolically in terms of the noise scale parameters. We can also express the variance of each marginal cell symbolically. We can use these symbolic expressions to set up any regular loss function and then run it through a convex optimizer to solve
In this section, we give an example for the weighted sum of variances, which one of the most popular loss functions for the matrix mechanism in research settings (mostly because this loss function is casiest to work with).
Each marginal has weight, which we set to be to avoid introducing more symbols, and the objective function is computed by adding up the cell variances in a marginal, multiplying by the weight, and adding up over the workload marginals. The marginal {Att,} } has two cells (so multiply the cell variance for this marginal, computed the previous section, by 2). The marginal on (Alli, Alla) has 4 cells, and the marginal on (All,, Alla) has cells. Thus, after the dust clears, the sum of the cell variances across the workload marginals is:
11
3
12 oe + LA + gisn + o(su) + ounm 20 Atts
21

---

Thus, we can set up the optimization problem: minimize the sum of variances subject to the privacy cost (computed in Section B.5) being less than some constant
5 12 0 2 i σ + oauss + to Aut) + 2 + Atts)
11 3
arg
min d of
aiaueg gaas)) of oiau A AMM))
1 such that 0
1 +
+ 20
+
c
(Am,)
2 20
(Aut)
3 3
(Atts
4 40 AAts
3 30 (Alts,Atts))
If we let the coefficient of σ be denoted by VA and the coefficient of 1/03 be denoted by PA, then this optimization problem can be written as:
arg Acclosure W kload)
Σ
UA
A AEclosure W klond)
s.t.
Σ
PA
S
2
O'A
Acloosuro W kloud)
Lemma H.1 in Section shows that the optimal solution obtained by computing:
== Σ VAPPA /c=
(V
11 +1+
1
1 * + /2/3+ V1/4+ v2/3 /c
12
*
2
* +
2
V 6
2 21.18/c
A (TPA/(CUA)
/21.18pA/uA/c
~ 21.18 12/11/c 4.8/c
etc.
C Example Variance Calculations
We next illustrate how the a parameters affect the variance different marginals based on Theorem 4.7. We illustrate it with toy dataset that has 5 attributes, each with 3 possible values. In this discussion, the variance of a marginal is the largest variance of its cells (all cells within the same marginal have the same variance, the variance of marginal is basically the variance of any cell).
EXAMPLE C.I. The objective function is minimize the max variance among all marginals while satisfying p- y-Gaussian DP with p=1. In this case all marginals end up with the same variance of 7.594 and the a parameters are:
o 7.594
A 10.125 when A contains I altribute.
d A 13.5 when A contains attributes.
A 18 when A contains 3 attributes.
A 24 when A contains 4 attributes.
A 32 when A contains all of the attributes.
EXAMPLE C.2. The objective function minimize the weighted max variance among all marginals (i..., minimize max, weightm * vor(m)). We set the weight of a marginal to be 3 if it is the 5-way marginal and otherwise. This objective function basicully says we want more accurucy on the 5-way marginal (it has higher weight). Again the privacy constraint is I-Gaussian DP. In the optimal solution, each cell the 5-way marginal has variance 2.718, the 4-way marginals have variance 5.528, and the other marginals have variance 8.154. The o parameters
22

---

0 8.154
0 A 10.871 when A contains I attribute.
A 14.495 when A contains 2 attributes.
A 19.327 when A contains 2 attributes.
4 12.477 when A contains 2 attributes.
0 4.159 when A contains all of the attributes.
For the variance calculation, we show this for Example C.2.
We start with the variance of a one-way marginal, say the marginal on attribute (i.e., A The calculation involves (1) and og (because @ S {1}) and the summation has two terms. The term involving og is multiplied by 1 (the first product in the variance expression for Theorem 4.7, since an empty product is 1) and that is multiplied by 1/9 (the second product, since each attribute has possible values). Meanwhile, the term involving oi would be multiplied by 2/3 (first product) and 1 (since the second product is empty). Thus the variance for the marginal on attribute is: 8.154 1 1/9 10.871 2/3 1 R 8.154.
{1}).
For the variance on the 5-way marginal, consists of I term for A' = 0, 5 terms for when A' has 1 attribute since there are 5 such A' (but all the terms have the same value), 10 terms for when A' has attributes (all have the same value), 10 terms for when A' has 3 attributes (again these terms all are equal). 5 terms when A' has 4 attributes, and term for when A' = {1, 2, 3, 4, 5). First, we note that the total number of terms is 32, which not bad because the number of cells in the 5-way marginal is 3 (i.e., much larger). The expression for the variance is:
1 (8.154 (2/3)" (1/9)²)
(the term involving of) (the sum of the terms having A' with attribute) (the sum of the 10 terms having A' with 2 attributes, etc.)
+5 (10.871 (2/3)² (1/9)²)
+ 10 (14.495 (2/3)² (1/9))
+ 10 (19.327 * (2/3)² (1/9)²)
+5* (12.477 (2/3)* (1/9)²)
+ 1 * (4.159 * (2/3)5 (1/9)))
~ 2.718
So the main takeaway here that when evaluating the variance of the 5-way marginal, the 1/9 terms in the products reduce the influence of any o² for which A' has small number of attributes. Hence the most important value is o (1.233,455) followed by the o² for the 5 sets A' that contain 4 attributes, etc.
D Optimality Proof of ResidualPlanner
In this section, we prove the optimality of ResidualPlanner. It takes advantage of the symmetry inherent in marginals and regular loss functions.
The proof sketch is the following. Given one optimal mechanism M, we can create a variation M of that does the following. (1) M modifies each input record by applying some invertible function fa to each attribute Att, (for example, if Att, is a tertiary attribute, we can modify the value of Att, for each record using function f, where f(( 3, f22 = 1, f((3 2). This step can be viewed as simply renaming the attribute values within an attribute. (2) Then M runs M on the resulting dataset. Note that marginals can be reconstructed from the output of M by first running the reconstruction one would do for M and then inverting the fi functions on the resulting marginals (i.e., rearranging the cells in each marginal to undo the aithin-at renaming caused by the ft). This variation M has the same privacy properties M and the same loss (due to the regularity condition on the loss).
23

---

Hence M is also optimal. Then we create yet another optimal privacy mechanism M that splits the privacy budget across all variations of M and returns their outputs. turns out that the privacy cost matrix of M has eigenvectors that are equal to the rows of the residual matrices R. used by ResidualPlanner. Rewriting the privacy cost matrix of M using this eigendecomposition, we create another mechanism (the mechanism that runs the base mechanisms of ResidualPlanner) that has the same privacy cost matrix and the same value for the loss and hence optimal.
The rest of this section explains these steps in details with formal proofs and running commentary that helps to better understand the notation and constructs in the proof.
D.1 Notation Review
We first start with review of key notation. Recall that dataset D (r Fn) is a collection of records. Each record r, contains attributes (J)
Attn, and each attribute Att, can take values
di .......AAA, |Aus)"
An attribute value 0. for attribute Atty can be represented as a vector using one-hot encoding. (5) Specifically, let ei be row vector of size |Atty] with one in component and 0 everywhere else.
In this way, e/ is representation of (5)
A record with attributes Att, 0ig Atl2 0
(1)
(2)
(ma) Att.,, ain. can thus be represented as
the kron product Ci 60e ... ge (n.) This vector has exactly one position and Os everywhere else. The position of the is the index of record
(2)
Thus, a data vector x is vector of integers. The value at index i is the number of times the record associated with index appears in D.
D.2 Permutations
For each attribute All,, let (T) be the set of permutations the numbers 1,..-, |Al4s), that each E IT()) can be interpreted as a permutation (or renaming) of the attributes values of Att,, We can also view as a function on vectors of size |Att;| that permutes their coordinates. That is, the 7th coordinate of a vector y is the (i))t coordinate of 7 (y).
One can select a permutation for each attribute (1)) E (1)
(ma) E (m() and use it to de- fine a permutation over records. This permutation maps record represented by the kron product (na) into π (e(, (2) (o)))))).... (o (ma)
(1) 00 60 B.e
(2)
(e(
(())). We can think of this permu-
tation (T()), ( as function that independently renames each attribute value in record. Thus this permutation can be extended to datavectors x. The value of x at the index associated with record is the value of æ (x) at the index associated with record (r)). Another way look it is that π (x) is the histogram associated with the dataset (m(r1), ),, o (r2),.... क (ra)). This permutation permutation matrix W, such that W (x)).
can be represented
We let II (1) permutations since each æ E II renames the values of each attribute separately.
(ma) be the of all such permutations. We call this the space of renaming
Our first result is that permutation does not affect the privacy parameters of mechanism.
LEMMA D.I. Let M(x) Bx + ( Σ) be a mechanism that satisfies p-zCDP, (e, d)aaproxximate DP, and μ u-Gaussian DP. Let be permutation of the indices of x and W n the corresponding permutation matrix. Then M BW x + N Σ) satisfies p-zCDP, (c, 6) apppprxxiee DP, and μ y-Gaussian DP (i.e., with the same privacy parameters).
Proof. The privacy cost pCost(M) of M the largest diagonal of B The privacy cost (c) of M, t the largest diagonal of E The effect of W- - on both sides to permute the rows and columns of - 'B in the same way. Thus the diagonals of B - and WTB - are the same up to permutation and hence M and M, have the same privacy cost and therefore the same privacy parameters.
24

---

The next result is that renaming permutation preserves the accuracy of a marginal derived from the answer mechanism.
LEMMA D.2. Let Wkload = {A1...., A be a workload on marginals. Let M(x) = Bx [(. Σ) be a mechanism whose output can be used to provide unbiased estimates of those marginals. Let E II be a renaming permutation and W the corresponding permutation matrix. Define M2 (x) BW 3Wxx++ OO Σ). Then unbiased answers to W kload can be obtained from the output from
of M and for any regular loss function & (Definition 4. I), L(V ar A1;M),..... Var( Ak; M)) (A1; ...... Mz))
Proof. For each set of attributes A; E Whload, let QA. be the query matrix of the marginal (i.e., the true marginal is computed as QA,x). Then the best linear unbiased estimate of the marginal on A, from the output w of MM is is the diagonal of the covariance matrix of this estimate, which is QA, (B"E='B) B)QQ Mcanwhile, the best linear unbiased estimate of the marginal on A, from the output w/ of MM is is QA, (W" B" Σ 'BB,, " I''w' and Var(A;; is the diagonal of QA, W (B" BB)..
'B)'"""" w and V (ar(Ar; M)
Qw,T"""T BB,,
We note that QA, W is permutation of the rows of QA, (computing marginal on dataset in which attribute values within the same attribute are renamed is the same computing the marginal on the original dataset and then renaming the marginal cells, which is permutation of the output of the marginal computation).
Therefore the diagonals of QA, (B'E and QA, (W 1 are the same up to permutation. Hence the vector Var(A,;M is the same as the vector V "ar((A)))) M2) up to permutation of the components, and hence does not affect regular loss function L.
Finally, we show that there exists an optimal mechanism whose privacy cost matrix exhibits symme- tries defined by the set of permutaitons II.
LEMMA D.3. Let W Wkload= = {A1 ......, Ar} be a workload of marginal queries. Let L be a regular loss function. Let U be the set of all Gaussian linear mechanisms that can provide unbiased answers to the marginals the W kload. Let y be a real number. Then whenever either of the following optimization problems are feasible,
min pCost(M) s.1. C(Var(Ais) (A;; Var(Au; 52 MEU
min MEU
L(V Var(As; s.t. pcost(M) S
the feasible optimization problem is minimized by some mechanism of the form M(x) = Bx N NO, Σ) whose privacy cost matrix r = E has the following symmetries: for all renaming permutations E II (with Wz being the associated permutation matrix), we have I = WTTW, (in other words, permuting the rows has no effect as long as the columns are permuted in the same way).
Proof. Let Mopt = Bopt NN., Eopt) ) be an optimal mechanism one of these problems. may not have the required symmetries, but from it we will construct an optimal mechanism that does.
For permutation æ (and corresponding permutation matrix Wz) and positive number X, consider the mechanism Mx,x(x) = B Bop W x + N N(0, oppt) By Lemma D.2, this mechanism also answers the marginals in W kload.
Now consider the mechanism M which, on input x outputs the result of Mr for all i E II.
B Boys W
The query matrix of M B
and the covariance matrix Σ is block diagonal matrix
Bop
with the scaled matrix [T Eopt each block. Clearly, by Lemma D.2, also provides unbiased answers to the marginals in W kload.
25

---

First, we claim that the (Cost(M I pcost(M Mopt) so that the privacy parameters are at least as good. Recall PCost(M is the largest diagonal entry of:
B' B=
Σ W TEI
B E opt
B Bopt Wx,
Since the privacy cost (Most(Ma,,) is the largest diagonal of W pcost(Mopt), Equation 4 (and convexity of the max function) shows that the pcost s pcost(Mopt))
opt Enpt Byj W and equals
Next we consider the loss function. Let A, E Whload be a set of attributes and let QA, be the corresponding query matrix for the marginal Aç. Then the reconstructed variances of the answers to this marginal, based on the output of M is:
Var(A,; M) diag QA. (B Σ O))
diog
1 Σoa
(WTB² 2 Ws, )'xx
0%
1
Var Var(Ar;MM.1)
III
For any π E II, Lemma D.2 tells us that
Var(As; Mopt))
C(V ar (r; Mz,),,,......... Var(AA;;M,)) and so regularity of C (which includes convexity), means that C(V al ()
Var(Ar;MM) S (op)) Var Var(Ax; Mop)))
Thus M is worse in privacy utility than Mopt and hence is optimal.
Thus we consider the symmetries of the privacy cost matrix of M, which is given in Equation 4. Clearly it has the desired symmetry property that = wTTW, for any ι E as the permutation space II is an algebraic group.
D.3 From permutations to interpretations
Let Mope (x) = B Bopt + (N, Eopt) be optimal mechanism that has the symmetries guaranteed by Lemma D.3. Our goal is to use the symmetries in the privacy cost matrix T opt B Sop! Bopt to examine the structure of optt
If Yh is the th entry of Topt and if there is a renaming permutation that maps r, (the record associated with index i) to some (at index i') and maps r; to some ry then Yij 3 Note that if r; and ry have the same values for attributes Att, and Attz then ræ and ry must match on the same attributes because renaming permutations just change the names of values within each attribute. Thus we introduce notation for the set attributes on which two records match:
DEFINITION D.4 (Common Attributes). Define Ç to be the function that takes two records and outputs the set of attributes on which they match We emphasize that Ç(r,; FT) is set of attributes, not attribute values.
This discussion leads to the following result which characterizes the privacy cost matrix of optimal mechanism.
LEMMA D.5. Under the same conditions as Lemma D.3, there exists an optimal mechanism with privacy cost matrix oopt for which the following holds. addition to the symmetry guaranteed by Lemma D.3, for every subset of attributes S C {Atti,..., Att }. there exists number es such that Th.jj the (i, entry of I Popss equal to Cc(rur,)) In other words, the (i, entry is completely determined by the set ((r,,r)) (recall r, the record value associated with index and ry is the record value associated with index j).
26

---

Proof. By Lemma D.3, there exists an optimal mechanism with privacy cost matrix I Topt that is invariant under renaming permutations of its rows as long as the columns are permuted in the same way. Thus if r. is the record value corresponding to position i and ry is the record value corresponding to position j. there exists a renaming permutation that maps ry to some ry and r to some r'g and only if the attributes on which r; and ry match are the same the attributes on which ry and ry' match each other (in symbols: [(ri, r3) = ((re,Ty)) r)))). When there exists such a renaming permutation then 7io W,,. Thus the value of "/s is completely determined by <(ri, T3) and the result follows.
From Theorem 4.2, we know that the rows of the matrices of RA. for all A S {Alli...., Alla,, } are a linearly independent basis for Rd, where d = nu i=1 [Atty]. Thus we call the rows a residual basis.
DEFINITION D.6. A row vector is residual basis vector if it is a row in RA for some A S }.
We now provide an interpretation of the residual bases. First, for an attribute Attz, define the vector ( to be a vector of length |Attyl such that the element at position i is 1, the element at position (2)
ei. E (E) (e) (recall e; is I in position i and 0
is 1 and everywhere else is O. In other words,
Ej
everywhere else and is one-hot encoding of the attribute a; ). Now, each element of the residual basis has the form v @ ("a))) where, for each E, v-(*) is either the vector 1 1/Anta or vector (e)
(
1, When the vector for attribute Alle is the vector 1 |A we say that all attribute values of Allz are selected. When the vector for Alte is ei then we say attribute value ( is positively selected and dic negatively selected (the other attribute values of Att, are not selected at all). The attributes for which the kron term is not 1/trs are called the discriminative attributes.
(8)
As an example of this notation and terminology, consider Table 8. Suppose we have three attributes: Att takes values 'a' 'b'; Atty takes values 'y' or 'n'; Atty takes values I or 2 or 3.
ay1
ay2
ay3
anl
an2
an3
byl
by2
by3
bml
bie
bn3
bnl: j0. 10 1,000
0
0
0
0
0
0
0
0
0
1 [1, 1, 1,
1
0
-1
1
0
-1
0
-1
0
0
-1
0
-1
0
1
-1
0
1
Table 8: Kron product representations.
In this case, the data vector would have 12 components. The first component corresponds to the number of appearances of record "a.y.I" in the dataset, the second component corresponds to record "a.y.2" and so on. The records corresponding to each index of x are listed in order as the column headings in Table 8. The first row shows the representation of record "b.n, 1"", which is composed of the second value (b) for Att,, the second value (n) for Attz and the first value (1) for Att3. Hence its kron representation is [o. 1] [0. 1]@ [1, 0, 0] and when the kron product is evaluated, the resulting vector has a in the index corresponding to "bnl" (10th column) and 0 everywhere else.
The second and third rows show the expansions of two residual basis vectors [1, 1| (its discriminative attributes are Alla and Allz) and [1, 11,-1[63 1|0 (1,
-1,0
1) 011 (its discriminative
attributes are Atl and AM23). Consider again the kron product [1, 1 11] -1. Note that the first part of the kron product, [L, 1] refers to the first attribute and selects both of its values (sets them to 1). The second part of the kron product [1, -1] refers to the Att, and positively selects the first attribute value 'y" (sets it to 1) and negatively selected the second attribute value 'n' (sets it to -1). The third part is [1, 11, 0] and it positively selects the first attribute value, negatively selects the second, but the third attribute value is not selected at all (i.e., the 3rd position is 0). These attribute selections can help us determine what the kron product looks like when it is expanded as follows. For the residual basis vector v (1)
0].
gg (m,) the value at the index associated with a record r is
* O if r has an attribute whose value is not selected by the residual basis vector's kron product. In this case we say the residual basis vector assigns a to record r. For example, in the residual basis vector corresponding to kron product [1, 1]11](11 -1] -1, 0), the third value of the third attribute not selected. For any record that assigns the attribute value 3 to Attg, this residual basis vector assigns a 0 to such record.
27

---

if for every attribute, the value assigned to it by is selected (posititvely or negatively), and the number of negatively selected attribute values is even. In this case we say the residual basis vector assigns a 1 to record r.
-1 if the attribute value for each attribute is selected, and the number of negatively selected attribute values is odd. In this case we say the residual basis vector assigns a -1 to record r.
For example. for the residual basis vector [1. 1| 1, - -1] 0j. the attribute value 3 for Attz is not selected. Hence the value at indices corresponding to records an3, an3,bn3.ay3.bby are all 0 (see Table 8). Next, consider the record an2. The value "a" is positively selected, "n" is negatively selected, and "2" is negatively selected. Hence all attributes are selected and an even number of attributes are negatively selected. Therefore the value at the index associated with an2 is 1. Now for the record by2. The "b" positively selected, "yy is positively selected, and "2" is negatively selected. Hence there are an odd number of negative selections and so the value at the index associated with by2 is -1.
With this discussion and associated notation, we can now show that each residual basis vector is an eigenvector of the optimal privacy cost matrix, and the eigenvalue only depends on which attributes are discriminative.
THEOREM D.7. Under the same conditions as Lemma D.3, there exists an optimal mechanism such that the eigenvectors of its privacy cost matrix I are the residual basis vectors (Definition D.6). F Furthermore, if two residual basis vectors v()) (..8(((T.)) and w (1) ('))... (w((=a) have the same discriminative attributes for all i, w()) * A if and only v + 1 Auc,) #1'Au,
then the two residual
basis vectors have the same eigenvalues (in other words, all rows of the same residual matrix have the same eigenvalues).
Proof. Recall from Definition D.4 that ((ri,rz) is the set of attributes on which r; and ry are equal.
Let P be the privacy cost matrix guaranteed by Lemma D.5 with the properties guaranteed by Lemma D.5, namely that for every subset of attributes S C {AAtt...... Attn, }. there exists a number os such that W.j. the (i. (h entry of r, is equal to eç(r..r)) - the constant associated with the set ((ra.Ty), where T; the record value associated with index i and rj is the record value associated with index j.
Let be record associated with index f. We consider the dot product between residual basis vector (P)) ... (n()))) and the hd row of P. Since the entries of the gth row are C((r2.r)) C(trair)) and the entries of are 0,1,-1, this dot product can be expressed as:
Σ c((re))
Σ
CC(rer)
(5)
assigned value by
assigned value -1 by
We analyze this in three cases.
Case 1: v assigns a 0 to re. In this case, there is an attribute for which re has a value that is not selected. Without loss of generality, (the vector with I at the first index and -1 at the 7th index for some i and 0 everywhere else) and the value of All, for r' is therefore not aj or (1) (because ry got assigned by v due to attribute A Now, if a record appears in the left summation of Equation 5 then its value for All, is either aj or a;
may assume this is the first attribute Att, so that v(!) 61,
(1)
(1) (1) and it does not match re on the first attribute. But this means that we can transform
r into a record r' by replacing 01
(1) and a with each other. This r' would be on the right hand side of the summation (because we are flipping the sign of the selection by of attribute Att, in r'). Furthermore r' also does not match ra on Att, and therefore r matches r'g exactly the same attributes as r' matches rg. Thus ((rer)) = C(re, Thus the summation term from record is cancelled out by r' in Equation 5. Using the same argument, we see that every term in the left summation is canceled out by a unique term in the right summation, and vice versa. Hence, if v assigns 0 to record ry (i.c., has a 0 in index l when its kron product representation is expanded) then the dot product between v and the 4h row of I is O.
Case 2: assigns 1 to rg. In this case, every attribute of ry has value that (either positively or negatively) selected by and even number are negatively selected. Our goal is to show that if
28

---

and & is its some other record rt is also assigned 1 by v, then the dot product between v and eth row of I is the same as the dot product between v and the ht row of T. That is, we want show:
Σ c((ra))
Σ
c((re))
Σ Cc(Fe))
Σ
cc(re))
(6)
I assigned value I by
7' nssigned value - by
7. assigned value by
I' assigned value -1 by
Let be the set of attributes on which ry and r, disagree. Now define mapping ø between records such that ø only modifies attributes in S. For each attribute Att in S, it maps the value that record ry has into the value that T, has an vice versa. (For example, suppose S {Att,, Att2] and re
has values a2 (1) and (2) for those attributes, respectively, and suppose that rı has values 04 (1) and
a for those attributes. Then @ changes a Att, to 04 and changes ( into a,); for Attz it changes 03
(2) and changes ag into agg") Thus Φ(rz) r₁ and ((r:) own inverse. Furthermore, for any record r, ((r,.r) ((d(r)), = ((rr.((r)) since renaming attribute values the same way in two records does not affect the set of attributes which they match (and the last equality is because ((re) rt).
(2) into 0s
We next note that since and ra are both assigned by then they must differ on even number of discriminative attributes of v (if they differ on a discriminative attribute, one must have a value that is positively selected and the other must have value that is negatively selected there cannot be because ry and r, are not assigned 0 by v). Therefore, due its definition, & modifies an even number of discriminative attributes and therefore for any record both r and (6r) get assigned the same value by v.
Putting these facts together, we get:
Σ assigned value I by
Σ
(((r)))
C((rn))
y ussigned value I by v
Σ
Ce(rei))
Σ
Cc(re))
since doesn't it change the summation set
d(r) assigned value by v
((r) assigned value -1 by
Σ
(c(o(r))
Σ
(((0(r)):0(1))
since & preserves the outcome of
d()) assigned value by w
@(r) assigned value -1 by
Σ
c((r))(())
Σ
(((())())
since <(re)
d(r) assigned value by v
((r) assigned value by v
c((r))))
Ce(ra)))
renaming the summation variable from ø(r) to r'
assigned
r' assigned value 11 by v
value by
and that proves Equation 6
Case 3: assigns a -1 to rz- In this case, every attribute of re has a value that is (either positively negatively) selected by and odd number negatively selected. Our goal is to show that if some other record is assigned a 1 by then the dot product between v and 4h row of I is the negative of the dot product between and the th row of Г. That we want show:
Σ cc(re)))
Σ assigned
(((r)))) =- Σ
Σ cg(re))
cc(r..)) +
(7)
F' assigned value by
assigned value by
assigned value by
value -1 by
As in the previous case, we define the same way and reasoning as before we see that for any record ((r,.r) ((o(r)), ((r,, o(r)) and since now á must change odd number of

---

discriminative attributes (since and are assigned -1 and 1 by v) then for any record r, the value assigned by v is the negative the value assigned to ((()) by v. Thus we have:
Σ assagmed value I by
Σ
(((r))))
c((ra.))
r assigned value I by v
Σ
cc(re.)
Σ
Os(re.))
since flips the summation sets
((r) assigned value -I by
(fr) assigned value +1 by
Σ
(c(A(re))(())
(((O(re))((r)
since & preserves the outcome of
(ir) assigned value -I by
((r) assigned value +1 by by
Σ
c((re)(())
Σ
(c(mao(r) since Φ(re)
Φ(r) assigned valuee -1 by v
((r) assigned value by
(((r()))
((())))
renaming the summation variable from @(r") to r'
r assigned value by v
assigned value
and that proves Equation 7.
Thus what these 3 cases show us are that there exists constant / such that:
If the 1th position of the expansion v 0 (i.e., rs is assigned 0 by v), then the it position of Iv is also 0 (the dot product between the 2th row and is 0).
If the 1h position of the expansion of (i.e., is assigned by v), then the 1 position Tv is (the dot product between the 7th row and v is B).
If the 1h position of the expansion of v -1 (i.c., T2 is assigned -1 by v), then the 1h position of Iv -B (the dot product between the 7th row and is -B).
Thus v an eigenvector of with eigenvalue 3. That proves the first part of the theorem.
The next part of the theorem is to show that if two residual basis vectors have the same dis- criminative attributes, then they have the same eigenvalue. So let v = (1)) gy(()) and w w(1) & (na) be two residual basis vectors that have the same discriminative attributes. Define renaming permutation follows:
For an attribute Att, that is not discriminative for v (and hence also not for w), n does not rename its values (i.c., it acts the identity for those attribute values).
For a discriminative attribute Alle, let 61,1, the kron component for v (i.e., v(0) e1,iz) and let ei be the kron component for w. Note the indices is and jr are not equal to 1. In this case, we make æ do the following renamings:
ai + Oje
aj. -> 0i,
The remaining attribute values are unchanged.
By considering which records are assigned 1,-1 and by v and w, is clear that и converts into w (and vice versa). Let W be the matrix representation of the renaming permutation æ, so that Wv w and W v (a permutation matrix is orthogonal, so inverse is its transpose). Thus, letting 3 denote the eigenvalue of v with respect to I, we have:
=v= = Iv
T
30

---

-WTWWW w due to the symmetry from Lemma D.3
Wwww
since W is the inverse of W and
Bw = WW = wW = Tw
and thus has the same eigenvalue
Thus each residual basis matrix R has a useful property: its rows are linearly independent and are part of the same eigenspace (linear space of vectors with the same eigenvalue) of the privacy cost. matrix P of an optimal mechanism. This allows us to prove the main result:
THEOREM 4.4. Given a marginal workload W klood and a regular loss function L, suppose the optimization problem (either Equation 1 or 2) is feasible. Then there exist nonnegative constants a for each A & closure kload) (the constants do not depend on the data), such that the optimal linear Gaussian mechanism Mopt for loss function L. releases Ma(x; (x; for all A closure( W kload). Furthermore, any matrix mechanism for this workload must produce at least this many noise measurements during its selection phase.
Proof of Theorem 4.4. Let ALL represent closure ((Att1, Atttr }) tributes. Theorem D.7 guarantees that there is an optimal mechanism whose privacy cost matrix has eigenvectors equal to the rows of the residual matrices. Rows within the same residual matrix have the same eigenvalues. Since privacy cost matrices are symmetric positive semidefinite, this means that for every A E ALL, there exists nonnegative number 3A such that:
all possible subsets of at-
TRA BARA
By Theorem 3.5 of [47], if two Gaussian linear mechanisms have the privacy matrix then each can be obtained by linearly processing the other. Thus they have the same privacy properties (under any postprocessing invariant privacy definition) and can be used answer the same queries with the same exact accuracies (under any measure of accuracy). Thus we just need to construct the appropriate mechanism having privacy cost matrix r.
For each A, let Za be a matrix with orthonormal rows that span the row space of RA Thus the rows of ZA are also eigenvectors of I (having common eigenvalue AA) and the rows of ZA orthogonal to the rows of A for A + A' (a consequence of Theorem 4.2). Thus the set of rows the Z for all A ALL complete list of the eigenvecotrs of T (the are linearly independent and span RRd). Thus the (symmetric positive semidefinite) privacy cost matrix T can be expressed as:
r
Σ BAZ ZA
AEALL
and one mechanism that achieves this privacy cost matrix is the one that releases ZAX + N(0 FA I) for each A ALL for which BA # (i.c., we can drop the eigenvectors with eigenvalue equal to they make difference to the privacy
matrix).
Now, since the rows of RA and ZA are independent linear bases the same subspace, then there exists an invertible matrix Y A such that RA YAZA. Furthermore, RAR is invertible and ZA A = I by orthonormality of its rows. Therefore
A RA
YAAAA
Z (ZAZA) -Y
=ZA(ZAZ>) -ZA
=ZAZA
by orthonormality of the rows of ZA
Thus have
T= Σ (AR 'RA
AEALL
31

---

and a mechanism that achieves this privacy cost matrix is the one that releases RAX
N (O, 1 AA ) for each A for which AA # O.
We next note that each covariance matrices we propose to use, ΣA. is proportional to RA RA (they are equal up to positive rescaling). we define the positive constants KA such that RA = KA AA then we note that the x in the theorem statement are equal to KA/3A.
Next, we show that the eigenvalues SA > for A E closure W kload) and O otherwise, so that the optimal mechanism would not make use of any submechanism MA for A & closure (loodd).
First, by Theorem 4.2, the rows of RA, for A closure(Wkloudd) form an independent linear basis for the space spanned by the rows of the marginals Q for A E Whload. If a noisy RAX is not released for some A closure(W kload), then an unbiased noisy answer to at least one of the workload marginals could not be computed. Hence, they must all be part of the optimal mechanism (and thus, because of linear independence, any mechanism needs get at least as many scalar noisy answers as this). This shows that AA > 0 for all A E closure W kload). On the other hand since the rows of A are orthogonal to the rows of R& for A + A', getting answers to RAXX, x, for A' & closure [W kload), cannot help estimate the answers to the marginals Q^ for A E W kload (by Theorem 4.2, RA' are orthogonal the matrices representing these marginals when A' & closure ( kload)). Hence an optimal privacy mechanism cannot waste privacy budget on these irrelevant queries. This shows that AA = Ofor A' & closure (W kload) and concludes the proof.
E The other proofs about base mechanisms
THEOREM 4.2. Let A be a set of attributes and let QA be the matrix representation of the marginal on A. Then the rows of the matrices RA, for all A C A, form a linearly independent basis of the row space of Qa. Furthermore, if A' + A" then RARRA R 0 (they are mutually orthogonal).
Proof of Theorem 4.2. Consider two sets A' + A" and represent there respective residual matrices as:
R V @ V
RA V VVV'.VVV
R = (V 8V',, (V".)")
Since A' + A" then one of them contains an attribute, say Att,, that the other doesn't have. Therefore either V or V is the vector [/Au and the other is Subj However, 1/Am, Subjate = 0 and Sub | |tt,,] 0 and hence RA R O.
Next, for any set A', it is clear that the row space of A is contained in the row space of the marginal matrix Q It is also clear that if A' C A then the row space of the marginal matrix QA is contained in the row space of QA (because Q^ represents sub-mary mub-marginal of ).). Thus the rows of the matrices R. for all A' C A, are contained in the rowspace of QA Thus we just need to show that the combined rows of RA for all A' C A, are linearly independent and that the number of rows is the same as the number of rows of QA
First, each R A is a kronecker product of matrices with full row rank, and so R has full row rank (therefore its rows are linearly independent). Furthermore, since R. RR. = 0 whenever A' * A" this means that the row space of R is orthogonal to the row space of RA.. Hence the combined rows of the A for all A' C A, are linearly independent.
Next, the number of rows in R3 and the number of rows in RA equal
II ([Att,) 1)
AHLEAA
for A' + 0 and so the total number of rows in the residual matrices is 1 + Σ II (|Att,) - 1).
ACA.CEA
A 4D
By the distributive property of multiplication, this is exactly the same as the product:
II
1))
II Atr,
|Att,|
Att. EA
32

---

which is the number of rows in QA and that proves that the combined rows of RA for all A' SA. form linearly independent basis for the row span of QA
(uc,) LEMMA E.1. For any i, Subj Arc. (Sub, Au. Sub Atc.)) ) |SubjAu. = TAutl
lAce,
1 1/secal
[Ate,
Proof of Lemma E.I. For the moment, let denote SubjAm. (Sub) Art. Subj -Suul
Then know:
Y is symmetric.
Y is an |Att]] |Att,) matrix and its rank is |Atti| since the rank of Sub is
|Att,] 11
Subjau, YSub Auc.
At. Sub (Au.)
Now, one symmetric solution to the equation Sub Act, XSub [am, and X1 is another symmetric solution then Sub Att, (I [Tjn Sub T
( Atc.l Sub Am, Am, Sub T Amz,
is X
Att, = 0.
This means that Sub A 0 for each eigenvector of the symmetric matrix I|Att that has nonzero eigenvalue. Since the rank of Sub Art,] is |Att, 1. the only vectors for which Sub, Au, = 0 are proportional to | (the null space has rank 1) and so IJAu. XI = jau,
Xi
1 Atr. for some constant
This means that Y (and any other symmetric solution) has the form I [|Art.] + cl Att, TA To find c, we note that Y is not full rank.
By the Sherman-Morison-Woond
[Ate invertible, then inversion formula, if [| + cc cI
Thus, to its inverse is Iam, -cl c||/trt (1 c1 [Ate 1 1/A0e.1 = Iiamal - c 1+c prevent invertibility, we must have = -1 A/t/l Therefore Y I[A
Art, |'ve..
THEOREM 4.5. The privacy cost of MA with noise parameter o² is o IlAu,E the evaluation of MA given in Algorithm is correct i.e., the output has the distribution N AA).
|Atti|-1
AAC.T and
Proof of Theorem 4.5. Without loss of generality (and to simplify notation), assume A [Att,....,Att,, consists of the first attributes.
By definition, Scontttoo,pposs(MMooo peost(Ma is the largest diagonal of E RA. Thus we can write:
RA =
Subjamt
c
1 Lateyl
i=1
j=f+1
RT =
SubT
1 pateyl
iml
jmB++
H =
Subianti
X
[1]
(rightmost krons use x 1 matrices)
i=1
j=(+1
ΣΛ = HHT
(Sub Aut, Sub T (ece))
[2]
j=(+1
33

---

Σイ [Sub (Subian,,Suuaaaa Subfan,))
[1] 1++1
R RA
Sub Ats Am,, SubfAtr, SSub
1 |
1 1 1
j=l+l
(8)
Now, by Lemma E.I,
Sub Atc (Sub) Atc, / " SSbbAtc, I[au
1
Attt
Att.
Since its diagonals are
Atte -1 AtC
then combined with Equation 8 it proves the result for
We next consider the correctness of Algorithm 1. First, we need to show that for the matrix H defined Line in Algorithm HQAA== RAX. Then we can write:
RA
Sub SubjAm..
ACt.
&
1 |/reey
j=t+1
QA
I Lttil
x
1
|Att,
rightmost product is matrix with row
i=1
j=tt1
Sub
Subjani Atc.
8 [[1]
(rightmost term is matrix)
i=1
no Haus )
HQA =
(Sub Au, [iaui)
x [1]
j=t+1
RA
Next, we note that if z is distributed N(0, I,.) (Line 4 in Algorithm 1) then a Hz has the distribution (0, o² HH = EA and hence the algorithm is correct.
L
F Proofs related to the reconstruction step
LEMMA 4.6. For any Atta let l = |Att,) The matrix Sub; has the following block matrix, with
17
dimensions x (l (e-11 1), as its pseudo-inverse inverse (and right inverse): Sub/ = 1--1 EIe-1
Proof of Lemma 4.6. First, if matrix has a right inverse then that the pseudo-inverse. Hence we just need to show that SubySub/ Iz-1-
Note that the 7hh row of Sub; has position 1, -1 in position j 1, and is 0 everywhere else. Meanwhile, the ,th column of claimed representation of Sub! has - 1)/8 e in position + and 1/f everywhere else.
Hence if j # then the dot product between row j of Sub, and column of Sub! is 0 since the nonzero elements of the row from Sub, are being multiplied by 1/8 and 1/e.
If = j then the corresponding first elements that are multiplied are 1 and 1/e while the elements at Furthermore, 1(1/E) (-1)(-(e-
position i + being multiplied are -1 and
LEMMA F.I. For any attribute Att, let ll |Att,]. Then (ub, "Sbbb iT It 111
34

---

Proof of Lemma F.I. Because Sub, has linearly independent rows, the pseudo-inverse inverse of it can be expressed as,
Sub -Sub (Sub/SuD))
From lemma E.1 we get,
Sub/Sub: Sub / (Sub:Sub?) Subb
=I, 7 1
Therefore,
(ubl(Sub )ubb
17 =(Sub/Sub//Suub/Ssnn
1 1.d (I+ (1a7))
=(I
1 t -T10T + 1
I
=I, tel7
1
THEOREM F.2. Let A be set of attributes and lel Q^ be the matrix representation of the marginal on A. Given the matrices A for all A' E closuuee( A)), we have QA
Σ
QA R A R
E/Ellsseel A)
Proof of Theorem F.2.
if AMt E A if Att, & A Sub (Au.) T AtL
[
Q
K, where, for each i, K;
t=1
ifAll E A' ifAtt: & A'
V where, for each i, V, =
1=
It is straightforward to verify that the following is right inverse (and hence pseudo-inverse) of RA
Tla
where, for each i, V Sub t AtM
ifAtt, A' ifAtt; & A'
R
A'
[AU. 1
Sub Au. Sub Arc.
ifAtt, E A' ifAtt, E A/A' ifAll, A
na
Q | RA =
K.V/V, where, for each i, K.V.V.
A |Atta 1 Att.) 1 |
Because Sub Atc. has linearly independent rows, the pseudo-inverse of it can be expressed as,
Sub At, Sub ( (SubjAn, SubjAu,,))
From lemma E.I we get,
Subt Att;
Sub Subjan, (Sbbla, S
I[jAc] [Att, 1 |Acc, 1 T.ss..
Therefore,
I [Atrll [Ate, 1 | [Aucl
ifAtt, E A' ifAtt, E A/A'
Tha
Q
R RR RA
T;
where, for each i, T,
1 [atee) 1 A/Arec)
TAn,
i=1
[/A
ifAtt, $ A
35

---

Without loss of generality (and to simplify notation), assume A consists of the first l attributes.
QA
IIAuaI
ji=+11
na T;
Σ
QA RA
A' (closure(A)
A (A)
iiml
[acc.)) )
A Ecloouure
1=1
i=(+1
Σ
X
2
A'Eloouree A)
vi=++1
I Atttll
[Are,] 1 LAn,
ifAtt: E A' ifAtt, A/A'
where, for each i S e, T,
AttE.
| Lateal
Because of the distributive property of the Kronecker product,
((IAAt)))
1 |,ce, M(aees) + |Att,l
Aeee, 1
A
|Att,
Σ
X Tr
A A'elosureeAA A)
Therefore, combining everything together,
Σ A' (A)
Q QAR =
X i=1
T.
Facca
A (closurre
i=t+1
X
IpAmal
x
1 Aute
i=1
ii=+1
QA
THEOREM 4.7. Given marginal workload Wklood and positive numbers 03 for each A closure(W) W kload), let M be the mechanism that oulputs (MA(x;03 A E closure( (WouureWaar ( and let (W^ WAA Ma(x, Then for any marginal on an altribule set A E closure(W kloud), Algo- rithm returns the unique linear unbiased estimate of QAX (i.e., answers to the marginal query) from that can be computed from the noisy differentially private answers.
A E closure(W kload)} (lloodd( denote the privacy-preserving noisy answers (e.g..
The variances Var(A;M) of all the noisy cell counts of the marginal A is the vector whose components are all equal ENSA (0x EN (AA
|AR.]-1 I(AAAE(A/A")) [AM,, TAt.
1
The covariance between any two noisy answers of the marginal on A is ENSA (0'x I' TAB.T IILUAEE(A/A) 1
Proof of Theorem 4.7. We first verify the correctness and uniqueness of the reconstruction in Algorithm Uniqueness follows from the fact that the rows from all the matrices RA (for A E closure(W kload)) are linearly independent.
36

---

Consider Line from Algorithm 2. It uses U matrix that depends on both the attributes A of the marginal one wants compute and a subset A' of So, for notational dependence, write it as UA-A'. It is straightforward to verify that A = QA Q. From Theorem F.2, QAX CA'CA Q RA AA'CA U and Algorithm 2 is correct because each wi is an unbiased noisy version of R
Having established that the q returned by Line 5 in Algorithm is an unbiased estimate of the marginal query answer QA X, the next step is to compute the covariance matrix Elqq").
Elqa" =
Σ
UA-A (WAWA) U
A'CA
Σ NCA
(O-A'(22 UA
U U
Without loss generality (and to simplify notation), assume A {Atti..... Atte) consists of the first l attributes, A' .Attt consists of the first S E attributes, then A/A' {Atte+1..... Atte).
By definition, Var(A;: is the diagonal of Elqq") EA' Eclosure(A) EA A+A" Thus we can write:
Qa
I|Atc.1
&
ILAus,
@
X
TAccal
i=1
j=++1
k=o+1
RA
Sub
Am Amm
1
1
[eteal
i=1
j=H+1
N-P-1
1
nh
R A'
=
X
Sub
AAn
LAtt
lAtesl
Atta
1 |
j=1+1
k=t+1
UA-A Q QAR =
Sub
Aetell
2
Att,
Att,l
x
[1]
j=t+1
A A=L+1
n. x
UT A-A
Sub IT"
1
[1]
Att,
AAtE
jmttl
v=t+1
ΣN
Sub Att. SubfAu. (Au
[1]
[1]
j=t+1
W-P-1
UA-A-EA A
Sub Mn, Sub Sub T Met,, Sub Sub/T tr
Artt))
na
jmt+1 Att, 12 1 1 [1 [1]
[1]
(10)
Now, by Lemma F.I,
Sub Att.
Sub Atc.
Sub (ubl (ub Arr.]] = Ijan
Sub tT
1 |ete 17
(11)
[Au
So the diagonals of U JA-A EA. UT A-A A' be computed by multiplying |Art]|-1 for each All;
[
A' and Att, for each Att, E A A'. Meanwhile, the off diagonals are all the same and can be computed by multiplying -1 for each Att, E A' and 1 for each Att, A A'. Att,
[AM.
37

---

Computing the variance and covariance of the marginal query answer is therefore the summation of these quantities for all A' A and is what the theorem states.
G Computational Complexity Proofs
THEOREM 4.8. Let na be the total number of attributes. Let #cells(A) denote the number of cells in the marginal attribute set A. Then:
1. Expressing the privacy cost of the optimal mechanism M as a linear combination of the 1/02 values takes O Ae #cells(A) total time.
2. Expressing all of the V Var(A; for for A E W Wkload, linear combinations of the o values can be done in O(E #ccels(A)) total time.
Computing all the noisy outputs of the optimal mechanism (i.e., (x for A closure(Wkloadd kload)) takes (na LAEwkoood IIA EAu,EAA(AAt (lAtt,) + +1) total time after the true an-
swers have been precomputed (Line I in Algorithm 1). Note that the total number of cells on marginals W kload O (Exewklond IAAtee [Att,)).
Reconstructing marginals for all A Wkload takes O(E |A #Alccels(A)) (A)) total time. Computing the variance of the cells for all of the marginals for A W kload can be done in AEW kload #cells( (A)) total time.
Proof of Theorem 4.8. First we establish that Closure(Wklooade S EAEWklond #cells(A). Given an set A E Wkload, we note that it has 2|A| subsets, so that |closure(A) (A)l = 2|A|, However, #cells(A) A) is at least 2|A| (because each attribute has at least attribute values). We also note that closure W kload)
U closure(A) (A). Hence
AkWkload
ccoouureW BotnreeWlloood klood)
Σ
|closure(A))
=
Σ
#cells(A) (A)
AeWkload
AEWiload
To analyze the time complexity of symbolically representing the privacy cost, as linear combi- nation of the 1/0 values (for all A E closure( (W' kload)) we note that the coefficient of 1/0 [AMAl-1 Thus computing the coefficient 1/oğ takes O(1) time. Then, computing the [AM.
is II A
coefficient of L/o[AU can be computed from the coefficient of 1/03 in O(1) additional time. Thus, we if go level by level, first computing the coefficients of 1/0 with |A| = then for |A] = 2, etc. then computing the coefficient for each new A takes incremental ((1) time. Thus the overall time is O ([closuueeM ( kload))) and therefore is O OooeWWood (Ccell((A)).
Let Neells EAEWkload kload #cells(A) To express the variance symbolically as linear function of for [ttt
the o² values via Theorem 4.7, we note from the previous part that computing II AULEAA
|
all A' closure closure(Wkloadd (Wkload) can done in total (Reatls) time. Similarly, computing
II AM;EA
for all A' E closure(Wkloadd kload) also take total ((ncctts) time. Once this is pre-computed, then for any A' c A closure(W (oloodd) the product IIAHE
|AHt]-1 "Aur, IAAA) TA
be computed in O(1) time since A \ A' E (Wkuoad) Now, Var(A; ILA TA This is a linear combination of Al terms
Σ IlAM,EA A'CA
[Attl-1 A
(one term for each variable x for A' C A). Each term is computed in O(1) time after the pre- computation phase. Thus the symbolic representation of (ar((AAA) A") takes ((2)Al) time (which is at most the number of cells in the marginal on A) time after precomputation. Thus computing Var(A A; M²) for all A Wklood can be done in total (fnatlss time after precomputation, but precomputation also takes (Rncllt) time. Thus the overall total time is (
38

---

We next analyze the time it takes to generate noisy answers once the true answers have been precomputed (Line in Algorithm 1). This involves (1) computing the product Hv in the algorithm. (2) generating one Gaussian random variable for each column of H and (3) computingHz, Now, the first and third steps take the same amount of time. The second step generates one Gaussian for each row of H and hence, for each MA A takes time IT Am. () - 1).
For the first step, the fast pronccker-product multiplication algorithm (Algorithm 1 of [38]) has the following complexity. Given a kronecker product of l matrices of sizes (m - x 1....... (m--1)x me and vector with my
me components, their algorithm has & iterations. In iteration i, the gt matrix (with size m,-1 X m2) ) is multiplied by a matrix with shape (m, [[ my * ( - 1)). In our case, each m, is subtraction matrix with two nonzero elements each row. Thus, in each iteration, the product makes 2 [[]==1 my [m - 1) scalar multiplication operations. There are é iterations, so the multiplication algorithm uses O I m²) multiplications.
Now, to run algorithm MA. the number of kron products é |A| and each m, is |Att, for Att, E A. Hence the running time of MA is O IAtte |AAt,,)) which is most A times the number of cells in the marginal on A. Note that the constant the big-Q notation is bounded across all A. Next, when adding up the complexity across all A' E closure(A) A)), we can replace |A| with |A]. and then the summation looks like the product
(I + 1) when this product expanded. Hence AlL,AA
II
the time all QA for all A' closure(A) is O(IA) II (lAtt:) 1)). Adding up over all AH,
A E W kload gets the results.
Next we consider the reconstruction phase. Using the same analysis of the fast kron-product vector multiplication, we see that in each iteration of Algorithm 2, there is a kron product vector multiplication. Using similar reasoning for the previous item, each such multiplication takes O O(AA|IAAt, [AAt,] = O(IA) #cells A)) time. The number of iterations in the algorithm is 2| < #cells(A). Thus the overall runtime is O O(EAeWktoad |A| (cells(A))))
Finally, the variance computation no harder than expressing the Var(A; as linear combina- tions of the optimization variables and we have shown this to be (
H Closed Form Solution to the Weighted Sum of Variances Loss
By Theorem 4.5, the privacy cost is linear combination of the 1/0 values. By Theorem 4.7, each reconstructed marginal's 's cell variances are linear combination of the o values. Thus, minimizing the weighted sum of reconstructed marginal variances subject to the privacy cost being S can be formulated as problem of the following type:
A Aclossue W kloud)
arg min
Σ
UAO
A
(12)
Eclosure W kloud)
Σ
PA
s.t.
S c
A AEclosureWW kloud)
where the VA are the linear coefficients of the o and the PA are the linear coefficients of the 1/02 in the privacy cost. The closed form solution is given by htc following lemma.
LEMMA H.1. Given the optimization problem in Equation 12 The optimal objective function value is T= = (= ) /ee, the optimal value of each noise scale parameter is o /TPA/(CON)
Proof. Clearly, for the optimal solution, the inequality constraint must be tight (i.e., = c) because if it is not tight, we can lower variance while increasing privacy cost by dividing each x by a number 1. Thus just need to solve the problem subject to ΣA PA/O2
39

---

From Fauchy-Schward inequality,
ΣPAO - Evaoz
Σ PA
Σ VUAPA /c=-
/e2
Equality holds when PA O = t for all A (for some constant t). Since
Σx o
Σa VAPA/t, then must have t T/c. Plugging this into the definition of get A = (TPA)(CUA).
Thus, if the loss function is the weighted of variances, ResidualPlanner does not need any optimization steps. The selection of the noise scales and the reconstruction phase are direct algorithms.
I Additional Experiments
In this section, we present additional experiments. Following [37], the experiments use the following type of workloads:
All w-way marginals.
All I 3-way marginals. This includes all O-way marginal (the total sum), all 1-way marginals, all 2-way marginals, and all 3-way marginals.
Small marginals. This includes any k-way marginal that has at most 5000 cells.
We also use these metrics:
The total variance is the sum of the variances of the reconstructed cells in each marginal in the workload. Root Mean Squared Error is obtained by taking the total variance, dividing by the total number of cells in the workload marginals, then taking the square root. The SVD Bound (SVDB for short) [31] provides a theoretical lower bound on RMSE for any matrix mechanism. For marginals, the SVDB is tight, but its computation is not scalable.
RMSE:
Max Var: compute the variance of each reconstructed cell for each marginal in the workload, then take the maximum these.
Running time (in seconds) of the different stages of the algorithms (select and reconstruct).
Unless otherwise stated, ResidualPlanner uses the open-source ECOS optimizer [14] for solving the optimization problem it generates for the select step.
For all experiments, we require all mechanisms to have privacy cost peost = 1. By definition 2.3, M satisfies p-zCDP with p 1/2 [46] and satisfies y-Gaussian DP with μ 1 [15, 46].
Each experiment repeated 5 times, we report the mean value of these results and a confidence interval consisting of +2 standard deviations. This is most useful for running time, the variance loss metrics have negligible variance across all algorithms.
L1 Scalability
In this section, study the scalability of ResidualPlanner. This is done using the Synth-n" dataset, where d is the number of attributes and n the domain size of each attribute. We use all < 3- way marginals as a fixed workload and vary n d to get the computation time for HDMM and ResidualPlanner.
L1.1 Varying Attribute Domain Size n in the Selection Step.
This experiment considers what happens when the attribute domain size n get larger. We fix the and vary the domain size n for each attribute, where n ranges from 2 to
number of attributes 1024. We evaluate the running time and accuracy of the selection step
Table 9 shows the running time for the selection step HDMM and ResidualPlanner. The RMSE on the workload that the selection step guarantees is also measured. Both HDMM and ResidualPlanme
40

---

have no trouble here. HDMM is nearly optimal in RMSE and ResidualPlanner is optimal, as shown by agreement with the SVD Bound. ResidualPlanner is faster, but both methods are fast in this experiment setting.
Table 9: Selection step on Synth dataset where d = and n varies, The workload is all I 3-way marginals. Metries running time and RMSE.
TMMeHDMM
Time Res Plan
RM RMSEHDMA
RMS E Res Plan
SVDB
0.069 = 0.018
0.001 = 0.000
1.903
1.890
1.890
0.064 + 0.006
0.001 0.000
2.685
2.681
2.681
0.070 + 0.021
0.001 + 0.000
3.156
3.156
3.156
0.076 + 0.020
0.001 0.000
3.367
3.366
3.366
32
0.105 + 0.020
0.001 + 0.000
3.422
3.423
3,423
0.114 = 0.033
0.001 + 0.000
3,408
3.407
3.407
128
0.137 + 0.048
0.001 0.000
3.371
3.367
3.367
256
0.187 + 0.050
0.001 + 0.000
3.331
3.322
3.322
512
0.183 = 0.020
0.001 + 0.000
3,294
3,283
3,283
1024
0.353 = 0.058
0.001 + 0.000
3.328
3,251
3,251
Table 10 shows the running time and Max Variance comparison for the selection step. HDMM can only optimize for RMSE, not max variance, so this table shows that RMSE not a good substitute when needs to optimize for Max Variance.
Table 10: Selection step on Synth-n" dataset where d = 5 and n varies. The workload is all S 3-way marginals. Metrics are running time and Max Variance.
DMM
TimeResPle
MaxVarrDDMe
MoxV ar ResPlan
0.069 = 0.018
0.008 + 0.001
8.091
4.148
0.064 = 0.006
0.008 = 0.001
44.693
9.760
0.070 = 0.021
0.008 = 0.001
180.343
15,643
16
0.076 = 0.020
0.008 = 0.001
588.115
20.067
32
0.105 + 0.020
0.008 + 0.001
1649.341
22.811
64
0.114 + 0.033
0.008 + 0.001
5560.807
24.345
128
0.137 + 0.048
0.008 + 0.001
12229.488 488
25.157
256
0.187 = 0.050
0.008 + 0.001
8168.716
25.574
512
0.183 - 0.020
0.008 + 0.001
32159.958
25.786
1024
0.353 + 0.058
0.008 + 0.001
277825.955
25.893
L1.2
Impact of varying the number of attributes in the Selection Step.
Next, fix the domain size of each attribute be 10 and vary the number of attributes d, where ranges from 2 to 200. This experiment can test some of the limits of ResidualPlanner. While HDMM cannot perform selection when the number of attributes is 20 larger, ResidualPlanner has no trouble optimizing RMSE even for 200 attributes. However, optimizing for Max Variance much more difficult. ResidualPlanne than hour for = 200 and we killed the process.
do this for 100 but the underlying optimization took more
Table 11 shows the running time and RMSE comparison for the selection step. The running time of HDMM increases sharply and quickly runs out of memory. the same point, the SVD Bound can no longer be computed. Meanwhile, ResidualPlanner continues to run efficiently.
Table 12 shows the running time and Max Variance comparison on the Selection step. Optimizing for Max Variance is much harder for ResidualPlanner compared to RMSE and we killed the process for d 200. Mcanwhile. HDMM is not able to run RMSE even if one cares about Max Variance). There is an interesting phenomenon with HDMM that takes place for d between 8 and In this case, HDMM always produces max variance of 1000. This maximum is always achieved for the sum query (a rero-dimensional marginal) for the following reason. For beween and 15, HDMM decides to add noise to all 3-way marginals and nothing else (even though the workload is all < 3 marginals). The privacy loss budget is split equally among them. Thus, each of the (2) marginals it measures gets N (0, (d) noise. The query gets reconstructed
20 (we emphasize again, optimizes for
41

---

Table 11: Selection step on Synth- n dataset where n 10 and d varies. The workload is all < 3- 3-way marginals. Metrics are running time and RMSE.
d
DMM 0.013 + 0.003
T'meResPlar 0.001 + 0.0008
RM R.SMMDDM
RMSE ResPlan
SVDB
2
1.379
1.379
1.379
4
0.028 + 0.007
0.002 + 0.001
2.346
2.345
2.345
6
0.065 + 0.012
0.002 + 0.0008
4.278
4.275
4.275
8
0.167 + 0.019
0.004 = 0.001
6,726
6.638
6.638
10
0.639 + 0.059
0.009 + 0.001
9.629
9.348
9.348
12
4.702 = 0.315
0.015 = 0.001
12.904
12.359
12.359
14
46.054 + 12.735
0.025 = 0.002
16,506
15.642
15.642
15
201.485 = 13.697
18,421
17.378
17.378
20
Out of memory
0.079:0.000 0.011
Out of memory
26.916
Out of memory
30
Out of memory
0.211
Out of memory
49.713
Out of memory
50
Out of memory
1.207 0.047
Out of memory
107.258
Out of memory
100
Out of memory
9.913 = 0.246
Out of memory
303.216
Out of memory
200
Out of memory
80.120 = 1.502
Out of memory
855,330
Out of memory
as follows. For any single noisy 3-way marginal, one can estimate the sum by adding up the cells in the marginal. Since each cell has variance (3) and there are n 1, 000 cells, the sum estimate from single way marginal has variance of 100) But one can obtain an independent estimate to the sum query from each of the (5) noisy 3-way marginals. By averaging these noisy estimates, one can obtain an estimate of the sum query with variance 1, 000.
Table 12:
Selection step on Synth-n" dataset where = 10 and d varies. The workload is all < 3- 3-way marginals. Metrics are running time and Max Variance.
TMM 0.013 + 0.003
TimeRes ReaPlan 0.007 + 0.001
MaxV HDM
Max V ar ResPlon
13.745
3.306
0.028 0.007
0.010 + 0.005
132.620
10.480
0.065 0.012
0.009 + 0.001
461.132
26.904
0.167 0.019
0.015 + 0.003
1000.000
56.961
10
0.639 + 0.059
0.018 + 0.001
1000.000
105.031
4.702 0.315
0.028 0.001
1000.000
175.496
14
46.054
12.735
0.041 = 0.001
1000,000
272.738
15
201.485 13.697
0.050 + 0.001
1000.000
332.769
20
Out of memory
0.123 + 0.023
Out of memory
768.941
30
Out of memory
0.461 + 0.024
Out of memory
2540.440
50
Out of memory
4.011 + 0.112
Out of memory
11597.037
100
Out of memory
121.224 + 3.008
Out of memory
91960.917
L1.3
Scalability the Reconstruction Step.
We conduct similar experiments, but now we measure the time in the reconstruction step. To com- plement the reconstruction scalability experiments from the main paper on the Synth-n' synthetic dataset, we first fix the number of attributes d' and vary the domain size n for each attribute, where n ranges from 2 to 512. The reconstruction time for ResidualPlanner does not depend on the metric that the select step was optimized for. Again we compare with HDMM [38] and a version of HDMM with improved reconstruction scalability called HDMM+PGM [38, 41] (the PGM settings used 50 iterations of its Local- Inference estimator, as the default 1000 was too slow). Table 13 shows the results. Again, at some point HDMM runs out of memory while ResidualPlanner runs efficiently. HDMM runs of out memory because choices it had made in the selection step. When n = 128 decided to measure 5-way marginal, which is so large (requiring 128 space) that it caused HDMM and HDMM+PGM to have memory issues.
We next fix 3 and vary d. Table 14 shows ResidualPlanner is clearly faster. Furthermore, HDMM and HDMM +GM are hampered by the failure the selection step (when selection fails, there nothing to reconstruct). It is interesting to compare HDMM+PGM behavior when 3 in Table
42

---

Table 13: Running time (in seconds) of the reconstruction step on Synth - dataset where and n. varies. The workload is all I 3-way marginals.
HDMM
HDMM + PGM
ResPlan
2
0.005 = 0.002
2.466 0.278
0.008 0.002
4
0.005 = 0.000
1.894 + 0.146
0.011 + 0.008
0.008 = 0.000
# 1.936 + 0.131
0.011 0.008
16
0.064 = 0.036
0.016 0.001
32
1.924 = 0.060
3.211 + 0.220
0.045 0.007
64
56.736 = 1.460
12.574 = 0.512
0.217 = 0.021
128
Out of memory
Out of memory
1.244 0.059
256
Out of memory
Out of memory
12.090 + 0.504
512
Out of memory
Out of memory
166.045 + 13.803
14 with n. 10 in Table 2 from the main paper. Clearly HDMM+PGM is faster for 10 than 7 = 3. This counterintuitive result can be explained by the complex workings of HDMM as follows. When 3, the selection step in HDMM returns some 4-way marginals. But when 10, HDMM only returns S. 3-way marginals. The 4-way marginals make the reconstruction step harder for both HDMM and HDMM + PGM.
Table 14: Time for Reconstruction Step in seconds on Synth- nd dataset. and the number of attributes d varies. The workload consists of all marginals on < 3 attributes each. Times are reported with +2 standard deviations. Reconstruction can only be performed the select step completed.
HDMM
HDMM PGM
ResidualPlanner
0.001 + 0.0001
0.256 + 0.030
0.005 + 0.002
0.009 0.001
3.293 0.253
0.020 0.004
10
0.334 = 0.010
51.568 = 3.391
0.086 + 0.004
3.882 = 0.101
180.708= 5,437
0.153 + 0.002
14
55.856 + 0.361
314.252 + 3.991
0.280 = 0.072
231.283 + 0.554
713.526 + 4.957
0.307 = 0.005
20
Unavailable (select step failed)
Unavailable (select step failed)
0.758 = 0.023
30
Unavailable (select step failed)
Unavailable (select step failed)
2.700 = 0.200
50
Unavailable (select step failed)
Unavailable (select step failed)
12.480 + 0.208
100
Unavailable (select step failed)
Unavailable (select step failed)
99.787 2.113
1.2
Comparison Real Datasets.
In this section, we compare RMSE and Max Variance on the real datasets: CPS, Adult, and Loans. The different workloads 1-way, 2-way, 3-way, 4-way, 5-way marginals, all S 3-way marginals, and Small Marginals.
L2.1 RMSE Comparisons
We provide expanded comparison of RMSE the real datasets from the main paper. Here add more workloads. Table 15, 16 and 17 show the comparison of RMSE on the CPS, Adult, and Loans datasets respectively.
We notice that ResidualPlanner matches the theoretical SVD Bound while HDMM is slightly worse, but still accurate. We conclude that when optimizing RMSE, the main advantage of ResidualPlanner superior scalability.
Since ResidualPlanner is optimal, the purpose of the accuracy comparisons is a sanity check. For RMSE, we compare the quality of ResidualPlanner the theoretically optimal lower bound known the SVD bound [31] (they match, as shown in Table 18).
43

---

Table 15: Comparison of RMSE on CPS(5D) dataset.
Workload
HDMM
ResPlan
SVDB
1-way Marginals
1.756
1.744
1.744
2-way Marginals
2.103
2.035
2.035
3-way Marginals
2.089
2.048
2.048
4-way Marginals
1.648
1.627
1.627
5-way Marginals
1.000
1.000
1.000
3-way Marginals
2.301
2.276
2.276
Small Marginals 2.525
2.525
2.525
Table 16: Comparison of RMSE on Adult(14D) dataset.
Workload
HDMM
ResPlan
SVDB
1-way Marginals
3.081
3,047
3.047
2-way Marginals
6,504
6.359
6.359
3-way Marginals
11.529
10.515
10.515
4-way Marginals
16.618
14.656
14,656
5-way Marginals
20.240
17.844
17.844
< 3-way Marginals
11.555
10.665
10.665
Small Marginals
10.006
9.945
9.945
1.2.2
Max Variance
The next comparison is on optimization for Max Variance. We repeat that HDMM only optimizes for RMSE and this shows that optimizing for RMSE is highly suboptimal when one cares about max variance.
In contrast to RMSE, where the optimization problem generated by ResidualPlanner's selection step can be solved in closed form, for Max Variance, the optimization needs convex solver. Hence in- clude comparisons between the open source ECOS [14] optimizer to the commercial Gurobi optimizer and ResidualPlannerr-Gurhhh
[21]. Thus, results have columns labeled Residuai
Tables 19, 20 and 21 show the results for the CPS, Adult, and Loans datasets, respectively. There one item note about numerical stability. Although Gurobi is generally faster and more numerically stable, the differences
not matter much. Situations where EOCS was worse are highlighted in red. For example, in Table 19 for the CPS dataset, the dataset has only 5 attributes, basically the entire dataset. The optimal mechanism for 5-way marginals simply adds N(0, 1) noise to each cell and optimizing for RMSE is equal to optimizing Max Variance for this special case. As we see, the Max Variance for Residuuallannee+EECO, is 1.008 which is 0.8% worse than optimal. The reason for this is the numerical precision with which ECOS solve the optimization problem that ResidualPlanner gives it. In general, however, it looks like open source optimizers should work fairly reliably for them to be used in real applications of ResidualPlanner.
5-way marginal is
44

---

Table 17: Comparison RMSE on Loans( dataset.
Workload
HDMM
ResPlan
SVDB
1-way Marginals
2.903
2.875
2.875
2-way Marginals
5.747
5.634
5.634
3-way Marginals
9.478
8.702
8.702
4-way Marginals
12.537
11.267
11.267
5-way Marginals
14.872
12.678
12.678
I 3-way Marginals
9.406
8.876
8.876
Small Marginals
8.262
8,206
8.206
Table 18: RMSE Comparisons the theoretical lower bound SVD Bound [31]
Adult Dataset
CPS Dataset
Loans Dataset
Workload
ResPlan
SVDB
ResPlan
SVDB
ResPlan
SVDB
1-way Marginals
3,047
3.047
1.744
1.744
2.875
2.875
2-way Marginals
6,359
6.359
2.035
2.035
5.634
5.634
3-way Marginals
10.515
10.515
2.048
2.048
8.702
8.702
3-way Marginals
10.665
10.665
2.276
2.276
8.876
8.876
Table 19: Comparison of Max Variance CPS(SD) dataset.
Workload
HDMM
ResPlan + ECOS
ResPlan + Gurobi
I-way Marginals
13.672
4.346
4.346
2-way Marginals
47.741
7.897
7,897
3-way Marginals
71.549
7.706
7.706
4-way Marginals
15.538
4.142
4.141
5-way Marginals
1.000
1.008
1.000
3-way Marginals
415.073
13.216
13.216
Small Marginals
223.579
11.774
11.774
Table 20: Comparison of Max Variance on Adult(14D) dataset.
Workload
HDMM
ResPlan ECOS
ResPlan + Gurobi
1-way Marginals
41.772
12.047
12.047
2-way Marginals
599,843
67.802
67,802
3-way Marginals
5675.238
236.843
236.843
4 4ay Marginals
26959.322
575.213
575.213
5-way Marginals
79817.002
1030.948
1030.948
3-way Marginals
6677.253
253.605
253.605
Small Marginals
2586.980
126.902
126.902
Table 21: Comparison Max Variance on Loans(12D dataset.
Workload
HDMM
ResPlan ECOS
ResPlan Gurobi
1-way Marginals
33.256
10.640
10,640
2-way Marginals
437.478
52.217
52.217
3-way Marginals
3095.997
156.638
156.638
4-way Marginals
13776.417
320.778
320.778
5-way Marginals
26056.289
474.244
474.243
3-way Marginals
4317.709
180.817
180.817
Small Marginals
2330.883
89.873
89.873
45


Reviews:
[{"review_id": "6uqaia6Xyu", "reviewer": "Reviewer_2C53", "summary": "This work presents a scalable and optimal, under some conditions, matrix mechanism, which can compute private marginals.  Releasing private marginals is one of the most fundamental problems in private data analytics, and as mentioned in the paper, an important primitive in synthetic data generation.  This work seems to improve on the existing work in every dimension, from scalability, generalizability, and accuracy.  \n", "questions": "Is there some connection between optimality for linear Gaussian mechanisms and optimality for Gaussian DP that would strengthen Theorem 4.4?\n\nDoes solving (2) provide some ex-post privacy guarantee, as in Ligett et al. ’17?\n\nIn the computational complexity section, it claims that the time complexity does not depend on the universe size, but how can that be if we are looking at all the k-way marginals with k<= 3?  If we keep the marginals the same but then increase the universe size in each dimension, I would expect the time complexity to increase.\n\nIs the time in Tables 1 and 2 in minutes or seconds?", "limitations": "The paper points out some limitations.  Another limitation is that this assumes that each user can contribute at most one record (at least for user-level privacy).  How would bias introduced by clipping the number of records per user impact overall utility in this approach since this work is wanting to return unbiased results.  ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper does a great job of presenting the related work and the underlying problem they want to solve.  The results are pretty amazing when compared to HDMM.  ResidualPlanner is more scalable, more accurate, and works for more general loss functions.   The paper has a nice outline that follows the general framework of the matrix mechanism, starting with the select step, followed by measure and reconstruct steps.  One takeaway from the table of results that was not mentioned is that ResidualPlanner also tends to have less variability in its run time\n", "weaknesses": "The paper is very notation heavy and the provided rationale behind the base mechanisms is lacking. I would have liked to have seen more discussion about why the general linear Gaussian Mechanism is necessary and why not just use an identity covariance and matrix B.  Furthermore, I would have liked to have seen more discussion on why we need more general loss functions and what applications they would be needed, in particular are other loss functions important for synthetic data?  I don’t think Table 3 is necessary in the paper, so that could be removed and more discussion could be added regarding the points above.  I like how there is some result on optimality, but I find it to be a little weak, in that it restricts optimality to linear Gaussian mechanisms.  Although this is a very general class of mechanisms, I would have liked to have seen some optimality guarantee for all DP or Gaussian DP mechanisms.  I am curious about the two problems that were presented in equations (1) and (2) where (1) follows the general approach of differential privacy (maximize utility subject to privacy), while (2) seems to follow something closer to “ex-post” privacy from Ligett, Neel, Roth, Waggoner, Wu ’17, where we want to return the best privacy subject to some accuracy constraint.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n**Why the general linear Gaussian Mechanism is necessary and why not just use an identity covariance and matrix B?**\n\nGreat question. In theory, it is the same, but as a practical matter, if the covariance is the identity, then B will have irrational entries (a general formula for B even seems tricky). Using the approach we took, all matrices are integer-valued or rational, meaning that a secure implementation (avoiding floating point and rounding issues) is simplified. After the submission deadline, we used these properties to figure out how to use the Discrete Gaussian noise to replace the continuous Gaussian noise (the difficulty was in extending it to the rational covariance matrices we use). \n\n**Why we need more general loss functions?**\n\nOne example is multiple users, with each user interested in the sum of squared error for the marginals they care about (different users care about different marginals). One could take a max over each user's loss function to create the overall loss function (minimize the worst user's unhappiness). For another perspective, economists criticize the DP community for using error metrics that are too simple. By expanding the list of supported loss functions, the ball is back in their court to quantify the utility they seek from differentially private data.\n\n\n**Is there some connection between optimality for linear Gaussian mechanisms and optimality for Gaussian DP that would strengthen Theorem 4.4?**\n\nIn general, Gaussian DP allows data dependent algorithms while matrix mechanisms provide data independent guarantees, so the requested connection for each regular loss function is probably not possible. We feel that linear Gaussian mechanisms have some extremely important practical properties -- even after the reconstruct phase, the noise distribution of each marginal is known exactly (Gaussian with known covariance matrix).  This allows  statisticians to perform valid statistical inference on the resulting data products and is one of the most important criteria for them. \n\n**Does solving (2) provide some ex-post privacy guarantee, as in Ligett et al. ’17?**\n\nSince the accuracy guarantees are data independent (as with all matrix mechanisms), it is not an ex-post guarantee, but rather another *a priori* way of exploring the privacy/utility tradeoff. For example, if you want to add Gaussian noise to a sensitivity 1 query and guarantee variance $\\leq \\sigma^2$, then the best privacy you can get is $\\mu$-Gaussian DP with $\\mu=1/\\sigma$ (i.e., if you set this as your privacy budget, then you will meet the accuracy constraint).\n\n**In the computational complexity section, it claims that the time complexity does not depend on the universe size**\n\nSorry, it was not phrased well. We will rephrase it as: \"Although the universe size grows exponentially with the number of attributes, the complexity of ResidualPlanner depends directly on quantities that typically grow polynomially (e.g., the number of desired marginals and total number of cells in those marginals).\"\n\n\n**Is the time in Tables 1 and 2 in minutes or seconds?**\n\nThe time is measured in seconds. This was easy to miss in the long captions so we will add units after every number.\n\n**Notation heavy**\n\nUnfortunately we find this happens when linear algebra is involved. We also felt the paper was notation heavy though the notation seems necessary. We tried to minimize the cognitive burden by using more descriptive notation where possible (e.g., $Att_i$ and the $Sub$ matrices). For this reason, we also included in the supplementary material  both a table of notation and an example  run-through of ResidualPlanner on a toy problem to help readers along.  We will be happy to incorporate additional suggestions.\n\n**Another limitation is that this assumes that each user can contribute at most one record.**\n\nThis is a good point that we will add.\n"}, {"review_id": "gMQO0xqsiD", "reviewer": "Reviewer_zbBa", "summary": "The paper studies scalability of matrix mechanism when answering marginal queries. The paper looks at a restricted yet large enough class which they call regular loss function, satisfying three key properties. Scalability of the matrix mechanism is often poor as it requires heavy SVD computation to compute the matrix inverses. This has been studied by several researchers since the inception of matrix mechanism in 2010, and often heuristics are proposed that provides some degree of scalability. The subject of this paper is to put it on a more firm ground.", "questions": "Please see above.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "As I discussed above, the matrix mechanism has been often suggested as a mechanism that provides almost optimal accuracy guarantees (in terms of means-squared error). However, one major challenge, that several past work has not adequately addressed and becomes problematic if the problem size grows even in the medium range, is the scalability issue. This is because, without any structure in the queries, finding optimal factorization to be used in the matrix mechanism requires either solving a semidefinite program or solving a generalized regression problem, whose complexity is cubic in the size of the dimension. The scalability issue is to an extent that even considering a 2-marginal on a medium size dataset leads to out-of-memory on really high-powered clusters. \n\nTo address these scalability issues, several recent works have proposed using some heuristics, like removing the consistency constraints. This leads to a suboptimal matrix mechanism. This paper suggests the use of a new mechanism that can optimize over a large class of convex objective functions (the ones that are regular) and return solutions that are optimal under Gaussian noise addition. The matrix mechanism consists of designing two matrices: strategy matrix and reconstruction matrix. The authors propose a new strategy matrix which is in the form of a tensor product of $Sub_d$ matrix. This construction only works in full-rank structure, so they perform a Gaussian elimination to get linear independence.", "weaknesses": "Before stating the weakness section, I would like to make a disclaimer that I have been unable to read the supplementary material, so if there are some questions that I raised here and are present in the supplementary material, please just state the page number and I will have a look.\n\n1. The authors mention that their result is optimal for the Gaussian mechanism. I am unsure what this statement means. Is it the case that any other mechanism will add Gaussian noise with a larger variance than what they suggest? I am a little skeptical of this statement considering that their strategy matrix is a fixed matrix and then their reconstruction matrix just depends on the inverse of the strategy matrix. This is true for a given strategy matrix, but why does this hold for an arbitrary strategy matrix?\n\n2. They design their algorithm under the assumption that the loss function is convex and regular; however, HDMM is more general. Can we simply not add another constraint in HDMM that takes into account the regularity of the loss function and achieve competitive run time? Is there a fundamental reason why that cannot be done? \n\n3. The error of the matrix mechanism is at least the trace norm of the query matrix (the SVD bound). So, to me, it feels like, for the worst case k-marginal, the mean squared error would scale like $\\Omega((d/k)^{2\\sqrt{k}})$. I might be making a mistake in my calculation, but translating it to \\ell_\\infty error, this sounds about right (comparing with the known upper bound result from ICALP 2012 paper making it tight). Is the regularity assumption the one that gets you around this bound?\n\n4. I really would like to see a concrete error bound (at least for some structured marginal queries that satisfy their requirements) to get a feel of their bound. Can the author provide me with one? \n\n\n> I am currently keeping my score to just below acceptance, but I am highly inclined to move it above the threshold and would definitely do that if the authors satisfactorily answer my questions (and other reviewer's questions)\n\nI revised my score to \"Accept\" based on the rebuttal and upon revisiting the paper once again post-rebuttal. I thank the authors for clarifying some of my misunderstandings in the first reading of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**This construction only works in full-rank structure, so they perform a Gaussian elimination to get linear independence.**\n\nThis is a confusion due to our writing.  We propose a residual basis (formed by all possible R matrices as defined in Section 4.2). This basis is linearly independent, but not all basis elements are needed for the marginals that a user requests. We simply drop unnecessary bases (no Gaussian elimination is needed) as explained in lines 209-214. This is possible because the residual basis we propose has a useful property -- any set of marginals is compactly represented by a subset of the basis vectors. When a set of marginals is represented in matrix form, the number of linearly independent rows is equal to the number of residual basis vectors that we need.\n\n**What optimality means? ...**\n\nSorry, we were not clear enough in theorem 4.4. \nAs we are re-reading Theorem 4.4, we can see the confusion. As we will clarify in the paper,\n1) The user picks a privacy budget, a workload of marginals and a regular loss function L (e.g.,  weighted sum of squares or max squared error over the workload). \n2) Based on this, residual planner decides how much noise to add to the different parts of the strategy queries (i.e., it determines the $\\sigma_A$ parameters in the base mechanisms).\n3) Then it reconstructs answers the workload queries. The resulting noisy workload answers are optimal meaning that subject to the privacy constraints, no other matrix mechanism with Gaussian noise can have a lower value of the loss function (e.g., HDMM cannot have a better sum of variances, if that is what the user sets the loss function to be).\n\n**\"their strategy matrix is a fixed matrix\"**\n\nYes, however different strategy query answers get different amounts of noise added. These are the $\\sigma^2_A$ parameters of the base mechanisms. \nThese parameters depend on the workload marginals\nand the objective function. That turns out to be sufficient for optimality (theorem 4.4) because of the residual basis used by the base mechanisms. The residual basis has an important property -- for any subset of the workload marginals, the rows of the query matrices for those marginals span a linear space; the basis for that linear space is always a subset of the residual basis.\n\n**The loss function is convex and regular; however, HDMM is more general. Can we simply not add another constraint in HDMM that takes into account the regularity of the loss function**\n\nPerhaps we are misreading what is being asked. For marginals answered with Gaussian noise, HDMM is not more general. HDMM can only optimize for the weighted total variance of any given workload of marginals. This is a regular loss function, which means that ResidualPlanner can also optimize for the weighted total variance of any given workload of marginals (i.e., ResidualPlanner can solve the same problem). ResidualPlanner will return the optimal solution. HDMM returns approximate solutions (but can run out of memory on medium sized datasets). However, ResidualPlanner can optimize other loss functions, while HDMM only gives you one choice.\n\n**The error of the matrix mechanism is at least the trace norm of the query matrix (the SVD bound). I really would like to see a concrete error bound (at least for some structured marginal queries that satisfy their requirements) to get a feel of their bound. Can the author provide me with one?**\n\nWhen the objective function is total squared error on $k$-way marginals or on weighted data cube queries (as defined in the paper that introduced the SVD bound), the SVD bound is tight and therefore ResidualPlanner matches it. Just in case there is any confusion, ResidualPlanner does not restrict the workload marginals one can use.\n\n**So, to me, it feels like, for the worst case k-marginal, the mean squared error would scale like $\\Omega ((d/k)^{2\\sqrt{k}})$\n. I might be making a mistake in my calculation, but translating it to $\\ell_\\infty$ error, this sounds about right (comparing with the known upper bound result from ICALP 2012 paper making it tight: (https://arxiv.org/pdf/1205.1758.pdf Faster Algorithms for Privately\nReleasing Marginals). Is the regularity assumption the one that gets you around this bound?**\n\nThis refers to \"Faster algorithms for privately releasing marginals\" by Thaler et al. (and Theorem 1.1 in their section 1.1)? Their performance criteria are not comparable for the following reason. Since they look at additive error for proportions (e.g., the DP estimate of the **fraction** of women in the dataset is within $\\alpha$ of the true answer with high probability), then in the language of counts their result is about whether the differentially private **counts** are within $\\alpha n$ of the true counts (where $n$ is the number of people in the dataset). Rescaling $\\alpha$ by $n$ makes it pop up in their other constants/expressions and so their results have a dependence on $n$. Matrix mechanisms (and so also ResidualPlanner) provide data independent errors (no dependence on $n$). Thus there is no translation between the bounds.\n\n\n"}, {"review_id": "YnNw0JDn44", "reviewer": "Reviewer_zYAs", "summary": "INTRODUCTION:\nThis paper presents significant advancements in the matrix mechanism, a technique used for releasing differentially private linear queries or count statistics. Releasing these types of queries, for instance, “count of people living in NYC who are male” (also known as a 2-way marginal query), is a fundamental task in the differential privacy community. The proposed matrix mechanism is considerably more efficient compared to previous approaches.\n\nBASICS OF MATRIX MECHANISM:\n\nIn differential privacy, when given a collection of linear queries, a simple approach is to add independent Gaussian noise to each query response. The scale of this noise is tuned to the sensitivity of the queries, which denotes the amount of change in the output corresponding to alterations in individual data points. Informally, this implies that as the number of queries to be released increases, more noise must be added to each query answer to maintain privacy.\n\nROLE OF MATRIX MECHANISM:\n\nThe matrix mechanism is designed to reduce the amount of added noise for achieving differential privacy, aiming for better query estimates while preserving the same level of privacy. This mechanism operates by refactoring the set of queries and constructing a function with lower sensitivity, yet retaining most information from the original query set. This is effective because queries are often correlated, and this refactoring process capitalizes on such correlations. However, matrix mechanisms traditionally face computational inefficiencies in high-dimensional settings, as they require performance-intensive matrix operations.\n\nEXISTING SOLUTION AND ITS LIMITATION:\n\nThe High-Dimensional Matrix Mechanism (HDMM) is a notable prior attempt to enhance the scalability of the original matrix mechanism. Despite its significant improvements, HDMM has limitations. Specifically, HDMM struggles to approximate 3-way marginal queries on datasets comprising more than 10 attributes (each with a cardinality of 10).\n\nNEW CONTRIBUTION:\n\nThis paper breaks new ground by proposing an efficient and scalable method named 'ResidualPlanner.' This method can estimate marginal queries on datasets with 100 features (each with a cardinality of 10), outperforming the previous HDMM method. The scalability and speed of ResidualPlanner underscore a significant advancement in the application of matrix mechanisms for differential privacy. Moreover, this method handles optimizing over different loss functions. For example, prior work only optimizes over the square error over all queries, whereas this method allows for optimizing over max error. ", "questions": "In line 69, is there a typo in the example Q_{Att_2}?\n- Line 130, Typo: “privcy”.", "limitations": "Yes", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The ResidualPlanner heralds a substantial advancement in the release of linear statistical queries, an important task in the field of differential privacy. Notably, it enhances efficiency by facilitating the release of an exponentially higher number of linear queries across high-dimensional datasets, compared to its predecessor, the HDMM method. This accomplishment bears significant practical implications for the field of differential privacy, given that real-world datasets are often high dimensional.\n\nThe innovation behind ResidualPlanner's improved computational performance lies in a novel technique that produces a compact representation of the query matrix, Q. This approach deviates from the traditional matrix mechanism, which tends to be overparameterized and consequently computationally intensive. By avoiding this overparameterization, ResidualPlanner yields improved computational efficiency.\n", "weaknesses": "Certain sections of this paper have a high degree of technicality, which poses readability challenges. Thus, the paper could greatly benefit from providing more intuitive explanations of their techniques. For instance, the definition and context of the Kronecker product are noticeably absent, which detracts from the clarity of the relevant sections.\n\nAdditionally, the discourse on Algorithm 1 is notably brief. The paper lacks a clear explanation of the method's purpose and its necessity in the overall context. Providing further elaboration on these aspects would greatly improve the paper's readability and comprehension.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Thus, the paper could greatly benefit from providing more intuitive explanations of their techniques. For instance, the definition and context of the Kronecker product are noticeably absent, which detracts from the clarity of the relevant sections.**\n\nSorry for the omission, we will add that. In the supplementary material, we also have a run-through (with commentary) of ResidualPlanner on a toy example to illustrate how it works. The NeurIPS tight page restrictions tend to force papers to be terse in the main part but we took great care in preparing the supplementary material (adding intuition, etc.) knowing that, if accepted, it would be accessible with the main paper.\n\n**Additionally, the discourse on Algorithm 1 is notably brief. The paper lacks a clear explanation of the method's purpose and its necessity in the overall context.**\n\nWe will add more explanation. It is just there for completeness to show that the measurement step can be performed quickly without expanding the kronecker product and shows how the generate the correlated noise quickly (the general scipy routine for sampling multivariate Gaussian noise must invert the covariance matrix and that is slow; we avoid that).\n\n**In line 69, is there a typo in the example $Q_{Att_2}$?**\n\nYes, thanks for finding the typos.\n"}, {"review_id": "ZFRyo42ldz", "reviewer": "Reviewer_rP9C", "summary": "The paper studies a timely problem of improving the scalability of differentially private query releases using a matrix mechanism. The central approach is to carefully design a set of the residual basis for the representation of workload queries, such that the workload queries could be represented as Kronecker products of block matrices with small sizes. This design of basis representation allows subsequent reconstruction steps of the matrix mechanism to be computed in a closed-form, efficient manner. Consequently, this allows a significantly more efficient reconstruction step (from noisy query answers) than prior matrix mechanisms. The efficiency is proved in computation complexity and empirically shown through improved runtime compared to previous matrix mechanisms via extensive experiments. Finally, the authors show that their mechanism easily extends to different objectives (such as a weighted sum of variance and max variance) for query release. They also illustrate the improved empirical error of the proposed mechanism for the max variance objective (which is not optimized by prior matrix mechanisms).\n\n\n**Minor comments:** Some statements need to be clarified. E.g., in theorem 4.5, what does \" is correct\" mean? Does it mean the output is an unbiased estimator?", "questions": "Q1: Theorem 4.7 shows that the variance for the proposed mechanism is larger as the number of attributes for marginal increases. In other words, 3-way marginals have a larger variance than 2-way marginals. Is that correct? If so, how does this compare to the original matrix mechanism (where I suppose the variance for 3-way and 2-way marginals are the same)? Are we sacrificing the accuracy of higher-order marginals for lower-order marginals? Is this unavoidable?\n\nQ2: One of the main contributions of the paper is the investigation of other objectives (besides the sum of variance) for matrix mechanisms in a scalable manner. However, why would optimizing for other objectives be difficult for prior matrix mechanisms? Maybe the authors could clarify more regarding this to help understand the significance of this generalized mechanism for different objectives.\n\nQ3: The optimality statement Theorem 4.4 puzzles me, as it seems only about an optimal number of noisy answers. In that sense, all previous matrix mechanism-based solutions are also optimal. (As they answer the same number of noisy queries as ResidualPlanner in this paper.) In that sense, I wonder whether there is an optimality improvement. Additionally, could the authors comment on the optimality of ResidualPlanner in terms of the optimization objective, e.g., the smallest sum of variance (weighted) or max variance, among all matrix mechanisms?", "limitations": "The paper achieves significant scalability improvement for the matrix mechanisms, and uses an interesting idea of optimizing noise added to different marginals for the overall query release objective. However, it needs to be clarified whether the algorithm inevitably generates more noisy answers to higher-order marginals. The authors also adequately discussed the limitation of marginal queries and possible future works of generalizing the mechanisms for other noise distributions in the limitation section.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Significantly improved efficiency of the matrix mechanism. The idea of designing a careful set of query representation basis is novel. The reason for efficiency improvements (via more convenient pseudo-inverse matrix computation for Kronecker product of known block matrices) is also explained in detail. \n- The proposed mechanism is general and extends to different objectives for private query release (such as max variance). By contrast, prior works mainly focus on the sum of variance objectives. However, the significance of this generalized mechanism needs to be clarified (see question Q2 for more details).", "weaknesses": "- The comparison with prior matrix mechanisms sometimes needs more clarity. The improvement and the necessary cost for improvement need more clarification. -- The proposed mechanism seems to sacrifice the accuracy of higher-order marginals for lower-order marginals. Is this an unavoidable cost for improved efficiency? See question Q1 for more details.\n- The difficulty and significance of extending the matrix mechanism to more general objectives, such as max variance, need to be clarified. See question Q2 for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**The optimality statement Theorem 4.4 puzzles me, as it seems only about an optimal number of noisy answers. In that sense, all previous matrix mechanism-based solutions are also optimal. (As they answer the same number of noisy queries as ResidualPlanner in this paper.) In that sense, I wonder whether there is an optimality improvement. Additionally, could the authors comment on the optimality of ResidualPlanner in terms of the optimization objective, e.g., the smallest sum of variance (weighted) or max variance, among all matrix mechanisms?**\n\nSorry, we were not clear enough in theorem 4.4. \nAs we are re-reading Theorem 4.4, we can see the confusion. As we will clarify in the paper,\n1) The user picks a privacy budget, a workload of marginals and a regular loss function L (e.g.,  weighted sum of squares or max squared error over the workload). \n2) Based on this, residual planner decides how much noise to add to the different parts of the strategy queries (i.e., it determines the $\\sigma_A$ parameters in the base mechanisms).\n3) Then it reconstructs answers the workload queries. The resulting noisy workload answers are optimal meaning that subject to the privacy constraints, no other matrix mechanism with Gaussian noise can have a lower value of the loss function (e.g., HDMM cannot have a better sum of variances, if that is what the user sets the loss function to be).\n\n\nRegarding the number of noisy answers -- this refers to the number of noisy answers produced in the measurement step (not the reconstruction step). HDMM and prior matrix mechanisms were overparametrized -- they used more noisy answers than necessary, that is why they needed to use least squares postprocessing instead of inversion.\n\n\n**in theorem 4.5, what does \" is correct\" mean? Does it mean the output is an unbiased estimator?**\n\nSorry, it was not phrased well. It simply means that the output of the algorithm is the same as if one naively computed $R_A \\vec{x} + $Gaussian noise with the given covariance. In the algorithm, the matrix multiplication and generation of correlated noise are performed more quickly than a naive matrix multiply or a scipy multivariate Gaussian library call (in particular, scipy would try to invert the covariance matrix).\n\n**Theorem 4.7 shows that the variance for the proposed mechanism is larger as the number of attributes for marginal increases. In other words, 3-way marginals have a larger variance than 2-way marginals. Is that correct?**\n\nThank you for considering the implications of our results and this theorem in particular. In short, that is not necessarily the case.\nThe variance in Theorem 4.7 is a summation and the summation has two product terms in it. For the second product (i.e., where the $1/|Att_j|^2$ appears), it generally has more terms, causing the product to decrease. At the same time, more things are being added in the overall summation. These two opposing forces mean that, depending on the objective function and desired workload, in some cases the larger marginals have larger variance and \nin some cases they have smaller variance.\n\n**Why would optimizing for other objectives be difficult for prior matrix mechanisms?**\n\nThat is a very good question. In theory, one could throw a generic semidefinite solver at the problem, but it would be painfully slow, even for toy problems -- the number of variables is large and computing the objective function takes a lot of time. Prior work took a specific objective function (usually weighted sum of variances) and took advantage of its mathematical properties to speed up the algorithm. For example, HDMM figured out how to compute the sum of variances faster with the help of the kronecker product. These tricks from prior work are very specific to the objective functions they study.\n\n"}]

Author rebuttal:
We thank the reviewers for carefully reading the paper and the insightful comments. The questions pointed out where we need additional clarification and explanation. As suggested, these can be added by moving Table 3 to the supplementary material.
Since we have enough space in the comments for each reviewer, we address each review separately.

Meta-review: All reviewers agree that this paper provides a substantial advancement that broadens the applicability of the matrix mechanism with significant practical applications. All of the reviewer questions were addressed during the discussion period. I agree that Table 3 should be moved to the supplementary material so that points from the discussion may be included in the main body of the paper.
Decision: Accept (spotlight)