Euclidean distance compression via deep random features

Authors: brett  leroux
luis  rademacher
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:44:19

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.

Main paper: 
 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 a high-dimensional set of points in R d to a 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 a variety of prominent algorithms [11, 17, 5, 8] including nearest neighbor search [13, 12] .The theoretical foundation of random projection is the Johnson-Lindenstrauss lemma which states that a random orthogonal projection to a lower dimensional subspace has the property of preserving pairwise distances and inner products [16] . Later it was observed [9, 13] that one can alternatively take the projection matrix to be a matrix with i.i.d. Gaussian N (0, 1) entries. Lemma 1 ([9, 13, 30] ). Let each entry of an d × k matrix R be chosen independently from N (0, 1).Let v = 1 √ k R T u for u ∈ R d .Then for any ϵ > 0, P ∥v∥ 2 -∥u∥ 2 ≥ ϵ∥u∥ 2 < 2e -(ϵ 2 -ϵ 3 )k/4 .A corollary of the above lemma is that if an arbitrary set of n points in R d is mapped by the random projection matrix R to R k where k = Θ(ϵ -2 log 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 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 now instead be performed on the lower dimensional points.The second main advantage of the lower dimensional representation is a reduction in the cost of data storage. The Johnson-Lindenstrauss lemma shows that random projection of a point set S produces 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-Lindenstrauss lemma gives an upper bound on the size of such a sketch as follows: Any set of n points S can be projected to R k where k = Θ(ϵ -2 log n) while distorting pairwise squared distances by a factor of at most (1 ± ϵ). 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 k : In order to preserve squared distances up to a multiplicative (1 ± ϵ) error, it suffices to preserve squared distances up to an additive m 2 ϵ 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 2 ϵ-net, we can produce a sketch with Θ nϵ -2 log n log(1/m 2 ϵ) bits. 1While the Johnson-Lindenstrauss lemma shows that efficient sketches can be obtained by mapping the points to a lower dimensional space with a random linear mapping (the projection), it is 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 our main result first for sets of points contained in the unit sphere S d-1 and at the end of this section we include the extension to subsets of the unit ball. EQUATION2) (defined in the proof of Theorem 5 and independent of S except through parameters n, d, m and min x,y∈S,x̸ =y 1 -|⟨x, y⟩|) satisfies the following with probability at least (1 -2 n ) ℓ : φ ℓ (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 ± ϵ) error. The number of bits of the sketch isΘ n log n ϵ 2 (log 1 m ) 2 log 2 (π/ √ 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 φ ℓ 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 φ ℓ produces sketches with asymptotically fewer bits than those obtained using the Johnson-Lindenstrauss lemma if (log( 1 m )) 2 log 2 (π/ √ 2) = o log( 1 m 2 ϵ ) . This is equivalent to the condition that (log( 1 m )) 2 log 2 (π/ √ 2) = o log( 1 ϵ) . Furthermore, the sketch φ ℓ (S) has the desired properties "with high probability". The probability that the sketch succeeds is (1 -2/n) ℓ 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 n = Ω(d). We also take ϵ = Ω(d -1/2 ) (ignoring logarithmic factors) because otherwise the target dimension N is larger than d and then a sketch based on an ϵ-net (as above, but without random projection) for S would be better, by having bitlength nd (up to logarithmic factors). The assumption that ϵ < 1 -|⟨x, y⟩| for all x, y, x ̸ = y means that ϵ < m 2 and so1/m < ϵ -1/2 = O(d 1/4 ). This means that ℓ = O(log 2 log 2 d) and so (1 -2/n) ℓ = Ω(1 -2/d) ℓ approaches one.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 B d we use x to denote x/∥x∥. 2) (defined in the proof of Theorem 5 and independent of S except through parameters n, d, m and min x,y∈S,x̸ =y 1 -|⟨x, ŷ⟩|) satisfies the following with probability at least (1 -2 n ) ℓ : φ ℓ ( Ŝ) and the norm of each point in S up to an additive ±ρm 2 ϵ/48 error is a 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 isEQUATIONΘ n log n ϵ 2 log 1 m 2 log 2 (π/ √ 2) + n log 1 ρm 2 ϵ .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 Johnson-Lindenstrauss lemma because the Johnson-Lindenstrauss sketches do not rely on any normalization step. However, as in the case of point sets on S d-1 , there is a large family of point sets in B d for which our sketching technique produces sketches with a fewer number of bits.1.1 The maps φ ℓ and the recovery of ∥x -y∥ 2 by φ ℓ (x) and φ ℓ (y)In this section we summarize the construction of the maps φ ℓ which are used in Theorem 2 and formally analyzed in Theorem 5 and how they can be used to recover squared distances between points. Let f (t) = 2 π arcsin(t) and g(t) = sin( πt 2 ). So f : [-1, 1] → [-1, 1] is the inverse of g : [-1, 1] → [-1, 1]. For ℓ ∈ N + ,let f ℓ be the function f composed with itself ℓ times and similar for g ℓ . Notice that for anyℓ ∈ N + , f ℓ : [-1, 1] → [-1, 1] is the inverse of g ℓ : [-1, 1] → [-1, 1].For simplicity in the rest of the introduction we assume all points are normalized to be on the unit sphere S d-1 . We define the sign function assign(t) = 1 if t ≥ 0 -1 if t < 0.The maps φ ℓ will be defined as the composition of ℓ maps of the following form.Set D ∈ N + . Let Z i , 1 ≤ i ≤ D be i.i.d. standard Gaussian random vectors in R d . Let φ D : R d → R D be defined by φ D (x) i := D -1/2 sign(⟨x, Z i ⟩)where φ D (x) i is the ith coordinate of φ D (x). 2 The maps φ ℓ are now defined as the ℓ-fold composition of maps of the type φ D . That is, for some integers D 1 , D 2 , . . . , D ℓ , we let φ 1 :S d-1 → D -1/2 1 {-1, 1} D1 be defined by φ 1 (x) = φ D (x). For j ∈ {1, . . . , ℓ -1}, we let φ j+1 (x) = φ Dj+1 (φ j (x)). Therefore, the map φ ℓ maps S d-1 to D -1/2 ℓ {-1, 1} D ℓ .To avoid writing the double subscript we write the final dimension of the map as D ℓ = N . We remark that the map φ ℓ can also be defined as a standard neural network with ℓ hidden layers using activation function sign(t) and having all weights be i.i.d. standard Gaussian random variables.It was shown in [26] that for x, y ∈ S d-1 , E sign(⟨x, Z 1 ⟩) sign(⟨y, Z 1 ⟩) = f (⟨x, y⟩). Since ⟨φ D (x), φ D (y)⟩ is a sum of D independent copies of D -1 sign(⟨x, Z⟩) sign(⟨y, Z⟩) we get that E⟨φ D (x), φ D (y)⟩ = f (⟨x, y⟩). Now we can explain how one recovers pairwise distances between points in S from φ ℓ (S). Let S be a set of n points in S d-1 ⊂ R d . As in Theorem 2, we map S by φ ℓ :S d-1 → N -1/2 {-1, 1} N .Here ℓ is some parameter which is chosen based on S that is explained below and N is chosen based on the desired ϵ error of the sketch. If the remaining integers D 1 , . . . , D ℓ-1 are chosen properly, then we show that ⟨φ ℓ (x), φ ℓ (y)⟩ is a good approximation of f ℓ (⟨x, y⟩) (Corollary 4). Since g ℓ is the inverse of f ℓ this implies that g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) should be a good approximation of ⟨x, y⟩. By the polarization identity, this implies that 2 -2g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) should be a good approximation of ∥x -y∥ 2 . So recovering ∥x -y∥ 2 from φ ℓ (S) simply involves calculating 2 -2g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩).In the next section we explain why this mapping and recovery scheme leads to good error guarantees.Now that we have defined the maps φ ℓ 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 g ℓ near t = 1. As previously mentioned, the map φ ℓ has the property that for all x, y ∈ S,EQUATIONfor some δ depending on N . Now when we want to recover ∥x -y∥ 2 based on φ ℓ (x) and φ ℓ (y), by the polarization identity, we use 2 -2g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) as an estimate of ∥x -y∥ 2 . The additive error of the approximation of ∥x -y∥ 2 by 2 -2g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) depends on the error in Eq. ( 1) as well as the derivative of g ℓ near the point f ℓ (⟨x, y⟩). The function g ℓ has the property that its derivative approaches zero as t approaches one and so the additive error of the approximation of ∥x -y∥ 2 by 2 -2g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) gets smaller the closer f ℓ (⟨x, y⟩) (and thus ⟨x, y⟩) is to one, i.e., the closer ∥x -y∥ 2 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 we actually approximate ∥x -y∥ 2 up to a multiplicative error.The role of the parameter ℓ in this construction is in controlling the rate at which g ′ ℓ (t) approaches zero as t approaches one. If there are pairs x, y such that ∥x -y∥ 2 is very small then we need the derivative to approach zero very quickly. This can be done by increasing the parameter ℓ; the rate at which g ′ ℓ approaches zero is faster for larger values of ℓ (see Theorem 7 in Appendix B). It turns out that the correct choice of ℓ is ⌈log 2 log 2 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 ℓ as the number of layers of the random mapping.We remark that the function g ℓ (t) has the property that its derivative can be as large as ≈ ( π 2 ) ℓ when t is near zero (see Lemma 8 in Appendix B). The effect that this has is that our algorithm leads to worse approximation of ∥x -y∥ 2 when ⟨x, y⟩ is close to 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 ⟨x, y⟩ is close to one outweighs the loss in accuracy when ⟨x, y⟩ is close to zero.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 a 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 a "deep" composition of 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 Johnson-Lindenstrauss lemma due to [1] (where the entries of the matrix are all either +1 or -1) is particularly important for the following reason. As discussed in [15] , an alternate way to convert sketches obtained by the Johnson-Lindenstrauss lemma to bits is possible if the points have bounded integer coordinates and one uses the binary variant of Johnson-Lindenstrauss lemma. This approach is somewhat incomparable to our setting because of the integrality assumption.Another variation on the random projection technique is to apply a quantization step after the projection which further reduces the cost of storing the data points [6, 21, 24, 29, 4, 10, 18, 25, 32] . A particularly relevant version of quantization is "sign random projections" [6] . Sign random projections are the same as the 1-layer maps φ 1 . 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.Random mappings are of course not the only way to compress a 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 as we explain below, can produce sketches with fewer bits.Given a set of n points in the unit ball in R d , what is the minimum number of bits of a sketch which allows one to recover all pairwise distances up to a multiplicative (1 ± ϵ) error? As explained above, the Johnson-Lindenstrauss lemma shows that O ϵ -2 n log n log(1/m 2 ϵ) bits suffice. However, this 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 O ϵ -2 n log n + n log log(1/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 n log n log(1/m) bits suffice [19] . These two results, however, use sketching techniques that differ from the sketches obtained by the random projection technique in a 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.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 problem, 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 message. It was shown in [27] that if the points are in the unit ball and the minimum distance is m, then Ω ϵ -2 n log(n/δ) log(1/m) bits are required for the one-way communication version of the problem if the sketch is required to be successful with probability at least 1 -δ.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 to 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 2 isΘ(ϵ -2 n log n(log(1/m)) 2 log 2 (π/ √ 2)). Thus our number of bits matches the lower bound from [27] up to the power on the log(1/m) term. This motivates the question of whether some variation on our sketching technique can reduce this power.Section 2 contains the construction of the maps φ ℓ and quantifies the error in the approximation of f ℓ (⟨x, y⟩) by ⟨φ ℓ (x), φ ℓ (y)⟩. Then in Section 3 we explain how the proof of Theorems 2 and 3 is completed. This amounts to showing how ⟨φ ℓ (x), φ ℓ (y)⟩ allows one to estimate ∥x -y∥ 2 and quantifying the error 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 x ∈ R d \{0} we use x to denote x/∥x∥. For x, y ∈ S d-1 , the polarization identity states that 2 -2⟨x, y⟩ = ∥x -y∥ 2 ; for arbitrary x, y ∈ R d , it states that ∥x∥ 2 + ∥y∥ 2 -2⟨x, y⟩ = ∥x -y∥ 2 .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract summarizes the main theoretical results of the paper and indicates their significance while also acknowledging that in some situations, other pre-existing methods are better. We also point out that experiments back up 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 in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
the construction of the maps φ ℓ: 
 The purpose of this section is to prove the following result, Corollary 4, which shows a bound on the error of the approximation of f ℓ (⟨x, y⟩) by ⟨φ ℓ (x), φ ℓ (y)⟩ for all pairs x, y in a set of n points. The error in this approximation depends on the dimension D ℓ of the image space of φ ℓ . In particular, we show how large D ℓ needs to be in order to guarantee with high probability that ⟨φ ℓ (x), φ ℓ (y)⟩ is equal to f ℓ (⟨x, y⟩) up to some additive error δ for all pairs x, y.We recall the definitions of the functions f ℓ and g ℓ : Let f (t) = 2 π arcsin(t) and g(t) = sin( πt 2 ). For ℓ ∈ N + , let f ℓ be the function f composed with itself ℓ times and similar for g ℓ . Notice that for anyℓ ∈ N + , f ℓ : [-1, 1] → [-1, 1] is the inverse of g ℓ : [-1, 1] → [-1, 1]. Corollary 4. Let S ⊂ S d-1 with |S| = n ≥ 2. Let r := max x,y∈S,x̸ =y 2 √ 1-|⟨x,y⟩| . Let ℓ ∈ N + . Let δ > 0 be such that δ < 2 r 2 .Then there exists a random map φ ℓ :R d → D -1/2 ℓ {-1, 1} D ℓ (independent of S except through parameters n, d, r) such that with probability (1 -1 n ) ℓ it satisfies ⟨φ ℓ (x), φ ℓ (y)⟩ -f ℓ (⟨x, y⟩) < δ for all x, y ∈ S, where D ℓ ≤ ⌈ 24 log n δ 2 ⌉.The above corollary follows immediately from the following theorem which also determines a bound on the error of the approximation accuracy not only of f ℓ (⟨x, y⟩) by ⟨φ ℓ (x), φ ℓ (y)⟩, but also the approximation accuracy of f j (⟨x, y⟩) by ⟨φ j (x), φ j (y)⟩ for all j ∈ {1, . . . , ℓ}.Theorem 5. Let S ⊂ S d-1 with |S| = n ≥ 2. Let r := max x,y∈S,x̸ =y 2 √ 1-|⟨x,y⟩| . Let ℓ ∈ N + .Let δ > 0 be such that δ < 2 r 2 . Then there exist random maps φ j : R d → D -1/2 j {-1, 1} Dj , j ∈ {1, . . . , ℓ} (independent of S except through parameters n, d, r) such that for all j ∈ {1, . . . , ℓ}, with probability at least (1EQUATIONfor all x, y ∈ S, where D j ≤ 24•2 2(ℓ-j) r 6((2/3) j -(2/3) ℓ ) log n δ 2.Proof. The maps φ j will be compositions of maps of the following form.Set D ∈ N + . Let Z i , 1 ≤ i ≤ D be i.i.d. standard Gaussian random vectors in R d . Let φ D : R d → R D be defined by φ D (x) i := D -1/2 sign(⟨x, Z i ⟩),where φ D (x) i is the ith coordinate of φ D (x). A direct calculation, see [26] , shows thatE⟨φ D (x), φ D (y)⟩ = f (⟨x, y⟩). Furthermore, ∥φ D (x)∥ = 1 for all x ∈ R d .First we use this construction to define φ 1 . We let φ 1 = φ D1 where D 1 is chosen below. Using Hoeffding's inequality, for all x, y ∈ S,P ⟨φ(x), φ(y)⟩ -f (⟨x, y⟩) > δ 2 ℓ-1 r 3((2/3)-(2/3) ℓ ) = P D 1 ⟨φ(x), φ(y)⟩ -D 1 f (⟨x, y⟩) > D 1 δ 2 ℓ-1 r 3((2/3)-(2/3) ℓ ) ≤ 2 exp - D 1 δ 2 2 • 2 2(ℓ-1) r 6((2/3)-(2/3) ℓ ) . We set D 1 = 6•2 2(ℓ-1) r 6((2/3)-(2/3) ℓ ) log n δ 2. This means that the above probability is less than 2/n 3 and that φ 1 satisfies the conditions of the theorem with probability at least 1 -n2 2 n 3 ≥ 1 -1/n ≥ 1 -2/n.Now assume that the required map exists for some j ≥ 1. We will show that it exists for j + 1. So there exists a map φ j : R d → D -1/2 j {-1, 1} Dj which satisfies Eq. ( 2) with probability at least (1 -2 n ) j . Let φ j+1 be defined by φ j+1 (x) = φ Dj+1 φ j (x) where D j+1 will be chosen at the end of the proof. We will show that, conditioned on the event that φ j does satisfy Eq. ( 2), the probability that φ j+1 satisfies Eq. ( 2) is at least 1 -2 n . So assume that φ j does satisfy Eq. ( 2). Recall that we want to show that ⟨φ j+1 (x), φ j+1 (y)⟩ is a good estimate of f j+1 (⟨x, y⟩). We have by [26] that E⟨φ j+1 (x), φ j+1 (y)⟩ = f (⟨φ j (x), φ j (y)⟩), i.e., ⟨φ j+1 (x), φ j+1 (y)⟩ is an unbiased estimator of f (⟨φ j (x), φ j (y)⟩). By the triangle inequality, ⟨φ j+1 (x), φ j+1 (y)⟩ -f j+1 (⟨x, y⟩)≤ ⟨φ j+1 (x), φ j+1 (y)⟩ -f (⟨φ j (x), φ j (y)⟩) + f (⟨φ j (x), φ j (y)⟩) -f (f j (⟨x, y⟩)) .(3) First we give a bound on the second term in Eq. ( 3). We are assuming that φ j satisfies Eq. ( 2), i.e., that for all x, y ∈ S,⟨φ j (x), φ j (y)⟩ -f j (⟨x, y⟩) ≤ δ 2 ℓ-j r 3((2/3) j -(2/3) ℓ ) .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 ⟨φ j (x), φ j (y)⟩ and f j (⟨x, y⟩). We claim for all pairs x, y ∈ S, x ̸ = y, the derivative of f in the interval between ⟨φ j (x), φ j (y)⟩ and f j (⟨x, y⟩) is upper bounded by r (2/3) j .Let t be in the closed interval between ⟨φ j (x), φ j (y)⟩ and f j (⟨x, y⟩). By definition of φ j and f j this implies |t| ≤ 1. We also have |t| ≤ |f j (⟨x, y⟩)| + δ/2 ℓ-j r 3((2/3) j -(2/3) ℓ ) ≤ |f j (⟨x, y⟩)| + δ by Eq. ( 2) and the fact that r ≥ 2 by definition. Thus,1 -|t| ≥ 1 -|f j (⟨x, y⟩)| -δ ≥ (1 -|⟨x, y⟩|) (2/3) j -δ by Lemma 10 in Appendix B ≥ (1 -|⟨x, y⟩|) (2/3) j 2 by δ < 2 r 2 ≤ (1 -|⟨x, y⟩|) 2 ≤ (1 -|⟨x, y⟩|) (2/3) j 2 .Using this and |t| ≤ 1, we getf ′ (t) = 2 π √ 1 -t 2 ≤ 2 π 1 -|t| ≤ 2 √ 2 π 1 -|⟨x, y⟩| (2/3) j ≤ 2 √ 2r (2/3) j π < r (2/3) j .We have shown that the derivative of f in the interval between ⟨φ j (x), φ j (y)⟩ and f j (⟨x, y⟩) is upper bounded by r (2/3) j . This combined with Eq. ( 2) and the fact that the derivative of f is positive implies thatf (⟨φ j (x), φ j (y)⟩) -f (f j (⟨x, y⟩)) ≤ r (2/3) j δ 2 ℓ-j r 3((2/3) j -(2/3) ℓ ) = δ 2 • 2 ℓ-(j+1) r 3((2/3) j+1 -(2/3) ℓ ), where the equality above uses that 3 (2/3) j -(2/3) ℓ = ℓ-1 i=j (2/3) j . Now we deal with the first term in Eq. (3). Using Hoeffding's inequality,P ⟨φ j+1 (x), φ j+1 (y)⟩ -f j+1 (⟨x, y⟩) > δ 2 • 2 ℓ-(j+1) r 3((2/3) j+1 -(2/3) ℓ ) = P D j+1 ⟨φ j+1 (x), φ j+1 (y)⟩ -D j+1 f j+1 (⟨x, y⟩) > D j+1 δ 2 • 2 ℓ-(j+1) r 3((2/3) j+1 -(2/3) ℓ ) ≤ 2 exp - δ 2 D j+1 8 • 2 2(ℓ-(j+1)) r 6((2/3) j+1 -(2/3) ℓ ) . We set D j+1 = ⌈ 24•2 2(ℓ-(j+1)) r 6((2/3) j+1 -(2/3) ℓ ) log n δ 2⌉. This means that the above probability is less than 2/n 3 . 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 ∈ S,⟨φ j+1 (x), φ j+1 (y)⟩ -f j+1 (⟨x, y⟩) < δ 2 ℓ-(j+1) r 3((2/3) j+1 -(2/3) ℓ )with probability at least 1 -2 n 3 . So, conditioned on the event that φ j satisfies Eq. ( 2), φ j+1 satisfies Eq. ( 2) with probability at least 1 -2 n . Since the probability that φ j+1 satisfies Eq. ( 2) is greater than or equal to the probability that both φ j+1 and φ j satisfy Eq. ( 2), this means that the probability that φ j+1 satisfies Eq. ( 2) is at least 3 The recovery of ∥x -y∥ 2 by φ ℓ (x) and φ ℓ (y)(1 -2 n ) j+1 .Here we explain how the proofs of the main theorems, Theorems 2 and 3 are completed. This is done in two steps. Recall that we showed in Corollary 4 that ⟨φ ℓ (x), φ ℓ (y)⟩ is a good approximation of f ℓ (⟨x, y⟩) for all pairs x, y ∈ S. The first step is Theorem 6 which shows that g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) is a good approximation of ⟨x, y⟩. The reason this is true is because g ℓ is the inverse of f ℓ . So the proof of Theorem 6 uses facts about the derivative of g ℓ (in particular Theorem 7 in Appendix B) to show that the bound on the error of the approximation of f ℓ (⟨x, y⟩) by ⟨φ ℓ (x), φ ℓ (y)⟩ implies a bound on the error of the approximation of ⟨x, y⟩ by g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) (Theorem 6).The second step is to set ℓ = ⌈log 2 log 2 4 m ⌉ where m is the minimum distance between pairs of distinct points in 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 in Appendix A. Theorem 6. Let S ⊂ S d-1 with |S| = n. Let ℓ ∈ N + and ϵ > 0 and assume that ϵ satisfies ϵ < 1 -|⟨x, y⟩| for all x, y ∈ S with x ̸ = y. Then the random map φ ℓ : S d-1 → N -1/2 {-1, 1} N from Theorem 5 satisfies that, with probability at least (1 -2/n) ℓ , for all x, y ∈ S, g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) is equal to ⟨x, y⟩ up to an additive ±ϵ∥x -y∥ 2-2 -ℓ+1 error whereN = 48(π/ √ 2) 2ℓ log n ϵ 2 .Equivalently, for all x, y ∈ S, 2 -2g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) is equal to ∥x -y∥ 2 up to an additive ±ϵ∥x -y∥ 2-2 -ℓ+1 error.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: In the paragraph after Theorem 2 we explain the range of parameters for which our maps use fewer bits than the Johnson-Lindenstrauss style maps. Furthermore, in section 4.1 we explain how our maps φ ℓ for ℓ ≥ 2 may only be useful in certain applications. (In particular, for point sets where there are many very close pairs of points.) Guidelines:• The answer NA means that the paper has no 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 a 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 authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In 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 approach. 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-text 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 address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 (d) We recognize that reproducibility may be tricky in some cases, in which case authors 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 be possible for other researchers to have some path to reproducing or verifying the results. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 error term ±ϵ∥x -y∥ 2-2 -ℓ+1 in Theorem 6 which is smaller for larger values of ℓ as long as ∥x -y∥ < 1. Recall that we refer to the parameter ℓ as the number of layers of the random mapping. In our experiments, we will focus on comparing the one layer maps φ 1 to the two layer maps φ 2 . First we do a simple experiment to determine more specifically under what conditions we should expect two layers to outperform one. Then we apply the maps to nearest neighbor search and again compare the performance of one layer to two layers.As already mentioned, Theorem 6 indicates that the additive error obtained by the one layer map is proportional to ∥x -y∥ and the additive error obtained by the two layer map is proportional to ∥x -y∥ 3/2 . Therefore, two layers should give better error estimates than one layer when ∥x -y∥ is sufficiently small. Our first experiment answers the following question; how small must ∥x -y∥ be so that two layers outperform one? We consider pairs of points x, y ∈ S d-1 where ∥x -y∥ ranges from .01 to .1. We will see in this experiment that the input dimension has little to no effect and so we can without loss of generality assume d = 2. In the d = 2 case we take x = (1, 0) and y = (a, √ 1 -a 2 ) where a is chosen so that ∥x -y∥ ranges from .01 to .1 in increments of .005, see Fig. 1 . We map x, y by both maps φ 1 and φ 2 where the output dimension of both maps is 1000 and φ 2 first maps to {-1, 1} 6000 . In Fig. 1 we plot the average over 4000 trials of the value of ϵ such that 2 -2g 1 (⟨φ 1 (x), φ 1 (y)⟩) and 2 -2g 2 (⟨φ 2 (x), φ 2 (y)⟩) approximate ∥x -y∥ 2 up to a multiplicative (1 ± ϵ) error. We see in Fig. 1 that the two layer map gives a better approximation of ∥x -y∥ 2 when ∥x -y∥ ≤ .06 and the one layer map gives a better approximation of ∥x -y∥ 2 when ∥x -y∥ > .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 a distance. However, very large datasets may be more likely to have distances in the range where two layers is better. We do this same experiment when d = 2000 except for d = 2000 we choose the input points randomly: We let x be uniform on S d-1 and set y = z/∥z∥ where z = x + (dist/ √ d)N (0, I d ) and dist ranges from .01 to .1. With this choice, E ∥x -y∥ ≈ dist. Because there is no dependence on the input dimension in our error bounds, we expect the error to depend on ∥x -y∥ but not d, which is verified in Fig. 1 .Given a set of points and a 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/classification problems. Before performing nearest neighbor search, some dimensionality reduction or compression method can be used to reduce the computational cost. We test the performance of our maps φ ℓ for this task.Again we focus on ℓ = 1, 2. Given a data set D and a query point X ∈ D, we first map D by φ 1 and φ 2 to N -1/2 {-1, 1} N . We then calculate the k nearest neighbors of X according to the compressed data and compare how many of the true k nearest neighbors of X in D are recovered.Randomly generated data. We let X 0 (the query point) be a uniform random vector on the unit sphere S 2 . Then for i ∈ {1, 2, . . . , 100}, we let Y i = X 0 + (4/5)(i/200)N (0, I 3 ) where N (0, I 3 ) ⊂ R 3 is from the multivariate normal distribution (and the Y i are independent). The constants are chosen so that E ∥X 0 -Y i ∥ ≈ i/200. Then the data D is defined to be X 0 along with {Y i /∥Y i ∥} i∈{1,100} . We map D by φ 1 and φ 2 where the output dimension ranges from 2 3 to 2 13 and φ 2 first maps to the space of dimension six times the output dimension. We also map D by a standard Gaussian random matrix to R d with the same range of output dimensions. The average number of k nearest neighbors recovered is shown in Fig. 2 . As is to be 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. Real data. We perform a similar experiment with the RCV1 dataset [20] . The RCV1 data set consists of 804414 samples and 47236 features. We only consider the first 23149 samples which have been previously designated as the training set. As query points, we select all data points which have at least one neighbor at distance less than .05. There are 179 such points. The RCV1 dataset consists of unit norm vectors. This is our data set D. We map D by φ 1 and φ 2 where the output dimension ranges from 2 3 to 2 11 and φ 2 first maps to the space of dimension six times the output dimension. We also map D by a standard Gaussian random matrix to R d with the same range of output dimensions. The average number of k 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 is sufficiently large. This again confirms expectations based on Fig. 1 . In the k = 4 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 at distance at most .05, the other three out of the four nearest neighbors may be at a significantly greater distance. Therefore, again considering Fig. 1 , it is not surprising that the one layer map gives a better approximation of the four nearest neighbors. 
