Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters

The actual improvement over the previous work seems very minimal, i.e. a tiny reduction in the space complexity on a very small portion of possible choices of p. However, the relation to heavy-hitters seems like an interesting and non-trivial insight used to achieve this improvement, and the algorithms for heavy hitters and residual estimation seem to me to be of independent interest.

Indeed, we do agree that in some settings, the quantitative improvement is not large. However, we emphasize that optimal bounds for adversarial insertion-deletion streams is a major open question and therefore, the main strength of our work is the conceptual message that the despite the lack of recent progress, previous results are not optimal. Thus we hope our work will inspire future research in this direction.

The authors do a great job at explaining the intuition behind their techniques and how they fit with existing works. However, I found the actual preliminaries to be extremely confusing. The paper would greatly benefit from a clearer introduction on the exact setting and definitions of the various variables. I found the introduction of https://arxiv.org/pdf/2003.14265 to be very helpful in clarifying my confusion.

Thanks for the suggestion. We will expand the preliminaries to reiterate the model described in Section 1 (lines 50-67) with the discussion specifically centered around the $L_p$ heavy-hitter problem and/or the $L_p$ norm estimation problem.

What is the variable b that is referred to in Algorithm 3 (in the parameters for LZeroEst and ResidualEst)? Perhaps I am missing something but I don't see where it is defined.

Similar to Algorithm 1, $b$ is the number of queries made to the oblivious algorithms. Since the stream has length $m$ and the stream is split into blocks of length $\ell$, then there are at most $\frac{m}{\ell}$ queries made to each of the algorithms, as in Algorithm 1. We will explicitly clarify the setting of $b=\frac{m}{\ell}$ in Algorithm 3.

I was a bit confused on the purpose of the empirical evaluations. It seems that you demonstrate that empirically in one real-world instance, the flip number of the residual vector can be significanly smaller than the flip number of the entire datastream. However, if I am understanding correctly, your algorithmic guarantees depend on the worst-case flip-number of the residual vector, and are not adaptive to the actual flip number. How should I interpret these empirical results with respect to the performance of your proposed algorithm?

Yes, that's a fair point. However, we remark that the algorithmic guarantees of the previous results also depend on the worst-case flip-number of the entire vector, so in some sense we are still comparing apples to apples by comparing the empirical flip-number of the residual vector to the empirical flip-number of the entire vector. In particular, the algorithm must still commit to some budget for the flip-number before the algorithm is initialized and our empirical results show that the same budget can handle significantly more updates for our algorithm.

The moments/norms for which the paper improves the space requirements are not the most important ones, which are I think are $p=0$ and $p=2$.

In general, a common goal is to find the heavy-hitters above a desired threshold that may be arbitrary. In this case, we want $|x_i|>\tau$ for some threshold $\tau$. We can then choose the values of $\varepsilon$ and $p$ accordingly, so that $\tau=\varepsilon\cdot\|x\|_p$ so that the $L_p$-heavy hitters correspond to the items whose frequency are above the threshold.

"Unusual" values of moments can be used for computing entropy (see Harvey, Nelson, Onak 2008). Do you think this could be used here to provide further motivation for your results?

Yes, entropy estimation is certainly an additional application for our results, particularly since the previous streaming algorithm utilizes $F_p$ moment estimation for $p\in(1,2)$. Thanks for the pointer!

Your result heavily relies on Ganguly's heavy hitters result. I tried looking at this and related papers but I didn't have enough time to read them. Those are not the most frequently cited papers. Did you maybe verify their correctness?

Are your results in the general turnstile model (where frequencies can get negative) or the strict turnstile modeli (where deletions are allowed, but all frequencies are always non-negative)? In particular, this goes back to the results of Ganguly. Which of the models are they for? Because if they are only for strict turnstile, then the case of $p=1$ is trivial.

Ganguly and Majumder's heavy-hitters algorithm uses Chinese remainder codes in their Lemma 9 statement and can be stated for the general turnstile model. Importantly, their Lemma 11 does not give an $\Omega(n)$ lower bound for the general turnstile model for the heavy-hitter problem because it only applies for heavy-hitters problem "with parameter $s$" with $s=\Omega(n)$, where the additive error for each estimate is $\frac{||x||_1}{s}$ and the universe has size $n$.

Furthermore, their work is subsequently extended to general error correcting codes in [NNW12], which actually achieves a slightly better space bound in logarithmic dependencies. Specifically, [NNW12] constructs a deterministic matrix $A$ with Johnson-Lindenstrauss properties, so that maintaining $Ax$ for the underlying frequency vector $x$ is amenable even in the general turnstile model.

[NNW12] Jelani Nelson, Huy L. Nguyên, David P. Woodruff: On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. APPROX-RANDOM 2012: 627-638

The only obvious weakness is that the result is a very slight improvement, sometimes in the third decimal place. While the insight is nice, the techniques are a linear combination of different algorithms for different cases. While I did not find the techniques very exciting, I think this passes the bar for NeurIPS.

We do agree that in some settings, the quantitative improvement is not large. However, we emphasize that optimal bounds for adversarial insertion-deletion streams is a major open question and therefore, the main strength of our work is the conceptual message that the despite the lack of recent progress, previous results are not optimal. Thus we hope our work will inspire future research in this direction.

Do you see any potential barriers to this approach? A discussion on what the limits are (is the bottleneck the heavy hitters algorithm or the tail-estimation algorithm?) would be greatly appreciated. This will also give the reader the assurance that this minor improvement is still significant as it pushes a new idea to a reasonable extent.

The relatively larger space used by the deterministic heavy-hitter algorithm compared to the space-optimal randomized heavy-hitter algorithms is a major bottleneck on further improving the bounds for this approach. One hope would be to improve the space usage of the deterministic heavy-hitter algorithm. However, it is known that the existing bounds are optimal, i.e., there are no deterministic heavy-hitter algorithms that use less space. Thus, the current analysis we use is tight for this approach and any further improvements likely require significantly new or different algorithmic designs.

Other than the $L_1$-heavy hitter estimation, many of the improvements are extremely incremental, for instance the aforementioned improvement of the dependence on the length $m$ of the stream for $L_{1.5}$-norm estimation to $m^{0.373}$ from $m^{0.375}$.

Other than the results for L_1-heavy-hitter estimation, my understanding is that there is no evidence of optimality for the results given in this work. For example, to the best of my understanding, it can conceivably be the case that the above-mentioned dependence of $m^{0.373}$ could in the future be improved to polylog$(m)$. If this happens, the impact of this work could potentially be small.

We do agree that in some settings, the quantitative improvement is not large. However, we emphasize that optimal bounds for adversarial insertion-deletion streams is a major open question and therefore, the main strength of our work is the conceptual message that the despite the lack of recent progress, previous results are not optimal. Thus we hope our work will inspire future research in this direction.

In subsection 1.1 what is the relationship between vectors $f$ and $x$? In the rest of the paper $f$ is used to denote the frequency vector of the stream, whereas the vector $x$ does not appear to be invoked anywhere again. In any case, it would be helpful if the vectors $x$ and $f$ are clearly defined in the beginning of subsection 1.1.

Due to the problems of heavy-hitters and moment estimation, we use both $f$ and $x$ to denote the same underlying vector. We will unify this notation with the same symbol in the updated version.

Subsection 1.1. would be easier to read if the paper used \paragraph to separate the parts of the subsection that address different problems.

Thanks for the suggestion, we will add paragraph notation to demarcate the discussion on heavy-hitters and norm estimation in the updated version.