On Differential Privacy for Adaptively Solving Search Problems via Sketching

We thank the reviewer for their question about prior work, which we address below:

1. Prior works using differential privacy for adaptivity focus on numerical estimates [Hassidim et al., 2022; Beimel et al., 2022; Song et al., 2023; Cherapanamjeri et al., 2023]. Our work instead tackles the search problem—returning a point using an adaptive DP data structure. While differentially private heavy hitter algorithms (e.g., [Chadha et al., 2023]) relate to private search, they lack adaptivity. To our knowledge, this is the first work combining DP with adaptive search.

2. Because of this, prior adaptive search methods either (a) build $T$ data structures (one per query), or (b) use a net argument over the space, requiring $\widetilde{O}(d)$ structures.

Below we compare our method to these baselines for ANN and regression. We omit $\widetilde{O}(\cdot)$ for clarity.

Approximate Nearest Neighbor (ANN)

For $T$ adaptive queries/updates, the exact method scans the dataset. If $T \leq d$, we outperform $T$-copies when $s \leq \min\\{\sqrt{T}, n\\}$; if $d \leq T$, we outperform $d$-copies when $s \leq \min\\{\frac{d}{\sqrt{T}}, n\\}$.

Regression

Let $U \in \mathbb{R}^{n \times d}$ and $b \in \mathbb{R}^n$, with goal to compute $x$ minimizing $\\|Ux - b\\|_2$ up to $(1+\alpha)$. Each step updates $U$, $b$ via $v_t$; $\kappa$ bounds $U$'s condition number.

We outperform $T$-copies when $\kappa^2 \leq \sqrt{T/d}$, and $nd$-copies when $\kappa^2 \leq n \sqrt{d/T}$—conditions often met in practice.

Regression with Sparse Label Updates

If only $b$ is updated and each $v_t$ changes at most $s$ entries, $\kappa^2$ dependence can be reduced to polylogarithmic.

Only $n$ copies are needed. Our method is faster when $T \leq n$ and $d \leq T$, or when $n \leq T$ and $\sqrt{T d} \leq n$. Since $T$ is user-chosen (rebuilding occurs every $T$ queries), trade-offs can be tuned (see Claims D.16–D.17).

Summary:
Our method leverages DP with advanced composition, achieving $\widetilde{O}(T)$ scaling and improved space, preprocessing, query, and update complexity. These advantages are especially notable when $T$ is large, or when sparsity $s$ and condition number $\kappa$ are favorable. We will ensure these comparisons are clearly included in the revision.

We thank you for your very helpful comments. We would also like to address your questions and comments regarding differential privacy.

Let us start with a high-level overview of the framework, first introduced in [Hassidim et al., 2022; Beimel et al., 2022]. The rough idea is to treat the random seeds used by data structures as the database for which we want to preserve privacy. In the simplest setting, to achieve a target privacy level $\epsilon$, one might need to aggregate the responses of $T$ data structures in a differentially private manner. However, by the advanced composition theorem, the same level of privacy in terms of $\epsilon$ can be achieved using only $\widetilde{O}(\sqrt{T})$ independent outputs—at the cost of moving from pure DP to approximate DP with $\delta > 0$. As long as $\delta$ is small, the approximation is acceptable.

Responses to Specific Questions

Q: Can the Gaussian mechanism be used for $(\epsilon, \delta)$-DP? In that case, how does it affect the final guarantees?

A: Yes, the Gaussian mechanism is valid for achieving $(\epsilon, \delta)$-DP, provided that $\delta$ is not too large. Suppose we want the data structure to succeed with probability at least $1 - \beta$. Let $\delta_{\text{final}}$ denote the total privacy loss, composed of:

• $\delta_{\text{Gaussian}}$: from the Gaussian mechanism
• $\delta_{\text{advanced}}$: from advanced composition

Then:

In our original setting, we set $\delta_{\text{advanced}} = \beta / 100$ using an appropriate $\epsilon$. To use the Gaussian mechanism instead, we may set $\delta_{\text{Gaussian}} = \frac{\beta}{200T}$ and reduce $\delta_{\text{advanced}}$ to $\beta/200$. This still yields $\delta_{\text{final}} = \beta / 100$, matching the Laplace mechanism’s privacy loss.

