- Theoretical analyses are not particularly difficult, even if they do provide some insights. That is, the analyses are what I would expect any competent grad student to be able to come up with within the context of a homework assignment. I would consider the contributions there to be worthy of a posted note / arXiv article. - Section 4 is interesting, but does not provide any actionable advice to the practitioner, unlike Theorem 4. The conclusion I took was that the learned function f needs to achieve a compression rate of \zeta / m with a false positive rate F_p and false negative rate F_n. To know if my deep neural network (for example) can do that, I would have to actually train a fixed size network and then empirically measure its errors. But if I have to do that, the current theory on standard Bloom filters would provide me with an estimate of the equivalent Bloom filter that achieves the same error false positive as the learned Bloom filter. - To reiterate the above point, the analysis of Section 4 doesn't change how I would build, evaluate, and decide on whether to use learned Bloom filters. - The analytical approach of Section 4 gets confusing by starting with a fixed f with known \zeta, F_p, F_n, and then drawing the conclusion for an a priori fixed F_p, F_n (lines 231-233) before fixing the learned function f (lines 235-237). In practice, one typically fixes the function class (e.g. parameterized neural networks with the same architecture) *first* and measures F_p, F_n after. For such settings where \zeta and b are fixed a priori, one would be advised to minimize the learned Bloom filter's overall false positive (F_p + (1-F_p)\alpha^{b/F_n}) in the function class. An interesting analysis would then be to say whether this is feasible, and how it compares to the log loss function. Experiments can then conducted to back this up. This could constitute actionable advice to practitioners. Similarly for the sandwiched learned Bloom filter. - Claim (first para of Section 3.2) that "this methodology requires significant additional assumptions" seems too extreme to me. The only additional assumption is that the test set be drawn from the same distribution as the query set, which is natural for many machine learning settings where the train, validation, test sets are typically assumed to be from the same iid distribution. (If this assumption is in fact too hard to satisfy, then Theorem 4 isn't very useful too.) - Inequality on line 310 has wrong sign; compare inequality line 227 --- base \alpha < 1. - No empirical validation. I would have like to see some experiments where the bounds are validated.
- To reiterate the above point, the analysis of Section 4 doesn't change how I would build, evaluate, and decide on whether to use learned Bloom filters.