Robust Algorithms on Adaptive Inputs from Bounded Adversaries
Authors: Yeshwanth Cherapanamjeri
Sandeep Silwal
David Woodruff
Fred Zhang
Qiuyi Zhang
Samson Zhou
Venue: ICLR 2023 poster (2023)
Keywords: streaming algorithms
adversarial robustness
sketching
kernel density estimation

Abstract: We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust linear algebraic algorithms when the updates to the input are sparse but given by an adversary with access to a query oracle. We also study robust algorithms in the standard centralized setting, where an adversary queries an algorithm in an adaptive manner, but the number of interactions between the adversary and the algorithm is bounded. We first recall a unified framework of (Hassidim et al., 2020; Beimel et al., 2022; Attias et al., 2023) for answering $Q$ adaptive queries that incurs $\widetilde{\mathcal{O}}(\sqrt{Q})$ overhead in space, which is roughly a quadratic improvement over the na\"{i}ve implementation, and only incurs a logarithmic overhead in query time. Although the general framework has diverse applications in machine learning and data science, such as adaptive distance estimation, kernel density estimation, linear regression, range queries, point queries,  and serves as a preliminary benchmark, we demonstrate even better algorithmic improvements for (1) reducing the pre-processing time for adaptive distance estimation and (2) permitting an unlimited number of adaptive queries for kernel density estimation. Finally, we complement our theoretical results with additional empirical evaluations. 

ROBUST ALGORITHMS ON ADAPTIVE INPUTS FROM
BOUNDED ADVERSARIES
Yeshwanth Cherapanamjeri UC Berkeley
Sandeep Silwal MIT sil silwal @mi t. edu
David P. Woodruff
Carnegie Mellon University
yeshwanth@berkelley edu
dwoodruf eeccoduf@aancee @andrew. cmu edu
Fred Zhang UC Berkeley
Qiuyi (Richard) Zhang Google Research giuyiz@google. com
Samson Zhou
UC Berkeley and Rice University samsonzhou@ gmail. com
z0@errkeley.edu
ABSTRACT
We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust linear algebraic algorithms when the updates to the input are sparse but given by an adversary with access to query oracle. We also study robust algo- rithms in the standard centralized setting, where an adversary queries an algorithm in an adaptive manner, but the number of interactions between the adversary and the algorithm is bounded. We first recall a unified framework of (Hassidim et al., 2020; Beimel et al., 2022; Attias et al., 2023) for answering Q adaptive queries that incurs ((VQ) overhead space, which is roughly a quadratic improvement over the naïve implementation, and only incurs a logarithmic overhead in query time. Although the general framework has diverse applications in machine learning and data science, such as adaptive distance estimation, kemnel density estimation, linear regression, range queries, point queries, and serves as a preliminary benchmark, we demonstrate even better algorithmic improvements for (1) reducing the pre- processing time for adaptive distance estimation and (2) permitting an unlimited number of adaptive queries for kernel density estimation. Finally, we complement our theoretical results with additional empirical evaluations.
INTRODUCTION
Robustness to adaptive inputs or adversarial attacks has recently emerged as an important desirable characteristic for algorithm design. An adversarial input can be created using knowledge of the model to induce incorrect outputs on widely used models, such as neural networks (Biggio et al., 2013; Szegedy et al., 2014; Goodfellow et al., 2015; Carlini & Wagner, 2017; 7; Madry et al., 201 8). Adversarial attacks against machine learning algorithms in practice have also been documented in applications such network monitoring (Chandola et al., 2009), strategic classification (Hardt et al., 2016), and autonomous navigation (Papernot et al., 2016; Liu et al., 2017; Papernot et al., 2017). The need for sound theoretical understanding of adversarial robustness is also salient in situations where successive inputs to an algorithm can be possibly correlated; even if the input is not adversarially generated, a user may need to repeatedly interact with a mechanism in way such that future updates may depend on the outcomes of previous interactions (Mironov et al., 201 I; Gilbert er al., 2012 2; Bogunovic et al., 2017; Naor & Yogev, 2019; Avdiukhin et al., 2019). Motivated by both practical needs and a lack of theoretical understanding, there has been a recent flurry of theoretical studies of adversarial robustness. The streaming model of computation has especially received significant attention Ben-Eliezer et al. (2021); ); Hassidim et al. (2020); Woodruff & Zhou (2021); Kaplan et al. (2021); Braverman et al. (2021); Chakrabarti et al. (2022); Ajtai et al. (2022); Chakrabarti et al. (2022); Ben-Eliezer et al. (2022); Assadi et al. (2022); Attias et al. (2023); Dinur et al. (2023); Woodruff et al. (2023). More recently. there have also been a few initial results for dynamic algorithms on adaptive inputs for graph algorithms (Waje, 2020; Beimel et al., 2021; Bernstein et al., 2022). These works explored the capabilities and limits of algorithms for adversaries that were freely able to choose the input based previous outputs by the algorithm.

---

