Statistical-Computational Trade-offs for Density Estimation
Authors: Anders Aamand
Alexandr Andoni
Justin Y. Chen
Piotr Indyk
Shyam Narayanan
Sandeep Silwal
Haike Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: statistical-computational tradeoffs
lower bounds
data structures
density estimation
hypothesis selection
Primary area: learning_theory
TL;DR: We show the first lower bound for the data structures version of the fundamental density estimation problem, establishing that there is no data structure with strongly sublinear sample complexity and query time.

Abstract: We study the density estimation problem defined as follows: given $k$ distributions $p_1, \ldots, p_k$ over a discrete domain $[n]$,  as well as a collection of samples chosen from a "query" distribution $q$ over $[n]$, output $p_i$ that is "close" to $q$. Recently Aamand et al. gave the first and only known result that achieves sublinear bounds in both the sampling complexity and the query time while preserving polynomial data structure space. However, their improvement over linear samples and time is only by subpolynomial factors.

Our main result is a lower bound showing that, for a broad class of data structures, their bounds cannot be significantly improved. In particular, if an algorithm uses $O(n/\log^c k)$ samples for some constant $c>0$ and polynomial space, then the query time of the data structure must be at least $k^{1-O(1)/\log  \log  k}$, i.e., close to linear in the number of distributions $k$. This is a novel statistical-computational trade-off for density estimation, demonstrating that any data structure must use close to a linear number of samples or take close to linear query time. The lower bound holds even in the realizable case where $q=p_i$ for some $i$, and when the distributions are flat (specifically, all distributions are uniform over half of the domain $[n]$). We also give a simple data structure for our lower bound instance with asymptotically matching upper bounds. Experiments show that the data structure is quite efficient in practice.

Statisical-Computtational Trade-offs for Density Estimation
Anders Aamand
Alexandr Andoni Columbia University andoni@cs columbia. edu
Justin Y. Chen MIT justcomit, edu
University of Copenhagen aamand@mit edu
Piotr Indyk MIT indyk@mit.n edu
Shyam Narayanan
Sandeep Silwal UW-Madison si silwal@cs, wisc.edu
Citadel Securities*
shyam. s. naw.yaaannngaaaaaa...a com
Haike Xu MIT haikexuêmit edu
Abstract
We study the density estimation problem defined as follows: given & distributions P1..... Ps over discrete domain [n]. as well as a collection of samples chosen from "query" distribution q over (n].. output p; that is "close" to Recently [[] gave the first and only known result that achieves sublinear bounds both the sampling complexity and the query time while preserving polynomial data structure space. However, their improvement over linear samples and time is only by subpolynomial factors.
Our main result is lower bound showing that, for a broad class of data structures, their bounds cannot be significantly improved. In particular, if an algorithm uses (n// log" k)) samples for some constant c > and polynomial space, then the query time of the data structure must be at least 1 (0)0 log loglog i... close to linear in the number of distributions k. This is novel statistical-cut computatioal trade-off for density estimation, demonstrating that any data structure must use close to linear number of samples take close linear query time. The lower bound holds even the realizable case where p; for some i, and when the distributions flat (specifically, all distributions
uniform over half of the domain [n)).. We also give a simple data structure for our lower bound instance with asymptotically matching upper bounds. Experiments show that the data structure is quite efficient in practice.
Introduction
The general density estimation problem is defined as follows: given & distributions PI.... ... Pk domain [n]] build a data structure which when queried with collection of samples chosen from "query" distribution q over [ri], outputs p; that is "close" q. An ideal data structure reports the desired quickly given the samples (i.e., has fast query time), uses few samples from q (i.e., has low sampling complexity) and uses little space.
"Wok done student MIT In this paper we focus on finite domains.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In the realizable case, we know that is equal to one of the distributions Pj, | S k, and the goal
identify a (potentially different) p; such that l - p;ll 1 I for an error parameter 0. In the more general agnostic case, is arbitrary and the goal is to report such that
l1g pell C min l1g Py p|||1
for some constant C > 1 and error parameter > The problem essentially that of non non- con-paamettii learning of a distribution statistical complexity was understood already in [7], and the more modern focus has been on the structured case (when FF has additional properties). Surprisingly, its computational complexity is still not fully understood.
F, where the family F == {PI....P. has no structure whatsoever. Its
Due to its generality, density estimation is fundamental problem with myriad applications in statistics and learning distributions. For example, the framework provides essentially the best possible sampling bounds for mixtures of Gaussians [T0] 18 [2]. The framework has also been studied in and low-space settings.
private g
Samples
Query time
Space
Comment
Reference
log &
kn k2 loo k
kn
17
log
k log k k
log
log &
log k nkk
ne Olog 2
precompute all possible samples any constant >
folklore
fon + tit
n
n + k
177
104
n/s
k.
O(pu)7 log
lower bound for any p.. >> O, sufficiently large algorithm for half-uniform distributions
this paper
n/s
k. D(P
kn + kltp=
this paper
Table 1: Prior work and results. For simplicity the results stated only for the realizable constant e > 0, and with (-)) factors suppressed. The bound of (I (row 6 of the table) is stated as in Theorem 3.1 of that paper. However, by adjusting the free parameters, their algorithm can be easily generalized to use n/s samples for n/s > n/polylog(n), resulting in a query time of O(n + + k1=R())/>)) Note that the term 1/s in their bound results in a larger exponent than 1/ 1/log s in our upper bound, Furthermore, our algorithm correct as long as n/s > log k/c² which is the information theoretic lower bound.
Table summarizes known results as well as our work. As seen in the table, the data structures are subject to statistical-computee computaaall trade-offs. On one hand, if the query time not a concern, logarithmic in & samples are sufficient [I]. On the other hand, if the sampling complexity is not an issue, then one can use the algorithm of [6] learn the distribution such that ||@ all S c/2, and then deploy standard approximate nearest neighbor search algorithms with sublinear query time, e.g., from [14]. Unfortunately both of these extremes require either linear (in n) sample complexity, or linear (in k) query time time. Thus, achieving the best performance with respect to one metric resulted in the worst possible performance on the other metric.
The first and only known result that obtained non-trivial trivirii improvements to both the sampling complex- ity and the query time is due a recent work of M. Their improvements, however, were quite subtle: the sample complexity was improved by sub-logarithmic factor, while the query time was improved by nobboollyooiil factor of 1 1/1/4
2k)g(k)
This result raises the question of whether further improvements are possible. In particular, [T] asks: To what extent our upper bounds of query and sample complexity be improved? What are the computational ceonutaaiina--saatttii -statistical tradeoffs between the sample complexity and query time? These are the questions that we address in this paper.
We give the first limit to the best possible tradeoff between the query time and sampling complexity. demonstrating a novel citistical-cmmpuaationnlll tradeoff for fundamental problem. To our knowledge, this the first statistical-com computation trade-off for a data structures problem-if we allow for superpolynomial space, logarithmic sampling and query complexity
Lower bound:

---

