Beyond Worst-Case Dimensionality Reduction for Sparse Vectors

Thank you for your feedback.

It would be great if the paper could give a little bit more intuition why the non-negativity makes such as significant difference. In particular, the authors write that simple translation is not good enough as it might affect sparsity. Intuitively I tend to agree (as this happens to be the case in many similar scenarios).

Intuitively, non-negativity provides more structure that we can exploit for better dimensionality reduction. Consider our map of Theorem 2.5 for the case of the L-infinity norm. Given two vectors x and y, some coordinate witnesses i their L-infinity distance, that is $\|x-y\|_{\infty} = |x_i - y_i|$ We would like to ‘isolate’ this coordinate without knowing the vectors x and y up front (we embed f(x) and f(y) separately). Thus, our map has two important properties:

• (1) Every coordinate in the support of $x$ and $y$ (in particular coordinate $i$) is isolated with large constant probability.
• (2) If $i$ collides with any other support coordinate, the distance of the embeddings never increases.

By stacking many independent copies of our map, we can boost the success probability of property (1). Furthermore, property (2) ensures that stacking does not distort the distances.

Now property (1) holds for arbitrary sparse vectors, with both positive and negative coordinates. However, for our map, property (2) crucially is only true for non-negative vectors. This is because we take the maximum inside every bucket of coordinates, and $|\max(a_1, \cdots, a_s) - \max(b_1, \cdots, b_s)| \le \max_i |a_i - b_i|$ only holds if the values $a_i$ and $b_i$ are non-negative. For general values, the inequality can only hold up to a factor of 2 which is not strong enough to obtain an embedding. This crisply demonstrates the extra structure we are exploiting.

Now a natural followup question is, are there potentially other maps that would give us dimensionality reduction for arbitrary sparse vectors? Why should we limit ourselves to this particular map in the paper? For that question, we point you to our lower bound of Theorem 2.9. There we show that even for 1-sparse vectors (with positive and negative coordinates), no non-trivial dimensionality reduction can exist in the L-infinity case. In the proof, we use the basis vectors and their negations and crucially exploit cancellations afforded by entries of different signs.

Finally, we note that while a dimensionality reduction map for general sparse vectors (with both positive and negative coordinates) is always valid for non-negative sparse vectors, the converse may not be true. A priori, it seems possible to just use a distance preserving transformation, such as a translation, to convert arbitrary sparse vectors into non-negative sparse vectors. However, a translation which converts arbitrary sparse vectors into non-negative sparse vectors can destroy sparsity.

We refer to the technical overview of Section 3.2 for further details.

Thank you for your comments. We hope that we can clarify a few points.

I don't recommend a strong accept mainly because of lack of a cohesive insight across the two main research questions they address -- average case lower bounds for general sparse vectors and improved upper bounds for non negative sparse vectors.

Our lower bounds show that for general sparse vectors, even the mild requirement of requiring only a constant fraction of the distances to be preserved already yields strong lower bounds against very general embedding maps. This motivates studying natural/common structure in addition to sparsity where dimensionality reduction is possible. A natural structure is non-negativity. Here, we show that we can embed non-negative sparse vectors in very low dimensional space (much lower than what is possible for general sparse vectors), and additionally preserve all pairwise distances.

The paper's array of results could also be supplemented with more insight into the hard distributions (of the type Unif_t,r ) that they constructed.

We would be happy to provide some intuition for our lower bound. The vectors used in the lower bound must represent all possible sparsity patterns. For example, if they were only supported on the first $s$ coordinates, then we could easily obtain a much better upper bound. This motivates us to sample random coordinates to be in our support.