However, in many realistic settings, adversary is limited in its abilities. For example, adversarial attacks in machine learning are often permitted to only alter the "true" input by a small amount bounded in norm. For the Lo norm, this restriction means that the adversary can only add sparse noise to the true input. More generally, it seems reasonable to assume that adversarial input is generated from source that has bounded computation time bounded interactions with honest algorithm.
1.1 OUR CONTRIBUTIONS
In this paper, we study algorithms robust to adaptive/adversarial input generated from sources with bounded capabilities. We first study dynamic algorithms for adaptive inputs from source that is restricted in sparsity. Namely, we consider robust linear algebraic algorithms when the updates to the label can be adversarial but are restricted in sparsity. We then study robust algorithms in the standard centralized setting, where an adversary queries an algorithm an adaptive manner, but the number of interactions between the adversary and the algorithm is bounded. We first show that combining novel subroutines for each of these problems in conjunction with a simple but elegant idea of using differential privaey to hide the internal randomness of various subroutines previously used by Hassidim et al. (2020); Beimel et al. (2022); Attias et al. (2023) suffices to achieve robust algorithms across these different settings.
Dynamic algorithms on adaptive input for regression. Motivated by the problem of label shift in machine learning, we consider a dynamic version of least-squares regression, where the labels get updated. In this model, we are given fixed design matrix and target label that receives sequence of updates. After each one, the algorithm is asked output an estimate of the optimal least-squares objective. The goal of the algorithm is to maintain the objective value within multiplicative factor (1 + =) to the optimal.
More specifically, the algorithm is given a fixed design matrix A E Rxd with 2 d and initial response vector (i.e., label) ((), which receives updates over time. We are interested in estimating the least-squares objective value F(A, b) min Ax - blß as the target label b undergoes updates.
xER
The updates to b are adaptively chosen by an adversary but can only affect at most K entries of b per step. Formally, on the i-th round:
(1) The adversary provides an update K entries of (i-1), possibly depending on all previous outputs of the algorithm.
(2) The algorithm updates its data structure and outputs an estimate F, of F; = F (A).
(3) The adversary observes and records the output F..
The goal of the adversary is to create a sequence of labels (b(O) that induces the algorithm output inaccurate estimate. To deal with adaptivity, na've idea is treat each step as an independent least-squares regression problem. However, this approach uses a completely new approximation of the objective value for each update, which seems potentially wasteful. On the other hand, any randomness that is shared by computations over multiple updates can potentially be leveraged by the adversary to induce an incorrect output.
Our main result is an algorithm that beats the naive algorithm in this challenging, adaptively adver- sarial setting. We provide a general result with run-time dependence on n, d, K, and the number of nonzero entries in A, nnz(A) A..
Theorem 1.1 (Informal: see Theorem 2.1). Let x(A) O(1) and e E (0, 1). There exists a dynamic algorithm that given adaptively chosen K K-sparse updates to b and fixed design matrix A E Raxd least-squares
outputs a (1 + =) approximation to the least- squares objective F(A, b()) every round with high
probability. The algorithm uses Ö (VK (VKunzz unz( //2²)) amortized time per step of update.
Specifically, the update time is d when K < d and n = Od)) and square root of the input sparsity when K O(1). Notice that this significantly betters the navve approach of treating each step independently and solving for the least-square objective, which requires mnz(A, + +oly(d) time by sketching (Woodruff (2014)).
2

---

We mention that recent work by Jiang et al. (2022) considers row-arrival model for dynamic linear regression. Our setting is different since we allow arbitrary updates to the target label, whereas in their setting the design matrix undertakes incremental change. We note that their algorithm maintains a solution vector, while we focus on the cost only.
Adaptive query framework. We then consider robust algorithms in the standard centralized setting, where an adversary queries an algorithm in an adaptive manner. In many key algorithmic applications, randomization necessary achieve fast query time and efficient storage. This necessitates the need for robust versions of these algorithm which can efficiently employ the power of randomness while also being accurate across multiple possibly correlated inputs. Our main parameters of interest are query time and the space used by robust algorithm compared to their naïve, non-robust, counterparts.
Formally, we define the model as a two-player game between an algorithm HonestAlg over data set X and an adversary A that makes adversarial queries about X to HonestAlg. At the beginning of the game, HonestAlg uses pre-processing time to compute a data structure D from X answer future queries from A. The game then proceeds in at most Q rounds for some predetermined Q, so that in the t-th round, where t E [Q]:
(1) A computes query qe on X, which depends all previous responses from HonestAlg.
(2) AogestAlg uses D to output a response de to query qt-
(3) A observes and records the response de.
The goal of is to formulate query qe for which the algorithm HonestAlg produces incorrect response d, We remark that the algorithm may not have access to X, after constructing D, to respond to the query q.. On the other hand, A can randomness of the data structure D and make future queries accordingly. In this case, the analysis of many randomized algorithms fails because it assumes that the randomness of the algorithm is independent of the input. Consequently, it does not seem evident how to handle Q adaptive queries without implementing Q instances of non-adaptive data structure, i.e., each instance handles separate query. Thus, natural question to ask is whether a space overhead of (2(Q) is necessary.
previous outputs possibly determine the internal
As preliminary benchmark, we show that a space overhead of (Q()) unnecessary by giving unified framework with only an Ô (VQ) space overhead.
Theorem 1.2.
Given data structure D that answers a query q with probability at least & using space S and query time T, there exists a data structure that answers Q adaptive queries, with high probabil- ity, ie., poly(n.Q]) using space O (SVQ log(nQ)) and query time Ô (T log(nQ) + log (nQ)).
Theorem 1.2 invokes the framework of Hassidim et al. (2020); Beimel et al. (2022); Attias et al. (2023) to the centralized setting, where number of queries are made only after the data structure is created.
To concretely instantiate our framework and state example, we consider the adaptive distance estimation problem defined as follows. In the adaptive distance estimation problem, there exists a set X (x(1).... xx")} of n points in Rd. We are also given an accuracy parameter E > 0. A query is of the form q, and the algorithm must output a (1 + appppooxiintionn to ||x(0) - qllp for all The trivial solution of storing all points and computing all n distances query point uses space and
query time O (nd). Cherapanamjeri & Nelson (2020) improved the query time O (ntd) at the
cost of using δ (i+t)dd space and Ö number of queries. By comparison, our data structure handles Q queries of approximate distances from a specified point in X, using query time ① (atd), pre-processing time ndve and space
nd? 2
pre-processing time, while permitting an arbitrary
g²
(n+d)/Q Thus, in the regime where d >>>>> n/Q, our data structure already improves on the work of Cherapanamjeri & Nelson (2020).
A noticeable weakness of our construction is that the Q queries return only the approximate distance between a query point and a single point in X, whereas Cherapanamjeri & Nelson (2020) outputs approximate distances to all points in X. Moreover, Cherapanamjeri & Nelson (2022) subsequently improve the pre-processing time to ① Thus we open up our framework to (1) show that it can
3

---

be further improved to handle the case where we return the approximate distances of all points in X from Q adaptive query points and (2) achieve pre-processing time O
nd 22)
Theorem 1.3. There is a data structure which, when instantiated with dataset X = (zi C Rd and query bound Q I d, answers any sequence of Q adaptively chosen distance estimation queries correctly with probability at least 0.99. Furthermore, the space complexity of the data structure is Ö(s- .n/Q) and the setup and query times are 0 .nd) and O(= (n + dd), respectively.
Another application of our framework is the adaptive kernel density estimation problem, where there exists a set X = fxx")) ................................ x(")} } of points in Id and the goal is to output (1 + =+ approxxmaaaoonnn to the quantity Lie(n] ((x("), q), for an accuracy parameter ε > 0, a query q, and a kernel function k, under the promise that the output is at least some threshold T > O. Backurs et al. (2019) give an algorithm for kernel density estimation that uses O (TEA)) space and O VTE?
query time, improving
over the standard algorithm that samples O ( (-2) points and then uses O Te2 the empirical kernel density. However, the analysis for both of these algorithms fails for the adaptive setting, where there can be dependencies between the query and the data structure. By using the data structure of Backurs et al. (2019) as a subroutine, our framework immediately implies an algorithm
d
query time to output
for adaptive kernel density estimation that uses ① TE" space and O d'log Q
query time answer
VTS4
each of Q adaptive queries. In this case, we are again able to go beyond our framework and give a data structure that handles an unlimited number of adaptive kernel density queries:
Theorem 1.4. Suppose the kernel function is L-Lipschitz in the second variable for some L > 0, i.e. |k(x, - k(x, z) < L|yy - z||2 for all x. y. E Rd. Moreover, suppose that for all ||x 2x-yl ylla S we have k(x,y) S 3. Then an algorithm that produces a kernel density estimation data structure D that is L.-Lpsschitz over a set X of points with diameter at most A and oulpuls a (1 -aprrrxippiiiiiiionn to KDE queries with value at least I with probability at least query time T(n,E, E, log 8). then there exists KDE data structure that with probability at least 0.99, outputs a (1 + apprroxximatio to any number of KDE queries with value at least T using space (A+p)L)
T.
5 using space S(n, e, T. log 6) and
n,, (c) (c), (T), O log ET )) and query time T (n, O (n,0 (c) (T) (d (dlog (A+p)L )) ET
Additionally, we show that our framework guarantees adversarial robustness for a number of other important problems such as nearest neighbor search, range queries, point queries, matrix-vector norm queries, and linear regression. Finally, we supplement our theoretical results with number of empirical evaluations, which are in the appendix.
1.2 OUR TECHNIQUES
Dynamic regression on adaptive inputs. Our dynamic algorithm for dynamic maintenance of least-squares objective exploits two main ideas. First, standard results in sketching and sampling show that it suffices to solve for the sketched objective of minxer" SAAx Sbilg. where S is an &2 subspace embedding for A. Here, we exploit several techniques from numerical linear algebra and in particular use leverage score sampling to obtain subspace embedding S of A. By standard results in sketching, (1 + =) optimal solution is given by x" = ( Sb. Moreover, since the goal is to output the objective value instead of the solution vector, we may take a Johnson- Lindonnsnnssssusss (JI.) sketch to further reduce dimensionality and run-time. This allows us to focus on ||AAx* - Gb 2 where G E R Olog 4) x is JL sketch.
As result, our algorithm dynamically maintains a solution GA(SA) in this sketched space. To achieve that, we first explicitly solve (SAS)) in pre-processing. Since GA has few rows, this reduces to a small number of linear solves and can be computed fast via conjugate gradient-type methods. To handle the updates, we leverage their sparsity to efficiently maintain the solution and show that each round takes roughly O (K) time. Amortizing the pre- pre-processing with the update costs over all iterations yields our desired run-time.
Finally, we apply techniques from differential privacy to ensure adversarial robustness, by aggre- gating independent copies of the algorithm via a private median mechanism. Intuitively, the private mechanism hides the internal randomness of the algorithm and therefore prevents the adversary from otherwise choosing a "bad" input based on knowledge of internal parameters.
4

---

Adaptive query framework. Our framework maintains Ô (VQ) instances of the non-adaptive data structure and crucially uses differential privacy (DP) to protect the internal randomness of the data structures. In addition to our previous results for dynamic regression, the technique of using DP to hide randomness has recently been used in the streaming model (Hassidim et al., 2020; Kaplan al., 2021) and the dynamic model (Beimel al., 2021). These works elegantly composition property of DP to bound the number of simultaneous algorithms that must be used in terms of the number of times the output changes "significantl" over the course of the stream. In the streaming model, the robust algorithms proceed by instantiating many "hidden" copies of a standard randomized algorithm. As the stream arrives, the algorithms are updated and an answer, aggregated using DP, is reported. Crucially, many of these results exploit the fact that the output answer is monotonic in the stream so that there a known upper bound on the final output. Thus, the reported answers can only increase by a multiplicative factor at most a logarithmic number of times, which is used to bound the initial number of algorithms which are initialized. In our centralized setting, this can be imagined as setting the parameter Q. The main parameter of interest in the streaming literature is the space used by the streaming algorithms, whereas we are concerned with both space usage and query times. Furthermore, stream elements are only accessed one at time and cannot be processed together unless memory is used. In our case, the dataset is given to us upfront and we can pre-process it to construct data structure towards solving a centralized problem.
the advanced
The work by Beimel et al. (2021) shares many of these ideas: the authors are concerned with dynamic graph algorithms where an adversary can update the graph in an adaptive fashion. Similar tools such as multiple randomized initialization and aggregated responses using DP are utilized. The main difference is their parameters of interest: the goal of Beimel al. (2021) is to have fast amortized update time across many queries. This necessitates the need to "throw away" existing algorithms and start with fresh randomness at intermittent points. In contrast, we study centralized setting where the underlying dataset is not updated but we wish to answer Q adaptive queries on the dataset.
Inspired by these works, our main framework also uses advanced composition to show the sufficiency of maintaining Ö (VQ) data structures to answer Q adaptive queries in the centralized setting, which gives rich set of applications. Moreover, to improve the query time of our algorithms, we further invoke the privacy amplification of sampling to show that it suffices to output the private median of a small subset, i.c., a subset of size O (log Q), of these Ö (vQ) data structures. Thus our framework
only incurs a logarithmic overhead in query time and an Ô (vQ) overhead in space. Surprisingly, our simple framework gives diverse applications for adaptive algorithms on a number of important problems, including estimating matrix-vector norms, adaptive range query search, adaptive nearest neighbor search, and adaptive kernel density estimation, to name few. These applications are discussed in depth in Section C.
Adaptive distance estimation. To achieve better pre-processing time for adaptive distance estima- tion, our main technique is to sample groups of rows from a Hadamard transform and argue that an interaction with a separate group should be considered in separate privacy budgets, effectively arguing that outputting n approximate distances single adaptive query only uses one unit of privacy budget. By contrast, our black-box framework charges one unit of privacy budget per approximate distance, so that outputting n approximate distances would use n units of privacy budget.
Adaptive kernel density estimation. Theorem 1.4 is based on showing that with constant probabil- ity, our data structure is accurate on all possible queries in Rd. In particular, we first show that our data structure is accurate on a sufficiently fine net of points through a standard union bound argument, which incurs the d overhead compared to the space required to handle single query. We then show that if the algorithm and the kernel function are both Lipschitz, which is true for sampling-bass algorithms and number of standard kernel functions, then accuracy on the net implies accuracy on all possible points in dd
2 DYNAMIC REGRESSION UNDER LABEL UPDATES
In this section, we consider the dynamic problem of maintaining the cost of the least-squares regression, where the labels receive adaptively chosen updates. Let A E Rexd be the design matrix and b E RD be the target label. A classic problem in numerical linear algebra and optimization is to
5

---

solve the & least-squares regression objective
F(A, b) = -min Ax = - -bll2
(2.1)
XER
We consider a dynamic version of the problem, where the label receives adaptively chosen updates. We assume that each update can only affect K entries of the label vector. this setting, we show: Theorem 2.1 (Main theorem; dynamic maintenance of regression cost). Let E (0, 1/4) be error parameter and ( be the initial target label. Given e, A, b(), stream of T adaptively chosen, K K-sparse updates the label, Algorithm 4 outputs estimate F; such that F. + (A, for all i with high probability.
Furthermore, the algorithm requires preprocessing step in time (nnz A) + poly(d)). The amortized update time of the algorithm
(A) Ö (VK (V)nnz(A) (VR(A)+0=3))
We defer the technical details to Appendix 3. Here, we describe the main ideas of the algorithm.
At a high-level, our algorithm implements a sketch-und-solve strategy. First, in pre-processing. the algorithm samples a leverage score sketching matrix E Rxxa, where & = (d d/=?). This provides a (1 + e) & subspace embedding for A. Standard results in sketching imply that it suffices to solve for the sketched objective of min |SAx Sbll2 (Sarlos (2006); Clarkson & Woodruff (2013; 2017); Woodruff (2014)). Let À SA. A (1 E) optimal solution is thus given by Á tb. Moreover, our goal is to maintain the regression cost, rather than this solution vector. Hence, we can apply the Linden--indeessrauus. lemma and focus on
min SAx Sbll² ~ ||AA[A)] Sb Gb 1
(2.2)
where E (1ogg///")x is a JL sketch.
To track the cost value dynamically, the algorithm first computes and stores M = GA(SA)1 in pre-processing. In the 1-st step, given the initial target label b(1,, the algorithm computes (b)) M (Sb(1)) and (1))), Then outputs F = [|MSb(1) Gb as an estimate of the regression cost. For the later steps, we show how to maintain ()))) Sb efficiently, by exploiting the sparsity of the updates. Finally, to remain robust under adaptive inputs, we aggregate multiple copies using private median and carefully balance the parameters to achieve the run-time guarantee.
3 DETAILS ON DYNAMIC REGRESSION
In this section, we consider the dynamic problem of maintaining the cost of the least-squares regression, where the labels receive adaptively chosen updates.
We first introduce the basic setting of the problem in Section 3.1. In Section 3.2, we design key subroutine under non-adaptive updates. The data structure enjoys a nearly linear update time. This allows us to aggregate multiple copies of the procedure and thereby efficiently ensure adversarial robustness against an adaptive adversary. The argument via an application of differential privacy and detailed subsequently in Section 3.3.
3.1 BASIC SETTING
Let A E I be the design matrix and b E IR" be the target label. A classic problem in numerical linear algebra and optimization solve the Eg least-squares regression objective
F(A, b) = min AA
bll2 | --Aib-bl1--
(3.1)
We consider dynamic version of the problem, where the design matrix A remains unchanged. However, at each step (at most) K entries of b undergo an update. Moreover, we assume that the updates are chosen adaptively by an adversary in the following manner.

---

The algorithm starts by receiving the input A Ruxd and b(1) IR..
In the i-th step, the algorithm outputs an estimate Fr the cost F(A, b(O), where b(o) the target label corresponding the step.
The adversary observes Pe and updates at most K labels to form b
Let (()), ((2) ,..., b (T) E IR" be the resulting sequence of labels over steps. The goal of the algorithm output (1 +e) approximation to the optimal cost at every step, while minimizing the update time.
3.2 DYNAMIC ALGORITHM FOR OBLIVIOUS INPUTS
In this section, we provide a key subroutine that maintains a data structure under oblivious updates. On high-level, the data structure aims to enable sketch-and-solvv strategy dynamically. The main ideas are two fold: (1) apply randomized sketching to reduce dimensionality and therefore the run-time, and (2) exploit the sparsity of the updates argue that the regression costs can be maintained efficiently.
Before delving into the technical details, give an overview of the algorithm.
Overview of the algorithm. We start by assuming that the algorithm has access to DL. (via Lemma A. I), the row leverage score sampling data structure for A. In preprocessing, the algorithm samples leverage score sketching matrix S E kx from DLs, where k = (d d/e²). This provides a (1 + =) & subspace embedding for A. Standard results in sketching imply that it suffices to solve for the sketched objective of min |AAx Sbll2 Sarlos (2006); Clarkson & Woodruff (2013; 2017); Woodruff (2014). Let Å SA. Then a (1 E) optimal solution thus given by À lb. Moreover, our goal is to maintain the regression cost, rather than this solution vector. Hence, we can apply Johnson-Lindenstraus lemma and focus on
|GAASA))Sb | min SAx SbIl KERd
Gb 1b
(3.2)
where G E Olog )xn is JL sketch.
Next, we describe how to track the cost value dynamically. We stress that the sketching matrices S and G are sampled upfront in the preprocessing stage and remain fixed afterwards. The algorithm stores G and M = GA(SA) both computed in preprocessing. Meanwhile, it maintains Gb((), 6b initialized at i = 1. In the first step, given the initial target label (()), the algorithm computes Sb(1), M (S)(1) and Gb( Then it outputs F (1) Gb( || as an estimate of the regression cost.
Let's consider the i-th step, where the label is updated ((9) First, we read the K labels that get changed and update Sb(r-1) Sb(") accordingly. This can be done in O(K) time. Finally, simply compute M()b()) and Gb and output F: MSb Gb We store (b for the next iteration.
We now describe the algorithm formally, followed by an analysis of its run-time and accuracy.
Formal description of the algorithm. We assume DLS for is given. The data structure is initialized by drawing the sketching matrices G and S. We also compute M CSA(SA)) in preprocessing. This matrix is stored explicitly throughout.
Algorithm Initialize the data structure, i.e., preprocessing
Input: Design matrix A Raxd initial label ((1) RR,,Lss. (0,
1: Let k = θ (d log d/
2: Sample (1 =/2) le leverage score sampling matrix R for A from DLS.
3: Sample a JL sketch matrix G RCs nog for sufficiently large C, by Theorem A.6.
4: Compute and store M GA(SA)),
7

---

At each step, the algorithm computes Sb by reading all K entries of b' that updated in the step. After that, compute (()b()) and Gb and output Mb ()) Gb The algorithm is formally given by Algorithm 2.
Algorithm 2 Update data structure and maintain regression cost
Input: Matrices G E RC logaxn S E Rx .MM E R (1/62)) and the label (())
Output: Estimate of the regression cost F (A, b(o)
1: Compute (b()) (5) by reading all K entries of b (i that are updated.
2: Compute M (Sb(1) and Gb
DStore MSb ( SbO,, Gb (*) for the next round.
Output F. = MSb (t) Gb
3:
Analysis of the algorithm. We now analyze the run-time of the algorithm. First, consider the preprocessing stage performed by Algorithm 1.
Lemma 3.1 (Preprocessing time). Assuming access to the leverage score sampling data structure DLS, the preprocessing time of Algorithm I
1 nnz(A) E²
V*(A) (n(A))nz(())o))) log
log n
+ e²
log n
(3.3)
E
Proof. By Lemma A. the guarantee of the sampling data structure DLS, takes O log (nd)) time obtain leverage score sample S of size k. Drawing the JL sketch is straightforward, and standard constructions such as i.i.d. Gaussian entries require Ol log n/E²) times to form G.
Finally, we need to compute M. Computing GA requires
O (nz((A)
log time by sparse matrix rows, then computing (GA)(SA)
multiplication. Moreover, since GA matrix of logn
reduces to O log number linear system solves with respect to SA E kxd By conjugate gradient type methods, since x(SA) (1 + e) ())( each solve can be achieved to high accuracy in O log(L))) number of matrix-vector products with respect A Golub Van Loan (2013). In total, this gives run-time of O (Vn (A))))o((1)))
Lemma 3.2 (Update time). The update time of Algorithm is O (2) log n) per step.
Proof. First, the algorithm reads the K entries that updated and compute the Sb from (b-1)) This step takes O(K) time, since we just need to update the entries that lie in the support of the row sampling matrix S. Similarly, in step 2 of Algorithm 2 we can update Gb-1 to Gb(() in OKK no=") time. Since S is a row sampling matrix and (() only has K entries updated, then (b()) has at most K entries updated as well. It follows that given M (S)( from the prior round, M (S) can be updated in O K 2 lo time.
Lemma 3.3 (Aceuracy). Given stream of = O(d?) non-adaptive updates and error parameter & E 104), Algorithm outputs an estimate F; of the regression cost ((Ab(()) such that 8. = (1 + FAA, b(0) ( for all i with high probability.
Proof. First, we apply the subspace embedding property of S. This implies that with high probability,
min SAX (1) 2 (1 + 5 min Ax b b())
2
Apply the JL lemma (Theorem A.6), where consider the collection of O (dP) (1 e) optimal predictions {yr)T" with y; = A(SA) ((), Via union bound, we have that with high probability for all i E [T]
Gyy - Gb()) ( 2 = (1 +1 |1: b0
8

---

Our algorithm precisely solves for y? each iteration. Combining the two equations above finishes the proof.
3.3 DYNAMIC ALGORITHM WITH ADVERSARIAL ROBUSTNESS
To put everything together and ensure adversarial robustness, we use standard approach of Hassidim et al. (2020); Beimel et al. (2022); Attias et al. (2023). Our full algorithm maintains -= (TToog(TT) independent copies of the key subroutine for T O step, we output the private median of the outputs of these copies. Advanced composition of DP ensures robustness up to 7 rounds. Afterwards, the algorithm reboots by rebuilding the copies, using fresh randomness independently for sampling and computing the sketching matrices.
u Then at each
Algorithm 3 Preprocessing step for Algorithm 4
Input: A design matrix A E Rnxd an approximation factor (0, 1). The leverage score sampling data structure DrS for A.
Output:
Compute the approximate row leverage scores of A.
>Lemma A.11
2: Build and output the data structure DLS
Algorithm 4 Dynamic algorithm for maintaining regression cost under adaptive updates
Input: A sequence of target labels { (b()) ) and a fixed design matrix A RRaxd an approximation
factor E E (0, 1), the leverage score sampling data structure DLS for A.
Output: Estimates of the regression cost F(A, (()) under adaptively chosen updates to b.
for every epoch
= =0
(nnz(A) e²K
updates do
Initialize r O (VT log (nTT) independent instances of the data structure in Section 3.2
2:
via Algorithm 1.
3: Run PrivMed on the instances with privacy parameter e' = (VTTOR(NT)) with failure
probability 8 = poly(m,.7)
4:
For each query, return the output of PrivMed.
[Main theorem; dynamic maintenance of regression cost] Let E (0, 1/4) be error parameter and (1) be the initial target label. Given E, A, b1), stream of T adaptively chosen, K K-sparse updates to the label, Algorithm 4 outputs estimate F; such that F. (1 F) b()) for all i with high probability.
Theorem 3.4.
Furthermore, the algorithm requires a preprocessing step in time (nnz(A) A) + poly(d)). The amortized update time of the algorithm is
δ (VK
K (NnnizA)) (Vr(A)+E*) +
per round.
We defer the proof of Theorem 3.4 and a discussion on a deterministic algorithm to Section B.
ACKNOWLEDGEMEENTS
Sandeep Silwal is supported by an NSF Graduate Research Fellowship under Grant No. 1745302, and NSF TRIPODS program (award DMS-2022448), NSF award CCF-2006798. and Simons Investigator Award (via Piotr Indyk). This work was done in part while David P. Woodruff was at Google Research and supported in part by a Simons Investigator Award and by the National Science Foundation under Grant No. CCF- 18 15840. Fred Zhang is supported by ONR grant N00014-18 1--18-1-2 This work was done in part while Samson Zhou was at Carnegie Mellon University and supported in part by a Simons Investigator Award and by the National Science Foundation under Grant No. CCF- 1PFF-8818400

---

REFERENCES
Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In PODS '22: International Conference Management of Data, pp. 15-27, 2022.
Josh Alman and Huacheng Yu. Faster update time for turnstile streaming algorithms. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1803-1813, 2020. 20
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. Advances in neural information processing systems, 28, 2015. 27
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Coloring in graph streams via deterministic and adversarially robust algorithms. CoRR, 12s/2212.11041,, 2022.
Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. In 14th Innovations in Theoretical Computer Science Conference, ITCS, pp. 8:1-8:19, 2023. 2, 9,
Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou Adversarially robust submodular maximization under knapsack constraints, In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pp. 148-156, 2019.
Arturs Backurs, Moses Charikar, Piotr Indyk, and Paris Siminelakis. Efficient density evaluation for smooth kernels. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 615-626, 2018.
Arturs Backurs, Piotr Indyk, and Tal Wagner. Space and time efficient kernel density estimation in high dimensions. In Advances Neural Information Processing Systems 32: Annual Conference
on Neural Information Processing Systems, NeurlPS, pp. 15773-15782, 2019. 4, 24, 25
Ainesh Bakshi, Piotr Indyk, Pranceth Kacham, Sandeep Silwal, and Samson Zhou. Sub-quadratic algorithms for kernel matrices via kernel density estimation. CoRR, abs/2212.00642, 2022. 24
Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput., 50(3), 2021. 14
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generie constructions and lower bounds. CoRR, abs/211 1.09880, 2021. 5,5
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1671-1684, 2022. 1,
Omri Ben-Eliezer, Rajesh Jayaram, David Woodruff, and Eylon Yogev. framework for adversari- ally robust streaming algorithms. SIGMOD Rec., 50(1):6-13 13, 2021. 1
Omri Ben-Eeiezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In 5th Symposium on Simplicity in Algorithms, SOSA@SODA, pp. 214, 2022. 1
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. 49th International Colloquium on Automata, Languages, and Program- ming, ICALP, pp. 20:1-20:20, 2022.
Battista Biggio, Igino Corona, Davide Maiorea, Blaine Nelson, Nedim SIndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. In Machine Learn- ing and Knowledge Discovery in Databases European Conference, ECML PKDD Proceedings.. 2013.
10

---

Iijja Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. Robust submodular maximization: A non-uniform partitioning approach. In Proceedings of the 34th International Conference Machine Learning, ICML, pp. 508-5088-0 106--16,,00 2017.
Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Advances Neural Information Processing Systems 34: Annual Conference on Neural Information
Processing Systems, NeurIPS, pp. 3544-3557, 2021.
Hervé Brönnimann, Bernard Chazelle, and János Pach. How hard is half-space range searching? Discrete Computational Geometry, 1032):443-15, 1993. 19
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pp. 634 649, 2015. 13
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP, pp. 39-57. IEEE Computer Society, 2017. 1
Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. In 13th Innovations in Theoretical Computer Science Conference, ITCS, pp. 37:1-37:23, 2022. 1
Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey, ACM Comput. Surv, 41(3):15:1-15::: 2009,
Moses Charikar and Paris Siminelakis. bushiin-based-esttiator for kernel density in high di- mensions. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 2017. 25
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theor: Comput. Sci., 312(():3-155 2004. 20
Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estimation through density constrained near neighbor search. In 61 IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 172-183, 2020. 24
Bernard Chazelle. The discrepancy method: randomness and complexity. Cambridge University Press, 2000. 19
Bernard Chazelle, Ding Liu, and Avner Magen. Approximate range searching in higher dimension. Computational Geometry, 39(1):24 290222222,2202 2008. 19
Nadiia Chepurko, Kenneth Clarkson, Lior Horesh, Honghao Lin, and David Woodruff. Quantum- inspired algorithmss from randomized numerical linear algebra. In International Conference on Machine Learning (ICML), 2022. 15
Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances in Neural Information Processing Systems 33: NeurIPS, 2020. 3, 20, 22, 27, 28
Yeshwanth Cherapanamjeri and Jelani Nelson. Uniform approximations for randomized hadamard transforms with applications. STOC 22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 659-671. 2022. 3, 20, 22, 27,28
Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity
time. In Symposium Theory of Computing Conference, STOC, pp. 81-90, 2013. 6, 7, 19
Kenneth L Clarkson and David Woodruff. Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM), 63(6):1-45, 2017. 6,7
Itai Dinur, Uri Stemmer, David P. Woodruff, and Samson Zhou, On differential privacy and adaptive data analysis with bounded space. CoRR, abs/2302.05707, 2023.

---

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC, Proceedings, pp. 265-284, 2006. 13
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium Foundations of Computer Science, FOCS, pp. 51-60, 2010. 14
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pp. 117-126. ACM, 2015. 14
Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, and Mary Wootters. Reusable low-error compressive sampling schemes through privacy. In IEEE Statistical Signal Processing Workshop, SSP, pp. 536-539, 2012.
Gene H Golub and Charles Van Loan. Matrix computations. Johns Hopkins University Press, 2013.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2015.
Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 111-122, 2016.1 1
Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurlPS, 2020. 1, 2, 3, 9, 14, 16, 17
Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. ACM, 53(3):307-322 2006. 18
Shunhua Jiang, Binghui Peng, and Omri Weinstein. Dynamic least-squares regression. arXiv preprint
arXiv:2201.00228, 2022. 3
Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. Advances in Cryptology- CRYPTO 2021 sI Annual International Cryptology Conference, CRYPTO, Proceedings, Part III, pp. 94-121, 2021. 1,5
Ping Li. Estimators and tail bounds for dimension reduction in la (0 < a S 2) using stable random projections. In Shang-Hua Teng (ed.), Proceedings of the Nineteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 10-19, 2008. 18
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. In 5th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR, 2018.
Michael W Mahoney. Randomized algorithms for matrices and data. Foundations and Trends@ in Machine Learning, (22):123-224, 2011. 14
Ilya Mironov, Moni Naor, and Gil Segev. Sketching in adversarial environments. SIAM J. Comput., 40(6):1845-1878 2011.
Moni Naor and Eylon Yogev. Bloom filters in adversarial enviromments. ACM Trans. Algorithms, 15 (3):35:1-35:30, 2019.
12

---

Nicolas Papernot, Patrick D. McDaniel, and Ian J. Goodfellow. Transferability in machine learning: from phenomena to black- box attacks using adversarial samples. CoRR, abs/1605.072777, 2016.
Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM Asia Conference on Computer and Communications Security, AsiaCCS, pp. 506-519, 2017. 1
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. 47th annual IEEE symposium on foundations of computer science (FOCS), pp. 143-152, 2006. 6,
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference Learning Representations, ICLR, Conference Track Proceedings, 2014.
Csaba Toth, Joseph O' O'Ruur and Jacob E Goodman. Handbook of discrete and computational geometry. CRC press, 2017. 19
David Waje. Rounding dynamic matchings against an adaptive adversary. In Proccedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC, pp. 194-207, 2020.
David P Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1 (011-2)1--17, 2014. 2, 6, 7, 14, 15
David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1183-1196, 2021.
David P. Woodruff, Fred Zhang, and Samson Zhou. Streaming algorithms for learning with experts: Deterministic versus robust, 2023.
Vladimir Zolotarev. One-dimensional stable distributions, volume 65. American Mathematical
Soc., 1986. 19
A PRELIMINARIES
Notations this paper, we use [n] for a positive integer
denote the set f1...., .n.. We
use poly(n) to denote fixed polynomial in We say an event occurs with high probability if occurs with probability
poly(nj' For real numbers a, b and positive e, we say a = (1 ebb
R" be the i'th standard basis vector. Let X denote the Moore-Penrose pseudo-invers of matrix X. Let || denote the operator norm of X. Let <(X) X |X||||||||| denote the condition number of X.
if (1 5)6 < < (1 + b)b. Let
A. DIFFERENTIAL PRIVACY
Much of technical results leverage tools from DP. We recall its definition and several key statements.
Definition A.1 (Differential privacy, Dwork et al. (2006)), Given e > 0 and ō E (0, 1), a randomized every neighboring datasets S and S! algorithm A X is (8, ddiiferrnntl private if, eorevery and for all E y,
Pr Pr(A(S) E EJ S eF Pr[A(S") E +.
Theorem A.2 (Amplification via sampling, e.g., Bun et al. (2015)). Let A be an (E, 8) differrentill private algorithm for e < 1, 8 E (0, 1). Given a database S of size n, let A' be the algorithm that constructs a dutabase T C S by subsampling (with replacement) < rows of S and outputs A(T). Then A' is "'dd8'd)ffeerentiaall private for
6ck:
4k6
8' = "xxx(66kk/1)
n
13

---

Theorem A.3 (Private median, e.g.. Hassidim et al. (2020)), Given database D E X", there exists
an (e, d)dffffrenttially private algorithm PrivMed that outputs an element x E X such that with
probability at least 1 - 8, there are at least 2 |s] k elements in S in S that
|8] k elements in S that are at least and at least
most I, for O log )
Theorem A.4 (Advanced composition, e.g., Dwork al. (2010)). Let e, 8' (0, and let ó [0, Any mechanism that permits & adaptive interactions with mechanisms that preserve (e, 8)-differential
privacy guarantees (E', kō + 8') d'ifferrent privacy, where e' 2 In 8 - 2kc?
Theorem A.5 (Generalization of DP, e.g., Dwork et al. (2015); Bassily et al. (2021)). Lere E (0, 10.1/3).
ò E (0, 44), and 2 1/2 log f. Suppose A X 2x is an (E. -.)--dffeeeentilly private algorithm that curates database of size and produces function h. X - {0, 1}. Suppose 'D is distribution over and a set of n elements drawn independently and identically distributed from D. Then
Pr S~DAReA(S)
[1(x)
h(x)
[bxx)]
2 10e
S
IND
A.2 NUMERICAL LINEAR ALGEBRA
Our results on dynamic regression relies upon some tools in numerical linear algebra. We first recall the dimensionality reduction techniques.
Theorem A.6 (Johnson- (Johnson-Lindenstraus Lindenstrauss transformation, e-JL). Given & > 0, there exists a family of random maps md Rexd with O (1) such that for any Rdd we have
3
Pr H-Hl..a
- =)]x// < |[xi||2 (1 +1+ (1++))[x1])
x
Moreover, Ilx takes O (#) time to compute.
Theorem A.7 (Fast JL). Given > O, there exists a family of random maps 1m,,a Rmxxd with
m O logd z
such that for any E Rd,, we have
3
Pr [[1- [1=x)]1x112 S [xx||2 S (1 +1+ [x|2]]
Moreover, IIx takes O (
log ( dlog d) time compute.
A row sampling matrix S has rows that are multiples of natural basis vectors, so that SA is (weighted) sample of the rows of A. A column sampling matrix defined similarly. The size of row/column sampling matrix is defined as the number of rows/columns it samples. The leverage score the ith row a, of A is
(A) def a. (ATA)* a;-
For survey on leverage score and applications, we refer the reader to Mahoney (2011).
Definition A.8 (Leverage score sampling). Lel be vector of leverage score overestimates, i.e., (A( < Let a be sampling rate parameter and c be fixed positive constant. For each row, we define a sampling probability p. min a u.c log d). The leverage score sampling matrix is row sampling matrix with independently chosen entries such that S = - with probability p: and 0 otherwise.
Definition A.9 (Subspace embedding). A (1 + E) lg subspace embedding, for the column space of an n x d matrix is a matrix S for which for all x E Rd
SAA 2 (1 + AA
Theorem A.10 (Leverage sampling implies subspace embedding, Theorem 17 of Woodruff (2014)). Let a = E 22 and be sufficiently large constant. With high probability, the leverage score sampling matrix is (1 + 8) &g subspace embedding. Furthermore, has size O (dg d
14

---

The approximate leverage scores be computed in input-sparsity time. Afterwards, repeated sampling from the leverage score distribution can be done efficiently using the binary tree data structure in quantum-inspired numerical linear algebra.
Lemma A.11 (Leverage score computation and sampling data structure; see Woodruff (2014); Chepurko et al. (2022)). Lel Rand There exists an algorithm that given A oulputs vector of row leverage score overestimates with high probability and in run-time O (nnz(A) + poly(d)).
Furthermore, there exists a sampling data structure DLs that stores the leverage scores of A such that given a positive integer m I n, returns a leverage score sample of A of size m in O (m log(mm)) time. In total, the pre-processing takes O (nnz) poly(d)) time.
B ADDITIONAL DETAILS ON DYNAMIC REGRESSION
Theorem 3.4. [Main theorem; dynamic maintenance of regression cost] Let (0,1/4) be error parameter and b be the initial target label. Given E, A, b(1), stream of adaptively chosen, K K-sparse updates the label, Algorithm 4 oulputs estimate F3 such that F. (1 F b()) for all i with high probability.
Furthermore, the algorithm requires preprocessing step in time Ô (nnz((A A) + poly(d)). The amortized update time of the algorithm
δ K (Inz(A) (Vx(A) (vR(A)+E-))
per round.
Proof. We focus on any fixed epoch of iterations. Let (AtH the collection of I' data structures maintained by the Algorithm 4 and Ti be the transcript between Algorithm 4 and the adversary at round i, consisting of the algorithm's is output and the update requested by the adversary.
To handle sequence of T adaptive queries, consider the transcript T(R) where R denotes the internal randomness of Algorithm 4. Note that for a fixed iteration, Te is (o
{T..... Tr }.
Vooggr
differentially private with respect to the algorithms A Ar. since the pri-
vate median algorithm PrivMed is (VTTIgE(TT) .0) -iiferentially private. By the advanced com-
position of differential privacy, i.e., Theorem A.4, the transcript (0(1,, poly(n) differentially private with respect the algorithms AI,...,Ar Ar.
Algorithm 4 runs instances of the data structure with emor parameter e. For any given round E [T). we say that an instance j E [ is correct its output ft,j is within a (1 + e) factor of F(A, b()) and incorrect otherwise. For a fixed let Y, be the indicator variable for whether Si correct.
From the generalization properties of differential privacy, i.e., Theorem A.5, we have that for any fixed iteration i,
Pr
Σ Y, B jELLI
2
<
10
(oly T)'
where denotes the indicator random variable for whether a random instance of the algorithm A (not necessarily restricted to the m instances maintained by the algorithm) is correct at the given round Since random instance A has randomness that is independent the adaptive update, then E [Y] > 3 Therefore, by union bound over all T rounds, we have 4-
Pr
0.6 E P
Y. NET
>1 (oly(m,
which implies that the output the ith round is correct with probability least 1 = d. Then by a union bound over E [T] for all rounds within an epoch, we have that the data structure answers all 7 queries with probability ... under the adaptively chosen updates. Finally,
777 since
15

---

by union bound over all m updates, have that the algorithm succeeds with probability least
1
We now analyze the run-time of the algorithm. The preprocessing time follows from the guarantee of Lemma A.11. For update time, we amortize over each epoch. Within an epoch, we invoke o
VT (ogg(())) copies of the data structure in Section 3.2, and so we consider the preprocessing and update time from there and amortize over the epoch length T. By Lemma 3.1, each copy takes
= (Vx(A) anz(() log maz(A) logn + ş² log time to pre-process. For every step of update, each copy takes O ( log n)) time by Lemma 3.2. Therefore, the amortized update time for mnz(A)
every epoch of length T = 0 c²K
o This completes the proof.
(
TB T 1 IT
(
= OVKK { (VR(A) +E-))
K
log )))
B. AN EXACT AND DETERMINISTIC ALGORITIIM
We now give simple deterministic algorithm for the dynamic regression problem based on an SVD trick. Let A UEVT be the SVD of A, where U E Raxd Σ E Ikdxd and V E Rdxd, The starting observation that for any solution vector x, we can write the regression cost as
AA bl UEEV x - bl| | U'b//:
(B.1)
since is orthonormal. The goal the maintain the solution vector x = A Alb and the associated bll.
right-side quantity EVT
Now suppose we compute At a E Rdxa and UT Rdxx pre-processing, and A Atb(2) and U (()
in the first round. Then since all subsequent updates to b are all K K-sparse, we only pay OdK) time step maintain A (1) and (
Algorithm 5 A simple SVD-based algorithm for dynamic regression
Input: Design matrix A E Ruxd, its pseudoinverse A E [d and its SVD A UΣVT, sequence of labels (a) E R"
UEVT, where E Rad Σ Rdxd E Rddd 2: Compute and store At from the SVD. >In the 1st-round, compute and store Alb(), DO)
1: Compute and store SVD
3: for each update (()) do
4: Update and store x ()
5: Update and store U (()
6: Output F. = EV (0) b
The algorithm is formally given by Algorithm 5. Observe that the algorithm always maintains the exact optimal regression cost. Moreover, the procedure does not require any randomness, and therefore it is adversarially robust to adaptive inputs. We formally claim the following guarantees of the algorithm.
Theorem B.1 (Deterministic maintenance regression costs). Given A, (() and a stream of adaptively chosen, K K-sparse updates to the label, Algorithm 5 takes (dd) time update and maintain the exact regression cost F(A, (()) at all iterations i. The pre pre-processing requires SVD of A, in dn) time.
C A FRAMEWORK FOR ADVERSARIAL ROBUSTNESS
In this section, we describe the benchmark framework that enables Q adaptive queries to a data structure by using δ (VQ) copies a non-adaetive data structure. The framework and corresponding analysis of correctness simply compartmenttlizzttooss of the techniques in Hassidim al. (2020);
16

---

Beimel et al. (2022); Attias al. (2023). For the sake of completeness, include them here and discuss additional applications. Namely, we show that through advanced composition of differential privacy, the private median of Ö (vQ) copies protects the internal randomness of each non-adaptive data structure while still adding sufficiently small noise guarantee accuracy. Moreover, we use amplification of privacy by sampling to only consider small subset of the (vQ) non-adaptive data structures to further improve the runtime.
Algorithm 6 Adaptive Algorithm Interaction
I: +- O (VQlog" logllo"(nn (nQ)), + O (log(nQ))
2: for E (r] do
3: Implement data structure D; the input
4: for each query qis E [Q) do
5: Let S be set of k indices sampled (with replacement) from
6: For each j E [k], let di,j be the output of Ds, on query d;
7: di t PrivMed (di, (E()) where PrivMed is ODPD
We first argue that Algorithm maintains accuracy against Q rounds of interaction with an adaptive adversary. Let R (R( , R()), where R R R(r) denotes the random strings used by the oblivious data structures D....., ,..,,,,, Dr, and R( denotes the additional randomness used by Algorithm 6, such in the private median subroutine PrivMed. Consider transcript T(R)
(TI....,Tq) T such that for each i E (Q). we define T, = (g:: d,) to be the ordered pair consisting of the query and the corresponding answer d; by Algorithm 6 using the random string R(O), as well as the oblivious data structures D Dj..... D, with random strings R((1) R(O). We remark that d, is random variable due to the randomness of each data structure, as well as the randomness of the private median subroutine PrivMed.
We will first argue that the transcript TR is differentially private with respect R. We emphasize that similar arguments were made in the streaming model by Hassidim et al. (2020) and in the dynamic model Beimel al. (2022); Attias al. (2023).
Lemma C.1. For a fixed iteration, T; is (o( .0) differentially private with respect to R.
Proof. We first observe that PrivMed is (1, difffeerrftl private on the outputs of the O (VQlo"(((()) (n()) data structures. Algorithm 6 samples i: O (log(n()) groups of data structures from the total data structures. Thus by amplification via sampling, i.c., Theorem A.2, PrivMed
(o VQ (oginn))) .0 -differentiallly private. Therefore, Ti is (o (QQ (oqgg(na)) ) private with respect to R.
-differennially
We next argue that the entire transcript is differentially private with respect to the randomness
Lemma C.2. T is (O()), polv(ng) -diferrnntillly private with respect to R.
Proof. By Lemma C.I, for each fixed iteration E [Q]. the transcript T; is (o VQ (o o)- differentially private with respect to R. Note that the transcript T is an adaptive composition of the transcripts Ti...., To. Thus, by the advanced composition of differential privacy, i.c. Theorem A.4, the transcript T (O polyinqz))
-differentially private with respect R.
We now prove the correctness of our unifying framework.
Proof of Theorem 1.2: For fixed query 9; with é e [Q], let be the corresponding set of k indices sampled from [r]. Let y be the set of valid answers on query qi- Let Ty be indicator variable
17

---

for whether the output di on query qi by Ds, is correct, that 1 if dag V and 1, 0 if ds $ V. By assumption, we have that for each j E [k]
Vand
Pr 14 1| 4'
so that E [14 2 ..8 We define the random variable / = Ej 1j so that by linearity of expectation, [4] = EEE [4] 4
To handle a sequence of Q adaptive queries, we consider the transcript T(R) = TT! for the randomness R = { . R(*)} previously defined, i.e., for each i E [Q]. T. (q: d4) is the ordered pair consisting of the query di and the corresponding answer d, by Algorithm 6 using
the random string R well as the oblivious data structures D1...., D, with random strings
, ,, By Lemma C.2, we have that T is (O()) poly(n -differentially private with respect R.
For E [A:], we define the function success (R( to be the indicator variable for whether the output di,s; by data structure Ds, is successful on query Qi- For example, if D is supposed to answer queries within (1 + -pparopoxinaaionn then we define success (H)())) to be one if di,s, is within (1 + -ppappoxximttion to the true answer on query gis and zero otherwise. From the generalization properties of differential privacy, i... Theorem A.5, have
Pr
success R(()))
E H
success R)]
z
10
poly(n, Q)
JE(M]
for sufficiently small O (1). Therefore, by union bound over all Q queries, we have
1 k KE[M]
1
Pr
I > 0.6 >
poly(n, Q)*
which implies that de is correct on query Then by a union bound over i E [Q] for all Q adaptive queries, we have that the data structure answers all Q adaptive queries with high probability. D
D APPLICATIONS OF OUR FRAMEWORK
Theorem 1.2 has applications to a number of central problems in data science and machine learning. In this section, formally deseribe the range queries, point queries, matrix- norm queries, and linear regression problems; we defer discussion of adaptive distance estimation, kernel density estimation, and nearest neighbor search to the the appendix.
D.1 APPLICATION: MATRIX- VECTORR NORM QUERIES
In the matrix-vector to handle Q adaptive queries (1) , (Q) for an approximation parameter > 0 by outputting
query problem,
given matrix A Raxd and would like
(1 + =aaapooxximttoonn to AI for each query x(1) e gd with i E [Q]. Here we define ||vl| = Eieg |u:|2 for vector E Rdd. Observe that computing (x explicitly and then computing its p-norm requires O (nd) time. Thus for d, much faster approach is to produce subspace embedding, i.c., to compute a matrix M E Rondd with m < n, such that for all x e Rdd
(1 =) Ax|p, < ||Mx|, < (1 + Ax||p
However, because subspace embeddings must be correct over all possible queries, the number of rows of M is usually = 52 (+) due to requiring correctness over an e-net.
Theorem D.1 (Indyk (2006); Li (2008)). Given A Baxd p (0,2), and an accuracy parameter & > 0, there exists an algorithm that creates data structure that uses O ( logn) bits of space and outputs (1 + e) -approximatiin to ||Ax|Ip for query Rd, with high probability, in time O (& logn).
18

---

Theorem D.1 essentially creates matrix R E R of random variables sampled from p-stable distribution (Zolotarev, 1986) and then stores the matrix RA. Once the query x arrives, the data structure then outputs (1 + apprroxximtoo to || by computing a predetermined function on R.Ax. The restriction on p E (0, is due to the fact that p-stable distributions only exist for p E (0, 2). From Theorem D.1 and Theorem 1.2, we have the following:
Theorem D.2. Given A E R=xd E (0, 2). and an accuracy parameter E > 0, there exists an algorithm that creates a data structure that uses O ( log (nQ( bits of space and outputs a
(1+ + appprooximnatoon to ||Ax()) lp with E [Q] Q adaptive queries x(") x......., x!9) E RR, with high probability, in time O (# logg(((Q)))))))))))))()) + log" (nQ)).
D.2 APPLICATION: LINEAR REGRESSION
In the linear regression problem, we are given fixed matrix A E Baxd and we would like to handle Q adaptive queries (2)) ....,,..", b for an approximation parameter e >> 0, by outputting a +1+ apprroxixiiit to min ||Ax - b for each query b(9) E R" with E [Q]. For linear regression,
again compute subspace embedding M SA R and answer query ((0) by approximately solving min ||SAx Sb where S is sketching matrix (Clarkson & Woodruff, 2013).
Theorem D.3 (Clarkson & Woodruff (2013)). Given A Raxd b Rh, and accuracy parameter > 0, there exists an algorithm that creates data structure that uses O ( (et log)(nQ))
bits of space and outputs a (1 + -aprroxiimmttnnnnn to mingeR* || - bl[2 with high probubility
However, this may fail for multiple interactions with the data structure. For example, suppose the adversary learns the kernel of S. Then the adversary could query some vector b(() in the kernel of S so that (b( is the all zeros vector, so that the output is the all zeros vector of dimension d, which could be arbitrarily bad compared to the actual minimizer. Thus the na've approach to maintain Q subspace embeddings,
for each query, resulting in data structure with space Ö Qd' By comparison, Theorem D.3 and Theorem 1.2 yield the following:
Theorem D.4. Given A Raxd and an accuracy parameter > there exists an algorithm that creates data structure that uses O (vQL log"((()) (nQ)) bits of space and with high probubility, outputs (1 + approximatts minxerd ||Ax ( 1l2 for Q adaptive queries b(), ........."". b(Q)).
D.3 APPLICATION: HALF-SPACE QUERIES
Given a set P of n points in Rd the range query or search problem asks us to pre-process P so that given a region R, chosen from a predetermined family, one can quickly count or return the points in PO This is an extremely well-studied class of problems in computational geometry Toth et al. (2017) and the case where the regions R are hyperplanes (also called half-spaces) is of special interest since many algebraic constraints can be "lifted" to be hyperplanes in higher dimension.
Unfortunately, exact versions of the problem are known to have the "curse of dimensionality" and suffer from exponential dependence on d in the query time (Brönnimann et al., 1993; Chazelle, 2000). Nonetheless, Chazelle et al. (2008) gave a data structure capable of answering hyperplane queries approximately with polynomial query time. Their notion of approximation is as follows: given set of points P in the unit & ball, hyperplane R, and e >> 0, we return the number of points that are on given side of the hyperplane R up additive error equal to the number of points in P which lie within distance of the boundary of R. We will refer to this query as an e-approximate hyperplane query. Chazelle al. (2008) proved the following theorem.
Theorem D.5 (Chazelle et al. (2008)). Given a set of points P that lie in the unit l ball, there exists a data structure that pre-processes P using space Ö (dn such that any e-approximate hyperplane range query is answered correctly with high probability. The query time is Õ (d/e?).
The data structure of Chazelle et al. (2008) is randomized and in particular employs randomized dimensionality reduction. Thus, it is feasible that queries might fail for multiple adaptive interactions
19

---

with the data structure. By utilizing framework of Section C and Theorem 1.2, we can obtain the following robust guarantee.
Theorem D.6. Given a set of points P that lie in the unit lg ball, there exists data structure which pre-processes P using space Ö (vQdn such that Q adaptive e-hyperplane range queries answered correctly with high probability. The query time is Ô (d/e²).
D.4 APPLICATION: POINT QUERIES ON TURNSTILE STREAMS
In the problem of point queries on turnstile streams, there exists a stream of m updates. Each update specifies coordinate E [n] of an underlying frequency vector R" and changes fi by some amount between A; E [-A, A], where A = poly(n). Given any constant accuracy parameter s > any time t E [m]. we define f(() to be the frequency vector implicitly defined after the first t updates. Then the point query problem is to output f(²) for various choices of t E [m] and i [n] within an additive error of = f|]
Theorem D.7 (Alman & Yu (2020)). There exists an algorithm that uses space O (log" n) bits, worst-case update time O (log n),, and query time O (log).588 n.). that supports point queries with ε = 0.1 with high probability.
An important quality of Theorem D.7 is that it significantly improves the update time over previous data structures, e.g., Charikar al. (2004), at a cost in query time. By applying Theorem 1.2, we can avoid a blow-up in query time while still enjoying the update time improvements:
Theorem D.8. There exists an algorithm that uses space O (vQ log" (nQ)) bits, has worst-case update time O (vQ lolglll02000001 (5(2() and query time Ö (nQ)), and supports Q adaptive point queries with &- = 0.1 and with high probability.
E ADAPTIVE DISTANCE ESTIMATION
In the adaptive distance estimation problem, there exists set X (x())
x()) of n points in R4.
Given accuracy parameter 0. the goal is to output (1 + E) approximmaiinn to ||x( -qllp for each query q across all points x() E X, while minimizing the space, query time, or pre-processing time for the corresponding data structures. The trivial solution stores all n points and computes all distances each query point and thus can handle unlimited number of queries. Since each point has dimension d, the trivial solution uses space and query time O (nd). Cherapanamjeri &
Nelson (2020) first improved the query time to Ö n+td at the cost of using Ō (m+d]dd space and
nud pre-processing time. Like the trivial solution, the algorithm of Cherapanamjeri & Nelson (2020) also permits an arbitrary number of queries.
In this section, we first apply our framework to show a data structure that can handle Q queries of approximate distances from a specified point in X, using query time ① (=dd) pre-processing time
δ nd and space Ō (x+d)/² Hence for d >> n2/Q, our data structure already improves the work of Cherapanamjeri & Nelson (2020).
However in this setting, each of the Q queries returns only the approximate distance between query point and a single point in X. By comparison, Cherapanamjeri & Nelson (2020) outputs approximate distances to all points in and moreover, follow-up work by Cherapanamjeri & Nelson (2022) improved the pre- pre-processing time to (md) Therefore, we address these two shortcomings of our framework by giving a data structure that (1) handles the case where we return the approximate distances of all points in X from Q adaptive query points and (2) achieves pre- pre-processing time δ nd
For completeness, now show correctness of our algorithm across all Q adaptive queries, though we remark that the proof can simply be black-boxed into Theorem 1.2.
Theorem E.1. With high probability, we have
(1 [xi, y,ll2 d, (1 e)](x;, yall2.
20

---

Algorithm 7 Adaptive Distance Estimation
1: r + O (/Qlog((n))) +- O (log(nQ))
2: Let .e..,,,
1I, , E IRa be JL transformation matrix (see Theorem A.6 or Theorem A.7)
3: for for [r] do
4: Compute I1,x;
5:
for each query (y, 1) with y e gd, i [n] do
>Adaptive queries
6: Let S be set of k indices sampled (with replacement) from [r]
7:
for j E [A: do
8:
de, [[ss, (x: y)ll2
9:
d; < PrivMed {ds,s he(w)) where PrivMed is (1,0)-DI
10:
return d3
for all q E [Q]
Proof. Fix query (yg, 1g) with E [Q] and ig E [n]. Let S be a set of ls indices sampled (with replacement) from [r]. By Theorem A.6 or Theorem A.7, then we have for each [k]].
3
Pr (1 - ([1-s)[xx; sx,, y,l2 S [[Is, (Xi, y,)ll2 < (1 + +)|lx,, - Nolla]
Let I be an indicator variable so that I, if || -yll2 - |[T (xi, y,)ll s
(1 + xx; -y and I = otherwise, so that we have Pr [4 = 1] 2
3 1' or equivalently,
E [4, 2 3 Let = Σjen L so that by linearity of expectation, [[]] = 1/b EjEN B 2 -.-
To address adaptive queries, we first note that PrivMed is (1, -)-iifferenntillly private on the outputs of the Fast JL transforms. Since sample k O (log(n()) groups from the r O ( (vQ log (nQ)) groups with replacement, then by amplification via sampling, i.c., Theorem A.2, PrivMed is
(o ((Qiog(nq)) .0) -differentially private. Thus, by the advanced composition of differential
privacy, i.e., Theorem A.4, the mechanism permits Q adaptive queries and (O) poly(nq)) ) differentially private. By the generalization properties of differential privacy, i.e., Theorem A.5, we have
1
Pr
ΣΣ
B
<
10
n))y(Q,n)
JELK
for sufficiently small O (1). Thus have
Pr
Σ KE(M]
4 > 0.6 > poly(Q, n)
k
which implies that (1 (1-e)l[x;, Ygll2 < d2 < (1+))||x,, -y Therefore. by union bound across Q adaptive queries (y xt,) with q [Q], we have that (1-s) xx, -yyll2 2 S d, S (1+ yall2 for all E [Q] with high probability.
Theorem E.2. There exists an algorithm that answers Q adaptive distance estimation queries within
factor of (1 e). For O ( (Logd + dlog log(nQ)) query time, it stores O [nV (nQ)
words of space. For O (.l log(nQ)) query time, stores O (nvQ (ogg words of space.
Proof. By Theorem A.7, each fast JL transform uses o log + d log runtime and stores m
logd rows. On the other hand, by Theorem A.6, each JL transform uses O (# + d log d)
runtime and stores m = log
rows.
21

---

By comparison, Cherapanamjeri & Nelson (2020) uses O query time.
nd ndlog words of space and O
E. FASTER PRE-PROCESSING TIME FOR ADAPTIVE DISTANCE ESTIMATION
In this section, we present an improved algorithm for Adaptive Distance Estimation, which allows the release of distances to all n points in the datasct for a single query, matching the query time of Cherapanamjeri & Nelson (2020) with an improved space complexity of O VVQn). Our results utilize a class structured randomized linear transformations based on Hadamard matrices recursively defined below:
Ha/2 Ha/z
H1 = [1]
Ha
Ha/z
-Ha/2
The associated class of randomized linear transformations are now defined below:
{D) bemm C Rdxd s.t Di.
std
[N(0,
=
k.l
(0
otherwise
DL H2D²
Va Rd h(2)= =
2.
(SRHT)
: H2D"
Note that for any vector 2, h22) may be computed time Ommd log d) due the recursive definition of the Hadamard transform. We now let and & denote the pdf and edf of a standard normal random variable, Quant (fa vem)) the th quantile of multi-set of real numbers {ushee for any E N
and define v as follows:
Yr > 0, a E R: (a) == min([a], r).
Through the remainder of the section, we condition on the event defined in the following lemma:
Lemma E.3 (Claims 5.1 and 5.2 Cherapanamjeri & Nelson (2022)). For any 6 E (0, 1), with probability at least
Vz s.1 |||||| = : 2 s Quant 3/4/4 ((h(2)))<(mm) S Quant ((h(=)) S4
Vz | 1, 4 Avlog(1/e) (1 (1- c md sE[md]
(h+(())) - 1 2
as long 2 Cc Ce-2log(2/0) logo (d/E) for some absolute constant C' 0.
We will additionally require the following technical result from Cherapanamjeri & Nelson (2022), where for any vector E Rd and multiset S {igbsej with [d]. vi denotes the vector
[U....... 0iyl:
Lemma E.4 (Theorem 1.4 Cherapanamjeri & Nelson (2022)). Assume : Rdd - Rend (SRHT) satisfies the conclusion of Lemma E.3. Then, there an algorithm, RetNorm, which satisfies for all E Rd.
Ps {11 ((. |x||| < Re(Norm(((()s) S (1 (1+)) -|=]]] 2 f-r Uigssen with in itd Unif((md)
when k > -2 2og 1oog(/2/))) log((/)) some C > 0. Furthermore, RetNorm runs in time O(k).
With these primitives, we will construct our data structure for adaptive distance estimation. Our constructions formally described in Algorithm 8.
22

---

Algorithm 8 Adaptive Distance Estimation with SRHTs
1: m < C== logg (2dn/E)
2: Let h be an SRHT defined in SRHT
--Reeealed to analyst
3: + CVQ log"log (nd)., k + Ce-² (og(2/e) log(2nd)
4: for i [n] do
5: Compute y/1 h(x;))
6: for j E [r] do
7:
Let Let S be set of le indices sampled with replacement from [md]
8: I C'log(nd)
9:
for j E Q do
DAdaptive queries
10:
Receive query 4j U, + h-h(g;)
12:
for i E [m] do
Let [1r.s.)pp([] be a set of I indices sampled (with replacement) from
for p E [1] do
15:
di f RetNorm((uy Vi) s.........r
16:
dej- t (ddMMed((dd.pppeet where PrivMed is (O O)DD
17:
return (dr))
The proof of correctness of Algorithm 8 will follow along similar lines to that of Algorithm 6 with more refined analysis of the privacy loss incurred due to the adaptivity of the data analyst. In particular, each input query results in n different queries made to differentially private mechanism PrivMed leading to a total of nQ queries. naïve application of Theorem 1.2 would thus result in data structure with space complexity scaling as Ö(re/2vQQ as opposed to the desired (nnQQ) and query complexity nnd- The key insight yielding the improved result is the privacy loss incurred by a single query is effectively amortized across independent differentially private algorithms each capable of answering Q adaptively chosen queries correctly with high probability.
To start, we first condition on the event Lemma E.3 and assume public access the correspondingly defined SRHT h. We now use R to denote the randomness used to instantiate the multisets, Suj- in Algorithm and decompose corresponds to the randomness used to generate the set Si,j and the random elements 4i.p. As in the proof Theorem 1.2, we define a transcript T = {Ty betQ) with T, = (q), {d (iel)) denoting the jth query and the responses returned by Algorithm as single transaction.
follows = (Re)ven)) with R.
Rerber where R.
Lemma E.S. For all i E [n], E [Q]. is (o ((
differentially private with Rş.
Proof. The proof identical to that of Lemma C.I with the observation that each transaction T3 only results in single query to a differentially private mechanism operating on R.
Lemma E.6. For all [m), T is (o(1), polyinq; -differemtially private with respect to R..
Proof. The proof is identical to Lemma C.2 and follows from Theorem A.4 and Lemma E.5.
We now prove the correctness of our improved procedure for adaptive distance estimation.
Proof of Theorem 1.3: We condition the event in the conclusion of Lemma E.3 start by bounding the failure probability single query. The bound for the whole sequence of adaptively chosen queries follows by union bound. Now, fixing [n] and j [Q), note that the sub-transcript T()) (Tp) is (o(1), polliqq) -differentially private with respect to R, Furthermore, define the indicator random variables:
vp E W, 1 {11 =) ||q =x1l RetNorm (uy 34) )))s....)))) s (1+ 119 xall
23

---

Additionally, defining W := Ep=1 p. we get by the differential privacy of the sub-transcripl. TÚ)
Lemma E.4 and Theorem A.5:
W 3
P
400 (nQ)²*
Consequently, get from Theorem A.3 and another union bound:
1
P ((1 E) llq - =: _ d. _ (1 E) |1g - ==ll} 2
200 (nQ)²*
subsequent union bound over E [n]] j E [ yields:
P (vi E [n] [Q) (1 6) 1b क; di (1 (6) 11 1:11)
2
200 (nQ)
A final union bound over the conclusion of Lemma E.3 concludes the proof. The runtime guarantees follow from the fact that for all E Rd, h(2) is computable time ((md log d) and the runtime guarantees of RetNorm.
F ADAPTIVE KERNEL DENSITY ESTIMATION
Kernel density estimation is an important problem in learning theory and statistics that has recently attracted significant interest, e.g.. (Charikar & Siminelakis, 2017; Backurs et al., 2018 Charikan al., 2020; Bakshi et al., 2022). In the adaptive kernel density estimation problem, the input is set X (x(1) :.... x(")) of points in R. Given accuracy parameter
and threshold parameter 0. the goal is to output (1 + apprrxxmmato to the quantity 1 EiE(n) k(x(()) q).
for kernel function & under the promise that the output is at least A standard approach is to sample O TE" points and then use O re query time to output the empirical kernel density for
specific query. Backurs et al. (2019) give an algorithm for kernel density estimation that uses O 7E2
space and O
VTEz
query time, improving over the standard sampling approach.
Theorem F.1. Backurs et al. (2019) Given E, 0, there exists data structure D that uses O
(
query time that outputs (1 appproxiimttoon D(y) to a kernel density estimation query that has value at least т, i.e.,
space and O (V/
Pr[l KDE(X, SE KDE(X,)) 3
However, the analysis for both these algorithms fails for the adaptive setting, where there can be dependencies between the query and the data structure. By using the data structure of Backurs al. (2019) subroutine, our framework immediately implies an algorithm for adaptive kernel density estimation that uses ① QQ space and O dlogg queries.
query time to answer each of Q adaptive /78"
Algorithm 9 Adaptive Kernel Density Estimation
Input: Number Q of queries, accuracy s, threshold т
1: + O (VQ log" Q)
2: for [r] do
>Pre- Pre-processing
3: Let T; be KDE data structure
4: for each query Y, E Rd with q [Q] do
DAdaptive queries
5: Let S be set of k indices sampled (with replacement) from [r]
6: for i [k] do
7: Let D, be the output of Ts, on query Yq
8: return d,, PrivMed ((D.)eet))) where PrivMed is (1,0)-DP
show adversarial robustness of algorithm across Q adaptive queries. Again we remark that the proof can simply be black-boxed into Theorem 1.2, though we include the specific kernel density details in the following proof warm-up for the following section.
For completeness,
24

---

Lemma E.2. Algorithm 9 answers Q adaptive kernel density estimation queries within factor of (1+ E}, provided each query has value at least T.
Proof. Fix query Y4 E Rdd with q E [Q). Let S be a set of ls indices sampled (with replacement) from [r]. Then by Theorem F.1, we have that for each j E [k.]
Pr Ds, (y) - KDE(X, y) E KDE(X, 2
Let I be indicator variable that I, if Ds, (x) KDE(X, y) I E (DD(XXy) y) and 1 otherwise, so that we have Pr [4 1] N or equivalently, [4,]
3 Let 1 = E
so that E [4] = E E E
2 4.
To handle adaptive queries, we first note that PrivMed is (1,0) -differrettilly private on the out- puts of the r kernel density estimation data structures. We sample = O (log Q) indices from the r = O (vQ log² Q) data structures with replacement. Thus by amplification via sampling, ie., Theorem A.2, PrivMed is (o(volog 1 - private. By the advanced compo- sition of differential privacy, i.e., Theorem A.4, our algorithm can answer Q adaptive queries with (1) (Qly(Q)) -differentially privacy. By the generalization properties of differential privacy, i.e.,
Theorem A.5, we have
Pr
Σ
B
<
0.01,
k: JE[K
10
for sufficiently small constant O (1) in the private median algorithm PrivMed. Therefore,
Pr
Σ
1 0.6 0.99,
so that [dg KDE(XX, < KD)((X,)) across Q queries Yg with q E [Q].
Theorem F.3. There exists an algorithm that uses O (VQlug' Q) space and answers Q adaptive
(
kernel density estimation queries within factor of (1 (1+E),, provided each query has value least runtime.
Each query uses O d [log(nQ)
By comparison, random sampling, e.g., Charikar & Siminelakis (2017), uses Q samples to answer Q queries and each query uses O (+E2 runtime and using Q copies of the data structure by Backurs et al. (2019) uses O space and O runtime.
F.1 UNLIMITED ADAPTIVE QUERIES FOR KERNEL DENSITY ESTIMATION
In this section, we beyond the limits of our framework and analyze the case where there may be an unbounded number of adversarial queries.
Theorem 1.4. Suppose the kernel function is L-Lipschitz in the second variable for some L >>>>> 0, i.e., y) - k(x, z)1 < L - 2|I2 for all x,y, z E Rd. Moreover, suppose that for all ||x yll2 S we have k(x,y) S 3. Then an algorithm that produces a kernel density estimation data structure D that is L- L-Lipschitz over a set X of points with diameter at most A and outputs a
KDE queries with value at least 5 with probability at least 1- ò using space S(n, E, T, log 6) and query time T(n, T, log ö), then there exists KDE data structure that with probability at least 0.99, any number of KDE queries with value at least T using space S n. 0 (s) (7), O Id (At)))) and query time T 1. (T) (dlog (A+p)L )) et
outputs a (1 + E) apprroiiiatio
Proof. Given a set X C Rd of n points with diameter A, let N be an 5--net over a ball of radius A + p that contains X. More formally, let B be ball of radius (A () that contains X and for
25

---

every y E B, there exists a point A such that lly - z/12 S E7 We can construct the net greedily
so that [ (((++)))
We implement a data structure D that answers each (non-adaptive) kernel density estimation query with multiplicative approximation (1 + {) for any kernel density estimation query with value at least 2. with probability least 1 6, where 100]N Then by union bound, D correctly answers each kernel density estimation query /V with probability at least 0.99.
Let q E Rd be an arbitrary query such that KDE(X, q) 2 T. By assumption, we have that l|q - x||2 S p for some X and thus q E B. By the definition N, there exists some y W such that l yl12 3L. Then since k is L-Lipschitz in the second variable, we have
KDD(X, 9) KDE(X,
Σ XEX
k(x,9) 9)
1 Σ k(x,y) XEX
L S =11 1011-11222
ET 3n
Hence, KDE(X, implies that KDE(X, y) 2. Let Ky be the output of the data structure D on query y. Then by correctness of on N for any query with threshold at least &. we have
Ky - KDE y)
KDE(X,y).
3
Let Kg be the output of the data structure D on query y. Since the algorithm itself L-Lipschitz, then
Kgq Kyl S Lllq yl12 S ET Therefore by the triangle inequality, have that
3
[Kq KDE(X, 4)ه S [gq Kyl - Ky - KDE((X KDE(X.y) - KDE(DEEX,, q)]
ET
ET
s + KDE(X, +
3
3n
Since KDE(X,y) & KDE(X, q) + S then it follows that
E²T ET
IKq - KDE(X, $ ET E + KDE(X,9
3n + $ <<KDE q),
3
n
for n 2
In particular, campling-based algorithms for kernels that are Lipschitz are also Lipschitz. Thus to apply Theorem 1.4, it suffices to identify kernels that are L-Lipschitz and use the data structure of Theorem F.I. To that end, we note that the kernels k(x, y) = C+I[x-ylla for > and
C
k(x,y) = Ce -II-xyl are both Lipschitz for some function C. In particular, we have
C'
C
(k(x,y) k(x,2)l
C x||||~X00 y112
C+ || z 2||2
C ||x 22122
||x
y|
(C (0-l)))((C)) +
||x 2
y 2|12
C 80 kxx,)) = c+|xx-lla is -ipsschitz Similarly, since - is 1-Lipschitz, then
(xxx,y) k(xx Ce -1x--1x-y lxx-vlla -e- xx-2|12
< <011i zl|2 - ||x -ylaa 5 <Clyy -z|12,
so kxx,)) -x-Ixxylla is C-Lipschitz.
26

---

G EMPIRICAL EVALUATION
We empirically demonstrate the space and query time efficiency of our framework of Section C. We consider the problem of lg norm estimation where queries q1. 92.... are generated in an adaptive fashion and our goal is to output an estimate of 119:l12 for all i. This setting is a special case of adaptive distance estimation and captures the essence of our adversarial robustness framework. In addition, this same setting was investigated empirically in prior works Cherapanamjeri & Nelson (2020).
Consider the setting of Algorithm 6: it creates copies of an underlying randomized data structure and upon query, it subsamples & of them and outputs an answer aggregated via the private median. In our setting, the underlying algorithm will be the fast cathhhsoon-nndnnttrauue (JL) transform which is defined follows: it is the matrix PHD: F - R where D is a diagonal matrix with uniformly random +1 entries, H is the Hadamard transform, and P is a sampling matrix uniformly samples m rows of HD. Our algorithm will initialize copies of this matrix where the sampling matrix P and diagonal D will be the randomness which is "hidden" from the adversary. Upon query q. we sample different Fast JL data structures, input g to all of them, and proceed as in Algorithm 6. Note that this setting exactly mimics the theoretical guarantees of Section C and is exactly Algorithm 7 of Section E. In our experiments, d 4096, m = 250, r 200, and k 5. These are exactly the parameters chosen in prior works Cherapanamjeri & Nelson (2020). We will have 5000 adaptive queries q: which are described shortly. Our experiments are done on 2021 MI Macbook Pro with 32 gigabytes of RAM. We implemented all algorithms in Python 3.5 using Numpy. The Hadamard transform code is from Andoni et al. (2015)) and we use Google's 's differential privacy library² for the private median implementation.
Experimental Setup.
Baselines. We will consider three baselines. JL will denote a standard (Gaussian) JL map from dimension 4096 to 250. Baseline 1 will denote the algorithm of Cherapanamjeri & Nelson (2020). At a high level, it instantiates many independent copies of the standard Gaussian JL map and only feeds an incoming query into a select number of subsampled data structures. Note that our experimental setting is mimicking exactly that of Cherapanamjeri & Nelson (2020) where the same parameters (number of different underlying data structures) and & (number of subsampled data structures to use for query) were used. This ensures that both our algorithm and theirs have access to the same number of different JL maps and thus allows us to compare the two approaches on an equal footing. The last baseline, denoted as Baseline 2, is the main algorithm of Cherapanamjeri & Nelson (2022) which is the optimized version of Cherapanamjeri & Nelson (2020). At a high level, their algorithm proceeds similarly to that of Cherapanamjeri & Nelson (2020), except they employ Hadamard transforms (after multiplying the query entry-wise by random Gaussians), rather than using Gaussian JL maps. Furthermore, instead of subsampling, their algorithm feeds an incoming query into all the different copies of the Hadamard transform, and subsamples the coordinates of the concatenated output for norm estimation. We again set the parameters of their algorithm to match that of our algorithm and Baseline 1 by using copies of their Hadamard transform and subsampling mk total coordinates. We refer to the respective papers for full details of their algorithms.
Summary of adaptive queries. Our input queries are the same adaptive queries used in Chera- panamjeri & Nelson (2020). To summarize, let II denote the map used in the JL benchmark stated
above. The i-th query for 1 < I 5000 will be of the form g: Σラ=1 -y=1(-1) (-1)W.z,, zg. which we then normalize to have unit norm. The z; are standard Gaussian vectors. W; is the indicator variable for the event []][= - ei ll2 < ||I[(2; + ei )ll where e is the first standard basis vector. Intuitively, the queries become increasingly correlated with the matrix II since we successively "augment" the
queries in a biased fashion. See Section 5 of Cherapanamjeri & Nelson (2020) for a more detailed discussion of the adaptive inputs.
Results.
Our results are shown in Figure 1. In Figure Ia, we plot the norm estimated by each of the algorithms in each of the queries across iterations. We see that the naive JL map increasingly deviates from the true value of 1.0. This is intuitive as the adaptive queries are inereasingly correlated
'available in https: :/ "available in https: / //g thub. htt...ccomoogggg/ d/ fferential-privaant
LIB//PHT
27

---

1600
3.2
Bostrel
1400
Bodtr1 Basins
Basiins
1200
Extmatt
1000
Cumuuatttv Huntime
2.0
800
600
2.5
1.2
1.000
2000
3000
4000
5030
0
1000
2000
3000
4000
5030
(a)
(b)
(c)
Fig. Figures for our experiments.
with the map II. The performance of all other algorithms are indistinguishable in Figure la. Thus, we only zoom into the performances of our algorithm and Baseline and Baseline 2, shown in plot histogram of answers outputted by the respective
Figure 1b. For these three algorithms, algorithms across all iterations. We see that the algorithm of Cherapanamjeri & Nelson (2020), shown in the blue shaded histogram, the most accurate it has the smallest deviations from the true answer of 1.0. Our algorithm, shown in green, is noisier than Baseline 1 since it has wider range of variability. This may due the fact that we use differentially private median algorithm, which naturally incurs additional noise. Lastly, Baseline 2 is also noisier than Baseline and comparable to our algorithm. This may be due to the fact that the algorithm of Cherapanamjeri
Nelson (2022) requires very fine-tuned constants in their theoretical bounds, which naturally deviate in practice. Lastly, Figure Ic shows the cumulative runtime of all three algorithms across all iterations. Our algorithm, shown in green, is the fastest while Baseline 2 is the slowest. This is explained by the fact that Baseline 2 calculates many more Hadamard transforms than our algorithm does.
28


Reviews:
[{"review_id": "aVsaViHJJH", "reviewer": "Reviewer_iYm7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies algorithms that are robust to adversaries of limited power. This is interesting since the input to an algorithm in many situations can change dynamically, either natural or as the consequence of  an attack. The paper considers two such models: in the first one the adversary can only alter a few elements of the input (and this model is applied to linear algebraic algorithms). In the second setting the adversary is allowed a limited number of (adaptive) queries to the algorithm. In the latter setting, an idea from differential privacy is employed to hide the internals of the algorithm to the adversary and thus guarantee robustness. This setting is applied to a sequence of problems.\n\n", "summary_of_the_review": "This is a good paper and I recommend acceptance.", "strength_and_weaknesses": "Strengths:\n- interesting topic\n- well written paper\n- neat way of incorporating differential privacy result\n\nWeaknesses:\n- no empirical evaluation. It would be interesting to see how the algorithms perform in practice against other algorithms that are not-robust to adversarial intervention.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BQwJ5wNJAX", "reviewer": "Reviewer_n2fk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces training algorithms that are robust to bounded dynamics in the data, with a focus on label updates. \n\n\n----------------------\nUpdate: I thank the authors for their informative feedback. I have updated my overall recommendation but remain unconfident about it.  ", "summary_of_the_review": "My main concern is that it may not fit into the ICLR context. I'll be happy to change my evaluation if the authors and other reviewers may enlighten me regarding this point. ", "strength_and_weaknesses": "The work seems theoretically solid. However, it doesn't seem to fit into the representation learning context, especially the robustness questions. First, the models are primarily linear ones and the authors didn't give insight how these might scale to non-linear ones. Second, the perturbation in the target is interesting but the authors didn't explain what kind of applications it may find in reality. The paper seems fairly theoretical and very difficult to follow without the specific background. I'm wondering if the work would fit better in another venue. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6g-iBznHCw", "reviewer": "Reviewer_Kvip", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors investigate the space complexity and amortized round time or query time of the sequential (approximate) query answering problem under adversarial queries. First, they deal with the problem of sequentially answering the least-square objective value with an adversary who modifies the outcome values with L0 restriction. Second, they develop a general framework that can convert an algorithm working with stochastic queries to one for adversarial queries. They demonstrate many applications of their framework, including matrix-vector norm, linear regression, half-space query, point query on turnstile streams, distance estimation, and kernel density estimation. A general idea for dealing with these tasks is to hide the internal state from the adversary by utilizing the differentially private median. ", "summary_of_the_review": "The sequential estimation problem under adversarial queries is interesting and crucial. The first result for the sequential estimation of the least-square objective value is novel and significant. I'm thus currently recommending acceptance. However, I have some concerns regarding the implication of the first result and the originality of the second result of the general framework for adversarial sequential estimation. I'd like the authors to address such concerns in the rebuttal.", "strength_and_weaknesses": "Strength:\n- Sequential estimation under adversarial queries is interesting and well-motivated.\n- This paper gives novel and significant results for the sequential least-square objective value estimation under L0-restricted adversarial queries.\n\nWeakness:\n- The implication of the sequential least-square objective value estimation results is somewhat unclear.\n- This paper lacks a detailed comparison with some crucial related works, which makes me unsure about the significance of the results. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0SWPkkHSdt0", "reviewer": "Reviewer_w9hf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the setting where an algorithm/data structure has to give responses to a sequence of adversarially chosen inputs.\nThe paper considers tow separate settings:\n1. The consider linear regression $min_x \\|Ax =b\\|_2^2$ where the target $b$ can be updated in $K$ locations at each step. The goal is approximate the squared error.\n2. They consider a setting where you have a non-adaptive data structure for a problem. They show that in order to answer $Q$ adversarial queries,  rather than use $Q$ independent copies of the. data structure, one can use privacy amplification techniques to only maintain $\\sqrt{Q}$ copies.", "summary_of_the_review": "I think this paper is nice and ought to be accpted.", "strength_and_weaknesses": "I am not quite convinced by the first problem. I think the problem of how to not resolve linear regression under updates is natural, but I am not sure why you would only care about approximating the squared error rather computing a near-optimal solution. Typically, the loss is a means to the end of finding a good $x$, not the end in itself.\n\nI found the second result much more interesting and general. The use of differential privacy is nice (and is somewhat reminiscent of the adaptive data analysis paper of Dwork et. al). It gives them  black box results for distance and kernel density estimation, which they are able to improve on in some settings. Similar techniques seem to have been used earlier in work on the streaming model. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster