Adversarial Robustness of Streaming Algorithms through Importance Sampling

Abstract:
Robustness against adversarial attacks has recently been at the forefront of algorithmic design for machine learning tasks. In the adversarial streaming model, an adversary gives an algorithm a sequence of adaptively chosen updates u1, . . . , un as a data stream. The goal of the algorithm is to compute or approximate some predetermined function for every prefix of the adversarial stream, but the adversary may generate future updates based on previous outputs of the algorithm. In particular, the adversary may gradually learn the random bits internally used by an algorithm to manipulate dependencies in the input. This is especially problematic as many important problems in the streaming model require randomized algorithms, as they are known to not admit any deterministic algorithms that use sublinear space. In this paper, we introduce adversarially robust streaming algorithms for central machine learning and algorithmic tasks, such as regression and clustering, as well as their more general counterparts, subspace embedding, low-rank approximation, and coreset construction. For regression and other numerical linear algebra related tasks, we consider the row arrival streaming model. Our results are based on a simple, but powerful, observation that many importance sampling-based algorithms give rise to adversarial robustness which is in contrast to sketching based algorithms, which are very prevalent in the streaming literature but suffer from adversarial attacks. In addition, we show that the well-known merge and reduce paradigm in streaming is adversarially robust. Since the merge and reduce paradigm allows coreset constructions in the streaming setting, we thus obtain robust algorithms for k-means, k-median, k-center, Bregman clustering, projective clustering, principal component analysis (PCA) and non-negative matrix factorization. To the best of our knowledge, these are the first adversarially robust results for these problems yet require no new algorithmic implementations. Finally, we empirically confirm the robustness of our algorithms on various adversarial attacks and demonstrate that by contrast, some common existing algorithms are not robust.

heading: 1 Introduction
text: Robustness against adversarial attacks have recently been at the forefront of algorithmic design for machine learning tasks [GSS15, CW17, AEIK18, MMS+18, TSE+19]. We extend this line of work by studying adversarially robust streaming algorithms.
In the streaming model, data points are generated one at a time in a stream and the goal is to compute some meaningful function of the input points while using a limited amount of memory, typically
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
sublinear in the total size of the input. The streaming model is applicable in many algorithmic and ML related tasks where the size of the data far exceeds the available storage. Applications of the streaming model include monitoring IP traffic flow, analyzing web search queries [LMV+16], processing large scientific data, feature selection in machine learning [HZZ21, GRB+19, WYWD10], and estimating word statistics in natural language processing [GDC12] to name a few. Streaming algorithms have also been implemented in popular data processing libraries such as Apache Spark which have implementations for streaming tasks such as clustering and linear regression [ZXW+16a].
In the adversarial streaming model [MBN+17, BMSC17, AMYZ19, BY20, BJWY20, HKM+20, WZ20, ABD+21, KMNS21], an adversary gives an algorithm a sequence of adaptively chosen updates u1, . . . , un as a data stream. The goal of the algorithm is to compute or approximate some predetermined function for every prefix of the adversarial stream, but the adversary may generate future updates based on previous outputs of the algorithm. In particular, the adversary may gradually learn the random bits internally used by an algorithm to manipulate dependencies in the input. This is especially problematic as many important problems in the streaming model require randomized algorithms, as they are known to not admit any deterministic algorithms that use sublinear space. Studying when adversarially robust streaming algorithms are possible is an important problem in lieu of recent interest in adversarial attacks in ML with applications to adaptive data analysis.
Formally, we define the model as a two-player game between a streaming algorithm StreamAlg and a source Adversary of adaptive and adversarial input to StreamAlg. At the beginning of the game, a fixed queryQ is determined and asks for a fixed function for the underlying dataset implicitly defined by the stream. The game then proceeds in rounds, and in the t-th round,
(1) Adversary computes an update ut ∈ [n] for the stream, which depends on all previous stream updates and all previous outputs from StreamAlg.
(2) StreamAlg uses ut to update its data structures Dt, acquires a fresh batch Rt of random bits, and outputs a response At to the query Q.
(3) Adversary observes and records the response At.
The goal of Adversary is to induce StreamAlg to make an incorrect response At to the query Q at some time t ∈ [m] throughout the stream.
Related Works. Adversarial robustness of streaming algorithms has been an important topic of recent research. On the positive note, [BJWY20] gave a robust framework for estimating the Lp norm of points in a stream in the insertion-only model, where previous stream updates cannot later be deleted. Their work thus shows that deletions are integral to the attack of [HW13]. Subsequently, [HKM+20] introduced a new algorithmic design for robust Lp norm estimation algorithms, by using differential privacy to protect the internal randomness of algorithms against the adversary. Although [WZ20] tightened these bounds, showing that essentially no losses related to the size of the input n or the accuracy parameter ε were needed, [KMNS21] showed that this may not be true in general. Specifically, they showed a separation between oblivious and adversarial streaming in the adaptive data analysis problem.
[BY20] showed that sampling is not necessarily adversarially robust; they introduce an exponentially sized set system where a constant number of samples, corresponding to the VC-dimension of the set system, may result in a very unrepresentative set of samples. However, they show that with an additional logarithmic overhead in the number of samples, then Bernoulli and or reservoir sampling are adversarially robust. This notion is further formalized by [ABD+21], who showed that the classes that are online learnable requires essentially sample-complexity proportional to the Littlestone’s dimension of the underlying set system, rather than VC dimension. However, these sampling procedures are uniform in the sense that each item in the stream is sampled with the same probability. Thus the sampling probability of each item is oblivious to the identity of the item. By contrast, we show the robustness for a variety of algorithms based on non-oblivious sampling, where each stream item is sampled with probability roughly proportional to the “importance” of the item.

