Optimality of Matrix Mechanism on $\ell_p^p$-metric
Authors: Zongrui Zou
Jingcheng Liu
Jalaj Upadhyay
Venue: ICLR 2025 Poster (2025)
Keywords: differential privacy
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: In this paper, we introduce the $\ell_p^p$-error metric (for $p \geq 2$) when answering linear queries under the constraint of differential privacy. We characterize such an error under $(\epsilon,\delta)$-differential privacy in the natural add/remove model. Before this paper, tight characterization in the hardness of privately answering linear queries was known under $\ell_2^2$-error metric (Edmonds et al. 2020) and $\ell_p^2$-error metric for unbiased mechanisms in the substitution model (Nikolov et al. 2024). As a direct consequence of our results, we give tight bounds on answering prefix sum and parity queries under differential privacy for all constant $p$ in terms of the $\ell_p^p$ error, generalizing the bounds in Hhenzinger et al. for $p=2$.

Published as a conference paper at ICLR 2025
OPTIMALITY OF MATRIX MECHANISM ON ME-METRIC
( P
Zongrui Zou, Jingcheng Liu"
State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory Nanjing University
163 Xianlin Avenue, Nanjing, Jiangsu Province, 210023, China zou . zongrui @ ssmail njju. edu. cn, liulnnuinnni ju. edu. cn
Jalaj Upadhyay!
Management Science & Information Systems Department Rutgers University
100 Rockafeller Road, Piscataway, NJ 08854, USA ja laj uppahhay@rutgerss
ABSTRACT
In this paper, we introduce the fe-error metric (for p 2) when answering linear queries under the constraint of differential privacy. We characterize such an error under (s, diffferretlaa privacy the natural add/remove model. Before this paper, tight characterization in the hardness of privately answering linear queries was known under 23-error metric (Edmonds et al. (2020) and le fe-error metric for unbiased mechanisms in the substitution model (Nikolov & Tang (2024)). As a direct consequence of our results, we give tight bounds on answering prefix sum and parity queries under differential privacy for all constant p in terms of the f error, generalizing the bounds Henzinger et al. (2023) for =
INTRODUCTION
Analysis or learning with sensitive datasets under privacy has garnered increasing attention in recent years. In this paper, study the most fundamental question of answering linear queries on confidential dataset E R" while preserving differential privacy (DP) (Dwork et al.] 2016). Informally speaking, differential privacy captures the property of randomized algorithm that its output distribution is relatively stable when executed on two neighboring datasets, i.e., datasets that can be formed by changing one data point. More formally.
Definition 1.1 Let
R be randomized algorithm, where R is the output domain. For fixed E > 0 and 8 E [0, 1), we say that M preserves (s, (5,8) diffferretl privacy if. for any measurable set C R and any pair of neighboring datasets x, E X, Pr[M(a) E S) & &Pr[M(y) E S) ef + 8. If 8 = 0, we say A preserves pure differential privacy (denoted by E-DP).
Many fundamental analyses can be cast as set of linear queries (Dwork & Roth 2014, Vadhan 2017): given an input E RR, set of m linear queries can be represented as the rows of matrix A E pmxn, The answer the set of queries is simply the matrix-vector product Ar. Here, x, x E R" are neighboring - x' S (known as add/remove model of privacy). When these queries answered using privacy-pre preeeeiigg algorithm, M, the performance of the algorithm is usually measured in terms of its absolute error or mean squared error (eq. 13
H. and 77. have been supported by National Science Foundation China under Grant No. 62472212 and the New Comerstone Science Foundation. JU's research was funded by the Rutgers Decanal Grant no. 302918 and unrestricted gift from Google.

---

Published as a conference paper at ICLR 2025
In this paper, we initiate the study of eg-error metric that seamlessly interpolate between p (squared error) to oo (absolute error):
erre (M, A) max (E [1i))))-Aill))*
(1)
ZER"
The error metric defined above has natural and intuitive interpretation for data analysis. To elaborate on this, consider the most natural mechanism that adds i.d. noise to each answer of a set of linear queries, and let e be the error in answering the i-th query. Then error metric captures the p-th moment of the error, which is a random vector v E IR" By considering all p. one can identify the exact nature of the probability distribution of the error.
One popular mechanism for privately answering linear queries under different error metrics is the matrix mechanism (Li al. 2015), also known the factorization mechanism. In the matrix mechanism, given set of m linear queries represented by a workload matrix A E Rmmxn, we compute factorization LR A (where L E Rm*k R Rx*) and output L(Rr + 2) for any input E IR" with an appropriately scaled Gaussian random vector z E R This mechanism is both unbiased (i.e., [8[2] 0) and oblivious, i.e., the distribution of & stochastically independent of x. In this paper, we show that the optimal matrix mechanism is also optimal among all differentially private mechanisms with respect to the ly metric, up to logarithmic factors:
Theorem 1.2 (Informal statement of Theorem 1.4 and Theorem D.I) Fix E R be a ma- trix representing m linear queries, and let M I exists a factorization of A = LR such that Mmatrix(2) = L(Re + 2) with ~ [R preserves (e, -DD and that err (Mmatrixs A) S errey is the identity matrix.
+ Rmm be any (s,0)-DP algorithm. Then, there
erre (M, polylog(L/6,,))) Here, 1l E R R
To prove this, we characterize the fg-error for answering linear queries under (c, -ddifferennt privacy generalizing Edmonds et al. (2020), and also obtain a characterization of err (M A) that is tight up to log factors, for every query matrix A and p 2 2. For the convenience of use, we start by stating a weaker form of our lower bound. We will see that this is an immediate corollary of our main theorem.
Theorem 1.3 Let A E RuRn be a matrix representing m linear queries. Then for any (e, 8)DP algorithm M, err, (Mr, = 2e.s(m= (tmmmm//////1AA////// Here, || is the Schatten-1 norm of A and 8-) hides the dependency on the privacy parameters.
To demonstrate the power of the above results, obtain tight bounds for privately answering prefix sum and parity queries. These are two important classes of queries: for example, prefix sum used as subroutine in private learning Kairouz et al. 2021) and parity querie> are often used for hardness results Kasiviswanathan et al. 2011).
1. (Prefix sum) In this problem, the data curator outputs Eige 24 of a vector (x) (2, :.)
in a differentially private manner for all t n. This is equivalent to asking linear queries with Aprefix E 10,1n where Aprefix is a lower-triangular matrix with non-zero entry equal one. In Theorem L.5] we show that, for all constant p. the ef-error of prefix sum under (c, -diifferenta privacy is (z,s(n-/p log(n)) and can be achieved by the same mechanism for all p 0(1); for p (1). the gap between the upper and lower bound is of factor vlog(n). This generalizes the result of Dwork et al. (010)) and Henzinger et al. (2023).
2. (Parity Queries). Let 2 {qp(x) = Il 24 P C
[d).
w) be the class of
parity queries over the input domain {-1, 13d. In Theorem 1.6 we show that for any (e, diffeerrreytillllyy private mechanism M that takes as input d and w.
err (M, Qi,,.) Z2,8 m 1/2+1/r
Thorin 1948 ) and it is one of the primary reasons for the initial support for Riesz 1910 1913)* study -norm despite Minkowski's skepti- cism [Minkowski] 1913).
'Interpolation plays a key role in functional analysis (Riesz 1927
Depending which parity queries are made, the workload matrix would consist of a subset of rows of normalized n Hadamard matrix
2

---

Published as a conference paper at ICLR 2025
for m -. Since Oe,5 (m//2+1/p min (og(m))) is the eg error of the trivial Gaussian mechanism, this is optimal whenever min (og(m)) O
Our study is motivated and inspired by recent elegant work by Nikolov & Tang (024)) who proved the instance optimality of the matrix mechanism instantiated using correlated Gaussian noise for unbiased mean estimation. They considered the following error metric)
eT AM == max (E [ILM())- Ar1 12 WER"
(2)
Nikolov & Tang
2024) showed that, with the privacy notion where || - 2'11 S (1) and that (commonly known as the substitution model of privacy), matrix mechanism is
Lieja (2; x
instance-optimal for any unbiased mechanism under the metric defined in eq.
q Our work instead focuses on obliviousness of the matrix mechanism, more natural Eg metric and a different (stronger) privacy notion, i.c., it differs both in the error metric and the results:
2
1. To understand the difference between these two error metrics, consider the error vector V E RT.. The metric used in Nikolov & Tang (2024) amounts to estimating E[[e, +.... emm (2mp))/2)]] instead of a more natural [Elp +.... oh in eq. In other words, it does not explain the behavior of the error even in the case of the naive additive noise mechanisms.
This is one of the primary reasons we believe our error metric is more natural.
2. They focused on instance optimality of unbiased mean estimation. While this is well- studied problem, it does not cover the question of the ey-optimality of general linear queries under the error metric defined by eq. (1 for general mechanisms. We answer this question broadly and prove equivalent results for a more natural error metric.
3. Differential privacy in the add/remove model (i.e., || - x'1l1 < 1) is usually the most natural notion considered in literature of answering linear queries ( (Edmonds et al. (2020) ;
Nikolov et al. (2013): Bhaskara et al. (2012)). ). In contrast, Nikolov & (2024 considered the substitution model for unbiased mean estimation over some convex polytopes. The
sensitivity polytope related to the substitution model can be substantially smaller than that
of the add/remove model (see also Appendix B.3 for more detailed discussion). result, deriving new lower bound for the stronger add/remove model is needed.
From a pure analysis perspective (and as is often the case in mathematics) as well, one prefers a metric respecting the symmetry as shown in our choice of metric, the Eg -n-mo, and Fp moments studied in the streaming literature. While both of the error metrics (eq. (T) and eq. (2)) converge to the same metric as p - oo and when + 2, the mathematical object the sequence captures as function of p is vastly different. That is, our results complement that of Nikolov & Tang (2024).
1.1 OUR CONTRIBUTIONS
Our main result is a lower bound on general (s, -)diffferentially private mechanisms for answering linear queries in high privacy regimes in terms of certain certain factorization norms Nikolov & Tang 2024) defined b
1/p (EiL Ug)
(A) == min LR=A
where trp(U)=
p<o 00
maxseld |Uii
0
is the p-trace. Equipped with this definition, we state our lower bound:
Nikolov and Tang confirmed with us that they did not consider the metric considered in this paper.
"We note that Gaussian distribution is entirely characterized by its first two moments and, at high level.
eq. (2) captures the variance of the E, norm of the zero mean vector representing the additive error.
Let |Bppp = min ||Ba]|e- Then two commonly studied factorization norms in privacy and
functional analysis denoted by (2) and (F(A)
defined as 72(A) minn.R= [|||||a==|||||]|]___-- and
(F()) = minu,RR=t [|] [[]] 2.). Both these norms are special cases 7pp) because when p =
tr (IL = || and when p oc, then to (T.I.)) = max (T.L.) )a | 2
3

