Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposed a neural model to estimate item frequencies of data streams, which is using the thought of meta-learning. And they called the model meta-sketch. It’s said that they are the first to try to solve this problem with neural data structure and gain good performances on real datasets.

strengths_and_weaknesses: Strengths:
The paper is well structured and the explanation is easy to understand.

Weakness:
1.	In my view, training data and evaluation data should be isolated completely. That is, there should be a certain mount streams and items haven’t happened in the meta-tasks. Therefore, sampling training set and evaluating set from the same pool is not sufficient enough to prove the generalization.
2.	The references and baselines are out of date, more researches of recent years should be covered. And it is easy to get a lot of results if you search items like “Item Frequencies of Data Streams”.
3.	One advantage of meta-learning is that it could find better params of network faster and more efficiently. So I believe the efficiency is also a good sight of this model and it should be contained in the experiment.

questions: Apart from the above, I have question about the update rule for M, M=M+z_i a_i. Is this adding process derived by some objective? Could the authors give this rule out directly. Please explain that it is representable for all items and streams.
limitations: None
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces a sketching method where neural networks are used for specific components of the sketching. In particular, a neural network is used to encode stream/query items into an internal representation used to update/retrieve frequency values of items, which is followed by another neural network that decodes this information into actual frequency values. A meta-training procedure is also introduced, whose goal is to train the neural networks to handle the task at hand on a meta level, that is, not tied to a specific dataset. The method and its multiple aspects are experimentally evaluated, showing how its internal mechanisms behave under differing circumstances and improved performance over baseline methods built on Count sketch and Count-min sketch.

strengths_and_weaknesses: Overall, I find this to be a strong submission. The paper is properly motivated, well-organized, and clearly written. The introduced methodology is quite original for sketching, leveraging neural networks and increasing the robustness to changes in distribution significantly, compared to existing approaches, without additional training.

I was also pleased with the experimental evaluation, as it not only compares accuracy in frequency estimates under varied conditions, but also evaluates the different components that comprise the approach. In my view, this helps justifying why certain parts are a positive contributor to the overall performance of the method, shedding also some light on when they might fail. One weakness, however pointed out by the authors, is that the proposed method needs to be extended to other sketching tasks supported by traditional sketches.

questions: There are two major points where I would appreciate an answer from the authors:
1. How is the method's robustness to the meta-training step? That is, how much variance is expected in the results under repeated experiments with different initial seeds?
2. Are there any theoretical results that can be leveraged from existing literature on sketches? It seems to me the proposed method is lacking on the theoretical side.

Minor points:
- l. 97: what is meant by "length"? Perhaps $l_r$ elements has less ambiguous meanings (cf. length vs. norm)
- Footnote 2 (p. 3): does that mean $a_i^\top \in \mathbb{R}^{d_2 \times d_1 \times 1}$? Please write explicitly the space where $a_i^\top$ comes from to avoid confusion
- l. 271: $\phi$ does not seem to be defined

limitations: I believe the authors have sufficiently addressed the limitations of their method by analyzing its multiple components and how they behave under different circumstances.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The work considers the problem of estimating item frequencies in data streams. Sketches are probabilistic data structures that solve this problem approximately; e.g., a classical count-min (CM) sketch increments counts resulting from several hash functions for each query (exactly like a Bloom filter, only with integer counts) and outputs the minimal value of these counts as the result; this is a biased estimator that can overestimate but not underestimate. Machine learning models can be used in sketches to exploit the properties of underlying data distributions. For example, it would be better to assign heavy hitters separate buckets in a CM-sketch to avoid collisions, and a machine learning model can be used to identify these heavy hitters when they appear.

The work presents Meta-Sketch, a neural data structure that emulates a sketch in a neural network. The Meta-Sketch is a neural network with an encoder that produces embeddings $z_i$ and refined embeddings $r_i$ of incoming items, a sparse addressing unit that converts $r_i$ into an address $a_i$ in the storage matrix (this is the neural version of hash functions), a compressed storage matrix $M$ that stores embedding vectors, and a decoder that produces the frequency from a reading from the storage matrix, embedding vector $z_i$, and the total number of stored items $N$. The network supports two kinds of operations: "Store" that additively writes $z_i$ to $M$ and "Query" that estimates the frequency via the decoder.

The entire network is both pretrained and fine-tuned (adapted) on a series of meta-tasks; each meta-task is a set of store and query operations; during pretraining, the meta-tasks are synthetic problems generated based on the Zipf distribution (the result is called a basic meta-sketch), and during adaption the network is fine-tuned on real data records (advanced meta-sketch). The idea here is to pretrain the architecture to operate as a sketch while preserving the ability to quickly adapt to a given data distribution.

The authors evaluate on two real datasets, a stream of search queries (several words each) and an IP trace where packets are identified with source/destination IP addresses. They report improved performance over classical sketches and also over previous attempts of adding ML to sketches: learned CM-sketch and learned C-sketch. The paper also presents an analysis section that studies how different units of the architecture perform.
strengths_and_weaknesses: Strengths:
* novel neural data structure with a clear use case
* analysis section supporting that the components operate as intended
* convincing experimental evaluation

Weaknesses (see also questions):
* lack of discussion of the architectural choices for the neural networks
* only two real datasets with no motivation for this choice and no discussion of their differences
questions: 1. There is an ablation study in the supplement but I think the paper would benefit from a discussion of neural network architecture choices. For example, are there gains to be achieved from more involved encoder/decoder architectures?

2. It appears that the authors simply picked the same real datasets that were used in previous work (references [15, 21]). Are there other use-cases and available datasets for evaluation? Are there differences in the data distributions between these two (it appears there should be: IP traces are generally more heavy-tailed) and does it make any difference to Meta-Sketch results?
limitations: Limitations of the work and possible extensions have been adequately discussed in the conclusion. The societal impact question is not applicable in this case.
review_title: null

Meta-review: metareview: The paper had mixed reviews in terms of scores but if we put the strengths and the weakness together the weakness appears stronger. 
Strengths: People liked the neural only method and good experimental results on two datasets.
Weakness:  Evaluations may not make sense in data stream settings, only two datasets, no theoretical motivation etc. Paper do not cite and compare recent literature on learned/adaptive learned sketches

The AC went through the paper and did find that there are certain major arguments that needs to be made before the paper is accepted.
1. The paper is about learned sketches that typically works in a bursty environment and with a lot of distribution changes all the time. No wonder all the learning augmented method still use sketches to provide worst case guarantees and control over the estimation errors. This is more or less required if at all any learning based method claims to replace sketches. As a result, the purely neural approach which treats this as a learning problem without any theoretical understanding requires more justification and case study of real scenarios.
2. The paper did not cite and compare with several recent learned/adaptive learned sketches in the literature (including recent papers in NeurIPS/ICML)
3. Looking at supplementary martial and meta-task generation, it seems that there is a very strong assumption that distribution of frequency does not change over intervals. For instance, one of the typical use case of frequency estimation is to recover frequency in any interval of time (See papers on sketches over time or adaptive sketches) and dyadic interval tricks to extend sketches to do that. A purely learning based approach is unlikely to achieve much there.


confidence: Certain
Decision: Reject