heading: 1.1 Our Contributions
text: Our main contribution is a powerful yet simple statement that algorithms based on non-oblivious sampling are adversarially robust if informally speaking, the process of sampling each item in the
stream can be viewed as using fresh randomness independent of previous steps, even if the sampling probabilities depend on previous steps.
Let us describe, very informally, our meta-approach. Suppose we have an adversarial stream of elements given by u1, . . . , un. Our algorithm A will maintain a data structure At at time t which updates as the stream progresses. A will use a function g(At, ut) to determine the probability of sampling item ut to update At to At+1. The function g measures the ‘importance’ of the element ut to the overall problem that we wish to solve. For example, if our application is k-means clustering and ut is a point far away from all previously seen points so far, we want to sample it with a higher probability. We highlight that even though the sampling probability for ut given by g(At, ut) is adversarial, since the adversary designs ut and previous streaming elements, the coin toss performed by our algorithm A to keep item ut is independent of any events that have occurred so far, including the adversary’s actions. This new randomness introduced by the independent coin toss is a key conceptual step in the analysis for all of the applications listed in Figure 1.
Contrast this to the situation where a “fixed” data structure or sketch is specified upfront. In this case, we would not be adaptive to which inputs ut the adversary designs to be “important” for our problem which would lead us to potentially disregard such important items rendering the algorithm ineffective.
As applications of our meta-approach, we introduce adversarially robust streaming algorithms for two central machine learning tasks, regression and clustering, as well as their more general counterparts, subspace embedding, low-rank approximation, and coreset construction.
We show that several methods from the streaming algorithms “toolbox”, namely merge and reduce, online leverage score sampling, and edge sampling are adversarially robust “for free.” As a result, existing (and future) streaming algorithms that use these tools are robust as well. We discuss our results in more detail below and provide a summary of our results and applications in Figure 1.
We first show that the well-known merge and reduce paradigm is adversarially robust. Since the merge and reduce paradigm defines coreset constructions, we thus obtain robust algorithms for k-means, k-median, Bregman clustering, projective clustering, principal component analysis (PCA), non-negative matrix factorization (NNMF) [LK17].
Theorem 1.1 (Merge and reduce is adversarially robust) Given an offline ε-coreset construction, the merge and reduce framework gives an adversarially robust streaming construction for an ε-coreset with high probability.
For regression and other numerical linear algebra related tasks, we consider the row arrival streaming model, in which the adversary generates a sequence of row vectors a1, . . . ,an in d-dimensional vector space. For t ∈ [n], the t-th prefix of the stream induces a matrix At ∈ Rt×d with rows a1, . . . ,at. We denote this matrix as At = a1 ◦ . . . ◦ at and define κ to be an upper bound on the largest condition number1 of the matrices A1, . . . ,An.
Theorem 1.2 (Row sampling is adversarially robust) There exists a row sampling based framework for adversarially robust streaming algorithms that at each time t ∈ [n]:
1the ratio of the largest and smallest nonzero singular values
(1) Outputs a matrix Mt such that (1 − ε)A>t At M>t Mt (1 + ε)A>t At, while sampling O ( d2κ ε2 log n log κ ) rows (spectral approximation/subspace embedding/linear regres-
sion/generalized regression).
(2) Outputs a matrix Mt such that for all rank k orthogonal projection matrices P ∈ Rd×d,
(1− ε) ‖At −AtP‖2F ≤ ‖Mt −MtP‖ 2 F ≤ (1 + ε) ‖At −AtP‖ 2 F , while sampling O ( dkκ ε2 log n log 2 κ )
rows (projection-cost preservation/low-rank approximation).
(3) Outputs a matrix Mt such that (1 − ε) ‖Atx‖1 ≤ ‖Mtx‖1 ≤ (1 + ε) ‖Atx‖1, while sampling O ( d2κ ε2 log 2 n log κ ) rows (L1 subspace embedding).
Finally, we show that our analysis also applies to algorithms for graph sparsification for in which edges are sampled according to their “importance”. Define κ as the ratio of the largest and the smallest cut sizes in G (see Section 4 and Supplementary Section C for exact details).
Theorem 1.3 Given a weighted graph G = (V,E) with |V | = n whose edges e1, . . . , em arrive sequentially in a stream, there exists an adversarially robust streaming algorithm that outputs a 1± ε cut sparsifier with O ( κ2n logn
ε2
) edges with probability 1− 1/ poly(n).
Sketching vs Sampling Algorithms. A central tool for randomized streaming algorithms is the use of linear sketches. These methods maintain a data structure f such that after the (i+ 1)-th input xi, we can update f by computing a linear function of xi. Typically, these methods employ a random matrix. For example, if the input consists of vectors, sketching methods will use a random matrix to project the vector into a much smaller dimension space. In [HW13], it was proved no linear sketch can approximate the L2-norm within a polynomial multiplicative factor against such an adaptive adversary. In general, streaming algorithms that use sketching are highly susceptible to the type of attack described in [HW13] where the adversary can effectively ‘learn’ the kernel of the linear function used and send inputs along the kernel. For example, if an adversary knows the kernel of the random matrix used to project the input points, then by sending points that lie on the kernel of the matrix as inputs, the adversary can render the whole streaming algorithm useless.
One the other hand, we employ a different family of streaming algorithms that are based on sampling the input rather than sketching it. Surprisingly, this simple change allows one to automatically get many adversarially robust algorithms either “for free” or without new algorithmic overheads. For more information, see Section 1.1. We emphasize that while our techniques are not theoretically sophisticated, we believe its power lies in its simple message that sampling is often superior to sketching for adversarial robustness. In addition to downstream algorithmic and ML applications, this provides an interesting separation and trade-offs between the two paradigms; for non adversarial inputs sketching often gives similar or better performance guarantees for many tasks [BYKS01].

