Density Sketches for Sampling and Estimation
Authors: Aditya Desai
Benjamin Coleman
Anshumali Shrivastava
Venue: Submitted to ICLR 2023 (2023)
Keywords: density estimation
sampling
machine learning

Abstract: There has been an exponential increase in the data generated worldwide. Insights into this data led by machine learning (ML) have given rise to exciting applications such as recommendation engines, conversational agents, and so on. Often, data for these applications is generated at a rate faster than ML pipelines can consume it. In this paper, we propose Density Sketches(DS) - a cheap and practical approach to reducing data redundancy in a streaming fashion. DS creates a succinct online summary of data distribution. While DS does not store the samples from the stream, we can sample unseen data on the fly from DS to use for downstream learning tasks. In this sense, DS can replace actual data in many machine learning pipelines analogous to generative models. Importantly, unlike generative models, which do not have statistical guarantees, the sampling distribution of DS asymptotically converges to underlying unknown density distribution.

Under review as a conference paper at ICLR 2023
DENSITY SKETCHES FOR SAMPLING AND ESTIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
There has been an exponential increase in the data generated worldwide. Insights into this data led by machine learning (ML) have given rise to exciting applica- tions such as recommendation engines, conversational agents, and so on. Often, data for these applications is generated at rate faster than ML pipelines can con- sume it. In this paper, we propose Density Sketches(DS)- a cheap and practical approach to reducing data redundancy in a streaming fashion. DS creates suc- cinct online summary of data distribution. While DS does not store the samples from the stream, we can sample unseen data on the fly from DS to use for down- stream learning tasks. In this sense, DS can replace actual data in many machine learning pipelines analogous to generative models. Importantly, unlike generative models, which do not have statistical guarantees, the sampling distribution of DS asymptotically converges to underlying unknown density distribution. Addition- ally, DS is one-pass algorithm that can be computed on data streams in compute and memory-constrained environments, including edge devices.
INTRODUCTION
With the advent of big data, the rate of data generation is exploding. For instance, Google has around 3.8 million search queries per minute, amounting to over 5 billion data points or terabytes of data generated daily. Any processing over this data, such using the training of recommendation model, would suffer from data explosion. By the time existing data is consumed, newer data is already available. In such cases, we need to discard a lot of data. One of the critical research directions is how to reduce data storage. In this paper, we present Density Sketches (DS): an efficient and online data structure for reducing redundancy in data.
Often data comes from an underlying unknown distribution, and one of the challenges in data reduc- tion is maintaining this distribution. In DS, we approximately store the data distribution in the form of a sketch. Using this DS, we can perform point-wise density estimation queries. Additionally, we can sample synthetic data from this sketch to use in downstream machine learning tasks. This paper shows that data sampled from DS asymptotically converges to the underlying unknown distribution. We can also view density sketches through the lens of coresets. Specifically, DS compressed version of grid coresets. Grid coresets are the oldest form of coresets, giving lower additive errors than modern coresets. However, grid coresets are generally prohibitive as they are exponential in dimension (d). DS enables us approximate grid coresets with the dependence of memory usage depending on the actual variety in the data instead of being exponential in d. Also, DS provides a streaming construction for this coreset.
In this paper, we focus more on the density estimation and sampling aspects of DS. Sampling from distribution described using data requires estimating the underlying distribution. Popular methods to infer the distribution and sample from it belong to the following three categories: 1. Parametric density estimation (Friedman et al.) (001) Density Estimators (KDE) (Scott 2015) 3. Learning beasd approaches such as Variational Auto En- coders (VAE), Generative Adversarial Networks (GANs), and related methods (Gooddellow et al., 2014 2016). Generally, parametric estimation is not suitable to model most real data as it can lead to significant, unavoidable bias from the choice of the model (Scott) 2015). Learning the distribution, e.g., via neural networks, is one solution to this problem. Although learning-based methods have recently found remarkable success, they do not have any theoretical guarantees for the distribution of generated samples. Histograms and KDEs, on the other hand, are thcoretically well understood. These statistical estimators of density are known to uniformly converge to the underlying true dis- tribution almost surely. This paper focuses on such estimators, which have theoretical guarantees.
-on-maramettric estimation Histograms and Kernel

---

Under review as a conference paper at ICLR 2023
Storage of histograms and sampling from them is expensive because of exponential number of partitions (also known as bins). Apart from this, histograms also suffer from the bin-edge problem: slight variation in data can lead to significant differences in the estimation of densities. KDEs are used to solve the bin-edge problem. KDE gives a smoother estimate of density. While sampling from KDE is efficient, KDE is expensive to store. KDE requires us to store the entire data. Coresets for KDE are a good solution to the storage problems of KDE. However, the construction of coresets typically quite expensive. In this work, we propose Density Sketches(DS) of density constructed in an efficient streaming manner. DS does not store actual samples of the data. But we can still efficiently produce samples from a KDE for specific kernels, which, in turn, approximates [zx) Being compressed sketch, we can tune the accuracy-storage trade-off of DS, and we analyze this trade-off in the theorem |
compressed sketch
2 PROBLEM STATEMENT AND RELATED WORK
Formally, we want to create a data structure that has the following properties : (1) It sketches density information.
Problem Statement:
(2) The sketch size is much smaller than the data size and does not scale linearly with it. (3) The construction is streaming and efficient. (4) We do not store any samples in the data structure created (for privacy reasons).
(5) We want the sampling distribution,
say fs(x), obtained by sampling from these data structures to approximate the true underlying distribution (xx).
The problem we aim to solve can be considered a data reduction problem and has been widely pur- sued in literature. The set of existing approaches can be broadly classified into two sections. (1) Sampling based / Coresets: Approaches such as clustering/imporaacee sampling (Charikar & Siminelakis 2017: Cortes & Scott 2016 Chen et al., 2012) and coresets for KDE (Phillips Tail 2020 2018) fall under this category. These approaches aim to find small set of possibly weighted samples for specific objective function such that the result obtained by applying the function to this small set is within a small approximation error of the result obtained by applying the objective function on a complete dataset. The issue with these approaches that of efficiency. Most of these the entire data. Some streaming algorithms were recently proposed for coresets for KDE (Karnin & Liberty (2019). However, even these algorithms need perform (m)) (m is compactor size) computationally expensive operations per sample for large chunks of size (m), making them unsuitable for our purposes. (2) Dimensionality reduction: These approaches aim reduce the width of the data matrix. Approaches such as Principle Com- ponent Analysis (PCA) are computationally expensive and require iterative computation over the entire dataset. Random projections an efficient streaming algorithm for dimensionality reduc- tion. However, this approach leads to compressed data that increases linearly with the original data size. As we can see, existing approaches fall short of the requirements in our problem statement.
algorithms require complicated computation
3 BACKGROUND
3.1 HISTOGRAMS AND KERNEL DENSITY ESTIMATION
Histograms and KDE (Soot 2015 Scott & Sain 2004) are popular methods to estimate the density of a distribution given a finite i...d. sample of n points in Rd drawn from the true density, say f(xx).
Histogram: Histogram divides the support S Rd of the data into multiple partitions. It then uses the counts in every partition to predict the density. fu (z), at a point æ. Formally the density predicted at the point E S is given by
C(bin(x))
fn(x)= nV((ii(z:))
where bin(z) identifies the partition of x. C(b) and V(b) measures the the number of samples in partition 6 and the volume of partition b respectively. fx) integrates to I and hence fH (x) is also an estimate the underlying density function f(x). Regular histograms use hyper-cube partitions of width B aligned with the data axes. As B increases, the bias of the estimate increases, and its variance decreases. Histograms suffer from bin-edge problems where slight change in data across the bin's edge change predictions significantly.
Kernel Density Estimation(KDE)) KDE provides a smoother estimate of f(x) which resolves the bin-edge problem of histograms. For a positive semi-definite kernel function k(x, v) Rd Rd R
2

---

