Euclidean distance compression via deep random features
Authors: Brett Leroux
Luis Rademacher
Venue: NeurIPS 2024 poster (2024)
Keywords: dimensionality reduction
random projection
random features
metric embedding
Primary area: learning_theory
TL;DR: We construct random nonlinear maps (as compositions of several random features maps) that compress point sets while maintaining information about approximate distances between points.

Abstract: Motivated by the problem of compressing point sets into as few bits as possible while maintaining information about approximate distances between points, we construct random nonlinear maps $\varphi_\ell$ that compress point sets in the following way. For a point set $S$, the map $\varphi_\ell:\mathbb{R}^d \to N^{-1/2}\{-1,1\}^N$ has the property that storing  $\varphi_\ell(S)$ (a sketch of $S$) allows one to report squared distances between points up to some  multiplicative  $(1\pm \epsilon)$ error with high probability.  The maps $\varphi_\ell$ are the $\ell$-fold composition of a certain type of random feature mapping. 

Compared to existing techniques, our maps offer several advantages. The standard method for compressing point sets by random mappings relies on the Johnson-Lindenstrauss lemma and involves compressing point sets with a random linear map. The main advantage of our maps $\varphi_\ell$ over random linear maps is that ours map point sets directly into the discrete cube $N^{-1/2}\{-1,1\}^N$ and so there is no additional step needed to convert the sketch to bits. For some range of parameters, our maps $\varphi_\ell$ produce sketches using fewer bits of storage space. We validate the method with experiments, including an application to nearest neighbor search.