heading: 2 Merge and Reduce
text: We show that the general merge and reduce paradigm is adversarially robust. Merge and reduce is widely used for the construction of a coreset, which provides dimensionality reduction on the size of an underlying dataset, so that algorithms for downstream applications can run more efficiently:
Definition 2.1 (ε coreset) Let P ⊂ X be a set of elements from a universe X , z ≥ 0, ε ∈ (0, 1), and (P,dist, Q) be a query space. Then a subset C equipped with a weight function w : P → R is called an ε-coreset with respect to the query space (P,dist, Q) if
(1− ε) ∑ p∈P dist(p, Q)z ≤ ∑ p∈C w(p) dist(p, Q)z ≤ (1 + ε) ∑ p∈P dist(p, Q)z.
The study of efficient offline coreset constructions for a variety of geometric and algebraic problems forms a long line of active research. For example, offline coreset constructions are known for linear
regression, low-rank approximation, L1-subspace embedding, k-means clustering, k-median clustering, k-center, support vector machine, Gaussian mixture models, M -estimators, Bregman clustering, projective clustering, principal component analysis, k-line center, j-subspace approximation, and so on. Thus, our result essentially shows that using the merge and reduce paradigm, these offline coreset constructions can be extended to obtain robust and accurate streaming algorithms. The merge and reduce paradigm works as follows. Suppose we have a stream p1, . . . , pn of length n = 2k for some
Theorem 2.2 There exists a merge-and-reduce row sampling based framework for adversarially robust streaming algorithms that at each time t ∈ [n]:
(1) Outputs a matrix Mt such that (1 − ε)A>t At M>t Mt (1 + ε)A>t At, while sampling O ( d2
ε2 log 4 n log κ
) rows (spectral approximation/subspace embedding/linear regres-
sion/generalized regression).
(2) Outputs a matrix Mt such that for all rank k orthogonal projection matrices P ∈ Rd×d, (1− ε) ‖At −AtP‖2F ≤ ‖Mt −MtP‖ 2 F ≤ (1 + ε) ‖At −AtP‖ 2 F ,
while sampling O ( k ε2 log 4 n log2 κ )
rows (projection-cost preservation/low-rank approximation).
(3) Outputs a matrix Mt such that (1 − ε) ‖Atx‖1 ≤ ‖Mtx‖1 ≤ (1 + ε) ‖Atx‖1, while sampling O ( d ε2 log 5 n log κ ) rows (L1 subspace embedding).
Using coresets of [HV20], then Theorem 1.1 also gives applications for (k, z)-clustering such as k-median for z = 1 and k-means for z = 2. Moreover, [LK17] noted that constructions of [FL11] give coresets for Bregman clustering, which handles µ-similar Bregman divergences such as the Itakura-Saito distance, KL-divergence, Mahalanobis distance, etc.
Theorem 2.3 There exists a merge-and-reduce importance sampling based framework for adversarially robust streaming algorithms that at each time t:
(1) Outputs a set of centers that gives a (1 + ε)-approximation to the optimal (k, z)clustering, k-means clustering (z = 2), and k-median clustering (z = 1), while storing O (
1 ε2z+2 k log 2z+2 n log k log k lognε
) points.
(2) Outputs a set of centers that gives a (1 + ε)-approximation to the optimal k-Bregman clustering, while storing O ( 1 ε2 dk 3 log3 n ) points.
Using the sensitivity bounds of [VX12a, VX12b] and the coreset constructions of [BFL16], then Theorem 1.1 also gives applications for the following shape fitting problems:
Theorem 2.4 There exists a merge-and-reduce importance sampling based framework for adversarially robust streaming algorithms that at each time t:
(1) Outputs a set of lines that gives a (1 + ε)-approximation to the optimal k-lines clustering, while storing O ( d ε2 f(d, k)k f(d,k) log4 n ) points of Rd, for a fixed function f(d, k).
(2) Outputs a subspace that gives a (1 + ε)-approximation to the optimal dimension j subspace approximation, while storing O ( d ε2 g(d, j)k g(d,j) log4 n )
points of Rd, for a fixed function g(d, j).
(3) Outputs a set of subspaces that gives a (1+ε)-approximation to the optimal (j, k)-projective clustering, while storing O ( d ε2 h(d, j, k) log 3 n(log n)h(d,j,k) )
points of Rds, for a fixed function h(d, j, k), for a set of input points with integer coordinates.
Adversarially robust approximation algorithms for Bayesian logistic regression, Gaussian mixture models, generative adversarial networks (GANs), and support vector machine can be obtained from Theorem 1.1 and coreset constructions of [HCB16, FKW19, SZG+20, TBFR20]; a significant number of additional applications of Theorem 1.1 using coreset constructions can be seen from recent surveys on coresets, e.g., see [LK17, Fel20]. The merge-and-reduce framework also has applications to a large number of other problems such as finding heavy-hitters [MG82] or frequent directions [GLPW16] and in various settings, such as the sliding window model [DGIM02], time decay models [BLUZ19] or for at-the-time or back-in-time queries [SZP+21].

