Adversarial Robustness of Streaming Algorithms through Importance Sampling
Authors: Vladimir Braverman
Avinatan Hassidim
Yossi Matias
Mariano Schain
Sandeep Silwal
Samson Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial robustness
streaming algorithms
coresets

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 $u_1,\ldots,u_n$ 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. 

Adversarial Robustness of Streaming Algorithms through Importance Sampling
Vladimir Braverman
Avinatan Hassidim Google
Yossi Matias
Google vbravernanngoogle..u com
Google yossi@google. com
avinatanOgoogle.cmm com
Mariano Schain
Sandeep Silwal MIT
Samson Zhou Carnegie Mellon University
Google marianos@google.com com
silwalemit.edo edu
samsonzhou@gmail. com
Abstract
Robustness against adversarial attacks has recently been the forefront of algo- rithmic design for machine learning tasks. In the adversarial streaming model, an adversary gives an algorithm sequence of adaptively chosen updates .1...., Un as data stream. The goal of the algorithm is to compute 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 par- ticular, the adversary may gradually learn the random bits internally used by an algorithm manipulate dependencies in the input. This is especially problematic as many important problems
streaming model require randomized algorithms, they are known not admit any deterministic algorithms that use sublinear space. this paper, we introduce adversarially robust streaming algorithms for central machine learning and algorithmic tasks, such regression and cluster- ing, 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 simple, but powerful, observation that many importance sampling- based algorithms give rise to adversarial robustness which 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 factoriza- tion. To the best 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.
Introduction
Robustness against adversarial attacks have recently been at the forefront of algorithmic design for machine learning tasks [GSS15, CW17, AEIKI8, MMS+ 18, TSE 19]. We extend this line of work by studying adversarially robust streaming algorithms.
In the streaming model, data points generated at time in stream and the goal is compute some meaningful function the input points while using a limited amount of memory, typically
35th Conference on Neural Information Processing Systems (NcurIPS 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 [HZ7211, GRB+19 19, WYWD100, and estimating word statistics in natural language processing [GDC12] to name 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 WZ20, 21D KMNS2I], an adversary gives an algorithm sequence of adaptively chosen updates ui..... Uh as a data stream. The goal of the algorithm 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 especially problematic as many important problems in the streaming model require randomized algorithms, 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 lieu of recent interest in adversarial attacks in ML with applications to adaptive data analysis.
Formally. we define the model 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 query Q is determined and asks for fixed function for the underlying dataset implicitly defined by the stream. The game then proceeds in rounds, and in the 1-th round,
(1) Adversary computes an update E [n] for the stream, which depends on all previous stream updates and all previous outputs from StreamAlg.
(2) StreamAlg uses 4e to update its data structures Di, acquires a fresh batch Rg of random bits, and outputs response A, to the query Q.
Adversary observes and records the response Ar-
The goal of Adversary to induce StreamAlg to make an incorrect response A, to the query Q at some time t E [m] throughout the stream.
Related Works. Adversarial robustness of streaming algorithms has been an important topic of recent research. On the positive note, Y20] gave a robust framework for estimating the Lp norm of points in stream in the insertion-only model, where previous stream updates cannot later be deleted. Their work thus shows that delctions are integral to the attack of [HW13]. Subsequently, [HKM+20] introduced
algorithmic design for robust T.p 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 or the accuracy parameter s 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.
[B Y20] 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 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 adversarially robust. This notion is further formalized by [ABD+2] 21], who showed that the classes that are online learnable requires essentially sample-complexity proportional to the Littlestone's '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 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.
1.1 Our Contributions
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
2

