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 , and say and are neighboring if one can obtain from 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 is -differentially private if, for any pair of neighboring datasets , , and every measurable set of outputs,
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 , where and the data universe has finite size . Note that we adopt the add/remove definition of neighboring datasets, so the dataset size 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 . For a dataset , its answer is
Counting queries are the special case when 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 is the vector , where counts the number of occurrences of in , i.e., for .
A linear query can then be viewed as the inner product of a query row vector and the histogram 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 , the query matrix of the workload is defined by . The answer to the workload is
Note that, for any two neighboring datasets and , the corresponding histograms satisfy . This easily implies that , where is the largest norm of a column of . I.e., the -sensitivity of is .
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 where is a noise vector from some distribution that depends on but not on . A simple example of such a mechanism is the Gaussian noise mechanism [14], in which is a vector of independent and identically distributed (i.i.d.) Gaussians, with mean 0, and standard deviation scaled to the -sensitivity of . 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 -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 , one can find a factorization , then answer , where is again a vector of i.i.d. Gaussians, this time with standard deviation scaled proportionally to . The maximum noise variance over queries in the workload achieved by this mechanism is proportional to , where is the maximum norm of a row of . Optimizing the error of a factorization mechanism then corresponds to minimizing over all choices of and that give . The minimum such value is denoted , the norm of . 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 in order to find its optimal factorization . 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 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 have rows , revealed sequentially, and let consist of its first rows. The number is not known in advance.
Starting from the empty matrix , an online factorization algorithm processes each arriving row by appending additional rows to to obtain , and producing a row vector such that
Let contain the rows , padded with zeros as necessary. The algorithm achieves factorization value on if
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 . There exists an online factorization algorithm whose factorization value on every matrix satisfies
This algorithm first solves a semidefinite program online to obtain a factorization in which the column norms of 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 and . We compute , where is a vector of i.i.d. Gaussian noise variables, one for each row of . We can do so by just computing answers for the new rows in and adding Gaussian noise to them. Then we take an inner product of and to compute an answer to . 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 to correlate with the noise , 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 at time step , outputs before receiving the next query, while keeping the entire transcript private, and every answer 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 over any dataset with error
where is the mechanism’s output at time .
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 . 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 at each time step . The online factorization framework ensures that , and for any pair of neighbouring we have . One can view as a query, and as a private point . Then our problem translates to a problem where we are given a point as the private input, neighboring inputs differ by at most in distance, and queries ask for an inner product of with a vector of norm at most . We use a modified version of IDC to answer these queries.
The original Euclidean IDC algorithm keeps a public dataset and tries to answer each query with it. Upon receiving query it tries to answer it with , 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 to the query, then updates the public dataset by shifting a fixed amount toward the direction of . With some minor modification, we can use this method to achieve a competitive ratio of . Instead of using the Euclidean IDC as a blackbox, we introduce a layered structure: we maintain a partition of , where is the dimension of ; 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 . 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 according to the layers - within each layer, project onto the layer’s subspace and then take the 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 sensitivity of , 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 , any private mechanism that answers online queries needs error of
on some obliviously chosen sequence of queries .
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 for the worst case competitive ratio for any deterministic online factorization algorithm.
Related Works
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 -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 adaptively chosen online threshold queries of , where the dataset points are from the infinite universe . 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 , we use to denote the set of the first natural numbers.
Throughout the paper, refers to the size of the dataset, refers to the number of queries and refers to the size of the universe .
We use to denote the projection matrix onto a subspace .
We use to denote that is a positive semidefinite (PSD) matrix and to denote that . The notation is equivalent to .
For two quantities and that may depend on other parameters, we use the notation when there is an absolute constant such that ; the notation is equivalent to .
For a vector , we use the standard notation for the , and norms:
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 factorization norm of an matrix as
Recall that is the maximum norm of a column of , and is the maximum norm of a row of .
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 have sensitivity at most , where
For any , the mechanism
is -differentially private.
Lemma 2.2 (Post-processing [14]). If is -differentially private and is a mapping that does not depend on , then is -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 and an interactive data analyst .
We first consider an oblivious analyst that determines the sequence of queries given to independently of the answers gives. Without loss of generality, we can assume that 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 is and choose the queries with this knowledge.
We also consider adaptive analysts that determine the next query to be given to based on the answers to previous queries, as shown in Algorithm 2.
Definition 2.3 (Privacy of Interactive Algorithms). An interactive algorithm is -differentially private (for non-adaptive/adaptive analysts) if for every dataset , and for every (resp. non-adaptive/adaptive) analyst , the algorithm is -differentially private.
Similarly, we can define accuracy for interactive algorithms via the same meta-algorithm:
Algorithm 1 The meta-algorithm for oblivious analysts
Require: Dataset
chooses queries .
for do
Give to and receive an answer .
end for
return .
Algorithm 2 The meta-algorithm for adaptive analysts
Require: Dataset
.
for do
Give to and receive a query .
Give to and receive an answer .
end for
return .
Definition 2.4 (()-Accuracy of Interactive Algorithms). An interactive algorithm is -accurate for queries against non-adaptive/adaptive analysts if for every dataset , and every (resp. non-adaptive/adaptive) analyst , if is the queries submitted by ,
where is some real-valued function of .
Definition 2.5 ( Error of Interactive Algorithms). An interactive algorithm has error at most for queries against oblivious/adaptive analysts if, for every dataset and every (resp. oblivious/adaptive) analyst ,
where is some real-valued function of . The expectation is over the randomness of both and . Moreover, we define the error for the worst case dataset to be
Moreover, when the adversary is oblivious, since the queries do not depend on the answers, we can denote the error as . We remark that the supremum in 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 arriving online, we say an online algorithm that outputs a sequence of positive semidefinite (PSD) matrices achieves value for the Growing Matrix Problem over if, for each ,
is a PSD matrix;
is the principal submatrix of consisting of its top rows and columns;
(and, therefore, every ) has all its diagonal entries bounded by , for a non-negative number ;
if is the submatrix of that has arrived by time step , and is a column of , then .
The Proposition below states the equivalence between the Growing Matrix Problem and the online factorization problem. At a high level, corresponds to , and its growing property allows us to construct the matrix so that only new rows are being appended to it over time.
Proposition 3.2. There is an online algorithm that achieves value for the Growing Matrix Problem over if and only if there exists an online factorization mechanism for with factorization value .
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 , appends at most one row to .
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 by only one at each time step , and therefore, we also increase the number of rows of 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 be an online -differentially private algorithm answering obliviously chosen linear queries on datasets . For every smaller than some absolute constants, there exists a deterministic online factorization algorithm that on every query matrix achieves factorization value
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 , for every interactive -differentially private mechanism , and for any , there exists an -differentially private data-independent mechanism such that
Here, we say an online algorithm is data-independent if, upon receiving query at time , it outputs where does not depend on .
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 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 adding noise , independent of the dataset , to . For some absolute constant , we take
where contains all the noises up to time . By the same covariance bound in [15 Lemma 27], we obtain
Furthermore, we can bound the diagonal entries
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 such that
For a dataset , its answer is
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 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 : assume is a power of and construct a full binary tree, where the root node represents , its children represent and , etc., down to the leaf nodes that represent singleton sets for . 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 .
As a direct consequence, the worst case competitive ratio of any deterministic online factorization algorithm is .
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 , after asking the threshold query corresponding to a range , the adversary selects one of and , the left and right disjoint halves of . Let us define
The above vector is an average of the columns of inside the range . We will show that is strictly larger than . We know that , where is the threshold query corresponding to the range . By the definition of a threshold query, is a binary vector that has all ones up to the middle point of , and all zeros after that. Then it is clear that
and, therefore, by Cauchy-Schwarz,
By the parallelogram identity, we have
Thus at each time there exists s.t.
At each step, the adversary chooses this , and the average column norm squared over the current range grows by an additive factor of at least . Note that the online factorization algorithm only appends rows to the 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 is
Hence, denoting the number of queries by , we have
To prove the second part of the lemma, observe that any path of the tree corresponds to a sequence of threshold queries, and the norm of the corresponding query matrix is known to be only 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 bounded by absolute constants, for any -DP online mechanism , there exists a sequence of obliviously chosen linear queries over a universe of size , such that
Remark 4.5. One can show that for sufficiently small , no -differentially private algorithm can achieve error
with probability more than on all sequences of queries, by clipping the noise after applying Lemma 4.2.
Adaptive Private Query Release
In this section, we consider the following problem: we hold a private point , where neighboring points have distance at most 1 from each other. At each time step , we receive a query . We want to release a private estimate of , and we give accuracy bounds assuming queries have norm at most . 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 (-target [CL23, Definition 2.1]). Let be a randomized algorithm, and let , . A measurable set is a -target with parameter for if, for every neighboring pair , there exist , a distribution on , and an -DP mechanism , such that if are the distributions of respectively, then for every ,
An output in 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 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 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 be an -DP algorithm, where is nonempty and . Then is a -target with parameter for .
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 , a unit direction , and public thresholds , we define to be a noisy test for whether lands inside . When this noisy test does not report inside, it outputs a noisy estimate of . The parameter controls the magnitude of noises. Every call to this algorithm uses fresh independent randomness.
Algorithm 3 InsideOrRelease
Input: , , , .
Draw
if then
return Inside.
else
return .
end if
We now state the privacy guarantee of this subroutine.
Lemma 5.3 (Indistinguishability of InsideOrRelease). Fix , , and a pair . The outputs of Algorithm 3 over and are -indistinguishable, where we say two distributions and are -indistinguishable if for any measurable subset ,
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 , i.e. when the above test releases a real number. In fact, later in this section we choose appropriate parameters so that is a -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 ; horizon .
for do
Receive , chosen according to the preceding transcript, where is -DP, is determined by the history before time , and is a -target with parameter for .
Release
end for
Lemma 5.4 (Privacy of weighted target charging with bounded privacy loss). For every and , if in every execution,
then Algorithm 4 is
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 , where initially . We partition the data universe into orthogonal subspaces . Initially, and . On each query , the algorithm goes through every , and tries to examine if and are far in the direction of , i.e. projected to subspace and renormalized. If they are close, can be used to answer the query inside this subspace. Otherwise, we release a noisy estimate . We shift alongside such that , and kick out the line through direction to the next subspace. Effectively, after identifying a bad direction, we pay some privacy cost to rewrite 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 , consider the potential
which is the distance between the public and private points inside subspace . 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, and 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 ; Query horizon ; parameters .
▷ Public synthetic point
▷ The final layer is never tested
for do
Receive
for do
▷ Projection onto the current layer
if then
;
if then
▷ Kick out of layer
end if
end if
end for
Release
end for
The parameters and are for controlling, respectively, the width of the inside range and the magnitude of the noise of . 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 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 by , and let be the unit direction used in call . For each layer , let be the set of indices of calls that kick a direction out of . On every execution, the directions are orthonormal within each layer .
Fix neighboring points , and assign call the pairwise privacy parameter
Then , and on every execution,
Equivalently, since each numerical output is a target hit and causes exactly one kick-out,
Proof. The orthonormal property holds because, once is kicked out of , all future directions used to call InsideOrRelease inside layer lie inside . The fact that 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 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 InsideOrRelease 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 , , , and , . For a sufficiently large universal constant , set
Then Algorithm 5 is -differentially private. Moreover, for every and every adaptive analyst submitting at most queries with ,
Proof. Since, by Lemma 5.2, , each real output of InsideOrRelease is a -target. Combining Lemma 5.5 with Lemma 5.4, and choosing
proves the privacy guarantee. To understand the intuition behind the parameter choices here and in the theorem statement, the choice of bounds the failure probability, i.e. the term; the first term of is to bound each by 1; the other two terms are to give us the term in -differential privacy.
Now we prove the error bound. There are at most Laplace draws, and each satisfies . Thus, by the choice of and a union bound, all the Laplace noises have absolute value less than with probability at least . We bound the error assuming this event happens.
For each layer , recall that the potential is
Observe that whenever the kick-out happens at layer , drops by at least , and increases by at most . Since is non-negative at every time step, this means the number of dimensions that enter each layer , , is at most -th of the number of dimensions that enter the previous layer . Moreover, at most dimensions can enter layer 2: Layer 1 has unbounded potential but only dimensions have to be kicked out of it. Consequently, at most directions can enter layer , so this layer must always be empty.
At any fixed layer , whenever InsideOrRelease outputs Inside, or immediately after a kick-out is performed, it is clear that
Summing over layers using the orthogonality between layers and then scaling by finishes the proof.
Remark 5.7. In particular, the maximum error is
with probability at least , and we can take .
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 has growing dimension. In particular, for any time , the algorithm receives a pair such that there exists ,
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 as being fixed ahead of time, and the dimensions in are introduced into layer 1 at time step . At most 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 , where neighboring histograms differ at most by 1 at one entry. At each time we receive a query and we want to release a private estimate of .
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 , and uses as the point , 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 , , , and , , . For a sufficiently large universal constant , set
Algorithm 6 is -differentially private. Moreover, for every and every adaptive analyst submitting at most queries , define to be the query matrix of rows formed by ’s. Then, with probability at least ,
where
Proof. By Lemma 1.6, is a “growing” point for LayeredIDC and for neighboring
By Corollary 3.3, we may assume has at most 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 . For a dataset , its answer is
These statistical queries are simply normalized linear queries defined by binary-valued functions. For the matrix representation, the corresponding will simply be binary, and the answer will be . In this setting, we assume that each datapoint inside is drawn from some unknown underlying distribution over . We say answers to queries are accurate with respect to the population if we use as the true answer.
We will simply plug our algorithm into the Transfer Theorem, as stated below.
Theorem 5.10 (Transfer Theorem [4]). Let be an interactive algorithm that takes a dataset and answers adaptively chosen statistical queries. Suppose that is
-differentially private with respect to the dataset, and also
-accurate with respect to the dataset for queries.
Then is -accurate with respect to the population for queries.
With the right choice of parameter , we have the following corollary:
Corollary 5.11. For any and , there exists an interactive algorithm that takes a dataset , answers an adaptively chosen statistical query matrix , and is
where
Comparing with [4], we improve the error from to , since is an upper bound for the norm of any 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 matrix , and matrix , there exists a factorization with if and only if for every column of . Moreover, if this condition holds, then we can take , where is any matrix satisfying and .
Proposition 3.2. There is an online algorithm that achieves value for the Growing Matrix Problem over if and only if there exists an online factorization mechanism for with factorization value .
Proof of Proposition 3.2. The converse is easy to see by setting and using Lemma A.1. We only prove the forward direction below.
Using induction on , we construct two sequences of matrices , and , so that
and are lower triangular matrices that only depend on ;
is the principal submatrix of consisting of its top rows and columns, and is the principal submatrix of consisting of its top rows and columns;
.
;
is a diagonal matrix with diagonal entries in .
We then set . It follows from the properties above, and Lemma A.1 that this defines an online factorization mechanism with factorization value .
In the base case , is just a non-negative number such that for every entry of the first row . We set and . Here, and below, we use the notation for
Next we handle the inductive step. Suppose that is written as
for a -dimensional column vector , and a scalar . It is a standard fact that, since is PSD, is in the range of , and , where is the pseudoinverse of . We also have the factorization
where is the Schur complement of in . We set
and
The first two properties are obvious. It is also clear from the factorization of and the inductive hypothesis that . Let us then verify the last two properties. We have
By the inductive hypothesis, this is a diagonal matrix with diagonal entries in . Moreover,
where we used the inductive hypothesis to guarantee . This completes the proof.
Lemma 4.2. For any oblivious sequence of linear queries with query matrix , for every interactive -differentially private mechanism , and for any , there exists an -differentially private data-independent mechanism such that
Here, we say an online algorithm is data-independent if, upon receiving query at time , it outputs where does not depend on .
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 , , and interactive mechanism .
Sample .
Initialize one instance of , using as the histogram.
for do
Receive query .
Input to and obtain answer .
Output .
end for
We first prove the privacy. To do so, we view the algorithm in a different way. Let . Then
Consider an algorithm that first releases , then runs on to obtain the answers . We can then compute answers that are identically distributed to the output of Algorithm 7 via post-processing: . The privacy claim now follows by composition, since the release of is -differentially private.
Clearly, Algorithm 7 achieves the same error guarantee as when the queries are oblivious. Since 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 and , if in every execution,
then Algorithm 4 is
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 , and parameters , s.t. . Algorithm and the parameter may depend on the outputs of . Suppose there is a set (also possibly depending on the outputs of ) such that, for any input , conditional on any possible sequence of outputs of , with probability at least . Let be the indicator variable for . If on every execution
then for every $\alpha > 0
Proof. Let the random variable denote the sequence of outputs of , with denoting the empty sequence. Observe that, conditioning on calls before the -th call, we have
Taking , and multiplying the above bound over , we obtain
Since , if , then we have
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 . By Claim A.2, this early stop can happen with probability no more than . Applying fully adaptive composition ([WRRW23, Theorem 2]) finishes the proof.
References
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [16]Andrew Gelman and Eric Loken. The statistical crisis in science. Am Sci, 102(6):460, 2014. 1
- [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
- [18]Moritz Hardt and Guy Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS, pages 61–70, 2014. 1
- [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
- [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