conclusion: 
 We introduced a new method for compressing point sets while maintaining information about approximate distances between pairs of points. The method compresses point sets using a composition φ ℓ 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 a multiplicative (1 ± ϵ) error. The reason that we get multiplicative rather than additive error guarantees is a direct result of composing multiple random feature maps and has to do with the behavior of the derivative of the function g ℓ (introduced in Section 1.1) near t = 1. We also validate the idea of composing multiple random feature maps experimentally. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: We do not report error bars. But because of the simplicity of the randomness inherent in our experiments, it is clear that they are significant simply because we perform a sufficient number of independent trials. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is 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 are out of range (e.g. negative error 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: We ran experiments on a 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, or 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]• Depending on the country in which research is conducted, IRB approval (or equivalent) 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. 
 
 Appendix: Proof of Theorem 6. We will actually prove the stronger result that with probability at least (1 -2/n) ℓ , for all x, y ∈ S, g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) is equal to ⟨x, y⟩ up to an additive ±ϵ(2-2|⟨x, y⟩|) 1-2 -ℓ error. This statement implies the theorem statement by the polarization identity.Set δ = (ϵ/ √ 2)( √ 2/π) ℓ in Theorem 5.One can check that the assumption that ϵ < 1 -|⟨x, y⟩| for all x, y ∈ S with x ̸ = y implies that δ < 2/r 2 for all x, y ∈ S with x ̸ = y as required by Theorem 5. From Theorem 5, the map φ ℓ : R d → 1EQUATIONfor all x, y ∈ S whereN = 48(π/ √ 2) 2ℓ log n ϵ 2. Now assume that φ ℓ does satisfy Eq. ( 4) for allx, y ∈ S. Since g ℓ f ℓ (t) = t for all t ∈ [-1, 1], Eq. ( 4) implies that g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) should be a good approximation of ⟨x, y⟩. In particular, we claim that for all x, y ∈ S, g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) is equal to ⟨x, y⟩ up to an additive error of ±ϵ(2 -2|⟨x, y⟩|) 1-2 -ℓ . In order to show this we first need to get a bound on the derivative of g ℓ in the interval between ⟨φ ℓ (x), φ ℓ (y)⟩ and f ℓ (⟨x, y⟩).Let t be in the interval between ⟨φ ℓ (x), φ ℓ (y)⟩ and f ℓ (⟨x, y⟩). By Theorem 7,g ′ ℓ (t) ≤ π ℓ 2 ℓ+1 2 2 -2g ℓ (|t|) 1-2 -ℓ.By Eq. ( 4), we have thatEQUATIONπ ) ℓ . By Lemma 8 this means that g ℓ |f ℓ (⟨x, y⟩)| -g ℓ (|t|) ≤ √ 2ϵ( √ 2/π) ℓ (π/2) ℓ ≤ ϵ, i.e. that g ℓ (|t|) ≥ g ℓ |f ℓ (⟨x, y⟩)| -ϵ. Since f is an odd function, f ℓ (t) is also an odd function and so g ℓ |f ℓ (⟨x, y⟩)| = g ℓ f ℓ (|⟨x, y⟩|) = |⟨x, y⟩|. So we have shown that g ℓ (|t|) ≥ |⟨x, y⟩| -ϵ. Since ϵ < 1 -|⟨x, y⟩|, we have that 2 -2g ℓ (|t|) ≤ 2 -2|⟨x, y⟩| + 2ϵ < 2(2 -2|⟨x, y⟩|). Using that 2 1-2 -ℓ ≤ 2, this means that g ′ ℓ (t) ≤ π ℓ 2 ℓ+1 2 2 -2g ℓ (|t|) 1-2 -ℓ ≤ √ 2 π √ 2 ℓ (2 -2|⟨x, y⟩|) 1-2 -ℓ .This bound on the derivative along with the fact that g ′ ℓ (t) > 0 and Eq. ( 4) means thatg ℓ ⟨φ ℓ (x), φ ℓ (y)⟩ -g ℓ f ℓ (⟨x, y⟩) < ϵ 2 -2|⟨x, y⟩| 1-2 -ℓ.Since g ℓ f ℓ (⟨x, y⟩) = ⟨x, y⟩, the theorem follows.Now that we have established the above result, we can prove Theorems 2 and 3. We restate the theorems from the intro for the sake of readability. EQUATION2) (defined in the proof of Theorem 5 and independent of S except through parameters n, d, m and min x,y∈S,x̸ =y 1 -|⟨x, y⟩|) satisfies the following with probability at least (1 -2 n ) ℓ : φ ℓ (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 ± ϵ) error. The number of bits of the sketch isΘ n log n ϵ 2 (log 1 m ) 2 log 2 (π/ √ 2) .Proof. Let φ ℓ : S d-1 → N -1/2 {-1, 1} N be the map from Theorem 5 that by Theorem 6 satisfies, with probability at least (1 -2/n) ℓ , that 2 -2g ℓ (⟨φ ℓ (x), φ ℓ (y)⟩) is equal to ∥x -y∥ 2 up to an additive ±(ϵ/4)∥x -y∥ 2-2 -ℓ+1 error for all x, y ∈ S with N = 768(π/ √ 2) 2ℓ log n ϵ 2. Now assume that φ ℓ does satisfy this condition for all x, y ∈ S. We have∥x -y∥ -2 -ℓ+1 ≤ (1/m) 2 -ℓ+1 = (1/m) 2 -ℓ 2 ≤ (1/m) 1 log 2 (4/m) 2 < 4.This means that we actually estimate ∥x-y∥ 2 up to an additive ±ϵ∥x-y∥ 2 error, i.e., a multiplicative (1 ± ϵ) error. We haveπ √ 2 2ℓ ≤ π √ 2 2(1+log 2 log 2 4 m ) = π 2 2 2 2 log 2 ( π √ 2 ) log 2 log 2 ( 4 m ) = π 2 2 log 2 4 m 2 log 2 π √ 2so the result follows.The above theorem shows that given a set of points S ⊂ R d , there exists an appropriate choice of ℓ and N so that the random map φ ℓ : S d-1 → N -1/2 {-1, 1} N satisfies, with high probability, that φ ℓ (S) is a sketch of S that allows one to recover all squared distances between points in S up to a multiplicative (1 ± ϵ) 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. EQUATION2) (defined in the proof of Theorem 5 and independent of S except through parameters n, d, m and min x,y∈S,x̸ =y 1 -|⟨x, ŷ⟩|) satisfies the following with probability at least (1 -2 n ) ℓ : φ ℓ ( Ŝ) and the norm of each point in S up to an additive ±ρm 2 ϵ/48 error is a 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Θ n log n ϵ 2 log 1 m 2 log 2 (π/ √ 2) + n log 1 ρm 2 ϵ .Proof. For each x ∈ S, let n x be an approximation of ∥x∥ up to an additive ±ρm 2 ϵ/48 error.First we claim that in order to recover squared distances up to a multiplicative (1 ± ϵ) error, it suffices to recover squared distances to an additive ±ϵ∥x∥∥y∥∥x -ŷ∥ 2 error. The reason is that for any x, y ∈ R d , we can prove the inequality ϵ∥x∥∥y∥∥x -ŷ∥ 2 ≤ ϵ∥x -y∥ 2 by observing that ∥x∥∥y∥∥x-ŷ∥ 2 = ∥x∥∥y∥(2-2⟨x, ŷ⟩) = 2∥x∥∥y∥-2⟨x, y⟩ ≤ ∥x∥ 2 +∥y∥ 2 -2⟨x, y⟩ = ∥x-y∥ 2 . Now let Ŝ = {x : x ∈ S}. Let φ ℓ : S d-1 → N -1/2 {-1, 1} N with N = Θ (π/ √ 2) 2ℓ log n ϵ 2be the map from Theorem 5 that by Theorem 6 satisfies, with probability at least (1 -2/n) ℓ , that g ℓ (⟨φ ℓ (x), φ ℓ (ŷ)⟩) is equal to ⟨x, ŷ⟩ up to an additive ±(ϵ/32)(2 -2|⟨x, ŷ⟩|) 1-2 -ℓ error for all x, ŷ ∈ Ŝ. Assume that φ ℓ does satisfy this condition for all x, ŷ ∈ Ŝ. Notice that this implies that g ℓ (⟨φ ℓ (x), φ ℓ (ŷ)⟩) is equal to ⟨x, ŷ⟩ up to an additive ±(ϵ/32)(2 -2⟨x, ŷ⟩) 1-2 -ℓ error for all x, ŷ ∈ Ŝ. We have(2 -2⟨x, ŷ⟩) -2 -ℓ ≤ (1/m) 2 -ℓ+1 = (1/m) 2 -ℓ 2 ≤ (1/m) 1 log 2 (4/m) 2 < 4.This means that g ℓ (⟨φ ℓ (x), φ ℓ (ŷ)⟩) is equal to ⟨x, ŷ⟩ up to an additive ±(ϵ/8)(2 -2⟨x, ŷ⟩) error for all x, ŷ ∈ Ŝ, i.e., an additive ±(ϵ/8)∥x -ŷ∥ 2 error. For any x, y ∈ S,n x n y g ℓ (⟨φ ℓ (x), φ ℓ (ŷ)⟩) ≤ ∥x∥ + ρm 2 ϵ/48 ∥y∥ + ρm 2 ϵ/48 ⟨x, ŷ⟩ + (ϵ/8)∥x -ŷ∥ 2 ≤ ⟨x, y⟩ + (ϵ/4)∥x∥∥y∥∥x -ŷ∥ 2where the second inequality uses the definition of ρ and m. We can also show thatn x n y g ℓ (⟨φ ℓ (x), φ ℓ (ŷ)⟩) ≥ ⟨x, y⟩ -(ϵ/4)∥x∥∥y∥∥x -ŷ∥ 2 .This means that n x n y g ℓ (⟨φ ℓ (x), φ ℓ (ŷ)⟩) approximates ⟨x, y⟩ up to an additive ±(ϵ/4)∥x∥∥y∥∥x -ŷ∥ 2 error. Since n x approximates ∥x∥ up to an additive ±(ϵ/24) min x,y∈S ∥x∥∥y∥∥x -ŷ∥ 2 error this means that n 2 x approximates ∥x∥ 2 up to at least an additive ±(ϵ/4)∥x∥∥y∥∥x -ŷ∥ 2 error. Now this means that n 2x + n 2 y -2n x n y g ℓ (⟨φ ℓ (x), φ ℓ (ŷ)⟩) approximates ∥x∥ 2 + ∥y∥ 2 -2⟨x, y⟩ = ∥x -y∥ 2 up to an additive ±ϵ∥x∥∥y∥∥x -ŷ∥ 2 error.Storing all the norms of the points up to an additive ±ρ error requires log(1/ρ) bits per point.We have(π/ √ 2) 2ℓ ≤ (π/ √ 2) 2(1+log 2 log 2 r) = (π 2 /2)2 2 log 2 (π/ √ 2) log 2 log 2 r = (π 2 /2)(log 2 r) 2 log 2 (π/ √ 2)so the result follows.Theorem 7. For all t ∈ [0, 1],g ′ ℓ f ℓ (t) ≤ π ℓ 2 ℓ+1 2 (2 -2t) 1-2 -ℓ .This implies that for all t ∈ [0, 1],g ′ ℓ (t) ≤ π ℓ 2 ℓ+1 2 2 -2g ℓ (t) 1-2 -ℓ.and that for all t ∈ [-1, 1],g ′ ℓ (t) ≤ π ℓ 2 ℓ+1 2 2 -2g ℓ (|t|) 1-2 -ℓ .Proof. We start by proving the first claim.We will use the inequalityEQUATIONwhich follows by finding critical points of √ 1 -t -2 π arccos(t). Now this enables us to prove by induction that1 -f ℓ (t) ≤ (2 -2t) 2 -ℓ for t ∈ [0, 1]for all ℓ ∈ N + . The base case ℓ = 1 is (using Eq. ( 5))1 -f (t) = 2 π arccos(t) ≤ √ 1 -t ≤ √ 2 -2t.The induction step again uses Eq. ( 5) and also uses thatf ℓ-1 (t) ∈ [0, 1] if t ∈ [0, 1]. For all t ∈ [0, 1], we have 1 -f ℓ (t) = 1 -f (f ℓ-1 (t)) ≤ 1 -f ℓ-1 (t) ≤ (2 -2t) 2 -ℓ+1 = (2 -2t) 2 -ℓ . So 1 -f ℓ (t) ≤ (2 -2t) 2 -ℓ for t ∈ [0, 1] follows.Now we will prove the first theorem claim by induction. The base case isg ′ f (t) = π 2 cos arcsin(t) = π 2 1 -t 2 ≤ π 2 √ 2 -2t.Now for the induction step, assume that the first theorem claim holds for f ℓ-1 . We first need to establish that for all t ∈ [-1, 1],g ′ f ℓ (t) = π 2 cos (π/2)f ℓ (t) = π 2 cos arcsin(f ℓ-1 (t)) = π 2 1 -(f ℓ-1 (t)) 2 ≤ π √ 2 1 -f ℓ-1 (t) by f ℓ-1 (t) ≤ 1 ≤ π √ 2 (2 -2t) 2 -ℓ .Using the chain rule, g ′ ℓ (t) = g ′ (t)g ′ ℓ-1 g(t) . So for all t ∈ [0, 1],g ′ ℓ f ℓ (t) = g ′ f ℓ (t) g ′ ℓ-1 g(f ℓ (t)) = g ′ f ℓ (t) g ′ ℓ-1 f ℓ-1 (t) ≤ π √ 2 (2 -2t) 2 -ℓ π ℓ-1 2 ℓ 2 (2 -2t) 1-2 -ℓ+1 = π ℓ 2 ℓ+1 2 (2 -2t) 1-2 -ℓ .The second claim follows by plugging in g ℓ (t) into the first claim. The third claim follows by observing that if t ∈ [-1, 0], then g ′ ℓ (t) = g ′ ℓ (|t|) since g ′ ℓ is an even function (by the fact that g ℓ is odd.)Lemma 8. For all t ∈ [-1, 1], 0 ≤ g ′ ℓ (t) ≤ (π/2) ℓ . Proof. By induction. When ℓ = 1, g ′ (t) = π 2 cos( πt 2 ) ∈ [0, π/2] when t ∈ [-1, 1].For the induction step, we need to use the fact that g ℓ-1 (t) ∈ [-1, 1] when t ∈ [-1, 1]. Using this, g ′ ℓ (t) = g ′ g ℓ-1 (t) g ′ ℓ-1 (t) = π 2 cos π 2 g ℓ-1 (t) g ′ ℓ-1 (t) ∈ [0, (π/2) ℓ ]. Lemma 9. |f ℓ (t)| ≤ |t| for all t ∈ [-1, 1] and all ℓ ∈ N + . Proof. Since f ℓ (-t) = -f ℓ (t) for all t ∈ [-1, 1], it suffices to prove that f ℓ (t) ≤ t for all t ∈ [0, 1].The claim follows by induction in ℓ.Lemma 10. For all ℓ ∈ N and t ∈[-1, 1], 1 -|f ℓ (t)| ≥ (1 -|t|) (2/3) ℓ . Proof. Since f ℓ (-t) = -f ℓ (t), it suffices to show that 1 -f ℓ (t) ≥ (1 -t) (2/3) ℓ for all t ∈ [0, 1].To prove that 1 -f (t) ≥ (1 -t) 2/3 we will use that arccos(t) ≥ π(1-t) 1/2 2(1+t) 1/6 for all t ∈ [0, 1] as shown in [31, Remark 2.1 ]. Now we have 1 -f (t) = 2 π arccos(t) ≥ (1-t) 1/2 (1+t) 1/6 . The result now follows since 1 (1+t) 1/6 ≥ (1 -t) 1/6 for all t ∈ (-1, 1]. This is the base case. The induction step uses the fact that for all t ∈ [0, 1], f ℓ (t) ∈ [0, 1]. Using this and the base case proven above,1 -f ℓ+1 (t) ≥ 1 -f ℓ (t) 2/3 ≥ (1 -t) (2/3) ℓ 2/3 = (1 -t) (2/3) ℓ+1 .NeurIPS Paper ChecklistJustification: Our research conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024).Since the points are in the unit ball, for any δ > 0, approximating distances to within additive error δ/6 gives approximation of squared distances to within additive error δ. So the size of the epsilon net is, up to a constant, (1/mϵ) ϵ -2 log n . This gives Θ log(1/m 2 ϵ)ϵ -2 log n bits per pointWe remark that the map φ D is often referred to as a random feature map, see[28,7,26]. 


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