A corollary of the above lemma is that if an arbitrary set of n points in g is mapped by the random projection matrix R. to R$ where & ( 2 logg n)), then the squared distances between pairs of points are distorted by a factor of at most (1 with high probability. The projected points are thus Euclidean distance compression via deep random features
Brett Leroux Department of Mathematics University of California, Davis Davis, CA 95616 lerouxbew@gmail.c. com
Luis Rademacher Department of Mathematics University of California, Davis
Davis, CA 95616 1rademacQucdavvss.co edu
Abstract
Motivated by the problem of compressing point sets into as few bits as possible while maintaining information about approximate distances between points, we construct random nonlinear maps &e that compress point sets in the following way. For a point set S, the map : R + N 1-1/2(-1,1)" has the property that storing (S) sketch of S) allows one to report squared distances between points up to some multiplicative (1 + <) error with high probability. The maps y are the ê-fold composition of certain type of random feature mapping.
Compared existing techniques, our maps offer several advantages. The standard method for compressing point sets by random mappings relies on the Johnson- Lindenstrauss lemma and involves compressing point sets with a random linear map. The main advantage of our maps ip over random linear maps is that ours map point sets directly into the discrete cube N (11/2(-1,1) 1) and so there is no additional step needed to convert the sketch to bits. For some range of parameters, our maps şe: produce sketches using fewer bits of storage space. We validate the method with experiments, including an application nearest neighbor search.
Introduction
Random projection is a commonly used method to lower the dimension of a set of points while maintaining important properties of the data [30]. The random projection method involves mapping high high-dimensional set of points in Rd lower dimensional subspace by some random projection matrix in such a way that the pairwise distances and inner products between points are approximately preserved. The random projection method has many applications to data analysis and variety of prominent algorithms [11, 17, 5, 8] including nearest neighbor search [13, 12].
The theoretical foundation of random projection is the Johnson-LLnndenstenn that a random orthogonal projection to lower dimensional subspace has the property of preserving pairwise distances and inner products take the projection matrix to be a matrix with i.i.d. Gaussian N (0, 1) entries.
lemma which states
[16]. Later it was observed [9, 13] that one can alternatively
Lemma ([9, 13, 30)). Let each entry of an d x matrix R be chosen independently from N N 1). IP [| || 2 e|]u|l?) < 2e 22-
Let 0 J RT u for E Rd. Then for any
a lower dimensional representation of the original point set and this lowering of the dimension offers two main advantages. The first is that algorithms that were originally intended to be performed on the original point set can instead be performed on the lower dimensional points.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The second main advantage of the lower dimensional representation is reduction in the cost of data storage. The Johnson-Lindenstinn a data structure (called a sketch) that can be used to report the squared distances between pairs of points up to a multiplicative (1 <) error. The size of the sketch of course depends on both |S] and From this viewpoint, it is natural to ask what is the minimum number of bits of such a sketch? The Johnson-Lindenstrauus lemma gives an upper bound on the size of such a sketch as follows: Any set of n points can be projected to R where k =
lemma shows that random projection of point set S produces
while distorting pairwise squared distances by factor of at most (1 + t). The projected data points are real-valued, and thus the projected data points needs to be encoded into bits in such a way that guarantees squared distances are preserved. One way to convert to bits is to use an epsilon-net for the unit ball in Rº In order to preserve squared distances up to multiplicative e1 error, it suffices to preserve squared distances up to an additive m²c error where m is the minimum distance between pairs of points in S. By identifying each projected point with the closest point in an m²c-net, we can produce sketch with 6 nee 2 log n log (1/m²e) bits.'
While the Johnson-Linneenstran the points to a lower dimensional space with a random linear mapping (the projection), it natural to ask if there are other types of random maps (in particular, possibly nonlinear maps) which are able to produce sketches with a smaller number of bits. Our main result shows that this is possible in certain cases by using the composition of random feature maps. We state main result first for sets of points contained in the unit sphere 5 and at the end of this section we include the extension to subsets of the unit ball.
lemma shows that efficient sketches can be obtained by mapping
Theorem 2. Lel S
5t-1 with |S] n 2 2. Let m = minn 1| yll and = [oog log2 =1 m 2 1. Lete > O and assume that 6 < minz.yes. 1- (10, Then the random
map Pe : Sd + JN [-1,1] with N = e (Loga (log in 1 (1) v2) (defined in the proof of Theorem and independent of except through parameters n, d. m and z. 1 Kr. y) satisfies the following with probability at least (1 2)²: (p((S) is a sketch of S that allows one to recover all squared distances between pairs of points in S up to a multiplicative (1 + c) error. The number of bits of the sketch is O log
(log 1/, [=2log2(7//2))
The proof of Theorem 2 is explained in Section 3 and the final details of the proof are in Appendix A. We explain how the map şe is constructed in the next subsection and the role of the parameter é is discussed in Section 1.2. The main advantage of the map ( is that it maps the point set S directly into the discrete cube and thus there is no need to convert the sketch to bits after performing the random mapping. Furthermore, the map foe produces sketches with asymptotically fewer bits than those obtained using the LindesnnLindesstrauss lemma if (log( ) (0///(1//22) = o(log( m)))).
This is equivalent to the condition that (log( 1 ))2 long(a// /2) o(log()))
Furthermore, the sketch (S) has the desired properties "with high probability". The probability that the sketch succeeds is (1 - 2/n1) and we claim that this quantity approaches one for all useful choices of the parameters: First of all, we recall that in all applications of Theorem 2, we should take = M(d). We also take
(2(d-1/2) (ignoring logarithmic factors) because otherwise the target dimension N is larger than dl and then a sketch based on an e-net (as above, but without random projection) for S would be better, by having bitlength nd (up to logarithmic factors). The assumption that < 1 (z. أ for all x. V. x * means that < m² and so 1/m- < <1/1 = O(d//4). This
means that e = Ologg loga d) and so (1 2//n = 22(1 2/d) approaches one.
1- Ka, y) for all x, E S, x * y by the weaker assumption that < 1 - (z. y) = 1 | y/1². The reason that an assumption of this sort is necessary is that, because we are trying produce sketches which allow recovery of squared distances, pairs of points with very small distance are difficult to deal with. As result, need to assume for technical reasons that the accuracy parameter is smaller then (half) the minimum squared distance, i.c. e < 1 - (z, y). There is an inherent symmetry in the maps fo that we use which makes it convenient to use the stronger assumption that e < 1 ((x g)
We remark that it might be possible to replace the assumption in Theorem 2 that
'innc the points are in the unit ball, for any 8 > 0, approximating distances to within additive crror 8/6 gives approximation of squared distances to within additive error d. So the size of the epsilon net is, up to constant, (L/m² e)= logn This gives @(log(1 L /mm mm²)e =)² log n) bits per point

---

We are able to extend our main result to deal with not only sets of points contained in the unit sphere, but also any set of points in the unit ball. For a point x in the unit ball 8d we use & to denote z/ |2]||
Theorem 3. Let S C Bdd with |S| = n 2 2 and set minses ||=||? Let m
l
all and & = [log, log2 m 2 L. Let > O and assume that < min NEIL 1- (@, D3 Then the random map &pe : 5d-1 / (-1,1) with N e (Lgg" (log 1) 2220 (defined the proof Theorem 5 and independent S except through parameters n,,, m and mina.yes.. 1- (2, 9) ) satisfies the following with probability at least (1 11--,, f);: (p((S) and the norm of each point in S up to an additive =pm2 error is sketch of S that allows one to recover all squared distances between pairs of points in S up to a multiplicative (1 error. Moreover the number of
bits of the sketch is O alogg (log 1 (1ogg(7/VV)) + +n +n pm
The proof of Theorem 2 is explained in Section 3 and the final details of the proof are in Appendix A. The number of bits of the sketches in the above theorem depend on the parameter m which is the minimum distance between pairs of points after all points have been normalized to have unit norm. Thus, it is more complicated to compare the number of bits of our sketches to the sketches obtained using the Linisoon-nnddsstruuss lemma because the Soasson-indenstrauss sketches do not rely on any normalization step. However, in the case of point sets on Sd-1, there is a large family of point sets in Bd for which our sketching technique produces sketches with a fewer number of bits.
1.1 The maps yp and the recovery of | - - by (p((a) and (pr(y)
In this section we summarize the construction of the maps set which are used in Theorem 2 and formally analyzed in Theorem 5 and how they can be used to recover squared distances between arcsin(t) and g(t) sin( mf). So So [-1,1] + [-1, 1] is the inverse of points. Let (() --1, I]. For E N+ + let fe be the function f composed with itself & times and similar
g:
for ge- Notice that for any E N+ fe [-1,1] [-1, is the inverse of ge [-1, 1] + [-1,
For simplicity in the rest of the introduction we assume all points are normalized to be on the unit sphere 5d-1 We define the sign function as
{-,
1 if 0
sign(()
if < 0.
The maps ype will be defined as the composition of maps of the following form. Set D E N+. Let Z, 1 < i S D be i.idd. standard Gaussian random vectors in Rd. Let pD RR. - RR. be defined by
Px)) = D-1/2 sign( (z, 2,))
where (xr); is the ith coordinate of (x.).
The maps ipe are now defined as the é-fold composition of maps of the type pp, That is, for some integers D,, D2....... Dr, we let 10 5 - 1/2 (11,) be defined by sp ( = 40 (r)). For j E {l....,( E 13, we let (z)1(x)= = (z))),, Therefore, the map (Pt maps S to D-1/22 D. 1/2 [11, P),, To avoid writing the double subscript we write the final dimension of the map as
Dj = N. We remark that the map S can also be defined as a standard neural network with é hidden layers using activation function sign(() and having all weights be i.i.d. standard Gaussian random variables.
It was shown in [26] that for I, Sd-1, E sign ((x, Z1)) sign( (y, Zi) f((z, v)). Since (ip (x), yp (x)) is a sum of D independent copies of D sign( (a, 2)) sign( (y, Z)) we get that Bly D (x), x (v)) = v))
Now we can explain how one recovers pairwise distances between points in from (S)) Let S be a set of n points in gd-1 c: Rdd As in Theorem 2, we map S by fer Sd-1 + N - 1 Here l is some parameter which is chosen based on S that is explained below and N is chosen based on the desired e error of the sketch. If the remaining integers Dı,..., Di-1 are chosen properly,
We remark that the map 6 is often referred to random feature map, see 128, 7, 7.26.
3

---

then we show that (pp(ar), pz(v)) is good approximation of fe((x, v)) (Corollary 4), Since is the inverse of ft this implies that ge((pr(=)), (pr(y)) should be good approximation of v). By the polarization identity, this implies that 2 2grl (fr((r) (v)))) should be a good approximation of | - yll². So recovering || - yll² from (p)(S) simply involves calculating (g))())())) (e (e()))) In the next section we explain why this mapping and recovery scheme leads to good error guarantees.
1.2 Intuition behind the construction
Now that we have defined the maps (o we can explain the idea behind using maps of this form. The reason why this type of map is useful has to do with the behavior of the derivative of the function gr near As previously mentioned, the map ype has the property that for all x, y S,
((pe(x)) - fe((x, v\)l < 8
(I)
for some depending on N. Now when we want to recover || - y/1² based on (r(x)) and (e(y), by
as estimate of ||ær yll The additive error of the approximation of || - y/ by 2 2gr (1r( (p()))) depends on the error in Eq. (I) as well as the derivative of gr. near the point (ar, v)). The function de has the property that its derivative approaches zero as & approaches one and so the additive error of the approximation of ||æc - y/l by 2 2ge (x)( (pe()))) gets smaller the closer fe((z, y)) (and thus (I, y)) is to one, i... the closer | y/ is to zero. (This is quantified in Theorem 6, specifically the exponent approaching 2 in the additive error) The effect that this has is that actually approximate || - y/l up to a multiplicative error.
the polarization identity, we use 2 - (vpr(((()) (p(()))
The role of the parameter l in this construction is in controlling the rate at which (t()) approaches zero as / approaches one. If there are pairs x, such that || - yl|² is very small then we need the derivative to approach zero very quickly. This can be done by increasing the parameter E; the rate at which 9 approaches zero is faster for larger values of & (see Theorem 7 in Appendix B). It turns out that the correct choice of é [log, log, r where r is approximately the reciprocal of the minimum distance between pairs of points in S (see Theorem 2). Because of the connection with standard neural networks with hidden layers mentioned in Section 1.1, we refer to the parameter l as the number of layers of the random mapping.
We remark that the function (t) has the property that its derivative can be large as (5) when I is near zero (see Lemma 8 in Appendix B). The effect that this has is that our algorithm leads to worse approximation of || - y when (ir, y) is close zero if é is large. However, this loss in accuracy is made up for by increasing N by only a relatively small amount and the gain in accuracy when (Ir y) close to one outweighs the loss in accuracy when (I, y) is close zero
1.3 Previous variations on random projection
Our compression method is similar to random projection in that they both involve compressing a set of points by randomly mapping it to a lower dimensional space. A number of other papers have also suggested variations on random projection where a different random mapping is used. In some, the random mapping is still linear. In others, they use linear mapping followed by some quantization step. The main difference in our method is that it is more fundamentally non-linear due to the fact that it is "deep" composition of non- non-linear maps.
One of the standard versions of random projection involves mapping points by a random Gaussian matrix. It was later shown that other types of random matrices work equally well. [1, 3, 30, 23]. In particular, the "binary" version of the of the matrix are all either +1 or -1) is particularly important for the following reason. As dis- lemma
lemma due to [1] (where the entries
cussed in [15], an alternate way to convert sketches obtained by the to bits is possible if the points have bounded integer coordinates and one uses the binary variant of Johnson-Lindenstiee
lemma. This approach is somewhat incomparable to our setting because of the integrality assumption.
Another variation on the random projection technique to apply a quantization step after the pro- jection which further reduces the cost of storing the data points [6, 21, 24, 29, 4, 10, 18, 25, 32). particularly relevant version of quantization "sign random projections" [6]. Sign random pro- jections are the same as the l-layer maps 11- They were used to estimate angles between points in

---

[6] and used to estimate inner products between points in [22]. Therefore, the main novelty of our technique is the idea of composing multiple such maps.
1.4 Distance compression beyond random mappings
Random mappings are of course not the only way to compress data set. Here we compare our method to compression techniques that use methods other than random mappings. These methods tend to be more complicated algorithmically but we explain below, can produce sketches with fewer bits.
Given a set of n points in the unit ball in R., what is the minimum number of bits of a sketch which allows one to recover all pairwise distances up to multiplicative (1=c) error? As explained above, the Johnson-Lindenntrauue is not the optimal number of bits. It was recently shown in [14, 15] that if the points are contained in the unit ball and m is the minimum distance between points, then ( 2n log n + n log log (L/m)) bits suffice. The additive error version of this question was answered in [2]. Previous to the result of [14, 15], the best known result was that O --2 log log(I/m)) bits suffice [19]. These two results, however, use sketching techniques that differ from the sketches obtained by the random projection technique in fundamental way. Random projection compresses the data set "point by point" in the sense that the compression process is applied to each point independently from the others. In contrast, the sketches in [15] and [19] must compress the entire data set simultaneously.
lemma shows that ( log n log(1 ( 1/m=))) bits suffice. However, this
Another way of stating this distinction is that "point by point" methods (such as random projection) satisfy the requirements of the one-way communication version of this sketching problem while the methods used in [15] and [19] do not. In the one-way communication version of the sketching prob- lem, Alice holds half of the data points and Bob holds the other half. Alice sends a message to Bob using as few bits as possible. Bob then must report distances between pairs of points where one point in the pair is known by Alice and the other by Bob. The one-way communication version of the sketching problem asks one to determine the minimum number of bits of Alice's 's message. was shown [27] that if the points are in the unit ball and the minimum distance is m, then ((c 2 log
log(1, (1/m)) bits are required for the one-way communication version of the prob- lem if the sketch required to be successful with probability at least 6.
Any sketching algorithm which compresses the data set point by point satisfies the requirements of the one-way communication variant of the sketching problem. We therefore know that sketching algorithms which compress the data set point by point cannot produce sketches with the optimal number of bits. However, there are several advantages to sketching algorithms of this sort. One advantage is that they are generally simpler and easier to implement. Another is that if one wants to add additional points the data set, the entire sketching algorithm does not need to be re-run.
Our sketching algorithm from Theorem 2 also has the property that it compresses the data set point by point. Furthermore, the number of bits of our sketch almost matches the lower bound from [27]. The dominant term in the bound from Theorem is (cc-2n log n(oo(1 (/mm// (o))))))g((//221) Thus our number of bits matches the lower bound from [27] up to the power on the log(1 1/m) term. This motivates the question whether some variation on our sketching technique can reduce this power.
1.5 Outline of the paper and notation
Section 2 contains the construction of the maps yp and quantifies the error in the approximation of fe((x, y)) by (e (y)). Then in Section we explain how the proof of Theorems 2 and is completed. This amounts to showing how (jp(()), (pe(t) allows one to estimate | y/|² and quantifying the eиror of the estimation. Some of the details are deferred to the appendix. Finally, Section 4 contains experimental results, including an application to nearest neighbor search.
For E R \{0} we use å to denote z/ e/|l=|| For x. 5d-1, the polarization identity states that 2 - 2(z, v\ || 2112: for arbitrary 2, y IR. it states that ||=:|/ + || 2(xz, y) || y/
5

---

2 The construction of the maps fpr
The purpose this section is to prove the following result, Corollary 4, which shows bound on the error of the approximation of (zz, v by (fe( for all pairs 2, y in set of n points. The error in this approximation depends on the dimension De of the image space of ye. In particular, we show how large D₂ needs to be in order to guarantee with high probability that (fe(x)), is equal to Se((2; 5i) up to some additive error ó for all pairs æ;, y-
We recall the definitions of the functions Jt and gs: Let f(() = - arcsin(() and g(() = sin ) For l E N let fe be the function f composed with itself times and similar for gr- Notice that for any E - fe 1-1,1] 1] [-1, iJ is the inverse of gr: [1,
Corollary 4. Let S St-1 with |S| n 2 Let == maxx.yES.utt
VI-(aa)) Let & E N
Let 8 > 0 be such that 8 < 3. Then there exists random map : E - De 1/2 {-1, (independent of S except through parameters n, d, r) such thut with probability (1 - 4 y it satisfies
((pe(x), pe(()) fe((a, ()1, 8
for all x, y E S. where De
-24
The above corollary follows immediately from the following theorem which also determines a bound on the error of the approximation accuracy not only of [a((2, v)) by (1pe(x), spr(y)) but also the approximation accuracy of [5(( x)) by (1)(2), (v()) for all j (1....,(}
Theorem 5. Let S C S with |S| = 2 2. Let r == maxx.yES,7rv
Let l E N+ V1-1(z.071
2
Let > be such that 8 3. Then there exist random maps iPj B
+ Dj 1/2 { 1- 13
j E (1....,f) (independent of except through parameters n, d, r) such that for all E (1,...,() with probability at least (1 y, V0 satisfies
8
((p(()), f5((,,))) 2 21-3,0(233)- (2/3)-
(2)
for all x, E S, where D, 24.2att 0,0//a (2/31) logn
Proof. The maps Py will be compositions of maps of the following form. Set D N+ Let Zi, 1 Kii D be i.i.d. standard Gaussian random vectors in Rd Let DD Rdd R be defined by
(x)) = D-
1/2 sign((æ, Z,)),
where (x); the ith coordinate of (x))) A direct calculation, see [26]. shows that (x))((x), ( = f((z,))) v)). Furthermore, 1x)(()) = for all x E Rd.
First we use this construction to define f1. We let Φ1 = Dp where D1 is chosen below. Using Hoeffding's inequality, for all x, y. S.
((((()) p(v)) f((2,))) - 26-1, (2/3)
8
-P (p p(u)) Dif((a,u))
Dj
28- 32-3
D282
$ 2exp
2. 22 1), (2/3))
(t22((t-1), 1,00((--1),0((2))----1 log
This means that the above probability is less than 2/n and that 9p satisfies the conditions of the theorem with probability at least 1 2/n.
We set D1
8
1/n 2
2 r2
Now assume that the required map exists for some j 2 1. We will show that it exists for j + 1. D, 1/2 1/11/ 1-1, D, which satisfies Eq. (2) with probability least
So there exists map Py d

---

(1 - 2t Let Pj+1 be defined by 9j+1(()) = (p)((z) of the proof. We will show that, conditioned on the event that sp, does satisfy Eq. (2), the probability that 9j+1 satisfies Eq. (2) is at least " So assume that 99, does satisfy Eq. (2). Recall that we want to show that (1)+1(()), P3+1 (V)) is good estimate of ff+1(( v¹). We have by [26] that E(p)+1 (z), ())1 = (2), i.e. (1)+1(()) is an unbiased estimator of (z))) By the triangle inequality, (()))(()))) f (),
where D,+1 will be chosen at the end
2.
{ (p) (0)) f((p) Pps (())) + (+((()(())))))))) f(f)((,)))) v>)]|- (3) First we give a bound on the second term in Eq. (3). We are assuming that y0y satisfies Eq. (2), i.., that for all 2, E S, (1), (2)())) - (xr,,))) S ( (2/3)5)
So to get a bound on the second term in Eq. (3) we need to get an upper bound on the derivative of f in the interval between (x), (2)) and (( v)). We claim for all pairs y E S, x # y. the
derivative of f in the interval between (1)(x),, sy (v)) and [5((2, v)) is upper bounded by ,(2/3))
Let t be in the closed interval between (2) (v)) and fz By definition of Φj and fg this implies [t] S We also have |t] S (f) v)) + (/22-3)) (2/38') s (fz((z, 3))l + by
Eq. (2) and the fact that r 2 2 by definition. Thus,
1 |t| 2 1 - Ifs v)) -8
2 (1 (0r, y) 11//3/ -
by Lemma 10 in Appendix B
M (1 (x, y (2/33))
2 by 8
(z, v)
(1 KI, 23333
2
p2
2
2
Using this and |t| S 1, we get
2
2
2/2
2 2/
f'(1) TVI 12
(2/3)
TV
[
π T(
(a, y)
(2/3))
π
We have shown that the derivative of f in the interval between (1) (1), 12, (w)) and [z((2, vi) is upper bounded by (2/33), This combined with Eq. (2) and the fact that the derivative of f is positive implies that
- < (2/33)
2 (2/3))
8
2( (233))
where the equality above uses that ((1233)-12///) -
= - -
Now we deal with the first term in Eq. (3). Using Hoeffding's 's inequality,
((00) - f)-1((x, v)) >
2 2-2 1 (2/33')
D
= =P(DDH2(PgHH (1+1 D D)t2fs+2((110)) >
2. 222--
DD
22exp -
8 8.22((-(++)))) (2/3))
(2/3)) log"1 This means that the above probability is less than 2/n².. So, using Eq. (3) and the previously established bound on the second term in Eq. (3), we have shown that for any pair x, y E S,
We set Dj+1 = 24.2200 3a
(1)+1 Pj+i (v))
w))
2(- (2/33))
with probability at least 3.. So, conditioned on the event that y,, satisfies Eq. (2), P/t1 satisfies Eq. (2) with probability at least
2. Since the probability that (o41 satisfies Eq. (2) is greater
than or equal to the probability that both 40 and yo, satisfy Eq. (2), this means that the probability
that 4j++1 satisfies Eq. (2) is at least (1 2)++1
7

---

und layer
loyer
bed layers
laye's
0.6
0.3
0.4
0.3
0.0 0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.08
0.10
0.01
0.02
0.02
0.04
0.05
0.06
0.07
0.08
0.00
0.10
[K-11
Figure 1: The left, resp. right figure shows the average over 4000 trials of the value of such that 2 - 2g ((p1 p1 (y))) and - ()2(((2(x)) (P(())) approximate | y/2 up to multiplicative
(1 e) error when the input dimension is 2, resp. 2000.
The recovery of || - yyl by (2( and (p((y)
Here we explain how the proofs of the main theorems, Theorems and are completed. This is done in two steps. Recall that we showed in Corollary 4 that (fPe(r), (v() ) is a good approximation of (a( y)) for pairs x, y E S. The first step Theorem which shows that (e((( (p(())) is good approximation of (x,, y). The reason this is true is because ge is the inverse of fe. So the proof of Theorem uses facts about the derivative of ge (in particular Theorem in Appendix B) to show that the bound the error of the approximation of fe((z, y)) by (pp(2)), (p)()) implies bound on the error the approximation of (z, y) by ge ge(((p(z)) (pe()) (Theorem 6).
The second step is to set é [log, log2 1 where m is the minimum distance between pairs of distinct points S and then show using the polarization identity that the error bound established in Theorem 6 implies the error bounds in Theorems 2 and 3. The proof of the following theorem and the proof that Theorems 2 and 3 follow from Theorem 6 are Appendix
Theorem 6. Let S S with |S| n. Let l E N+ and e > and assume that satisfies e 1 (xx, u) for all x, y E S with x & y. Then the random map ye S N-1/2 (1,, from Theorem satisfies that, with probability at least (1 - 2/m)* for all z, S. ge(((p( (e) (p())) is equal to (x,u) v) up to additive +e|læ
2|12-2 error where N /8(=/v2)= log 2²
Equivalently, for all x,y E S, 2 tellæ v/12 2 erron.
is equal to || y112 up to an additive
Experiments
The main goal of our experiments is to validate the idea of composing multiple random feature maps. Our main results show that better error guarantees can be obtained by composing multiple random feature maps. This is demonstrated by the additive eтror term +-|| 2-2 in Theorem 6 which is smaller for larger values
as long as || yll < Recall that we refer to the parameter l as the number of layers of the random mapping. In our experiments, we will focus on comparing one layer maps i to the two layer maps 222. First we do a simple experiment to determine more specifically under what conditions we should expect two layers to outperform one. Then apply maps to nearest neighbor search and again compare performance one layer to two layers.
4.1 Two layers vs. one layer
As already mentioned, Theorem indicates that the additive error obtained by the one layer map proportional to || yll and the additive error obtained by the two layer map is proportional to ||æ - y||3/2, Therefore, two layers should give better error estimates than one layer when || - y/ sufficiently small. Our first experiment answers the following question; how small must | yl

---

1.0
4.
1.0
0.7
2.0
syyer
one layer
layers
layers
projection
10-
Gaussion random projection
12
6
30
12
Icg base sxipect dimwromn
log bane 2 oliuupuu dimeraion
Figure 2: Average over 500 trials of the number true nearest neighbors of Xo in recovered from (D(),, (D()), and GD where G is an i..dd Gaussian random matrix.
be so that two layers outperform one? We consider pairs of points x,y Sd where | yl ranges from .01 to .1. We will see in this experiment that the input dimension has little to no effect and
without loss of generality assume d 2. In the d 2 case we take æ (1, 0) and y (a, v1 a²) where is chosen that || - yll ranges from .01 to in increments of .005, by both maps 91 and 92 where the output dimension of both maps is 1000 and 22 first maps to {-1, 160000 In Fig. we plot the average over 4000 trials of the value of such that 2-2gi ((p) (x),, 1 (4))) and 2g2 (1)(()) (2())) approximate | y| up to a multiplicative (1 error. We see in Fig. that the two layer map gives better approximation of v when || --- S .06 and the one layer map gives better approximation of || -ar-vll y/I when | vil > .06. From a practical perspective, this means that the one layer map may often outperform the two layer map because most real world datasets have few points at this small of distance. However, very large datasets may be more likely to have distances this same experiment when d 2000 except for d = 2000 we choose the input points randomly: z/ 2|| where z + (dist/ Vd).N (0, Lạ) and dist ranges
Fig. 1. We map
range where two layers better. We do
We let be uniform Sdd1 and set from .01 to .I. With this choice, EE [2 y| dist. Because there is no dependence on the input dimension in our error bounds, we expect the error to depend on || y/ but not d, which is verified in Fig. 1.
4.2
Two layers vs. one layer; nearest neighhor search
Given set of points and query point, nearest neighbor search is the task of finding the points that are closest to the given query point. Nearest neighbor search is used in many applications to solve regression/Clasifccttioo problems. Before performing nearest neighbor search, some dimen- sionality reduction or compression method can be used to reduce the computational cost. We test the performance of our maps ypr for this task.
Again we focus on & 1, Given a data set and a query point X E D, we first map D by P1 and P2 to N N 1 We then calculate the k nearest neighbors X according to the compressed data and compare how many of the true & nearest neighbors of X in D are recovered.
Randomly generated data. We let Xo (the query point) be uniform random vector on the unit sphere S2, Then for i 21,2,.... ... 100), let Y, Xo + (4/5) (((///20)NN)) (O, I3) where (O0, la) g is from the multivariate normal distribution (and the Y, are independent). The constants are chosen so that E X| Yill RJ i/200. Then the data D defined to be X, along with [Y</I|X>]]]ee (1,,0000000) We map D by i and y22 where the output dimension ranges from 23 to 21 and 422 first maps the space of dimension six times the output dimension. We also map D by standard Gaussian random matrix to Rd with the same range of output dimensions. The average number of & nearest neighbors recovered is shown in Fig. As to expected based on the previous experiment, two layers generally outperform one. We remark that the accuracy of our maps is not meant to be compared to the accuracy of the Gaussian random matrix because that mapping uses full precision real numbers and does not convert to bits.

---

ond layer
two layers
Gaussian rancom projection
0100000 1000 how.oee
2.0
1.0
layer
0.5
projection
10
11
Icg base euspett dimmromn
Big tanu 2 ol dlouupu dimeraion
Figure 3: Average over 10 independent trials and over all 179 query points of the number of true nearest neighbors of 179 query points in RCVI recovered from s (D), (2(D), and GD where G is an i.i.d. Gaussian random matrix.
Real data. We perform similar experiment with the RCVI dataset [20]. The RCVI I data set consists of 804414 samples and 47236 features. We only consider the first 23149 samples which have been previously designated the training set. As query points, select all data points which have at least one neighbor at distance less than .05. There are 179 such points. The RCVI dataset consists of unit norm vectors. This our data set D. We map D by (2 and y22 where the output dimension ranges from 2 to 21l and (o2 first maps to the space of dimension six times the output dimension. We also map D by a standard Gaussian random matrix to RRd with the same range of output dimensions. The average number of & nearest neighbors recovered is shown in Fig. 3. We see that in the case k = 1. the two layer map outperforms the one layer map when the output dimension sufficiently large. This again confirms expectations based on Fig. 1. In the k case, the one layer map is superior. This is likely due to the fact that while our query points all have at least one neighbor distance most .05, the other three out of the four nearest neighbors may be at significantly greater distance. Therefore, again considering Fig. 1, it is not surprising that the one layer map gives better approximation of the four nearest neighbors.
Conclusion
We introduced new method for compressing point sets while maintaining information about ap- proximate distances between pairs points. The method compresses point sets using a composition Pe of & random feature mappings. The main advantage of composing multiple feature maps is that, rather than approximating pairwise distances up to an additive error, our maps accomplish the more difficult task of approximating the distances up to multiplicative (I + e) error. The reason that get multiplicative rather than additive error guarantees a direct result composing multiple ran- dom feature maps and has to do with the behavior of the derivative of the function ge (introduced in Section 1.1) near = 1. We also validate the idea of composing multiple random feature maps experimentally.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation under Grants CCF- 1934568 and CCF-2006994.
References
[1] D. Achlioptas. Database-friendly random projections. In P. Buneman, editor, Proceedings of the Twentieth ACM SICACT-SIGMOD-SIGARTT Symposium on Principles of Database Sys- tems, May 21-23, 2001, Santa Barbara, California, USA. ACM, 2001.
10

---

[2] N. Alon and B. Klartag. Optimal compression of approximate inner products and dimension reduction. C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 639-650. IEEE Com- puter Society, 2017.
[3] R. I. Arriaga and S. S. Vempala. An algorithmic theory of learning: Robust concepts and random projection. Mach. Learn., 63(2):161-1)) 2006.
[4] P. Boufounos and R. G. Baraniuk. 1-bit compressive sensing. In 42nd Annual Conference on Information Sciences and Systems, CISS 2008, Princeton, NJ. USA, 19-21 March 2008, pages 16-21. IEEE, 2008.
[5] E. Candès, J. K. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruc- tion from highly incomplete frequency information. IEEE Trans. Inf. Theory, 52(2))489-509, 2006.
[6] M. Charikar. Similarity estimation techniques from rounding algorithms. In J. H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 380-388. ACM, 2002.
[7] Y. Cho and L.. K. Saul. Kernel methods for deep learning. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Process- ing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009, Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pages 342-350. Curran Associates, Inc., 2009.
[8] S. Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 634-644. IEEE Computer Society, 1999.
[9] S. Dasgupta and A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures Algorithms, ((1):60-65, 2003.
[10] W. Dong, M. Charikar, and K. Li. Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. In S. Myaeng, D. W. Oard, F. Sebastiani, T. Chua, and M. Leong, editors, Proceedings of the 31st Annual International ACM SIGIR Conference Research and Development in Information Retrieval, SIGIR 2008, Singapore, July 20-24, 2008, pages 123-130. ACM, 2008
[11] X. Z. Fern and C. E. Brodley. Random projection for high dimensional data clustering: A clus- ter ensemble approach. In T. Fawcett and N. Mishra, editors, Machine Learning. Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pages 186-193. AAAI Press, 2003.
[12] S. Har-Peled. A replacement for voronoi diagrams of near linear size. In 42nd Annual Sym- postum Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 94-103. IEEE Computer Society, 2001.
[13] P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. J. S. Vitter, editor. Proceedings of the Thirtieth Anmual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 604-613 ACM, 1998.
[14] Indyk and Wagner. Near-optimal (Euclidean) metric compression. In Proceedings of the Eheety-Eighhte Annual ACM- SIAM Symposium Discrete Algorithms, pages 710-723. SIAM. Philadelphia, PA, 2017.
[15] P. Indyk and T. Wagner. Optimal (Fuclidean) metric compression. SIAM J. Comput., 51(3):467-491, 2022.
[16] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into Hilbert space. In Conference in modern analysis and probubility (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189-206. Amer. Math. Soc., Providence, RI, 1984.
11

---

[17] K. Kenthapadi, A. Korolova, I. Mironov, and N. Mishra, Privacy via the johnson johnson- lindenstrausss transform. CoRR, abs/1204.26600 2012.
[18] K. Knudson, Saab, and A. Ward. One-bit compressive sensing with norm estimation. IEEE Trans. Inf. Theory, 62(5):2748-2733 2016.
[19] E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces, SIAM J. Comput., 30(2)457-477, 2000.
[20] D. D. Lewis, Y. Yang, T. G. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. J. Mach. Learn. Res., 5:361-397, 2004.
[21] Li. Binary and multi-bit coding for stable random projections. In A. Singh and X. J. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statis- ties, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pages 1430-1438. PMLR, 2017.
[22] P. Li, T. Hastie, and K. W. Church. Improving random projections using marginal information. In G. Lugosi and H. U. Simon, editors, Learning Theorry 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006, Proceedings, volume 4005 of Lecture Notes in Computer Science, pages 635-649. Springer, 2006.
[23] Li, T. Hastic, and K. W. Church. Very sparse random projections. In T. Eliassi-Rad L. H. Ungar, M. Craven, and D. Gunopulos, editors, Proceedings of the Twelfth ACM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August 20-23, 2006, pages 287-296. ACM, 2006.
[24] X. Li and P. Li. Random projections with asymmetric quantization. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages
10857-10866, 2019.
[25] X. Li and P. Li. One-sketch-for-al Non-linear random features from compressed linear mea- surements. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13- 15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 2647-2655 PMLR, 2021.
[26] Z. Liao and R. Couillet. On the spectrum of random features maps of high dimensional data. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference Ma- chine Learning. volume 80 of Proceedings of Machine Learning Research, pages 3063-3071.
PMLR, 10-15 Jul 2018
[27] M. Molinaro, D. P. Woodruff, and G. Yaroslavtsev. Beating the direct sum theorem in com- munication complexity with implications for sketching. In Proceedings of the Twenty-Foure Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1738 1738-1756. SIAM, Philadel- phia, PA, 2012.
[28] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, editors, Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Pro- cessing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 1177 1184. Curran Associates, Inc., 2007.
[29] S. Rane, P. Boufounos, and A. Vetro. Quantized embeddings: An efficient and universal nearest neighbor method for cloud-based image retrieval. In Applications of Digital Image Processing XXXVI, volume 8856, pages 63-73. SPIE, 2013.
[30] S. S. Vempala. The random projection method, volume 65 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Providence, RI, 2004. With foreword by Christos H. Papadimitriou.
[31] J.-I. Zhao, C.-F. Wei, B.-N. Guo, and F. Qi. Sharpening and generalizations of Carlson's double inequality for the arc cosine function. Hacet. J. Math. Stat., 41(2):011-009 2012.
12

---

[32] A. Zymnis, S. P. Boyd, and E. J. Candès. Compressed sensing with quantized measurements.
IEEE Signal Process. Lett., 1722):199-152, 2010.
13

---

A Proofs of Theorems 2, 3, and 6
Proof of Theorem 6. We will actually prove the stronger result that with probability at least (1 2/n)., for all 2, y E S. (e((pe())) (e(t))) is equal to (z, 3) up to an additive (x,,))))
3)1) 1-2-
error. This statement implies the theorem statement by the polarization identity.
Set 0 = (v2/2) in Theorem 5. One can check that the assumption that < 1 Kr,, 4) for all z, E S with + implies that 8 < 2/r² for all x, y E S with x # y as required by Theorem 5. From Theorem 5, the map pe : Rdd VN {-1,1] 13 satisfies, with probability at least (1 - 2/n)², that
((PE(E), pe(()) - Se ((,,,)))) < (e/22)(V2/=))
(4)
for all 2, E where N 48(x/ logn Now assume that i does satisfy Eq. (4) for all
I, E S. Since ge (fe(t)) = t for all E [-1, 1], Eq. (4) implies that ge (e(())()), (pe(t))) should be a good approximation of (ar, v)- In particular, we claim that for all x, y E S. ge (x). (p(()) is equal to (x, y) up to an additive error of = (z, x>1"-22'. In order to show this we first need to get a bound on the derivative of gr in the interval between (p)(x)) (p(()) and fe((2, v)).
Let / be in the interval between (1px(e), sp(()) and Se((2, v)). By Theorem 7,
n² (2 (22gg((()) 1-2 .
sé(l) v
2
By Eq. (4), we have that []fe((z) v\)l |t|| I v3) By Lemma 8 this means that (e((e((a 1)) - ge(1)) S (v2/// (m/2)² S e, i.e that ge((4)) 2 (e(eee(z,, w))l) - c. Since f is an odd function, ft) is also an odd function and so ge ((f,(((x,))) = ge (ff(((( y))) = (xx, v) So we have shown that ge(lt) 2 Kz, v>! c. Since e < Kz, vYl. we have that 2 - ((t( S 2- - 2 (x, v) + 2c < 2 - 21 v\l). Using that 21-2 < 2, this means that
(c(t) v tt (2 (g)( 1-2 S v2
π
(2 - (2, 8) 122-
2
-2
This bound the derivative along with the fact that (t) > 0 and Eq. (4) means that
ge (((e(()))<(()))) ge (fe((z, < c( - (z, v\l) vii)= 1-2-
Since ge (ff((xx,))) v))) = (z. the theorem follows.
Now that we have established the above result, we can prove Theorems and 3. We restate the theorems from the intro for the sake of readability.
Theorem 2. Let S C 5 with |S| n 2 2. Let m = min || - yll and é= [log2 log, 41 2 1. Lete > O and assume that e < mineweeS,a.y 1- (xx Then the random
map iee : Sd + VN 1-1, with N = Ologg" (oog"(log 1)2 v2) (defined in the proof of Theorem 5 and independent of S except through parameters n, d, and yES 1- -KK, a)) D) satisfies the following with probability at least (1 - -2)= ve((S) is a sketch of S that allows one to recover all squared distances between pairs of points in S up to a multiplicative (1 + e) error. The a logn (nlog. (log }) (22oog(1// (1)).
number of bits of the sketch is O
Proof. Let po : Sd-11 - N N-1/2 1,11 1)N be the map from Theorem 5 that by Theorem 6 satisfies,
with probability at least (1 - 2/m) that 29g2 ())(()))) (P(())) is equal to ||x y11² up to an additive (c/44]|l= y 2 error for all x, y E with N 768(m/ / logn" Now assume that for does satisfy this condition for all z, y E S. We have
++1
- -- < (L/m)² 2- ((I/m)²*)² < ((1/m) (oeadarm) )² <44
14

---

This means that we actually estimate || 2 up to an additive - error, i.e., multiplicative (1 = <) error. We have
2
2(1 Hogg loRg m
n=2 2a 1og2( (z) logg logg(
x²² 2 m
4
lowa /7
logg
V2
V2
2
so the result follows.
The above theorem shows that given a set of points C RR"", there exists an appropriate choice of & and N so that the random map yp: S NN11/2--1,1) satisfies, with high probability, that (Pr(S) is a sketch of S that allows one to recover all squared distances between points in S up to multiplicative (1 + e) error. The next theorem shows that this same sketching algorithm also works for point sets that do not necessarily consist of unit norm points provided that the sketch also stores the approximate norms of points in S.
Theorem 3. Let S Bdd with |S| = n 2 2 and set p minges ||=||. Lerm m yEE 1 all and & [log2 log2 A 2 L. Let
O and assume that min 1- (22 0)1. Then ) (defined in the the random map øe : 5d - vズ (-1,1} with N = e ( (log 1 m proof of Theorem 5 and independent of S except through parameters n, d, m and yE (ē, 9) ) satisfies the following with probability at least (1 2 (e((S and the norm of each point in S up to an additive = ervor is a sketch of S that allows one to recover all squared distances between pairs of points in S up to multiplicative (1 (1 c) error. Moreover the number of
bits of the sketch is θ [log (log 1 2 (=//( + +n log pmite)
Proof. For each x S, let ny be an approximation of ||-||| up to additive tpm²e/ error.
First we claim that in order to recover squared distances up to multiplicative (1 e) error, suffices to recover squared distances to an additive =<||=>|||v=|||| - .il error. The reason is that for any y, E R.d we can prove the inequality <||x||]]>||| ||@ ~11² < <l|xx - -yll² by observing that
|| | [|lll a ğ 2 = [|=]|]lv|(2222 i)) = 2||0|| |lyll 2) S ||=|| +1yyl2 11y112-((xx,)) = ||x0 -|---yll yll
Now let S = {0: x S}. Let Pe S N (--1 with N e ( 20gg)
2
be the map from Theorem 5 that by Theorem 6 satisfies, with probability at least 2/n) that ge( (e(()e())) (0))) is equal to (ă, up to an additive (2/322) - 2 (2. 0)1 error for all i, E S. Assume that &p does satisfy this condition for all é, E S. Notice that this implies that ge((pe(#)) (e(())) is equal to (it 1) up an additive =cc332) 2(2, 1-2 error for all i, S. We have
(2 20. 0 2- < (1/m)² -(1/m)) ((1/m)2**)
) < ((1/m) boxed4/3) )² < 4.
This means that ge ( (0), (0)) is equal to (f. 9) up to an additive +c/ - 2(, 9)) error for all f, 9 E S, i.c. an additive [| 011 error. For any x, E S,
- (||= + pm (leyl + pm2c/48) ((t, 0) + (c/8)]l= - 011²)
n,
< (z. v) + (c/4) b || 0||²
where the second inequality uses the definition of p and m. We can also show that
ne Re (o())) 2 (z. v) - (</4)||=|lbbbll| ó This means that ngngge (essee((yeet) (()e((), sp (e())) (()) approximates (z. up to an additive ((c/4)]==]]) ||
e|| error. Since ny approximates ||= up to additive +e//24) ming || ~l error
this means that n approximates ||a:|| up at least an additive ( (<//4]]]== [|]bl]l - error. Now this means that
n + n 2n (+).
approximates
| + 12 2(z v) 1|- 4/12
up to additive =e||a]|| ||vl|| ú error.
15

---

Storing all the norms of the points up to an additive =p error requires log(1/p) bits per point.
We have
(T/V2) S (T/v (T/V2)20t logz r) = =1x² /m2 logz (2/v2) log, logs (x2/22)log2 1) r)2loga(7/v2)
so the result follows.
B Technical lemmas
Theorem 7. For all [0, 1].
(f((()))
(2 (2-26)2-2 22)2-22-
This implies that for all t [0,1]
π
(2 - 2=)ge(t)) 1-2
g1(())
2
2
and that for all E [-1,1].
ge(l)
π
(2 2ge (g)((11)) 1=1)
-=1
Proof. We start by proving the first claim.
We will the inequality
2 1 1 f-) arccos(t) S vI- for [0, 1],
(5)
π
which follows by finding critical points of vI -I-t- arecos(t). Now this enables us to prove by induction that
1 - f2(() < (2 21)²- for E [0,
for all l e N+. The base case l = is (using Eq. (5))
2
ft) arccos(t) (t) S v1 - ts v2 2t.
The induction step again uses Eq. (5) and also uses that fi-1(t) [0, if t e [0, 1]. For all t e [0, 1]. we have
1 fe(t) = 1 f(fc-1(t))
$ /I - fe-1(t)
$ (22 21)2-
= (2 2t) 2
So - 5 (2- < 'or [0, follows.
Now we will prove the first theorem claim by induction. The base case
g' (f(t) cos (osccicsi)())
π / 1 t2 < 5 2t.
Now for the induction step, assume that the first theorem claim holds for fe-1- We first need to establish that for all E 1-1, 1].
g' (f)
π
cos cos((T/))fe(())
2
π cos (fresin(fe-
2
VI (f))1
2
/1 ft-1(t)
by ft-1(t)
2
π
(2
24)
22"
16

---

Using the chain rule, g((t) - ((())=((t)((-((((t)) So for all E [0, 1].
-((((()))--1(10-(0)
I TT (2 (2- 22)2
(2 - (2-2t)2-22 2-)
V2
2
x²
2 (2 21) 1-2"
The second claim follows by plugging in gt into the first claim. The third claim follows by observing that if t E [-1, 0], then g()) ((()) since ze is an even function (by the fact that Ze odd.)
Lemma 8. For all 1 E l2(1) - (T/2)².
Proof. By induction. When = 1, (t) = cosl zt E T/2] when E [-1.1]. For the 2 induction step, we need to use the fact that gr- (1) 11,,] when [-1, Using this,
d((() (9c-1 (9c-1
T ())- (1) (m/2))
Lemma 9. [fe(t)) < for all E [-1,1] and all E N+
Proof. Since fe(-t) f(( for all t [-1, 1]. it suffices to prove that fe(t) t for all e [0, 1]. The claim follows by induction in l.
Lemma 10. For all 8 N and E [-1, [+(0) (1 111)(2/33)
Proof. Since fe(-t) = -f((t), it suffices to show that 1 - fe(t) 2 (1 t)(2/3) for all t E [0, 1].
To prove that 1 1-((() (121) will use that arccos( 2 =(1-))//2
2(141)770 for all / [0, as shown
(1-1)1/2
in [31, Remark 2.1]. Now have 1 f(t) x arccos(t)
(1+1)1/6- The result now follows
since (1+1)1/6 2 (1 f)2/6 for all & E (-1, 1J. This is the base case. The induction step uses the fact that for all t E [0, fe(t) E [0, 1]. Using this and the base case proven above,
1 (t) 2 - f()) 2/3 2 ((1 1)12/33)) 2/3 (1 2)2333)
17

---

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:
The abstract summarizes the main theoretical results of the paper and indi-
cates their significance while also acknowledging that some situations, other pre-existing methods are better. We also point out that experiments back the theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the paragraph after Theorem 2 explain the range of parameters for which our maps use fewer bits than the Johnson-Lindenstrann
style maps. Furthermore, in section 4.1 we explain how our maps (e for L > may only be useful in certain applica- tions. (In particular, for point sets where there are many very close pairs of points.)
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
18

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theorems include complete proof. Some of the details of the proofs of the main results are deferred the first appendix. But we give short overview of how the proof is completed in the first two paragraphs of Section 3.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We explain all of the details of how the experiments are conducted. Further- more, they are simple and easy to implement.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way to accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
19

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We included link to github repository containing the code used for experiments in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips.c. cc/
Srriddes/Codeuumiiss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips.coo wttpccpppppccccccccctccccccccccc htaplli//gugddeee guwdge/id////e SuddeSummiieee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
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:
The experiments are fully explained in section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We do not report enror bars. But because of the simplicity of the randomness inherent our experiments, it is clear that they are significant simply because we perform sufficient number of independent trials.
Guidelines:
20

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report 1-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: We ran experiments standard laptop and do not think it is necessary to report compute time because we are not including code in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http::////euuuuueeeeeee httpc//pcc//etiiccoiiiiiiiieooio
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
21

---

Justification:
Our research has no immediate negative upplications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our models/data do not pose such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
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 the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide citations for all pre-existing models. And we also cite the paper that first introduced the dataset that we use (RCVI)
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
22

---

The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, anperswithoode www.com///a///c con/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
23

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "4I4eUMu8na", "reviewer": "Reviewer_4gJb", "summary": "The authors investigate the bit complexity of distance preserving embeddings of points on the unit sphere and in the unit ball.\nTheir main finding is that iterative application of Charikar's hyperplane SimHash could use slightly fewer bits of storage than snapping a random projection to an epsilon net for certain parameters. \n\nExisting prior work could compress a set of points to even fewer bits while preserving distances all these methods operate on the entire set. The authors' method compresses data points (vectors) individually, which is an advantage.\n\nEmpirical evaluation with synthetic and small scale real world data support the theoretical claims.", "questions": "Could you compare the theoretical predictions of Theorem 6 with the empirical findings of Figure 1 that for distances < 0.06 two layers have lower error than one layer?\n\nLine 340: \"six time the output dimensions.\" Could you elaborate how 6 was chosen?", "limitations": "Limitations are sufficiently discussed. (Mostly) theoretical work, no negative societal implications.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors study a broadly applicable problem.\n\nThe proposed method is simple to implement and comes with theoretical guarantees.\n\nThe experiments support the theory.", "weaknesses": "The reduction in the number of bits needed only impacts lower order factors, as explained on line 77.\n\nCould you please discuss the many quantization methods cited on line 173 and compare yours with them both analytically and experimentally?\n\nFigures 1 and 2 lack baselines that compress to bits, could you please add a few, including quantizing (epsilon-netting) a random projection?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weakness 2: Of the quantization methods discussed on line 173, the most relevant one is known as \"sign random projections\" [6] and some of those other papers generalize sign random projections in various ways. We will add a remark saying the our 1-layer map $\\varphi_1$ is the same as the original sign random projection and that the main novelty of our work is composing multiple sign random projections.\n\nConcerning the experiments, paper [6] is essentially the same as our 1-layer map, with the same guarantees. Papers [4],[18],[21],[31] are about compressive sensing and [24] is about quantizing random Fourier features so there is no direct comparison to be made. Paper [28] provides an additive error guarantee, ours is multiplicative. Paper [10] and [23] have no theoretical estimates for the number of bits required as in our Theorem 2, instead they take the approach of bounding the variance of the estimator.\n\nWeakness 3: As our main contribution is theoretical, we did compare our technique to epsilon-netting a random projection analytically but not experimentally. Part of the difficulty is that for such an experiment it is not clear how to choose the tradeoff between the projection dimension and the size of the epsilon net (A fair experiment would have to know the optimal choice of the size of the epsilon net compared to the projection dimension.) \n\nWeakness 4: We sent the code to the AC per the instructions. We will publish the code and add a link to the paper.\n\nQuestion 1: According to Theorem 6, the $\\ell$-layer map approximates distances up to an additive $\\pm \\epsilon \\|x-y\\|^{2-2^{-\\ell+1}}$ error. Say that we use the 1-layer and 2-layer map with the same output dimension $N$. Looking at the definition of $N$ in Theorem 6 and solving that equation for $\\epsilon$ we get that the 1-layer map approximates squared distances up to an additive $\\frac{\\sqrt{48 \\log n}(\\pi/\\sqrt{2})\\|x-y\\|}{\\sqrt{N}}$ error and that the 2-layer map approximates squared distances up to an additive $\\frac{\\sqrt{48 \\log n}(\\pi/\\sqrt{2})^2\\|x-y\\|^{3/2}}{\\sqrt{N}}$ error. So from this we conclude that 2-layers is better if $\\|x-y\\|$ is sufficiently small. However, in the context of the experiment in figure 1, Theorem 6 is not able to accurately predict exactly how small $\\|x-y\\|$ needs to be to make 2-layers better. The reason is that Theorem 6 assumes that $\\epsilon<1- \\langle x, y\\rangle = \\frac{\\|x-y\\|^2}{2} = \\frac{1}{200}$ when $\\|x-y\\|=.05$. Theorem 6 then says that the output dimension $N$ is bigger than $\\epsilon^{-2}$ so bigger than 40,000, but in the experiment in Figure 1, $N$ is only 1000. Overall, this shows that Theorem 6 is not best possible and future work could attempt to determine what one can prove without the assumption that $\\epsilon<1- \\langle x, y\\rangle$. \n\nQuestion 2: We chose 6 experimentally. In particular, using 6 instead of 2 made the error significantly smaller. But, for example, using 8 or 10 instead of 6 offered no significant improvement.", "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": "MM0NG9Exlv", "reviewer": "Reviewer_mnzD", "summary": "This paper studies the bit complexity of storing the Euclidean distance between n points X up to (1 +- eps) error.  The simplest setting assumes all points have ||x||_2 = 1, and all results depend on the \"spread\" of the point set m = min_{x_1,x_2 in X} ||x_1 - x_2||.  \n\nA good comparison for their results is via a JL-random project embedding; the bits required for this is:\n   - O(n * (1/eps^2) log n * log(1/m eps)\n\nThe number of bits required for their approach is\n  - O(n * (1/eps^2) log n * log(1/m)^{2.3})", "questions": "none", "limitations": "N/A.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The main advantage of this approach is that it directly records the embedding as bit vectors (well as [-1, +1] vectors, plus an implicit scaling term depending on the dimension of the data].  \n\nThe paper appears technically interesting.  It introduces an idea of composing maps into bits instead of just a single map, which can show some technical improvement in theory and practice for small distances.", "weaknesses": "This might be of some independent interest, but as of now the improvement is quite minor.  \n\nThis paper reports a very small improvement in very limited cases.  \nIn particular, the improvement occurs when the desired error eps is much smaller than the spread parameter m; but typically for (1 +- eps) error, eps is a constant, so this seems of limited interest.   \n\nAs a result, I do not think it is worth publishing at NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weaknesses: We believe our theoretical contributions are substantial because of the new algorithmic ideas and because our upper bound nearly matches an existing lower bound. See the overall author rebuttal for more details.", "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": "YYfKnw5nEY", "reviewer": "Reviewer_f7H3", "summary": "The paper focuses on constructing sketches of point sets via (compositions of) random maps $\\varphi_l$ into the discrete cube $N^{-\\frac{1}{2}}\\{-1,1\\}^N$, and describes how to get an estimate of the squared Euclidean distance. The paper explains how the maps $\\varphi_l$ are constructed and motivate the choice based on properties of the functions $f, g$ , and has detailed proofs bounding the error of the sketch based on $l$. The paper discusses the limitations of $\\varphi_l$, i.e. there is an additive $\\epsilon\\|x - y\\|^{2-2^{1-l}}$ error ; hence for $\\|x - y\\| > 1$, $\\varphi_l, l > 1$ may not be optimal. There are experiments with simulated data to show how $\\epsilon$ varies, and how $l = 1, 2$ performs for nearest neighbor search, as well as nearest neighbor search with the RCV1 dataset. Based on the experiments, the paper summarizes conditions in when $l = 1$ and $l = 2$ should be used.", "questions": "- Li et al (Section 4) states \"In fact, when $\\theta$ is close to $0$ or $\\pi$, due to the high nonlinearity, the asymptotic variance formula is not reliable.\" Can the results of Theorem 6 (in this paper) show that if ``sign random projections\" were applied again, an angle $\\theta$ close to $0$ would have a lower variance (since a small $\\theta$ implies a small Euclidean distance)? \n\n- I am uncomfortable with line 472-473, \"Since $g_l(f_l(t)) = t$ ..., $g_l(\\langle\\varphi_l(x), \\varphi_l(y)\\rangle)$ should be a good approximation of $\\langle x, y\\rangle$\". I agree that $\\mathbb E{\\langle \\varphi^D(x), \\varphi^D(y)\\rangle} = f(\\langle x,y\\rangle)$, and also that $g(\\mathbb E{\\langle \\varphi^D(x), \\varphi^D(y)\\rangle}) = g(f(\\langle x,y\\rangle)) = \\langle x, y \\rangle$. But as the goal is to approximate $\\langle x,y\\rangle$ (and from it the Euclidean distance), $\\mathbb E{g({\\langle \\varphi^D(x), \\varphi^D(y)\\rangle})} \\neq g(\\mathbb E{\\langle \\varphi^D(x), \\varphi^D(y)\\rangle})$. Hence I am not sure if the bounds are as accurate (here, I am thinking of Taylor expansions of $\\mathbb E{g({\\langle \\varphi^D(x), \\varphi^D(y)\\rangle})}$, and bounding remainder terms). I might be wrong, and happy to be corrected. \n\nI have tried $\\|x-y\\| = 0.03$ with $l = 2$ in a similar experiment in Section 4.1, lines 304-325, and I do see the two layer map outperforming the one layer map, but the three layer map having poor performance compared to the two layer map. However, with a lower $\\|x-y\\| = 0.0003$, I see that the three layer map outperforms both the two layer map and the one layer map (using the choice of 50000->6000->1000), so the general idea is still right.\n\n- Are the true nearest neighbors the original neighbors, or the true nearest neighbors after projecting with a Gaussian random matrix for the experiments in Fig 3?\n\n- The left plot in Fig1 might be more informative when $\\epsilon$s are plotted within the unit circle in order to see comparisons for the one layer and two layer map for some fixed values of output dimension. E.g., plot the corresponding $\\epsilon$s for the one layer map / two layer map on the \"line\" parameterized by $(a, \\sqrt{1-a^2})$ as $a$ varies, so a reader can visually see the region where the one layer map performs better, and the two layer map performs better. Admittedly, this is only useful in 2D when it is easy to \"convert visually\" from angles to Euclidean distances. \n\n- A conclusion (or discussion section) that summarizes the ideas in Section 1 would be good as well - although I think this can be done by placing some parts of Section 1 at the end of the paper.\n\nReferences:\nLi et al: Improving Random Projections Using Marginal Information, COLT 2006", "limitations": "The authors address the main limitation when $\\varphi_l, l \\geq 2$ performs better.\n\nI like the ideas in this paper, and future work on sketching algorithm with quantization steps could potentially build on this, but the experimental results and discussion could be more convincing. \n\nMy score is motivated by the unit circle mentioned in the questions (comparing when a one layer map is better than two layer map) which shows a small \"slice\" where the two layer map is better. Broadly speaking, I cannot think of any application where it is desirable to have good estimates for points extremely close to each other, yet ensure false positives do not occur (i.e. that \"slice\" where the Euclidean distance is $< 0.06$). I am happy to raise my score if there are potential applications, experiments or discussion (niche but realistic cases are okay).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The sketching algorithm outlined here stores data as bits (on the discrete cube $\\{-1,1\\}^N$) (scaling factor can be applied after storage) ; this saves on space (compared to a sketching algorithm that stores data as doubles or floats)\n\n- Treating $\\varphi^D$ as the random map, the idea of applying $\\varphi^D$ repeatedly, and finding an appropriate ``inverse\" to recover the Euclidean distance is a nifty idea.\n\n- The paper is extremely clear, motivating random projection and sketching, as well as giving detailed proofs and explaining why each step was taking for w.h.p. bounds on the error of the sketch.\n\nTo summarize, I feel the strengths of this paper are putting together several ideas: linking the derivative of the function $g \\equiv \\sin(\\pi/2 t)$ to bounding the additive error of the approximation, and carefully explaining what happens if $\\varphi^D$ is applied multiple times.", "weaknesses": "- The one layer map $\\varphi_l$ (lines 111-113), if I am not mistaken, comes from the original sign random projections in [6] (Section 3, Random Hyperplane Based Hash Functions for Vectors). While this was originally used to estimate angles, Li et al (Section 4, Sign Random Projections) looked at estimating $a$ (which is $\\langle x,y \\rangle$ in the notation of this paper) using $\\arccos(..)$, given that the margins are known / data is normalized (which is equivalent to points being on $S^{d-1}$ in the notation of this paper). By the polarization identity, $\\|x-y\\|$ can be recovered directly from $\\langle x,y\\rangle$. The experiments run generally show that the one layer map is better than the two layer map, except in cases where $\\|x - y\\| \\leq 0.06$ (line 317), but this seems that the two layer map is only useful in very niche cases. It would be good if there is some reference to sign random projections when referring to the one layer map. Unfortunately, this means any novelty would be for the $l$ layer map, $l \\geq 2$. \n\n- The plots in Figure 1 show that $\\epsilon$ is generally larger than $\\|x - y\\|$. Moreover (line 317), the two layer map performs better when the Euclidean distance $\\|x-y\\| \\leq 0.06$, which corresponds to $\\theta_{x,y} < 0.06$. I am not exactly sure how realistic a two layer map would be. While it may accurately recover the true nearest neighbor, there may also be false positives, i.e. a point with a farther Euclidean distance but have an estimate that is \"closer\". \n\n- I found it difficult to replicate the experiment in Figure 3 ; since a quick Google search found the text dataset (not pre-processed into vectors). Moreover, I found the \"first project the data with a Gaussian random matrix to $\\mathbb R^{5000}$\" a bit puzzling (e.g. are the true nearest neighbors the original neighbors, or the true nearest neighbors after projecting with a Gaussian random matrix?)\n\n- I note that computing the second layer map took up substantially more time than just the first layer map (even with $D_1 = 6000, D_2 = 1000$), so I am not sure if the increase in computing time is worth the gain in less error. \n\n\nReferences:\nLi et al: Improving Random Projections Using Marginal Information, COLT 2006", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weakness 1: We agree and we only claim novelty in the case $l \\geq 2$; versions of the 1-layer map have been discussed in several papers. We will clarify the relationship with [6] (Charikar) and [Li et al, COLT 2006] when the maps are introduced. See overall author rebuttal for a discussion of the \"niche\" aspect.\n\nWeakness 2: We agree that there can be incorrect nearest neighbors after approximation. This issue seems to be inherent to any multiplicative approximation applied to nearest neighbors. Namely, given a query point and several points at nearly the same distance of the query point, any point could be returned as an approximate nearest neighbor. At the same time, because out theoretical guarantees are for multiplicative (and not just additive) error, some types of \"false positives\" are not possible. For example, if x is the query point and y is it's nearest neighbor at distance .05,  and there is a third point z at distance 1/2 from x, it is not possible for z to be misclassified as the nearest neighbor as long as the sketch succeeds.\n\nWeakness 3: The RCV1 dataset is available (in normalized vector form) in scikit-learn with the command from sklearn.datasets import fetch_rcv1. We also sent our code to the AC so that should be available now. Concerning the projection step, it is just for computational savings. The \"true nearest neighbors\" are the nearest neighbors after projection. To make the experiment simpler and more convincing, we rerun the experiment without projecting and obtained essentially the same result (see the attached pdf). We will update the experiment in the paper with the version without projection.\n\nQuestion 1: Our analysis shows that the additive error is small with high probability for multilayer maps and this suggests that the variance is smaller, but we do not have a formal argument for the variance.\n\nQuestion 2: The \"good approximation\" is in the sense of a small additive error with high probability. We do not need the approximation to be \"unbiased.\" Namely, we are using  $\\langle \\varphi_\\ell(x),\\varphi_\\ell(y)\\rangle$  as an estimator of $f_\\ell(\\langle x,y \\rangle )$. But we are not claiming that  $E \\langle \\varphi_\\ell(x),\\varphi_\\ell(y)\\rangle $ is equal to $f_\\ell(\\langle x,y \\rangle )$. However, one of our main results (Theorem 5) shows that it is a good estimator in an additive sense as long as dimensions are large. This \"additive approximation\" interpretation is clarified in the next sentence (473-474).\n\nQuestion 3: The \"true nearest neighbors\" are the nearest neighbors after projection.\n\nQuestion 4: From Figure 1, we see that the  distance threshold at which the 2-layer map becomes better than the 1-layer map is approximately $\\|x-y\\| = .06$. This corresponds to $\\langle x,y \\rangle \\approx .998 $ and $\\Theta_{x,y}\\approx .06$. \n\nQuestion 5: This is a good suggestion, we will add a conclusion in the manner suggested. \n\nLimitations: \nPlease see the overall author rebuttal for a discussion of the significance of the theoretical and experimental contributions. Building on what we wrote in \"Weakness 2\" above, some kinds of false positives are impossible because our approximation guarantee is multiplicative and other kinds of false positives are intrinsic to any comparable kind of approximation.\n\nWe agree that there is only a small \"slice\" where 2-layers is better, i.e. when the minimum distances is <.06. However, because we estimate distances up to a multiplicative $(1\\pm\\epsilon)$ error, the risk of false positives is not any larger in that scenario than it is for the datasets where minimum distances are much larger. So the question of the applicability of the 2-layer map is essentially the question of the existence of datasets where minimum distances tend to often be smaller than .06. This is rare, but it does happen. Our example is the RCV1 dataset which does have pairs of points at distance <.06. Figure 3 (and the updated experiment in the attached pdf) demonstrate that 2-layers does perform better for the 1-nearest neighbor.", "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:
We thank the reviewers for your constructive and helpful feedback. We have the following comments about our contributions and the experiments for all the reviewers:

The main contribution of the paper is theoretical, including algorithmic ideas and their analysis. We believe we have strong contributions and novelty there. Our contributions are about a very basic algorithmic problem: the approximation of distances up to a multiplicative $1\pm\epsilon$ error. While compared to existing upper bounds (algorithms) our improvement appears modest, it is very strong if one takes into account the known lower bounds. Namely, our algorithm's upper bound is very close to being optimal because it matches the lower bound up to the power of the $\log(1/m)$ factor. As we explain in section 1.4, it is known that for the one-way communication version of the sketching/compression problem,
$$
\Omega(\epsilon^{-2}n \log(n/\delta) \log(1/m))
$$
bits are necessary if the algorithm is to be successful with probability $1-\delta$ and $m$ is the minimum distance. Our technique uses
$$
\Theta(\epsilon^{-2}n \log(n) \log(1/m)^{2.3})
$$
bits. When $m$ is asymptotically smaller than $\epsilon$, this is closer to the lower bound than the number of bits one needs if using regular Johnson Lindenstrauss random projection which requires
$$
\Theta(\epsilon^{-2}n \log(n) \log(1/m\epsilon)).
$$
Please see the discussion in Section 1.4 for additional details.

The intent of the experiments is not to show that the proposed algorithm is an improvement in practice; it is to show that the ideas are actually implementable and have a complexity that is within the realm of other methods (i.e. it is not orders of magnitude worse). The experiments also validate the theoretical idea of "composing maps" (depth) in the following sense: They show that the 2-layer map is better than the 1-layer map for reasonable values of the parameters. To make this point stronger, we also show a real world dataset (RCV1) where the 2-layer map is better than the 1-layer map. We redid the experiment with the RCV1 dataset (i.e., Figure 3 in the paper) without first projecting the data to $\mathbb{R}^{5000}$, please see the plots in the attached PDF. The result is essentially the same as the original experiment, but is somewhat more convincing because now we are recovering the true nearest neighbors of query points in RCV1 rather than the nearest neighbors according to the projected data.

Meta-review: This paper studies the problem of compressing/sketching a set of points while approximately preserving the pairwise Euclidean distances. The paper proposes a method based on the idea of ell-fold composition of a feature mapping, or a multi-layer mapping. The paper shows that the number of bits needed by the proposed sketching algorithm is theoretically smaller than what is needed by a standard JL random map in some parameter regimes. While the contribution of the paper is mainly theoretical, the proposed method is elegant and simple to implement. Some experiments are provided to validate the idea of composing maps and to show that the 2-layer map is better than the 1-layer map.

The reviewers agree that the theoretical contribution of the paper is interesting. The disagreement is basically about the practical relevance of the proposed method and, consequently, whether it is a good fit for NeurIPS. Since theory is one of the listed topics in the NeurIPS call for papers, and sketching techniques should be of interest to some part of the community, I recommend acceptance.
Decision: Accept (poster)