We also put Gaussian entries in the sampled coordinates. This helps us relate $||Ax||_2 \approx ||x||_2$ to an event about Gaussian random variables which can be analyzed. More precisely, in Theorem 3.1 we show that if $| ||Ax||_2^2 - ||x||_2^2 | \le \gamma ||x\||_2^2$ for a small $\gamma$, then this would imply that a suitable polynomial (obtained by expanding the relation $||Ax||_2^2 - ||x||_2^2$ as a variable in the support of $x$), must lie in a very small interval. This relates to polynomial anti-concentration inequalities for unit variance Gaussians, for which we can invoke Lemma 3.2.

Another useful property of Gaussians that we exploit in our hard distributions is scale invariance: scaling a vector sampled from Unif_t,r is equivalent to sampling from Unif_t,r′ for an appropriate r′. This is crucial in the proof of Theorem B.2 which extends our average case lower bound to arbitrary smooth functions. Our high level proof idea is to reduce the case of a smooth function f to that of linear maps. This is done by approximating a smooth map via a linear one in a very local region around the origin. The approximation incurs an error, allowing us to essentially only understand the behavior of f(x) for an x also close to the origin, where we can approximate $f(x) \approx Ax$. For this A (derived from f), we know that it approximates the norm of sparse vectors x with very small norm (i.e., those from Unif_t,r for a suitably small r). However by linearity, A must also preserve the norm of any c*x, and by choosing c, it must also preserve the norm of x sampled from Unif_t,1. Now we are in the setting of Theorem 3.1 (linear case) so the lower bound proof goes through. They also mention that Birthday Paradox like maps are folklore, but it would provide more completeness if they referenced mentions or proof of the upper bound.

We note that the entire proof of the folklore Birthday paradox map is contained in line 73. We have also updated our paper with citations for prior works that contain the folklore argument.

Thank you again for your review.

We believe we have addressed your concerns by providing insights to connections between our upper and lower bounds as well as a thorough discussion of our lower bounds. If any of your concerns have not been addressed, could you please let us know before the end of the discussion phase?

Many thanks, The authors

Thank you for your comments. We hope that we can clarify a few points.

Regarding the first result, it seems to be natural that one should expect a lower bound of s^2 because of the birthday paradox. Indeed, the main analysis of the lower bound is mostly a probability calculation and the construction is based on uniform sampling which is not particularly surprising. I am not quite able to see new techniques introduced in this part.