Reviews: review: paper_summary: paper_summary: The authors investigate the bit complexity of distance preserving embeddings of points on the unit sphere and in the unit ball.
Their 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. 

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

Empirical evaluation with synthetic and small scale real world data support the theoretical claims.
strength_weakness: strength_weakness: The reduction in the number of bits needed only impacts lower order factors, as explained on line 77.

Could you please discuss the many quantization methods cited on line 173 and compare yours with them both analytically and experimentally?

Figures 1 and 2 lack baselines that compress to bits, could you please add a few, including quantizing (epsilon-netting) a random projection?
questions: 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?

Line 340: "six time the output dimensions." Could you elaborate how 6 was chosen?
limitations: limitations: Limitations are sufficiently discussed. (Mostly) theoretical work, no negative societal implications.
paper_summary: paper_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||.  

A good comparison for their results is via a JL-random project embedding; the bits required for this is:
   - O(n * (1/eps^2) log n * log(1/m eps)

The number of bits required for their approach is
  - O(n * (1/eps^2) log n * log(1/m)^{2.3})
strength_weakness: strength_weakness: This might be of some independent interest, but as of now the improvement is quite minor.  

This paper reports a very small improvement in very limited cases.  
In 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.   

As a result, I do not think it is worth publishing at NeurIPS.
questions: questions: none
limitations: limitations: N/A.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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$. 

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

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

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


References:
Li et al: Improving Random Projections Using Marginal Information, COLT 2006
questions: 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)? 

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

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

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

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

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

References:
Li et al: Improving Random Projections Using Marginal Information, COLT 2006
limitations: limitations: The authors address the main limitation when $\varphi_l, l \geq 2$ performs better.

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

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

Comments: comment: Thanks for the explanation and clarifications.
Thank you for correcting my statement about needing eps to be exponentially smaller than m.  Still the difference needs to be more than polynomial.  The results are asymptotic so I do not find the results with small constant values compelling.  Moreover I assume normal cases of interest are eps >= 0.1 and m < 0.01.  

I agree the algorithm does appear naturally simpler.
The improvement is not only an improvement when $\epsilon$ is exponentially smaller than the spread. The actual range of improvement is much better than exponential in theory and even in practice $\epsilon$ does not need to be much smaller that $m$ to see an improvement. The relevant terms to be compared are $\log(1/(m \epsilon))$ and $(\log (1/m))^{2/3}$. In theory, to have $\log(1/(m \epsilon)) \geq (\log (1/m))^{2/3}$ it is sufficient to have $1/\epsilon \geq (1/m)^{(\log(1/m))^{1.3}}$ so the threshold for improvement is no worse that quasi-polynomial (much better than exponential). This can also be verified numerically for practical values of $m$ and $\epsilon$: the largest $\epsilon$ given $m$ where $\log(1/(m \epsilon)) \geq (\log (1/m))^{2/3}$ for $m=1/4$ is $\epsilon=.48$ (so $\epsilon$ can even be larger than $m$) and for $m=1/10$ is $\epsilon=.011$.