1.0
CaalisticllCoomputtaiioaaa Trade-offs
1.000
Log-Scale Scale
0.975
(Query Exponent)
0.8
0.6
0.900
0.4
0.875
UB for Hals-Uniform Distribations
& 0.2
Distributions Numerical UpperiLower Bound for Hale-Unitora Distributions
0.850
0.825
Hall-Unnform Distribattoons
0.0
0.01
0.03
0.05
0.07
0.09
0.800
10-1
10-1
10-7
10-6
10-3
10-1
10
1/s (Samples as fraction of n)
1/s (Samples as a fraction of m)
Figure 1: Left: Trade-off between 1/8 (samples as a fraction of n) and the query time exponent Pg for algorithm for half-uniform distributions (solid green curve), the algorithm by [ for general distributions (dashed green curve), our analytic lower bound (solid red curve), and numerical evaluation of the bound from Theorem (32 (dashed black curve). We have fixed the space parameter Pv. = 1/2. The plots illustrate the asymptotic behaviour proven in Theorem 3.1 and Theorem 4.2 that oe, Pg 1 ( log s) both in the lower bound and for our algorithm for half-uniform distributions. Right: The same plot zoomed in to the upper left corner with 1/s on log-scale.
is possible. As in 5 6
3), we focus on data structures that operate in the so-called list-of- points mode which captures all bounds depicted in Table I Suppose that the query time of the data structure is of the form kPs. We show that, the data structure allowed polynomial space kn+hl+0n and uses n/s samples, then the query time exponent P3 must be at least 1 (pw) log Therefore, we set s = log" k for some c > 0, as in []. then the query time of the data structure must be at least {11)((1) log log That is, the query time can be improved over linear time by at most a factor of ((((1) log log 20ilog k/ log log k), This shows that it is indeed not possible to improve the linear query time by a polynomial factor while keeping the sampling complexity 0.
below n/ log" n, for any constant
Our lower bound instance falls within the realizable case and in the restricted setting where the data and query distributions are "half-uniform" i.c. each distribution is uniform over half of the universe fn). Note that showing a lower bound under these restrictions automatically extends to the agnostic with general distributions, the former is a special case of the latter.
Our construction takes lower bounds by for set similarity search as a starting point. We adapt their lower bound to our setting in which queries are formed via samples from distribution. The resulting lower bound is expressed via a complicated optimization problem and does not yield closed-form vatistical-computatie
trade-off. One of our technical contributions is solve this optimization problem for a regime of interest to get our explicit lower bound.
We complement the lower bound by demonstrating data structure for hard instances (in the realizable case with half-uniform distributions) achieving sampling and query time bounds asymptotically matching those of the lower bound. We note that the existence such an algorithm essentially follows from [3]. However, the algorithms presented there are quite complex. "bare-bones" version of their approach, and
Upper bound:
In contrast, our algorithm can be viewed result it is simple and easy to implement. To demonstrate the last point, we present an empirical evaluation of the algorithm on the synthetic data set from [[] and compare that paper, as well as a baseline tailored to half-uniform distributions. Our faster algorithm achieves over 6x reduction in the number of operations needed to correctly answer 100 random queries.
the algorithm from
Figure [ we illustrate the trade-off between the number of samples and the query time exponent Pg in upper and lower bounds.
Open Questions: The direct question left open by our work is whether there exists data structure whose upper bounds for general distributions match our lower bounds (note we give matching
*See Section 2 for the formal definition. Generally, proving data structure lower bounds requires restriction to specific model of computation, and the of list-of-points model is a standard choice for related approximate nearest neighbor problems.
3

---

upper bounds for half-uniform distributions). [ give an algorithm for the general case, but with a worse trade-off than that described by our lower bound. More generally. are there other data structures problems for which one can show statistical-compuaationaa tradeoffs between the trifecta of samples, query time, and space?
Preliminaries and Roadmap for the Lower Bound
First we introduce helpful notation used throughout the paper.
Notation: We use Bern(p) to denote the Bernoullip) distribution and Poi(A) to denote the Poisson(A) distribution. For a discrete distribution f X R, we use supp(f) {z E X f(z) * 0f to denote f's support and (supp([)) to denote the size of its support. We use f to denote the tensor product of n identical distribution We call distribution / half-uniform it is uniform distribution on its support with [T] = n/2. For a binary distribution P supported on (0, 1 with a random
TP = 1]] Similarly, for a joint distribution P[r 0]
variable x ~ P, we sometimes explicitly write P
TP(r = 1, = 1 PP = = 1, PQ over {0, 1)2 with (z, y) ~ PQ, we write PQ = PP(r 0, y 1]
P|z 0, - 0]
For a vector E R", we æ[i] to denote its i-th coordinate. We use d(pllq) p log
(1 (1-p) 1- and D(PIIQ) = Eper? P log P to denote the standard KL-divergence over binary distribution or general discrete distribution. KL. divergence D ()) is only finite when supp( P) C supp(Q), also denoted as < Q. All logarithms are natural.
q
We now introduce the main problem which we use to prove our statistical-computttionn lower bound. We state a version which generalizes half-uniform distributions.
Definition 2.1 (Uniform random density estimation problem). For universe generate the following problem instance:
{0, 1)", we
1. dataset Ps is constructed by sampling uniform distributions, where for each uniform distribution p E P. every element E [n]] is contained in p's support with probability w..
2. Fix distribution p" P. take Poi
supp(p"))
samples from p' and get query set q.
The goal of the data structure is to preprocess P such that when given the query set q, it recovers the distribution p".
We denote this problem as URDE(w,, s). URDE abbreviates Uniform Random Density Estimation. The name comes from the fact that the data set distributions are uniform over randomly generated supports. In Section 3 we prove a lower bound for URDE by showing that previously studied 'hard' problem can be reduced to URDE. The previously studied hard problem is the GapSS problem.
Definition 2.2 (Random GapSS problem (3), For a universe U = 10, and parameters 0 < Wg
<
< 1, let distribution Pt- = Bern(w.,)" Pq Bern(w,,". and PQu random CapSS(w,,, w.) problem is generated by the following steps:
0
A
dataset P S U constructed by sampling points where p ~ Po for all p P. dataset point p* P is fixed and query point q is sampled such that (g.p") PQu.
3. The goal of the data structure is preprocess P such that recovers p" when given the query point g.
We denote this problem as random CapSS(wa, W.y GapSS abbreviates Gap Subset Search. To pro- vide some intuition about how GapSS relates to URDE, let us denote the data set P = {pI..... Pk Then the Pa E (0, 1)" can naturally be viewed as independently generated random subsets of [n]. For each i, p; includes each element of [n] with probability w.. The query point q can similarly be viewed as random subset of [n] including each element with probability Wy but it correlated with some fixed p" e P. Namely, p" and q generated according to the join distribution Pqu (with the

---

right marginal distributions Po and Pt) such q a subset of p.. The goal in GapSS is to identify pd given q. This intuition is formalized in Section 3
Our main goal is to study the asymptotic behavior of algorithms with sublinear samples, or specifically, the query time and memory trade-off when only sublinear samples are available, so all our theorems assume the setting that both the support size and the number of samples & goes to infinity and n & k & poly(n). Sublinear samples mean that < o(1) as n goes to infinity.
Our lower bound extend and generalize lower bounds for GapSS in the dist-of-point's model. Thus, the lower bound we provide for URDE also the "List-of-points" model defined below (slightly adjusted from the original definition in [5] to our setting). The model captures large class of data structures for retrieval problems such as partial match and nearest neighbor search: where one "match" a point in the dataset.
preprocesses dataset P to answer queries 9 that
Definition 2.3 (List-of-points model). Fix universe Q of queries, a universe U of dataset points, as well as a partial predicate Φ Q x S + {0, 1, J. We first define the following eerrerieval problem: preprocess a dataset P _ U so that given a query q Q such that there exist some p" E P with 6(q. = 1 and p(g. p) = 0 on all p E P {p*), we must report p".
Then list-of-points data structure solving the above problem is as follows:
1. We fix (possibly random) sets A, S U, for 1 < i S m; and with each possible query point q E Q. we associate a (random) set of indices ((g) S [m]]
2. For the given dataset P U, we maintain m lists of points L1, L.,.... Lmm where L, = Pn A..
3. On query q E Q, we scan through lists L, where i I(q), and check whether there exists some p E Lg with ()..p) = 1. it exists, return p.
The data structure succeeds, for a given q E Q. p" P with o(g.p") 1. if there exists E I(4) such that p* E L, The total space is defined by S = m Eie(m) |L,] and the query time by T = [(a)) + EiEr()) [L,]-
To see how the lower bound model relates URDE, in our setting, the 'é-retrieval problem' is the URDE problem: U is the set of random half-uniform distributions, Q is the family of query samples, and (²(.))) p) if the samples were drawn from the distribution p, and otherwise. (The I case corresponds to an "approximate" answer, considering by the earlier papers; but we define URDE problem directly to not have approximate solutions.)
We use the list-of-points model as it captures all known "data-indeppndent" similarity search data structures, such as Locality-Sensitic Hashing 14. In principle, a lower bound against this model does not rule out dependeenndnnt hashing approaches. However, these have been useful only for datasets which are not chosen at random. In particular, (5) conjecture that data-dependency doesn't help on random instances, which is the setting of our theorems.
3 Lower bounds for random half-uniform density estimation problem
In this section, we formalize our lower bound. The main theorem of the section is the following. Theorem 3.1 (Lower bound for URDE). If list-of-points data structure solves the URDE (b.s) using time O(kpa) and space O(k)+Pu), and succeeds with probability at least 0.99, then for sufficiently large s, Pg 2 21-log2-og3
Pa
log
To prove Theorem 3.1, our starting point the following result of S that provides lower-bound for the random GapSS problem.
Theorem 3.2 (Lower bound for random GapSS. Bl). Consider any list-of-points data structure for solving the random GapSS(ww: wg) problem on k points, which uses expected space O(k-tpy tP.), has expected query time OkkPo-oz(l) and succeeds with probability at least 0.99. Then every [0, 11, we have that
apg (1 a)pu 2 inf F(tust tt))
l dn [00011 tw
5

---

where F( tq)
P( dit l1ne)
d(tul wa) + (1 a)
DiT ( p
mg
and
d(tullwu
win 1ig
T= arg inf
D(T
TEP Ex-rlX)
Our proof strategy is to first give reduction from the the GapSS problem to the URDE problem. Note that the URDE problem involves a statistical step where we receive samples from an unknown distribution (our query). On the other hand, the query of GapSS is specified vector, rather than distribution, with no ambiguity. Our reduction bridges this and shows that GapSS is a 'strictly easier' problem than URDE.
Theorem 3.3 (Reduction from random GapSS to URDE). If y list-of-points data structure solves the URDE(w, ww: 8) problem of size in Definition 2.1 using time O(kPs) and space Okk+tp)), and succeeds with probability at least 0.99, then there exists list-of-points data structure solving the using space Pp)) and time O(k + +wo -1).
GapSS(ww, (w.; Wa) problem for wo- Wa - e
and succeeds with probability at least 0.99.
Proof. We provide reduction from random GapSS(wa Wa) to URDE(W,. s) with Specifically, for each instance (P1. Pi 91) generated from GapSS (ww, wy) in Def-
uu log [1 mig
inition 2.2 will construct an instance (P2, p2, q2) generated from URDE(W,, 8) satisfying Definition 2.1 for some 8.
For each point P1 P1. is straightforward to construct corresponding uniform distribution P2 supported on those coordinates where p1 = 1. Then let's construct d from gı- Recall that for each i E U with [
we have [1] O with probability 1 'Ls in which case we add no element to aa
42-
If q1 [i] = 1, we add Poi.
copies of clement i to 92 where IP [Poi (A) = x]
Poi (A)= =zz]
for any x > 0. By setting s
we have Poi
= 0
"y. Thus for
wh log
each element in pi. the number of its appearances d2 exactly follows the distribution Poi(
According to the property of the Poisson distribution, uniformly sampling Poi
supp(p5))
elements times. Therefore,
from set of size |supp(p))] is equivalent to sampling each element Poi( a-wa. the constructed instance (P2, P2, 92) is instance of URDE(W,,, s), stated in Definition 2.1 Equivalently, we have the relationship Wig = Wa arttie
Hence we complete our reduction from GapSS(Definition 2.2 to URDE (Definition 2.1
To get the desired space-time trade-off in the sublinear sample regime, which means $ - oo (or equivalently W1 -> 0), and get an interpretable analytic bound, we need develop upon the lower bound in Theorem 3.2 This requires explicitly solving the optimization problem in Theorem 3.2
Proving Theorem 3.4 (roof in Appendix 33) is the main technical contribution of the paper.
Theorem 3.4 (Explicit lower bound for random GapSS instance). Consider any list-of-points data structure for solving the random GapSS (1, w.) which has expected space O(kl+pu) ), uses expected
query time O (kPr (kPr-)(1)), and succeeds with probability least 0.99. Then have the following 20gg2-0(1))
lower bound for sufficiently small Wg P4 2 Wy
T
Applying our reduction to the random GapSS lower bound above allows us to prove our main theorem.
Proof of Theorem 3.7 According to the reduction given in Theorem 3.3 from GapSS( (Way W. to
URDE(W,, 8) where Wi = Wm wu and get the desired lower bound.
> 1. We can apply the lower bound in Theorem 3.4
Remark 3.5. Note that in URDE (1, s), the distributions uniform random subsets of expected size n/2 and the query set is generated by taking Poi (2]supp(r")) samples from one of them p". This is not quite saying that the query complexity is n/s. However, by standard

---

concentration bounds, from the Poisson sample, we can simulate sampling with a fixed number of samples n/s Ó ((vn/8) n/s(1 o(1)) with high probability, and so, any algorithm using this fixed number of samples must have the same lower bound on Ps as in Theorem 3.1
4 A simple algorithm for half-uniform density estimation problem
In this section, we present a simple algorithm for special case of the density estimation problem when the input distributions are half-uniform. The algorithm also works for the related URDE( 2. s) problem of Theorem 3.1 A distribution over [n] is half-uniform if there exists T C [nx] with [7]] = n/2 such that p.l = 2/n if E T and 0 otherwise. The problem we consider in this section is:
Definition 4.1 (Half-uniform density estimation problem; (U)D(s,e))- For domain [nt, integer k, 8 > 0, and
O, we consider the following data structure problem.
1. A dataset P of & distributions Pl....,P over [n] which are half-uniform over subsets ......, Th [n]] each of size n/2 is given.
2. We receive a query q consisting of n/s samples from unknown distribution p P satisfying that lp::- - P5 2 for + i".
3. The goal of the data structure is to preprocess P such that when given the query set q, it recovers the distribution p;- with probability at least 0.99.
This problem is related to the URDE(1/2,55 s) problem in Theorem 3.1 Indeed, with high probability, an instance of URDE(1/2, s) consists of almost half-unifome distributions with support size n/2 +
O(yn log E). Moreover, two such distributions pt, Py have 1p: Py l| (1 = (( (log k)/n) with high probability. Thus, an instance of (RD2(1/2,s) s) is essentially an instance of (UUDE(s.) 1).
To solve HUDE(s, E), can essentially apply the similarity search data structure of 33 querying it with the set Q consisting of all elements that were sampled at least once. This approach obtains the optimal trade-off between Pu. and P. (at least in the List-of points model). The contribution of this section is to provide a very simple alternative algorithm with a slightly weaker trade-off between Pu. and Pg. Section 5 evaluates the simplified algorithm experimentally. Our main theorem is:
List-off-oints
Theorem 4.2. Suppose n and k are polynomially related, 8 2 2, and that s is such that 22 2 Clogk for sufficiently large constant C. Let > O and Pu > 0 be given. There exists a data structure for the HUDE(ss E) problem using space O(K + nk) and with query time O
Tog
+ tnss)
Let us compare the upper bound of Theorem 4.2 to the lower bound in Theorem 3.1 While The- orem 4.2 is stated for half-uniform distributions, its proof is easily modified to work for the URDE (1/,,s) 2) problem where the support size is random. Then E 1 ((1) and as s - oc, 2
27- = +(1+)())) Thus, the query time exponent in Theorem 4.2 is Pa 1-(1+o(1)) log(2)p. log know that any algorithm must have Pq 2 1- (1+ o(1) Au as s + 0o. Asymptotically, our algorithm therefore gets the right logarithmic dependence on s but with leading constant of log(2) ~ 0.693 instead of 1.
URDE(1/2,s) s) is exactly the hard instance in Theorem 3.1 and
log
Next define the algorithm. Let l and L be parameters which will also specify shortly. During preprocessing, our algorithm samples L. subsets Si...., St. of [n) each of size l independently and uniformly at random. For each E T,, it stores set A, of all indices j E [k] such that S; TJ, namely the indices of the distributions /) which contain S, in their support. See Algorithm !
During the query phase, we receive n//s samples from p P:- for some unknown i" E [A:]. Our algorithm first forms the subset Q C [r]] consisting of all elements that were sampled at least once. Note that [Q] < n//s as elements can be sampled several times. The algorithm proceeds in two steps. First, it goes through the L sets Si,..., SL until finds an such that S, C Q. Second, scans through the indices j A,. For each such j it samples set U, one element at a time from Q. It stops this sampling at the first point of time where either U, & Т₃ or [U,] = C log for a sufficiently
'The requirement n/s >> log k/e² is the information theoretic lower bound for the density estimation
problem.
7

---

Algorithm Density estimation for half-uniform distributions (preprocessing)
Input: Half uniform distributions {pt Jo over [n] with support sets {T,
2: Output: A data structure for the density estimation problem.
3: procedure PREPROCESSING((pp)))
4: for i = 1 to L do
5: 5; < sample of size from [n]
6: A; - {j E [k] 5; C }
7: Return (S,, [e)E(()
Algorithm Query algorithm for half-uniform distributions
1: Input: Half uniform distributions {p: jp over [n] with support sets (Ti data structure (St, A.)eezz + Preprrressssnnn (pt))=)) and n/s samples from query distribution p..
2: Output: A distribution Рy.
3: procedure DENSITY-ESTIMATION
4: Q - -i E [n]] appeared in the n/s samples)
5: for i 1 L do
6: if S; C Q then
7:
for j E A; do
8:
U, < sample from Q size C log for a large constant C.
9:
if U, C TΙ then
Return: Pj
large constant C. In the first case, it concludes that Pj is not the right distribution and proceeds to the next element of A, and in the latter case, it returns the distribution pj as the answer to the density estimation problem. See Algorithm 2 We defer the formal proofs to Appendix B
Experiments
We test our algorithm in Section experimentally on datasets of half-uniform distributions as in and corresponding our study in Sections and 4 Given parameters and n, the input distributions are & distributions each uniform over randomly chosen n/2 elements.
Algorithms We compare two main algorithms: an implementation of the algorithm presented in Section which we refer to as the Subset algorithm and baseline for half-uniform distributions which we refer to as the Flimination algorithm. The Subset algorithm utilizes the same techniques as that presented Section but with some slight changes geared towards practical usage. We do not compare the "FastToumament" of [] since it computationally prohibitive; see Remark C
The Subset algorithm picks L subsets of size and preprocesses the data by constructing a dictionary mapping subsets to the distributions whose support contains that subset. When a query arrives, scan through the L subset until we find one that is contained the support of the query. We then restrict ourselves to solving the problem over the set of distributions mapped to by that subset and run Elimination. The Elimination algorithm goes through the samples one at time. starts with a set of distributions which is the entire input in general Subset algorithm. To process sample, the Elimination algorithm removes from consideration all distributions which do not contain that element in its support. When a single distribution remains, the algorithm returns that distribution as the solution. As the input distributions are random half-unifome distributions, we expect to throw away half of the distributions at each step (other than the true distribution) and terminate in logarithmically size of the initial set of distribution steps.
subset of the input when called subroutine of
Experimental Setup Our experiments compare the Subset and Elimination algorithms while varying several problem parameters: the number of distributions k. the domain size n, the number of samples S (for simplicity, we use this notation rather than n/s samples as in the rest of the paper), and the size of subsets used by the Subset algorithm. While we vary one parameter at time, the others set to default of & 50000, 500, S = 50, [ = 3. Given these parameters,

---

000
rope Susse 10uro
0.4
Subret (ound #3ps #0ys
005
Operaators
timmntoer linw
Tire in Seconds
operatonns
Binration
000
02
0.04
00000
0.23
20032
0.0
100380
200038
100000
#30000
503000
203
422
660
000
1000
Distributions
Domein Size
(a)
100000
Subret (Dunt) KOps
0.040
Subcet NOpO
0.00
80000
Eimenation #0pe
0.00
Opperations
Operattions
Elmecation Time
Time SECCO
60000
0 825
-0.00
40000
T1/00
0 010
10000
0.01
30
50
50
00
2.0
25
3.0
3.5
4.0
4.5
5.0
Samples
Subset Size
(d)
Figure 2: Comparison of efficiency of the Subset (Ours) and Elimination algorithms as (a): the number of distributions varies. Other parameters are set to n 500, S = 50, = 3. (b): the domain size varies. Other parameters are set to k = 50000, S = 50, l - 3. (c): the number of
samples S varies. Other parameters are set to k 50000, n 500, 3. (d): the subset size varies. Other parameters are set to k 50000, 500, S 50.
evaluate the Subset algorithm and the Elimination algorithm 100 random queries where each query corresponds to picking one of the input distributions as the true distribution to draw samples from.
In all settings we test, the Elimination algorithm achieves 100% accuracy on these queries, which to be expected as long as the number of samples is sufficently more than the log, k. There remaining free parameter, which is the number of subsets L used in the Subset algorithm. We start with a modest value
= 200 and increase L by a factor of 1.5 repeatedly until the Subset algorithm also achieves 100% accuracy the queries (in reality, it's failure probability will likely still be greater than that of the Elimination algorithm). The results we report correspond to this smallest value of L for which the algorithm got all the queries correct.
For both algorithms, we track the average number of operations well as the execution time of the algorithms (not counting preprocessing). A single operation corresponds to membership query of checking whether given distribution/sample contains a specified element in its support which the main primitive used by both algorithms. We use code from as basis for our setup.
Results For all parameter settings we test, the number of operations per query by our Subset algorithm is significantly less than those required by Elimination algorithm, up to a factor more than 6x. The average query time (measured in seconds) shows similar improvements for the Subset algorithm though for some parameter settings, takes more time than the Elimination algorithm. While, in general, operations and time are highly correlated, these instances where they differ may depend on the specific Python data structures used to implement the algorithms, cache efficiency, or other computational factors.
As the number of distributions & increases, Figure 2a shows that both time and number of operations scale linearly. Across the board, our Subset algorithm outperforms the Elimination algorithm baseline and exhibits a greater improvement as & increases. On the other hand, as the domain size increases in Figure 2b the efficiency of the Subset algorithm degrades while the Elimination algorithm maintains its performance. This due to the fact that for larger domains, more subsets are needed in order to correctly answer all queries, leading to greater runtime.

---

In Figure 2c we see that across the board, as we vary the number of samples, the Subset algorithm has sigmificant advantage over the Elimination algorithm in query operations and time. Finally, Figure 2d shows that for subset size L E {2, 3, 4), the Subset algorithm experiences a significant improvement over the Elimination algorithm. But for & 5, the improvement (at least in terms of time) suddenly disappears. For this setting, that subset size requires many subsets in order to get high accuracy, leading to longer running times.
Overall, on flat distributions for a variety of parameters, our algorithm has significant benefits even over a baseline tailored for this case. The good performance of the Subset algorithm corresponds with our theory and validates the contribution of providing simple algorithm for density estimation in this hard setting.
This work was supported by the Jacobs Presidential Fellowship, the Mathworks Fellowship, the NSF TRIPODS program (award DMS-2022448) and Simons Investigator Award; also supported in part by NSF (CCF2008733) and ONR (N00014-22-1-2133) Justin Chen is supported by an NSF Graduate Research Fellowship under Grant No. 174530. Shyam Narayanan is supported by an NSF Graduate Fellowship and Google Fellowship. Anders Aamand was supported by the DFF-International Postdoc Grant 0164-00022B and by the VILLUM Foundation grants 54451 and 16582.
Acknowledgments:
References
[1] Anders Aamand, Alexandr Andoni, Justin Y Chen, Piotr Indyk, Shyam Narayanan, and Sandeep Silwal. Data structures for density estimation. In International Conference on Machine Learning. 2023.
[2] Jayadev Acharya, Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Maximum selection and sorting with adversarial comparators. The Journal of Machine Learning Research, 19(1):2427-2457, 2018.
[3] Thomas D Able and Jakob BT Knudsen. Subsets and supermajorities: Optimal hashing-basee set similarity search. In 2020 IEEE 61st Annual Symposium Foundations of Computer Science (FOCS), pages 728-739. IEEE, 2020.
[4] Maryam Aliakbarpour, Mark Bun, and Adam Smith. Hypothesis selection with memory constraints. Advances in Neural Information Processing Systems, 36, 2024.
[5] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing- based time-space trade-offs for approximate near neighbors. In Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms, pages 47-66. SIAM, 2017.
[6] Alexandr Andoni, Huy L Nguyen, Aleksandar Nikolov, llya Razenshteyn, and Erik Waingarten. Approximate near neighbors for general symmetric norms. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 902-913, 2017.
[7] Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Z Wu. Private hypothesis selection. Advances in Neural Information Processing Systems, 32, 2019.
[8] Clément Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman. The structure of optimal private tests for simple hypotheses. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 310-321, 2019.
[9] Tobias Christiani and Rasmus Pagh. Set similarity search beyond minhash. In Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, pages 1094-1107, 2017.
[10] Constantinos Daskalakis and Gautam Kamath, Faster and sample near-optimal algorithms for proper learning mixtures of gaussians. In Conference on Learning Theory, pages 1183-1213. PMLR, 2014.
[11] Lue Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer series in statistics. Springer, 2001.
10

---

[12] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-866 -64, 2019.
[13] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Conference on Learning Theory, pages 1716-1816. PMLR, 2020.
[14] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604-613, 1998.
[15] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pages
PMLR, 2020.
[16] Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh. On learning distributions from their samples. In Conference on Learning Theory, pages 1066-1 1 100. PMLR, 2015.
[17] Henry Scheffe. A Useful Convergence Theorem for Probability Distributions. The Annals of Mathematical Statistics, 18(3):434-43 438, 1947.
[18] Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. Near-optimal- sample estimators for spherical gaussian mixtures. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014.

---

A Appendix: Omitted Proofs of Section 3
Theorem 3.4 (Explicit lower bound for random GapSS instance). Consider any list-of-points data structure for solving the random GapSS (2. We) which has expected space O(kl+Pu), ), uses expected query time O (kPr-)1)), and succeeds with probability at least 0.99. Then we have the following Pu.
lower bound for sufficiently small wgi Pq 2 Wg
1-log2--000 2-1()
1+log
Proof. Our proof proceeds by explicitly calculating the lower bound given in Theorem 3.2 when w., and Wig approaches O. Recall that Theorem 3.2 states that if list-of-points data structure solves GapSS(wa: we) for k points uses expected space k2te", and has expected query time : (1))), then for every a E [0, 1], we have that
a D(TI d(tgllug) d dluullww
D(T P) d(tullwa) (1)
aP4 + +1 10-00111 -u)pu 2
inf 6(0.11
+ +11 a1 d(lulluig
uu
where P- =
Wg
0
and T
arg inf D(T(PP).
Wn Wg
1 wo
TEP B [X]
We denote the fraction the right hand side of Equation as F(lg: Our goal to provide a lower bound in the case W/a = 1/2.
1g [
First, notice that to satisfy T << P (i.e. supp(T) S supp(P)) and E X-T
[X]
the only
[..]
lg
0
available choice is T tu tt
Plugging this in and expanding Ftus ty), we get
tw tu tu + d(lull - Lu log tu wa wi We
(In (g) log
a d(tgll/og) + bg log wi
Fluu: tq)
(2)
d(Lull/ws
For W. -1/2 fixed, and for fixed Wy Or, lu 1/2, we can consider F as function of only by Because F is a continuously differentiable function in terms of by the infimum of F (for fixed Wa, Wgy Or, Lw) only be achieved either when 0F/al, ty + ).
or the boundary points (l,, 0 or
We first consider the case when the partial derivative is 0 and handle the endpoint cases later. Calculating the partial derivative of F with respect to ty gives us of to Iu-ta 8hg
log wy
log wi -4y
alog (1-tt)))
(11ww,)) When St O, we must have
La - ly
lg
bg a Ww
(3)
Wy Wy
Wl9
Plugging in the relation in 33 and wi = 5, we have
F(tus tn) + (hr bn) log we - We lu log wu
tu -ta
d((yll100) ) + by log de
we
d(t,, (ww))
tu (log lu-by log tu a +
ty log
l--6 a d(e.gll(ll))) tg log wi
tg
wo -wg
wi.
wn ww-wa
d(bu ([ww)
tu [og Lu log Lu lo weg
t.- to log ws wy
a (1 tg) log t- + (1- - a) ty log tu we
wi
d(talluu (Wa)
tu (log lu log la
- a log
1-ta I-wo
+
wa-wa
wi
(Plugging in equation 3)
d(trx (www)
1x) Lu (log (1-
log T-20q
1-ty log
I-
=a a
(Plugging in wa = }
d(t.ul1 1
12

---

By Lemma A.1 if we set = +
1 for Wy is sufficiently small, we have F( tgg 2 a log we
W/ 1-logg--a0 2-11) uniformly over overty,ty Eg. Next, let's check the boundary cases, For ig 0. Lemma A.8
proves that F(t., 0) 2 Wg 1-o(1) 2 Wy 21-1o)2-((1) For to + t because oF is continuous 8r, for 0 I tg < tu and lim of = too, the infimum of F cannot be achieved when by - tu. at, tu bto
Thus, for Wha 1/2, any fixed Wy sufficiently small, 1 logen" wig" and any fixed i. + 1/2 and the infinum of F across 0 S in < lu is at least a - Wig logog 2- o(1) where the o(1) term goes to as Wg goes uniformly across lus l-- So in fact, F(br, bn)
Wig 1- log 2-0()) uniformly across lux lg- Applying this bound back to our original inequality in gives us the desired bound.
Our goal is to now bound the fraction in the final step of the proof of Theorem 3.4 The following lemma bound this fraction.
Lemma A.1. Fix any constant 5 > 0. Suppose W1 < smaller than a sufficiently small constant
c= Cj that only depends on 8, Wy = 1/2, and 1 + log myy" Suppose these parameters satisfy the relation given in Equation 3 Then
hr (log (1 f4 + log 1-2w.)
log 1-4 I-
inf E(0.1] tw ta
W1
1 -log
d(tuul Ww)
Equivalently,
tu (log (1- :x) + log T-2mm, a log
1-te T-
inf tg El0.1] tugtn fu
2 - w
1olog 2-gg2=(()))
d(tullwa)
for sufficiently small Wa. where o(1) denotes a term that uniformly goes to 0 as Wy + (regardless of tut) tu).
In the rest of this section, we use d(1) to denote any term that goes to as Wi - 0, uniformly over ty tu- We will prove some auxiliary lemmas before proving Lemma A.I We first define the following function (x).
Definition A.2. For a value H (x) == z log (1 x)) log - x)).
is clear that (xx) only defined when 0 < a Moreover, we note the following basic property and provide its proof for completeness.
Proposition A.3. For any x E (0, 1). 2 x)² < H(x) - 16( x)².
Proof. It is simple to check that H(1/2) and (1/) Moreover, the second derivative
is H" (x) = + 2- For 0 < x < 1, x² < 1/4, so H² 2 4 for all æ. Thus,
(x) 2(--r))
Next, have that x2
16 for [1/4,3/4], which means H²(x) < 16 for x (1/4,3/4).
3
Thus, (x)) S 811 2)) for E 3/4). Since the first derivative H' (x) log(z) log(1 x)
negative for x < and positive for x > 3. this means H(x) is maximized as x approaches either
0 or 1. But the limits equal log 2, so H (xx) S log 2 for all æ. Since (2 - xx)² >
16 for all 1 >> >
or 0 < x < 1. this means for any such x, H (z) S log 2 < 16 16log2 2- ( x)² < 16. (3 -x))² So in either case, H(x) S 16( - 2
L
We are now ready to prove Lemma A.I
Proof of Lemma A. For simplicity of notation, let x fg.. Recalling the value of a, Ww. and Equation we have
1-a
x
fy = x
+
W/g
W
W
2
13

---

Now we denote the fraction in the lemma statement as b(x)/a(x) and we note
a = (tw) = tu log (2 + (1 - tu) log (2 tu))
1 + tu
loog (1 [
x
1
a log
+ log
(4)
- Wig
La
2ww
From Proposition A.4, it suffices check the following cases:
< 10100 or w.
0.99
I x < x.
2. "
Wgg or log wy
Wy < < un w..99
log wi
3. and (1 + log wiy w I x S (1 log mi )10g
In Case I, 1. is such that x E (0, x²) is the regime of æ such that a and are well defined. Proposition
A.4 further states that x² only depends Wy and x² I
Swy ww11 lol-loo 2 2-o(1) We + O.
The cases are handled in Lemmas A.5 A.6 and respectively. Combining them proves Lemma A.
Proposition A.4. Suppose that < wy <
3 and 1 x S Then, the regime of x such that a, b
are well defined x E (0,x*), where x² < 1 only depends on wa and x* I wiq Wy + O.
1--oo22-of
as
Proof. We must have that 0 < tu < 1, so that a = (t..) is well-defined. If = 0, tu = 0, and 1, then log T-mo isn't defined, isn't defined. If 1, ty is always positive, so
being well-defined is equivalent to 1 tu > O, which is equivalent to
x
1-
[ Wig
1-x>
Wig
wig
We rearrange this
1 x 1/(log wiy)
1 x
1-a
1/2 Wg
e(1/2 2 - wgy
1 -a(1 w. )a
(1 w2g) 2 2 w.)
x
W0g
We can again rearrange this as
1 C(w)) =
e(1/2 W.y)
log wa
x
w.)) (1 1 w.)
where C(w)) is positive if w.y < 1/3. This is equivalent to is equivalent to 0 < < C(m,)+1 So, we can set x² C(. Thus, a well defined if and only if x < x", where x¹ E (0, 1) clearly holds. Moreover, if Wi < 1/3, then log 1-x and log 1-2w, are well-defined, and t, > > so 1-w.
log 1- z fw I+C(w,)'
is also well-defined. In summary, a, are well defined if and only if 0 < x x²
| (log we) = 1 and 1/2 Wy = 1/2 - (11) so C(my) = (S (1 + o(1)) log (e/2)= - log wop (1=0(1)) = lo
Finally, we bound x² for wi sufficiently small. Note that (1 Wgg
=w.g
log 1o)
Thus, C(wg) 2 why
log 2000)) which means that xx S <wyg 2--lo22-of)
<x x < x² Then, Lemma A.5. Suppose that wy is sufficiently small, and 0 < x S w 1.01 or 0.99
Wig 1ogog2-00 2-o(1) as W. + 0.
Proof. Since x is strictly positive, we can write x = w/ +7 for some real y with |y] 2 0.01. Then,
1-a
wy - log ? Finally, since x = =(1) and wa = o(1), this means
= w.. so
14

