Optimality of Matrix Mechanism on $\ell_p^p$-metric

We thank the reviewer for the comments and suggestions.

About the privacy notion

We would like to emphasize that the main distinction between substitution model and add/remove model is that they are related to different sensitivity polytope that are not directly comparable, and thus we need a new lower bound (see also the discussion in Appendix B.3). As the reviewer pointed out, $n$ is the size of data universe, and the number of data points is $\lVert x\rVert_1$. We define the privacy notion using $\lVert x - x'\rVert_1$ not to emphasize that we permit "fractional" contributions from multiple users (as the reviewer mentioned), but rather to just encompass the add/remove model. In this model, $\lVert x\rVert_1$ and $\lVert x'\rVert_1$ do not need to be equal because we allow the addition or removal of a single user. We do not intend to say that allowing fractional changes is more natural, we will make this point more clear.

"Edmonds-Nikolov-Ullman also appears to use the same neighboring notion as Nikolov-Tang"

Edmonds-Nikolov-Ullman uses the same privacy notion as ours, as it does not require $\lVert x\rVert_1$ and $\lVert x'\rVert_1$ to be equal (see also page 26, specifically the discussion between Lemma 26 and Lemma 27 in the ENU paper). Moreover, we have confirmed with the authors of NT24 in personal communication that they consider the substitution model, in which the number of users, $\lVert x\rVert_1$, is fixed.

"The error metrics are clearly different, but what do they meaningfully add to our understanding?"

We believe studying $\ell_p$ error contributes to our understanding in the following aspects:

1. Studying the $\ell_p$ error for larger $p$ provides a characterization of the distribution of the error. To elaborate, let $v_i$ be the difference between the $i$-th coordinate of the output and the ground truth, then the error we studied is just $\mathbb{E}[|v_1|^p + \cdots + |v_n|^p]$. For any additive noise mechanism that adds noise from identical distribution, by the linearity of expectation, our lower bounds provides a lower bound for the $p$-th moment $\mathbb{E}[|v_i|^p]$ of the noise distribution. Therefore, obtaining the lower bound for various values of $p$ offers a more precise characterization of the "optimal" distribution, as it is well-known that the $p$-th moment for $p\geq 2$ provides substantial information about the distribution more than just $\mathbb{E}[|v_i|^2]$, which is implied by the squared error.

2. We note that our lower bound on $\ell_p$ error is tight, as it is accompanied with a matching upper bound. So it interpolates the curve of the "correct" magnitude of the error. For example, in the private prefix sum problem, we show that the tight error is $\tilde{\Theta}(n^{1/p})$, bridging the gap between the known bounds for squared error ($\tilde{\Theta}(\sqrt{n})$) and worst-case error ($\text{polylog}(n)$).

3. It serves as a unifying lens to understand several prior works including [ENU20], [ALNP24] and [NT24] since both [NT24] and [ALNP24] study the similar $\ell_p$ error.

[ENU20] The Power of Factorization Mechanisms in Local and Central Differential Privacy

[NT24] General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation

[ALNP24] PLAN: Variance-Aware Private Mean Estimation

"I don't think anybody expected that biased mechanisms were the key to better worst-case error guarantees"

In our experience, the best possible worst-case error is usually achieved by biased mechanism, so we are not sure if we understand the reviewer's comment correctly (please correct us if not). In the context of linear query, a line of works have been working on answering the sizes of all cuts privately in a graph, which can be considered as a special case of linear query whose workload matrix is the edge-adjacency matrix in terms of all $(S,T)$ cut. The optimal private algorithm on this problems that gives $\tilde{O}(\sqrt{mn})$ worst-case additive error is achieved by private mirror descent ([EKKL20]), which is a biased mechanism as it computes the private gradient by multiplicative Gaussian noise. Similarly, private multiplicative weights update (MWU) usually gives the optimal worst-case error for other well-known linear queries [Vad16] and it is also a biased mechanism because of its weighing of the hypothesize (and private) dataset. Apart from linear queries, exponential mechanism is usually considered as the optimal algorithm for many private problems, while discrete exponential mechanisms are typically biased (for example, consider the randomized response mechanism).

[EKKL20] Differentially Private Release of Synthetic Graphs

[Vad16] The Complexity of Differential Privacy

We thank the reviewer for the comments and suggestions.

"I do not understand what the workload matrix for parity queries is like. "

Depending on which parity queries are made, the workload matrix would consist of a subset of rows of a normalized $n \times n$ Hadamard matrix.

We thank the reviewer for the comments and suggestions.

"In Theorem 1.2, the distribution of $z$ does not incorporate the privacy parameter".

Thanks for catching this typo. We missed the privacy parameters here. The correct distribution should be $z\in \mathcal{N}(0, \lVert R \rVert_{1\rightarrow 2}^2 \cdot \sigma^2 \cdot \mathbb{I}_{k\times k})$ where $\sigma^2 = O(\frac{\log(1/\delta)}{\varepsilon^2})$.

"Why is Theorem 1.3 included in the introduction?"

Theorem 1.3 is an easy-to-use lower bound. Since to apply Theorem 1.3, one only needs to compute the Schatten-1 norm (i.e., the sum of singular values) of the workload matrix, which is much easier than computing the $\gamma_{(p)}$ norm in the main theorem. Also, Theorem 1.3 is enough to derive the tight and explicit lower bound for prefix sum. We will make this point more clear.