---

Published as a conference paper at ICLR 2025
Theorem 1.4 (Lower bound for (e, 6)-DP) Fix any n.m N. E E (0. 0 S 8 I and p [2, oo). For any query matrix A E Rmxx if mechanism M R + T preserves (s, 6)- differential privacy, then there exists a universal constant C',
(1 (1- (A)))
where 2c (c ? 1) 8.
er (M, 2
Ce
e -
Theorem 1.4 generalizes the result Edmonds et al. (2020) for p = 2 to all p 2 2. Our result can also be contrasted with the lower bound which uses discrepancy methods. It is known that the -eror of an (e, -ifffferrent private algorithm for linear queries is lower bounded by the hereditary discrepancy of the corresponding matrix A Rm** (Muthukrishnan & Nikolov 2012), which in turn is lower bounded by T(oo)/ Vlog(m) using its characterization in terms of semidefinite
program (Matoušek et al. (020). Our result shows that we can get a / /log(m) better lower bound. We complement this lower-bound with a tight upper bound in Appendix D (see Theorem D.II) matching up to an (log((16) min (p, (og(2m)) } factor, combining this and Theorem I.4 gives Theorem 1.2
The meaning of 7(p) (A) in Theorem 1.4 is not immediately apparent. Thus, as of its applications, we study explicit lower bound (with respect instead of T(p)) (pp) (A)) for some special types of queries that are widely used the community of privacy. We first characterize the accuracy of prefix sum, i.e., when the query matrix Aprefix is lower-triangular all-one matrix. The upper bound in Theorem 1.5 follows from the binary tree mechanism (Chan et al. [201]] Dwork et al., (010)) while the lower bound uses Theorem I.4 Notably, we can extend the lower bound for prefix sum queries all rather than limiting it to high privacy regime of & < 1/2 as in Theorem 1.4
Theorem 1.5 For any n N and any p [2, oo), the matrix mechanism, Mtact achieves the following error guarantee while preserving (e, -)differreetti privacy:
(n-/r log(n) Mlg(1/8)))) (og(p))o(n))
errez Aprefix n)
Further, there is no (e, (e.d)-diffreentiall private mechanism M that achieves
err (M, A prefix; n.) =0 ( f/mn//1op log(n) ) for 8 8 min
en 3p In(n)
16
We note that شع -1 O(e) in high privacy regime where E = (1), so the lower and upper bound match in such regime. Theorem 1.5 recovers the result in Henzinger al. (2023) for 2 as special case, Moreover, exactly characterizes the error of prefix sum with respect to any & metric for constant p. One can obtain an 22(log(n) lower bound on -errrr using a slight modification of the packing argument in Dwork et al. 2010 for 8 = o(1/n). Our bound extends the macking-bssed lower bound to larger values of 8 and all
p E 2, 2o).
As another application, in Theorem 1.6 (shown in Appendix C) we characterize the lower bound on privately answering parity queries. The theorem recovers the lower bound in Section 8 of Henzinger al. (023) for p 2 and Section 3.6 of Edmonds et al. (2020) when p oc.
Theorem 1.6 Let OT. be the collection of parity queries. For any (s, -idfffrrennt private mechanism M for answering queries in 22, the worst case Eg error
errg (M.
(())= =0
( 33
8) d 1/2+1/1
Organization of the proof. In Section 2.1 we first develop the lower bound for additive noise mechanism on arbitrary matrix with linearly independent rows. For general matrix, in Section 2.2. we remove the linear independency assumption
the start of Section 2 and then with the help of the back-box reduction from additive noise mechanism to general mechanism, we give (e, DDD lower bound with respect to general matrix A E mm in only high privacy regime, which establishes Theorem| I.4 Next, in Section 2.3 prove easy-to-use bound Theorem [.3 based on Theorem I.4] We derive Theorem [.5 as a corollary of previous sections. The proof of Theorem 1.6
follows similar reasoning and defer it in Section
4

---

Published as a conference paper at ICLR 2025
2 LOWER BOUND FOR (E, AND ITS APPLICATION
In this section, we prove our lower bound and its applications in proving lower bounds of prefix sum and parity queries in f metric. Throughout this paper, we write 2 b if there exists some universal constant e such that 2 b. For proving the lower bound in terms (s, -)-iifferential privacy, we first consider special class of mechanisms that adds noise sampled from an appropriate distribution to the real answer of the queries (a high-level idea our proof is presented in Appendix B). We call such a class of mechanisms the additive noise mechanisms. Unlike Nikolov & Tang (2024), we do not assume that the mechanism unbiased which makes our analysis more subtle.
Before stating the result, fix some notations. Let B {ir R ||]|p 1} denote the n-dimensional bp b-alll and ABT := {Ar: : x ]T} denote the sensitivity polytope. To describe the lower bound, for any matrix A E R= we define the map, k : Rmxa + R. that computes the width of the sensitivity polytope with respect to the most "narrow" direction:
((A) = min WARF( (0) where WART (0) = max O Ax min 0TAa |
(3)
|0
|1
To prove Theorem 1.4
we first show lower bound for additive noise mechanisms when A has linearly independent rows. We then remove this assumption in a high privacy regime (c < 1/2) in Section 2.2 Theorem 1.4 then follows by using general reduction of Bhaskara et al. (2012).
2.1
LOWER BOUND ON ADDITIVE NOISE MECHANISMS
Theorem 2.1 (Lower bound for additive noise mechanisms) Fix any E 0, E 20) and query matrix A E RRmxn, There exists a ō(A, n) = min Io. s² s:m(A)n'-2/9 such that for any 8 < m(),e,)), if M as (e, -idfffereett private additive noise mechanism, then for any x E TR?",
(2%()(()
E Aell))) 1/v
(1-8')((p)A)) 8(c~
where 8'= 1-
28
The above theorem implics an almost tight lower bound in high privacy regime. For example, when 0 S E S 1 since 36 I e - 1 < 6c, it directly implies that
3,
(1
(A)
(E (o
48c
This matches the upper bound given in Theorem D.I For additive noise mechanisms. Theorem is naturally instance-optimal on any x E IR. We note that the range of 8 in Theorem depends on (A),, and is easy to verify that k( > if and only if A has linearly independent rows (see Lemma 2.5 for details). While special linear queries such as prefix sum and parity queries inherently possess linearly independent rows, there are many interesting matrices without linearly independent rows. In the high privacy regime, which was the setting considered in Edmonds et al. (2020). we remove the full rank assumption (see Theorem 2n Section 2.2b. This underpins Theorem 1.4
The main technical obstacle of Theorem 2. lies in making explicit all the intricate dependencies on the width of the sensitivity polytope, and how to handle the bias in lower bound proofs. We note that Edmonds et al. (2020) only studies E error. Therefore, without loss of generality, it can be assumed that the bias is O. Nikolov & Tang (2024) studies an unbiased setting and their approximate DP lower bound depends
the minimum width of the polytope (wp in Nikolov & Tang (2024)). Our lower bound does not assume unbiasedness, and our lower bound in Theorem [2. does not depend on the minimum width in the bound itself. Instead, the minimum width only required in Theorem 2.1 for the applicable range of 5. This means that our bound remains non-trivial even if the minimum width like 1 n.. In proving the new lower bound, we also adapt geometric characterizations in Nikolov Tang 2024) to handle bias of an additive noise mechanism. We also give more detailed discussion in Appendix B.3
To prove Theorem 2.1 we consider mechanisms of the form M(x) = Ar+z, where 2 is stochastically independent of xr. For any input x E R., we define the covariance matrix of M(x) to be
[m(x)= ((( (MM())))((()) E[M())))
5

---

Published as a conference paper at ICLR 2025
Since additive noise mechanism be biased, [[M(2)] is not necessarily Ar. We prove in Appendix E. the following relationship between the fg error and the p-trace of the covariance matrix.
Lemma 2.2 Fix any p [2, oo) and any additive noise mechanism M R R It holds that VE R",
(I [[[M(x) - Arl 1/p 2 (Vtp//(M(()))
Therefore to prove Theorem 2.1 it suffices prove a lower bound on tr (z))2( for any additive noise private mechanism M(-). To start with, give statement bounding the bias of an additive noise mechanism. In particular, using the Hölder's inequality, for p 2 2, we have
EE 2
(EE)) &
Σ(E
- (1-22)/
& [E 2/2 (x--2//p.
Taking the square root of both sides gives the following result.
Lemma 2.3 Fix p 2 Let M(x) Ar be an additive noise mechanism with 2 R"", then (E]IM(<>> Az (1))
1/8
| (/2-1/2)
Yoo (A) (--2)) 2//20
Therefore, we can assume
|||=|]l I
Otherwise, due to Lemma 2.3 for all x E R",
|||||||2
Y(p) Tis) (A)) T(p) (A) (1-8') (A)
[[L(()) - AxIE) //
(p-2))2pp
(n(v-2)1/2
So, suffices to prove a lower bound on tr E (M)()) for additive noise mechanisms with small bias. For this, we use folklore trick (Smith) 2016) that has been used frequently the literature of differential privacy. It consists of the following steps: For distributions 2 and 2 corresponding to the output distribution of define the support on which the privacy loss variable with respect to DD and DD is bounded. Then we update the probability distribution D such that the privacy loss random variable with respect to the new distribution and D is still bounded and the measure of the new distribution is close some metric to D. more details, for any two distributions and Q over Z and > 0, let
mechanism on the neighboring dataset, we first
Q(w) S Se²) be the subset of the ground set Q in which P and Q c-indistinguisaable. Note that this is the same Bads in Kasiviswanathan & Smith 2014b). As in Nikolov & Tang (2024). define
SP.Q.e =- { E Ω e S P(w)
P Q(Sp.Q.e) P(T n Sp...))) Q(T) 2(SP.Q2))
where T Q. This allows us to reduce differential privacy to x2 divergeen (eq. 10 using Lemma 46 in Nikolov & Tang (2024) (see Lemma 18).). The following lemma (proven in Appendix (E.2) states that, for small bias additive noise mechanism, f2 I2 and P.Q are distributions of some additive noise mechanism on neighboring datasets, then E x [X] Ex=qq(X) cannot be small.
Lemma 2.4 Suppose the additive noise mechanism M(x) = Ax + 2 (E, 8) dJiffeerentill private. Fix any 0 E R Let Mg(x)) : R - R. such that Mg(x) = 0 Ax + AT where [[E[=]]l2 I
P-2
E Then, for aorany any I E R", there exists a neighboring dataset such that if P.Q are the distributions of Mo(x) and Mo(x') respectively, and let P be the distribution defined in eq.
28 (A) 2)/2,, Let e, be such that 8' = I- S min c.x(A) n
16 12)()((A
(4), we have
1
W WAB (0)
17
E x [X
Ex=
-28
V O' (
2
2
We will use Lemma 2.4 to prove Theorem 2.1
To do so, we need to study the applicable range of 8' in Lemma 2.4 Fix any 0 E R Given any E (0, H), let en) be the maximum value of 8 such that
28
1
s. x(A)
2-P
8' =
min
1
e
1 E
16
12 (A)

---

Published as a conference paper at ICLR 2025
Note that 8' > O iff x(A) > 0 as other quantities positive. We characterize when k(A) > 0 in
Appendix F.2 that ensures 8' > O through the following lemma:
Lemma 2.5 <(A) > 0 if and only if A has linearly independent rows.
We will also need two geometric lemmas inspired by Nikolov & Tang (022). that connect & geometry and lg geometry, and also to the factorization norm. For K,L S K" denote by K Ce + Ev E IR. + C That is, K St means that K covered by in terms of translation. We define
inf WERmXm (/ ABT C.. W W
Ap(A):
The first lemma is similar to the one in Nikolov & Tang (024), but for general mechanism (instead of only for unbiased mechanisms). This lemma shows that if the variance of one way marginal of an additive noise mechanism MM-) is lower bounded by the square of the width of the sensitivity polytope ABT, then ABT can be covered by (VM BT terms of translation with proper C.
Lemma 2.6 (Nikolov Tang 2024)) Let M R" + Rm be any randomized mechanism and A IR m be any matrix. there exists some universal constant C such that for any input R" and uny E Th, satisfies Var (Mx))
[alABB] 2
then ABT S+ CVEMM(())..
The original lemma in Nikolov & Tang (2024) is only stated for unbiased mechanisms instead of general mechanisms. Thus, we include proof in Appendix (restated Lemma F.4 for completeness.
The final piece we need is lemma implicit Nikolov & Tang 2024 that connects (p(A) and the factorization norm 7(p) (A).
Lemma 2.7 Nikolov & Tang 2024) For any p E [2, oo] and A e Rmx" Ap(A) 2 7pp) (A).
Now are ready to prove Theorem 2.1
Proof: [Proof of Theorem 2.1 Let ē = 2e - log(1 (1 - 8¹). Note that, for every & > 0, we have
< 1 - e-s, and thus é < 2c + I 35. Finally 1 2/p 2 n For any x and x' chosen Lemma
2.4 we consider two cases based on the variance, Var(0 M(x)]]
(AB (0)
1. When Varl0 M(x)]
By Lemma 2.4
xx>a(X]] - Ex~q [X] is at least
2568'
(1 28
WABT (0)
17
1 1- 85'
V d'Var o 2
WABT (0).
2
8
Note that Q is the distribution of 8 M(xa), and Var M(x)] = Var oblivious noise 01 is independent of the input. Then, by the Hammersley-Chapman Chapman--oonn Robins bound (Lemma A.1 we have that for such pair of datasets (xt 2²):
Var[OTM(a')) M(x')] since the
E EXxF
- Ex=olX11 (1-88')2 (WABT (0))
Var M(x))
Varl0TM(x)) = Varl0 M(x')2
(P.OTM
6Px²
86')2 (WABp(() (8))
(5)
64e- (ef 1)2
Here, used Lemma A. that shows that P and Q are ě-indistinguissable (Defini-
tion A.17 Thus (P, Q) S e
E 1)2 by Lemma 39 in Nikolov & Tang 2024 (also
see Lemma A.13
(a))
2. When Var(0TM(x))
2565' First note that, when 8' S g² < E?, we have
1-88' < 16V8 16a
Therefore, for every E Rm, as in the other case, for any x,
88')2 AWA (0))²
Var MMx)] 2 64e 35 (c 1)2
(6)
7

---

Published as a conference paper at ICLR 2025
Lemma 2.6 with eq. 5 and eq.
implies that ABT C+ CVEM(E)BB where C
162
8-8- So
C² t/p (M)))
inf WE
(trp/2(WW ABT S+ W WBT) (Ap(
(7)
(1-86"AA,4))
for all p 22 2. That is, (tp/2(2MMa))
162
Combining Lemma
2.2 Lemma
and eq.
therefore gives us the result:
(B M - Ax (3)
1/v
tr (x))(()(())
(1 86'
88") Y(p) (A)
162
The proof of Theorem 2.1 is complete after replacing by s.
2.2 PROOF OF THEORFM
Theorem 2.1
assumes that rows of the linear query matrix is linearly independent (i.e., s(A) > 0), otherwise the lower bound reduces to the one for pure differential privacy. We next show that for additive noise mechanisms, this assumption can be removed in the most natural high privacy regime:
0 < < 1, p. e oo] and query matrix A E Rux" I.) is an additive noise mechanism such that M(x) Ax 2 for any dataset R and M(-) preserves (e, -)dfffeerent privacy, then for every RR", we have that there exists universal constant C,
Theorem 2.8
Fix any 0 <
(1 8') (A)
8' 2/22
(E [IMM(s))Aol()) 1/8
-
Ce
where
6-6""
Unlike the proof of Theorem 2.1 we prove the above result using Lemma F.5 in which some of the technical ingredients with (Nikolov& & Tang 2024 Lemma 35). We defer the proof of Theorem 2.8 to Section F Note that
implicit in (Kasiviswanathan et al.) 2010 Lemma 4. 12). Then combine
for general ε >> the analysis of Theorem 2. also naturally gives an (T(p)) (A))(( (E) 1)) lower
bound when A has full rank rows, while Theorem 2.8 only works for high privacy regime.
To obtain lower bound for general (e. difffereettall private algorithm, we recall that the reduction in Bhaskara et al. (2012) does not rely on the еπтоr metric. In particular, Theorem follows by combining Theorem 2.8 and the reduction given by the following theorem get worst-case lower bound for arbitrary mechanisms.
Theorem 2.9 (Theorem 4.3 in Bhaskara al. (2022) Fix any A m Let M R" + R be a (e, 8) -diffeerentillly private algorithu. Then there exists (2e, e difffferrnnllllll private algo- rithm M' Ax with oblivious such that errg (M', A) S errg (M, A).
2.3 CONNECTING ((p) (+) AND SCHATTEN-1 NORM: PROOF OF THEOREM
1.3
In previous sections, we established the connection between the hardness of privately answering linear queries defined by A and the generalized factorization norm of A, denoted as (2) (A). However, expressing Tip) (A) analytically for a general matrix A can be difficult. To provide more practical lower bound and facilitate potential applications, the following lemma, we give a lower bound of Y(p) in terms of the Schatten-1 norm of A, which is simply the sum of singular values of A.
Lemma 2.10 Let A E mn be any real matrix. It holds that
(A) m ////||lll///mm
2023 Theorem 23) and Lemma 27 in Nikolov & Tang 2024), for any p > 2, the Mpp -norm A can be rewritten as the following optimization problem:
Proof: By Nikolov & Tang
7(p) (A) max (1(2) (DA): D is diagonal D o, Tr, (D²) = 1}
where q p-2
p Let D m then D is diagonal PSD matrix and Tr, (122) m .
Using (Henzinger al. 2023 Lemma 1.1), we therefore have
m//n-1/21 1//0-1/2||A||
(A) 2 m 1/p-1/2 7(2) A) = m 1/p-1/2 (A)
Vn
8

---

Published as a conference paper at ICLR 2025
completing the proof.
Theorem
1.3
directly follows from Lemma 2.10 and Theorem I.4
2.4 APPLICATION I: TIGHT LOWER BOUND FOR PRIVATE PREFIX SUM WITH EY ERROR
So far, we have seen that the lower bounds on privately answering linear queries depend on Yp) (A). In this section, we focus a fundamental type of query: prefix sum and establish explicit bound that underpins Theorem 1.5 by giving tight upper and lower bounds of (p) (A) and x(A) ) for such a specific A. In particular, given E N., consider the prefix sum (i.e., continual counting) matrix Aprefix. whose jith entry is
{1
i2j
A prefixx
[1, =
0
otherwise
be the matrix computing prefix sum of the dataset on private prefix sum:
R". We first give the following lower bound
Theorem 2.11 Fix any E (0, ) and E o0]. Then, for any ô S Co-1/111/2 where
1 s(1 - - e -
C. = min 12 (1 (m(4m/5)/m)
if .. R IR. preserves (c, 8) -differential privacy, then
max (BII
Aprefixct (eeeiar(1)))))
1/0 2 21 (1-
logn
where
8 (1 e=e)
28e
#ERR
96c
Next, we show that there exists factorization of Aprefix such that the f fe-error of the matrix mechanism
bounded by ( log(n)) (n)) implying the lower bound Theorem 2.11 is optimal for p = 0(1)
proving Theorem 1.5 If 2(1), then this lower bound is near optimal with only a @( n) gap.
Theorem 2.12 Fix parameters e > O and O < 5 < 1. Given any x E TR",, there exists a (c, 6)-
differentially private matrix mechanism M such that
E ( Aprefx
1/9
3/p log n
log(1/0) min(r, log(n))
2
The upper and lower bound in Theorem 1.5 directly follows from Theorem 2.11 and Theorem 2.12 We defer the proof of Theorem 2.12 to Appendix G.2
2.4.1 PROOF OF THEOREM 2.
To prove this theorem for all > O, we need two things: firstly, lower bound on the factorization norm Yp) (Aprefix: secondly, in order to determine 8', we show that x((Arefix) is lower bounded by a constant (Lemma 2.14). Such geometrie property of Aprefix could also be of independent interest. Then, the explicit lower bound on privately computing A Aprefica: is obtained by applying Theorem 2.1
and the black-box reduction given in Theorem 2.9 (Theorem 4.3 in Bhaskara al. (2012)
Lemma 2.13 Let Aprefix be the matrix defined in Equation (8) Then, (Apreti) 2 n n.
Proof: Recall that for any p > 2, the Ep factorization norm Aprefix can be rewritten as: Tpp) (Aprefii) max (T2)) Apretii)) D is diagonal, D > 0, Tr, =1} where q p_ Let D 1/2// then D is diagonal PSD matrix and Tr₃ 2/p1-1
p-2
1// = 1. Using (Henzinger et al. 2023 equation (5.30)),
(Apreii) 2 1//-1/22 72) (I A Aprett) 2 / log
completing the proof.
Next, compute n²( (preffx). The proof of Lemma 2.14 is given in Section G.1

---

Published as a conference paper at ICLR 2025
Lemma 2.14 Let rc.)) be defined in eq.
(3) Then x(Apeefx) = 2.
Now ready to complete the proof of Theorem 2.11 which is lower bound for private continual releasing of the prefix sum on arbitrary &p metric with S < 20.
Recalling Theorem 2.1
it remains to show (AAprefix n, 2 CanA/p-1/2 In particular, we have the
following:
2-p
8Appreti e, n)
2(e
min
8 15( A preffix) n
e²
2(e -1) 1)
min e n 6 Gyp((ppetiin
2
16' 12T(p) (Aprefix)
6
c(1 - - E2e (1-- (1-6(1)))))
Ce n1/2-1/p²
2
n
min
12 (1 + (n(4n/5))//
2
where the first inequality comes from that Nip. ()) < (2) = (r() for any A and 2 2, the second inequality follows from Henzinger al. (2023). This completes the proof.
DISCUSSION
In this paper, we established lower bounds on approximating the linear query Ax with respect to approximate differential privacy under ée error, so we can study the optimality of matrix mechanisms only in expectation but also with respect to probability tail bounds. For limitations, we note that we only give a worst case lower bound over all z E R" by the definition of E error metric (see also eq. (T). To understand why we cannot get a instance-optimal lower bound, consider a trivial mechanism Map such that for any E TR", it always outputs Azo where E IR=" is any given dataset. Clearly M2. is not an oblivious additive noise mechanism, and it preserves perfect differential privacy, ie.. 0, and perfect accuracy on the input To. which explains why instance-optimal lower bound is unrealistic for general mechanisms.
In Nikolov & Tang (0024), the authors study unbiased mechanism, and show that the Gaussian mechanism is indeed instance-optima over all such unbiased mechanisms, by giving an asymmetric lower bound saying that if an unbiased mechanism performs well in an input zo, then it must perform worse in some other inputs x' where x' neighboring ih- is still open if such an asymmetric lower bound exists for general linear queries over all general mechanisms.
ACKNOWLEDGMENTS
The authors would like thank Aleksandar Nikolov for his valuable comments and especially his insights on removing the assumption of linear independence in Edmonds et al. (2020) and an earlier version of this paper. The authors also thank George Li for his discussions during the project and his helpful feedback on the paper draft.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar. Unconditional differentially private mechanisms for linear queries. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 1269-1284, 2012.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, (55-4):111-0777 2014.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 715-724, 2010.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentiality, 7(3):17-51, 2016.
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mecha- nisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 425-438, 2020.
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound differentially private continual observation. In International Conference Machine Learning, ICMI., Proceedings of Machine Learning Research, pp. 10072-10092, 2023.
Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2951-2970. SIAM, 2025.
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differen- tially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 5003-5039. SIAM, 2023.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. International Conference on Machine Learning. pp. 5213-5225. PMLR, 2021.
Shiva Prasad Kasiviswanathan and Adam Smith. On the 'semantics' of differential privacy: A bayesian formulation. J. Priv. Confidentiality, 6(1), 2014a. doi: 10.29012/jpc..611.634. URL https::/doi. http:::://oo..or//// 2t..:0..112222 jpc. v611. 634.
Shiva Prasad Kasiviswanathan and Adam Smith. On the semantics' of differential privacy: bayesian formulation. Journal of Privacy and Confidentiality 6(1), 2014b.
Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 775-784, 2010.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793 399-8,799-82, 2011.
Chao Li and Gerome Miklau. Optimal error of query sets under the seiteentially-privatt matrix mechanism. In Proceedings of the 16th International Conference on Database Theory, pp. 272-283, 2013.
Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal, 24 (6):757-781, 2015.
Jifí Matoušek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy. International Mathematics Research Notices, 2020(3):511-88., 2020.

---

Published as a conference paper at ICLR 2025
Hermann Minkowski. Review of "les systèmes d' d'équations linéaires à une infinite d' d'inconnues". Paris: Vaulaier-Villars, +I+ 182 S. 8 (Collection Borel.) (1913)., 1913.
Shanmugavelayutham Muthukrishnan and Aleksandar Nikolov. Optimal private halfspace counting via discrepancy. In Proceedings of the forty-fourth annual ACM symposium Theory of computing, pp. 1285-1292, 2012.
Aleksandar Nikolov and Haohua Tang. Gaussian noise is nearly instance optimal for private unbiased mean estimation. CoRR, abs/2301. 13850, 2023.
Alcksandar Nikolov and Haohua Tang. General gaussian noise mechanisms and their optimality for unbiased mean estimation. In Innovation Theoretical Computer Science, 2024.
Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 351-360. ACM, 2013.
Friedrich Riesz. Untersuchungen über systeme integrierbarer funktionen. Mathematische Annalen, 69(4))449-49)) 1910.
Frigyes Riesz. Les systèmes d' d'équations linéaires une infinité d d'inconnues. Gauthier- Gauthier-Villars, 1913.
Marcel Riesz. On the maxima of bilinear forms and on linear functionals. Acta mathematica, 49 (3-4):465-497, 1927.
Adam Smith. Personal communication. 2016.
G Olof Thorin. Convexity theorems generalizing those of riesz and hadamard with some applica- tions. Comm. Sém. Muth. Univ. Lund [Medd. Lunds Univ. Mat. Sem. 9:1-58, 1948.
Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pp. 347 457.450,22 2017.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge University Press, 2018.
12

---

Published as a conference paper at ICLR 2025
A BASIC DEFINITIONS AND PRELIMINARIES
Matrix theory and Convex Geometry We first introduce several definitions regarding the matrix norms and geometric properties the query matrix A.
Definition A.1 (Schatten-1 norm) Let $1," Sm be the singular values of A, define the Schatten-1 norn to be
m
A|||
Σ
8i- i=1
Definition A.2 (p-trace) Fix any N+. Let U E Iddd be positive semi-definite matrix, define the p-trace norm to be
1/p
d
trp(U)= =
UP 8
Naturally, define (U) m [Ua]. The following definition for generalized factorization norm was firstly pointed out by Nikolov and Tang Nikolov & Tang (024):
Definition A.3 For any 2 S S do and A E Rax" we define
( (twa((LT))
(A) min LR=A
can be verified that (1a) tr (LpT)(LLT) = 1| and when + co, then tr (LLT) = max (LLT); = 14112 We use
(A) = (A) and (A) = (2)) This is because when p =
the following result connect the factorization norm and the Schatten-1 norm:
Lemma A.4 (Henzinger et al. (2023) and Li & Miklau (013)) Let A E C be complex ma- trix Then
||
(A) 2
Vn
Using Theorem A.4 Henzinger et Henzinger et al. (2023) showed the following bound:
Theorem A.5 (enzinger (203)) For any n N, let Meount be a lower triangular matrix with all ones.
Then
/n 2
2n +1
In(2n + +1)
1(2) (Mcount)
π
2n
Definition A.6 (Parity Query) Let and w integer parameters and let the domain be X [+1]d. Then a parity query is query that belongs to the family of queries
Q
qr(x))
II REP
o. PC ((l....,d,,,II
(9)
Definition A.7 (Hadamard matrix) Fix any integer d 2 1, the d-th Hadamard matrix Ha is 2d 2d matrix
Ha-1
Ha-1
Ha-1
Ha-
When d = 0, Ho [1].
The following definitions related the geometry property of a query matrix.
Definition A.8 Fix any d E N. For any K, L C IR., we write
K C.. L + Fu ER Ku L.
13

---

Published as a conference paper at ICLR 2025
This is saying that if K C++ L, then K can be covered by L by "relocating" the center of K. Next, we define the width of a convex body.
Definition A.9 (Width of convex body) Given any vector 0 IR we define the width any convex body K S _h with respect to 0 be
W (0) == max 0'
min 0 x.
#EK
We use B denote the unit ball of dimension d with respect to the bp norm. Formally,
By = R ||>||p - 1}.
For matrix W with d columns, also write W W (Wx E BB) denote the sensitivity polytope of W with respect to the p-th norm.
Definition A.10 (Nikolov & Tang (2024) For any query matrix E m and E [2, oo). we define
Ap(A):= inf WER { (VWT)/((WWT) ABT S. W
Here, we give some insights about why (A) in Definition A.10 is useful for establishing the lower bound. Geometrically, AB, is exactly the convex body comprising differences between the ground truth output of any pair of neighboring datasets, A(x =²) where || x' 1. Since (p(A) is the minimum trace norm of WWT where W B3 covers the sensitivity polytope AB, then, Ap(A) can be interpreted as a specific kind of measurements on the volume of the body W BY that "covers" A(x 2') over all pair of neighboring datasets.
Intuitively, if this volume gets larger, it is harder to preserve utility because the outputs of neighboring datasets will be far apart. Therefore, it gives way to prove the lower bound by establishing connection between the f error and (A))). The following lemma also reveals the relationship between (A) and the factorization norm (A):
Lemma A.11 Nikolov & Tang 2024) For any p E [2, 00] and A E R Ap(A) 2 7pp)
Basically speaking, for any matrix A E RR one can always find a factorization of A = LR such that [| is smaller than and that ABT C.. LBT. Then, taking the L that minimizes / ttpp/(LLLT) yields the above lemma.
Differential privacy. Here, we first introduce Gaussian mechanism, which is the main component of the upper bound proof in this paper.
Lemma A.12 (Gaussian mechanism) Fix any 0 e, 1. Let f X + Y be any deterministic function. for all neighboring dataset x, x', [I[(x) (xx))l2 2 S A, then M(x) = (xx + where
02 satisfies (e, d)ddiffereltial privacy as long as σ² 942 log(1/6)
25
As in Nikolov & Tang 2024), of the necessary conditions of DP algorithms that will consider that DP algorithms preserve the -dvveeegee between neighboring datasets. For two distribution P and Q the x2 divergence between them is
@(a)) -1 -
x2 (P.Q)) = =
(10)
is not hard to verify (perhaps it is also well-known) the following lemma:
Lemma A.13 (Lemma 39 in Nikolov & Tang (024)) Suppose M is an e-differentially private al- gorithm and x, x' be two neighboring datasets such that || - I'1l1 S 1. Let P and Q be the distributions of M(x) and M(x') respectively. Then
(P),Q) < (e
14

---

Published as a conference paper at ICLR 2025
The reason why consider x² distribution is that the lower bound of the variance of real random variable can be characterized by its x² divergence between another arbitrary random variable. This is the classical Gammersley-Chapmann Robins bound stated in the following lemma:
Lemma A.14 -haneerleyy-haaaan---eee Robins bound) For any two distributions P. Q over real numbers and for X, Y distributed, respectively, according P and Q, we have
Var(YY) [[ EY]
Vx²(P.Q)
We also need the following lemma in this paper:
Lemma A.15 (Lemma 4.4 Kasiviswanathan et al. (2010)) Let E R." be any single query and (z) w² x + 2 (z' E R. be any additive noise mechanism that is (E,0)-differentiall private for any < E < 1, then E[ z for some universal constant C.
Lemma A.16 (Kasiviswanathan & Smith (2014b)) Let M be any (5.8) difffferrett private mechanism, let P be the distribution of M(x)
1) and Q be the distribution of M(x'). Let
P(w) Sp.Q. WEREET f 1 Q(w)
Se e
(11)
Then
25
max (Pr(P PrQQ $]} < 8
1 E-
Given distribution and Q and defined by eq. 11 Nikolov & Tang (2024) defined distribution P such that for any T Q
P (Sp..2.)) P(SpQ.2))
PPT)S + Q(T
(12)
Here we define (e, ( indiisiinguishabbltt::
Definition A.17 Kasiviswanathhnn & Smith (001b)) Let be a ground set and p1, P2 be two
distributions with support Q C Q, She C Ω respectively. We say that pr and #2 (s, 6)- indistinguishable for & > and E 10 for any S C 2 it holds that
pi (S) S (S) ef + and 12(5) I (S(S) e + 5.
If 8 = 0, we also say and are e-indistinguishabl.
We use the following lemma to characterize the relation between P and Q:
Lemma A.18 (Lemma 46 in Nikoloy & Tang 2024)) Let P.Q be a pair of (s,
indistinguishable distributions over Ω and P be the distribution defined in
12 then
P(w) log (w)
2 16--oo log(1 - 85) = =
for all w E Ω. Here, 8'
28 T-e-r.
That is to say, P and Q are ě-indistinguishable.
Error Metric. Two of the normally used metrics for private mechanism M are the squared error (denoted by errMsB) and absolute error (denoted by erre ). respectively:
erTMSE(M, A, = max 2E3"
[M(x) Ax
7
(13)
err (M,, = max [[[[(x) - Aroloo]] ZER"
B HIGH-LEVEL OVERVIEW OF OUR TECHNIQUES
In this section, we briefly discuss techniques and ideas that underpin our proof.
15

---

Published as a conference paper at ICLR 2025
B.1 UPPER BOUND ON MATRIX MECHANISM EY METRIC.
To find an upper bound on answering linear queries, we use the Gaussian mechanism that adds correlated noise based on factorization of the query matrix A. Specifically, given a query matrix A E R= we consider the additive noise mechanism M(z) = Az + 2. For any factorization of LR where E Rm and R E R such mechanism can be rewritten as M(xx)= L(Re + z²) where Lz' has the same distribution as z. Finally, we show that minimizing the g error on such mechanism is equivalent to finding an "optimal" factorization of A, and the optimal error can be characterized by the generalized factorization norm "(p)) (A)).
B.2 LOWER BOUND ON OBLIVIOUS ADDITIVE NOISE APPROXIMATE DP MECHANISMS IN Ep METRIC.
To prove lower bound on mechanisms that add oblivious additive noise, we consider the convex sensitivity polytope ABT = {Ay y E IR" and |لا|| < 1 of the query matrix A E R= We use the following measurement introduced by Nikolov Tang (024):
inf WER"Xm
(VDT))((WTT) : Be E R", ABT +
(14)
to bound the minimum scale of the variance needed for the noise to achieve differential privacy.
Intuitively, if the measure of the sensitivity polytope ABT is larger (in terms of / (trg/a(WWT) then it is harder to make two points in ABT indistinguishable. To formulate such intuition, we first establish bridge between Eg error and the covariance matrix EM( mmxm of the output distribution (Lemma 2.2). Next, a direct approach is to show that an oblivious mechanism M is (c, 8.- diffferentially private, then by standard lower bound in Kasiviswanathan al. (2010), the square root of the covariance matrix (M(2) satisfies that
ABT + VEM(")
for some E R" which establishes relationship between the infimum value in eq. (14) and the g error. Finally, we apply Lemma 20 Nikolov and Tang Nikolov & Tang (2024) to lower bound such infimum value by the general factorization norm Y(p) (A).
However, the lower bound in Kasiviswanathan et al. (210)) works in only high privacy regime. To get O, we use the fact that output distributions of differentially private mechanisms under two adjacent datasets must be close under x² >dddieegee Consequently, we employ the x--divergence to set a lower bound on the minimum variance of the oblivious noise that must be introduced to achieve differential privacy. Since we do not assume the unbiasedness as Nikolov Tang (024). we have to consider the bias of the oblivious noise. However, we show that such a pipeline still works if the oblivious noise has small bias. On the other hand, if the noise has a large enough bias, then one can show that the EG error already large. Combined, we establish a lower bound that the y -roo of the fg error is at least 22((1 5) (A)/e) for any oblivious (e, 6DP mechanisms any query matrix A E Rmmn with x(A) 0.
lower bound for approximate DP algorithms for all
With the lower bounds on oblivious mechanisms, we use the standard reduction in Bhaskara et al. (2012) obtain worst case (in terms of the input x E R²) lower bound for general (c, O) mechanisms that might be data-dependent.
B.3 COMPARISON OF TECHNIQUES
As alluded in the introduction, the focus of Nikolov and Tang Nikolov & Tang (023)) is the l instance optimality of matrix mechanisms among unbiased mechanısms, while we instead focus on the worst case E optimality of matrix mechanisms among any differentially private mechanisms. Here, we highlight key departures between this paper and previous works.
Add/remove model v.s. Substitution model. Our main departure compared to Nikolov & Tang (2024) lies in different privacy notion, leading to different choice of sensitivity polytopes for the geometric arguments of lower bound. To elaborate, we recall a natural way to view linear query as a mean estimation task suggested in Nikolov & Tang 2024
16

---

Published as a conference paper at ICLR 2025
Let X' be the domain of data points, X (21 22,,... .2)) be the dataset, and Q X' - R" be the query workload. Then, answering Q(X) is equivalent to doing mean estimation in the polytope Kº {Q(z): x E
X²). The authors in Nikolov & Tang 2024) considered a substitution DP model,
where a data point can be replaced by another within the domain. If we further let h E E (where | = n: in the notation of our paper) be the histogram of the dataset, then the substitution DP model corresponds to the neighboring notion where ||h - h/1l1 I and Exex (hg k₂)
(i.e., bounded DP). This differs from the commonly used privacy notion for linear queries (as used in Bhaskara et al. (2012), Edmonds al. (2020) etc.) where we only ask || h'll 1'Il1 = ((1), representing natural & sensitivity, and is more like the add/remove DP model when translated back to mean estimation. 6
Even if we restrict our discussion to the substitution DP model, the lowerbound for mean estimation from Nikolov and Tang would be in terms of I r == inf { (AAT) : Ko Se AB3 In contrast, our lowerbound for linear queries is in terms of the factorization norm of the workload matrix A associated with the query Q. These two are not comparable: imagine when the workload matrix consists of vectors that are very far from the origin, but are close to each other; then we have small (K)) but substantially larger factorization norm of the workload matrix A. Therefore, lower bound in terms of T (K(K) does not imply a lower bound in terms of the factorization norm (A) as ours. Essentially, this is due to the fact that the most suitable choice for "sensitivity polytope" is different for mean estimation and linear queries.
Technical comparisons. Our departure in analysis and its complication compared to previous works stems from the fact that we do not assume unbiased mechanisms. Our different approach also means that our dependency on K appears only in the applicable range of the privacy parameter 8, instead of showing up in the lower bound itself. We elaborate it next.
The lower bound of Nikolov & Tang (2024) combined techniques from Edmonds et al. (2020) for oblivious mechanisms with the classical results for unbiased estimators, T.e., they crucially rely on the estimator being unbiased. We first explain at a high level why they need the assumption of an unbiased mechanism.
Edmonds et al. (2020) showed that the variance of the mie-dmmesioonal private mechanism is lower bounded by the width of the underlying sensitivity polytope. For a data oblivious mechanism, as considered in Eddmond et al.] (2020) in their first step, this almost immediately implies a lower bound. However, this might not always be true for unbiased mechanism. In fact, since Edmonds et al. (2020) consider the l error metric, they can assume without any loss of generality that the bias is O. This is not the case for Eg error considered in Nikolov & Tang (2024) or e--error as considered in this paper.
This causes the departure of our proof technique from Edmonds et al. (0200) and Nikolov & Tang (2024) since we cannot assume that the bias is O either by an assumption of unbiased mechanism or because of the choice of metric (i.e., f2 error metric). We first show in Lemma 2.3 that the error would be large if the bias is large enough. So, the rest of our proof has to deal with the setting when the bias small. In fact, using a case analysis based on the magnitude of bias is also helpful from another perspective: our lower bound depends only on 7(pp norm while the effect of minimum width of sensitivity polytope is reflected in the applicable range of 8 when we consider any (including the low privacy regime). In general, the width of the sensitivity polytope can be 0 as shown Lemma 2.5 but as we show it is lower bounded by a constant for two important linear query matrices. Further, for general linear query matrices whose sensitivity polytope has a small minimum width, say 1/n, our lower bound remains non-trive trivial, While|Nkolae & Tang (2024) only provided a very weak lower bound (that is, dependent inversely on the dimension). We discuss it next.
For approximate differential privacy, Nikolov & Tang (024) proved that any mechanism would have large eтror either on the input or one of its neighbor x'. This is because they rely on classical result from statistics, known as Hammersley Chammersley-Chapmann.
bound (Lemma [. 14). To apply this bound, they need to prove that the x² -dvdieegee between the mechanism's 's output on two neighboring datasets is bounded. However, while this is true for e-differential privacy, this is not true for (e, 6) ddifferential privacy because the support of the two mechanisms might differ. To ensure that
'We have also confirmed with the authors of Nikolov & Tang 2024) that if using add/remove DP as in our setting, lot of results in their paper need to be modified. Consequently. there is no black-box reduction and it does not appear simplify our current proof.
17

---

Published as a conference paper at ICLR 2025
the two distributions have the same support, they use the general trick used in differential privacy (and, to our knowledge, first appeared in Kasiviswanathan & Smith (2014a)) and define a set as we defined in eq. 44). This set serves two purposes: (i) the x -iveeeegee between both distributions bounded, and (ii) the difference of the expectation of either the two distributions restricted the set is close the original unrestricted distribution unless one of the two distributions has large variance, We can now do the case analysis. In case 1, if the expectation of neither of the two distributions changes much, we can restrict our attention the defined set. Otherwise, we are in case 2, where we just pick the distribution whose expectation changed by a lot and for which we are in the case where the variance is high. As a result, one can only prove that either Munbiased or Munbiased (x') have large error.
There is another price with this analysis. we are case 2, then their technique gives a lower bound on the variance that depends on the minimum width (x(-) in our paper and wx)() in Nikolov & Tangl (024)). Due Lemma 2.5] their result by itself is vacuous if the query matrix has linearly dependent rows. They alleviate this concern using the following trick: one can always find random subspace, so the minimum width at least the inverse of the dimension of the original sensitivity polytope under the projection onto that subspace. In other words, in case 2, can only prove lower bound with inverse dependence on the dimension. As result, the lower bound is less useful as the dimension increases.
Since the reduction from the class of oblivious additive noise differentially private mechanism to the class of general differentially private mechanism follows from Bhaskar et al. [Baakkar al. (2012). we only focus on the class of oblivious additive noise differentially private mechanism in the following exposition. Since the large bias case is easy to deal with (and already implies lower bound on the error as shown in Lemma 2.3j. we need to deal with the case when the mechanism has small bias.
Dealing with the possibility of bias results in an extra term of E[0 =] 1 1- 8 in eq. 17 where P
and Q are the distribution of the output of the mechanism on two neighboring datasets, 0 E 12d and is the noise which is stochastically independent of the input. Since E[O z] is not identically zero, this term finally results in an extra term of 8 E(E 2] term. For a non-vacuous lower bound, this term has to be ow ABY (0)) in all directions 8. Using the fact that we are in the low bias case, we have an upper bound on E[O z]; this gives us an applicable range of 8', i..., the value of for which the E[0T 2] E o(WAR AB (f)), which in turn depends on the narrowest direction of WABC This narrowest direction is x(A) by definition.
C PROOF OF THEOREM 1.6
We use the observation made in Edmonds et al. 2020 Let Q = =d, be the corresponding matrix of the va-way parity queries on the domain 1-1, ja Then, Q is the sub-matrix of a 2d 2d Hadamard matrix H (see also Definition A.7 produced by selecting (w) rows of H. We have the following lemma that gives the lower bound on x(Q). This allows us to set the range of 8 and combined with the worst case lower bound Theorem 1.4 give an (c, 6)DP lower bound for general mechanisms on answering parity queries.
Lemma C.1 x(Q)= 2 2.
Proof: Let (d) and let q 42 4, be the rows of Q. We first note that since Q contains é rows of Hardamard matrix, then each row of Q is orthogonal to each other, and the Eg norm of each row q,T is 24/2 where & i S l. We recall that
K x(Q) = min
TTQZ= max T Qz - min 0 Qz) 11
(15)
1ell:11
First note that for any fixed unit vector 0 (01, 0z. 0z) R
t
QTQ2= = =081q + .... (019 + + peqe) = Σ pgg = 2d Σ 8 = 2d
i=1
18

---

Published as a conference paper at ICLR 2025
where the second equality comes from that q 9 0 for any i j. j. Then, we choose x4 R²" be the vector such that |I++|11 1 and 01 Q c for some scalar 0, and 22 Finally, observe that
10 Q112
i Qr+ - 0- Q--=== 20 Qx 2
Q|12 2 ||+ //2
22
where the inequality comes from the fact that || 112 2 |21||1/ 1/12/22. Since for any A we can always find such a pair x. and x-, then we have (Q) 2 2 by eq. (15)
Lemma C.2
|QQ11 (4))4/2
Proof: As noted in Edmonds et al. (2020) the parity query matrix, Q, is the submatrix formed by choosing the appropriate (() rows of 2d 2d unnormalized Hadamard matrix. In other words,
n 2d and m = (+)- Since the Hadamard matrix is orthogonal, the rows of Q are linearly independent. Furthermore, there are (w) singular values, all of which are 24/2, Since [|Q11 is just the sum of the singular values of Q, we have the result.
Setting n 24 and m
gives us the required bound and proof of Theorem 1.6.
D PROOF OF THE UPPER BOUND
We first state the theorem in its full generality for the ease of the readers.
Theorem D.1 Fix any < e, <1 and 2 S p < oo. For any query matrix Tkmx and dataset
E RR, there exists a factorization of A LR and parameter = ale, 6, R) such that the mechanism
M(x) == L(Rx + 2) where each entry in 2 is i..d sampled from N' (0, o2) preserves (e, didffferent privacy. Moreover,
log(1 log(1/6) (60)) log(2m))
EE [Il((x) Ax1E))
(A)
2=a
Note that the factorization of query matrix A is independent of æ. Thus, the mechanism (-) can considered as the post-processing Rr. + z. The lg sensitivity of Ra can be bounded by
Proof:
Let 3 (8g(//))
Rx Rx 112 S max
|Ryle = ||]]|
since || x' 1| < if (I,x') x') is pair of neighboring datasets. Then, let o² A
277 where
A 1- by Lemma A.12 Rx preserves (e,6)-DP well M(x)). For the utility part, we consider the Gaussian variable z' = La and thus z' AN(0, LL Then, the eg error can be formulated
E M[x - Arll)) (E [ + Lz - Ax Ax
1/8 = (E [IIAT + 2' - Axll)T) 1/p
1/P
(E 11=))
Σ
iEn
v log(2m)
(Var [
ViE
min log(2m))
22p / min log po v (t,/2(LLTT)
Letting L and R be the optimal factorization of A yields the desired result. Here, the inequality comes from the standard bound on the p-th moment of the Gaussian variable (Proposition 2.5.2 in Vershynin Vershynin (208)) and the union bound over all coordinates respectively.
0
19

---

Published as a conference paper at ICLR 2025
E
MISSING PROOFS FROM SECTION 2.1
Recall that
Em(x) E(((()) ([M()))(M(2) B[M())))
the covariance matrix of (a:)..
E.1 PROOF OF LEMMA 2.2
The proof follows from the following set of derivation.
d ( (EM(())(AD)))8
(B [1I((x) Axl
BIIM(x) Avl = IE
$
d
(B [MM()) - (Ab)))9)2
Σ
3
Σ
(E (=11)
(E [2 ()) $
#
Σ Var (M
= =t//2(E((()))
E.2 PROOF OF LEMMA 2.4
Note that T M(x) preserves (s, dd-ffferrenti privacy for any M(.) is (e, didifferreel private. Further, WABY (0) max.eAbp TTv min 0 v. For any proposition P. we let
[(P) - {
if is true otherwise
Let S = Sp, By the definition of P, similar to Nikolov & Tang (2024), we have
E Exx Exxo(X]1 =
:P(xx) x((2))
xx((x)) - x²(x)) + xx((x))) - xQ(x))
R/8
s
Q(S)
xP(x) - 2Q(z))
P(S)
(16)
Q(S)
P(S) Ex (X E S}] Xxxo|XXfX e SH
Q(S)
E Ex~p X Ex~o
P(S)
Q(S) E. Ex (11 (X $ S) (1 {
P(S)
20

---

Published as a conference paper at ICLR 2025
We now bound the above two terms separately. Recall that P and Q are distributions of Mz
T (Ax + +) and Ma(x') = e (Az' + 2) respectively, then
S
Q(S)
Ex Ex~P [X] E Ex~ [X]
2 0 A P(S) x -
P(S)*=
Q(S)
|B =]1 1
Q(S)
(17)
P(S)
P(S)
By Lemma A.16 1 8 s P(S)
and 1- 8 - Q(S) - 1. Further, if chose e and such that
8'
then
1 1-8 Q(5)
1
$ 1 + 28'
(18)
P(S)
1- 8'
Now we consider the term
f(x = AT ( QQ(S)
v) 3){
P(S)
We do a case analysis based on the ratio Q(S) P(S)
When Q19) P(S) 2 1, then
ABT C KP.Q= == { AA (P(5)) x -v) 12) :11 -ylb
Therefore, there exists a pair of (I+t, x44) with (x4 2-) E BT such that
f(x+,8+) = TT Q(S)
x+ 4+ )
waR (0)
P(S)
2
When Q(8) P(S)
1, then the set
P(S)
A Q(S) (0(5))-))
P(S)= || - u1l { A (A(x= x- Q(S)")) 11
P(S)
K2pQa
:1ıx - x1li
Q(S)
contains ABT. In this case, there also exists pair of (x--y-) with (x- -y-) BT such that
(
Q(5)
w-)
Q(S)
wand (0)
2 2 (1 8¹) w WAR (0)
A ((())
P(S)
2
Finally, we have that
Q(S)
(ABT
Ex -X [X] 2 21--8))
28' 2.
(19)
P(S)
2
Next, we try to bound the second term in eq. [6):
Q(S) Ex Ex-r|X & SH - ExI-Ex-lXX({X & SH
S₂ =
P(S)
Q(S)
P(S) Ex Ex~pl(X - [x & SH - Ex~Ql(X Ex(x1)1fx & 8i
Q(S)
P(S) Ep X Ex[1[X $ 5h - Eo[X] Eq & sh]
+
(20)
Q(S)
<
Ex Ex~r[(X - Ex(x)] & S) + +Exxol(X - Bx(x & S}]
P(S)
Sea
Sa1
Q(S)
+ 8
Ex [x= - Ex=olX]
P(S)
Saa
We bound each of these terms separately.
21

---

Published as a conference paper at ICLR 2025
Bounding S21 and S22
Using
Q(8) P(S) I 1 + 26', have
Q(S) S21 P(S) (X--((X-Bp(x)1(4 & SH S (1+ [Ex~p[(X Ex(X]) $S]l
$ (1 + 28)) -x-))
< + 28)) V 8 Ex S (1 + +5") 1
Similarly, we see that
S22 -Fo-o((XBo((]]] $J]] / (8Varl(0T M(a'))
Therefore.
Q(S)
S21 + S22
Ex~p[(X- - Ep( & SHI + Exxol(( - Ex(X]))(X & SH]
P(S)
Q(5)
$ P(S) V
(Var((TM(z)) + 8'Var(OT M(x')]
(21)
$ (1 + 28") 8'Varl0T M(x) + 8'Varl0T M(x')).
where the last inequality is due to eq. (8)
Bounding S23
With similar argument as in St, we have
S23 = 8'
((S)
Ex-r(X X [x] S 8 TT A
(P(S) 1 v) + +8 =]
[(())
Q(S)
P(S)
P(S)
ABA (0)
s 8'
28'BA
(22)
2
where the last inequality can achieved under the same choice of x and y as in eq. 19
Plugging the bound in eq.
21 and eq. 22 in to eq. 20 we get
Sa < S21 + S22 S23
S 8' WAB (0)
(23)
E0 z + (1 + 28') (VVrr(oMM(a)) + + LiVarloTMMan
2
Plugging eq.
17 and eq.
23 in eq. 16 and setting (c, 5) such that
e e. <(A) n op
8' s min
, s 2'
16'
12
for any fix 6, we have that for every x E R.,, there exists an x' such that || x' 1/1 S 1 and
Q(S)
E x
Ex=
Ex-p X Ex~o(X]
P(S)
Q(S)
Ex~ 1xxN(XX1X & SH - Ex SH
P(S)
WAB (0)
28')
38'E0 = 2-(1+ 28') 8'Varl00 M(x)) 8'Var (MM())))
2
28')
WAB (0)
e c(((A) (A)
(2 28') (Var(oTMia) (0 M(())),
4 (A)
W WABE (8)
17
28'
2
8
which completes the proof of Lemma 2.4
Here, the second last inequality comes from that M(.)
adds oblivious noise and thus Var(0 M
Var (0 M(x')).
22

---

Published as a conference paper at ICLR 2025
F MISSING PROOFS IN SECTION 2.2
F.1 PROOF OF THEOREM 2.8
The key step in proving Theorem 2.8 is applying Lemma 4.12 in Kasivishwanathan et al. siviswanathan al. (2010).
Ka
Lemma F.1 Kasiviswanathan al.
2010)) Suppose X, are real-valued random variables with
statistical difference at most e!72 1 8. Then, for all E R. at least one of E| or I[(Y - =] (1a2 - ))
The following lemma introduced & into the above lower bound.
Lemma F.2 (Dwork and Roth Dwork & Roth (2044) Fix any < E S and ó > 0. Let
A(z) R" + R. be any randomized algorithm. If is (c, diifferrrnell private, then A ()) is
1/2 (1/2, ex -
We first prove the following lemma based on Lemma F.1 which has also been claimed in Edmonds al. 2020) (Lemma 26) but without a proof.
Lemma F. Let w E R be any single query and Mxx) w 2 IR. be any data- independent mechanism that (c, d)iffferrnet private for < E = 2
and 0 s S 1, then
(E[==1))//2 2 L-8' || for for some universal constant C. Here, 8' 11/2188. Ce
Proof: We consider the mechanism M'xx) = (2 w x + 2sa. Let 8' 22110 8, then M' is
( difffeeerentlllly private. Fix any pair of neighboring dataset x and x' such that || - x'll S 1. Let X M'(x) and Y M2")') respectively. Then, it is easy to verify that
drv dxv(X, = max Pr[X e S Pr[Y E S]] S e/2 1 SCR
since M is ( d')-diiffreentiall private and thus Pr(X S] < e Pr E E + 8' for any S. Next, let X X w 252, Y Y w x 2m w (a' x) and w TT x:). Then drv (X', Y') 1/2 + 8' and thus by Lemma F.I (Lemma 4.12 in Kasiviswanathan et al. (2010)) ), we have
1 2
a}'} (w (r - (x-x2))² (1 81
E
2
E[
-
4
C²
for some universal constant C. Finally, choose the pair of neighboring datasets and x' that maximizes w (x x²) completes the proof.
Now, we ready start the proof of Theorem 2.8
Proof:
(Of Theorem 2.8 This proof can be considered complementary version of the proof in
Nikolov & Tang (2024) and Edmonds et al. (2020) since they only focus on unbiased mean estimation linear queries in to metric. We recall the reader the notation K C.. L for K, L R The
notations means that there exists a v E R such that K + v C L. We now restate Lemma 2.6 and give proof here:
and
Lemma F.4 (Restatement of Lemma 2.6 in (Nikolov & Tang 2024) Let M: + be any
randomized mechanism and A E m. be any matrix. If there exists some universal constant C such that for any input x E RD and any 0 E R., it satisfies
wo(AB
2
Var(0 M(x)]
(24)
then ABT C.s CV (EM()))
23

---

Published as a conference paper at ICLR 2025
Proof: Recall that
Em(x)= = (M - (IM( - B[M())))
is the covariance matrix of M(x). Therefore, VarlØ" Var(0TM(z)) can be written as
[[][TM((]]== v0 VOT
2 Note that [EM(( = - [V inequality, we have that
|/ul22 for any a E Bg. Therefore, by Cauchy-Schwand
|| [VM
max T VE((u max 0'v
We BT
VEE
for E = [MM(x) In the above, the equality can be achieved if 0/||0|12-
Now, for any E ABT, let K2 = {u- V.uE ABT be a convex body. Since ABT, for any 0 E 1
max oT max 10 - 00020
WEAB
This implies the following set of inequalities:
max H u max 0 uu + max
0 u max 0 min 8Ju ws wo(K,,) = (AB").
wEK. WEK.
ueK.
wEK,
Finally, the assumption in Lemma F4 is equivalent to the following: for any 0 R=
emax
TT max A
WEF
WEK,
Since both E = 1/EM2) (z)
BT and K, = ABT - (for some u E ABT) contain zero vector, we have K. S Cov B. This completes the proof of Lemma F.4 (and Lemma 2.6
In the view of Lemma F4 we next show that for any direction E R" VVrl M(x) > AAA (0) long as M is differrerrrr private.
Lemma F.5 Fix any 0 < 2. 0 1 and a query matrix A Rmxn Let C 0 be some universal constant. If M()) is an additive noise mechanism such that M(x) = Ax + 2 for any dataset E R and M(-) preserves (e, diffferrrtt privacy, then for any R and any direction
0 E IR," let 8' 2/2-16 6, we have
1 1-8
v VarlOT M(x))
Var))
N
w WAB (8).
Ce
Proof: [Proof Of Lemma F.5
Given any vector E Rm, recall that the width convex body
K 12 with respect to 0 is defined as
wk (8) = max 0
min 0 mEK
x
z K
in Definition A.9 then the variance of the one-dimensional marginal M(x) cannot be very small terms of WAB) Unlike Nikolov & Tang (2024), since focus the additive noise mechanisms, consider Lemma F.3 relating to the lower bound for such mechanisms.
In this LEmma, aim to show that if M(x) preserves (e, ddddffferelt privacy,
trying the give the lower bound of the variance of one- dimensional marginal T M(xx,, and 0 M(x) = T Ar + T By the post-processing property, @ (x) also preserves (c, diffffrrenti privacy since M(x:) is e-differentially private. Thus, by
Fix any / Rdd. We remark that
Lemma F3
(1 (1-8)22
(1
8')2
[0 =)]]] = Varl0 M(x)) 2
||00 2
max 10T A(x - x²) (25)
e2
I
S1
24

---

Published as a conference paper at ICLR 2025
Fix any 8 R We then show that for any 2, there always exist neighboring dataset x' such that 10t A(x - +x)| can be lower bounded by WAB, (0)/2. This gives a lower bound of [(TT2)] =)²].
The construction closely follows Nikolov & Tang 2024) and state the construction here for completeness.
Consider mapping IR R from ABT Bf such that for any ABT, Af(e). Given any 0 E Rmm, let w be the vector ABA that maximizes 0 w. Then, we can choose x4 such that (x, 24, is pair of neighboring datasets such that x'4 (ww). In this case,
0 A(x x44) - 0 Af(w) 0 BEABT
max 0Fv.
Similarly, for any we can also find another pair of neighboring datasets a and x'_ such that
0 A(r - -'-)-
max eEABT
-0 v
min wEABT
0e..
Thus, have
10 A( - 2441+ A07A(x +')1
A(x
max 0
+
min Q
"EART
"EABT
max DEA
0Tu
v
min .EABT
0 2 WAB (0).
In particular, this implies that, for any 0 E R and any a E R", there exists an x' E Rd neighboring to x such that
WABC (0)
0 ATA(2 r')1
where wk( = max
min v TO. oeK
(26)
2
"EK
Combining eq.
25 and eq.
26
we get
(1
8))
Varl0' M[x)]
2
max
A(x A - x²)1
g2
||x-z' $1
(1 8)
WABT (0)
A(x - x²) 2 2 (1 8¹)2
for any 0 E R
We now proceed to complete the proof of Theorem 2.8 As consequence of Lemma F.4 and Lemma
FS
by setting W = CE EEM(z)
that for any (e, diffferreett private algorithm M and
P 2, there are
(VrD)((WWT) AABT C... W
Ca p/2 t/22 (EM(z)) z
inf
W Wermxm
(A)..
Then, by Lemma
2.7 and Lemma 2.2 have
(E [[I((x) -
-aro))-A11113 Ar 1/8
1 1-
Ce (r//tr//(EMM())
(1 (A)Ap(A)
(1 (1- (1)8))))(A)
>
Ce
Ce
which completes the proof of Theorem 2.8
F.2 PROOF OF LEMMA 2.5
Suppose A has linearly independent rows, then for any non-zero 1 e Rm 0T must have at least one non-zero elements since @T A would be linear combinations of rows of A. Let the non-zero element be (A A); > 0. Then
<(A) min 0T 0=
max @TAz. =EBB
Az
min 0 Ax B
2
2
A)2
On the other hand, if A has linearly dependent rows, then there will be a Ø E RR" such that ØT A = and thus x(A). Intuitively, such A maps By to lower dimension polytope.
25

---

Published as a conference paper at ICLR 2025
GUM
35A
Figure 1: geometric intuition of Lemma 2.14
G MISSING PROOFS FROM SECTION 2.4
G.1 PROOF OF LEMMA 2.14
Proof: We first show that k( ((Aprefix) 2 2. Fix any unit vector 0 = E IR", we have
max o Aprefixe [0] + 2|02 + n100ll Σ :10:1.
(27)
aalla 51
We show the minimum value eq. (27) by induction. We claim that for any S i < n, conditioned on Σj= of = a for any < a S 1, the minimum value of Σj=1510,1 is at least /c. Now, consider the new condition Σラ 03 for some <<ssL. Let = c - 0% according to the assumption, we have that
Σ 110 (i 1)10+11 Vc 6 + (i 11
Consider the function fvy y²- (i + 1)y for < < 1 and S y S Vo. We have Af dy Ve-v² +i+1. Clearly for any Z 1, there exists a co Vesuch that f(y monotonically increasing in (0, and monotonically decreasing in (co. Vc). Thus, f(y) 2 min(f()) 2 Ve. That is,
Σ 510,1 (i 11+))0mmm 2 Ve.
1=1
Since e can be any value in (0, 1] and 10 = 1 07 1, by induction, for any unit vector 0 E R"
Aprefix
0 > 1.
With a symmetric argument, we have that for the same vector 8,
n
min 0J A'reffii: ||l|SS1
Σ 2100 5
Which implies that x<(Aprefi) 2 2. On the other hand, Let Ø = = (1,0,...,0) then it is easy to that W A3 (0) 2. Thus, x² x(Aprefix) 2.
Figure T also gives a geometric explanation of the most "narrow" width of AB when n 2. In the following diagram, + (1, Apretix B2 and (-1,-1) Aprefix B2.
26

---

Published as a conference paper at ICLR 2025
G.2 PROOF OF THEOREM 2.12
We show two factorizations of the counting matrix Aprefix that works across all p-norm for constant p. If we the factorization of Aprefix in Fichtenberger et al. (2023) or Henzinger & Upadhyay (2025). We here discuss Fichtenberger et al. (2023) for its simplicity. To recall their result, they
construct matrices L and such that LR= Aprefix and
{ f(ii-) - 5)
i2j
[ x f(k f(k- -1
k k
[ = A[i,j]
where f(k) =
0
i i<j'
1
==
By noting that f(k) is the Wallis' formula, we know that f(k) S
- Vsk
This implies that
T Σ
1
|| 1-
Ri,11
1) s++
Olog((n)
1)
1=1
1
1=2
Similarly,
1/8 =0
)mm)
1/1)
(LLT) =
Σ (114
Σ
logh/((())
/lg((n)
That is, 7(p) (Apretix) = O(n log(n)). Then, Theorem 2.12 follows using Theorem D.1
27


Reviews:
[{"review_id": "x8LOHWlI8C", "reviewer": "Reviewer_Qtjr", "summary": "This paper studies the so-called \"factorization mechanism\" for answering linear queries privately. To recap, a workload of $n$ linear queries over a domain of size $m$ can be described by a matrix $A: [\\pm 1]^{n\\times m}$. The private query releasing algorithm asks to estimate $Ax$ while preventing the privacy of $x$ w.r.t. any adjacent $x'$ s.t. $\\|x-x'\\|_1 <= 1$.\n\nThe standard approach is to publish $Ax + N(0, sigma^2)$ where the Gaussian noise is calibrated to the sensitivity of $A$. The factorization mechanism tries to improve over this by writing $A = L R$ and publish $L ( Rx + N(0, (\\sigma')^2))$ where $\\sigma'$ is calibrated to the sensitivity of $R$ only.\n\nThere is a lot of work studying the power and limitations of the factorization mechanism, trying to argue it is the \"optimal\" mechanism for this task. Generally, the theme along this line of research is to fix an arbitrary algorithm $\\mathcal{A}$ (not necessarily following the paradigm above), and let $\\mathcal{B}$ be the optimal factorization mechanism (following the approach above with an optimal $L,R$). Then, argue that for some error metric $err$, one has $err(\\mathcal{A}) \\preceq err(\\mathcal{B}))$ up to insignificant factors. The optimality of the factorization mechanism has been established for $\\ell_2^2$-error metric, the $\\ell^2_p$ metric (be a recent work [Nikolov-Tang'24]. \n\nThe current paper is a close follow-up of [Nikolov-Tang'24]. It proved that the factorization mechanism is optimal under the $\\ell^p_p$ metric, defined as\n$$\nerr = \\mathbb{E}[ \\| \\mathcal{A}(x) - Ax \\|_p^p ]\n$$\nNamely, this is the $p$-th moment of the ``error vector''. Some motivations are provided, for one, as $p$ increases from $2$ to $\\infty$, this error smoothly interpolates between the mean-squared error and the worst-case. Second, this paper argues that the error metric is more natural than $\\ell_p^2$ norm considered in prior work. \n\nThe lower bound on error, implied by the proof, depends on a mysterious factorization norm and is hard to interpret. This paper gives some applications of their general lower bound to specific query families of interest. These include prefix-sum queries and sparse parity queries (or some might prefer to call it $k$-way marginals)", "questions": "* Line 111: you argued that $\\ell_p^p$ is more natural. I somewhat agree with this point from a notational aesthetic point. However, can you comment on why the Nikolov-Tang paper was working with an \"unnatural\" measure of $\\ell_p^2$? This might make your claim more convincing.\n\n* Pargraphy beginning on Line 508: I struggled to understand why this paragraph means the Nikolov-Tang result is \"instance optimal\". Then I looked into their paper and found that their definition of instance optimality was somewhat nuanced, and your description was indeed accurate (but not super informative, IMO). I acknowledge it might be hard to convey the result of Nikolov-Tang concisely. But it might be worth rephrasing your conclusion a little bit.\n\n* Technical question: I think the current Section 2 is quite dense, and you seem to be citing Nikolov-Tang heavily. Could you maybe try to distill some of your technical punchlines and pin down the exact manipulation where you differ from prior works? I would be ok if you defer a \"complete proof sketch\" to appendix or so.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* I like the motivation of interpolating between $\\ell_2$ and $\\ell_\\infty$ error via $\\ell_p^p$.\n* The introduction of the paper is largely clear and easy to follow (perhaps with some background knowledge).", "weaknesses": "* Although the gentle introduction is clear, once it goes into a more technical part, it becomes significantly harder for me to appreciate the discussion. I take Lines 254-255 \"The main technical obstacle of Theorem 2.1 lies in ......\" as the punchline of this paper. However, I have little idea what this means in terms of technical novelty. Given my limited time reading, I hope the authors can clarify some of my questions below.\n\n* Some discussions in the introduction may be improved (see some of my questions below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2KncXuzDKT", "reviewer": "Reviewer_AQvd", "summary": "The paper investigates the asymptotic lower bounds of the expected $\\ell_p$ errors of differentially private algorithms for answering linear queries. Specifically, given a collection of linear queries represented by a query matrix $A$, it presents an asymptotic error lower bound that any differentially private algorithm will incur, expressed in terms of the matrix $A$ and privacy parameters. \n\nAfter establishing this lower bound, the paper demonstrates that the matrix mechanism can achieve it, up to logarithmic factors. Additionally, it explores two specific linear queries: the prefix sum and the parity queries, deriving their error lower bounds as special cases of the general lower bound obtained. It also presents specific matrix mechanisms that achieve asymptotic tight upper bounds (again, up to logarithmic factors).", "questions": "1. In Theorem 1.2, the distribution of $z$ does not incorporate the privacy parameter $\\epsilon$. It seems that something is missing here.\n2. In the next paragraph, change “also obtain a characterization of err() that is tight up to log factors” to “also obtain an err() that is tight up to log factors.”\n3. Why is Theorem 1.3 included in the introduction? It appears disconnected from the surrounding discussion. For instance, do you use Theorem 1.3 to prove the lower bound of the prefix sum later in the paper?\n4. Line 113: Change $v_1^p + \\ldots + v_m^p$ to $|v_1|^p + \\ldots + |v_m|^p$.\n5. In line 113, why doesn’t the approach of Nikolov & Tang explain the additive noise mechanism? Is it because the additive noise mechanism might not be unbiased?\n6. Is it common to encounter biased additive noise mechanisms? Would it be challenging to derive a lower bound for the biased case by reducing it to the unbiased one, using techniques similar to those presented in Lemma 2.3?\n7. Could you elaborate a bit more on the term “symmetry” in line 128? What does it signify in this context? Also, in line 130, clarify “the mathematical object the sequence captures…”\n8. Line 286: Change “the measure of the new distribution” to “the new distribution.”", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The problem addressed is of fundamental importance.\n2. The paper successfully derives asymptotic lower bounds for matrix mechanisms under $\\ell_p$ error.\n3. It demonstrates sophisticated applications of existing techniques.", "weaknesses": "1. The paper demonstrates that the matrix mechanism is asymptotically optimal, rather than instance optimal, for the error metric considered.\n2. The writing is generally good, but there are parts that lack consistency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kdvsOwgDPV", "reviewer": "Reviewer_BwNF", "summary": "This paper studies the $\\ell_p^p$-error of privately answering linear queries. The authors show a lower bound on the error in terms of a certain factorization norm ($\\gamma_{(p)}(A)$), suggesting that the classical matrix factorization mechanism is optimal up to logarithmic factors. Based on this main result, they also provide an easy-to-use lower bound that depends on the Schatten-1 norm of the workload matrix. They then apply their results to two kinds of queries: prefix-sum and parity, and obtain nearly tight bounds for both tasks.", "questions": "I do not understand what the workload matrix for parity queries is like. Can you provide a small example?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Linear query release is a fundamental problem in private data analysis. This article characterizes the error of this task with respect to $\\ell_p^p$-metric, contributing to a deeper understanding of the role of differential privacy.\n2. The writing is clear. Also, the technical details are well-organized and easy to follow.", "weaknesses": "1. It appears that the upper bound and lower bound only match in the high privacy regime. In the low privacy regime, where $\\varepsilon = \\Omega(1)$, the presented upper bound cannot match the lower bound.\n2. When $p$ is not a constant, the proposed bounds may not be tight for certain regimes of the parameters. For example, when $n = p$, the upper bound in Theorem 1.5 is $O(\\log^{1.5} (p))$ while the lower bound is $\\Omega(\\log (p))$.\n\nHowever, I think both of the above are not serious issues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AJY4OB93vi", "reviewer": "Reviewer_Gx7F", "summary": "The paper studies worst-case lower bounds for answering linear queries under add-remove approximate differential privacy for an $\\ell_p^p$ error metric. In contrast, past work derived instance-specific lower bounds for unbiased mechanisms under substitution approximation differential privacy in terms of $\\ell_p^2$ metrics. Its main result is a lower bound  that is characterized by the factorization norm of the query matrix (Theorem 1.4). This lower bound is almost tight with an upper bound that is also provided using, as a long line of recent work has done, the matrix mechanism (Theorem D.1). The paper also specializes this result to the specific problems of prefix sum and parity by explicitly analyzing the problems' factorization norms (Theorem 1.5 and 1.6).", "questions": "Overall, I think expending more effort trying to explain why the directions of novelty add up to an \"interesting\" result could go a long way for this paper, but as is the qualitative improvement over known results feels weak. Some specifics:\n\n1) The paper repeatedly emphasizes the distinction between add-remove and substitution, but this is described in a confusing way. Throughout, the database is presented as a vector in $\\mathbb{R}^n$ -- what is $n$ here? Is it the size of the data universe, or the number of data points? Since neighboring databases both lie in $\\mathbb{R}^n$ and the paper claims to study add-remove privacy -- where I'd expect neighboring databases to literally have # data points that differ by 1 -- I expect that $n$ is the size of the data universe and $x$ is a histogram, and Appendix B.3 seems to agree. But then, I don't know why it's more natural to allow neighboring databases to have $\\|\\|x-x'\\|\\|_1 \\leq 1$, which is more like a strange \"fractional\" contribution model where a user can technically contribute $<1$ to many items. Edmonds-Nikolov-Ullman also appears to use the same neighboring notion as Nikolov-Tang, despite this paper's claim that it uses the same notion as this paper. Overall: I am confused by this bit.\n\n2) Considering general $\\ell_p$ norms typically feels to me like generalization for its own sake. The paper makes a few attempts to argue that $p \\neq 2$ is more \"natural\", but the arguments are vague. The error metrics are clearly different, but what do they meaningfully add to our understanding? I think this paper would be stronger if the authors would try to make as cogent as possible a case that generalizing $p$ actually tells us something useful.\n\n3) I have pretty much the same reaction to biased vs unbiased as I do to $p$ vs 2. I don't think anybody expected that biased mechanisms were the key to better worst-case error guarantees, so their inclusion again feels more like a technical wrinkle that necessitates different arguments than something that significantly adds to our understanding of privacy (and since it's lower bounds, I think adding to understanding matters more -- if there were new upper bounds, there would be a much simpler case that it's just a new useful thing).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "To the best of my knowledge, the claimed novelty in the paper is accurate, and it is nice to have a more complete lower bound picture for linear queries. The paper does a reasonable job of providing high-level explanations for some of its technical challenges and solutions. It is mostly easy to read with careful explanations.", "weaknesses": "To me, the paper's primary weakness is significance. Any one of the directions of novelty referenced above -- add/remove vs substitute, $\\ell_p^p$ vs $\\ell_p^2$, potentially biased vs unbiased -- feels pretty niche on its own, especially since we're only talking about lower bounds (as I think the authors would agree, the matrix mechanism upper bound is not a significant contribution here). As is, I don't think the paper convincingly argues why expanding known results in these directions is worth doing, beyond it just being something we could do. Since these are lower bounds, I want a stronger argument that these results somehow add \"morally\" to our understanding of private mechanisms -- and I'm not sure one exists (but, see questions below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)