We chose the Laplace mechanism for conceptual simplicity and because the task is essentially a counting problem, where Laplace noise is more natural.

Q: In DP, privacy loss accumulates with repeated queries, so mechanisms are often shut down after a limit. Does your adaptive data structure exhibit this behavior?

A: Yes, the adaptive data structure’s ability to handle $T$ queries hinges on privacy composition. Using the advanced composition theorem, we guarantee $(\epsilon, \delta)$-DP across $T$ interactions by using $\widetilde{O}(T)$ resources (e.g., data structure copies or random seeds), rather than $O(T)$.

However, this requires $T$ to be fixed in advance. For indefinite querying, a standard approach is to rebuild the data structure periodically after every $T$ queries. This permits optimization of $T$ to balance space, amortized preprocessing time, and query/update efficiency.

Additional Comments

It would be better to discuss more on differential privacy, such as composition and loss accumulation.

A: Thank you for pointing this out. We will ensure that the final version includes a more detailed discussion on differential privacy, particularly covering composition theorems and cumulative privacy loss (please refer to our high-level overview and answers regarding loss accumulation above).

Including figures and diagrams would be helpful for explaining the techniques.

A: We appreciate the suggestion. We agree that visualizations—especially for illustrating how the sparse argmax mechanism is applied in our ANN algorithm—would enhance clarity and intuitively explain why our algorithm is both correct and efficient. We will include appropriate figures and diagrams to better illustrate the framework in the revision.

We thank you for your very helpful comments and we would like to address your comments on the quadratic dependence on $\kappa$ and linear dependence on $T$ for the alternative.

For the $\kappa^2$ dependence, the main reason is that by using the $\ell_\infty$ guarantee together with the standard relative error guarantee of sketched regression, we can show that the regression cost of the private median estimator $g$ satisfies $\\|Ug-b\\|_2 \leq (1+\kappa \alpha’)\\|Ux^*-b\\|_2$. Hence, to account for the blowup in condition number, we need to scale down the approximation factor by $\kappa$. Since the sketching dimension depends inverse quadratically on the approximation factor, we have a $\kappa^2$ dependence in the runtime. One could argue that known sketching-based methods based on the following framework need to incur such a dependence: our algorithm estimates each coordinate to high precision, and this inevitably incurs a dependence on the condition number for the error, and the sketching dimension in turn depends quadratically on the condition number. When there are no updates to $U$, we could use an iterative method instead to remove the polynomial condition number dependence. It is an interesting open question to develop an iterative algorithm that can remove the dependence on the condition number while also supporting updates to $U$. Therefore, while the $\kappa^2$ dependence is a consequence of our current sketching approach for worst-case guarantees, we believe the overall framework offers significant advantages, and reducing this dependence under updates is an important avenue for future work.

The alternative method based on the bounded path technique can be treated as a refinement to the method of using a fresh sketch for each update and query. Specifically, the algorithm depends on $\log |{\cal P}|$, and $|{\cal P}|$ can be naively upper bounded by $(n\kappa)^{dT}$, making it less appealing. However, we note that $|{\cal P}|$ is a more fine-grained parameter that could capture the structure of the input, e.g., if only entry changes between queries are allowed, then the upper bound reduces to $(nd)^T$. If the updates are infrequent, e.g., only $\sqrt T$ updates are performed, then the bound becomes $(nd)^{\sqrt T}$. Hence, while the alternative is no more efficient in the most general sense, it provides more fine-grained control and a speedup in situations for which the instance has extra structure.

We appreciate your encouraging and helpful comments. Regarding your comments:

• Line 40:
  We will clarify this sentence. Our intention is to express both ANN and regression in a unified way, and we will revise it to clearly explain the query and update models in each problem.

• Line 94:
  The assumption states that the predicate function $f_{v_t}$ is sparse, and we define the predicate as the intersection of the dataset $U$ and the $cr$-ball around $v_t$—that is, all points in $U$ within distance $cr$ of the query. We acknowledge that the current formulation does not make this connection explicit and will revise it for clarity.

• Line 258:
  We will fix the missing index $j$.