---

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 wi,,..., u4n- Our algorithm A will maintain data structure A, time t which updates as the stream progresses, A will use a function g(A,, we) to determine the probability of sampling item u, update A, Ac+1. The function 9 measures the 'importance" of the element ot to the overall problem that we wish to solve. For example, if our application is k-means clustering and un is 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 u4 given by ( 4t) is adversarial, since the adversary designs u, and previous streaming elements, the coin toss performed by our algorithm A to keep item Un is independent of any events that have occurred so far, including the adversary's '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 the situation where a "fixed" data structure or sketch is specified upfront. In this case, we would not be adaptive to which inputs uy the adversary designs to be "important" for our problem which would lead us 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.
Meta-approach
Applications
Coreset construction, support vector machine, Gaussian mixture models, k-means clustering, k-median clustering, projective clustering. principal component analysis, M-estimators, Bayesian logistic regression, generative adversarial networks (GANs), k-line center, j-subspace approximation, Bregman clustering
Merge and reduce (Theorem 1.1)
Linear regression, generalized regression, spectral
Row sampling (Theorem 1.2)
approximation, low-rank approximation, projection-cost preservation, -subspae embedding Graph sparsification
Edge sampling (Theorem I.3)
Fig. I: Summary of our robust sampling frameworks and corresponding applications
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) [LKI7].
Theorem 1.1 (Merge and reduce is adversarially robust) Given offline s-coreset construction, the merge and reduce framework gives an adversarially robust streaming construction for an E-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 E [n]. the 1-th prefix of the stream induces a matrix A, E RR with rows aj...., ag. We denote this matrix as A, a1 o... o a, and define x to be an upper bound on the largest condition number! of the matrices AI,...,An.
Theorem 1.2 (Row sampling is adversarially robust) There exists a row sampling based frame- work adversarially robust streaming algorithms that at each time t E [n]]
the ratio of the largest and smallest nonzero singular values
3

---

