betaFeedback

WorksComputer Science

Private Online Release of Adaptive Linear Queries

Abstract

In this paper we study answering counting and other linear queries online under differential privacy constraints. Recent work by Nikolov, Tang, and Ullman [STOC 2026] gave the first online algorithm that answers obliviously chosen online linear queries privately, and achieves poly-logarithmic competitiveness against an optimal offline factorization mechanism. This also implied poly-logarithmic competitiveness against arbitrary private offline mechanisms when the private dataset is large enough. The error guarantees of their algorithm, however, can fail when the queries are adaptive. We give a new algorithm that also achieves poly-logarithmic competitiveness, while being able to handle adaptively chosen queries. This implies that there is no large separation between the optimal error bounds for privately answering, respectively, offline linear queries, obliviously chosen online linear queries, and adaptively chosen online linear queries. Our algorithm combines the online factorization approach from prior work with a novel layered Euclidean iterative database construction, presenting a new way to use factorization in private algorithms. We also give a lower bound that shows that some poly-logarithmic factor in the competitive ratio is unavoidable. Our lower bound first shows that any interactive private mechanism implies a deterministic online factorization algorithm, and then gives a new lower bound for the competitive ratio of any deterministic online factorization algorithm.

Introduction

In the 20 years since it was introduced, differential privacy [12] has become the golden standard for analyzing data with rigorous individual privacy guarantees. Roughly, differential privacy requires that the output of the data analysis mechanism on a pair of neighboring datasets be similar. In this paper, as is standard, we assume that a dataset is a sequence of data points from some finite universe U\mathcal{U}, and say XX and X′X' are neighboring if one can obtain X′X' from XX by adding or removing one data point. This is the add/remove, or unbounded notion of neighborhood. The formal definition of differential privacy is as follows.

Definition 1.1 (Differential privacy [12]). A randomized mechanism MM is (ε,δ)(\varepsilon,\delta)-differentially private if, for any pair of neighboring datasets XX, X′X', and every measurable set SS of outputs,

