Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters

Summary

The authors present an algorithm for adversarially robust $L_p$-estimation estimation in the turnstile streaming model, which improves on the space-complexity of existing algorithms in the regime $p \in (1, 2)$. They achieve this improvement via an alteration of the dense-sparse tradeoff technique of the existing state-of-the-art algorithm where they show it is sufficient to track the heavy-hitters while keeping track of an estimated residual. In addition to the improved Lp-estimation algorithm, the results include an adversarially-robust streaming algorithm for the heavy-hitters problem along with an adversarially robust algorithm for estimating the residual of the frequency vector. The authors also include experiments providing support for their theoretical improvement guarantees.

Strengths

- The authors do a great job of situating themselves in prior work, and explaining exactly how their results differ and improve. - While I am not well-versed in this area, the results seem correct and were clearly explained and decomposed.

Weaknesses

- 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. - 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.

Questions

- 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. - 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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

I think the authors have adequately addressed limitations and the assumptions made in their results.

Summary

In adversarially robust streaming, one wants to design streaming algorithms that work well even in the interactive setting, in which the stream is not fully fixed in advance, but is constructed element by element by an adversary who can see the current solution provided by the streaming algorithm. If the algorithm is randomized, each intermediate solution may reveal some information about the internal randomness of the car, which could allow the adversary make updates that break the estimates of the algorithm. The paper concerns two fundamental problems in this setting: heavy hitters and moment estimation. In particular, the paper improves on the best known algorithm for moment estimation that considers two regimes, sparse and dense vectors. The paper shows that estimating $L_p$ moments for $p \in [1,2)$ can be done in smaller space than previously known. The achievement follows by leveraging known deterministic algorithms for heavy hitters and using them for tracking significant changes to the frequency vector.

Strengths

* Insightful contribution to a very active research area. * Non-trivial improvement for some of the most popular streaming problems: heavy hitters and moments. The combination of different ideas to make this work is not easy.

Weaknesses

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$.

Questions

"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? 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.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

No direct negative social impact.

Summary

This paper focuses on the L_p estimation (of the frequencies of items in a stream) in the adversarially robust streaming setting. The previous work by Ben-Eliezer, Eden and Onak achieved an $\tilde{O}(m^{p/2p+1})$ space, which is slightly better than the $P(\sqrt{m})$ space bound due to the flip number technique by considering a sparse-dense tradeoff. The authors of this work question whether the above bound is tight or if it can be improved. The authors present an algorithm that beats the bound of $\tilde{O}(m^{p/2p+1})$. This is obtained by first building an adversarially robust streaming algorithm for L_p heavy hitters, utilizing deterministic turnstile heavy-hitter algorithms with better tradeoffs. This is then combined with another algorithm that estimates the frequency of the tail-vector, and has additive error and space independent of the size of the tail.

Strengths

As the paper mentions, this is a conceptual breakthrough, showing that the previous bound of $\tilde{O}(m^{p/2p+1})$ is not tight. The paper explains all the ideas pretty well, and it was easy to read. The novel insight here is that in the dense-sparse tradeoff of [BEO22], in order to change the p-th moment by at least a $1+\epsilon$ factor, most of the updates are to a small number of coordinates, which then naturally must have either already been heavy-hitters, or became so after the update. The authors are able to effectively handle the had case of [BEO22], resulting in a better improvement.

Weaknesses

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.

Questions

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.

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Apart from the limitation described in the theorem statement, the authors could discuss limitations of this approach, and what the current barrier is.

Summary

The work develops new algorithms in the adversarially robust streaming model. In this model, the algorithm observes updates to some vector arrive in the form of a data stream and maintain estimates to some property of the vector as it changes. At each time-step i, the algorithm receives the update of the vector at this time-step. Specifically, it receives an update of the form $(i, \Delta_i)$ that means that the $i$-th coordinate of the vector changes by $\Delta_i$. Also, at every time-step i the algorithm outputs an estimate of some property of this vector. The work focuses on the adversarially robust setting, where the updates in subsequent time-steps can potentially depend on the estimates that the algorithm gave in previous time-steps. This is an important property of the streaming algorithm, because when decisions are made based on the estimates given by a streaming algorithm this will likely influence the data received by this algorithm in the future. At the same time, notably, many previously studied streaming algorithms are not adversarially robust. Additionally, the paper focuses on the turnstile setting, i.e. the updates $\Delta_i$ to the vector can be both positive and negative. The length of the data stream is denoted by $m$, and in the adversarially robust streaming setting the paper mainly studies the problems of $L_p$-heavy hitter estimation and the problem of estimating the $L_p$ norm of the vector. The problem of adversarially robust $L_p$-heavy-hitter estimation requires the streaming algorithm maintain a list of elements that contribute a lot to the $L_p$ norm of the vector. Formally, it requires the list to contain all elements $i$ for which $|x_i| \geq \epsilon ||x||_p$ and all elements $j$ in the list should satisfy $|x_j| \geq \epsilon/2 ||x||_p$. Up to constantants and logarithmic factors in m and $\epsilon$, the $L_p$-heavy-hitter estimation algorithm requires $1/\epsilon^2.5 * m^\alpha$, where $\alpha=(2p-2)/(4p-3)$. This improves on the previous algorithm from the literature that achieves $\alpha=p/(2p+1)$. This constitutes an improvement for all $p$ in $[1,2)$, with the most pronounced improvement at $p=1$ where the space usage is improved from polynomial in $m$ to polylogarithmic. The work also presents new algorithms for estimating the $L_p$-norm of the underlying vector (up to a multiplicative factor of $1+\epsilon$). Up to polylogarithmic factors and constants, the amount of space used by the algorithm is of the form $m^c poly(1/\epsilon)$. The exact dependence of $c$ on the value of $p$ is $c=(24p^2-23p+4)/((4p-3)(12p+3))$. As the paper notes, for $p=1.5$ we have $c=0.373$ whereas the best previous algorithm has $c=0.375$. The work improves on the dense-sparse decomposition method of the previous work.

Strengths

- The adversarially robust streaming framework is natural and well-motivated. - For the L_1-heavy-hitter problem the work gives qualitative improvement on the previous algorithms by improving the space use from polynomial in the stream length to polylogarithmic.

Weaknesses

- 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.

Questions

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. Subsection 1.1. would be easier to read if the paper used \paragraph to separate the parts of the subsection that address different problems.

Rating

6

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

It would be helpful if the authors added a dedicated paragraph in the paper that indicated what are the main limitations of the work according to the authors.