The data stream model is a fundamental model for processing massive data sets with limited memory and fast processing time. Recently Hsu et al. (2019) incorporated machine learning techniques into the data stream model in order to learn relevant patterns in the input data. Such techniques led to the training of an oracle to predict item frequencies in the streaming model. In this paper we explore the full power of such an oracle, showing that it can be applied to a wide array of problems in data streams, sometimes resulting in the first optimal bounds for such problems, and sometimes bypassing known lower bounds without such an oracle. We apply the oracle to counting distinct elements on the difference of streams, estimating frequency moments, estimating cascaded aggregates, and estimating moments of geometric data streams. For the distinct elements problem, we bypass the known lower bound and obtain a new space-optimal algorithm. For estimating the p-th frequency moment for 0 < p < 2 we obtain the first algorithms with optimal space and update time. For estimating the p-th frequency moment for p > 2 we obtain a quadratic savings in memory, bypassing known lower bounds without an oracle. We empirically validate our results, demonstrating also our improvements in practice.
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...)