heading: 3 Adversarial Robustness of Subspace Embedding and Applications
text: We use [n] to represent the set {1, . . . , n} for an integer n > 0. We typically use bold font to denote vectors and matrices. For a matrix A, we use A−1 to denote the Moore-Penrose inverse of A. We first formally define the goals of our algorithms:
Problem 3.1 (Spectral Approximation) Given a matrix A ∈ Rn×d and an approximation parameter ε > 0, the goal is to output a matrix M ∈ Rm×d with m n such that (1 − ε) ‖Ax‖2 ≤ ‖Mx‖2 ≤ (1 + ε) ‖Ax‖2 for all x ∈ Rd or equivalently, (1− ε)A>A M>M (1 + ε)A>A.
We note that linear regression is a well-known specific application of spectral approximation.
Problem 3.2 (Projection-Cost Preservation) Given a matrix A ∈ Rn×d, a rank parameter k > 0, and an approximation parameter ε > 0, the goal is to find a matrix M ∈ Rm×d with m n such that for all rank k orthogonal projection matrices P ∈ Rd×d,
(1− ε) ‖A−AP‖2F ≤ ‖M−MP‖ 2 F ≤ (1 + ε) ‖A−AP‖ 2 F .
Note if M is a projection-cost preservation of A, then its best low-rank approximation can be used to find a projection matrix that gives an approximation of the best low-rank approximation to A.
Problem 3.3 (Low-Rank Approximation) Given a matrix A ∈ Rn×d, a rank parameter k > 0, and an approximation parameter ε > 0, find a rank k matrix M ∈ Rn×d such that (1 − ε) ∥∥A−A(k)∥∥2F ≤ ‖A−M‖2F ≤ (1 + ε)∥∥A−A(k)∥∥2F , where A(k) for a matrix A denotes the best rank k approximation to A.
Problem 3.4 (L1-Subspace Embedding) Given a matrix A ∈ Rn×d and an approximation parameter ε > 0, the goal is to output a matrix M ∈ Rm×d with m n such that (1 − ε) ‖Ax‖1 ≤ ‖Mx‖1 ≤ (1 + ε) ‖Ax‖1 for all x ∈ Rd.
We consider the general class of row sampling algorithms, e.g., [CMP16, BDM+20]. Here we maintain a Lp subspace embedding of the underlying matrix by approximating the online Lp sensitivities of each row as a measure of importance to perform sampling. For more details, see Algorithm 1.
Definition 3.5 (Online Lp Sensitivities) For a matrix A = a1 ◦ . . . ◦ an ∈ Rn×d, the online sensitivity of row ai for each i ∈ [n] is the quantity maxx∈Rd |〈ai,x〉|p ‖Aix‖pp , where Ai−1 = a1 ◦ . . .◦ai−1.
Algorithm 1 Row sampling based algorithms, e.g., [CMP16, BDM+20] Input: A stream of rows a1, . . . ,an ∈ Rd, parameter p > 0, and an accuracy parameter ε > 0 Output: A (1 + ε) Lp subspace embedding.
1: M← ∅ 2: α← Cdε2 log n with sufficiently large parameter C > 0 3: for each row ai, i ∈ [n] do 4: if ai ∈ span(M) then 5: τi ← 2 ·maxx∈Rd,x∈span(M) |〈ai,x〉|p ‖Mx‖pp+|〈ai,x〉|p .See Remark 3.6 6: else 7: τi ← 1 8: pi ← min(1, ατi) 9: With probability pi, M←M ◦ ai
p 1/p i
.Online sensitivity sampling
10: return M
We remark on standard computation or approximation of the online Lp sensitivities, e.g., see [CEM+15, CMP16, CMM17, BDM+20].
Remark 3.6 We note that for p = 1, a constant fraction approximation to any online Lp sensitivity τi such that τi > 1poly(n) can be computed in polynomial time using (offline) linear programming while for p = 2, τi is equivalent to the online leverage score of ai, which has the closed form expression a>i (A > i Ai) −1ai, which can be approximated by a>i (M >M)−1ai, conditioned on M being a good approximation to Ai−1 when ai is in the span of M. Otherwise, τi takes value 1 when ai is not in the span of M.
Lemma 3.7 (Adversarially Robust Lp Subspace Embedding and Linear Regression) Given ε > 0, p ∈ {1, 2}, and a matrix A ∈ Rn×d whose rows a1, . . . ,an arrive sequentially in a stream with condition number at most κ, there exists an adversarially robust streaming algorithm that outputs a (1 + ε) spectral approximation with high probability. The algorithm samples O ( d2κ2 ε2 log n log κ )
rows for p = 2 and O ( d2λ2
ε2 log 2 n log κ
) rows for p = 1, with high probability, where λ is a ratio
between upper and lower bounds on ‖A‖1.
We also show robustness of row sampling for low-rank approximation by using online ridge-leverage scores. Together, Lemma 3.7 and Lemma 3.8 give Theorem 1.2.
Lemma 3.8 (Adversarially Robust Low-Rank Approximation) Given accuracy parameter ε > 0, rank parameter k > 0, and a matrix A ∈ Rn×d whose rows a1, . . . ,an arrive sequentially in a stream with condition number at most κ, there exists an adversarially robust streaming algorithm that outputs a (1 + ε) low-rank approximation with high probability. The algorithm samples
O ( kdκ2 ε2 log n log κ ) rows with high probability.

