Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.

Significance of the contribution: We give an example for obtaining a significantly faster algorithm for estimating weighted matchings, but similar examples exist for all the other problems considered here. Given a weighted graph with $n$ nodes and $m$ edges, one can estimate the size of a matching up to a $(1+\varepsilon)$ factor in time $O(m+n)$, ignoring lower order terms [1]. In Euclidean spaces, this is always $O(n^2)$, as all edges exist and computing all of these edges takes time $O(n^2d)$. This is clearly not a linear time algorithm as the input has only size $O(nd)$. A fast alternative using coresets exists [2], but it requires time $O(n\cdot\exp(d))$, which for worst case instances does not offer an improvement even when using previous dimension reduction bounds. Specifically, our lower bound shows that we can only replace $d$ with $O(\log n)$ in the worst case. However, if the doubling dimension is constant, we can use the coreset in combination with our new dimension reduction bounds to obtain a linear time algorithm, which to the best of our knowledge was not previously known.

In general, we prove that for a wide range of optimization problems, any dependency on $d$ may be replaced with a dependency on the doubling dimension. This almost always speeds up an algorithm, as the running time of the random projection is inexpensive. But it is particularly useful if the algorithm runs in time $\exp(d)$, as illustrated for the matching example above. Such examples are common in literature for the other problems considered here as well, due to the proverbial curse of dimensionality. The running time also gets reduced significantly in practice. Our experiments show that the runtimes are reduced by up to $10-100$x as shown in Table 2 in the appendix, and the reduction in solution quality is small.

• [1] R. Duan and S. Petite. Linear-Time Approximation for Maximum Weight Matching. J. ACM 2014.
• [2] G. Frahling and C. Sohler. Coresets in Dynamic Geometric Data Streams. STOC 2005.

Definition for max-matching: A matching is a set of pairs of points, with no point belonging to more than one pair; the cost of a matching is the sum of distances between the pair of points; and a maximum matching is a matching with the maximum cost. A (1+eps)-approximate matching is a matching whose cost is a (1+eps)-approximation to the cost of a max-matching. In other words, it is an approximation whose cost is approximately as large as the best possible cost.

Relation to broader scientific literature: We would like to point out that many papers related to the JL lemma and random projection based dimensionality reduction have recently appeared in top ML venues. See below for a small selection.

• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. ICLR 25
• MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings 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
• Dimensionality Reduction for General KDE Mode Finding. ICML 23
• Dimensionality reduction for Wasserstein barycenter. NeurIPS 21
• Randomized dimensionality reduction for facility location and single-linkage clustering. ICML 21
• Dimensionality Reduction for the Sum-of-Distances Metric. ICML 21

Explaining proof of Theorem 2.1: We consider maximum matching, so the cost of an optimal solution is larger than the cost of any other solution. Opt$(G(P))$ is the optimal solution in the projected space by definition, so it must be larger than the solution given by $G(S)$ where $S$ is the optimum in the original dimension.

Regarding placing the proof for diversity maximization in the appendix: Ideally, all proofs should be in the main body. However, due to the page limit, we chose to provide the entire proof for the max-matching problem, rather than providing fragmented proofs for all the claims.

We believe we have addressed your main concern about the significance of the contribution. Please let us know if you have any further concerns or questions; we are very happy to provide further clarifications!

Many thanks,

The authors

We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.

1) Datasets: We focused on datasets that have been used in prior empirical studies on diversity maximization and dimensionality reduction (Tenenbaum et al., 2000; Naeem et al. 2020). Furthermore, we believe our data is quite high dimensional. E.g. the Resnet embeddings we use are in dimension > 6000.