"why doesn’t the approach of Nikolov & Tang explain the additive noise mechanism?"

For additive noise mechanisms, bounding the $\ell_p^p$ error is equivalent to giving a lower bound of $\mathbb{E}[|v_1|^p + \cdots +|v_n|^p]$ where $\{v_i\} (i\in [n])$ are noises. Suppose the algorithm adds identically distributed noise; by the linearity of expectation, we are able to characterize the $p$-th moment $\mathbb{E}[|v_i|^p]$ of the noise distribution. It is well-known that the $p$-th moment provides substantial information about the distribution. We will make this point more clear.

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

We believe Lemma 2.3 is originally intended for making such reductions. We certainly do not rule out other possible ways for reduction, but we would like to emphasize that a black-box reduction from biased mechanism to unbiased mechanism in [NT24] does not give our result, as we use different privacy notion, which implies different choices of the sensitivity polytope (see also the discussions in Appendix B.3).

"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…"

By symmetry, here we mean that all the powers and roots taken on the error vector is the same. That is, it is of the form $(|v_1|_p+ \cdots + |v_n|^p)$ or $(|v_1|_p+ \cdots + |v_n|^p)^{1/p}$ instead of one being $p$ and the other being $2$.

When we consider $\ell_p$ norm, then it nicely interpolates between two popular norms studied in the literature, the Euclidean norm and max-norm. This is aligned with the Riesz's motivation to study the $\ell_p$ norm (also see footnote 1). For a given vector (or its distribution), computing its $\ell_p$ norm forms a sequence that converges to $\ell_\infty$ at one end and $\ell_2$ at the other. The behavior of this sequence is better understood than the metric considered in Nikolov-Tang, which also has the same limits at the either end, but behavior in the intermediate point is not very clear.

We thank the reviewer for the comments and suggestions.

"can you comment on why the Nikolov-Tang paper was working with an "unnatural" measure of $\ell_2^p$ norm?"

From a technical perspective, [NT24] establishes a lower bound by first lower bounding the minimum variance of noise in the Euclidean geometry required to ensure privacy, where the $\ell_p^2$ lower bound is more straightforward to establish. We extend this analysis to the $\ell_p$ geometry. Through personal communication, the authors of [NT24] confirmed to us that they did not consider the $\ell_p^p$ metric considered in this paper (also see the footnote in page 2).

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

We would love to discuss the difference between instance optimality and worst-case optimality more formally in the conclusion part.

"Could you maybe try to distill some of your technical punchlines and pin down the exact manipulation where you differ from prior works?"

Due to space constraints, we had to defer the detail discussion of the difference in our techniques and previous works to Appendix B.3. For the reviewer’s convenience, we also provide a high-level summary here. Please let us know if further clarification is needed.

1. A different privacy notion necessitates the choice of a different sensitivity polytope to exactly capture the geometry of error, and to relate to the factorization norm of the workload matrix itself.

We first note that [NT24] does not imply a lower bound for the usual setting of linear queries due to different privacy notions. We have confirmed with the authors of Nikolov-Tang that if using the same privacy notion as in our setting, a lot of results in their paper need to be modified. To elaborate, [NT24] gives a bound for mean estimation in the substitution model of privacy. Using the histogram notation, let $h \in \mathbb{R}^{|\mathcal{X}|}$ (where $|\mathcal{X}| = n$ in the notation of our paper) be the histogram of the dataset, then the substitution DP model corresponds to the neighboring notion where $\lVert h - h'\rVert_1 \leq 2$ and $\sum_{x \in \mathcal{X}} (h_x - h’_x) = 0$.

In contrast, our privacy notion for linear queries requires $\lVert h - h'\rVert_1 = O(1)$, representing a natural $\ell_1$ sensitivity, the same as [BDKT12], [ENU20] etc. Now answering linear queries, $Q$ over data $X = (x_1, x_2, \cdots, x_k)$, $Q(X)$ is equivalent to doing mean estimation in the polytope $K_Q = \{Q(x):x\in \mathcal{X}\}$. Even if we restrict our discussion to the substitution model, the lower bound for mean estimation from Nikolov and Tang would be in terms of $\Gamma_p(K_Q)$. In contrast, we get a bound in terms of the factorization norms 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 $\Gamma_p(K_Q)$ but a substantially larger factorization norm of the workload matrix $A$ (we are happy to include an example in our paper as well). Therefore, a lower bound in terms of $\Gamma_p(K_Q)$ does not imply a lower bound in terms of the factorization norm $\gamma_{(p)}(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. This is especially important since we would like to give explicit lower bounds for explicit linear query families, and tight bounds are only possible with the right choice for "sensitivity polytope".

2. Removing unbiasedness assumption via the Bhaskar et al. reduction.

Then, to remove the unbiasedness assumption, we chose a different path compared to [NT24] by first establishing a lower bound against data-oblivious mechanisms, where the ideas on handling the bias is summarized in Appendix B.3 (starting at line 887). We then follow the reduction of Bhaskar et al. to obtain lower bounds for general mechanisms.

Finally, a side benefit of our approach is that the width of the sensitivity polytope along the narrowest direction, denoted by $\kappa$ in our paper and $w_0$ in [NT24], plays a different role in our lower bound than theirs. Unlike [NT24], our lower bound does not depend on $\kappa$ and it is crucial for our explicit lower bounds for the two classes of linear queries we discuss later.