heading: 4 Graph Sparsification
text: In this section, we highlight how the sampling paradigm gives rise to an adversarially robust streaming algorithm for graph sparsification. First, we motivate the problem of graph sparsification. Massive graphs arise in many theoretical and applied settings, such as in the analysis of large social or biological networks. A key bottleneck in such analysis is the large computational resources, in both memory and time, needed. Therefore, it is desirable to get a representation of graphs that take up far less space while still preserving the underlying “structure” of the graph. Usually the number of vertices is much fewer than the number of edges; for example in typical real world graphs, the number of vertices can be several orders of magnitude smaller than the number of edges (for example, see the graph datasets in [RA15]). Hence, a natural benchmark is to reduce the number of edges to be comparable to the number of vertices.
The most common notion of graph sparsification is that of preserving the value of all cuts in the graph by keeping a small weighted set of edges of the original graph. More specifically, suppose our
graph is G = (V,E) and for simplicity assume all the edges have weight 1. A cut of the graph is a partition of V = (C, V \ C) and the value of a cut, ValG(C), is defined as the number of edges that cross between the vertices in C and V \C. A graph H on the same set of vertices as V is a sparsifier if it preserves the value of every cut in G and has a few number of weighted edges. For a precise formulation, see Problem 4.1.
In addition to being algorithmically tractable, this formulation is natural since it preserves the underlying cluster structure of the graph. For example, if there are two well connected components separated by a sparse cut, i.e. two distinct communities, then the sparsifier according to the definition above will ensure that the two communities are still well separated. Conversely, by considering any cut within a well connected component, it will also ensure that any community remains well connected (for more details, see [SPR11] and references therein). Lastly, graph sparsification has been considered in other frameworks such as differential privacy [EKKL20], distributed optimization [WWLZ18], and even learning graph sparsification using deep learning methods [ZZC+20]. The formal problem definition of graph sparsification is as follows.
Problem 4.1 (Graph Sparsification) Given a graph weighted G = (V,E) with |V | = n, |E| = m, and an approximation parameter ε > 0, compute a weighted subgraph H of G on the same set of vertices such that
(1) every cut in H has value between 1− ε and 1 + ε times its value in G: (1− ε)ValG(C) ≤ ValH(C) ≤ (1 + ε)ValG(C) for all cuts C where ValG(C),ValH(C) denotes the cost of the cut in the graphs G and H respectively and for the latter quantity, the edges are weighted,
(2) the number of edges in H is O ( n logn ε2 ) .
Ignoring dependence on ε, there are previous results that already get sparsifiers H with O(n log n) edges [BK96, SS08]. Their setting is when the entire graph is present up-front in memory. In contrast, we are interested in the streaming setting where future edges can depend on past edges as well as revealed randomness of an algorithm while processing the edges.
Our main goal is to show that the streaming algorithm from [AG09] (presented in Algorithm 2 in the supplementary section), which uses a sampling procedure to sample edges in a stream, is adversarially robust, albeit with a slightly worse guarantee for the number of edges. Following the proof techniques of the non streaming algorithm given in [BK96], it is shown in [AG09] that Algorithm 2 outputs a subgraph H such that H satisfies the conditions of Problem 4.1 with probability 1− 1/ poly(n) where the probability can be boosted by taking a larger constant C. We must show that this still holds true if the edges of the stream are adversarially chosen, i.e., when new edges in the stream depend on the previous edges and the randomness used by the algorithm so far. We thus again use a martingale argument; the full details are given in Supplementary Section C. As in Section 3, we let κ1 and κ2 to be deterministic lower/upper bounds on the size of any cut in G and define κ = κ2/κ1.
Theorem 1.3 Given a weighted graph G = (V,E) with |V | = n whose edges e1, . . . , em arrive sequentially in a stream, there exists an adversarially robust streaming algorithm that outputs a 1± ε cut sparsifier with O ( κ2n logn
ε2
) edges with probability 1− 1/ poly(n).

