Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: 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. 
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. 

Then 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.) 

Otherwise, 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.

A 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...
limitations_and_societal_impact: The experiments is not really "complete" but the main focus of the paper is theory.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Pros:
-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.
-The paper is well-written in general.
-The experiments support their results.

Cons:
-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.

Overall, since results are important but the technical strength is limited, I think the paper is marginally above the bar.
limitations_and_societal_impact: I did not find any potential negative societal impact of the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

main_review: ## Comments after response

I 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.

## Original Review

The 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.

One 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.

The 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.

The 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. 

This Reviewer did not check all the details of all the proofs, but the general "flow" of the proofs seems correct. 
limitations_and_societal_impact: There is no discussion of *algorithmic* limitations of the work, although the paper would benefit from such a discussion.

This Reviewer does not see any negative societal impact that is *only specific* to this work.
review_title: null

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)