Statistical-Computational Trade-offs for Density Estimation

Thank you for the review! We address your question below.

A quick question about the model of computation: do you suspect this to be the only and the main model of computation that is relevant for this problem? Are there any known algorithms (even inefficient) that do not fit this model of computation? In other words, do you expect this lower bound to hold universally over all algorithms (although, of course, maybe not provably)?

The list-of-points model of computation (this is the model in which we prove the lower bound) captures all known data-independent data structures for similarity search problems. Furthermore, it is the only model for which it is known how to prove strong lower bounds for such problems. As with any restricted model, it does not capture all possible algorithms. As mentioned in the paper, there exist data-dependent data structures (e.g., reference [5]) for approximate nearest-neighbor search (ANNS), but those techniques do not provide a benefit for random inputs such as in our lower bound construction. Since the submission of this paper, another interesting data-dependent technique has appeared for the ANNS problem. An exciting work by McCauley (reference below) applies black-box function inversion to yield better ANNS data structures in the regime where the data structure has near-linear space, in some cases even slightly improving beyond the list-of-points lower bound for that problem. Yet, we don't see a way to use this idea to improve our upper bound for density estimation on flat distributions. It is an interesting question whether some data structure for density estimation can utilize function inversion, though as it can only improve the space at the cost of query time, this seems unsuitable in our setting. In any case, where the data-dependent techniques do apply for the ANNS problem, they do not qualitatively change the relationship between the query time and space exponents.

Samuel McCauley. Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion. ESA 2024.

Thank you for your feedback. We address your comments below.

This paper only considers discrete density estimation, while I think it might be more interesting to learn density in the continuous setting, such as in mixtures of Gaussians.

The main contribution of this paper is a strong lower bound for density estimation. We prove it for very simple discrete instances, which automatically implies the same lower bounds for any (possibly continuous) generalizations of such instances.

From the upper bounds perspective, discrete density estimation (aka hypothesis selection) has had applications in learning mixtures of Gaussians and in robust learning of distributions (Daskalakis and Kamath [10], Diakonikolas et al [12]., Suresh et al. [18]). The basic idea is that the true distribution can be limited to a finite set of candidates, so that the density estimation can be run on those candidates.

The writing in this paper is a little bit confusing and it would be helpful if the authors could explain what they mean by data structure in the paper. For example: l5: what does it mean “preserving polynomial data structure”? l38: “the data structures are subject to statistical-computational trade-offs”, it is unclear to me what it means.

We are sorry if the writing was unclear. Our lower bounds are proved in the “list-of-points” model (Definition 2.3) which formally defines the class of data-structures. Intuitively, the model allows us to partition the set of input distributions into possibly overlapping groups. Given a query, we can search within a small number of adaptively chosen groups to find the most similar distributions to the query. Our main result is to show that in this model of computation, there is a non-trivial trade-off between the sample complexity of the algorithm and its runtime, when the algorithm is restricted to use polynomial space (referring to line 5). (We refer to it as "statistical-computational tradeoff"). As a concrete example, any data structure using space $k^{O(1)}$ and sample complexity $n/\log^{O(1)}(k)$, must have query time at least $k^{1-O(1)/\log\log k}$. In other words, even if we allow almost a linear number of samples, the running time must be close to linear.

Note that prior work can solve the density estimation problem with logarithmically many samples (at the cost of $\Omega(k)$ runtime) or $o(k)$ runtime (at the cost of $\Omega(n)$ samples). Thus our main result demonstrates a non-trivial statistical-computational trade-off (referring to line 38), since it rules out algorithms that simultaneously have very small sample complexity and fast runtime.

1. Could the authors explain where they incorporate the space information as a constraint in showing their lower bound? From Table 1, we know that if we allow superpolynomial space, then logarithmic sampling and query complexity are enough.

Please see the formal statement of Theorem 3.1 in the main body. The space parameter is directly linked to the query time. As stated there, allowing a large space means our query lower bound is smaller, as expected.

2. Does the query complexity used in this paper connect to the statistical query complexity? The latter is often used to establish statistical-computational trade-offs in statistical problems.

Indeed the statistical query (SQ) model has been very successful in showing many statistical-computational trade-offs, but we are not aware of any such work which incorporates all of space, sample complexity, and query complexity, as we do in our work. Likewise, the list-of-points model has been extensively used to show lower bounds in similarity search problems without a statistical component. In our work, we use the list-of-points model to prove hardness for a statistical similarity search problem, thereby establishing an alternate method to show hardness for statistical problems beyond SQ. It is not clear if one can prove similar bounds under the SQ model since its standard formulation does not have a `space’ or ‘preprocessing’ component, which the list-of-points model does.

3. Does the result in this paper provide evidence for row 5 in Table 1, i.e., when s is a constant?

In Theorem 3.1, $s$ needs to be at least a sufficiently large constant. We did not optimize this value since we are interested in the sublinear regime where $s = \omega(1)$.

4. l110 in Definition 2.1 is confusing. I am wondering P is a dataset that consists data or distributions? I think the word "dataset" usually refers to samples.

Here we refer to “dataset” as the set of input distributions which we can preprocess. The samples from the unknown distribution are always referred to as samples.

Thank you for your feedback. We address your comments below.

I'm not sure that NeurIPS is the best venue, this seems much more theoretical.

We believe that NeurIPS is an appropriate venue, given that several related works (e.g., [4,7,18]) appeared in past NeurIPS conferences.

The lower bound is only for a particular kind of data structure.

As mentioned at the end of Section 2, the data structure model we are proving lower bounds for captures all known “data-independent” similarity search data structures such as locality-sensitive hashing. This has also been the model of choice for other problems in literature, such as nearest-neighbor search. Unfortunately, proving strong lower bounds for general data structures for virtually any computational problem in any domain is beyond the current lower bound techniques.

The upper bound is just for the instances as used in the lower bound construction, and very synthetic.

Our upper bounds complement our lower bounds showing that our lower bound results are essentially tight for the setting they are proved in, therefore encapsulating the possibilities and limitations for this problem. We also note that the upper bound holds for general half-uniform distributions (not necessarily with random support).

But I don't really see a strong motivation for this problem, where one gets samples from one of a fixed, large-but-finite, set of possible discrete distributions and must identify which one.

The main contribution of this paper is a strong lower bound for density estimation. We prove it for very simple discrete instances, which automatically implies the same lower bounds for any (possibly continuous) generalizations of such instances.

Thank you for your feedback. Please see our general response discussing the novelty of our techniques above.