Under review as a conference paper at ICLR 2023
and data, say D, the KDE at point x: is defined as
fx (x) = KDE(x) 1 k;) where 2y E D
Kernel functions are positive, symmetric, and may be normalized to integrate to 1. Gaus- sian, Epanechnikov, Uniform, (Friedman et al. (000]) are some of the most widely used kernels. A smoothing parameter B also parameterizes the kernel function and deter- mines the standard deviation parameter for the Gaussian kernel function. For uniform and Epanechnikov kernel functions, B is the window width around x where the kernel non-zero. As increases, the bias of KDE increases, and variance decreases. Histograms estimator and KDE both uniformly converge to underlying true distribution asymp- totically. However, both suffer from the curse of dimensionality. To get a decent estimate of density in high dimensions, the number of sam- ples needed is exponential in dimensions. For the density estimation task, dimensions of 4-50 are considered large. (Wang & Scou 2019)
Count Sketch
(a)
ha(a) ha(a)
Insert (a,
(0. c)
(a)]
ge (aje
kange
Repertioons
3.2 COUNT SKETCHES
Query a
C4 9 (a)A(,,
The count sketch (CS) (Cormode & Muthukr- ishman 2009; Charikar et 20002) along with its variants, one of the most popular proba- bilistic data structures used for the heavy hitter problem. Given stream of (a,, 0a) key-value pairs, a Ud CS stores the compressed total counts for each of the keys in a small K x R array of integers and can be queried to retrieve this total count, C(ag). CS offers a probabilistic solution memory logarithmic in total number of unique keys. There is standard memory accuracy trade-off for CS. Let m be the number of distinct keys and C be the vector of counts indexed by each key. For count median sketch (Charikar et al.. (002). the 5c, guarantee P [a(a C(a)] > c/|C]|2) S 8 is achieved using O (log m + log (4))) space. [Chkrabbti] 2020). As seen from the above equation, the approximation accuracy for particular || Clll- Specifically, CS can give an excellent approximation for keys with the highest values in setting where most other keys have very low values. More discussion on CS can be found in Appendix F.
<(a)
median (cI, 02, ca)
Figure 1: Countsketch, sketching, and query
key depends on how it compares to the
3.3 LOCALITY SENSITIVE HASHING
Locality-sensitive hashing(I (LSH) et al. 2005 is popular approach to solving approximate
near-neighhor problems. If function : 27 fo...r - 1} for some r, is randomly drawn from the L.H family L, the probability of collision of the hash values for two distinct elements aj and 02 is
Prec(h(a))=n((0)) x Sim(a1,
Where Sim(a1, a2) is some similarity metric corresponding to the LSH family. The probability of collision is referred to as the kernel of the LSH family, generally denoted by (l...). Most ker- nels are positive, bounded, symmetric, and reflective. We can use p independent LSH functions, hr, h2.p...p to obtain a LSH function, (a) = (a), hn. o(,, ... We call p the power of the LSH function. Popular LSH functions for U = Rd are L2-LSH, LI-LSH and SRP (signed random projection). More details on LSH functions
The function (x()) has
kernel (6,-),
can be found in (Darrell al. 2005)
3.4
UNIFORM SAMPLING FROM CONVEX POLYTOPES
Uniform sampling from convex spaces is a well-studied problem (éllisle et al. 1993 Chen et al., 2017). For general convex polytopes, this is achieved by finding point inside the polytope using convex feasibility algorithms and then running an MCMC walk inside the polytope to generate a point with uniform probability. In the case of regular convex polytopes like hypercubes and paral- lelopiped, uniform sampling is much simpler. Sampling a data point at random in d-dimensional hypercube of width 1 is equivalent uniformly sampling real values in the interval [0. 1]. For sampling within d-dimensional parallelopiped, we first locate (d - 1) -dimennionnal hyperplane par- allel to each face at a distance drawn uniformly from [0, B] where B the width of parallelopiped in that direction. The sampled point is the intersection of these (d - ---dinensional hyperplanes.
3

---

Under review as a conference paper at ICLR 2023
Table I: bin(x) for different partitioning schemes
Partitioning Scheme
Parameters
bin(z): Rt N
Sampling E R² from b E N
Ti ~ (0, 1).r Rt
Regular histogram
B
bin(x); [x4/B]
8 B(b+r)
F1 (0, 1), E R
Aligned histogram
B Rd
bin(x)) = [x,/B,]
B (6 (6+ r)
W Raxd B R E Rd
~ (0, 1). r R
LI/L2-LSH
bin(æ); = (L(z, W;) 4)/BBJ
y B (b- +)
solve Ws
MCMC with constraints,
SRP
We E Rexd
bin(z), = (sign((z, W))
sign( ((2, W.) = b, bounding box
DENSITY SKETCHES
In DS, we aim to build compressed non-parametric estimation object in an efficient streaming fashion. As KDEs give better approximation of underlying function f((x) than histograms, want to build DS as a compressed KDE object. To achieve this, we use nice connection between KDE and Histograms with an LSH-based partition function.
4.1 HISTOGRAM WITH LSH-BASED PARTITION AND KERNEL DENSITY ESTIMATES
Any LSH function on Rd will partition the space into different bins. Specifically, if power L./L22- LSH, these partitions will be polytopes in R Similarly, power k SRP would give conical partitions with pyper-plane boundaries. We can employ a histogram-
estimation strategy on the top of these randomly drawn partitions. The density estimate using such histogram would be
I(x; bin(x)) where x; D (1( Σ
where a indicator function. This estimate the density has an expected value (over random partitions) equal to the KDE estimate, say fo(z) with the corresponding LSH kernel, o(...)
Ep(fn(x))
P(ac E bin(x))
(0 x) fs(
The expectation over random partitions. This connection between randomized histograms and KDE was first observed in (Coleman & Shrivastava (2220). To better approximate KDE, we can combine results from multiple histograms with independent LSH functions. For example, if we use m independent histograms, say H1, H1.,... Hm, then the density estimate can be written
m
f(an) (x)= - (m.(x) m
We can sample data point from this set by first choosing histogram randomly and then sampling point from that histogram. One can check that the sampling distribution, thus obtained. is 2(m) (I)).
4.2 CONSTRUCTING DENSITY SKETCHES
Now that have reduced the problem of KDE approximation to histograms, we will now show how to obtain compressed representation of a histogram in streaming fashion. We also show how to generate samples from this representation. First, let us establish some notation we will use
Notation: (1) Data D consists of n i.i.d samples of dimension d drawn from true distribution f(x): C Rd + R. (2) bin(x)): ID of the partition in which point falls. the case of p-power LSH functions, bin(x:) Rd + No, and each bin can be identified with unique tuple of p integers. In a regular histogram, we have a tuple of dl integers. For example, in regular histogram with width B, bin(x), [J. bin is generally parameterised with bandwidth parameter B which measures the size of the partition. Some partitioning schemes and sampling algorithms are mentioned in Table I (3) A CS M with range R and repetitions K described in section 3. (4) H: Augmented min-heap of size used with M. Hence for a given partitioning scheme (bin, B), DS is parameterized by (K, R. H) and includes two data structures M(K, R) and H(H).
4

---

Under review as a conference paper at ICLR 2023
Count Sketch M
Heap R
X,
pantioon1a 22:11
count
X1
(x(
((8(x))
nB82
Panga
(2.6)
(1.1)
251
Area
Racettins
fs(x) 2(biaa) (](C((=)))
X1
C(Bie))
Figure 2: Overview of the sketching algorithm
The histogram has exponential (in d) number of partitions. Hence, in high dimensions, it is impractical to store histograms. However, most high dimensional real data is clustered and thus has highly sparse histograms. This does not help with histograms, post-pruning of histograms still requires us to build and enumerate them. Nevertheless, the sparsity in histogram makes a good candidate for heavy hitter problems. We CS, M, store compressed version of the histogram. Unfortunately, sampling with just M does not have an efficient solution. We maintain set of heavy partitions for sampling in the min-heap H. We will discuss sampling in later subsections.
sketching M As shown in figure and algorithm [ we process the data in a streaming fashion. For each data point, say æ, we find the partition inserting (b, 1) into M. Along with each insertion, we also update H. If the H. is not at its capacity, we insert this b into the heap along with its updated count C(b). If the heap is at its capacity, we check updated count against the minimum of the H. b's count is greater, we pop the minimum element from the heap and insert (b, C(b)).
bin(x). We increment the count of b by by
4.3 fc(x): ESTIMATE OF DENSITY AT A POINT
We can use M for querying the density estimate at a particular point. The algorithm for querying is presented in Algorithm 2 and is explained in figure Reusing notation from [3.1] the density predicted by the histogram C(bin(x)), we would use its estimate from M. Let this estimate be C(bin(x)). Then can write the density predicted using count-sketch as fc(x)
be written as (z). When using the sketch, instead of actual
C(bin(x)) fn(x)) nV(bin(z))
fc(x) ((bin(x)) (b)nn)))))
We know from CS literature that C(bin(x)) is closely distributed around C(bin(x)) and so we can expect fc()) to be close to I' and hence to f(x)). Note that though fc:(2: is good estimate of density at point the function fo(-) is not density function as it does not integrate 1.
4.4
fz():: ESTIMATE OF DENSITY FUNCTION
To obtain density function from the sketches, we have to normalize the function fo(x) over the support. We can write (x) as
((x)) fa(x) = [((z)dr (bin())) E Everins(s C(b)
(xx)
C(xx (bin (x))
fa(x) & C(x)
It is easy to check the integral can be written as the sum over all the bins in the support. As is clear from the equations for (z) and fc(xx, n Σ (b) C(b). is replaced by ñ = Ebebias(s) C(b) to get a density function. We can check that á is an estimate of n using an estimate of count for each bin from the DS.
4.5
[z): SAMPLING FROM DENSITY SKETCHES
M is a good enough representation for querying the density at a point. However, it is not the best data structure generate samples efficiently. One naive way of sampling from these sketches is to
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Constructing density sketch of (x)
Algorithm 2: query fo(y), y R
Result: (v(
E Rd
Result: Density Sketch (DS)
b = biny
f(z): : Rd + R: : true distribution
MMquurr(b) return (c/(nV(b)))
F1,... Fa ~ f(r): sample drawn from fa)
bin(x): : 5
No partition function
Algorithm 3: sample y Rd such
M: CS with range R, repetitions
y fs(x)
H(H): min-heap store top H partitions
Result: y: sample from fs(y)
for i 1 to do b = bina; M. M.insert(b, 1)
P categorical distribution over bins s.t.
P(b) (H/b)/m if E H
P(b) 0 H
c = (bquery(b)
~ P y UniformRandomPiin((()
H. H.update(b,
return y
randomly select point in support of f(x) and then do rejection sampling using estimate fc(x). However, given the enormous volume of support in high dimensions, this method bound to be immensely inefficient. Another way is to choose partition with probability proportional to the count of elements that partition and then sample a random point from this chosen partition. is easy to check that the probability of sampling point æ in this manner, precisely, is (x) if we use exact counts and (x) if we use approximate counts from CS. However, given that number of bins exponential in dimension, sampling bin proportional to its counts requires prohibitive memory and computation. This is why we needed CS in the first place. Here, we further approximate the distribution by storing only top H partitions which contain most data points and discarding other partitions. As mentioned in [ we can efficiently maintain top H partitions with augmented heap H. We then sample a partition present in this heap with probability proportional to its count and sample a random data point from this partition (Algorithm 3). The probability of sampling data point whose bin not present augmented heap is then zero. The distribution of this sampling algorithm is,
((bin(x))
fs(x) = [(bi((x)) e H) (bin(())
where ân = EbEN C(b) is the count-sketch estimate the total number of elements captured in all partitions present the heap. I(.) is the indicator function with values or evaluating the boolean statement inside it. Let Ph. n.g ft be the capture ratio of heap. It is easy to see that as the capture ratio tends to 1, (I) tends to (x). Note that fx( is density function.
ANALYSIS
Histogram and Kernel Density Estimators are well-studied non-parametric estimators of density. Both of these estimators are shown to be capable of approximating large class of functions (Scotl 2015). For example, with the condition of Lipschitz Continuity on f(x), we can prove that point- wise MSE(f=(z) converges to 0 at rate of On -2/3). Better results can be obtained for functions that have continuous derivatives. In our analysis, we make assumptions along those made in (Scotl 2015); specifically, the existence and boundedness of all dunction-dependeds terms that appear in the theorems below. We refer the reader to (Scoti 2015) for an in-depth discussion on assumptions.
We restrict our analysis to convergence in probability for all the estimators discussed in this paper, which the standard (Scoti 2015). this section, we consider the regular histogram partitioning scheme and show that our sampling distribution fs(x) is an approximation of underlying distribution f()) and converge to it. However, similar analysis holds even for random partitioning schemes / KDE and is skipped here.
Mean integrated square error(MISE): MISE of estimator of function is widely used tool to analyze the performance of a density estimator.
MISE(f) = E [((()) 1(:))

---

Under review as a conference paper at ICLR 2023
A density estimator, with MISE asymptotically tending zero, is consistent estimator of true density and converges to it probability. We would use this tool to make statements about the convergence of our estimators. By Fubini's theorem, MISE is equal to IMSE (Integrated mean square error).
MISE(f) IMSE(f) - - dr
We now present our main result of the paper,
Theorem 1 (Main Theorem: (x) to f(x) The probability density function of sampling, fs(x), using a DS over regular histogram of width B. with parametersl K, H) created with n i.i.d samples from original density function f(xx), has an IMSE given by
IMSE(fs(1)) I 11((1-M)) - ph)² +3(1 + 2c)
nBdd + 9(f)
+0
(
Knap - KRnBé
11
Bed ((IV + 3E 1 (9(2(() + BVa
[ (f())VV1I1))
+ +3(1+ + 3c)
JES
with probability (1 (1- where == is the estimated capture ratio as described in section 4.5 and ((g) is roughness defined as ggz))2 du
Roop Z Onap is the number of non-empty bins histogram,
The dependence of IMSE on properties of f(z), such as roughness, standard Scott 2015 and cannot be avoided.
Interpretation The estimator (z) of f(x) is obtained by series of approximations from f(x) (x) + fc(x) - (z) - (x)). Hence to interpret this result, we break down the result above into multiple theorems enabling the reader easily notice which step of approximations leads to what terms in the theorem above. We provide these details in Appendix. We notice a few things from the theorem below
Similar to the standard analysis for histograms, the curse of dimensionality also manifests in theorem. B should go to zero and should increase faster than the rate which Bd Ba/nnsp decreases (condition 1). As compared to standard histograms, this requires n to grow faster. With these conditions B and n, it is clear how the second and third terms go zero.
The magnitude of the fourth term is controlled via e. The above statement is true for any 8 and e that are related via the expression 5 (Tmssp(e"'n.t RR). Choose arbitrarily small and 6, and
achieve it with large enough n n./naz by providing more intermediate resources and making K R large enough. For a fixed resource K Rt this term goes to zero asymptotically with n growing faster than Thap,, which
sub-condition of condition 1.
The term 12(1 - Pa)2 shows the effect of truncation that occurs due to using only heavy partitions. As can be seen, this term is data dependent, and IMSE does not depend directly on H (number of partitions) but Ph- Suppose the term adds no penalty to IMSE. H, via Ph. controls the accuracy-memory trade-off of DS.
capture the entire data in the heap (i.e., setting H=nazp), then
DISCUSSION
curse of dimensionality: As DS built over Histograms, they inherit the curse from Histograms: i.c. the number of samples needed increases exponentially with dimension. With increased data collection, the issue of the unavailability of large amounts of data is fast vanishing. We want to emphasize that DS' advantages are best seen when data is humongous. DS can absorb tons of data and give better density estimates and samples without increasing memory usage. Also, most real data in high dimensions is clustered or stays on a now-dimensional manifold. DS, throw away empty bins, and only store the histogram's 's populated bins. DS can deal with the curse of dimensionality better than Histograms. DS original data space: Some data types, like images, do not reside in a space where the usual distances or cosine similarities imply conceptual similarity. On these data types, DS will not perform well. One way is to learn a transformation and create sketches of the transformed data. While this will give better performance in practice, we might lose theoretical guarantees for certain transformations.
EXPERIMENTS
Visualization samples from density sketches: In the first set of experiments, we provide a sanity check for DS in the form of visualization of data generated from DS. (1) In the first experiment,
7

---

Under review as a conference paper at ICLR 2023
(a) sample drawn from true distribution
(b) sample drawn from Density Sketch
0
/:
2
3
4
5
6
7
8 9
(
2
3
4
5
6
7 1 7
8 5 8
9 9 9
0
1
2
3
4
5
6
7
3
4
6
0
2
MNIST Sample from Density Sketch using con- (c) MNIST Sample from Density Sketch using L2. ical partitions (multiple signed random projections LSH partitioning width: 0.01,0.1,1,10 from top to (SRP)). The rows have varying number of SRPs used bottom
increasing from top to hottom
Figure 4: Visualization of samples drawn from Density Sketch, (a-b) DS captures density infor- mation. (c) Higher power LSH functions lead to fine DS behaving like random sample (d) Coarser partitions lead to samples that resemble "avg" of samples in data
figure (a) shows the samples drawn from the actual multi-gaussian distribution, whereas figure (b) shows the samples drawn from the DS built the samples from the true distribution. In this experiment, we use L.2-LSH partitions with B=0.25, K=3, R=50000, and H=3000. As can be seen, the two samples are indistinguishable. So DS does capture the density information. (2) Figure (c) shows some samples drawn from DS built over the MNIST dataset (Chang & Lin 2011 T) with varying bin-width sizes. (again R=50000, K=3 and H=5000). We should notice that MNIST with 784 dimensions and 60K samples is not an ideal dataset for DS. In fact, with L2-LSH partitions the data would be so scattered that every sample is contained in its bin. we make the bin-width finer, we should sample data points very close to the random sample from the original data. So in the worst conditions, DS converges to a random sample which we know a good representation of data, (d) shows results again with MNIST. However, here we have created conical partitions (created using multiple signed random projections). While L2-LSH partitions use power 784 L22LSH functions, in this experiment,
smaller number of SRP functions( 10-25, increases in the image), thus promoting clustering. As expected, this coarse partitioning does show significant clustering; hence, the images drawn from the partitions look like the average of multiple samples from the original data. The results support that DS can create samples that resemble the original data.
go to lower rows
Evaluation of Samples on Classification Tasks:
For most datasets, is not possible to inspect samples visually. Hence we evaluate the quality of samples from DS by using them train classi- fication models. In these experiments, the data loader of the training algorithm is replaced with a sampler from DS. This sampler returns training batch when requested by the algorithm. All the experiments are performed on Tesla P-100 GPUs with 16GB memory.
Datasets: We choose big datasets from the liblinear website (Chang Lin 2011), which satisfy the constraints of 1) data dimension less than 100 and 2) the number of samples per class greater than 1,000,000. Large Datasets the main application domain for DS. Thus, we have datasets Higgs (10M samples, 28 dimensions) and Susy (5M samples, 18 dimensions) for our experiments.
Baselines: For baselines, we consider random samples of the same size and Liberty coresets pro- posed by (Karnin & Liberty 2019) to compare DS performance. For Liberty coresets, we m 100 as for larger m the process is very slow. Dimensionality reduction via random projections another streaming algorithm. Still, in these datasets, cannot get significant compression using
8

---

Under review as a conference paper at ICLR 2023
0.70
orgginei densily sketch coreset random sample
0.725
0.80
ACqURO
0.700
Test Leos
0.85
Test Accurary
0.79
0.575
0.60
0.78
0.650
ortginal]2.5GB] ty
ariginaljo.aGG
0.77
rendom sample
liberty coreset
0.55
0.76-
liberty coreset
0. 500
random sample
density sketch
0.50
0.75
20
60 Merrory (MI)
40
80
100
20
40
60
00
100
Memory (MU)
Merorry (MU)
(a) higgs test accuracy
(b) higgs test loss
(c) susy test accuracy
onginai(o. (GB)
higga
higga
0.55
random sample
liberiy
Hope Test Rocuracy
8.7400
Accusccy
1113
S099 Test (occuuu
7ett Loss
donsity skotcch
1133
0.50
13330
Haga Test
2281
233229
0.45
8.7300
C120
1.29
0.40
Memory (MB)
(e) varying K.R, with KR=1000000
(1) varying B
(d) susy test loss
Figure 5: (a-d) Performance of density sketches, Liberty coresets and random sample on downstream classification task. The bar widths refer to 2 x std. DS performs consistently better all memory sizes (e) Performance of DS is stable with K,R configs for decent budget KR=1000000, (f) Optimal exists for DS performance. larger and smaller values of lead to performance degradation
dimensionality reduction (it can be dx at best, where d is the dimension). So we cannot compare against this method. For a more detailed discussion on baselines, refer to appendix D.
Results: The DS has parameters: partition dunction(bandwide
B). We use L2-LSH partitions, sketch parameters K, R. and heap parameter H in all our experiments. The memory of the DS used for sampling is affected by only the heap parameter (see appendix FF for details on memory (=00=225000,HH1000000
and vary B. It is clear from the figure that B=0.001 works best for these datasets. Lower and higher values of affect the performance adversely. Larger B implies that we will capture more space than needed in a single partition, and smaller B implies that we will capture lesser data in the heap. So it is expected that a sweet spot for B exists. In figure (je), we fix (B=0.01, 1- 1000000 KR=1000000) and vary K from to 64. We can see that for a reasonable memory budget the results are stable with varying K. For the experiments in figure aa-dd we fix (B=0.01, K=5, R=250000) and vary H. This gives DS of different sizes. We plot test accuracy and losses for DS, random samples and Liberty coresets for different sizes of memory used. The width of the band signifies the 2 x std-dev of performance three independent runs. As can be seen, for the "Higgs" dataset, the model's 's accuracy achieved on original data of size 2.5GB can be closely reached by using a DS of size 50MB. So we get around 50x compression We see similar results for datasets of "Susy" (100x compression, 0.8GB) as well. The results show that DS is much more informative than Random Sample and Liberty Core- sets. For more details on running the experiments (data processing, memory measurements, etc.), refer to Appendix F.
computation). In figure ft), we use the config
Estimation of statistical properties of dataset: We also perform the experiments on the covariance estimation task. The observations are similar to the classification experiment. DS performs better than the corresponding random sample. The results are presented in Appendix F for the shortage of space.
CONCLUSION
In this paper, we talk about Density Sketches, a streaming algorithm to construct a summary of den- sity distribution from data. We show that new samples generated from this sketch asymptotically converge to the underlying distribution. Thus, DS comes with theoretical guarantees. Additionally, the cheap nature of online updates in Density Sketches, makes it an attractive alternative to con- structing coresets for the data. In terms of coresets, DS can be viewed as a compressed form of randomized grid-coresets one of the oldest forms of coresets.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Dimitris Achlioptas. Database-friendle random projections: Johmson-lindenstraus with binary coins. Journal of computer and System Sciences, 66(4):671-687, 2003.
Claude JP Bélisle, Edwin Romeijn, and Robert L Smith. Hit-and-run algorithms for generating multivariate distributions. Mathematics of Operations Research, (8(2):255-266 1993.
Amit Chakrabati. https://www.cs. https///www.ss.ddrrtmuuu....... www.moutt..hhuueee edu/~ac/ volume 1. 2020.
Teach/data streams-leenotes
Chih-Chung Chang and Chih-Jen Lin. Libsvm library for support vector machines. In Software
available at attp://www.ciie.ttu.ee edw.tw/wwwwwww////... cjlin/libsvm. ACM Transactions on Intelligent Systems and Technology, 2011.
Moses Charikar and Paris Siminelakis. Hashing-basee estimmasts for kernel density in high dimen- sions. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp- 1032-1043. IEEE, 2017.
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Aulomata, Languages, and Programming, pp. 693-703. Springer, 2002.
Yuansi Chen, Raaz Dwivedi, Martin J Wainwright, and Bin Yu. Vaidya walk: A sampling algorithm based on the volumetric barrier. 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1220-1227. IEEE, 2017.
Yutian Chen, Max Welling, and Alex Smola. Super-samples from kernel herding, arXiv preprint 1234::1203.347,, 2012.
Benjamin Coleman and Anshumali Shrivastava. Sub-linear race sketches for approximate kernel density estimation on streaming data. In Proceedings of The Web Conference 2020, pp. 1739- 1749, 2020.
Graham Cormode and M Muthukrishnan. Count-min sketch., 2009.
Efren Cruz Cortes and Clayton Scott. Sparse approximation of a kernel mean. IEEE Transactions on Signal Processing, 65(5):1310-1333, 2016.
Trevor Darrell, Piotr Indyk, and Gregory Shakhnarovich. Nearest-neighbor Methods in Learning and Vision: Theory and Practice. MIT Press, 2005.
Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning. volume 1. Springer series in statistics New York, 2001.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint 140.v:1406.2661 2014.
Zohar Karnin and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. In Confer- ence on Learning Theory, pp. 1975-1993. PMLR, 2019.
Jeff M Phillips and Wai Ming Tai. Improved coresets for kernel density estimates. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2718-2727. SIAM, 2018.
Jeff M Phillips and Wai Ming Tai. Near-optimal coresets of kernel density estimates. Discrete & Computational Geometry, 63(4))867-887 2020.
David W Scott. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons, 2015.
10

---

Under review as a conference paper at ICLR 2023
DW Scott and SR Sain. Multi-dimensional density estimation handbook of statisties vol 23 data mining and computational statistics ed er rao and ej wegman, 2004.
Zhipeng Wang and David W Scott. Nonparametric density estimation for high-dimensional data-algorithms and applications. Wiley Interdisciplinary Reviews: Computational Statistics, 11(4):1166, 2019.

---

Under review as a conference paper at ICLR 2023
Table 2
Notation
Description
f(x)
true density distribution
(x:
histogram estimate of f(x)
bin a
partition id of point
(in
enumerates all bins in the support S
C(b)
count of elements in the bin id 6
C(x)
count of elements in the bin(x)
C(b)
estimate count of elements in the bin id 6
V(b)
volume of bin i
D
data
k())
kernel function R x R +
B
B E R, scalar bin width
B Rd vector of bin widths in different directions
h(x)
4 1] hash function
g(z)
u u- (-1++1,11] hash function
W WED Rexd
weight matrix for SRP/L1-L2 LSH indicator function
I
E
Expected value
fo(x)
KDE estimate with kernel ø
M
Count sketch
K. R
parameters of count sketch
7
total number elements
CS estimate of total number of elements
number of elements in the heap
CS estimate number elements in the heap
Ph
capture ratio defined by n
A APPENDIX
A.1
NOTATION
A.2
THEOREM 2: fu TO f
While estimating true distribution f(x) Rd + R, the integrated mean square error (IMSE) for the estimator (x) using regular histogram with width h and number of samples n, is
9(
h2d
IMSE(
nhd n
4
Specifically, we have integrated variance (IV) and integrated square bias (ISB) as follows
IV(fu) 1
nhd + g( 1
+o
n
n
and
ISB(fn) < led 4 G(IV)(12)
where (()) is the roughness of the function o defined as G(Ø) = f 0² (x)dzz
Proof. Let x E S where S is the support of the distribution. Let bin(x) determine the bin of point .r Din enumerate all the bins that lie inside the support S of the distribution f(x) Let V ((bin(z) (z)) is volume of bin in which x lies. Equivalently, we can also use Vbb) to denote volume of bin b. For standard histogram, (b) hd
fu(x) =V((bi((z))
1
Σ I(x; E bin(x))
(1)
12

---

Under review as a conference paper at ICLR 2023
First let consider the integrated variance.
/
Var Var(fu(z))d = E
f Var(f (x))
IV
(2)
bEbins(S) JEb
ZES
For particular bin b, the variance is constant at all values of inside it. Also for particular æ in bin 6, we can write the following for Var(fu (z)) using independence of samples.
Var(fu(x)) nV((bi(z))2 Var(I(z;; bin(x:)
(3)
Also Var(I(x; 6)) po(1 pb) where ps is the probability of æ; lying in bin b. That is, Pb = Sacs f())dx
Using this in equation 2
1 V(b)
I
E
(V) po(1 pb)
(Ebins(S)
Simplifying.
IV Σ
(b) pb(1 pb)
(5)
(Ebimx(S)
For standard histogram V(b) is same across bins,
IV 1
Σ pb
Σ
pb)
(6)
nV
bEbins(S)
bebins(S) (S)
pt)
(7)
nV
(Ebins(S)
Using mean value theorem, can write, pb V(b)f(Eb) for some point &
Σ
p
Σ
V(b) Σ v(b)((E))
(8)
bEbins
bEbina
bEbine
Using Riemann Integral approximation, we can write the following as the bin size reduces,
Σ v(b)(())) J (xx)dx++ + o(1)
JUES
bEbina
SaeS (x))d is also known as the roughness the function. Let us denote it using G()). Hence
IV nV (b) (1 (bb) (9(f) + o()))
(10)
IV 1 g(f)
(11)
nV(b)
n
Putting Vbb = hd
G(
IV
(12)
nhd
71
Keeping only the leading the above expression.
IV = O
(13)
nhd
Now let us look at the ISB for this estimator, ISB( (x))
ISB(fn(x)) = /
(B(fn(t)-f(())224
(14)
ZES
13

---

Under review as a conference paper at ICLR 2023
Let us look at the expected value of the estimator,
[(f((=)) V(bin(a)) Jreninton f(I)dt
1
(15)
Recall that x E Rd. Using 2nd order multivariate taylor series expansion of this f(t) around z, we
get,
f(1) = f(x) (t x, Vf())) + ( x)) " (([(=))(( x)
(16)
Here H()(I) is the hessian of at Without the loss of generality let look at the bin(x) = [0 that is the bin at the origin. Let us say it is bo
J
f(t)dt = f(x) + 101 Vf(x)) +
(17)
LEDO
Using eq 17 in eq 15, we get
[(fn(x))= = f(x) + (12 x), Vf(x)) 0(h
(18)
Hence, just keeping the leading term, we have
Bias(fn(x)) = 11 - x)) Vf(x))
(19)
Now,
f rebo
[i (x:)) de [ ((0- - x xx) V((w)) 2
dr
(20)
Ixb
Using Schwarz inequality, we get
f Jeb
Bi (x) (x))
/
x) -
11 2/
V (x)))
(21)
IZEb
As is a mid point of the bin. The max norm of x - h/2 can be d/2
f Bi S hdd
[v](>)
(22)
J
Now looking at ISB
12d
ISB(fn)=
Σ
Bias (z)) S
[|Vf(z)
(23)
4 JOes
bEbins mebo
12d G(l vfl22)
ISB(fn) S 4
(24)
A.3 THEOREM 3:
fc TO fH
While estimating true distribution f(x): Rd + R, the integrated mean square error (IMSE) for the estimator fc(x) using regular histogram with width h, number of samples and countsketch with range R, repetitions K and mean recovery,
IMSE(fe) IMSE(fH) + Trap
K K'nhhd where nhap is the number of non-zero partitions. Specifically, we have
IV(fc) = IV(fm) +
Thzp KRnhd
and
ISB ISB(fe) = ISB(fn)
where uaap is the number of non-zero bins/partitions.
n
14

---

Under review as a conference paper at ICLR 2023
Proof. Consider Countsketch with range R. and just repetition (i.e. K 1). Let it be
parameterized by the randomly drawn hash functions bins(S) - {0, 2,.,, R - 1] and
(Sn + + (-1,+11, Let C(bin(z)) E (I(z; e bin(æ)) is the count of elements that lie inside the bin(x)
The estimate of density point then be written
fc(x) (bi((i())) C(bin(x)) + Σ I as $ bin(x) A g(bin(x:)) = g(bin(z))) (((lz))))>(bi((aaaaa ((bin(z)))s
(25)
We can rewrite this as
fc(x)= = fx(x)) nV (bin(a))
Σ
I as & bin(x) A (bbn((z))) g(bin(z))) (bbin(z)))
(26)
As E(s(b)) 0, it can be clearly seen that.
(fo(x))=B(fHH))
(27)
Hence, it follows that
ISB(fo(*)) = ISB(f=(z))
(28)
It can be checked that each of the terms in the summation for right hand side of equation innnuluiing the terms (x) are independent each other i.e. covariance between them is zero. Hence can write the variance of our estimator as,
Var(fo(x)) Var(fu
(29)
n n(2((i))())) Var (I(z, $ bin(z) g(bim():))=((bin()))) (bnn:// ((bin(z;))s(bin(())
(30)
Var(fo(z)) Var(f
(31)
n nV2((ii(x:)) ((xs & bin(x) ((bin(::))=g((bi((()
(32)
As square of indicator is just the indicator,
Var(fo(=)) (x))
(33)
[ (I(x: (xx & bin(x) ^ ((bin(z:))=<(bbn(()))
(34)
nV2((bn(xx))
Var(fe(x) = (a)(fn + (binn))())) (1 Poin(w) R
(35)
Hence, IV is
- IV(fm())) [ (bi((ii(z))) (1 --Poin(a)) }
(36)
Iv(fe())) -(f(()))-(((f(()))))))))))))))))
Ix))
bebins(S) Jeb nV2(() pb) +
Σ
(37)
Iv(fo(z)) (x) +
nV(b) (1 pb)
(38)
R
(Ebins(S)
15

---

Under review as a conference paper at ICLR 2023
Assuming standard partitions. V(b) h for all b
1 (nnpp" 1)
IV(fc())) (V(fn())) + nhd R
(39)
With mean recovery, with K repetitions, the analysis can be easily extended to get IV as
1 (Nnzp 1)
+ nhd KR
(40)
The ISB remains same in this case.
A.4 THEOREM 4: fč TO fc
While estimating true distribution f(z) Rd + R. the IMSE for the estimator (z) using reg- ular histogram with width h and number of samples n and countsketch with parameters (Rrange, K reepetitions) related to the estimator fc(x as follows
IMSE(fc(z)) <(N 2M) & IMSE(f?(z) & IMSE(fo(x)) + c(N 2M)
Specifically,
[V(c(()) - M < ISB(fc()) - NN < ISB(f(())) < +eN
+2M
and
where
M < (v((f(=)) 2(9(f) + h2d
((I hva / (f())lVf1l))
JZES
= = (1+ ISB(fc(=)))
with probability (1 11-6) 5) where 8 PnKR
Proof. Let look the estimator
fā(x) = ((bin(x))
Sc(x) n v(bin(x)) E, C(b)
(41)
where á = C(b) and n = C()( C(b)
and its relation to n:
Let us first analyse and how related
Σ
c(b)
Σ
Σ
[(xx E) (I(e, A g(bin((;)) -- ((i))s((ii((z)))s(())
bEbins(S) SS)
(Ebins(S)
(42)
I(e E) + I(x; bbbg (bbn(((()))) = ((i)))(( b,
(43)
Note that E(A) = n. For varaince, observe that most of the terms in the summation have covariance O, except the terms Cov(I(x; bı),I(æ; b2)) which are negatively correlated. Hence
Var(ñ)= Σ
Var(I(a; b)) Var(I(a; b g(bin(x:)) ((b))s((im(z)))s())))
(44)
Σ
Coo(I(x, e 6,), e b2))
i,b b2
We know that
Var(I(x; E b)) = po(1 pb)
Var(I(x; $ bb (bbi((x))) g(6))s((in(()))s(() E(I(x; (bgg:. g(ggii(n()))) s(6)))) 1- pb
Cou(I(a; bb), I(x; E b2)) Pb,
16

---

Under review as a conference paper at ICLR 2023
Hence, we pluggin in the values in previous equation,
Var(f) Σ po(l - Pb) + n
Σ
1
pb
2n
Σ
Pb,bbz Pbs
(45)
R
h
h
b1 dy bb
Var(i) = n11 Σ
pb) + 1
1 pb
2n
Σ
pby PbiPos
(46)
R
b
b
b1 ,b
Var(i)= = n((1+ (11+)
Σ
1 Pb
p6
2n
Σ
pb Pb, }
(47)
R
b
by d
Var(f)) = n((1 +
Σ
pb
}b} }
(48)
R
Var(f)) n 1
1- pb
(49)
R
Var(n)- nnmmmap - 1)
n n(nnap)
(50)
R
R
Using Chebyshev's inequality, we have
(fr
P(ln n| > cn) 5
(51)
n
Onzp
P(Ln - n| > en)
(52)
2nR
Anse Hence with probability (1- (1-5). = anit
á is within e multiplicative error.
relation of pointwise Bias and ISB
With probability 1-8,
fc(x) 1+6
S fō(x)= S fc(x)
(53)
1-6
As expectations respect inequalities
E(fe(x)) S F(f((z)) < E(fo(1))
(54)
1tc
1-c
E(fo(x)) [(x) S Bias(sz(r)) S E(fe(e)) f(x)
(55)
1+6 Bias (c(s(fc(())) ((()
1-6
< Bias( < Bias( + (x)
(56)
l Bias(fo(x)) - ef(z)
1-c
1+E < Bias( < Bias(fc(x)) + (x)
(57)
1-6
Integrating expressions again respects inequalities
- $ISB(((()) < TSB(fc(x))+ + f(x)
(58)
1+6
1 1-6
ISB(fc(x)) - < (I)(((())) ISB(fo(x))+ +c
(59)
1te
1-c
Using first order taylor expansion of i+c and ignore square terms
(1 ( - <
(1 (1+0)SB()C +
(60)
(61)
Hence,
ISB(fo(z)) eN < (sB(it(()) (IB(((())))) +eN
(62)
where
N (1 ISB(fc())))
17

---

Under review as a conference paper at ICLR 2023
Point wise variance and IV
Using the similar arguments
F(f((a)) (f((())) (1 c)²
S <Va((f((=)) V F((((z)) FF(o(a))
(63)
(1-
(1 c)² (1+c)²
Again making first order taylor expansions of denominator and ignoring square terms
(64)
Since, Since, Varffcl))-22oorrddc))2226616))1) <vr((((()))))))
Van (65)
/ E²(fc(1))
TV(CC())-2(((((((()))))))) JES
JES
(66)
Let us now figure out the Jaes (f(f(())
[ JES
(fc((()) / (f(((())
(67)
JOES
From equation 18, ((fn(=)))) f(z)² + (1() - -), Vf(x)))) + z), Vf(x))
/ JES
(((n(())) S 9()+ + 1idd
((1V/112) + lVa (((x)|V/lI2>
(68)
FES
Hence,
IV(fo(=)) 2cM & IV(f)(z)) +
(69)
Where
1dd M < (V((f(()) +
4 C(V))))) + +Ava /
(f()))
(70)
DES
A.5 LEMMA
Estimators fs(x) and fz))., obtained from the Density Sketch with parameters(R, using his- togram of width h built over i.i.d samples drawn from true distribution have relation
/ [ - fs(x)) 2(1 - ph))
where Ph the capture ratio as defined in section
/ |Isc(o) fs(x))de=
Σ
1fz(2) fs(x))dr
(71)
biins Jeb
Σ Σ/ bebsne(H)
/ (f((()) - fs(x))dr+
f E1ee Jee
Σ
(f)(()) f fs)
JaE
bebins(H)
(72)
we know that for x E b, & bins(H), fs(x)= 0. Hence,
[ -s(())/dr==
Σ
f 15z(x) fs(x))dx +
Σ
/
Po(2))a (73)
bebins(H) JEE
bebins(H) JuEB
18

---

Under review as a conference paper at ICLR 2023
JaeE fe(r)dr is the probability of data point lying in that bucket according to (x(
- / | -1/c(0) fs(t)/de= Σ / ff(())
Σ
(74)
bEbino(H) J06
(b
For points x E bb, E (in)(H), fo(x)) * [s(x) rin Hence, fs(x)=
fx(r)
/ (8((()) - fs(())do==
E bebino(H) wEb
fc(1) á
1)dx +
Σ bbbins(H)
cs
(75)
n
ñ
[1(c(0) - f((t)dd fs(x))de== E
c
(
1)dx +
(76)
bEbina( Hy web
(
P
f /18210)- (ocke)-s(tee fs(x))de= =
nt
cb
1)
(77)
1hpp
bEbina(() (H)
bebinn HF)
|18((0) |152(0) - -fs(x))do=
ft
1ih
nt
7
1)(
(78)
7iA
/ |V((CE) - fss(x)lda = (11 ni
+
(79)
n
/ (i(())-s(s))) =2(1
T2p
(80)
/ [ fs(x))dx (f(()))s(=))dds =2(1- ph))
(81)
A.6 THEOREM 5
The IMSE of estimator fz) obtained from the Density Sketch with parameters(R,K..)) using histogram of width h built over n i.i.d samples drawn from true distribution f(x) is
IMSE(fs(=) < 12(1 pm)) +3IM)E(((()))
where Ph is the capture ratio as defined in
Proof. Giving very loose relation between fs and f. We can write
J (fs(x) (is(z)-f(x))) f())) = (Ifs(0) -((())
f(x))
(82)
f (fsslo) [c 53 / /(fs(o) fo(z)) + (10(0)- ((x))))))x))))a
(83)
[Ustee f(x)) I 3( // - fa())) +3 /fíc(0) - f(x))
(84)
[ [(stE) f(x))) de S 12(1 pm)² 3 (f((x) fz
(85)
IMSE - MISE(fs()) < 12 pa +3MMS(((())
(86)
n
19

---

Under review as a conference paper at ICLR 2023
B THEOREM 1 (MAIN THEOREM) COMBINES ALL OTHER THEOREMS
This theorem directly relates the distribution fs(x) to the true distribution f(x). We will combine the following statements
9()) + 4 ((VV)
h2d
IMSE(fH) S nha 72
(87)
IMSE(fo(z)) (f + Bnap K Rnnh
(88)
IMSE(fC(z) - IMSE(fc(z)] S c(N + 2M) with probability (1-5),8- IMSE(fs) & 12(1 Phh)2 3IMSE(f((=))
Rnzz
(89)
enR
(90)
where,
M & + 12d (((V)) + +hva / (f(x)|
2EES
= (1 ISB(fc(z))
Let us now combine them
IMSE(fs(z) < 12(1 pm.) 3IMSE(f2(())
(91)
IMSE(fs(x)) S 12(1 - pmh) + 3 ( 2M)
(92)
IMSE((s(z) 12(1 ph) +3 [MMSE(M))
Bnap
K Runha + c(N + 2M)
(93)
IMSE(fs()) & 12(1 Ph_
nhd + 9(f)
+o
+ ((Ivfll))) + anep + <(N + 2M)
h2dd
4
KRnh
(94)
N = (1 11++150 ISB(fe))
12d
N N g(lV))l2)
12dd
M S IV( 2g(f) ((I + PAH (+(=)||V11b)
4
S3
M < (f
+
Knap
+g(()) + hdd
G(IV))l))) + bAvt (f(=)]
K Runha
4
WES
M <
1
G(f)
+0
1
Knap - K Rnhd
+g(() + hdd
4 ((11/11)) + AVV /
(f(x)||/111)
nhd
12
IMSE(fs(x)) 12(1 ph)
+3 nhd n
((f) +
+ ((IVFll2))
hdd
+ Ouzp K.nndd
4
1 h2d ((]VS11))
3e
2 ((1V/11)) 2
g(f)
1
aazp
+ 2g( + Rdd
((IV)1)))
-hvll)))-a////a / ((()))\VVll)))d
n
11
K Rnhdd
20

---

Under review as a conference paper at ICLR 2023
IMSE(fs(*) S12(1 - ph))++
3(1 2c)( nha
+ 9()
+ +o )
Dnap
)
KRnh
n
n
11dd
3(1 + 36) 4 -((VV
3e(1 + 2g() + hvd / ((())|IV/1a)
ZES
C OTHER BASE LINES
Coresets: We considered a comparison with sophisticated data summaries such as coresets. Briefly, coreset is a collection of (possibly weighted) points that can be used estimate functions over the dataset. To use coresets to generate a synthetic dataset, we would need to estimate the KDE. Unfortunately, coresets for the KDE suffer from practical issues such as large memory cost to construct the point set. Despite recent progress toward coresets in the streaming environment & Tai 2020), coresets remain difficult to implement for real-world KDE problems CCharikar & Siminelakis (2017).
Clustering and Importance Sampling: Another reasonable strategy is to represent the dataset as a collection of weighted cluster centers, which may be used to compute the KDE and sample synthetic points. Unfortunately, algorithms such as k-means clustering are inappropriate for large streaming datasets and do not have the same mergeability properties niques are unlikely to substantially improve over random sampling when the samples is spread sufficiently well over the support of the distribution. An alternative approach is select points from the dataset based on importance sampling Charikar & Siminelakis (2017), geometric prop- erties Cortes & Scott (2016), and other sampling techniques [Chen al. (2012). However, recent experiments show that for many real-world datasets, random samples have competitive performance when compared to point sets obtained via importance sampling and cluster-based approaches Cole- man & Shrivastava (2020).
sketch. Furthermore, such tech-
Dimensionality Reduction: One can also apply sketching algorithms compress a dataset by re- ducing the dimension of each data point via feature hashing, random projections or similar meth- ods Achhiiotps (2003). However, this is unlikely to perform well in our evaluation since our datasets are already relatively low-dimensional. Such algorithms also fail to address the streaming setting, where N can grow very large, because the size of the compressed representation linear in N. Finally, most dimensionality reduction algorithms do not easily permit the generation of more syn- thetic data in the original metric space.
D DIFFERENTIALLY PRIVATE DENSITY SKETCHES
In order to make the density sketch differentially private, we add noise to the distribution stored by density sketch. This is achieved by adding noise to the underlying count sketch array (K x R matrix of integers). Let the function mapping histogram of the data to the density sketch (before the heap construction) be denoted as | - ZKR where X is the set of all partitions. We fill first define an discrete analog of laplacian noise.
Definition (Double geometric distribution). The double geometric distribution parameterized by p E (0.1) 1) is defined follows the support of all integers.
1 1_ 1)
P(zlp)
-
(95)
Algorithm to make Density Sketches private: Each cell of sketch (K x R) matrix added an i..d noise drawn from the double geometric distribution. We will prove that this noise addition makes the function M = f + noise differentially private. Heap construction can considered as an post processing operation the density sketch matrix. Hence, the sampling distribution is then
21

---

Under review as a conference paper at ICLR 2023
differentially private. (Note that heap construction algorithm also needs be modified in practical settings to ensure that it carries the differential privacy properties. But this is achievable)
Theorem (Differential privacy). The density sketches constructed with addition of double geomet- ric noise with p 1 e-e where K is the number of repetitions in the sketch is (c. 0) differentially private.
Proof. Consider the 11 metric for computing the distance between datasets. Consider any arbitrary pair x.y which satisfy (e-yy11z = 1. In the histogram view of data, it is easy to check that distance of 1 can exist if and only if there an additional row in either x' or y and all other data points are same. Without loss of generality we can write x y U {d} where d is the extra data point. As the constructed count sketch does not depend on the order of insertion, we can say that count sketch for i.e. f(x), is obtained from count sketch for by sketching additional data point into it. Also, because of countsketch's 's mergeable property, we can write f(z) = f(y) + f((d)). Hence [f) - f() = [[f(d)) ][1- As sketching a single entry changes exactly element of each row of countsketch by 1. [If(()) = K. Hence sensitivity of the function f is A =
We use the double geometric distribution defined above for noise.
1
P(=lp) = 2- (1- (1-))
(96)
Now Let us consider the privacy achieved with this error. Let M be the final randomized algorithm with computation of and adding noise. We are interested in the following quantity with x.y such that || 1111 1.
P(M(x) = 2) IPM((()); = 21) P(M(y) =) ILP(((y): = 24)
II.(1 p) (1(())))1
11,(1 - ((l1-p)
= (1, -10
= (1 - -10-11111111-11--110-----------
As 11 11-norm is distance metric write
P(M(x)= (0(())=2) 2)
= (1 (10-)))000----1-11160------0----
P(M = 2)
2 (1 -(0
(1 p) AI)
If we put p = -</A(())
P(M(x) = 2)
20
P(M(y) 2)
P(M()) = 2)
P(M(x)= = Se
(97)
Hence M(x) is (e, 0)- differentially private. Hence have that the countsketch produced by the sketching algorithm with added double geometric noise is (c, 0)- differentially private when we have p p= p
why heaps are differentially private? If the data is bounded in Red (d is the dimension of the data), then it is easy to check that there is a cell in Rd, which contains all the data, It follows that the number of partitions inside this cell is finite. So we can consider heap construction as iteratively going through each partition and noting down its count. Once we do that, we sort all the partitions according to the counts and keep top H elements. In this sense, we can consider heap construction as post processing over count sketch. From the proposition 2.1 [Dwork, Roth), we know that post processing maintains differential privacy. Hence the heap we create is (e, 0) differentially private
22


Reviews:
[{"review_id": "nYTb-eEmkD", "reviewer": "Reviewer_jjJ4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper constructs a data structure, dubbed density sketch, that represents a density on a high-dimensional space. This data structure is constructed online, in a streaming fashion from data samples assumed drawn i.i.d. from a true density. The representation is capable of evaluating the density at specific points as well as of sampling points. The paper also provides analysis of the approximation level of this representation in MISE distance and illustrates its applicability via some experiments.", "summary_of_the_review": "The paper puts together various data reduction techniques in an intuitive manner to offer a novel density representation that can be constructed in a streaming fashion. This appears to lead to low space and time complexity, but ideally that analysis should also be part of the paper. The main result requires a bit of clarification, to make sure that the approximation ability of this representation is indeed there. What hampers the paper most is unpolished typesetting and language. With some clarification and polish, the paper may be worth sharing with the community.", "strength_and_weaknesses": "### Strengths\n\n* Reducing the overhead of data by representing it accurately in compressed form continues to be a timely topic. \n\n* The construction of the density sketch data structure is intuitive and the compression and accuracy levels achieved in experiments seem very promising. \n\n### Weaknesses\n\n* The paper is typographically in a very rough form. Many mathematical expressions are not placed in math style and there are typesetting errors in those in math style (e.g., hat symbols appearing in the wrong places) that make expressions hard to parse. There are also many linguistic issues, some of which are listed under minor comments. The paper needs a serious polish revision to become of publication quality.\n\n* The main theorem (Theorem 1) is not presented cleanly. Here are some issues:\n    * The parentheses are all the same size, making it hard to parse what goes where. This is an easy fix, with the exception that there seems to be an extra right parenthesis in the very end, which could change the meaning of the expression if it is associated with a left parenthesis somewhere.\n    * Perhaps a related issue to the above, but as written the right-hand side does *not* vanish, even if both $1/nB^d$ and $B^2d$ vanish. That’s because the last parenthesis block which starts with $3\\epsilon(1+2\\mathcal{G}(f)+\\cdots)$ is not affected by either of these. This could be an issue of misplaced parentheses. However, as far as I can tell from the proof (which I have only skimmed through), that term is there.\n\n* The reasons the last point necessitates a clarification is because it makes the conclusions from the Theorem a bit more subtle. In particular, it would seem that we can make $\\delta$ a constant, which implies that $\\epsilon$ vanishes, so this term would vanish. However, if I understand it correctly from the proof, the equation is only valid if $\\delta$ is small for a fixed $\\epsilon$. Therefore we cannot change the order of quantifiers, and that reasoning does not work. I welcome engaging with the authors to clarify this point, as going through the proof to reach the conclusion myself is a bit daunting.\n\n* The paper would benefit from a clear characterization of the worst-case space and time complexity of the method, since lower complexity is one of the selling points. \n\n### Questions\n\n* In Figure 1, what is $g_i(a)$?\n* In SRP, are the volumes of all partitions equal? You assume that throughout, but perhaps that only works for LSH?\n* I don’t think you mean multinomial distribution in Algorithm 3, you instead mean a categorical distribution over the bins.\n\n\n\n### Typos and suggestions\n\n(p.1) include edge > including edge\n(p.2) in the section 2 > in this section. ; function f(x) > function $f(x)$\n(p.3) place $\\hat$ symbols correctly; define $\\mathcal{C}$ as the count vector\n(p.4)\n* Your use of $i$ is too overloaded, you use it to index: data points, coordinates, and LSH/SRP weights. It would be more legible if each of theses uses had its own letter.\n* In Table 1:\n   * for LSH and SRP in the bin column, there shouldn’t be a subscript on $x$\n   * typeset the $w_1$ vector and $W$ vector in math mode\n   * remove trailing parenthesis after $U[0,1]$\n* point x > point $x$\n(p.5) a efficient > an efficient; in the figure > in Figure; fix all the $\\hat$ locations (last mention, this has to be fixed everywhere in the paper); remove trailing parenthesis from $\\hat \\mathcal{C}(x)$\n(p.6) in Algorithm 1, fix the partition function line; in Algorithm 3, remove trailing parenthesis from UniformRandomPoint(b); point x > point $x$; close parenthesis after MSE\n(p.7) add = between IMSE and MISE\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "av4fNQ3KPl", "reviewer": "Reviewer_Kdqf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes an approach to estimate the data distribution. For high-dimensional spaces, the traditional histogram-based algorithm and KDE methods require #data exponential in the dimension. The paper proposes Density Sketch (DS) which uses particular data structure Count Sketch (CS) to reduce the memory consumption of histogram-based methods. Moreover, the paper proposes to use a min-heap for efficient sampling from the estimated distribution. ", "summary_of_the_review": "While the paper is well-organized, it is very hard to read due to so many notation problems and typos. Here are my questions:\n\n1. In many places in the paper, what is the dot . in the denominator of $\\hat f_H$? (i.e., the $n.V(B(x))$)\n\n2. What is $\\hat C(x)$ in Section 4.4? What is the difference between Section 4.3 and 4.4? I don't understand why we don't just use $\\hat f^*_C(x)$ for estimating the density. As stated in the paper, $\\hat f_C(x)$ is not normalized ...\n\n3. In Section 5, what is the probability space of the $E$ in MISE? And what is exactly IMSE? Is there a typo in the second equation in page 7? What is the randomness in Theorem 1 (\"with probability ($1-\\delta$)\"). The argument in the analysis is that `if MISE -> 0, then $\\hat f$ converge to $f$ in probability'. Does the randomness affect this result or not?\n\n4. The author should give more background on L1/L2 LSH in the maintext as they are mentioned a lot later. \n\n5. There are many notation problems in the paper. For example, in Section 4.2 when introducing notations, what is $f(x): S \\subset R^d \\rightarrow R$ intend to tell us? My guess is $S$ a Borel set, but not sure .... Also, the author simply writes $p$ for p as well as many other symbols in many places in the paper. The author seems submitted this work in a rush and there are even paragraphs without period. \n\n6. While the author claims that DS has advantages for high-dimensional spaces, it seems that the evaluations are still performed on datasets with dimensions $<100$. \n\nI suggest the author do a thorough proofreading of the paper to improve the paper's readability and clarity. ", "strength_and_weaknesses": "The method is simple and seems effective from the empirical evaluation. The paper is well-organized and easy to follow. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L8XE4BWmMW", "reviewer": "Reviewer_VE18", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper presents density sketches, which is a cheap and practical way to reduce data in a streaming setting., DS can keep a succint representation of data and can sample unseen data on the fly from this succint represesentation. This is done by reducing KDE into a problem related to histograms. The integrated mean squared error is analyzed. Experimental analysis is perofmred on small scale datasets.", "summary_of_the_review": "NIce algorithmic contributions to density estimation literature. But, these approaches will not sale to larger dimensionality, Euliean data. ", "strength_and_weaknesses": "Pros: Interesting algorithmic ideas that work for low-dimensional, Euclidean data.\nCons: Most modern ML problems are high-dimensional problems that do not involve Euclidean data. In such cases density estimation is done via powerful parametric models. For problems which have a Euclidean structure, density estimation procedures cannot scale beyond a few dimensions. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject