Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper presents algorithms for solving computational problems in a datastream model augmented with an oracle learned from data. The authors show that under this model, there exist algorithms that have significantly better time and space complexity than the current best known algorithms that do not use an oracle. The authors support their theoretical analysis with experiments in which the oracle is represented by a deep neural network and demonstrate improvement over classical algorithms that do not use machine learning.

Overall, this paper seems like a solid contribution to the literature. However, in its current state it does seem to be presented and motivated in a way that is appropriate for the audience of ML researchers at ICLR. It reads very much like a STOC theory paper, and a lot of the key ML details that would be relevant to audience at this conference seem to have been shoved under the rug in a way. Therefore my score for now is a weak reject, but I am very happy to increase the score if the authors address my presentations concerns.

Major comments:
* The oracle-augmented datasteam model needs to be contextualized better. I don't have a good sense of whether this is a reasonable theoretical model to explore and a lot of very basic questions remain unanswered for me. For example, how do I even know that the oracle in question exists? What are the particular assumptions under which it exists? What are the requirements on the training data, optimization ability, generalization error, etc. How do we know that we can create in practice ML learning models that are sufficiently accurate to serve as an oracle?

* The connections to deep learning seem arbitrary in some of the experiments. In one of the experiments, the authors train neural networks over a concatenation of IP address embeddings. Why do we need to use deep learning here? What is the benefit of using DL algorithms within the oracle-augmented datastream model? Is a simple algorithm enough? What algorithms should we ideally use in practice? What if you used simpler online learning algorithms with formal accuracy guarantees?

Minor comments:
* I thought there was a bit over-selling in intro. The authors say that they match the theoretical lower bounds for several problems. However, you are in a different computational model in which you now have access to an oracle. This needs to be made more explicitly, and language could be a bit toned down (e.g. in this model, we can obtain runtime that match or improve over lower bounds...)
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: Algorithms for Streaming data using a machine learning oracle is analyzed theoretically and empirically.

The idea is to build on some recent work (Hsu 19) which used RNNs to predict heavy hitters in streaming data. The purpose of this paper is to analyze whether such an oracle can help streaming algorithms to obtain improved bounds. I am not very familiar with this line of research so my comments will be more general in this case. The idea of improved bounds for streaming algorithms using machine learning oracle seems to be very appealing to me. The authors present novel theoretical results supporting this.

Experiments are performed on real as well as synthetic datasets using Hsu et al.’s method as an oracle.  Two real-world problems are selected, i.e., distinct packets in a network flow, Number of occurrences of each type of search query, and it is shown that using a oracle improves performance as compared to methods that do not use the oracle. Overall, I think the paper seems to be  an interesting direction which has both formal guarantees and experiments validating them in real-world datasets. One issue is perhaps, very little in terms of related work. I am not sure if this is the first work in this direction of proving bounds assuming an oracle or if there is some background work that the authors could provide to put this into context.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The paper talks about calculating various statistics over data streams. This is a very popular topic and is very relevant in big data analysis. A lot of work has been done in this general area and on the problems that are discussed in the paper. The new idea in the paper is better streaming algorithms under the assumption that there is a “heavy hitters” oracle that returns data items that have a lot of representation in the stream. The authors give provably better algorithms for the distinct elements problem, F_p moment problem (p > 2), and some more problems. These are important problems in streaming data analysis. They improve the space bounds and interestingly in some cases the bounds are better than what is possible without the oracle assumption. This also shows the power of such an oracle. There are experimental results to demonstrate the efficiency of the algorithms. At a high level the work seems good and interesting for a large audience interested in streaming data analysis. I have not gone over the proofs in detail (much of which is in the appendix).

- Even though oracle results are interesting, to make it practical it may make sense to talk about a more realistic, weaker oracle where some of the queries may be incorrect.
- It may even make sense to minimise the number of oracle calls which can be thought of as a resource and discuss the relationship between number of oracle calls and other resources such as space.

review_title: Official Blind Review #3

Meta-review: This paper theoretically analyzes the use of an oracle to predict various quantities in data stream models.  Building upon Hsu et al., (2019), the overriding goal is to examine the degree to which such an oracle is can provide memory and time improvements across broad streaming regimes.  In doing so, optimal bounds are derived in conjunction with a heavy hitter oracle.

Although the rebuttal and discussion period did not lead to a consensus in the scoring of this paper, two reviewers were highly supportive.  However, the primary criticism from the lone dissenting reviewer was based on the high-level presentation and motivation, and in particular, the impression that the paper read more like a STOC theory paper.  In this regard though, my belief is that the authors can easily tailor a revision to increase the accessibility to a wider ICLR audience.
Decision: Accept (Poster)