We note that the lower bound holds for any possible linear map, not just those that do “hashing into buckets.” In other words, the matrix $A$ in our lower bound does not have to have columns of sparsity $1$ (which holds for the birthday paradox). We allow $A$ to have arbitrary real entries and $A$ can be arbitrarily dense. This leads to complications in our argument since $A$ can spread the mass of a vector along many coordinates. For example, consider the case where $A$ has rows $[1/\sqrt{2}, 1/\sqrt{2}, 0, …, 0]$ and $[1/\sqrt{2}, -1/\sqrt{2}, 0, …, 0]$. These two rows ‘evenly’ spread out the mass on the first two coordinates. That is, $||Ax||_2$ will be exactly equal to $||x||_2$ if $x$ is only supported on the first two coordinates. Thus using arbitrary entries potentially allows the embedding matrix to use multiple coordinates in the embedding vector to `account for’ any coordinate in the input vector $x$. Any lower bound must also rule out these cases.

Another complication is that well known methods to prove dimensionality reduction lower bounds do not seem to apply in our setting, because we do not assume all distances have to be preserved. Rather, we assume a weaker hypothesis of only a constant fraction of distances being preserved. Thus, lower bound techniques such as the rank based argument of Alon for the classic JL lemma cannot be directly used. Instead, we generalize rank based arguments to the average case. We show any linear embedding A which preserves most pairwise distances must have a high rank. Unlike the JL case, we only have control over 99% of the entries of $A$, which is problematic as the remaining 1% can wildly influence the rank to be arbitrarily large (more precisely we look at the rank of $A^TA$). Thus, we consider a “softer” notion of rank, which we show is captured by a suitable polynomial in terms of the entries of A and a sparse vector $x$ which we query $A$ on. We reduce the average case guarantees to showing that the polynomial must lie in a small interval, when we pick x from an appropriate distribution over sparse vectors. Finally, we show that if the rank of $A$ is too small, this polynomial violates anti-concentration properties of random polynomials. We also generalize this argument to sufficiently smooth maps. Please see our technical contribution section, Section 3.2 for more details.

Questions and typos.

Thank you for pointing out the small typos. They have been updated.

Thank you for your comments. We hope that we can clarify a few points.

The results are nice, but it does feel like a pure theory paper, raising the question of whether ICLR is the right venue. That said, dimension reduction is ubiquitous in ML, and so I feel it is justified.

Thank you for your feedback. We would like to point out that many papers related to dimensionality reduction have recently appeared in top ML venues. Here is a small selection of papers that study dimensionality reduction and embeddings in a wide range of ML problems within the last 3 years:

• Contrastive dimension reduction: when and how? NeurIPS 24
• ESPACE: Dimensionality Reduction of Activations for Model Compression. NeurIPS 24
• Sparse Dimensionality Reduction Revisited. ICML 24
• Dynamic Metric Embedding into lp Space. ICML 24
• Simple, Scalable and Effective Clustering via One-Dimensional Projections. NeurIPS 23
• Fast Optimal Locally Private Mean Estimation via Random Projections. NeurIPS 23
• SNEkhorn: Dimension Reduction with Symmetric Entropic Affinities. NeurIPS 23
• A Heat Diffusion Perspective on Geodesic Preserving Dimensionality Reduction. NeurIPS 23
• Dimensionality Reduction for General KDE Mode Finding. ICML 23
• A Probabilistic Graph Coupling View of Dimension Reduction. NeurIPS 22
• Dimensionality reduction for Wasserstein barycenter. NeurIPS 21
• Randomized dimensionality reduction for facility location and single-linkage clustering. ICML 21
• HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projections. ICML 21
• Dimensionality Reduction for the Sum-of-Distances Metric. ICML 21

The setting considered in the lower bounds and upper bounds are quite different -- lower bounds work only for linear and smooth embeddings while the upper bound uses a non-linear embedding. So stating the results as a "separation" between general and non-negative results does not seem convincing to me.

Our lower bounds show that for general sparse vectors, even the mild requirement of requiring only a constant fraction of the distances to be preserved already yields strong lower bounds against very general embedding maps. Specifically, this includes the upper bound, which uses a smooth albeit non-linear embedding. Thus, this motivates studying structure in addition to sparsity where dimensionality reduction is possible. A natural type of additional structure is non-negativity. Here, we show that we can embed non-negative sparse vectors in very low dimensional space (much lower than what is possible for general sparse vectors), and additionally preserve all pairwise distances. We agree that our average case lower bounds are only shown to hold for linear and smooth maps, and it is an interesting future direction to extend our lower bounds to arbitrary maps.

(Of course, there is also the bigger difference that one case considers distances between the vectors, while the other case considers the vectors themselves.)

Our lower bounds for average case guarantees hold for linear maps and transfer to distances between vectors directly. Here, we are proving a lower bound for linear maps $A$ that have to satisfy $||Ax||_2 \approx ||x||_2$ with probability $99\%$ over the choice of $x$ in a dataset. However, we note that this lower bound also extends to the case where we must satisfy $||A(x-y)||_2 \approx ||x-y||_2$ for $99\%$ of pairs in a dataset, by just modifying the dataset to contain the difference of all pairwise vectors (due to linearity). In other words, the lower bound we prove is a stronger claim.

Can the authors say more about whether the known non-linear embeddings (eg., compressed sensing) work for the non-negative vector setting considered in the paper? (will it be that most pairs of distances will be preserved but not all?)

RIP matrices (which are one example of compressed sensing techniques) will give an embedding for all sparse vectors (including nonnegative ones), but it will have an exponential dependence in p on the embedding dimension (See Table 2). Other compressed sensing algorithms such as LASSO are not embeddings.