Pr⁡[M(X)∈S]≤eεPr⁡[M(X′)∈S]+δ.\Pr[M(X) \in S] \leq e^{\varepsilon}\Pr[M(X') \in S] + \delta.

Absent privacy constraints, data analysts often interact repeatedly with their data, by first doing exploratory analysis, before settling on a final collection of statistical analyses. Differential privacy doesn’t allow direct data access, and, instead, the analyst must interact with the data via the private mechanism. To offer an interactive workflow similar to the non-private setting, the mechanism should itself be interactive, and be able to answer the analyst’s queries immediately, before new queries are specified based on the answers to the initial ones. This motivates the online/interactive private query release problem: design mechanisms that receive a new query at each time step, output a reasonably accurate answer to it, and ensure that the entire interaction transcript is differentially private.

In the interactive query release problem, the queries could be obliviously chosen, i.e., unknown to the mechanism but fixed ahead of time, or adaptive, where new queries depend on the transcript so far. Understanding the adaptive queries case is of particular practical importance. For example, suppose we have a dataset of demographic statistics. A data analyst may first want to understand correlations between ethnicity and a certain income level, and only after seeing a high correlation with one of the ethnicities, they ask more queries that may reveal confounding factors. These queries are adaptively chosen, so the data releasing mechanism must have both privacy and accuracy guarantees against adaptively chosen queries. Another advantage of interactive mechanisms that can accurately answer adaptively chosen queries is that other algorithms can use them as subroutines. As a toy example, suppose we have a dataset of ages of a group of people, and the type of query allowed is to count the number of people inside an age range. We can then use binary search to find an approximate median age for the group using adaptively chosen range queries. Adaptivity is important since binary search chooses its next query based on answers to the previous ones.

Overall, these examples show the importance of adaptiveness of queries for private interactive data release. Alongside the motivation from private data analysis, asking adaptive queries poses statistical validity questions even when privacy is not a concern. In particular, adaptively analyzing a fixed dataset may lead to results that overfit to the data and do not generalize to the underlying population [16]. Prior work [10, 4] has shown that differential privacy can be used as a tool to ensure validity of adaptive data analysis: an analyst that interacts with the data via a differentially private mechanism, even adaptively, cannot overfit to the dataset. Slightly more precisely, if an interactive mechanism answers adaptively chosen queries privately, and accurately with respect to the dataset, then its answers are also accurate with respect to the population. This provides further motivation for the interactive private query release problem in the adaptive setting.

Despite the substantial motivation for developing interactive private mechanisms that can accurately answer queries posed by an adaptive analyst, optimal mechanisms for this problem are poorly understood, even for the fundamental example of counting queries, i.e., queries of the type, “How many data points satisfy a given property?” By contrast, there is a substantial body of work in differential privacy that has identified approximately optimal mechanisms for answering offline counting queries, and, more generally, linear queries (see the definition below) [19 BDKT12, NTZ16, 1, 15]. These mechanisms need all queries to be specified ahead of time, run in time polynomial in the dataset size, universe size, and number of queries, and achieve error within poly-logarithmic factors of the optimal error achievable by any differentially private mechanism. Our goal in this paper is to achieve similar guarantees in the interactive setting with adaptive queries.

Linear Queries

We study private algorithms that take as input a dataset X∈UnX \in\mathcal{U}^{n}, where n∈Nn \in\mathbb{N} and the data universe U\mathcal{U} has finite size NN. Note that we adopt the add/remove definition of neighboring datasets, so the dataset size nn is not public. We consider linear queries, defined below, which characterize a broad class of queries of interest in applications, including all counting queries.

Definition 1.2 (Linear Query). A linear query is specified by a function q:U→Rq : \mathcal{U} \to\mathbb{R}. For a dataset X=(x1,…,xn)∈UnX = (x_1, \ldots, x_n) \in\mathcal{U}^{n}, its answer is

q(X):=∑i=1nq(xi).q(X) := \sum_{i=1}^{n} q(x_i).

Counting queries are the special case when qq only takes values 0 or 1. Linear queries have been studied extensively under differential privacy, and many real world data releases, such as the 2020 US Census [DLS^{+}17], are of this form. Even more restricted classes of counting queries, like marginal queries [BCD^{+}07, LNT26, XHT^{+}26], have received significant attention.

It is convenient to represent the dataset as a vector, known in the literature as the histogram representation.

Definition 1.3 (Histogram). The histogram of a dataset X∈U∗X \in\mathcal{U}^{*} is the vector h∈Z≥0Uh \in\mathbb{Z}_{\geq0}^{\mathcal{U}}, where hxh_x counts the number of occurrences of xx in XX, i.e., hx:=∣{i:xi=x}∣h_x := |\{i : x_i = x\}| for X=(x1,…,xn)X = (x_1, \ldots, x_n).

A linear query can then be viewed as the inner product of a query row vector qtq_t and the histogram hh corresponding to the dataset, and the answer to a workload of linear queries can be written as a matrix-vector product of a matrix representing the queries and the histogram, as shown below.

Definition 1.4 (Query Matrix). For a workload of linear queries q1,…,qm:U→Rq_1, \ldots, q_m : \mathcal{U} \to\mathbb{R}, the query matrix Q∈Rm×UQ \in\mathbb{R}^{m \times\mathcal{U}} of the workload is defined by Qi,u=qi(u)Q_{i,u} = q_i(u). The answer to the workload is

Q(X):=[q1(X)⋮qm(X)]=Qh.Q(X) := \begin{bmatrix} q_1(X) \\ \vdots\\ q_m(X) \end{bmatrix} = Qh.

Note that, for any two neighboring datasets XX and X′X', the corresponding histograms satisfy ∥h−h′∥1≤1\lVert h-h'\rVert_1 \leq1. This easily implies that ∥Q(X)−Q(X′)∥2≤∥Q∥1→2\lVert Q(X) - Q(X')\rVert_2 \leq\lVert Q\rVert_{1 \to2}, where ∥Q∥1→2\lVert Q\rVert_{1 \to2} is the largest ℓ2\ell_2 norm of a column of QQ. I.e., the ℓ2\ell_2-sensitivity of QQ is ∥Q∥1→2\lVert Q\rVert_{1 \to2}.

An important, and widely used, class of private mechanisms for releasing answers to workloads of linear queries are noise-adding, also known as oblivious, mechanisms. These mechanisms output Q(X)+ZQ(X) + Z where ZZ is a noise vector from some distribution that depends on QQ but not on XX. A simple example of such a mechanism is the Gaussian noise mechanism [14], in which ZZ is a vector of independent and identically distributed (i.i.d.) Gaussians, with mean 0, and standard deviation scaled to the ℓ2\ell_2-sensitivity ∥Q∥1→2\lVert Q\rVert_{1 \to2} of QQ. Both the privacy and accuracy guarantees of this mechanism extend, in a straightforward way, to the interactive setting with adaptively chosen queries, as long as the ℓ2\ell_2-sensitivity of the queries is bounded: one just needs to add the Gaussian noise to each query answer “on the fly” as the queries arrive.

(Online) Factorization Mechanisms

Factorization mechanisms [LMH^{+}15, ENU20] provide a principled way to achieve better error than the i.i.d. Gaussian noise by adding correlated Gaussian noise. Given the query matrix QQ, one can find a factorization Q=LRQ = LR, then answer Qh+LZQh + LZ, where ZZ is again a vector of i.i.d. Gaussians, this time with standard deviation scaled proportionally to ∥R∥1→2\lVert R\rVert_{1 \to2}. The maximum noise variance over queries in the workload achieved by this mechanism is proportional to ∥L∥2→∞∥R∥1→2\lVert L\rVert_{2 \to\infty}\lVert R\rVert_{1 \to2}, where ∥L∥2→∞\lVert L\rVert_{2 \to\infty} is the maximum ℓ2\ell_2 norm of a row of LL. Optimizing the error of a factorization mechanism then corresponds to minimizing ∥L∥2→∞∥R∥1→2\lVert L\rVert_{2 \to\infty}\lVert R\rVert_{1 \to2} over all choices of LL and RR that give Q=LRQ = LR. The minimum such value is denoted γ2(Q)\gamma_2(Q), the γ2\gamma_2 norm of QQ. Together with an optimal factorization, it can be computed efficiently using convex optimization. Factorization mechanisms generalize and allow us to optimize widely used mechanisms such as the binary tree mechanism [13, 9]. It was shown by Edmonds et al. [15] that, in the offline setting, the optimal factorization mechanism is also asymptotically optimal among all noise-adding mechanisms, and, when the dataset is large enough, among all differentially private mechanisms.

Intuitively one might expect that factorization mechanisms are restricted to the offline setting, since one needs to know the whole query matrix QQ in order to find its optimal factorization Q=LRQ = LR. Counter to this intuition, it was shown in recent work by Nikolov, Tang, and Ullman [NTU26] that an approximately optimal factorization can be computed when the rows of the matrix QQ arrive online. The value of their online factorization is within a poly-logarithmic factor from the optimal offline factorization. Nikolov et al. then also showed that this online factorization can be used to answer online queries privately, similarly to how an offline factorization is used. Their mechanism is still private against adaptive queries, but its error bound breaks against carefully chosen adaptive queries. This motivates us to ask: Is there a mechanism that works for adaptively chosen queries with a similar accuracy guarantee, and, conversely, can one show a lower bound on the competitive ratio, i.e. can one actually do as well as the offline case without even losing a log factor? In this paper, we address these two problems.

Let us describe the online factorization framework of Nikolov, Tang and Ullman [NTU26].

Definition 1.5 (Online Factorization Problem). Let Q∈Rm×NQ \in\mathbb{R}^{m \times N} have rows q1,…,qmq_1,\ldots,q_m, revealed sequentially, and let QtQ_t consist of its first tt rows. The number mm is not known in advance.

Starting from the empty matrix R0R_0, an online factorization algorithm processes each arriving row qtq_t by appending additional rows to Rt−1R_{t-1} to obtain RtR_t, and producing a row vector ℓt\ell_t such that

ℓtRt=qt,∥Rt∥1→2≤1.\ell_t R_t = q_t,\qquad\lVert R_t\rVert_{1\to2} \le1.

Let LtL_t contain the rows ℓ1,…,ℓt\ell_1,\ldots,\ell_t, padded with zeros as necessary. The algorithm achieves factorization value γ\gamma on QQ if

∥Lm∥2→∞≤γ.\lVert L_m\rVert_{2\to\infty} \le\gamma.

Nikolov, Tang, and Ullman showed that there exists an online factorization algorithm that is polylogarithmically competitive against the best offline factorization at every time step.

Lemma 1.6 ([NTU26], Theorem 1.4). Fix c>0c > 0. There exists an online factorization algorithm whose factorization value on every matrix Q∈Rm×NQ \in\mathbb{R}^{m \times N} satisfies

γ=O(γ2(Q)[log⁡(γ2(Q)∥q1∥∞)]12+c(log⁡N)3).\gamma= O\left(\gamma_2(Q)\left[\log\left(\frac{\gamma_2(Q)}{\lVert q_1\rVert_\infty}\right)\right]^{\frac{1}{2}+c}(\log N)^3\right).

This algorithm first solves a semidefinite program online to obtain a factorization in which the column norms of RtR_t are bounded only on average, and then uses some classical combinatorial tricks to satisfy the stronger requirements of online factorization. In our paper, we use this algorithm as a black box.

It is straightforward to use the online factorization to privately answer online linear queries. When a new query arrives, we use the online factorization to compute ℓt\ell_t and RtR_t. We compute Rth+ZtR_t h + Z_t, where ZtZ_t is a vector of i.i.d. Gaussian noise variables, one for each row of RtR_t. We can do so by just computing answers for the new rows in RtR_t and adding Gaussian noise to them. Then we take an inner product of ℓt\ell_t and Rth+ZtR_t h + Z_t to compute an answer to qtq_t. The privacy of this mechanism holds against adaptive queries, and follows from the privacy of the Gaussian noise mechanism. It is also straightforward to prove accuracy guarantees against oblivious queries. When the queries are adaptive, however, the analyst may choose qtq_t to correlate with the noise ZtZ_t, achieving much larger error than in the oblivious setting. Thus, we need a novel way of using the online factorization when the queries are adaptive.

Our Results

In this subsection we introduce our results. We defer the formal definition of interactive algorithms, their privacy and accuracy, to § 4 - roughly, the algorithm receives query qtq_t at time step tt, outputs oto_t before receiving the next query, while keeping the entire transcript private, and every answer oto_t accurate.

Our first main result is a new algorithm that privately answers adaptively chosen linear queries with polylogarithmic competitiveness against the best offline factorization mechanism. Compared with the aforementioned algorithm in [NTU26], our algorithm has slightly worse log factors, but maintains both privacy and accuracy under adaptive queries.

Theorem 1.7 (Main Upper Bound, Informal, Full Version in Section 5). There exists a differentially private mechanism that w.h.p. answers adaptively chosen linear queries Q=(q1,…,qm)Q=(q_1,\ldots,q_m) over any dataset X∈UnX\in\mathcal{U}^n with error

max⁡t≤m∣ot−qt(X)∣=O(γ2(Q)polylog⁡(N))\max_{t\le m} \lvert o_t-q_t(X)\rvert=O(\gamma_2(Q)\operatorname{polylog}(N))

where oto_t is the mechanism’s output at time tt.

In a previous work [5], Bun, Steinke, and Ullman posed the open problem of whether there is a polynomial separation between adaptive and oblivious analysts for privately answering linear queries online. The work by [15] already shows that even for the offline case, when the dataset is sufficiently large, the best error one can achieve is in Ω(γ2(Q))\Omega(\gamma_2(Q)). Our new upper bound matches this lower bound up to poly-logarithmic factors, giving an answer to the open problem for large datasets, and showing that, in this regime, there is only poly-logarithmic separation between offline query release, online oblivious query release, and online adaptive query release.

Our upper bound’s algorithm uses three key ingredients: the online factorization algorithm from [NTU26], a layered version of the Euclidean Iterative Database Construction (IDC) algorithm from [17] and an extended version of the target charging analysis from [CL23]. We use factorization to get ℓtRt=qt\ell_tR_t=q_t at each time step tt. The online factorization framework ensures that ∥ℓt∥2≤γ\lVert\ell_t\rVert_2\le\gamma, and for any pair of neighbouring h,h′h,h' we have ∥Rth−Rth′∥2≤1\lVert R_th-R_th'\rVert_2\le1. One can view ℓt\ell_t as a query, and RthR_th as a private point xx. Then our problem translates to a problem where we are given a point xx as the private input, neighboring inputs differ by at most 11 in ℓ2\ell_2 distance, and queries ask for an inner product of xx with a vector of ℓ2\ell_2 norm at most γ\gamma. We use a modified version of IDC to answer these queries.

The original Euclidean IDC algorithm keeps a public dataset x^\hat{x} and tries to answer each query with it. Upon receiving query qq it tries to answer it with ⟨q,x⟩\langle q,x\rangle, and uses a private test like AboveThreshold to determine if the error would be too large. If the test returns positive, it first releases a new noisy answer zz to the query, then updates the public dataset by shifting a fixed amount toward the direction of qq. With some minor modification, we can use this method to achieve a competitive ratio of O~(N1/4)\widetilde{O}(N^{1/4}). Instead of using the Euclidean IDC as a blackbox, we introduce a layered structure: we maintain a partition of Rd\mathbb{R}^d, where dd is the dimension of xx; each layer corresponds to a pairwise orthogonal subspace. Within each layer, we run a classical Euclidean IDC for queries and the public dataset projected onto the corresponding subspace. The update rule we use is slightly different: first release a noisy estimate, and shift the public dataset along the direction of the query not by a fixed amount, but to match this estimate. The key novelty here in our algorithm is that, whenever an update is triggered, we “kick out” the span of the update direction to the next layer, where, at the beginning, the first layer contains the entire space Rd\mathbb{R}^d. This layered design will make sure the dimension of the subspaces ever handled by each layer decreases geometrically, thus bounding the total number of layers. This geometric decrease is derived by a potential argument inspired by the one used for the original Euclidean IDC. Our potential decomposes the original IDC potential ∥x^−x∥22\lVert\hat{x}-x\rVert_2^2 according to the layers - within each layer, project x^−x\hat{x}-x onto the layer’s subspace and then take the ℓ2\ell_2 norm squared. At a high level, this layered structure allows us to make further updates inside each layer without “damaging what has been fixed”, and achieve a logarithmic competitive ratio.

The target charging analysis by Cohen and Lyu [CL23], at a high level, allows a tighter composition of a sequence of private mechanisms by bounding the overall privacy cost using a count of occurrences of some carefully chosen outputs. This chosen set of outputs is called a “target”. The advantage of the technique is that private mechanisms in the composition that do not produce a target output do not incur privacy loss. Unlike the Cohen and Lyu analysis, for our algorithm we need to allow the privacy parameter for each individual algorithm to be different, and to be chosen adaptively based on the output of earlier algorithms. To be more specific, the algorithms we are composing are the private tests called by the layered IDC algorithm, where the “target” would be a positive test, i.e. large error detected. Here the layered structure and kicking out directions is again crucial: since, effectively, only positive tests incur a privacy loss, and the direction used in any positive test is kicked out of the layer, a privacy loss will not be incurred in this direction again in the same layer. This allows us to bound the overall privacy loss in each layer in terms of the ℓ2\ell_2 sensitivity of xx, which is just 1. By contrast for standard IDCs the privacy loss grows with the number of updates.

We also give a new lower bound showing that, compared with the offline factorization, a competitive ratio of about the square root of the log of the universe size is necessary. This is an online extension of the lower bound by [15].

Theorem 1.8 (Main Lower Bound, Informal, Full Version in § 6). For sufficiently large nn, any private mechanism that answers online queries needs error of

Ω(γ2(Q)log⁡Nlog⁡log⁡N)\Omega\left(\gamma_2(Q)\frac{\sqrt{\log N}}{\log\log N}\right)

on some obliviously chosen sequence of queries QQ.

Our lower bound shows that even if the queries are obliviously chosen, some log factor is necessary in the competitive ratio. The argument of our lower bound consists of two parts: the first half is essentially the same as in the offline version - in the offline world, [15 Theorem 30] shows that a private algorithm implies a factorization of the same query matrix, and we show that a private online algorithm implies an online factorization algorithm of the same query matrix too. The second part is to show a lower bound for online factorizations, i.e. showing every online factorization algorithm’s competitive ratio is lower bounded on a family of linear queries. In particular, inspired by [5], we choose to use a special set of threshold queries that forms a sequence of binary search steps, and we show that no online factorization algorithm can achieve a very small value on every single search path. This argument also gives a lower bound of Ω(log⁡Nlog⁡log⁡N)\Omega\left(\frac{\sqrt{\log N}}{\log\log N}\right) for the worst case competitive ratio for any deterministic online factorization algorithm.

As mentioned above, the problem of designing simple and efficient algorithms that release answers to offline linear queries with nearly optimal error is the subject of a long line of work. The best known bounds for large datasets and (ε,δ)(\varepsilon,\delta)-differential privacy are achieved by factorization mechanisms [15].

Several interactive mechanisms have been proposed for releasing answers to adaptive linear queries: the Median Mechanism [RR10], and the Private Multiplicative Weights Mechanism [18] are two examples, where the latter mechanism also achieves optimal error bounds for worst case counting query workloads [6]. Both of these mechanisms are generalized by the Iterative Database Construction (IDC) framework [17], which we already mentioned above.

A systematic study of the cost of privately releasing answers to online queries was initiated by Bun, Steinke, and Ullman [5]. Among other questions, they investigated possible separations between offline, oblivious, and adaptive queries. They showed an exponential separation between the oblivious and adaptive settings for a specially designed class of non-linear queries. They left open the question whether a similar separation exists for a more natural class of queries, such as workloads of linear queries. Our work answers this question and shows that for linear queries all separations are at most poly-logarithmic. They also gave an error upper bound for answering mm adaptively chosen online threshold queries of O(log⁡m+polylog⁡n)O(\log m+\operatorname{polylog} n), where the dataset points are from the infinite universe [0,1][0,1]. Cohen et al. [CLN^{+}24] gave a matching lower bound for this problem. These bounds are incomparable with our results since the class of queries (threshold queries) is known ahead of time, and the universe size is infinite.

The privacy analysis in our upper bound is based on a line of work going back to the AboveThreshold/SVT mechanism [14]. Later, [KMS21] introduced SVT with individual privacy charging, which can be generalized by the target charging framework of [CL23].

Preliminaries

Notational Conventions

  • Given a∈Na \in\mathbb{N}, we use [a]≔{1,…,a}[a] \coloneqq\{1,\ldots,a\} to denote the set of the first aa natural numbers.

  • Throughout the paper, nn refers to the size of the dataset, mm refers to the number of queries and NN refers to the size of the universe U\mathcal{U}.

  • We use PV\mathcal{P}_V to denote the projection matrix onto a subspace VV.

  • We use X⪰0X \succeq0 to denote that XX is a positive semidefinite (PSD) matrix and X⪰YX \succeq Y to denote that X−Y⪰0X-Y \succeq0. The notation X⪯YX \preceq Y is equivalent to Y⪰XY \succeq X.

  • For two quantities AA and BB that may depend on other parameters, we use the notation A≲BA \lesssim B when there is an absolute constant CC such that A≤CBA \le CB; the notation A≳BA \gtrsim B is equivalent to B≲AB \lesssim A.

  • For a vector v∈Rdv \in\mathbb{R}^d, we use the standard notation for the ℓ1\ell_1, ℓ2\ell_2 and ℓ∞\ell_\infty norms:

∥v∥1:=∣v1∣+⋯+∣vd∣∥v∥2:=∣v1∣2+⋯+∣vd∣2∥v∥∞:=max⁡i∈[d]∣vi∣.\|v\|_1 := |v_1| + \cdots+ |v_d| \qquad\|v\|_2 := \sqrt{|v_1|^2 + \cdots+ |v_d|^2} \qquad\|v\|_\infty:= \max_{i \in[d]} |v_i|.

Matrix Factorization Norms

Factorization norms were introduced in functional analysis to study linear operators that factor through Hilbert space. Here, we focus on a special case that is most common in applications in computer science, and give the definitions in terms of matrices. We define the γ2\gamma_2 factorization norm of an m×Nm \times N matrix AA as

γ2(A)=min⁡{∥L∥2→∞∥R∥1→2:LR=A}.\gamma_2(A) = \min\{\|L\|_{2\to\infty}\|R\|_{1\to2}: LR = A\}.

Recall that ∥R∥1→2\|R\|_{1\to2} is the maximum ℓ2\ell_2 norm of a column of RR, and ∥L∥2→∞\|L\|_{2\to\infty} is the maximum ℓ2\ell_2 norm of a row of LL.

Basic Tools for Differential Privacy

In this subsection we define some of the most well-known tools for differential privacy.

Lemma 2.1 (Laplace mechanism [14]). Let f:Un→Rf: \mathcal{U}^n \to\mathbb{R} have sensitivity at most Δ>0\Delta> 0, where

Δ:=sup⁡X,X′ neighboring∣f(X)−f(X′)∣.\Delta:= \sup_{X,X' \text{ neighboring}} |f(X)-f(X')|.

For any ε>0\varepsilon> 0, the mechanism

M(X)=f(X)+Z,Z∼Lap⁡(Δ/ε),\mathcal{M}(X) = f(X) + Z,\qquad Z \sim\operatorname{Lap}(\Delta/\varepsilon),

is ε\varepsilon-differentially private.

Lemma 2.2 (Post-processing [14]). If M\mathcal{M} is (ε,δ)(\varepsilon,\delta)-differentially private and ff is a mapping that does not depend on XX, then f∘Mf \circ\mathcal{M} is (ε,δ)(\varepsilon,\delta)-differentially private.

Interactive Differential Privacy

We need to define privacy and accuracy for algorithms interacting with a data analyst. We do so in terms of a meta algorithm that outputs the transcript of the interaction between the algorithm M\mathcal{M} and an interactive data analyst AA.

We first consider an oblivious analyst AA that determines the sequence of queries given to M\mathcal{M} independently of the answers M\mathcal{M} gives. Without loss of generality, we can assume that AA decides the sequence of queries before the interaction starts, as shown in Algorithm 1. It is worth noting that an oblivious adversary can still know what the mechanism M\mathcal{M} is and choose the queries with this knowledge.

We also consider adaptive analysts AA that determine the next query to be given to M\mathcal{M} based on the answers to previous queries, as shown in Algorithm 2.

Definition 2.3 (Privacy of Interactive Algorithms). An interactive algorithm M\mathcal{M} is (ε,δ)(\varepsilon,\delta)-differentially private (for non-adaptive/adaptive analysts) if for every dataset X∈UnX \in\mathcal{U}^n, and for every (resp. non-adaptive/adaptive) analyst AA, the algorithm Trans⁡M↔Am\operatorname{Trans}_{\mathcal{M}\leftrightarrow A}^{m} is (ε,δ)(\varepsilon,\delta)-differentially private.

Similarly, we can define accuracy for interactive algorithms via the same meta-algorithm:

Algorithm 1 The meta-algorithm Trans⁡mM↔A(X)\operatorname{Trans}_{m}^{M\leftrightarrow A}(X) for oblivious analysts

Require: Dataset X∈UnX \in\mathcal{U}^{n}

  1. AA chooses queries q1,…,qmq_{1},\ldots,q_{m}.

  2. for j=1,…,mj=1,\ldots,m do

  3. Give qjq_{j} to M(X)\mathcal{M}(X) and receive an answer ojo_{j}.

  4. end for

  5. return (Q=(q1,…,qm),o=(o1,…,om))(Q=(q_{1},\ldots,q_{m}),o=(o_{1},\ldots,o_{m})).

Algorithm 2 The meta-algorithm Trans⁡mM↔A(X)\operatorname{Trans}_{m}^{M\leftrightarrow A}(X) for adaptive analysts

Require: Dataset X∈UnX \in\mathcal{U}^{n}

  1. o0←⊥o_{0} \leftarrow\perp.

  2. for j=1,…,mj=1,\ldots,m do

  3. Give oj−1o_{j-1} to AA and receive a query qjq_{j}.

  4. Give qjq_{j} to M(X)\mathcal{M}(X) and receive an answer ojo_{j}.

  5. end for

  6. return (Q=(q1,…,qm),o=(o1,…,om))(Q=(q_{1},\ldots,q_{m}),o=(o_{1},\ldots,o_{m})).

Definition 2.4 ((α,β\alpha,\beta)-Accuracy of Interactive Algorithms). An interactive algorithm MM is (α(Q),β)(\alpha(Q),\beta)-accurate for mm queries against non-adaptive/adaptive analysts if for every dataset X∈UnX \in\mathcal{U}^{n}, and every (resp. non-adaptive/adaptive) analyst AA, if QQ is the queries submitted by AA,

Pr⁡(Q,o)←Trans⁡mM↔A(X)[∥Q(X)−o∥∞≤α(Q)]≥1−β,\Pr_{(Q,o)\leftarrow\operatorname{Trans}_{m}^{M\leftrightarrow A}(X)}\left[\lVert Q(X)-o\rVert_{\infty}\leq\alpha(Q)\right]\geq1-\beta,

where α(Q)\alpha(Q) is some real-valued function of QQ.

Definition 2.5 (ℓ∞\ell_{\infty} Error of Interactive Algorithms). An interactive algorithm M\mathcal{M} has ℓ∞\ell_{\infty} error at most α(Q)\alpha(Q) for mm queries against oblivious/adaptive analysts if, for every dataset X∈UnX \in\mathcal{U}^{n} and every (resp. oblivious/adaptive) analyst AA,

(E(Q,o)←Trans⁡mM↔A(X)[∥Q(X)−o∥∞2])1/2≤α(Q),\left(\mathbb{E}_{(Q,o)\leftarrow\operatorname{Trans}_{m}^{M\leftrightarrow A}(X)}\left[\lVert Q(X)-o\rVert_{\infty}^{2}\right]\right)^{1/2}\leq\alpha(Q),

where α(Q)\alpha(Q) is some real-valued function of QQ. The expectation is over the randomness of both M\mathcal{M} and AA. Moreover, we define the ℓ∞2\ell_{\infty}^{2} error for the worst case dataset to be

err⁡(M,A):=sup⁡X(E(Q,o)←Trans⁡mM↔A(X)[∥Q(X)−o∥∞2])1/2.\operatorname{err}(\mathcal{M},A):=\sup_{X}\left(\mathbb{E}_{(Q,o)\leftarrow\operatorname{Trans}_{m}^{M\leftrightarrow A}(X)}\left[\lVert Q(X)-o\rVert_{\infty}^{2}\right]\right)^{1/2}.

Moreover, when the adversary is oblivious, since the queries do not depend on the answers, we can denote the error as err⁡(M,Q)\operatorname{err}(\mathcal{M},Q). We remark that the supremum in ℓ∞2\ell_{\infty}^{2} error is taken over all datasets of arbitrary size.

An Equivalent Form for Online Factorization Algorithms

In this technical section, we define the Growing Matrix Problem, which will be a convenient alternative way to view the online factorization problem.

Definition 3.1 (The Growing Matrix Problem). For a query matrix QQ arriving online, we say an online algorithm that outputs a sequence of positive semidefinite (PSD) matrices Σ1,…,Σm\Sigma_{1},\ldots,\Sigma_{m} achieves value γ\gamma for the Growing Matrix Problem over QQ if, for each t∈[m]t\in[m],

  • Σt\Sigma_{t} is a t×tt\times t PSD matrix;

  • Σt\Sigma_t is the principal submatrix of Σt+1\Sigma_{t+1} consisting of its top tt rows and columns;

  • Σm\Sigma_m (and, therefore, every Σt\Sigma_t) has all its diagonal entries bounded by γ2\gamma^2, for a non-negative number γ\gamma;

  • if QtQ_t is the submatrix of QQ that has arrived by time step tt, and qq is a column of QtQ_t, then Σt⪰qqT\Sigma_t \succeq qq^{T}.

The Proposition below states the equivalence between the Growing Matrix Problem and the online factorization problem. At a high level, Σt\Sigma_t corresponds to LtLtTL_tL_t^{T}, and its growing property allows us to construct the RtR_t matrix so that only new rows are being appended to it over time.

Proposition 3.2. There is an online algorithm that achieves value γ2\gamma^2 for the Growing Matrix Problem over QQ if and only if there exists an online factorization mechanism for QQ with factorization value γ\gamma.

The proof of the above proposition can be found in Appendix § 9. Let us also prove the following corollary of Proposition 3.2, which will be used later in § 7.

Corollary 3.3. For any online factorization algorithm, there exists an equivalent online factorization algorithm that, at each time tt, appends at most one row to Rt−1R_{t-1}.

Proof. Take any online factorization algorithm, and use Proposition 3.2 to first get an online algorithm for the growing matrix problem, and then use the proposition again to get back an equivalent online factorization. By construction, we increase the number of rows of MtM_t by only one at each time step tt, and therefore, we also increase the number of rows of Rt=MtQtR_t = M_tQ_t by at most 1. □

Lower Bound on Error for Private Online Query Release

In this section, we show a lower bound similar to [15 Theorem 30], but for online private query release algorithms. We will show that any private interactive mechanism can be made data-independent when the size of the dataset is large enough, with a slightly modified version of a result in [BDKT12], and that any data-independent private interactive mechanism implies an online factorization algorithm by using the data-independent noise’s covariance as the growing matrix, which implies an online factorization. Then we prove a lower bound on the competitive ratio of online factorization by looking at the family of threshold queries corresponding to binary search, and show that at least one search path has to have a lower bounded competitive ratio.

We start by showing the online version of Theorem 30 in [15].

Lemma 4.1. Let M\mathcal{M} be an online (ε,δ)(\varepsilon,\delta)-differentially private algorithm answering obliviously chosen linear queries on datasets X∈UnX \in U^n. For every ε,δ\varepsilon,\delta smaller than some absolute constants, there exists a deterministic online factorization algorithm that on every query matrix QQ achieves factorization value

γ=O(ε⋅err⁡(M,Q)).\gamma= O(\varepsilon\cdot\operatorname{err}(\mathcal{M},Q)).

As in the original proof, we first need to apply a reduction from data-dependent algorithms to data-independent ones. This is [15 Lemma 29], a slightly modified version of [BDKT12, Theorem 4.3], which also holds against oblivious online queries. Let us restate it here.

Lemma 4.2 (Online version of Lemma 29, [15]). For any oblivious sequence of linear queries with query matrix Q∈Rm×NQ \in\mathbb{R}^{m \times N}, for every interactive (ε,δ)(\varepsilon,\delta)-differentially private mechanism M\mathcal{M}, and for any c>0c > 0, there exists an (ε,δ+c)(\varepsilon,\delta+c)-differentially private data-independent mechanism M′\mathcal{M}' such that

err⁡(M′,Q)≤err⁡(M,Q).\operatorname{err}(\mathcal{M}',Q) \le\operatorname{err}(\mathcal{M},Q).

Here, we say an online algorithm is data-independent if, upon receiving query qtq_t at time tt, it outputs qt(X)+Wq_t(X)+\mathcal{W} where W\mathcal{W} does not depend on XX.

The proof of the above lemma can be found in Appendix § 9 - it follows the same idea as the proof of [BDKT12, Theorem 4.3], but uses a different noise distribution and a simpler analysis. Now let us return to Lemma 4.1. Proof of Lemma 4.1. First we note that the original theorem was for ℓ2\ell_2 error, but as mentioned right below the original proof it also extends to the max error. Applying Lemma 4.2 we obtain an online noise adding algorithm, at each time tt adding noise ZtZ_t, independent of the dataset XX, to qt(X)q_t(X). For some absolute constant CC, we take

Σt=C2ε2Cov⁡(Z≤t),\Sigma_t = C^2 \varepsilon^2 \operatorname{Cov}(Z_{\le t}),

where Z≤tZ_{\le t} contains all the noises up to time tt. By the same covariance bound in [15 Lemma 27], we obtain

Σt⪰qqT.\Sigma_t \succeq q q^{\mathsf T}.

Furthermore, we can bound the diagonal entries

(Σt)ii=C2ε2Var⁡(Zi)≲(ε⋅err⁡(M,Q))2(\Sigma_t)_{ii} = C^2 \varepsilon^2 \operatorname{Var}(Z_i) \lesssim\left(\varepsilon\cdot\operatorname{err}(\mathcal{M},Q)\right)^2

Applying Proposition 3.2 finishes the proof.

We now have a reduction from general online private query release to deterministic online factorization. We will give a direct lower bound for the latter. We consider a binary search tree, and, for any path in the tree, the sequence of threshold queries associated with nodes on the path, where threshold queries are a special subset of linear queries, defined as follows:

Definition 4.3 (Threshold Query). A threshold query is specified by a function qν:U→{0,1}q^\nu:\mathcal{U}\to\{0,1\} such that

qν(x)=1{x≤ν}.q^\nu(x) = 1\{x \le\nu\}.

For a dataset X=(x1,…,xn)∈UnX=(x_1,\ldots,x_n)\in\mathcal{U}^n, its answer is

qν(X):=∑i=1nqν(xi).q^\nu(X) := \sum_{i=1}^{n}q^\nu(x_i).

We show that no factorization algorithm can achieve a very small factorization value on all such paths. The key idea of the proof is that, at each step of choosing whether to ask a query corresponding to the left or right side of the current search range, there must be one side that makes the average column norm of RR restricted to the search range large, and thus one can always choose that side as the next query.

Lemma 4.4. For threshold queries on domain [N][N]: assume NN is a power of 22 and construct a full binary tree, where the root node represents [N][N], its children represent [N/2][N/2] and [N]∖[N/2][N]\setminus[N/2], etc., down to the leaf nodes that represent singleton sets {i}\{i\} for i∈[N]i\in[N]. We let each node represent the threshold query indexed by the middle point of the range it represents. Then each path from root to leaf forms a sequence of queries. Then, for any deterministic online factorization algorithm, there exists a path on which the algorithm achieves factorization value Ω(log⁡N)\Omega(\sqrt{\log N}).

As a direct consequence, the worst case competitive ratio of any deterministic online factorization algorithm is Ω(log⁡Nlog⁡log⁡N)\Omega\left(\frac{\sqrt{\log N}}{\log\log N}\right).

Proof. Since we are considering deterministic factorization algorithms, it is well-known ([20]) that adaptively chosen inputs have no extra power compared with oblivious inputs. So, we may assume without loss of generality that the queries are chosen adversarially. Consider the following adaptive adversary: At time tt, after asking the threshold query corresponding to a range SS, the adversary selects one of SLS_L and SRS_R, the left and right disjoint halves of SS. Let us define

μt(S):=Rt1S∣S∣.\mu_t(S) := \frac{R_t\mathbf{1}_S}{|S|}.

The above vector is an average of the columns of RtR_t inside the range SS. We will show that max⁡{∥μt(SL)∥2,∥μt(SR)∥2}\max\{\lVert\mu_t(S_L)\rVert_2,\lVert\mu_t(S_R)\rVert_2\} is strictly larger than ∥μt(S)∥2\lVert\mu_t(S)\rVert_2. We know that ℓtRt=qt\ell_tR_t=q_t, where qtq_t is the threshold query corresponding to the range SS. By the definition of a threshold query, qtq_t is a binary vector that has all ones up to the middle point of SS, and all zeros after that. Then it is clear that

ℓtμt(SL)=1,ℓtμt(SR)=0,\ell_t\mu_t(S_L)=1,\qquad\ell_t\mu_t(S_R)=0,

and, therefore, by Cauchy-Schwarz,

∥μt(SL)−μt(SR)∥2≥ℓt(μt(SL)−μt(SR))∥ℓt∥2≥1∥ℓt∥2.\lVert\mu_t(S_L)-\mu_t(S_R)\rVert_2 \ge\frac{\ell_t(\mu_t(S_L)-\mu_t(S_R))}{\lVert\ell_t\rVert_2} \ge\frac{1}{\lVert\ell_t\rVert_2}.

By the parallelogram identity, we have

∥μt(SL)∥22+∥μt(SR)∥222=∥μt(S)∥22+14∥μt(SL)−μt(SR)∥22≥∥μt(S)∥22+14∥ℓt∥22.\begin{aligned} \frac{\lVert\mu_t(S_L)\rVert_2^2+\lVert\mu_t(S_R)\rVert_2^2}{2} = \lVert\mu_t(S)\rVert_2^2+\frac{1}{4}\lVert\mu_t(S_L)-\mu_t(S_R)\rVert_2^2 \\ &\ge\lVert\mu_t(S)\rVert_2^2+\frac{1}{4\lVert\ell_t\rVert_2^2}. \end{aligned}

Thus at each time tt there exists b∈{L,R}b \in\{L,R\} s.t.

∥μt(Sb)∥22≥∥μt(S)∥22+14∥ℓt∥22.\lVert\mu_t(S_b)\rVert_2^2 \ge\lVert\mu_t(S)\rVert_2^2+\frac{1}{4\lVert\ell_t\rVert_2^2}.

At each step, the adversary chooses this bb, and the average column norm squared over the current range grows by an additive factor of at least 14∥ℓt∥22\frac{1}{4\lVert\ell_t\rVert_2^2}. Note that the online factorization algorithm only appends rows to the RtR_t matrix. Thus when the leaf node is reached, since each leaf node corresponds to only one element, the column norm corresponding to this leaf node with range SfinalS_{final} is

∥μt(Sfinal)∥22≥log⁡N4∥L∥2→∞2.\lVert\mu_t(S_{final})\rVert_2^2 \ge\frac{\log N}{4\lVert L\rVert_{2\to\infty}^2}.

Hence, denoting the number of queries by mm, we have

∥Rm∥1→2∥L∥2→∞≥log⁡N2.\lVert R_m\rVert_{1\to2}\lVert L\rVert_{2\to\infty} \ge\frac{\sqrt{\log N}}{2}.

To prove the second part of the lemma, observe that any path of the tree corresponds to a sequence of m=O(log⁡N)m=O(\log N) threshold queries, and the γ2\gamma_2 norm of the corresponding query matrix is known to be only O(log⁡m)=O(log⁡log⁡N)O(\log m)=O(\log\log N) by the work [MNT14].

We are now fully equipped with all the tools we need: Combining Lemma 4.4 and Lemma 4.1 proves our lower bound theorem.

Theorem 1.8 (Main Lower Bound, Formal). For sufficiently small privacy parameters ε,δ\varepsilon,\delta bounded by absolute constants, for any (ε,δ)(\varepsilon,\delta)-DP online mechanism M\mathcal{M}, there exists a sequence of mm obliviously chosen linear queries Q=(q1,…,qm)Q=(q_1,\ldots,q_m) over a universe of size NN, such that

err⁡(M,Q)=Ω(γ2(Q)log⁡NCεlog⁡log⁡N).\operatorname{err}(\mathcal{M},Q)=\Omega\left(\frac{\gamma_2(Q)\sqrt{\log N}}{C\varepsilon\log\log N}\right).

Remark 4.5. One can show that for sufficiently small ε,δ,β\varepsilon,\delta,\beta, no (ε,δ+β)(\varepsilon,\delta+\beta)-differentially private algorithm can achieve error

O(γ2(Q)log⁡NCεlog⁡log⁡N),O\left(\frac{\gamma_2(Q)\sqrt{\log N}}{C\varepsilon\log\log N}\right),

with probability more than 1−β1-\beta on all sequences of queries, by clipping the noise ZZ after applying Lemma 4.2.

Adaptive Private Query Release

In this section, we consider the following problem: we hold a private point x∈Rdx \in\mathbb{R}^d, where neighboring points have ℓ2\ell_2 distance at most 1 from each other. At each time step tt, we receive a query qtq_t. We want to release a private estimate of ⟨qt,x⟩\langle q_t,x\rangle, and we give accuracy bounds assuming queries have ℓ2\ell_2 norm at most γ\gamma. In this section, we design a layered Iterative Database Construction algorithm, that keeps a public synthetic point to answer the queries, and updates it according to the queries. The algorithm is composed of several Euclidean IDC instances, each handling a subspace of the data universe, where the subspaces for different instances are pairwise orthogonal. Before any query arrives, the first layer handles the entire space, while other layers handle the empty subspace. We use a kick-out trick to maintain bounded privacy and error for each instance - whenever the public dataset is updated, the span of the direction of update, which is the direction of the query vector projected to the subspace handled by the current layer, will be moved to the next layer. Apart from that, within each layer, the private test and the subsequent update can be viewed as a private mechanism together. We call this bundled mechanism InsideOrRelease. Then the execution of our algorithm will make a sequence of calls to InsideOrRelease, which can be analyzed using the target charging framework. One nuance is that these individual calls will have non-uniform privacy parameters that depend on the previous calls, so we need to provide an extended version of the target charging analysis suited to our use case.

The Target Charging Framework

Here we introduce some elements of the target charging analysis by Cohen and Lyu [CL23], which our privacy analysis will rely on.

Definition 5.1 (qq-target [CL23, Definition 2.1]). Let A:X→Y\mathcal{A}:\mathcal{X} \to\mathcal{Y} be a randomized algorithm, and let q∈(0,1]q \in(0,1], ε≥0\varepsilon\ge0. A measurable set T⊆YT \subseteq\mathcal{Y} is a qq-target with parameter ε\varepsilon for A\mathcal{A} if, for every neighboring pair x0,x1∈Xx_0,x_1 \in\mathcal{X}, there exist r∈[0,1]r \in[0,1], a distribution CC on Y\mathcal{Y}, and an ε\varepsilon-DP mechanism M:{0,1}→Y\mathcal{M}:\{0,1\} \to\mathcal{Y}, such that if Pj,QjP_j,Q_j are the distributions of A(xj),M(j)\mathcal{A}(x_j),\mathcal{M}(j) respectively, then for every j∈{0,1}j \in\{0,1\},

Pj=(1−r)C+rQj,Pr⁡[M(j)∈T]≥q.P_j = (1-r)C + rQ_j, \qquad\Pr[\mathcal{M}(j) \in T] \ge q.

An output in TT is called a target hit.

The target charging framework gives a convenient way for proving privacy of a composition of a collection of private algorithms when there is a guaranteed bound on the number of target hits. Each algorithm can be viewed as consisting of two branches, one branch that does not use the dataset at all, and another branch that depends on the dataset. A target is a subset TT of the output space such that when the algorithm goes into the branch that uses the dataset, it is guaranteed to produce an output in TT with probability bounded from below. Intuitively, if we have an upper bound on the number of target hits, we can bound the number of times the algorithms go into the data-dependent branch and thus also bound the overall privacy loss of the composition. This clearly gives a tighter analysis than simply applying a composition theorem to the entire collection of algorithms, and ignoring the bound on the number of target hits. For this paper, we only use one kind of target proposed in [CL23], restated in the following lemma.

Lemma 5.2 (NotPrior target [CL23, Lemma 2.3; Lemma C.2]). Let A:X→Y∪{⊥}\mathcal{A}:\mathcal{X} \to\mathcal{Y} \cup\{\perp\} be an ε\varepsilon-DP algorithm, where Y\mathcal{Y} is nonempty and ⊥∉Y\perp\notin\mathcal{Y}. Then Y\mathcal{Y} is a 1/(eε+1)1/(\mathrm{e}^{\varepsilon}+1)-target with parameter ε\varepsilon for A\mathcal{A}.

The lemma holds when the input domain is restricted to a fixed neighboring pair.

Target Charging Analysis for Private Threshold Tests

Let us first define the following subroutine that is being used in our algorithm. For b>0b > 0, a unit direction uu, and public thresholds τ−<τ+\tau_- < \tau_+, we define InsideOrRelease⁡b(x;u,τ−,τ+)\operatorname{InsideOrRelease}_b(x;u,\tau_-,\tau_+) to be a noisy test for whether ⟨x,u⟩\langle x,u\rangle lands inside [τ−,τ+][\tau_-,\tau_+]. When this noisy test does not report inside, it outputs a noisy estimate of ⟨x,u⟩\langle x,u\rangle. The parameter bb controls the magnitude of noises. Every call to this algorithm uses fresh independent randomness.

Algorithm 3 InsideOrReleaseb(x;u,τ−,τ+)_b(x; u, \tau_-, \tau_+)

Input: x∈Rdx \in\mathbb{R}^d, ∥u∥2=1\lVert u\rVert_2 = 1, τ−<τ+\tau_- < \tau_+, b>0b > 0.

  1. Draw Z∼Lap⁡(0,b)Z \sim\operatorname{Lap}(0,b)

  2. if τ−<⟨x,u⟩+Z<τ+\tau_- < \langle x,u\rangle+ Z < \tau_+ then

  3. return Inside.

  4. else

  5. return ⟨x,u⟩+Z\langle x,u\rangle+ Z.

  6. end if

We now state the privacy guarantee of this subroutine.

Lemma 5.3 (Indistinguishability of InsideOrRelease). Fix uu, τ−\tau_-, τ+\tau_+ and a pair x,x′x,x'. The outputs of Algorithm 3 over xx and x′x' are ∣⟨x−x′,u⟩∣b\frac{\lvert\langle x-x',u\rangle\rvert}{b}-indistinguishable, where we say two distributions PP and P′P' are ε\varepsilon-indistinguishable if for any measurable subset SS,

e−εP′(S)≤P(S)≤eεP′(S).e^{-\varepsilon}P'(S) \le P(S) \le e^\varepsilon P'(S).

Proof. This lemma follows trivially from privacy guarantees of the Laplace noise mechanisms and postprocessing.

This lemma is equivalent to saying the subroutine is differentially private up to the same parameter for fixed neighboring pairs, which is what Lemma 5.2 uses. The target will be R\mathbb{R}, i.e. when the above test releases a real number. In fact, later in this section we choose appropriate parameters so that R\mathbb{R} is a 1/41/4-target.

For the purpose of our algorithm, which is to be defined in a later subsection, we need to analyze the composition of a collection of private algorithms with non-uniform privacy parameters, and these parameters could depend on the execution of the previous algorithms. This is an extended version of [CL23, Lemma 2.2; Remark B.6].

Algorithm 4 Weighted Target Charging with bounded privacy loss

Input: Dataset x∈Xx \in\mathcal{X}; horizon T∈NT \in\mathbb{N}.

  1. for i=1,…,Ti = 1,\ldots,T do

  2. Receive (Ai,Ti)(\mathcal{A}_i,\mathcal{T}_i), chosen according to the preceding transcript, where Ai\mathcal{A}_i is εi\varepsilon_i-DP, εi\varepsilon_i is determined by the history before time ii, and Ti\mathcal{T}_i is a qq-target with parameter εi\varepsilon_i for Ai\mathcal{A}_i.

  3. Release Ai(x)\mathcal{A}_i(x)

  4. end for

Lemma 5.4 (Privacy of weighted target charging with bounded privacy loss). For every η∈(0,1)\eta\in(0,1) and α>0\alpha> 0, if in every execution,

∑i s.t. Ai(x)∈Tiεi2≤S,q∈(0,1],0≤εi≤εˉ≤1,\sum_{i\ \mathrm{s.t.}\ \mathcal{A}_i(x)\in\mathcal{T}_i} \varepsilon_i^2 \le S,\qquad q\in(0,1],\qquad0\le\varepsilon_i\le\bar{\varepsilon}\le1,

then Algorithm 4 is

((1+α)S2q+2log⁡(1/η)(1+α)Sq, η+exp⁡((log⁡(1+α)−α)Sεˉ2))-DP.\left(\frac{(1+\alpha)S}{2q}+\sqrt{2\log(1/\eta)(1+\alpha)\frac{S}{q}},\ \eta+\exp\left((\log(1+\alpha)-\alpha)\frac{S}{\bar{\varepsilon}^{2}}\right)\right)\text{-DP}.

We defer the proof to Appendix § 9.

Iterative Database Construction with Layered Subspaces

Now we define the layered IDC algorithm, as shown in Algorithm 5. The algorithm holds a public synthetic point x^\hat{x}, where initially x^=0\hat{x}=0. We partition the data universe into orthogonal subspaces V1,V2,…V_1,V_2,\ldots. Initially, V1=RdV_1 = \mathbb{R}^d and ∀j>1,Vj={0}\forall j > 1, V_j = \{0\}. On each query qtq_t, the algorithm goes through every VjV_j, and tries to examine if x^\hat{x} and xx are far in the direction of u:=PVjqt/∥PVjqt∥2u := P_{V_j}q_t/\|P_{V_j}q_t\|_2, i.e. qtq_t projected to subspace VjV_j and renormalized. If they are close, x^\hat{x} can be used to answer the query inside this subspace. Otherwise, we release a noisy estimate z=⟨x,u⟩+Zz = \langle x,u\rangle+ Z. We shift x^\hat{x} alongside uu such that ⟨x^,u⟩=z\langle\hat{x},u\rangle= z, and kick out the line through direction uu to the next subspace. Effectively, after identifying a bad direction, we pay some privacy cost to rewrite x^\hat{x} only in this direction. Each of these kick-out events can be viewed as a target hit, and we will use the target charging technique for the analysis.

The layered structure gives several desirable properties. By separating the subspaces orthogonally, future repairs in the remaining directions will not damage what is already repaired in the current layer. We also bound the number of layers needed by a potential argument. For each layer jj, consider the potential

Φj=∥PVj(x−x^)∥22\Phi_j = \|P_{V_j}(x-\hat{x})\|_2^2

which is the distance between the public and private points inside subspace VjV_j. When we kick out a direction, we can give an upper bound on the potential increment in the next layer (i.e., the layer receiving the kicked out direction) because this distance is exactly the square of the noise inside the estimate we just released. We can also give a lower bound on the potential decrement in the current layer because, to trigger an update, xx and x^\hat{x} must have been sufficiently separated in the query direction, and the contribution of this direction to the potential will become 0, since it no longer belongs to the current layer. We can then show the total potential gain for each layer decreases geometrically from one layer to the next, which allows us to bound the number of layers.

Algorithm 5 Layered IDC

Require: Private point x∈Rdx \in\mathbb{R}^d; Query horizon mm; parameters a,b>0a,b > 0.

  1. x^←0∈Rd\hat{x} \leftarrow0 \in\mathbb{R}^d ▷ Public synthetic point

  2. V1←RdV_1 \leftarrow\mathbb{R}^d

  3. V2,…,VL+1←{0}V_2,\ldots,V_{L+1} \leftarrow\{0\} ▷ The final layer VL+1V_{L+1} is never tested

  4. for t=1,…,mt = 1,\ldots,m do

  5. Receive qt∈Rdq_t \in\mathbb{R}^d

  6. for j=1,…,Lj = 1,\ldots,L do

  7. v←PVjqtv \leftarrow P_{V_j}q_t ▷ Projection onto the current layer

  8. if ∥v∥2>0\|v\|_2 > 0 then

  9. u←v/∥v∥2u \leftarrow v/\|v\|_2;

  10. z←InsideOrRelease⁡b(x;u,⟨x^,u⟩−2a,⟨x^,u⟩+2a)z \leftarrow\operatorname{InsideOrRelease}_b(x;u,\langle\hat{x},u\rangle-2a,\langle\hat{x},u\rangle+2a)

  11. if z≠Inside⁡z \ne\operatorname{Inside} then

  12. x^←x^+(z−⟨x^,u⟩)u\hat{x} \leftarrow\hat{x} + (z-\langle\hat{x},u\rangle)u

  13. Vj←Vj∩u⊥V_j \leftarrow V_j \cap u^\perp ▷ Kick uu out of layer jj

  14. Vj+1←Vj+1⊕span⁡{u}V_{j+1} \leftarrow V_{j+1} \oplus\operatorname{span}\{u\}

  15. end if

  16. end if

  17. end for

  18. Release ot:=⟨x^,qt⟩o_t := \langle\hat{x},q_t\rangle

  19. end for

The parameters aa and bb are for controlling, respectively, the width of the inside range and the magnitude of the noise of InsideOrRelease⁡\operatorname{InsideOrRelease}. Let us first prove the following technical lemma which bounds the privacy cost of all the target hits. Recall that a target hit here is just when InsideOrRelease⁡\operatorname{InsideOrRelease} outputs a real number, which triggers an update to the public point.

Lemma 5.5 (Orthonormal Properties and Counting kick-outs). In Algorithm 5, index all calls to InsideOrRelease⁡b\operatorname{InsideOrRelease}_b by ii, and let uiu_i be the unit direction used in call ii. For each layer j≤Lj \le L, let IjI_j be the set of indices of calls that kick a direction out of VjV_j. On every execution, the directions {ui:i∈Ij}\{u_i : i \in I_j\} are orthonormal within each layer j∈{1,…,L}j \in\{1,\ldots,L\}.

Fix neighboring points x,x′∈Rdx,x' \in\mathbb{R}^d, and assign call ii the pairwise privacy parameter

εi=∣⟨x−x′,ui⟩∣b.(1)\varepsilon_i = \frac{|\langle x-x',u_i\rangle|}{b}. \tag*{(1)}

Then 0≤εi≤1/b0 \le\varepsilon_i \le1/b, and on every execution,

∑j=1L∑i∈Ijεi2≤Lb2.\sum_{j=1}^{L}\sum_{i\in I_j}\varepsilon_i^2 \le\frac{L}{b^2}.

Equivalently, since each numerical output is a target hit and causes exactly one kick-out,

∑i: target hitεi2≤Lb2.\sum_{i:\,\text{target hit}}\varepsilon_i^2 \le\frac{L}{b^2}.

Proof. The orthonormal property holds because, once uiu_i is kicked out of VjV_j, all future directions uku_k used to call InsideOrReleaseb_b inside layer jj lie inside Vj∩ui⊥V_j \cap u_i^\perp. The fact that εi≤1/b\varepsilon_i \le1/b is trivial from the parameter choice. To prove the rest of this lemma, observe that the orthonormal property implies that each layer may only contribute at most 1b2∥x−x′∥2\frac{1}{b^2}\lVert x-x'\rVert_2 to the sum. □

We can now prove the main upper bound theorem for the layered IDC. Lemma 5.5 gives an upper bound on the privacy cost of target hits, i.e., the iterations in which InsideOrReleaseb_b outputs a number. With the target charging analysis, this will allow us to bound the overall privacy loss of the algorithm. The layered structure will ensure the error contributed by each layer is bounded. We will show that no element ever enters the last, never-tested layer, via a potential argument, thus bounding the overall error.

Theorem 5.6 (Privacy and accuracy of Layered IDC). Let m≥1m \ge1, γ>0\gamma> 0, ε>0\varepsilon> 0, and δ>0\delta> 0, β∈(0,1)\beta\in(0,1). For a sufficiently large universal constant C>0C > 0, set

L=2+⌊log⁡9d⌋,b=max⁡(1,CLε,Cε(Llog⁡1δ+log⁡1δ)),a=2blog⁡mLβ.L = 2 + \left\lfloor\log_9 d \right\rfloor,\qquad b = \max\left(1,C\sqrt{\frac{L}{\varepsilon}},\frac{C}{\varepsilon}\left(\sqrt{L\log\frac{1}{\delta}}+\log\frac{1}{\delta}\right)\right),\qquad a = 2b\log\frac{mL}{\beta}.

Then Algorithm 5 is (ε,δ)(\varepsilon,\delta)-differentially private. Moreover, for every x∈Rdx \in\mathbb{R}^d and every adaptive analyst submitting at most mm queries qt∈Rdq_t \in\mathbb{R}^d with ∥qt∥2≤γ\lVert q_t\rVert_2 \le\gamma,

Pr⁡[max⁡t≤m∣ot−⟨x,qt⟩∣≤5γaL2]≥1−β.\Pr\left[\max_{t\le m}|o_t-\langle x,q_t\rangle|\le\frac{5\gamma a\sqrt{L}}{2}\right]\ge1-\beta.

Proof. Since, by Lemma 5.2, εi≤1/b≤1\varepsilon_i \le1/b \le1, each real output of InsideOrRelease is a 1/41/4-target. Combining Lemma 5.5 with Lemma 5.4, and choosing

S=Lb2,α=4log⁡1δL+2,η=δ/2S=\frac{L}{b^2},\qquad\alpha=\frac{4\log\frac{1}{\delta}}{L}+2,\qquad\eta=\delta/2

proves the privacy guarantee. To understand the intuition behind the parameter choices here and in the theorem statement, the choice of α\alpha bounds the failure probability, i.e. the δ\delta term; the first term of bb is to bound each εi\varepsilon_i by 1; the other two terms are to give us the ε\varepsilon term in (ε,δ)(\varepsilon,\delta)-differential privacy.

Now we prove the error bound. There are at most mLmL Laplace draws, and each satisfies Pr⁡(∣Z∣≥a/2)=e−a/(2b)\Pr(|Z|\ge a/2)=e^{-a/(2b)}. Thus, by the choice of aa and a union bound, all the Laplace noises have absolute value less than a/2a/2 with probability at least 1−β1-\beta. We bound the error assuming this event happens.

For each layer jj, recall that the potential is

Φj=∥PVj(x−x^)∥22.\Phi_j=\lVert P_{V_j}(x-\hat{x})\rVert_2^2.

Observe that whenever the kick-out happens at layer jj, Φj\Phi_j drops by at least 9a24\frac{9a^2}{4}, and Φj+1\Phi_{j+1} increases by at most a24\frac{a^2}{4}. Since Φj\Phi_j is non-negative at every time step, this means the number of dimensions that enter each layer jj, j≥3j\ge3, is at most 1/91/9-th of the number of dimensions that enter the previous layer j−1j-1. Moreover, at most dd dimensions can enter layer 2: Layer 1 has unbounded potential but only dd dimensions have to be kicked out of it. Consequently, at most d/9L−1<1d/9^{L-1}<1 directions can enter layer L+1L+1, so this layer must always be empty.

At any fixed layer j≤Lj \le L, whenever InsideOrRelease outputs Inside, or immediately after a kick-out is performed, it is clear that

∣⟨x^−x,u⟩∣≤5a2.\lvert\langle\hat{x}-x,u\rangle\rvert\le\frac{5a}{2}.

Summing over layers using the orthogonality between layers and then scaling by γ\gamma finishes the proof.

Remark 5.7. In particular, the maximum error is

O(γ[log⁡dlog⁡(1/δ)+log⁡dlog⁡(1/δ)ε+log⁡dε+log⁡d]log⁡mlog⁡dβ)O\left(\gamma\left[\frac{\log d\sqrt{\log(1/\delta)}+\sqrt{\log d}\log(1/\delta)}{\varepsilon}+\frac{\log d}{\sqrt{\varepsilon}}+\sqrt{\log d}\right]\log\frac{m\log d}{\beta}\right)

with probability at least 1−β1-\beta, and we can take β=δ\beta=\delta.

We can easily extend the above theorem to the following setup where new dimensions are added to the private point over time. We will require this variant in our later use of the algorithm.

Corollary 5.8. Algorithm 5 works if the private point xx has growing dimension. In particular, for any time tt, the algorithm receives a pair (qt,xt)(q_t,x_t) such that there exists Ut⊆[d]U_t \subseteq[d],

Ut−1⊆Ut,xt∣Ut−1=xt−1∣Ut−1,qt∣[d]∖Ut=0U_{t-1} \subseteq U_t,\qquad x_t|_{U_{t-1}}=x_{t-1}|_{U_{t-1}},\qquad q_t|_{[d]\setminus U_t}=0

The privacy and accuracy guarantees shown above hold exactly unchanged, assuming the neighboring constraints hold for the fully revealed point at the end of the time horizon.

Proof. We can view the private point x:=xmx := x_m as being fixed ahead of time, and the dimensions in Ut∖Ut−1U_t \setminus U_{t-1} are introduced into layer 1 at time step tt. At most dd dimensions are ever introduced into layer 1. It is easy to verify that the analysis of our mechanism still holds.

The Main Algorithm

In this subsection, we describe how to use the algorithm for Adaptive Inner Product Query Release to answer linear queries without an assumption on the norm of each query.

Let us recall the adaptive linear query release setup: we hold a private histogram h∈RNh \in\mathbb{R}^N, where neighboring histograms differ at most by 1 at one entry. At each time we receive a query qtq_t and we want to release a private estimate of ⟨qt,h⟩\langle q_t,h\rangle.

We will use the online factorization algorithm in [NTU26, Theorem 1.4] and the version of layered IDC in Corollary 5.8 as subroutines. At the arrival of each query, our algorithm uses the online factorization algorithm to maintain a factorization ℓtRt=qt\ell_tR_t=q_t, and uses RthR_th as the point xx, ℓt\ell_t as the query for our IDC algorithm (with the extension introduced in Corollary 5.8).

Algorithm 6 Online Query Release
Require: Private histogram $h \in \mathbb{R}^N$; Query horizon $m$; $a$, $b$, $L$.
1: Initialize an instance of OnlineFactorization with parameter $c$
2: Initialize an instance of LayeredIDC with parameters $a$, $b$, $L$, using $\mathbb{R}^m$ as the data universe, starting with a point of 0 dimension
3: for $t = 1,\ldots,m$ do
4:     Receive $q_t \in \mathbb{R}^N$
5:     Input $q_t$ to OnlineFactorization
6:     $\ell_t,R_t \leftarrow$ output of OnlineFactorization
7:     Input $(\ell_t,R_th)$ to LayeredIDC, receive output $o_t$.
8:     Release $o_t$.
9: end for

We now prove the privacy and accuracy of this algorithm.

Theorem 1.7 (Main Upper Bound, Formal). Let m≥1m \ge1, γ>0\gamma> 0, ε>0\varepsilon> 0, and δ>0\delta> 0, c>0c > 0, β∈(0,1)\beta\in(0,1). For a sufficiently large universal constant C>0C > 0, set

L=2+⌊log⁡9m⌋,b=max⁡(1,CLε,Cε(Llog⁡1δ+log⁡1δ)),a=2blog⁡mLβ.L = 2 + \lfloor\log_{9} m \rfloor,\qquad b = \max\left(1,C\sqrt{\frac{L}{\varepsilon}},\frac{C}{\varepsilon}\left(\sqrt{L\log\frac{1}{\delta}}+\log\frac{1}{\delta}\right)\right),\qquad a = 2b\log\frac{mL}{\beta}.

Algorithm 6 is (ε,δ)(\varepsilon,\delta)-differentially private. Moreover, for every h∈RNh \in\mathbb{R}^{N} and every adaptive analyst submitting at most mm queries qt∈RNq_t \in\mathbb{R}^{N}, define QQ to be the query matrix of mm rows formed by qtq_t’s. Then, with probability at least 1−β1-\beta,

max⁡t≤m∣ot−⟨h,qt⟩∣=O(γ[log⁡mlog⁡(1/δ)+log⁡mlog⁡(1/δ)ε+log⁡mε+log⁡m]log⁡mlog⁡mβ).\max_{t \le m} \left|o_t-\langle h,q_t\rangle\right| = O\left(\gamma\left[\frac{\log m\sqrt{\log(1/\delta)}+\sqrt{\log m}\log(1/\delta)}{\varepsilon}+\frac{\log m}{\sqrt{\varepsilon}}+\sqrt{\log m}\right]\log\frac{m\log m}{\beta}\right).

where

γ=Θ(γ2(Q)log⁡12+c(γ2(Q)∥q1∥∞)log⁡3N).\gamma=\Theta\left(\gamma_2(Q)\log^{\frac{1}{2}+c}\left(\frac{\gamma_2(Q)}{\|q_1\|_\infty}\right)\log^3 N\right).

Proof. By Lemma 1.6, RthR_t h is a “growing” point for LayeredIDC and for neighboring h,h′h,h'

∥Rth−Rth′∥2≤1,∥ℓt∥2≤γ.\|R_t h-R_t h'\|_2 \le1,\qquad\|\ell_t\|_2 \le\gamma.

By Corollary 3.3, we may assume RthR_t h has at most mm rows. Thus applying Theorem 5.6 finishes the proof.

Non-private Adaptive Query Release

In this subsection we show a direct consequence of the above algorithm for answering statistical queries without privacy. Let us first define statistical queries.

Definition 5.9 (Statistical Query). A statistical query is specified by a function q:U→{0,1}q:\mathcal{U}\to\{0,1\}. For a dataset X=(x1,…,xn)∈UnX=(x_1,\ldots,x_n)\in\mathcal{U}^n, its answer is

q(X):=1n∑i=1nq(xi).q(X):=\frac{1}{n}\sum_{i=1}^{n}q(x_i).

These statistical queries are simply normalized linear queries defined by binary-valued functions. For the matrix representation, the corresponding QQ will simply be binary, and the answer will be Q(X)=QhnQ(X)=\frac{Qh}{n}. In this setting, we assume that each datapoint xix_i inside XX is drawn from some unknown underlying distribution PP over U\mathcal{U}. We say answers to queries are accurate with respect to the population if we use Ex∼P[q(x)]\mathbb{E}_{x\sim P}[q(x)] as the true answer.

We will simply plug our algorithm into the Transfer Theorem, as stated below.

Theorem 5.10 (Transfer Theorem [4]). Let M\mathcal{M} be an interactive algorithm that takes a dataset X∈UnX\in\mathcal{U}^n and answers adaptively chosen statistical queries. Suppose that M\mathcal{M} is

  1. (α,αβ)(\alpha,\alpha\beta)-differentially private with respect to the dataset, and also

  2. (α,αβ)(\alpha,\alpha\beta)-accurate with respect to the dataset for mm queries.

Then M\mathcal{M} is (O(α),O(β))(O(\alpha),O(\beta))-accurate with respect to the population for mm queries.

With the right choice of parameter α\alpha, we have the following corollary:

Corollary 5.11. For any β∈(0,1)\beta\in(0,1) and c>0c>0, there exists an interactive algorithm M\mathcal{M} that takes a dataset X∈UnX\in\mathcal{U}^n, answers an adaptively chosen m×Nm\times N statistical query matrix QQ, and is

(O(γnlog⁡5/4Nmnβ),β)-accurate,\left(O\left(\sqrt{\frac{\gamma}{n}\log^{5/4}N\frac{mn}{\beta}}\right),\beta\right)\text{-accurate},

where

γ=Θ(γ2(Q)log⁡12+cγ2(Q)log⁡3N).\gamma=\Theta\left(\gamma_2(Q)\log^{\frac{1}{2}+c}\gamma_2(Q)\log^3 N\right).

Comparing with [4], we improve the error from O~(mn)\widetilde{O}\left(\sqrt{\frac{m}{n}}\right) to O~(γ22(Q)n)\widetilde{O}\left(\sqrt{\frac{\gamma_{2}^{2}(Q)}{n}}\right), since m\sqrt{m} is an upper bound for the γ2\gamma_{2} norm of any mm statistical queries.

Acknowledgments and AI Use Statement

We started studying the adaptive setting after finishing the paper [NTU26]. Originally, we believed there is a polynomial separation between error bounds achievable in the oblivious and adaptive query settings. We studied a particular lower bound construction in order to show such a separation. While working on a lower bound with GPT6-Astra, the model proposed an algorithm for our lower bound construction, showing that the lower bound we conjectured doesn’t hold. We then used GPT6-Astra to extend the algorithm sufficiently so that it can be combined with the online factorization from [NTU26], and give the main upper bound in this paper. With the help of GPT6-Astra, we simplified the algorithm significantly, connected it with the IDC framework, and reworked the privacy analysis so that it fits within (an extension of) the target charging framework. The two main ideas suggested by the LLM were to use a layered algorithm, and when updating the public point, to use a one-shot update to match exactly to the noisy estimate.

The main ideas of the lower bound proof are ours, but the arguments were simplified and streamlined with the help of GPT6-Astra. In particular, the new version of Lemma 4.2, which can be found in Appendix § 9, is due to GPT6-Astra, whereas our original argument used a modification of the proof in [BDKT12]. The proof of Lemma 4.4 was also given by the same model. We originally had a more combinatorial but significantly more complicated proof of the lower bound for the same choice of query sequences.

We would like to thank Roodabeh Safavi for thoughtful discussion on understanding the online version of Theorem 4.3 of [BDKT12].

Additional Proofs

To prove Proposition 3.2, let us first introduce the following technical lemma.

Lemma A.1 ([NTU26], Lemma 3.3). For any m×Nm \times N matrix QQ, and m×km \times k matrix LL, there exists a factorization Q=LRQ = LR with ∥R∥1→2≤1\lVert R\rVert_{1 \to2} \le1 if and only if LLT⪰qqTLL^{\mathsf{T}} \succeq qq^{\mathsf{T}} for every column qq of QQ. Moreover, if this condition holds, then we can take R=MQR = MQ, where MM is any k×mk \times m matrix satisfying LMLT=LLML^{\mathsf{T}} = L and MLLTMT⪯IMLL^{\mathsf{T}}M^{\mathsf{T}} \preceq I.

Proposition 3.2. There is an online algorithm that achieves value γ2\gamma^2 for the Growing Matrix Problem over QQ if and only if there exists an online factorization mechanism for QQ with factorization value γ\gamma.

Proof of Proposition 3.2. The converse is easy to see by setting Σt=LtLtT\Sigma_t = L_t L_t^{\mathsf{T}} and using Lemma A.1. We only prove the forward direction below.

Using induction on tt, we construct two sequences of matrices L1,…,LmL_1,\ldots,L_m, and M1,…,MmM_1,\ldots,M_m, so that

  • LtL_t and MtM_t are t×tt \times t lower triangular matrices that only depend on Σ1,…,Σt\Sigma_1,\ldots,\Sigma_t;

  • LtL_t is the principal submatrix of Lt+1L_{t+1} consisting of its top tt rows and columns, and MtM_t is the principal submatrix of Mt+1M_{t+1} consisting of its top tt rows and columns;

  • LtLtT=ΣtL_tL_t^{T}=\Sigma_t.

  • LtMtLt=LtL_tM_tL_t=L_t;

  • MtLtM_tL_t is a diagonal matrix with diagonal entries in {0,1}\{0,1\}.

We then set Rt=MtQtR_t=M_tQ_t. It follows from the properties above, and Lemma A.1 that this defines an online factorization mechanism with factorization value γ\gamma.

In the base case t=1t=1, Σ1\Sigma_1 is just a non-negative number σ\sigma such that σ≥max⁡jq1,j2\sigma\ge\max_j q_{1,j}^2 for every entry q1,jq_{1,j} of the first row q1q_1. We set L1=(σ)L_1=(\sqrt{\sigma}) and M1=((σ)+)M_1=((\sqrt{\sigma})^+). Here, and below, we use the notation c+c^+ for

c+={1cc≠0,0c=0.c^+= \begin{cases} \frac{1}{c} & c\ne0,\\ 0 & c=0. \end{cases}

Next we handle the inductive step. Suppose that Σt+1\Sigma_{t+1} is written as

Σt+1=(ΣtxxTσ)\Sigma_{t+1}= \begin{pmatrix} \Sigma_t & x\\ x^T & \sigma \end{pmatrix}

for a tt-dimensional column vector xx, and a scalar σ≥0\sigma\ge0. It is a standard fact that, since Σt+1\Sigma_{t+1} is PSD, xx is in the range of Σt\Sigma_t, and σ≥xTΣt+x\sigma\ge x^T\Sigma_t^+x, where Σt+\Sigma_t^+ is the pseudoinverse of Σt\Sigma_t. We also have the factorization

Σt+1=(I0xTΣt+1)(Σt00c)(IΣt+x01)\Sigma_{t+1}= \begin{pmatrix} I & 0\\ x^T\Sigma_t^+ & 1 \end{pmatrix} \begin{pmatrix} \Sigma_t & 0\\ 0 & c \end{pmatrix} \begin{pmatrix} I & \Sigma_t^+x\\ 0 & 1 \end{pmatrix}

where c=σ−xTΣt+x≥0c=\sigma-x^T\Sigma_t^+x\ge0 is the Schur complement of Σt\Sigma_t in Σt+1\Sigma_{t+1}. We set

Lt+1=(I0xTΣt+1)(Lt00c)=(Lt0xTΣt+Ltc),L_{t+1}= \begin{pmatrix} I & 0\\ x^T\Sigma_t^+ & 1 \end{pmatrix} \begin{pmatrix} L_t & 0\\ 0 & \sqrt{c} \end{pmatrix} = \begin{pmatrix} L_t & 0\\ x^T\Sigma_t^+L_t & \sqrt{c} \end{pmatrix},

and

Mt+1=(Mt00(c)+)(I0−xTΣt+1)=(Mt0−(c)+xTΣt+(c)+).M_{t+1}= \begin{pmatrix} M_t & 0\\ 0 & (\sqrt{c})^+ \end{pmatrix} \begin{pmatrix} I & 0\\ -x^T\Sigma_t^+ & 1 \end{pmatrix} = \begin{pmatrix} M_t & 0\\ -(\sqrt{c})^+x^T\Sigma_t^+ & (\sqrt{c})^+ \end{pmatrix}.

The first two properties are obvious. It is also clear from the factorization of Σt+1\Sigma_{t+1} and the inductive hypothesis that Lt+1Lt+1T=Σt+1L_{t+1}L_{t+1}^{T}=\Sigma_{t+1}. Let us then verify the last two properties. We have

Mt+1Lt+1=(MtLt001{c≠0}).M_{t+1}L_{t+1}= \begin{pmatrix} M_tL_t & 0\\ 0 & \mathbf{1}\{c\ne0\} \end{pmatrix}.

By the inductive hypothesis, this is a diagonal matrix with diagonal entries in {0,1}\{0,1\}. Moreover,

Lt+1Mt+1Lt+1=(I0xTΣt+1)(LtMtLt00c)=Lt+1,L_{t+1}M_{t+1}L_{t+1}= \begin{pmatrix} I & 0\\ x^T\Sigma_t^+ & 1 \end{pmatrix} \begin{pmatrix} L_tM_tL_t & 0\\ 0 & \sqrt{c} \end{pmatrix} =L_{t+1},

where we used the inductive hypothesis to guarantee LtMtLt=LtL_tM_tL_t=L_t. This completes the proof. □\square

Lemma 4.2. For any oblivious sequence of linear queries with query matrix Q∈Rm×NQ\in\mathbb{R}^{m\times N}, for every interactive (ε,δ)(\varepsilon,\delta)-differentially private mechanism MM, and for any c>0c>0, there exists an (ε,δ+c)(\varepsilon,\delta+c)-differentially private data-independent mechanism M′M' such that

err⁡(M′,Q)≤err⁡(M,Q).\operatorname{err}(M',Q)\le\operatorname{err}(M,Q).

Here, we say an online algorithm is data-independent if, upon receiving query qtq_t at time tt, it outputs qt(X)+Wq_t(X)+W where WW does not depend on XX.

Proof of Lemma 4.2. Let us first state the online version of the reduction, Algorithm 7. The algorithm is almost unchanged compared to [BDKT12, ENU20] - it samples a noise vector as the histogram, runs the data-dependent algorithm on it, and applies the resulting error vector to the true answer as additive noise. Note that any valid histogram, that is, a non-negative integer vector, corresponds to a valid dataset.

Algorithm 7 Online version of BDKT reduction

Require: Private histogram h∈N≥0Nh \in\mathbb{N}_{\geq0}^{N}, c>0c > 0, and interactive mechanism M\mathcal{M}.

  1. Sample Z∼Uniform⁡([1/c]N≥0N)Z \sim\operatorname{Uniform}\left(\left[1/c\right]^{\mathbb{N}_{\geq0}^{N}}\right).

  2. Initialize one instance of M\mathcal{M}, using ZZ as the histogram.

  3. for t=1,…,mt = 1, \ldots, m do

  4. Receive query qt∈RNq_t \in\mathbb{R}^{N}.

  5. Input qtq_t to M\mathcal{M} and obtain answer ata_t.

  6. Output bt=⟨qt,h⟩+at−⟨qt,Z⟩b_t = \langle q_t, h\rangle+ a_t - \langle q_t, Z\rangle.

  7. end for

We first prove the privacy. To do so, we view the algorithm in a different way. Let h^:=h−Z\hat{h} := h - Z. Then

Z=h−h^,bt=⟨qt,h^⟩+at.Z = h - \hat{h}, \qquad b_t = \langle q_t, \hat{h}\rangle+ a_t.

Consider an algorithm that first releases h^\hat{h}, then runs M\mathcal{M} on h−h^h - \hat{h} to obtain the answers ata_t. We can then compute answers btb_t that are identically distributed to the output of Algorithm 7 via post-processing: bt=⟨qt,h^⟩+atb_t = \langle q_t, \hat{h}\rangle+ a_t. The privacy claim now follows by composition, since the release of h^\hat{h} is (0,c)(0,c)-differentially private.

Clearly, Algorithm 7 achieves the same error guarantee as M\mathcal{M} when the queries are oblivious. Since ZZ could correspond to a dataset of arbitrary size, we need to take the maximum over all possible dataset sizes. The error bound then clearly follows. □

Lemma 5.4. For every η∈(0,1)\eta\in(0,1) and α>0\alpha> 0, if in every execution,

∑i s.t. Ai(x)∈Tiεi2≤S,q∈(0,1],0≤εi≤εˉ≤1,\sum_{i\ \mathrm{s.t.}\ A_i(x)\in T_i} \varepsilon_i^2 \leq S, \qquad q \in(0,1], \qquad0 \leq\varepsilon_i \leq\bar{\varepsilon} \leq1,

then Algorithm 4 is

((1+α)S2q+2log⁡(1/η)(1+α)Sq, η+exp⁡((log⁡(1+α)−α)Sεˉ2))-DP.\left(\frac{(1+\alpha)S}{2q} + \sqrt{\frac{2\log(1/\eta)(1+\alpha)S}{q}},\ \eta+ \exp\left((\log(1+\alpha)-\alpha)\frac{S}{\bar{\varepsilon}^{2}}\right)\right)\text{-DP}.

Proof of Lemma 5.4. Our proof will be almost identical to the proof of Theorem B.4 in [CL23], but with an updated counting argument that replaces Equation (1) in the original proof. The next claim captures this argument.

Claim A.2 (Privacy Cost Counting). Consider a sequence of calls to randomized algorithms M1,M2,…:X→Y\mathcal{M}_1,\mathcal{M}_2,\ldots: \mathcal{X}\to\mathcal{Y}, and parameters ε1,ε2,…\varepsilon_1,\varepsilon_2,\ldots, s.t. ∀i, εi≤εˉ\forall i,\ \varepsilon_i\leq\bar{\varepsilon}. Algorithm Mi\mathcal{M}_i and the parameter εi\varepsilon_i may depend on the outputs of M1,…,Mi−1\mathcal{M}_1,\ldots,\mathcal{M}_{i-1}. Suppose there is a set Ti⊆YT_i\subseteq\mathcal{Y} (also possibly depending on the outputs of M1,…,Mi−1\mathcal{M}_1,\ldots,\mathcal{M}_{i-1}) such that, for any input x∈Xx\in\mathcal{X}, conditional on any possible sequence of outputs of M1,…,Mi−1\mathcal{M}_1,\ldots,\mathcal{M}_{i-1}, Mi(x)∈Ti\mathcal{M}_i(x)\in T_i with probability at least qq. Let BiB_i be the indicator variable for Mi(x)∈Ti\mathcal{M}_i(x)\in T_i. If on every execution

∑iεi2Bi≤S,\sum_i \varepsilon_i^2 B_i \leq S,

then for every $\alpha > 0

Pr⁡[∑iεi2>(1+α)Sq]≤exp⁡((log⁡(1+α)−α)Sεˉ2).\Pr\left[\sum_i \varepsilon_i^2 > (1+\alpha)\frac{S}{q}\right] \leq\exp\left((\log(1+\alpha)-\alpha)\frac{S}{\bar{\varepsilon}^{2}}\right).

Proof. Let the random variable πi\pi_i denote the sequence of outputs of M1,…,Mi−1\mathcal{M}_1,\ldots,\mathcal{M}_{i-1}, with π0\pi_0 denoting the empty sequence. Observe that, conditioning on calls before the ii-th call, we have

E[e−λεi2Bi∣πi]≤1−q(1−e−λεi2)≤exp⁡(−qεi2(1−e−λεi2)ε2).\mathbb{E}\left[e^{-\lambda\varepsilon_i^2 B_i}\mid\pi_i\right] \leq1-q\left(1-e^{-\lambda\varepsilon_i^2}\right) \leq\exp\left(-\frac{q\varepsilon_i^2\left(1-e^{-\lambda\varepsilon_i^2}\right)}{\varepsilon^2}\right).

Taking λ=log⁡(1+α)ε2\lambda= \frac{\log(1+\alpha)}{\varepsilon^2}, and multiplying the above bound over ii, we obtain

E[exp⁡(q(1−11+α)∑iεi2−log⁡(1+α)∑iεi2Biε2)]≤1.\mathbb{E}\left[\exp\left(\frac{q\left(1-\frac{1}{1+\alpha}\right)\sum_i\varepsilon_i^2-\log(1+\alpha)\sum_i\varepsilon_i^2B_i}{\varepsilon^2}\right)\right]\leq1.

Since ∑iεi2Bi≤S\sum_i\varepsilon_i^2B_i\leq S, if ∑iεi2>(1+α)Sq\sum_i\varepsilon_i^2>(1+\alpha)\frac{S}{q}, then we have

q(1−11+α)∑iεi2−log⁡(1+α)∑iεi2Biε2≥S[α−log⁡(1+α)]ε2,\frac{q\left(1-\frac{1}{1+\alpha}\right)\sum_i\varepsilon_i^2-\log(1+\alpha)\sum_i\varepsilon_i^2B_i}{\varepsilon^2}\geq\frac{S[\alpha-\log(1+\alpha)]}{\varepsilon^2},

and the claim follows from Markov’s Inequality.

We now show what modification needs to be made to the original proof. Similarly to the original proof, we have the same simulator, but we track the accumulated squared privacy cost instead of the number of target hits, and terminate the simulator if this exceeds (1+α)Sq\frac{(1+\alpha)S}{q}. By Claim A.2, this early stop can happen with probability no more than exp⁡((log⁡(1+α)−α)Sε2)\exp\left((\log(1+\alpha)-\alpha)\frac{S}{\varepsilon^2}\right). Applying fully adaptive composition ([WRRW23, Theorem 2]) finishes the proof.

References

  1. [1]Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. Towards instance-optimal private query release. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2480–2497. SIAM, 2019. 1arxiv.org/abs/1811.03763
  2. [4]Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the 48th Annual ACM Symposium on the Theory of Computing, STOC ’16, pages 1046–1059, Cambridge, MA, 2016. ACM. 1, 5.10, 5.5
  3. [5]Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages 1306–1325, Philadelphia, PA, 2017. SIAM. 1, 1, 1
  4. [6]Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In 46th Annual ACM Symposium on the Theory of Computing, STOC ’14, pages 1–10, New York, NY, USA, 2014. 1
  5. [9]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):26, 2011. 1
  6. [10]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 117–126, 2015. 1arxiv.org/abs/1411.2664
  7. [12]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC ’06, pages 265–284, Berlin, Heidelberg, 2006. Springer. 1, 1.1
  8. [13]Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Symposium on Theory of Computing (STOC), pages 715–724. ACM, 2010. 1DOI
  9. [14]Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014. 1, 1, 2.1, 2.2
  10. [15]Alexander Edmonds, Aleksandar Nikolov, and Jonathan R. Ullman. The power of factorization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 425–438. ACM, 2020. 1, 1, 1, 1, 1, 4, 4, 4.2, 4, Aarxiv.org/abs/1911.08339
  11. [16]Andrew Gelman and Eric Loken. The statistical crisis in science. Am Sci, 102(6):460, 2014. 1
  12. [17]Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of Cryptography, volume 7194 of Lecture Notes in Computer Science, pages 339–356. Springer, 2012. 1, 1
  13. [18]Moritz Hardt and Guy Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS, pages 61–70, 2014. 1
  14. [19]Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, 2010. 1arxiv.org/abs/0907.3754
  15. [20]Richard M. Karp. On-line algorithms versus off-line algorithms: How much is it worth to know the future? In Jan van Leeuwen, editor, Algorithms, Software, Architecture - Information Processing ’92, Volume 1, Proceedings of the IFIP 12th World Computer Congress, Madrid, Spain, 7-11 September 1992, volume A-12 of IFIP Transactions, pages 416–429. North-Holland, 1992. 4DOI

Paper details

vlnc:W_n34dbfs8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT6-Astra

View statement
Looking for related papers…
Contents