heading: 5 Experiments
text: To illustrate the robustness of importance-sampling-based streaming algorithms we devise adversarial settings for clustering and linear regression. With respect to our adversarial setting, we show that the performance of a merge-and-reduce based streaming k-means algorithm is robust while a popular streaming k-means implementation (not based on importance sampling) is not. Similarly, we show the robustness superiority of a streaming linear regression algorithm based on row sampling over a popular streaming linear regression implementation and over sketching.
Streaming k-means In this adversarial clustering setting we consider a series of point batches where all points except those in the last batch are randomly sampled from a two dimensional standard normal distribution and points in the last batch similarly sampled but around a distant center (see the data points realization in both panels of Figure 3). We then feed the point sequence
to StreamingKMeans, the streaming k-means implementation of Spark [ZXW+16b] the popular big-data processing framework. As illustrated in the left panel of Figure 3, the resulting two centers are both within the origin. Now, this result occurs regardless of the last batch’s distance from the origin, implying that the per-sample loss performance of the algorithm can be made arbitrarily large. Alternatively, we used a merge-and-reduce based streaming k-means algorithm and show that one of the resulting cluster centers is at the distant cluster (as illustrated in the right panel of Figure 3) thereby keeping the resulting per sample loss at the desired minimum. Specifically we use Streamkm, an implementation of StreamKM++ [AMR+12] from the ClusOpt Core library [Mac20].
Streaming linear regression. Similar to the clustering setting, in the adversarial setting for streaming linear regression all batches except the last one are sampled around a constellation of four points in the plane such that the optimal regression line is of −1 slope through the origin (see the leftmost panel of Figure 4). The last batch of points however, is again far from the origin (L,L) such that the resulting optimal regression line is of slope 1 through the origin2. We compare the performance of LinearRegression from the popular streaming machine learning library River [MHM+20] to our own row sampling based implementation of streaming linear regression along the lines of Algorithm 1 and observe the following: Without the last batch of points, both implementations result in the optimal regression line, however, the River implementation reaches that line only after several iterations, while our implementation is accurate throughout (This is illustrated in the second-left panel of Figure 4). When the last batch is used, nevertheless, Algorithm 1 picks up the drastic change and adapts immediately to a line of the optimal slope (the blue line of the second right panel of Figure 4) while the River implementation update merely moves the line in the desired direction (the orange line in that same panel) but is far from catching up. Finally, the rightmost panel of Figure 4) details the loss trajectory for both implementations. While the River loss skyrockets upon the last batch, the loss of Algorithm 1 remains relatively unaffected, illustrating its adversarial robustness.
Note that in both the clustering and linear regression settings above the adversary was not required to consider the algorithms internal randomization to achieve the desired effect (this is due to the local nature of the algorithms computations). This is no longer the case in the following last setting.
Sampling vs. sketching. Finally, we compare the performance of the leverage sampling Algorithm 1 to sketching. In this setting, for a random unit sketching matrix S (that is, each of its elements is sampled from {−1, 1} with equal probability), we create an adversarial data stream A such that its columns are in the null space of S. As a result, the linear regression as applied to the sketched data S ·A as a whole is unstable and might significantly differ from the resulting linear regression applied to streamed prefixes of the sketched data. As illustrated in Figure 5, this is not the case when applying the linear regression to the original streamed data A using Algorithm 1. Upon the last batch, the performance of the sketching-based regression deteriorates by orders of magnitude, while the performance of Algorithm 1 is not affected. Moreover, the data reduction factor achieved by leveraged sampling3 is almost double compared to the data reduction factor achieved by sketching.