Another issue with comparing our algorithmic approach with discretized J-L is that the bound we quote for J-L is intended as an information-theoretical bound only. Our algorithm is straightforward to implement while it is not clear that there is an efficient algorithm that matches the discretized J-L bound. This is because it is based on an optimal (non-algorithmic) epsilon-net of the unit ball and it is not clear what the compression/encoding algorithm is. For each projected point, the natural compression algorithm has to find the nearest point in the (exponentially large) $\epsilon$-net.
Thanks, we appreciate the suggestions and will plan to add some discussion of multiplicative error in the context of applications to the introduction.
Thanks for the rebuttal.  I agree these results and techniques may be of purely theoretical interest, but then I do not think NeurIPS is the right venue -- at least I am not convinced.  

This is only an improvement when eps (typically a constant) is **exponentially** smaller than the spread of the point set m.  I am just not convinced this improvement is of interest to any settings relevant to the NeurIPS community.
The authors have addressed my concerns, and I am happy to increase my score. I would suggest the authors to further emphasize the significance of their work (as mentioned in the global rebuttal), and maybe a discussion of false positives with respect to multiplicative error to reach out to the more applied folks.
Thank you for the detailed rebuttal! I am currently waiting for the AC to send out the code, as well as the global rebuttal (which I assume also has the attached pdf).