As for sparse NLP datasets, we performed a new experiment on maximum matching on TF-IDF embeddings for the 20 newsgroup dataset. These resulted in extremely sparse vectors with dimension > 170,000 (TF-IDF is based on word frequencies). We selected a set of 2000 vectors. The average sparsity was 100. As seen in the figure in this anonymous link (https://ibb.co/2YsR6kXS), the qualitative behaviour is the same as in our submission. By just projecting to 500 dimensions (~ 0.2% of the original dimension), we can preserve the max-matching cost up to relative error < 5%. In fact, since our bounds depend on the doubling dimension (always at most $O(\log n)$), their effect becomes increasingly pronounced as the ambient dimension of the dataset increases.

2) Comparison to manifold learning: Our paper focuses on proving worst-case theoretical guarantees. We do this by using data-oblivious maps based on the Johnson-Lindenstrauss (JL) Lemma.

In contrast, the methods suggested by the reviewer have no such theoretical guarantees for Euclidean distance, and can perform very poorly. This is well known, e.g. see [Ref 1] where it is shown theoretically and empirically that JL has better performance over PCA and Isomap heuristics. The underlying intuition is that manifold learning (such as Isomap) considers data points that are in a lower dimensional manifold embedded in a high dimensional space. Their goal is to recover the low dimensional manifold by approximating the geodesic distance along the unknown manifold. However, the geodesic distance could be very far from Euclidean. This deviates from our setting where we aim to approximate high dimensional Euclidean distances.

For concreteness, here is a simple example where PCA catastrophically fails: consider the dataset X consisting of all basis vectors and negations. Weight the first $n/2$ basis vectors and their negatives by a factor of $2$. This has doubling dimension $O(\log(|X|))$ and JL guarantees that all pairwise distances (and thus all the optimization problems we consider) is preserved up to $1\pm \epsilon$ factor when projected to $O(\log(|X|)/\epsilon^2)$ dimensions. However, for any $k < n/2$, the top $k$ PCA directions align with the first $k$ basis vectors. When we project onto them, this maps all other basis vectors to $0$, so all information about them is lost, and max-matching on this PCA projected dataset has large distortion.

[Ref 1]: Dimensionality reduction: theoretical perspective on practical measures. NeurIPS 19.

We also refer to the response to Reviewer jiNF for many works related to the JL lemma that have recently appeared in top ML venues.

3) Doubling dimension: The way JL transforms are applied is by determining a desired target dimension and performing the projection. In practice, users will use as many dimensions as are affordable and for many problems, worst case bounds are significantly larger than the dimensions that end up being used. Naturally, we are interested in understanding why this phenomenon occurs. An explanation is that data sets have low “intrinsic dimension”, which the doubling dimension captures and models. This is a popular approach in the literature which has led to development of several practically efficient algorithms (e.g. Cover Tree by Beygelzimer et al.). Our real-data experiments exemplify this, and demonstrate that data sets with low ``intrinsic dimension'' can be projected to very low dimension without significantly reducing the accuracy. This is why we selected real data sets (e.g. MNIST 2) that were studied in prominent works studying embeddings of data sets with low intrinsic dimension (Tenenbaum et al, Science'00).

We emphasize that the algorithm does not have to know the doubling dimension and as long as the target dimension is larger than the doubling dimension, it is always guaranteed to succeed with high probability. Works in this line of research typically only have to show that a given target dimension is sufficient, for a specific task, as the algorithm itself is oblivious to the dataset. This sets random projections apart from PCA and manifold learning and similar methods that are computationally expensive, have to know properties of the data set, and typically perform very poorly as metric embedding algorithms (see earlier example on PCA). If it is nevertheless desired by the user, we could compute an approximation of the doubling dimension in linear time (see Sect. 9 in https://arxiv.org/pdf/cs/0409057), but the efficiency of our method does not rely on this.

However, it seems to me they only give an lower bound, which corresponds to the special case (lambda = log n) but not for a general range of lambda?

We thank the reviewer for their careful reading and comments.

The lower bound can be extended to general $\lambda$ as follows. For every $\lambda$, consider the pointset that consists of the $2^\lambda$ first basis vectors, and duplicate each point $n/2^\lambda$ times. If you are concerned with having a set with multiplicities, you can move the copies slightly along one axis (this will not affect the doubling dimension).