heading: Acknowledgments
text: Sandeep Silwal was supported in part by a NSF Graduate Research Fellowship Program. Samson Zhou was supported by a Simons Investigator Award of David P. Woodruff.
2For MSE loss, this occurs for L at least the square root of the number of batches. 3The original stream A contained 2000 samples, each of dimension 10.

Review summaries:
Many streaming algorithms developed during the last decades are randomized and have an expected solution guarantee (approximation guarantee).  However, the promised guarantee is not with respect to an adaptive adversary that can choose the remaining part of the instance as a function of the decisions taken so far of the algorithm (and thus as a function of the random bits). This has prompted recent work on "adversarial robustness of streaming" to obtain guarantees regarding these stronger adaptive adversaries. First it has been shown that sketching based algorithms (i.e., sample a dimension-reduction matrix before the stream) is not robust against adaptive adversaries. This is because, the adversary can figure out the used matrix and then feed a worst-case instance.  The present paper has a more positive message. They show that a large family of streaming algorithms are in fact also robust against adaptive adversaries. On a high level they show that sampling based algorithms that roughly work as follows: before the arrival of an element e, we calculate a threshold for taking that element e based on the current state of the algorithm (and thus already used randomness). However, we use *new* randomness for deciding wether to take the element or not.  Such sampling based algorithms have been heavily used for e.g. clustering, graph sparsification and regression.   The main result of the paper is this observation together with tons of applications of prior algorithms that the authors list. 

This paper studies adversarial robust streaming algorithms. In the streaming model, there are many randomized algorithms. An adversary gives a sequence of update to the algorithm adaptively to learn the random bits used by the outputs of the algorithm. A adversarial robust streaming algorithm is robust to any adversarial updates. This paper gives an observation that if the streaming algorithm is sampling based and the random bit for each item is fresh, then the algorithm is robust even though the sampling probability depends on the previous random bits.