(1) Outputs a matrix M, such that (1 - []= = M. 3 (1+ As, while sam- pling O dxx log log 6) rows (spectral approximation/sussacee embedding/linear regres- sion/generalized regression).
2"
(2) Outputs a matrix M, such that for all rank k orthogonal projection matrices E Raxd
(1 (1-e) AIPl & M. M,PI s (1++) ||A - A.Pl
while sampling O (dr log n log k) rows petprpcoonnttosppeeeeertttttoott approxi- mation).
(3) Outputs matrix M, such that (1 a) || S ||,x|] S (1 + [)+ while
sampling O d log" nlog x)) rows (L1 subspace embedding).
Finally, we show that our analysis also applics to algorithms for graph sparsification for in which edges are sampled according their "importance". Define к the ratio of the largest and the smallest cut sizes in G (see Section and Supplementary Section C for exact details).
Theorem 1.3 Given a weighted graph G = EV with [V] = n whose edges ci,..., em arrive sequentially in stream, there exists adversarially robust streaming algorithm that outputs a + cut sparsifier with O
x xonnoo n
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 data structure f such that after the (i 1)-th input Ii, we can update f by computing linear function of z,. Typically, these methods employ a random matrix. For example, if the input consists of vectors, sketching methods will use 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 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 the kernel of the matrix as inputs, the adversary can render the whole streaming algorithm useless.
One the other hand, we employ different family of streaming algorithms that are based sampling the input rather than sketching it. Surprisingly, this simple change allows one to automatically get many adversarially robust algorithms either "for free" without new algorithmic overheads. For more information, see Section 1.1. We emphasize that while our techniques are not theoretically sophisticated, 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-off's between the two paradigms; for non adversarial inputs sketching often gives similar or better performance guarantees for many tasks [BYKS01].
2 Merge and Reduce
We show that the general merge and reduce paradigm is adversarially robust. Merge and reduce is widely used for the construction of coreset, which provides dimensionality reduction the size of an underlying dataset, so that algorithms for downstream applications can run more efficiently:
Definition 2.1 (s coreset) Let P X be set of elements from universe X, z 2 0, E E (0, 1), and (P, dist, Q) be a query space. Then a subset C equipped with a function w P - R called an e-coreset with respect to the query space (P, dist, Q)
(1 (1-E) Σ dist(p, Q)² < Σ ((p) dist (B, Q)² (1++)) DEP
Σ dist Q)²
DEC
DEP
The study of efficient offline coreset constructions for variety of geometric and algebraic problems forms long line of active research. For example, offline coreset constructions are known for linear

---

regression, low-rank approximation, Lssubspace embedding, k-means clustering, k-median cluster- ing, k-center, support vector machine, Gaussian mixture models, M -sttimattoss, 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 stream s of length n = 2 for some
{Ca,)):
C3.1
{C2,}]:
C2.1
2,2
{Ci,]:
C1,1
1
C1.
C1
Stream:
Fig. 2: Merge and reduce framework. Each C1. is O log n)) of the corresponding partition of the substream and each Ci is an e-coreset of C;-1,25-1 and C3- for i > 1. integer without loss of generality (otherwise
can use standard padding argument to increase the length of the stream). Define Cu., Pj for all j E [n]. Consider & levels, where each level i [k] consists of & coresets Cs....... Cin/2i and each coreset Ct,J an 2% -coreset of C;-1.2y-1 2 and Ct-12 Note that this approach can be implemented efficiently in the streaming model, since each C.,, can be built immediately once 1,21,2j-1 and 1;-,,2 are constructed, and after Ct,, is constructed, then both C,-1,2j-3 and C;-1,2 can be discarded. For an illustration of the merge and reduce framework, see Figure 2, though we defer all formal proofs to the supplementary material. Using the coresets of [BDM* 20), Theorem 1.1 gives the following applications:
Theorem 2.2 There exists a merge-and-reduce row sampling based framework for adversarially robust streaming algorithms that at each time E [n]]
(1) Outputs matrix M, such that (1 e)AT 3 M. (1+ A,, while sam- pling O sion/generalized regression).
( txr log" nlog x) rows (spectral appreximaation/sxsspaac embedding/linear regres-
(2) Outputs a matrix M, such that for all rank k orthogonal projection matrices P E gdxd
(1 - =) ||A, A,PlI I ||M, - M,P < (1+ A
=1=
while sampling O ( log" n log" rs) rows (projection-cost preservation/loowraat approxi- mation).
(3) Outputs a matrix Mf such that (1 - <) |AxlI & ||, S (1 + +1+ +|Axll),,,,, while sampling O 2 log" n logg) rows (L1 subspace embedding).
Using coresets of [HV20], then Theorem 1.1 also gives applications for (k, cllusterii such as k-median for 1 and k-means for z = 2. Moreover, [LK noted that constructions of [FL.1 1] give coresets for Bregman clustering, which handles j-similar Bregman divergences such as the Itakura-Saito distance, KL-divergence, Mahalanobis distance, etc.
Theorem 2.3 There exists a merge-and-ene and-reduce importance sampling based framework for adversari- ally robust streaming algorithms that at each time l.:
(1) Outputs a set of centers that gives a (1 + E) apprroxiimtto to the optimal (k,z)- clustering, k-means clustering (z = 2), and k-median clustering (z = 1), while storing
o 2242 k 2log22+2, n log k log & &lognn points.
(2) Outputs set of centers that gives (1 appproxximntioon to the optimal k-Bregman clustering, while storing O (1z dk log" n) points.
Using the sensitivity bounds of [VX12a, VX12b] and the coreset constructions of [BFL.16), then Theorem 1.1 also gives applications for the following shape fitting problems:
5

---

Theorem 2.4
There exists a merge and- reduce importance sampling based framework for adversari- ally robust streaming algorithms that at each time
(1) Outputs a set of lines that gives (1 + E) approxxiiatio to the optimal k-lines clustering, while storing O (2 f(d, k))))d log" n) points of TR. for a fixed function fdd k).
(2) Outputs subspace that gives (1 + apprrxxiiattnn the optimal dimension j subspace approximation, while storing O ( g(d, j)koddd)) log' n) points of R. for fixed function g(d, j).
(3) Outputs set of subspaces that gives (1 + -appproxxmmiitoonn to the optimal (j. ---pooeective clustering, while storing O ( h(d, j. k) log" n(log n) ())Md..)))) points of IR's, for fixed function h(d.j. k), for 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+ TBFR20]; significant number of additional applications of Theorem 1.1 using coreset constructions can be seen from recent surveys on coresets, e.g., see [LK17, Fe120]. 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] 16] 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].
3 Adversarial Robustness of Subspace Embedding and Applications
We use [n] to represent the set {L..... n for an integer n > O. We typically use bold font to denote vectors and matrices. For a matrix A, we use A to denote the Moore-Penross inverse of A. We first formally define the goals of our algorithms:
Problem 3.1 (Spectral Approximation) Given matrix A E Raad and approximation param-
eter E > 0, the goal is to output a matrix M R.mxd with m < n such that (1 - E) ||A ||g S
||Mx|]2 S (1 + =) ||xx|] for all x E Rd or equivalently, (1 - =) T A 1 M M (1+ A.
We note that linear regression is well-known specific application of spectral approximation.
Problem 3.2 (Projection-Con Cost Preservation) Given a matrix A E Raxd, a rank parameter >> and an approximation parameter >> O, the goal is to find a matrix M E RRxx with m & such that for all rank orthogonal projection matrices P E Rdxd
(1 -) IIA - API < |M- MP (A-
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 A.
Problem 3.3 (Low-Rank Approximation) Given matrix A Raxd, rank parameter l >
O, and an approximation parameter & > 0, find a rank i matrix M E TRaxd such that (1
E) A A < ||A M < (1 + A Awell where (1)) for a matrix A denotes the best rank k approximation A.
Problem 3.4 (Ly-Subspace Embedding) Given a matrix A E [Raxd and an approximation param- eter E 0, the goal to output a matrix M Rixxd with m < n such that (1 E) ||A]]] S ||M]]] S (1 + =) ||Ax||, for all x Rd.
We consider the general class of row sampling algorithms, e.g. [CMP16, BDM- Here we main- tain a T.p subspace embedding of the underlying matrix by approximating the online I.p sensitivities of each row as a measure of importance to perform sampling. For more details, see Algorithm
Definition 3.5 (Online Lp Sensitivities) For a matrix A ai o ... an Rxd the online sensitivity of row for each i E [n] is the quantity max
x),x) where A = aj o a A

---

Algorithm 1 Row sampling based algorithms, e.g., [CMP16, BDM + 20]
Input: A stream of rows ..,...,, an E Rd, parameter 0, and an accuracy parameter >> 0 Output: +) hp subspace embedding.
I: M +-0
Cd log n with sufficiently large parameter C' 2: a - zf
3: for each row a, E [n] do
4:
a, E (M) then
5:
+ 2 maxxex" xEspan(()
xa MX p x)
DSee Remark 3.6
6: else
7:
1+11
8:
Pj + min(1. aT,)
9:
With probability pt. M t Mo
DOnline sensitivity sampling
Pi
return M
We remark on standard computation or approximation of the online Lp sensitivities, c.g..
see [CEM* 15, CMP16, CMM17, BDM 20].
Remark 3.6 We note that for = 1. constant fraction approximation to any online Lp sensitivity Tę such that T4 > poly(n) can computed in polynomial time using (offline) linear programming while for p 2, T; is equivalent to the online leverage score of ag which has the closed form expression a (A A,) a, which be approximated by a (M M) -), conditioned on M being good approximation to A;-1 when a is in the span of M. Otherwise, takes value 1 when is not in the span of M.
Lemma 3.7 (Adversarially Robust Lp Subspace Embedding and Linear Regression) Given
> O, E {1, and a matrix A E Ruxd whose rows at..... arrive sequentially in a stream with condition number most k, there exists an adversarially robust streaming algorithm that outputs
(1 E) spectral approximation with high probability. The algorithm samples O dd""" log log
rows for p 2 and O ( log² n log ror p with high probability, where X is ratio between upper and lower bounds ||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 >> O, rank parameter k >> O, and a matrix A E IRn whose rows a &n arrive sequentially in stream with condition number at most K, there exists an adversarially robust streaming algorithm that outputs (1 + E) low-rank approximation with high probability. The algorithm samples kdw
log n log K. rows with high probability.
4
Graph Sparsification
In this section, we highlight how the sampling paradigm gives rise to an adversarially robust streaming algorithm for graph sparsification. First, motivate the problem of graph sparsification. Massive graphs arise in many thcoretical 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 edges to be comparable the number of vertices.
The most common notion of graph sparsification is that preserving the value of all cuts in the graph by keeping small weighted set of edges of the original graph. More specifically, suppose
7

---

and for simplicity assume all the edges have weight 1. A cut of the graph is partition V (C, C)) and the value of a cut, (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 sparsifier preserves the value of every cut in and has a few number of weighted edges. For precise formulation, see Problem 4.1.
graph is
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 [EKKI.20], distributed optimization [WWL218), and even learning graph sparsification using deep learning methods [7ZC+ 20]. The formal problem definition of graph sparsification is as follows.
Problem 4.1 (Graph Sparsification) Given graph weighted G = (V, E) with [V] and an approximation parameter 0, compute a weighted subgraph H of G on the same set of vertices such that
n, = m,
(1) every cut in H. has value between 1 - E and 1 + times its value in G: (1- (alc(()) S Val S (1++) Vala all cuts C where (ala Val (C) denotes the cost of the cut in the graphs G and H respectively and for the latter quantity, the edges are weighted,
for
(2) the number of edges in H is O
n log
Ignoring dependence on E, there are previous results that already get sparsifiers H with (n log edges [BK96, SS08J. 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 in the supplementary section), which uses sampling procedure to sample edges in a stream, is adversarially robust, albeit with 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 subgraph H such that H satisfies the conditions of Problem 4.1 with probability
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 martingale argument; the full details are given in Supplementary Section C. As in Section we let Kj and K2 to be deterministic lower/upper bounds on the size of any cut in G and define R2/K1-
Theorem 1.3 Given a weighted graph G = (V,E) with | n whose edges C1,.. ......, Cm arrive sequentially in stream, there exists an adversarially robust streaming algorithm that outputs a + x² Fnlog ) edges with probability 1/ poly
sparsifier with O
5 Experiments
To illustrate the robustness of settings for clustering and linear regression. With respect to our adversarial setting, we show that the performance of a perge-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.
based streaming algorithms we devise adversarial
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 two dimensional standard normal distribution and points the last batch similarly sampled but around a distant center (see the data points rcalization in both panels of Figure 3). We then feed the point sequence
8

---

to StreaminggKMens, the streaming k- k-mmans 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 's distance from the origin, implying that the per-sample loss performance 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].
10-
Data points
-
10-
Data prints
Spark Streaming
StreakM Coresets
Fig. 3: Resulting cluster centers (x) on our adversarial datapoints setting for the popular Spark implementation (left) and StreamKM++ (right).
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 - 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 origin'. We compare the performance of LinearRegress inn in from the popular streaming machine learning library River [MHM+ 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 I picks up the drastic change and adapts immediately to 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 longer the case in the following last setting.
Sampling vs. sketching. Finally, we compare the performance of the leverage sampling Algo- rithm 1 sketching. In this setting, for a random unit sketching matrix (that is, each of its elements is sampled from 1- with equal probability), we create an adversarial data stream A such that its columns are the null space of S. As result, the linear regression as applied to the sketched data S A as 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 sampling' is almost double compared to the data reduction factor achieved by sketching.
Acknowledgments
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.
2 For MSE loss, this occurs for at least the square root of the number of batches.
The original stream A contained 2000 samples, each of dimension 10.

---

Optimal regression
River streamed
Data points
0.6
Leveraged sample
MSE
-1
0.2
-2
40
100
120
2.0
-1.0
0.0
1.0
2.0
Iteration
Leveraged sample
800000
River streamed
400
Streamnd regression
Leveraged sample
Data points
600000
200
400000
200000
60 Iteration
100
120
10
20
30
40
50
60
Fig. 4: Streaming linear regression experiment (from left to right): points constellation without last batch, loss trajectory up to (not including) last batch, resulting regression lines upon training with last batch, and loss trajectory including the last batch.
(50 samples Leveraged Sampling (29 samples out of 2000)
50
40
1og telativ
10
28
0
100
125
1.50
175
Iberation
Fig. 5: Comparing the performance trajectory of leveraged sampling Algorithm 1 to sketching, for an adversarial data stream tailored to a sketching matrix. Sketching performance deteriorates catastrophically upon the last batch, while leveraged sampling remains robust.
References
[ABD+21] Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. CoRR, abs/2101.0905. 2021. 2
[AEIK18] Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML, pages 284 283.293, 2018.
[AG09] Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In Automata, Languages and Programmingg pages 328-338, 2009. 8, 20, 21
[AMR+12] Marcel R. Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Chris- tiane Lammersen, and Christian Sohler. Streamkm++: A clustering algorithm for data streams. ACM J. Exp. Algorithmics, 17, May 2012.
[AMYZ19] Dmitrii Avdiukhin, Slobodan Mitrovie, Grigory Yaroslavtsev, and Samson Zhou. Adver- sarially robust submodular maximization under knapsack constraints. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 148-156, 2019. 2
10

---

[BDM 20] 20] Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 517-528, 2020. 5, 6, 7, 15, 17, 18, 19
[BFL16] Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. CoRR, fbss/161..00889 2016. 5, 15
[BJWY20) Omri Ben-Flliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A frame- work for adversarially robust streaming algorithmss In Proceedings of the 39th ACM 63-80, 2020. 2
Symposium on Principles of Database Systems, PODS, pages
[BK96] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Ō(n²) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 47-55, 1996. 8, 20, 21
[9L Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus. Data-dependent coresets for compressing neural networks with applications general- ization bounds. In 7th International Conference on Learning Representations, ICLR, 2019. 15
[BLUZI9] Vladimir Braverman, Harry Lang. Enayat Ullah, and Samson Zhou Improved algo- rithms for time decay streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 27:1-27:17, 2019. 6, 15
[BMSC17] Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. Robust submodular maximization: A non-uniform partitioning approach. In Proceedings of the 34th International Conference on Machine Learning, ICML, volume 70, pages 508-516, 2017. 2
[BY20] Omri Beezzeiezer and Eylon Yogev. The adversarial robustness of sampling. In Proceedings of the 39th ACM SIGMOD-SIGACT-SSGA Symposium on Principles of Database Systems, PODS, pages 69-62,222 2020. 2
[BYKS01] Ziv Bar- Yossef, Ravi Kumar, and D. Sivakumar. Sampling algorithms: Lower bounds and applications. Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, page 266-275, 2001.
[CEM* 15] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 163 172, 2015. 7
[CMM17] Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling, In Proceedings of the Twenty-Eight Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1777, 2017. 7, 19
[CMP16] Michael B. Cohen, Cameron Musco, and Jakub W. Pachocki. Online row sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pages 7:1-7:18, 2016. 6, 18
[CW17] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy, SP, pages 39-57. IEEE Computer Society, 2017.
[DGIM02] Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM J. Compur.,
2002. 6
[EKKL20] Marek Eliás, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 560-578, 2020. 8
11

---

[Fe120] Dan Feldman. Introduction to core-sets: an updated survey. CoRR. 1.0984,, 2020. 6, 15
[FKW19] Dan Feldman, Zahi Kfir, and Xuan Wu. Coresets for gaussian mixture models of any shape. CoRR,
2019. 6
[FL11] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing.
STOC, pages 569-578. ACM, 2011. 5,
[FMSW10] Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. Core- sets and sketches for high dimensional subspace approximation problems. In Proceed- ings of the Twenty- First Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 630-649, 2010. 15
[Fre75] David A. Freedman. On tail probabilities for martingales. the Annals of Probability, 3(1):100-118; 1975. 16
[GDC12] Amit Goyal, Hal Daumé, and Graham Cormode. Sketch algorithms for estimating point queries in nip. In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, page 1093-1 103, 2012. 2
[GKKI0] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. Graph sparsification via refine- ment sampling. CoRR, abs/1000.49) 2010. 20
[GLPW16] Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions: Simple and deterministic matrix sketching. SIAM J. Comput., 45(5):1762 1792, 2016.
[9RB+19] Heitor Murilo Gomes, Jesse Read, Albert Bifet, Jean Paul Barddal, and João Gama. Machine learning for streaming data: State of the art, challenges, and opportunities. SIGKDD Explor. Newsl., 21 22, 2019.
[GSSI5] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2015.
[HCB16] Jonathan H. Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. In Advances Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems, pages 4080-4088. 2016.
[HKM+20] 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, 2020. 2
[HV20] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1416-1429, 2020. 5, 15
[HW13] Moritz Hardt and David P. Woodruff. How robust are linear sketches adaptive inputs? In Symposium on Theory of Computing Conference, STOC, pages 121-130, 2013. 2,
[HZZ21] Bo-Jian Hou, Lijun Zhang, and Zhi-Hua Zhou. Learning with feature evolvable streams. IEEE Trans. Knowl. Data Eng., 336)):202-2215,, 2021. 2
[KMNS21] Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming. CoRR,
2021. 2
[KNST19] Michael Kapralov, Navid Nouri, Aaron Sidford, and Jakab Tardos. Dynamic streaming spectral sparsification in nearly linear time and space. CoRR, abs/1903.1 12150, 2019.
20
12

---

[LK17] Olivier Bachem Mario Lucic and Andreas Krause, Practical coreset constructions for machine learning. CoRR, (ob//7003.,676, 2017. 5, 6, 15
[LMV* 16] Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braver- man. One sketch rule them all: Rethinking network flow monitoring with univmon. In Proceedings of the 2016 ACM SIGCOMM Conference, page 101-114, 2016. 2
[Mac20] Giuliano Oliveira De Macedo. Github, 2020.
[MBN 17] Slobodan Mitrovic, Iijaa Bogunovic, Ashkan Norouzi- Fard, Jakub Tarnawski, and Volkan Cevher. Streaming robust submodular maximization: partitioned thresh- olding approach. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pages 4557-4566, 2017. 2
[MG82] Jayadev Misra and David Gries. Finding repeated elements. Sci. Comput. Program., 2(2):143-15,, 1982. 6
[MHM 20] Jacob Montiel, Max Halford, Saulo Martiello Mastelini, Geoffrey Bolmier, Raphael Sourty, Robin Vaysse, Adil Zouitine, Heitor Murilo Gomes, Jesse Read, Talel Ab- dessalem, and Albert Bifet. River: machine learning for streaming data in python, 2020.
[MSS 18] Aleksander Madry, Alcksandar 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.
[MOB* f 20] Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, and Dan Feld- man. Data-independent neural pruning via coresets. In 8th International Conference on Learning Representations, ICLR, 2020. 15
[MSSW18] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff. On coresets for logistic regression. In Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS, pages 6562-6571, 2018. 15
[RA15] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. 7
[SPR11] Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. In Proceedings of the 2011 ACM SIGMOD International Conference Management of Data, page 721-732, 2011.
[SS08] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, page 563-568, 2008.
[SW18] Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 802-813, 2018. 15
[S] Samarth Sinha, Han Zhang, Anirudh Goyal, Yoshua Bengio, Hugo Larochelle, and Au- gustus Odena. Small-gan: Speeding up GAN training using core-sets. In Proceedings of the 37th International Conference on Machine Learning, ICML, pages 9005-9015, 2020. 6
[SZP+21] Benwei Shi, Zhuoyue Zhao, Yanqing Peng, Feifei Li, and Jeff M. Phillips. At-the-time and back-in-time persistent sketches. In SIGMOD '21: International Conference on Management of Data, pages 1623-1636, 2021.
[BBRR20] Murad Tukan, Cenk Baykal, Dan Feldman, and Daniela Rus. On coresets for sup- port vector machines. In Theory and Applications of Models of Computation, 16th International Conference, TAMC Proceedings, pages 287-299, 2020. 6
13

---

[TSE*19 19] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Alek- sander Madry. Robustness may be odds with accuracy. In 7th International Confer- ence on Learning Representations, ICIR, 2019. 1
[VX12a] Kasturi R. Varadarajan and Xin Xiao. A near-linear algorithm for projective clustering integer points. In Proceedings of the Twenty-Thine Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1329-1342, 2012. 5
[VX12b] Kasturi R. Varadarajan and Xin Xiao. On the sensitivity of shape fitting problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pages 486-497, 2012. 5
[WWLZ18] Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for distributed optimization. In Advances in Neural Information Processing Systems, 2018.
communication-efiin
[WYWD10] Xindong Wu, Kui Yu, Hao Wang, and Wei Ding. Online streaming feature selection. In Proceedings the 27th International Conference Machine Learning ICML, pages 1159-1166, 2010.
[WZ20] David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. CoRR, abs/201 1. 1.07471, 2020. 2
1ZX++16l Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das. Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. Apache spark: unified engine for big data processing. Commun. ACM, 59(1 1):56-65, 2016. 2
[ZXW 16b] Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das. Michael Armbrust, Ankur Dave, Xiangrui Meng. Josh Rosen, Shivaram Venkataraman, Michael Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. Apache spark: A unified engine for big data processing. Commun. ACM, 59 1):56-655,,, October 2016.
[ZZC+20] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In Proceedings of the 37th International Conference on Machine Learning, pages 1 11458 11 11468, 2020. 8
14


Reviews:
[{"review_id": "i_zNTksYpE9", "reviewer": "Reviewer_m5zL", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Pros:\n-Adversarial robustness streaming algorithms are important in the literature of streaming algorithm. Based on the observations of this paper, many previous streaming algorithms automatically are adversarially robust. These problems include many fundamental ML, numerical linear algebra and graph problems including clustering, Gaussian mixture models, SVM, k-clustering, regression, GANs, low rank approximation, spectral approximation, graph scarification, and etc.\n-The paper is well-written in general.\n-The experiments support their results.\n\nCons:\n-My major concern is the technical strength of the paper. Although the paper obtains many important results, all of them directly follows from previous streaming algorithms. Although authors show that Merge-and-Reduce framework and row sampling framework are adversarially robust in general. The techniques for analysis are not hard. Basically the structures of these frameworks make the analysis works in some sort of a straightforward way.\n\nOverall, since results are important but the technical strength is limited, I think the paper is marginally above the bar.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not find any potential negative societal impact of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "diQt7o_l5IJ", "reviewer": "Reviewer_AQVy", "summary": "This paper show how streaming algorithms based on importance sampling can achieve adversarial robustness in a specific but quite general adversarial model, where the adversary observes all the intermediate outputs of the algorithm and may even learn past random bits, but has no access to the \"new\" random bits used at each time. Any method that uses importance sampling (in the way described in the paper) is adversarial-robust, and many existing streaming approaches enjoy this property e.g., , those using coresets and the merge-and-reduce approach, and methods for regression using row sampling and methods for graph sparsification using edge sampling.\n", "questions": "", "limitations": "", "rating": 7, "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": "## Comments after response\n\nI thank the Authors for their response. I read it carefully, as I did the comments from other Reviewers and the responses to them. I believe should be accepted, and I increased my original score to reflect this new opinion. The new figures look good and should be included in the final version of the paper in place of the original ones.\n\n## Original Review\n\nThe results in this paper seem quite interesting. After [HV20], it is nice to see more work remarking on the beneficial properties of importance sampling, in this case versus \"non-adaptive\" sketching.\n\nOne downside of the paper is that the main text contains no proofs at all, not even sketches, roadmaps, intuitions, informal ideas, or anything that may guide the reader, who may not want to delve into the whole supplementary materials, into understanding *why* the proposed results are true. Indeed the paper, due to space restrictions, reads almost as just a list of results, which is a pity. I wonder whether the Authors could avoid presenting some results (deferring those to the supplementary materials), and present more discussion and possibly some proof sketches.\n\nThe experimental evaluation shows the large difference between adversarially-robust and \"non-robust\" methods. The settings and experiments feel a bit artificial, but they do drive home the point.\n\nThe figures and their discussion make reference to colors and other properties that are lost when the paper is printed in grayscale, and also to colorblind people. Additionally, some figures (e.g., Fig. 4) are too small to be readable when the paper is printed. Using different line styles, bigger markers / thicker lines, and other visual clues would be beneficial. \n\nThis Reviewer did not check all the details of all the proofs, but the general \"flow\" of the proofs seems correct. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion of *algorithmic* limitations of the work, although the paper would benefit from such a discussion.\n\nThis Reviewer does not see any negative societal impact that is *only specific* to this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "MIuO_MIcKY", "reviewer": "Reviewer_K1tg", "summary": "Many streaming algorithms developed during the last decades are randomized and have an expected solution guarantee (approximation guarantee).\n\nHowever, 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.\n\nThe 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. \n\nThe main result of the paper is this observation together with tons of applications of prior algorithms that the authors list. ", "questions": "", "limitations": "", "rating": 7, "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": "The paper is original in that it studies a stronger adversary, makes the insight that certain kind of sampling-based algorithms are robust against this stronger type of adversaries. \n\nThen the paper is less original in the sense that it feels like a long list of applications where the authors basically has verified that the known algorithms \"pass the test.\" (Personally, I'd prefer if they would have focused on one or few applications in the main body of the paper and showed some nice insights there. But if I understand the authors correctly the main result is this important insight (point of view) and then all the results basically follows from previous work.) \n\nOtherwise, I would say that the paper reads well and is clear (although they don't define all the problems that they list). I also think it is a good paper in terms of significance in the sense that it is good to know that all these algorithms are in fact robust. So I think the paper is definitely valuable to the research community.\n\nA more detailed comment to the authors: How important is it for your algorithms to know the length of the stream? It seems pretty crucial when you take a union bound over error probabilities but maybe I am missing something? If not, it would be good with a discussion if it is really necessary to know the length of the stream...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The experiments is not really \"complete\" but the main focus of the paper is theory.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission provides a nice overall message that many streaming algorithms are already adversarially robust. This was deemed an important message. There were some concerns with the presentation, as discussed in the reviews and the follow-ups, which the authors are encouraged to address and correct. 
Decision: Accept (Poster)