---

7 - o (e-7 + 1). Since hn > 0.01, this implies that, for Wy sufficiently small, It 0.5 2 2(1). which means a = (1.)) = 2(1) by Proposition A.3
tu ===z+e->- (2 - (1)) - 0.5 . e
We can also bound as follows. Note that log (O + wg). Next, note that for Wi sufficiently small (and thus x < is also sufficiently small),
1-x 1-w./
Ox + mgy) so a log 1-
since 0 < a, 1 - < 1, - 2 0.5, and
x
2 W/g 2 3. Thus, x 2 Also, 1
" 2 x +
1 2
7 6
x. Therefore, 0 S E. S 7. which means log (1 (1- :.) - 0xr (4.). Thus,
tu (log (1- 1.
+ log (-2 )) - (t (z/tu=+ my)) 0x Thus, |6| - 0 wg).
Since a (() is positive, and b -0 Wg), this means that 2 -O + wg)) Since we know that x < x== I W1 log 201 this implies that 2 Wig 2 a
Lemma A.6. Suppose that th < x + log mi Ww, or (1
)w, < 0.99 Then,
log miy
0.99
04
Proof. We again write x = w where this time |y/ < 0.01. Since either x > (1
1 log Wiy
Wuy or
I < (1+ + Tox ) uw, this means that |y| 2 S TToR [Top
Then, we can write
(~ (w, ((0
e_>
tu = Ou + w7 (log
=0 0.90 = 2
0(7),
2
since 0.01 > h1 2 Ω log way
so the 0.99 term is negligible compared to %. So, a = H(t) =
0(>2) 2 Ω (1/( /log m.y) 2), by Proposition A.3
Next, to bound b, note that boog
= O(r + :)g) S O(wg
Also, since tu = 2 +
T-
O(w this means that L, = (1), so Ow 0.99. Overall, |b| S O(u so & z Wy 0.99-0(1)
lu log
1 - tx + log (T-bmm)) < 0(x + +wg) =
Lemma A.7. Suppose that (1 + log wn
1
yu I x I (1
Wa.. Then, 2 Wi 1001
log wy
Proof. Suppose that x = (1 + F)wg. where |3| S grained perspective.
We will look at by from a more fine
log
Note that
z
(1 + (0/1/)1(100 1/(loR wd)
= (0#00(0))) = 1
g log wi
= O
B² Ing un
Moreover,
1 Dwl
a
1
Bw,
+ ((3w)) Thus,
1-
Wig
wy
1-a
1 x
Bwg a O
g2
Wig
1 wi
log Wy
1 Weg
log w/g
Thus, we can write
Iy = Wi + Bulg + (1
3
Bwy
3²
a 0
Wg
log Wig
1 Wi
log Wig
W1
(1
g22
= 2
+ BBugggg 8.
log Wig
+
- Wg
2
Wg
+
0
log Wg
(5)
Note that f. = 1/2 0(3 (113/logur wy since the other terms in 5 are all negligible compared to 3/ log wa- which means that a = e(32 /loo )2))2) by Proposition A.3
To bound b, we will need the more fine- sieeggrained approximation of t, from (). Indeed, note that Aw,)
log
1-x log T-
1 1-m = Bw, I-
(132 and Lu (log (1 [
z + log (I-2m,,)
15

---

Note that 2wytu = 2(1/2- ( log w = Wig @ wwn/ log wy). Thus, 2wigh ( ..g). Moreover, (n.(1 2xryg) = (1). Therefore,
tu log
1-= 1o(1-2we) tu log (1+
210, Fu =x
(1
we have that
2w0g/n -
20ghu - +
tu 2wg)) ) 2wIlu I +.(
2wylu -
+ tu(1 - 2w0gg) (111-200))
ln
ta -2wg)
211y
Therefore,
8un 2wghy - x + D(33w0))
b a
1 Wy
1
2w/g
Using the more fine-grained approximation of tu we have that
2wghu x wy 2,3u wgg
1
Wig
(1 (222) (ui + BBlg)) + O(8P((()) m)g
log Wy
Wiy
(23wz - -Bwg) way
+
W/g
(1 -2wn) + 003033 w.))
log Wi
wig
30g 2wg) wgg
W/y
a1 (1 (22wg) + O(33m,))
log W4
wiq
wigB- (-1
1
Wig
(1 2w() + ((P
log Wy
Wig
= w wi/
(11 2ww) + O332wg).
where the last line uses the fact that a
1 + log So.
Bwg
b b=a 1 W1 1-o(1)
- =0(fp))==0(((um))
= =0(33w.))
1 wg
Therefore, | < Oww, (log )² S wi
Finally we check the endpoint cases of Theorem Lemma A.8. For Fl 1n) defined in Equation 2 for a 1 + log F(ln; 0) 2 a wig 1-0(1)
where (11) goes to O as Wa goes to O, uniformly over lu-
Proof. For tu 0. we can calculate that tu log 1/2-wa, tu log(2tt) - ad((t]lws,)
a log((1 - w(g) - t. log(1 2w²g
F
=0
d(tull1/2)
d(tull1/22
Let us first consider the term a log(1 wy) - tu log(1 - 2w²). If we were to set tu = 1/2, this equals
log(1 - w.) 1 log(1- -2w,)) = log(( ( 2og(1-2w;,+++ log Wn
log(1 - =
W.
(w
log wi For sufficiently small Wg. log(1 2w,)1 )l I 3wg. which means that Wi
log w
a alog(1 - ww) - bn log (1 - 2w,) = log Wog
= Ow q + |tu - 1/2) wg).
is positive, since log w. is negative. If w. is sufficiently small and [e,, 1/2 < for some sufficiently small constant c, then the term (w + |tu - 11/2|- w.) is smaller than which means log(1 w.) f. log(1 2wrg) 2 0. Because d(t..l11/2) is nonnegative, this means F 2 a 2 a Wi 1-o(1) Alternatively, if It, - 1/2] 2 Tog Tog then we still have a log(1 - w,) - tu log - 2w,,) 2 -O + 1tu - 1/2 w.) 2 - -(ww,)) and by Proposition A.3
10g Note that
Tog n.
log Wa
log Meg
2 [(1u)11/2) H (I.,) = @((u_ - 1/2)2) 2 Ω log
So, F 2 a - 0 (w, (log w,y)? )2) >
a -- Wi 1-0(1) So, in either case, we have that Fl,,,, 0) 2 a w9 depend on tu.
1-o(1) where the o(1) term does not
16

---

B Appendix: Omitted proofs of section 4
Lemma B.I. The expected space usage of Algorithm O(LÉ LK2 + nk).
Proof. The algorithm has to store each of the L sets S; which requires space O(Le). Furthermore, it needs to store the sets A, which each have expected size O(2 O(2-(k). Indeed, the probability that a random subset of size is contained in given Tj is at most 2- Finally, the algorithm needs to store the sets T3j which takes ((nk) space.
Lemma B.2. The expected query time of Algorithm 2 O(LE [1 -//2)+++
Proof. First, the algorithm forms the set Q which takes O(n/s) time. Then, the algorithm goes over the sets St until finds an i such that S; C Q. This takes time (LE). Next, the algorithm goes through the indices j E A,. For each such j. it samples the set U, one element at time checking Uj C y. Let us first bound the expected size of A,, We clearly have that i" A₁, Indeed, S; C C Ti- and A, lists all the j such that S: C Tz. Now for a E [k] with j & i", the assumption that IIp; Ps+ |1 > e, gives that IT, n T:-l I n(2 {) As the sampling of Si... St. and Q are independent, we can view S; as random size-L subset of T... particular, the probability that S; C Tī can be upper bounded by
IT (. [h.
(1/2 & (1 =1--/22)
112
and so, the expected size of |A,] is most k(1 e/2) Finally, using the assumption that I|p:- Pyll > 8 for j # i", and that n/8 >> (log k)/e², by standard concentration bound, it holds for any j * i" that IQ E Tj S (1 e/4) with high probability in k. In particular, for * i", we only expect to include (1/e) samples in U, before observing that U, $ Ty. In conclusion, the expected query time is ( m + LL+ {11 e/2)²). as desired.
Lemma B.3. Let I. C (1==2773 for sufficiently large constant C. Assume that I. = R0(1) Then Algorithmm 2 returns i" with probability at least 0.99.
Proof. It is readily checked that e (log k) = O(log n), and further, for >> 10, it holds that O logg) We record this for later use.
f= ( log k)
log #
Note that by standard concentration bounds, it holds with high probability in & that Q C Tj only for j = i". In fact, as in the previous proof, for all j * 8", IQnz, S (Q1(1-e/4) with high probability in k. In particular, this implies that the algorithm with high probability never returns a j * i Indeed,
by a union bound, the probability of this happening is at most
A: Pr(U C CT,) S k(1 - e/4) k(1 e/4) log n/= < kn C/4 -c/4 S n 110
where we used that l and n are polynomially related and C is sufficiently large. In order for the algorithm succeed, it therefore suffices to show that there exists an i [Z] such that S; C Q. In that case, the algorithm will indeed return p;- with high probability.
The expected size of Q is
n/e
B
1
(1 (1-6-2/0 2/8
2
n
2
and by a standard application of Azuma's 's inequality, it holds with high probability in n that
71 [Q|
[ -
11-e-2//- -2/0 ((n/s)0.51).
(6)
2
Note that the probability that a single set S; contained in fixed set Q is
8-1
Q -
[
II 0=0
2
(7)
n-i
17

---

Using the bounds on é in the beginning of the proof, we find that é < (((ns))0.)) In particular, conditioning on the high probability event of Equation (6), the probability in Equation is at least,
(!22)))
2/s
2/s
n1. 11..1900.51
2
for some constant c 0. The probability that no S. contained in Q most
1 (1-c (0-1112)))
2
We thus choose L result follows.
ensure that this probability is most e <1/100 and the
1-e-
We can now prove our main theorem of Section 4
Theorem 4.2. Suppose n and k are polynomially related, 8 2 2, and that s is such that 2 C Clogk for a sufficiently large constant C. Let >> O and Pu > 0 be given. There exists a data structure for the HUDE(s, E) problem using space O(k++p= + nk) and with query time O (K*
ste6(cy + n//s)
cog
Proof of Theorem 4.2 Let us pick L = knn. We further choose such that L = C (1---//- for
some sufficiently large constant C' as in Lemma B.3 In particular, l S Ps. Ig((:), so we obtain that the space bound from Lemma B.1 is O(k++p= nk). On the other hand, the bound on the query time in Lemma is22is
o J log k + (1- + +n/s n//s
=0
1 1+p log(1-og111))33 km log k + -
$)/los (1_." (..)) + n/s)
as desired. Finally, by the choice of L and f, it follows by Lemma B.3 that the algorithm returns i" with probability at least 0.99.
Note that while vastly simplified from the expression of Theorem 3.2 from 3 the expression for the query time Theorem 4.2 unwieldy. For simplified version of the theorem, one can note that
log(1 ) S e/2 and for 2 2, we have that 1-7- < 2s, resulting in the claimed bound. O
2
Remark B.4. Theorem 4.2 is stated for the promise problem of Definition 4.1 where all distributions E P with p * Pi- have Ip - Ps. 11 2 E. However, even if this condition is not met, we can still guarantee return a distribution pj such that [lp; p² S 6 with probability 0.99 and only slight increase in the query time. Indeed, as in the proof of Lemma B.3 as long as there exists an S C Q, the list A, will contain p Moreover, a Pý with lip, - P:-ll II > E. Thus it will either return p.- when it encounters it in the list A,, or distribution Pj with [p; -P:-ll < E. The only difference is that now the bound on the number of samples included in U, in Lemma B.2 becomes Ologn//s instead of O(1/e) with a corresponding blow up by log factor in the query time.
in the proof of that lemma, the algorithm will never return
C Remark about experimental setting
Remark C.I. The prior work of [1] also tested their "FastTournament" algorithm random half- uniform distributions. That algorithm works for the general problem and not just flat distributions, but its generality makes it is much less efficient for the special case we consider. From their experiments, in the setting where & = 8192, n = 500, and = 50, the best setting of parameters achieves less than 98% accuracy using more than 400000 operations (their notion of operation corresponds to querying the probability mass at specific index for two distributions while our notion of operation corresponds querying whether specific index is in the support of single distribution/sample) For a comparable setting of k = 10000, n = 500, 5 = 50, our algorithm uses fewer then 20000
'The requirement n/ss >> log k/E² is the information theoretic lower bound for the density estimation problem.
18

---

operations, more than 20x improvement. In addition to having much better query time than the general algorithm, our algorithm has subquadratic preprocessing time of O(kLe) while the tournament-basee algorithm requires O(k2n) time which is prohibitive for the parameter settings we test. For these reasons, we restrict our comparisons to our Subset algorithm and the Elimination algorithm baseline, both tailored for the half-uniform setting.
19

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
All theorem statements have full proofs.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We lay out the assumptions underlying our results and discuss our bounds in comparison to prior work in the introduction.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical claims have full proofs.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Full experimental details given in Section
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Full experimental details given in Section 5 Code is attached in the supple- mentary material.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Full experimental details given in Section
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We do not report error bars but run experiments over 100 randomly chosen queries boost significance.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Full experimental details given in Section 5 The experiments are not computa- tionally intensive for the parameter regime study.
20

---

9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/s//aacrrs..c..cpppp/aataa
Question:
Answer: [Yes]
Justification: The paper adheres to the code of ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work theoretical in nature and we do not envision any socictal impacts.
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: No new data or models were generated as part of this project.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, open-source code from 11]
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: The experimental code is a lightweight modification of an existing code base as a proof-of-concept for our simple upper bound, so we do not add extensive documentation.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects.
21


Reviews:
[{"review_id": "EG6hAjD5Xv", "reviewer": "Reviewer_yUic", "summary": "The authors study the density estimation problem, i.e., given k distributions p1,...,pk over a domain [n] and a query based on samples from a query distribution q, the goal is to output a pi close to q in the 1-norm, i.e., |q-p_i|\\le eps (realizable case). Note that usually k>>n.\nThis leads to a natural trade-off between number of samples, query time and data-structure space. Their upper bound is a modest improvement over Aamand et al. Their main result is Theorem 3.1, a lower bound for the URDE problem, based on a reduction from set similarity (Ahle and Knudson).", "questions": "see strengths above", "limitations": "Theory paper, no concerns", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(strengths and weakness) The sample complexity of the density estimation problem is important practically and thus the lower bound in the paper is of interest. The authors do a good job of illustrating the reduction from the GapSS problem (Ahle and Knudson), but at the same time they only do an okay job of illustrating the novelty of their ideas. I feel the paper would benefit from a discussion of novelty in their techniques as opposed to just a survey of known bounds. Without that it's difficult for someone like me to judge their contribution.", "weaknesses": "see strengths above", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Please see our general response discussing the novelty of our techniques above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nBIXeSAGwM", "reviewer": "Reviewer_prnQ", "summary": "This paper considers the problem of constructing a data structure for density estimation: given a set of k distributions over [n], construct a data structure. Given samples from one of the distributions, use the data structure to identify a nearby distribution quickly. There is a three-way tradeoff between the number of samples, query time, and data structure space. The goal of this paper is to rule out any algorithm that is nearly optimal along all three axes: if you only have polynomial space, any sublinear sample complexity requires near-linear query time. [For contrast, with exponential space you can get logarithmic samples + time.]", "questions": "Are there other settings where one would like to solve this problem, so knowing it's hard is useful?", "limitations": "Fine.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The lower bound is evidence against \"good\" data structures for this problem.\n * This sort of lower bound, involving all of sample complexity + query time + space complexity, is pretty new.\n * The lower bound is numerically quite tight, at least for \"half-uniform\" distributions, for o(n) samples.", "weaknesses": "* I'm not sure that NeurIPS is the best venue, this seems much more theoretical.\n * The lower bound is only for a particular kind of data structure.\n * The upper bound is just for the instances as used in the lower bound construction, and very synthetic.\n\nOverall, it seems like this paper makes some reasonable progress towards understanding the complexity of data structures for this density estimation problem. 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. \n\nThe chief argument, AFAICT, is something like: there is a line of work using density estimation to learn mixtures of Gaussians, and this paper shows limits on improving the density estimation part as a black box.  But of course mixtures of Gaussians are probably way easier than the half-uniform distributions considered here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We address your comments below.\n\n> I'm not sure that NeurIPS is the best venue, this seems much more theoretical. \n\nWe believe that NeurIPS is an appropriate venue, given that several related works (e.g., [4,7,18]) appeared in past NeurIPS conferences. \n\n>The lower bound is only for a particular kind of data structure.\n\n 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.\n\n> The upper bound is just for the instances as used in the lower bound construction, and very synthetic.\n\nOur 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).\n\n>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.\n\nThe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eqetjV5AZ0", "reviewer": "Reviewer_ZQja", "summary": "This paper considers the discrete density estimation problem supported on n points. Specifically, given a set of k discrete distributions and samples from one distribution, we would like to recover the underlying distribution. The main focus of this paper is on the interplay between sample complexity and query complexity in solving this problem. The main contribution of this paper lies in establishing a trade-off between sample complexity and query complexity based on the data structure called “list-of-point-model”. The main message is that either we need a linear sample size or we need a number of queries proportional to k. The main tool used in this paper is based on the lower bound established in Ref. [3] and the technical contribution is on solving an implicit optimization problem for their problem.", "questions": "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.\n2.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.\n3.Does the result in this paper provide evidence for row 5 in Table 1, i.e., when s is a constant?\n4. 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.", "limitations": "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. It would be great if the authors could comment more on it.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The statistical and computational trade-off result for density estimation is interesting and explains why the results in the literature are nearly the best possible. This paper also gives a matching upper bound for some special cases.", "weaknesses": "It seems that the main hardness result the paper use is GapSS, which is from [3]. The reduction part from GapSS to URDE is new, but not sure what the novelty is there. \n\nThe 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:\nl5: what does it mean “preserving polynomial data structure”? \nl38: “the data structures are subject to statistical-computational trade-offs”, it is unclear to me what it means.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We address your comments below.\n\n>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.\n\nThe 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. \n\nFrom 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.\n\n>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.\n\nWe 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. \n\nNote 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. \n\n>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.\n\nPlease 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.\n\n>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.\n\nIndeed 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. \nIn 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.\n\n>3. Does the result in this paper provide evidence for row 5 in Table 1, i.e., when s is a constant?\n\nIn 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)$. \n\n>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.\n\nHere 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SZFgxG7jx8", "reviewer": "Reviewer_b6AN", "summary": "The paper provides a lower bound, and an upper bound w.r.t the hard instances, for the problem of Density Estimation. Their lower bound is based on the ‘list-of-points’ model of computation, which captures all the upper bounds from existing results. Their bounds quantify the necessary tradeoff between sampling complexity, runtime, and space complexity. Their theoretical results are also complemented by experiments showing an improvement over previous methods.", "questions": "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)?", "limitations": "authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Significance: The paper considers the prominent problem of density estimation, which arises in various areas of machine learning. They prove a fundamental lower bound for the problem (and an upper bound for the hard instances), which paves the way for the construction of better algorithms for this problem (and for a deeper understanding of the fundamental problem). \n\nOriginality: the paper’s proof techniques are not entirely original, they start from lower bounds for set similarity from [3]. However, adapting these to their setting is non-trivial, and they have to deal with a complicated optimization problem for which closed-form solutions are not immediate, and their techniques for dealing with that seem unique. \n\nQuality and Clarity: The paper is well written and clear, and the results are tight. The theoretical results are also complemented with experiments showing significant improvement over previous methods.", "weaknesses": "I do not know of any significant weakness to point out in the work. There is always room to make the work even more clear, especially since the bounds for the different complexities are not always intuitive, so maybe more diagrams could make it more clear but they are not necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! We address your question below.\n\n>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)?\n\nThe 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.\n\n\nSamuel McCauley. Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion. ESA 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**General response: The novelty of our techniques**

Thank you for the reviews! We provide a general comment here on the novelty of our techniques and have individual rebuttals for each reviewer.

We believe that the main conceptual contribution of this paper (specifically, the lower bound part) is in connecting a problem with a **statistical/computational tradeoff** (density estimation) to a  **purely computational** problem (similarity search, or GapSS). A priori, it is not clear that these two classes of problems are connected, given that the definition of GapSS assumes that the algorithm has access to the **full query** for free, in contrast to density estimation. In fact, we are not aware of a general black box reduction between the two problems.  Fortunately, we observed that a specific class of instances used to prove lower bounds for the GapSS can be modified to be applicable to density estimation. 

Additionally, implementing this idea required a significant amount of technical development.  This is because the theorem of Ahle and Knudsen provides a lower bound for the GapSS problem via a complicated optimization problem. In particular, it does not give any explicit expression for the query time and space trade-off. One of our technical contributions is to mathematically solve this complicated optimization problem and provide an analytical expression which matches our upper bounds.

Meta-review: This paper studies and derives basic results regarding data structures for hypothesis selection. I recommend acceptance.
Decision: Accept (poster)