Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Authors: Jie Gao
Rajesh Jayaram
Benedikt Kolbe
Shay Sapir
Chris Schwiegelshohn
Sandeep Silwal
Erik Waingarten
Venue: ICML 2025 poster (2025)
Keywords: Dimensionality Reduction
Dimension Reduction
Geometric Optimization
Johnson Lindenstrauss
Diversity Maximization
Diversity
Primary area: general_machine_learning->scalable_algorithms
TL;DR: Novel dimensionality reduction results for geometric maximization problems

Abstract: Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the *doubling dimension* $\lambda_X$ of the underlying dataset $X$---a quantity measuring intrinsic dimensionality of point sets. Specifically, the dimension required is $O(\lambda_X)$, which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence grow with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Jie Gao Rajesh Jayaram? Benedikt Kolbe 3 Shay Sapir* Chris Schwiegelshohn Sandeep Silwal
Erik Waingarten
Abstract
1. Introduction
Dimensionality reduction is key technique in data sci- ence and machine learning that allows one to transform dataset of n points in a d-dimensional space into a dataset where each point now lies in a much smaller t-dimensional space. This reduction in dimensionality occurs while (ap- proximately) preserving the dataset's 's essential properties. The benefits of such reduction are apparent- the total stor- age of d-dimensional dataset is (nd)). After dimension reduction, the total storage is O(nt).
Randomized dimensionality reduction is a widely- used algorithmic technique for speeding up large- scale Euclidean optimization problems. In this pa- per, we study dimension reduction for a variety of maximization problems, including max- max-matchine matchhig max-spanning tree, max TSP, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the doubling dimension Xx of the underlying dataset X-a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that target dimension of O(xx) suf- fices to approximately preserve the value of any near-optimal solution, which we also show is nec- essary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence increases with the dataset size | We also provide empirical results validat- ing the quality of solutions found in the projected space, as well as speedups due dimensionality reduction.
Another aspect is running time. After dimension reduc- tion, we may replace dependencies on d with a dependency on t. This seemingly addresses the curse of dimensionality which used to describe the phenomenon that algorithms scale poorly in high dimensions. Initially this seems very promising, as many problems admit polynomial time ap- proximation scheme (PTAS) in low-dimensional setting (Bartal & Gottlieb, 2021; Cevallos et al., 2019; Kolliopoulos & Rao, 2007). However, these algorithms typically have severe dependency on the dimension d (c.g., could be dou- bly exponential). We are thus interested in reducing the dimension as much as possible, ideally even to constants.
Problems for which efficient algorithms are known to ex- ist in low-dimensions, but are not known to exist in high- dimensions, include network design problems, such as the traveling salesperson (Arora, 1997; Kolliopoulos & Rao, 2007; Shenmaier, 2022), and diversity maximization prob- lems (Cevallos et al., 2019; 2018), both of which are staples of data analysis and operations research. However, this discrepancy between low- and high-dimensional data ex- ists primarily in the worst case. One can consider beyond worst-case analysis by attempting to identify tractable inputs to the problem which are not necessarily low dimensional (Awasthi et al., 2010; Ostrovsky et al., 2012). One way of utilizing such properties is to design a dimension reduction to uncover such structures that might not be easily used in the original high dimension, see (Awasthi & Sheffet, 2012; Cohen-Addad & Schwiegelshohn, 2017).
"Authors listed alphabetically. 'Department of Computer Science, Rutgers University, Piscataway, NJ, USA 'Googee Research, NYC, USA 'Hausdorff Center for Mathematics, Lamarr Institute for Machine Learning and Artificial Intelli- gence. University Boun. Germany 'Department of Computer Science, Weizmann Institute of Science, Israel 'Deparmment of Computer Science, Aarhus University, Denmark 'Department of Computer Sciences, University of Wisconsin-Madison USA 'University of Pennsylvania, Philadelphia, USA. Correspon- dence to: Jie Gao <jg <rkjayaram @ google.com>>. Benedikt Kolbe <bkolbe @ uni- bonn.de>, Shay Sapir <shay.sapirel weizmann.ac.ils Chris Schwiegelshohn <cschwiegelshohne @ gom,,, Sandeep Silwal <silwal@cs wisc. Erik Waingarten <ewain- gar @ seas.upenn.edu>.
Rajesh Jayaram
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
Dimensionality reduction techniques can be broadly cate- gorized into two distinct types: data-dependent and data-

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
oblivious. Data-dependent techniques, like Principal Com- ponents Analysis (PCA) and t-SNE (van der Maaten & Hin- ton, 2008), aim to produce "tailor-made" low-dimensional representations via (frequently) computationally-inees intensive procedures (possibly with quadratic running times). The benefit of being data-dependent is that one can capture the non-worst-case nature of "real world" datasets; the down- side is that data-dependent methods are computationally expensive, see (Boutsidis et al., 2009; Cohen et al., 2015; Feldman et al., 2020) for applications of PCA to clustering and subspace approximation.
Huang et al., 2024), single-linkage clustering (Narayanan et al., 2021), approximate nearest neighbors (Indyk & Naor, 2007) and k-center (Jiang et al., 2024).
We ask: For which problems can we design a data- data-oblivious dimension reduction with data-dependent target dimension? Can we identify a large collection of related geometric prob- lems which admit such dimensionality reduction?
1.1. Our Contributions
In this paper, we identify a large class of problems, with a special focus on network design (maximum weight match- ing, max TSP, max spanning tree) and diversity maximiza- tion problems (subgraph diversity maximization), for which we are able to obtain a data-oblivious dimension reduction with deta-dependent target dimension. Maximum weight matching, max TSP and max spanning tree are natural net- work design problems where the weights describe profit or rewards on the edges. Maximum diversity problems arise in many application settings, from facility location to network analysis, and have been a topic of study in both computer science (Indyk et al., 2014) and operational re- search (Martí et al., 2022). In general, such problems focus on identifying a subset of elements from a given set such that a diversity/distance measure is maximized. Different problems in this family choose ways to measure the overall diversity measure. Possibly the most notable problem is the dispersion maximization, which maximizes the small- est pairwise distance of the selected elements. But other measures of using the sum of edge lengths in a subgraph (clique, star, cycle, tree, matching, and pseudoforest) have also been studied (Indyk et al., 2014). Taking diversity into account in data analysis is also gaining traction in machine learning (Gong et al., 2018) especially in generative mod- els (Eigenschink et al., 2023; Naeem et al., 2020) and active learning (Melville & Mooney, 2004; Yang et al., 2015).
In data-oblivious dimension reduction, the goal is to produce-witte even looking at the dataset- a dimensionality-reduciiii map from R2d to R. These are con- siderably more "lightweight" and simple to apply and indeed vital for streaming and distributed models, where the applied dimensionality reduction method is restricted to small por- tion of the entire input. Indeed, the HaansoonLinndnstrauu (JL) transform (Johnson & Lindenstrauss, 1984), which can be realized by a t x d matrix of independent N (0, 1/t) en- tries (Indyk& & Motwani, 1998; Dasgupta & Gupta, 2003), among the most popular examples. Despite being data- oblivious, JL transforms are surprisingly powerful. They preserve pairwise distances, and also center-based cluster- ing (Makarychev et al., 2019; Izzo et al., 2021), linkage clustering (Narayanan et al., 2021), subspaces (Charikar& & Waingarten, 2022), and cuts (Chen et al., 2023), to name a few applications.
Among these works. (Indyk& & Naor, 2007; Narayanan et al., 2021) stand out in relating the performance of the JL trans- form to the doubling dimension of the input dataset, in- corporating elements of data-dependen and data-oblivious dimension reduction. On the one hand, the dimensionality- reducing map is still a JL transform; it is data-oblivious, simple to apply, store and communicate. On the other hand, the analysis is data-dependent- it ties the performance of the map to data-dependent quantity, the doubling dimen- sion, which captures the intrinsic dimensionality and non- worst-case nature of nigh-dimensional datasets. Formally, the doubling dimension is the smallest number À such that for every ball of radius r, the input points in that ball can be covered by 2d balls of radius r/2 (Gupta et al., 2003) (see also (Clarkson, 1999)). For arbitrary worst-case instances, < log nt, as we can always cover n points with 210g" n balls for any choice of radius r. For any given instance, however, the quantity may be substantially smaller. Perhaps surprisingly, it is possible to prove data-dependent bounds on the performance of data-oblivious dimension reduction, deriving the benefits of both.
Given input dataset with doubling dimension X, we show that reducing the dimension to roughly ( = O()), using a matrix of i.i.d. Gaussians drawn from (0, 4), preserves solutions up to a factor of + e on the problems in Table I found by any algorithm with high probability. Furthermore, we also show that the dependence on X in the target dimen- sion is tight for all of these problems there are datasets for which reducing the dimension below ?(A) introduces large errors.
A particularly nice feature of our bounds is that the guar- antee applies to all candidate solutions. We may thus use any algorithm in the low dimensional space in post process- ing. We are only aware of comparable result for nearest neighbor search (Indyk & Naor, 2007). Previous work in this direction only preserved the value of the optimum (for MST (Narayanan et al., 2021)) or restricted the candidate so- lutions (for facility location (Narayanan et al., 2021; Huang
So far, this type of analysis (incorporating the doubling di- mension to data-oblivious dimension reduction) has only been done for facility location (Narayanan et al., 2021:
2

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
Problem
Target Dimension
Reference
of maximum matching and maximum TSP, respectively.
Max weight matching
O logg?! ) (2(A)
Thm 2.1
Theorem 2.1. Let O < < and d, E N, and Gaus-
Thm 3.1
sian JL map E igtxd with suitable = O(E (i(E-22on "Moog t) X, with probability at least 2/3, every (1 + -)-pppoxximmate so- lution for optmaxx-atch (G(P)) mpt (GPP) is
Max TSP
O(e + log
Thm 2.1
Then for every set C Id with ddim(P)
((())
Thm 3.5
Max k-hypermatching
0( 2 A log 9)
Thm 2.3
Max spanning tree
O(e " log
Thm B.5
(1 + +(())) D(e)))-aproximmle solution mpx (P) or opt max-sxxssp (P). respectively. Moreover, (p))aapproximate
(2(A)
Thm B.6
Max k-voveraee
Ole A "A log :)
Cor B.4
solutions are preserved as well.
(((A)
Thm B.6
Suhgraph diversity
0 01 log _ log
Cor A.2
The proof of the theorem is by the following lemma.
((A)
Thm A.3
Lemma 2.2. Let < < and E N, and Gaussian
JI. map G E Raxt with suitable t O X 2) Then, for every set P C Rd with ddim(P)) = X, with probability 2 9/10, we have, for every matching M of P.
Table Summary of results for dimension reduction with 1 + e distortion using matrix of i.idd Gaussians. The doubling
dimension the input dataset is denoted by
Σ {p.g)EM
||pp Ggll S
Σ {pIgTEM
|p-gll+e-opp, max-machh (P).
et al., 2024) and k-center (Jiang et al., 2024)).
Threshold Phenomena As another contribution, we iden- tify an intriguing sharp threshold phenomenon for maximum matching, and we believe a similar phenomena also occurs for some the other problems (e.g., maximum TSP). While reducing the dimension to O()) (or O(log n) in general) provides (1 + -papproxmmmaio of maximum matching for any constant > O; there datasets such that reducing the dimension slightly below this bar causes a distortion of at least 2 (by Theorem 3.1). Curiously, the approxima- tion factor remains at most /2 all the way down to target dimension (1) (see Theorem 4.1). We are not aware of any previous work establishing similar phenomena.
Proof of Theorem 2.1. Notice that for both problems, (G)( 2 (1 -1-66 E) opt(P) w.h.p. by the following. Consider an optimal solution S in P (where S is either a perfect matching or a tour of P). We have
opt(G(P)) 2 cost cost(G((S)) = Σ
|Gp Gyll:
(R.ates
Epggle lip- اll (e.g., by ana- lyzing the expectation and applying Markov's inequality). Therefore, the result for maximum matching is immediate from Lemma 2.2.
which is w.h.p. (1- =1
For maximum TSP, consider tour S of G(P). It decom- poses to three matchings M1, M2, M3 (in fact, if is even then Mg is the empty set, and otherwise it contains single edge). Thus,
1.2. Preliminaries
For simplicity, we only consider random linear maps defined by a matrix of Gaussians as in many prior works.
Definition 1.1. A Gaussian JL map is a f x matrix with ii.d, entries drawn from (0, t).
cost(G (G(S))=)
= Σ Σ
|Gp - Gqll
The following is a crucial lemma in our analysis, which bounds the expansion of balls under a Gaussian JL map.
{p.g)EM.
3
Σ 1p- all 3 optmax-match (P)
Lemma 1.2 (Lemmaa 4.2 in (Indyk & Naor, 2007)). Let X C B(O,1) 1) be a subset of the Euclidean unit ball. Then there are universal constants e, C > such that for > C-ddim(X) (i)mm(X),,111
i=1 {p.9)EM,
=cost(S) + 35 0pp. opt (P))
1, and a Gaussian JL map G e Rtxd
Rescaling e concludes the proof.
Pr(Er E | > D) < -e-a
Our result for max-matching generalizes to hypermatching. where edges in the matching are replaced with k-hyperedges (e.g., triangles). Formally, in the max k-hypermatching problem, is multiple of k, and the goal is to partition P into n/ h sets SI....,S,/aa each of size k to maximize En/k Epges, lp - qll-
2. Maximum Matching and Max-TSP for Doubling Sets
In this section, we prove dimensionality reduction results for maximum matching and maximum traveling salesman prob- lem. Denote by opt, max-mathhhh and mptmax-tep the optimum
3

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
and d, A, N, and Gaus- sian JL map G TRexd with suitable t = O Xoo 5). Then for every set P C "d with ddim(() = X, with proba- bility at least 2/3. a (1 approxximani to the maxinum k-hypermatching of G() is a (1 + (())) (pprxxiipoi to the maximum k-hyppermatching of P.
Theorem 2.3. Let 0
Claim 2.5. Epepro S Sop((P))
Proof of Claim 2.5.
Σ PEP
p
Σ
(rp + rgg
i=0 M.qlEM.MMMr
The proof is essentially by picking e' = x and applying Theorem 2.1. The proof is provided in Appendix C.
Σ
8|p gll = =
(P.g)E M441
2.1. Proving Lemma 2.2.
where the inequality is by Equation (1).
A key observation in our proof is the following.
Lemma 2.4. Let M be a maximum matching of a dataset P with radius r. There exists ball of radius? 2 that contains every (p, () E M for which ||p- <ll S 4-
We will use helpful probability statement.
Claim 2.6 (Claim C.2 of (Makarychev et al., 2019)). There exists universal constant > 0 such that for all t d, and for a Gaussian JL map G e Rixd
Proof. Let (2, E M such that ||p all S _ and || - ull S F. We claim that y Bp, 5). from which the lemma follows.
Var E Rd r > 0, Pr[[|Ga||| > (1 + r)]l=))) -
The proof is by contradiction. Suppose 1|p- - x|| > (wlog, the same arguments hold for y). then there is a matching M' with cost larger than M - it the same as M, but with minor change, match the pairs (p. 2), (q. 3) (i.e., the pairs are switched). Indeed, the difference between the cost of M' and M is
We now analyze the error contributed by each ball. For every i E 2,, let N; be an er;-net of Pn Bi. By stan- dard arguments, it has size S N (2/e) (see e.g., (Gupta et al., 2003)). For suitable target dimension t= 0 log N) = O(e 0(e-=ddiing #ddim(P) log 2) the follow- ing holds for a matrix G E Rtxd of i.i.d. N(0, f): For every a > 1, x E Ed by Claim 2.6.
Σ (a.
aa- - b Σ l|a bll
M
Pr([|G=||| > (1+c))]]=|)) < exp(-S((e (aa2=t)) S N 22
= 1p 1p-pp x1| + 119 - vll - (lp all + |x- vll) -
> 1/2 22-2-1 2-22 =0,
By union bound over all pairs x, y E N,, with probability 21-2
and M' has larger cost, contradiction.
Vx, E N., |Ga - Gyll S (1 + ea)l =ll. (2)
Proof of Lemma 2.2. Let M be maximum matching of P. Denote by the radius of P. We construct a sequence of balls, such that intuitively, for every (p. 4) E M,, there exists a ball B in this sequence that contains g and [p all ((radius(B))
Additionally, for every y E N₁, we have by Lemma 1.2 that with probability 21- ooto.
Vp E Pn B(y,
|[G[p - v)ll s asr, (3)
The construction is as follows. Let Bg be the minimum enclosing ball of P. Let P1 be the set of points whose distance from their match in M is S á and B₁ be ball of radius? _ given by Lemma 2.4. In particular, P1 C Bi. Let Mj be the matching M induced on P1. Clearly, Mi is a maximum matching of P, (whose radius < 5). so we can apply Lemma 2.4 again, getting a ball B2 and P2 with
Thus, by union bound, with probability >
e-caa [N,] 2 - 2-a" the above hold for all y E N.. For every i, denote by a; the smallest a 2 for which Equations (2) and (3) hold. Therefore, for every j E N.
Pr(m: > Pr(ap>2' 2/-1) <Pi(Tr, E No, ||Gr - Gyll > (1 (2+ vll) + Pr E N., E Pn B(y, |Gp Gyl 2 2r-
radius smaller by factor of 2. Proceed in this manner, so for every E Z,, B, has radius r; $. By construction,
Vi E E4, V(p. g) E Mi \ M41.
1p- al 2 4. (1)
.2. 2 2-4-1
For every p E P. denote the last level that contains by ip. ie., the maximum such that p E P, \ P4+1, and denote the radius of that level by Tp-
Hence, Ea; S Ej- 2 Pr(a; 2 2/11 s E5 2'2 2-10-1 = =0(1).
4

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
Next, we consider random variable that captures the er- accumulated by all the balls together. Denote X == E as P.lri. We have,
Theorem 3.1. Let e E (0, n = ((1/62) be even and P (ei, ,nn ) be the standard basis vectors in TR.. Let G be a Gaussian JL map onto dimensions. If CloR(l/e) S
log(n) s log[1/e] for a sufficiently large constant C, then with probability 2 1 - exp(= - 1/n10 we have
EX- = Σ Piri =0 Σ PPlrs)
i=0
1=0
= 0 Tp) - (())t(P)).
(4)
opt max match (G(P)) 2 (V2- ==) opt
. mattmh (P).
PEP
The proof is by demonstrating matching with large cost in the target dimension. Note that mpt (P) v2. n/22, since all pairwise distances equal v2. After dimension reduction, the points are i.i.d. distributed [O, 44), hence are roughly mapped to be uniform on the unit sphere. Thus, we expect points to have an antipodal match at distance 2, so the matching would have size roughly 2 n/2. However, this holds on average, and it is unclear how to construct matching. We resolve this follows.
By Markov's inequality. w.p. > 9/10, we have X O(opt(P)). Assume this event holds.
Finally, we are ready to prove the lemma. Let M' be matching of P. We bound the cost of this matching on G(P). For every E P. consider level ip (recall, it is the last level containing p). For every (p.q) E M', assume wlog that ip S in (so B., S. B. Denote by Up E N the nearest net-point to p in that level, and by Map E N,, the nearest net-point to q in the same level ip. In particular, p E Blyp, ETp) and q Byysp eTp). By triangle inequality,
Lemma 3.2. Let E E (0, 1), t 2 C (loriy/s) large constant C > O. Let ø1. Ix be i.idd. draws from (0, L)) With probability E fraction of the x, satisfy ||22 V 1
e² for a sufficiently
exp(-Si(ne") at least
Σ
||pp Gall
(M-))EM'
Lemma 3.3. Let (0, 2(= and C Clog(1/e) < log(n)
Σ
||pp Gypll + |Gq - Gymol |l + [|yyp - Gym
e²
S CTon(1/E) for a sufficiently large constant C > O. Let ii,-.. Fn122 and y1,-." .ua/2 ,,n//" be i.i.d. draws from NO, Consider a bipartite graph H = (A, B) with bi- partition A = {II, _u/22] B {y1 ... .8n/2]. Put an edge between I; E A and y; E B if [|x, + yı ll S EVE.
(P-g)EM'
by Equations (2) and (3),
2eassTp + (1 + ea;,))l1b, yorll
(M.))MM
With failure probability at most 1/n we have
since Up, Bap are in a ball of radius rp. and by triangle in- cquality,
deg(z1) - EEdeg(<x)) )1 < =E(ee((11)-
Lemma 3.4. Consider the setting of Lemma 3.3. If C is a sufficiently large constant then H has a matching of size 2 nn/(11 E) with probability at least 1 1/n
Σ
4s0r + +11y> - pll + 111m - all + 1|p- all
(P.))EM' Σ
4sa;,Tp Tp + 2erp + 11p - all
For the proof of Lemma 3.4, recall the linear programming relaxation of the maximum matching problem on bipartite graph H = (AU B, E): max L( Zij subject to
(P-9)EM'
and by Equation (4),
Σ lp d/|
0 < zリ 1, v(i,))
+
(
Σ 2の V JEB
Σ
E ieA
This concludes the proof of Lemma 2.2.
It is a classic fact that any feasible (possibly fractional) solution to the above LP can be rounded to an integral solution with cost at least as large as the fractional solu- tion (even in polynomial time but we only need existence here) (Chakrabarty).. Using this, we can prove Lemma Lemma 3.4, whose full proof is deferred to Appendix D. The main idea is that we set each Zij to be ((1 + e) where A = E []deg(=1)]. The capacity constraints are sat- isfied since the capacity constraint for vertex F; sums to
3. 22 Approximation Lower Bound for Max Matching and Max-TSP
The aim of this section is to derive lower bound on the dimension necessary for the maximum matching (and max TSP) of a projected set of points to yield a better than v² approximation for the optimal cost of the original point set. Omitted proofs can be found in Appendix D.
5

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
deg( +)) < 1 by our degree concentration of Lemma 3.3. One check that this assignment also leads to large matching.
Theorem 4.1. Let and d E N. There is random lin- ear map g .Rd R. such that for every set P C RRd of even size, the ratio mlopt (g( /P)] mex-maath (P) P) is in [1, v2). Moreover, for a Gaussian JL map G E R txd with t = O we have with probability at least 2/3 that opt max (G)P)) is a (v2 + 5) appproxximttonn of max-maahh (P).
Proof of Theorem 3.1. We will prove the theorem by demonstrating matching with large objective value in the projected dimension. As noted earlier, opt, mptmaaxmatch (P) = v² 22 Furthermore, Ge, for 1 S i I n are all inde- pendent standard Gaussian vectors, scaled down by 1 1/vd. Partition the Ge 's into two disjoint sets of size n/2. Lemma 3.4 implies that (with high probability) we can find match- ing of size n n/2(1 e/100) among points across these two sets, satisfying that the vertices on every edge of the matching sum to a vector with & norm at most // //100. Fur- thermore, Lemma 3.2 implies that at least a (1 - -//1000) fraction of vectors in both sets satisfy that their &2 norms are 1 + =/100 (again with high probability). By a union bound, at least a (1 - 8/ e/10) fraction of the edges in the matching have both endpoints with l2 norms in 1 + That is, we can find n - e/110) pairs of vectors (in the projected space) such that every pair (a: y) satisfies (1) || + vll2 S e/100, (2) ||=|||, |lyl2 E + 8. By the reverse triangle inequality. this implies
In order to prove this theorem, we use the following lemma, which may be of independent interest. For a point set P c Rd the 1-median of P finds point E Id that minimizes Epep ||c |c-pll- pll-
Lemma 4.2. For every set P C R2, the cost of the 1-median of P is a v2-approxinmatin to mat (P). That is,
Σ
Ilu-el ell
max matching M on
{u.o)EM
<min CERd
Σ PEP
|ce
pll S S22
max matching M on P (u
Σ
1|u vil-
Proof of Theorem 4.1. Let E Rd be a vector of i..d. Gaussians distributed N(0, π /2). One could verify that for every x E Rd, Ellg x|| = || Denote by c* a point that realizes the 1-median of P. and by M maximum matching of P. The following holds.
| ul12 2 2 | - || + yllal
= 21 + 6) - || + y v122l 2 2 2()..
E max matching M
lg u g sTul] (u.0)EM
Σ
Thus, with high probability (more precisely with probability at least 1 exp
1/) which follows from combining the failure probabilities of Lemmas 3.4 and 3.2), we have demonstrated that a matching of weight at least 2 (1 - =) (2- - ((=))= Z OPT(P) (V2 - (()) exists in the projected space.
Σ {u.0)EM-
g Tu
Σ
Ilu-
e||-
(u.DEM
This immediately gives the lower bound of the claim. On the other hand, we have
We prove a similar lower bound as in Theorem 3.1 for the maximum weight TSP problem. The theorem below follows from carefully combining Theorem 3.1 on small subsets of the input dataset to form large cost tour.
E min ΣleTr cl
S
E
9 p
9 c01
CER
PEP
PEP
Σ
Ip--c11
-min
1|p
cll-
cER2
PEP
PEP
Theorem 3.5. Let E E (0, n = Q(1/E2) and P (ei,... ,Cn) be the standard basis vectors in R Let G be a Gaussian JL map onto dimensions. If Clog(1/E) <
Together with Lemma 4.2, we now have
6²
E max maicching M
Σ
gg Tu g gol
Ing(n) is Clog(1/e] for sufficiently large constant C, then with probability 2 1 exp( exp((S((n=))) - 11/225, we have
{a
< min CER
Σ pEP
1g p --c] cl
mpx (tpnxxxsspGPP2222 > (V2-e) optimax-ssppP (P).
< min
Σ 1lp-cc cl < V2
Σ
||u
eERd
PEP
(uN)EM-
4. A--oppoxxnnttionn for Maximum Matching
The "moreover" part follows by standard analysis of the expectation and variance of Chi-Squared distribution. O
We consider dimension reduction for maximum matching without the doubling assumption. We provide a similar result of 2-aprroximation for maximum TSP in Appendix E.
To prove Lemma 4.2, we use results on Tverberg graphs A weighted graph G = (V, F,, w) is called a Tverberg graph
6

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
if its vertex set V is subset of IRd the weight of every edge (u, v) E E is w(e) ||0 u||2, and if one places a diametrical ball B(wv)-
randomized dimensionality reduction can be very effective in reducing the runtime of geometric computation in high dimensions. This is not surprising and indeed, many empiri- cal and theoretical findings in the literature already validate
( for every edge e = {u, 2 E E., then these balls intersect, i.e., N(uAEEF (vvu) o 0. We will use the following result by (Pirahmad et al., 2024).
this hypothesis (this is the entire basis of the long line of work on the JL lemma). Our contribution is simply showing that the expected speedups are also possible for the various geometric problems we study, including many well-studied measures of dataset diversity maximization (to the best of our knowledge, we are the first to consider these problems under the lens of dimensionality reduction).
Lemma 4.3 ((Pirahmad et al., 2024)). For every pointsel P C. R' of even size, there exists a perfect matching that is Tverberg graph.
Proof of Lemma 4.2. By triangle inequality,
The second and the more salient point we demonstrate is that the effects of doubling dimension is an empirically observ- able phenomenon which can be quantitatively measured. In particular, seemingly similar datasets living in the same am- bient dimension, but with different 'intrinsie dimensionality, (which we theoretically formalize in terms of the doubling dimension) can behave wildly differently with respect to dimensionality reduction. As expected, datasets with lower intrinsic dimension can be projected to significantly smaller dimension while still preserving 'relevant' (with respect to the problem at hand) geometric information.
min
|cc 1c-2p pll N
max matching M
Σ
11u- u/|.
CERR
PEP
(u.
It thus remains to prove the other direction.
Denote by M a matching given by Lemma 4.3, and by p"
point in (o,u)EEs- B(vu). Let {v, ub E M Therefore,
||0 p"1l 1=1l S /2 1 pr 112 + 1u pr
S 2 F u/l,
where the first inequality is due to Sauchy-Schwar inequal- ity and the second inequality is because p" is inside the ball with wo as diameter and the angle up" " not acute, as illustrated in Figure 1. Thus,
Datasets We use two real and one synthetic dataset. For each dataset, we create a 'low-intrinsic dimension' version and 'high-intrinsic dimension' version. Both versions will live in the same ambient dimension and ostensibly they will be very similar, however, they will approximately cor- respond to versions of the dataset with low/high doubling dimension. We demonstrate that the 'low-dimensional" ver- sions have much more desirable behavior with respect to dimensionality reduction.
Dataset MNIST. We select 1000 randomly chosen im- ages from the MNIST dataset (dimension 784 with entries normalized to be in [0, 1)), restricted to the digit 2. We fixed the digit since it has been studied in prior works as example of a dataset with low-doubling dimension (Tenenbaum et al., 2000; Narayanan et al., 2021). This dataset is labeled MNIST '2' in our figures. For the "high-intrinsic dimension' version, we add i.i.d. Gaus- sian entries to all coordinates (note the noise of the same scale as the original entries). This dataset labeled MNIST '2' Gaussian in our figures.
Figure 1. Tverberg graph and point in the intersection of all
disks. The angle up" u is not acute.
min Σ nEBd PEP
||c pl
-
Σ
l|p-
pll
PEP
Σ {a.
V21lu - 1/| S 2
max
Σ
||u (u--o v||,
Dataset 2: CIFAR -erre--ebeddiing. We use penultimate layer embeddings of pre-trained ResNet models (Yu et al., 2021; Backurs al., 2024) in 1114 We use 1000 randomly chosen embeddings. These are the 'high-intrissic dimen- sion' version of the dataset. This is labeled Cifar-High in our figures. For the 'low-intrinsic dimension', we only keep the first 128 dimensions of these embeddings, but rotate the resulting points to also lie in 86144 using a ran- dom orthogonal matrix. This procedure simulates 'hiding'
matching M
{u,ueMs
concluding the proof.
5. Empirical Evaluation
We complement our theoretical results with an empirical evaluation. Our goal to convey two key messages: first,
7

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
MNIST
Embeddings chinging
High Doubling Dia Matching
theck Tigs Eoabiig feu Seath
0.30-
0.20
0.15
6:15
0.13
100
0.05
0.85-
0.00
20
5.05
0.00
Projection Dimension
Projection Dimension
Projection Dimonsion
Figure 2. Relative error versus projection dimension for maximum maximun-matching.
truly low-dimensional data in high-dimension. Note that this is not so obvious a-priori, since the rotation ensures the vectors are dense vectors in 166444, This is labeled Cif our figures.
Our greedy strategy builds the size h set in remote-clique and max k-coverage iteratively, by picking the best choice at every step. Such greedy heuristics have been extensively used in the applied literature on diversity maximization (see (Mahabadi & Narayanan, 2023) and references within), and demonstrate that they produce solutions quite close to the ground truth for real world datasets (Mahabadi & Trajanovski, 2024; Gollapudi et al., 2024).
Dataset 3: Synthetic. The 'high-intrinsic dimension'
version of this dataset consists of the basis vectors in IR.. This is labeled High Doubling Dim in our figures. The 'low-intrinsic dimension' version of the dataset the cumulative sums of the basis vectors, i.e. e1 + E2,..., 61 + + en. These two versions ap- pear to be similar, but it can be shown that their respec- tive doubling dimensions tively. They were also considered in the experiments of (Narayanan et al., 2021). ). This is labeled Low-Doubling Dim in our figures. We also consider a 'Small' version of the iigh-intrrinsc dimension' dataset, where we just take the first n/2 basis vectors. This labeled High Doubling Dim (Small) in our figures. We set n 1000 in our experiments.
For each problem, we compute a solution (using the afore- mentioned algorithms) in the original dimension. Then we reduce the dimension of our datasets, varying the target di- mension, and run the same computation the projected data. We then compare the values of the two solutions found and measure the relative error between them. In all of our results we plot the average over at least 20 independent trials and one standard deviation error is shaded. We implement our algorithms using Python 3.9.7 on an M1 MacbookPro with 32GB of RAM.
!2(log n) and (1)) respec-
Results: Effect of High Low Doubling Dimension Our figures empirically demonstrate that the "high-intrinsic dimensionality' versions of all of our datasets require a much larger projection dimension to achieve the same rel- ative error compared to the 'low-intrinsic dimensionality' versions of our datasets. This is displayed Figure 2 for the max- max-matching problem and the same qualitative results can be observed for our other two problems (see Figures 3 to 6 in Appendix F). As sanity check, the relative errors are decreasing in the projection dimension.
Note that throughout our figures, orange represents the "high-intrinsic dimensionality' versions of our datasets and blue represents the fow-intrinsic dimensionality' versions. Green is only used for our synthetic dataset, where also have third version where we take half of the basis vec- tors (the "high-intrinsic dimensionality" case) as a separate dataset version.
We focus our attention to three representative problems among the many that we study. We pick maximum weight matching, remote-clique, and max k-coverage. We selected these three since they are repre- sentative of our main theoretical results. For maximum matching, we experiment with the bipartite version by sim- ply dividing our dataset in half. This allows efficient exact solver using SciPy (Virtanen et al., 2020). The other two problems correspond to well-studied dataset diversity measures, many known to be NP-Hard to optimize exactly (Erkut, 1990; Chandra & Halldórsson, 2001), so we use a greedy algorithm as a proxy for finding the optimum.
Optimization Problems
In Figure 2, we see for the MNIST dataset that the rela- tive error achieved by projecting into 50 dimensions for the 'high-intrinsic dimensionality" version (orange curve) can already be achieved at much smaller projection dimension (approximately 20) for the -hwwiiiintiinicc dimensionality' ver- sion (blue curve). The same qualitative phenomena can be observed across datasets and problems that we study.
use
We would like to especially highlight the third plot in Figure 2. There, the orange and green curves are virtually identical, and both are much higher than the blue curve. However,
8

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
the blue curve corresponds point set with twice the cardinality than the point set for the green curve! Thus, for the max-matching problem (and also for the two other prob- lems we experiment on), the performance of dimensionality reduction is not determined by the size the point set, as the naive application the JL lemma suggests. Rather for these problems, the doubling dimension is the quantity of interest, as characterized by our theory.
A Acknowledgements
This research was initiated during the Workshop "Massive Data Models and Computational Geometry" held at the University of Bonn in September 2024 and funded by the DFG, German Research Foundation, through EXC 2047 Hausdorff Center for Mathematics and FOR 5361: KI-FOR Algorithmic Data Analytics for Geodesy (AlgoForGe). We thank the organizers and participants for the stimulating environment that inspired this research.
Results: Speedups Due to Dimensionality Reduction Lastly, we mention that, as expected, performing the com- putation in the projected space is much more efficient. Our Figures (see Figure 2 for maximum matching, Figures 3 and 4 for remote clique, and Figures and 6 for max k- coverage) already demonstrate that we can achieve small relative error for high dimensional datasets, by projecting them dimensions as low 20. Indeed, across datasets and problems, optimizing for three different objectives in the original ambient dimension, versus optimizing for them after projecting onto dimension 20 leads to speed ups of up to two orders of magnitude. The speedups for computing the objective in the projected space (taking into account the time required to perform the dimensionality reduction) is shown in Table 2.
Jie Gao would like to acknowledge NSF support through IIS-22298766, DMS-2220271, DMS-231 1064, CRCNS- 2207440, CCF-2208663 and CCF-2118993 Schwiegelshohn the support by the Independent Research Fund Denmark (DFF) under Sapere Aude Research Leader grant No 1051-00106B: Erik Waingarten thanks the NSF support under grant CCF-2337993.
Chris
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here. Our work of theoretical nature.
References
Abbar, S., Amer-Yahiaa S., Indyk, P., Mahabadi, S., and Varadarajan, K. R. Diverse near neighbor problem. In Symposium on Computational Geometry, SoCG, pp. 207- 214. ACM, 2013. doi: 10. 14.14444262355246644111
Arora, S. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pp. 554-563. IEEE Computer Society, 1997. doi: 199.099/FCCS.1997.6666 URL https: /ttp//cc.ooo/ 1997 646145.
Awasthi, P. and Sheffet, O. Improved spectral-norm bounds for clustering, In Gupta, A., Jansen, K., Rolim, J. D. P., and Servedio, R. A. (eds.), Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithmms and Techniques- - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cam bridge, MA, USA, August 15-17, 2012. Proceedings, vol- ume 7408 of Lecture Notes in Computer Science, pp. 37- 49. Springer, 2012. doi: 10. 10.10077978-336442-251111 URL https: / doi. org 10 100700.1.00//00 -32512-0_4
4.
642
Awasthi, P., Blum, A., and Sheffet, O. Stability yields a PTAS for k-median and k-means clustering. In 5/th

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
Annual IEEE Symposium Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Ve-
Chandra, B. and Halldórsson, M. M. Approximation algo- rithms for dispersion problems. Journal of algorithms, 38(2):33-445, 2001.
gas, Nevada, USA, pp. 309-318. IEEE Computer So-
ciety, 2010. doi: 10. 1 10.1110//OCC.20000 20000. URL
https: //os:///oo../ .ooiiorrggg www.///..... 09//FC5 2010.36 3.36.
Charikar, M. and Waingarten, E. The Linissnn-Lnddestrruus Lemma for clustering and subspace approximation: From coresets to dimension reduction. CoRR, 2022.
Backurs, A., Lin, Z., Mahabadi, S., Silwal, S., and Tar- nawski, J. Efficiently computing similarities to pri- vate datasets. In The Tweifth International Conference on Learning Representations, 2024. URL https: / //openreview.oomm wwtp:/iiwww..eeeeeeeeeeeeeeeeeee
Chen, X., Jiang, S. H.-C., and Krauthgamer, R. Streaming Euclidean max-cut: Dimension vs data reduction. In Pro- ceedings of the 55th Anmual ACM Symposium on Theory of Computing, pp. 170-182, 2023,
net wwwttnrrtrr// 500v999
Bartal, Y. and Gottlieb, L. Near-linear time approximation schemes for steiner tree and forest in din-dimesiional spaces. Khuller, and Williams, V. V. (eds.), STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pp. 1028 1041. ACM, 2021. doi: 10.1145//406335534510000 URL https: doi. wrg. 1 11411144///32 3451063.
Clarkson, K. L. Nearest neighbor queries in metric spaces. Discret. Comput. Geom., 22(1):63-93, 1999. doi: 10.100 7/PL00009449.
Cohen, M. B., Elder, S., Musco, C., Musco, C., and Persu, M. Dimensionality reduction for k-means clustering and low rank approximation. In Servedio, R. A. and Rubin- feld, R. (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pp. 163-172. ACM, 2015. doi: 10. 00.11445/2446339277466666 URL ht. tps wtg.ooi......ooooooooooooooooe.. 10 1tt.:.1..111155. 10D...115//244460
Boutsidis, C., Mahoney, M. W., and Drineas, P. Unsu- pervised feature selection for the $kS-mean clustering problem. In Bengio, Y., Schuurmans, D., Lafferty, J. D., Williams, C. K. I., and Culotta, A. (eds.), Advances in Neural Information Processing Systems 22: 23rd An- nual Conference on Neural Information Processing Sys- tems 2009. Proceedings of a meeting held 7-10 Decem- ber 2009, Vancouver, British Columbia, Canada, pp- 153-161. Curran Associates, Inc., 2009. URL https: / //proceedings. wwwnrne.....e cc/ cctppper/pp/p////////////// hash chehh/55ce411 1011 g-Abstract. html.
Cohen-Addad, V. and Schwiegelshohn, C.
On the local structure of stable clustering instances. In Umans, (ed.), 58th IEEE Annual Symposium on Foundations of Computer Science. FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 49-60. IEEE Computer So-
ciety, 2017. doi: 10. 10.1109/FOCS.200 201... 14. URL https: /ttp::///oo.ooo http:/i..ooogg//o//o/oo////ooogd http://1..1199FFFO 1109/F0050000/ 20100.....0..11. 2017.14.
Dasgupta, S. and Gupta, A. An elementary proof of a
Cevallos, A., Eisenbrand, F., and Morell, S. Diversity maxi- mization in doubling metrics. In Hsu, W., Lee, D., and Liao, C. (eds.), 29th International Symposium on Algo- rithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LiPlcs, pp- 33:1-33:12. Schloss Dagstuhl- Lecibniz-Zentrumm für In- formatik, 2018. doi: 10.4330LIPCCS..AAAA.20.... URL https:ttt///.. /t/////..ii /ttp//o..og/...2000..0. 02t0:/10.4230//111 SAAC. 2018.2212 33.
theorem of Johnson and Lindenstrauss. Random Struct.
Algorithms, 22(1):60-65, 2003. doi: 10.1002/raa.1073 URL www.thttp//t/o....m http://ooooorrooo 100.//11.0..0 0020000///// 100000
10073.
Eigenschink, P., Reutterer, T., Vamosi, S., Vamosi, R., Sun, C., and Kalcher, K. Deep generative models for synthetic data: survey. IEEE Access, 1 11:47304-47320, 2023.
Erkut, The discrete p-dispersion problem. European Journal of Operational Research, 46 4641):48 60, 1990.
Cevallos, A., Eisenbrand, F., and Zenklusen, R. An im- proved analysis of local search for max-sum diversi- fication. Math. Oper. Res., 1444519994 2019. doi: 10.1287/M0OR.201 0982. URL https: //doi. 1287 /ooo. 2018. 0982.
Feldman, D., Schmidt, M., and Sohler, C. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM J. Comput., 49(3): 601-657, 2020. doi: 10.1137/18 https /to.ooo.rgg..................... http//...11///11 8117//11111111 8M1 209854.
URL
Chakrabarty, D. Deterministic rounding for bipartite match- ing and GAP. htt.tttsss::t...etttttttt wwt.ccs...aautttoo dartmouth st stiiBooudiingforrGeeeraaaaaeeedd Deterriin Problem.pdf.
Gollapudi, S., Mahabadi, S., and Sivashankar, V. Compos- able coresets for determinant maximization: Greedy is almost optimal. Advances in Neural Information Process- ing Systems, 36, 2024.
10

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
Gong, Z., Zhong, P., and Hu, W. Diversity in machine learning. IEEE Access, 7:64323-64338 July 2018.
Mahabadi, S. and Narayanan, S. Improved diversity maximization algorithms for matching and pseudofor- est. In Approximation, Randomization, and Com- binatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Schloss Dagstuhl-Leibnizz Zentrum für Informatik, 2023.
Gupta, A., Krauthgamer, R., and Lee, J. R. Bounded ge- ometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, FOCS, pp. 534-543. IEEE Computer Society, 2003. doi: 10.1109/SFCS.200 200......0.....2222.
Mahabadi, S. and Trajanovski, S. Core-sets for fair and diverse data summarization. Advances in Neural Infor- mation Processing Systems, 36, 2024.
Huang, L., Jiang, S. H., Krauthgamer, R., and Yue, D. Near- optimal dimension reduction for facility location. CoRR, 2024. doi: 10.48550/ARXIV.20 2211 105432..
Makarychev, K., Makarychev, Y., and Razenshteyn, P. Performance of Johnson-LLindenstaass transform for k-means and k-medians clustering. In Proceedings of the 51st Anmual ACM SIGACT Symposium The- ory of Computing, STOC, pp. 1027-1038, 2019. doi: 10. N0.1145/311327733336330
Indyk, P. Sublinear time algorithms for metrie space problems. In Proceedings of the Thirly-First Annual ACM Symposium on Theory of Computing, pp. 428-434. ACM, 1999. doi: 10.1145/301 250. 301366. 10.1145/50125000011333 055500000666666 URL
https: /tte://doo..oo hweddi...ogoooooooooooo org.
Indyk, and Motwani, R. Approximate nearest neigh- bors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Sympo- sium the Theory of Computing, STOC, pp. 604-613, 1998. doi: 10. 10.1145/2766988276688 URL https: //doi.
Martí, R., Martinez- Gavara, A., Pérez-Peló, S., and Sánchez- Oro, J. A review discrete diversity and dispersion maximization from OR perspective. Eur. J. Oper. Res., 299(3):795-813, June 2022.
Melville, P. and Mooney, R. J. Diverse ensembles for active learning. In Twenty-first international conference on Ma- chine learning ICML '04, New York, New York. USA, 2004. ACM Press.
276876.
Indyk, P. and Naor, A. Nearess-neighhoor-pressrvii em- beddings. ACM Trans. Algorithmss, 3(3):11, 2007. doi: 10.1145//273340.127334 URL https: /ttps:////i..// /ttc///c.ooo/////////// g/10. 11.0.114: 1et.:1114111333 1273347
Nacem, M. F., Oh, J., Uh, Y., Choi, Y., and Yoo, J. Reli- able fidelity and diversity metrics for generative models. ICML, 119:7176-7188 February 2020.
Indyk, P., Mahabadi, S., Mahdian, M., and Mirrokni, V. Composable core-sets for diversity and coverage maxi- mization. In Proceedings of the 33rd ACM SIGMOD- SIGACT-SIGART symposium on Principles of database systems, pp. 100-108, 2014.
Narayanan, S., Silwal, S., Indyk, P., and Zamir, O. Ran- domized dimensionality reduction for facility location and single-linkage clustering. In Proceedings of the 38th International Conference on Machine Learning, ICML, volume 139 of Proceedings of Machine Learning Re- search, pp. 7948-7957. PMLR, 2021. URL http: //proceedings mlr waa.r.press/vv11 http:///vv///aaaaanana narayan an2lb.html.
Izzo, Z., Silwal, S., and Zhou, S. Dimensionality reduction for wasserstein barycenter. Advances in neural informa- tion processing systems, 34:15582-15528 2021.
Jang. S. H., Krauthgamer. R., and Sapir, Moderate dimension reduction for k-center clustering. In 40th International Symposium Computational Geometry (SoCG 2024), volume 293 of Leibniz International Pro- ceedings in Informatics (LIPIcs), pp. 64:1-64:16. Schloss Dagstuhl- Leibniez-Zeetteee für Informatik, 2024. ISBN 978-3-95977-316-4
Nil, I. Is the kth central moment less than the kth raw moment for even k? Mathemat- ies Stack Exchange, 2021. URL https: / stmath.stackeccharee com/q/40104000/0 wubbechwwgg/nnnn...eccccccccceee nil.
Johnson, W. B. and Lindenstrauss, Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26:189-206, 1984. URL hww.h:ttt/////tt semantiis scholar. org/ /ttp:/opsss::111111155.
Ostrovsky, R., Rabani, Y., Schulman, L. J., and Swamy, C. The effectiveness of Lloyd-type methods for the means problem. ACM, 5966)228:1228:2,, 2012. doi: 10. 10.1445/29551162299111 URL https: //tess///oo... .oi.or 2395117.
Kolliopoulos, S. G. and Rao, S. A nearly linear-time ap- proximation scheme for the Euclidean k-median prob- lem. SIAM J. Comput., 3788) 2007. doi:
g/10 1/110.114/23388
Pirahmad, O., Polyanskii, A., and Vasilevskii, A. Inter- secting diametral balls induced by geometric graph. Discret. Comput. Geom,, 71(2):480-49) 2024. doi:
10. 10.113775009133397244005555 URL https: /do 1lorg//...137//0009777

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
10. 10.100775500444-022-00557771 URL https:
Shenmaier, Efficient PTAS for the maximum traveling salesman problem in metric space of fixed doubling
dimension. Optim. Letr. 16(7):211-21122, 2022. doi:
10. 10.10077/1115500011--106666 URL https::/p///o /doi 0tg/10.11017 /0007//1119900 02000000021----11011
Tenenbaum, J. B., Silva, V. d., and Langford, A global geometric framework for nonlinear dimensionality reduction. science, 29015500))2319-2333, 2000.
van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of Machine Learning Research, 986)) 2579-2605, 2008. URL http: jmlr. org/papez //v//vandeermateeO@aaa... html.
Virtanen, P., Gommers, R., Oliphant, T. E.,, Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, Millman, K. Mayorov, N., Nelson, R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, I. Feng, Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E. A., Harris, C. R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F,, van Mulbregt, P., and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 1110388441592-019-0668888
Wainwright, M. Basic tail and concentration bounds, pp- 21-57. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Yang, Y., Ma, Z., Nie, F., Chang, X., and Hauptmann, A. G. Multi-class active learning by uncertainty sampling with diversity maximization. Int. J. Comput. Vis., 113()):113 127, June 2015.
Yu, D., Zhang, H., Chen, W., and Liu, T.Y. Do not let privacy overbill utility: Gradient embedding perturba- tion for private learning. In International Conference on Learning Representations, 2021. URL https: //openrevies foree//orumiiii do
12

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
A. Remote Subgraph Diversity Measures
In this section, we consider remote subgraph problems, which include many well studied diversity measures. The goal is to find a subset P of size that maximizes a certain diversity measure of S. The diversity measures we consider satisfy the following.
(P) Given set of points S, compute the minimum/maximum of the sum of edges over a subgraph family, where all elements the graph family have the same number of edges.
Theorem A.I. Let O < < and d, X, k N, and Gaussian JL map G B with suitable t O(
log k))-
Then, for every set P Rd with ddim(P) X. with probability least 2/3. the following holds. Let a diversity measure div and denote by the problem of finding a subset S C P of size k that maximizes div(S); if div satisfies Property (P), then every (1 + -approxmmaee solution for π (G(P)) is (1 -apprxiito solution to π (P)).
Corollary A.2. The theorem above holds for the following diversity measures of the set S:
Remote-edge: minp.ges - -ql--
Remote-clique: Ep.es |lp qll-
Remote-tree: weight of a minimum spanning tree of S.
Remote-star: minpes Egerrp lpp g/l-
Remote-cycle: length of a minimum TSP tour of S.
Remote-matching: weight of a minimum perfect matching of S.
Remote- psenofoosss Epes dist(p, S (pp)).
The dependence the doubling dimension is tight, can be seen by the following.
Theorem A.3. Let n E N, there exists set P of n points, such that for Gaussian JL map G onto dimension Let be problem as defined in Theorem A. If is defined for 2, then x (G(P)) 2 22(
((P) with high probability.
This theorem can be seen as a direct corollary of a similar statement for the diameter of the dataset; one can find proof in the full version of (Jiang et al., 2024).
Lemma A.. Under the same conditions of Theorem A.3, the diameter is distorted by factor 92 2 logn with high probability
Proof of Theorem A.3. For k the problems for which Theorem A.l applies are identical to computing the diameter,
Applying Lemma A.4 concludes the proof.
A.1. Proof of Theorem A.1
The proof of Theorem A.1 uses the following two lemmas. For a point set P, the k-center problem finds a subset S C P with [S] = & such that every point in P is within distance from some point in S, with the goal of minimizing the radius We denote by KC2 (P) the radius in the optimal k-center solution. The following lemma is well-known. See e.g. Lemma 2 in (Abbar et al., 2013).
Lemma A.5. Let d, le E N and point-set P Rd. There exists set S P of ls points such that for every x, y E S. + y. we have || vll 2 (P)
The next lemma is implicit in (Jiang et al., 2024). We provide proof at the end of this section for completeness.
Lemma A.6. Ler 0 < c and d, l N, and a Gaussian JL map G E Rtxd with suitable O(c (A log k)).
Then, for every P Rdd with ddim P) X, with probability at least 2/3, for all 3ı, 22 P.
| Gaall E (1 + t)llo - x2ll + cKCr(P).
13

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
Proof of Theorem A.I. Consider target dimension as in Lemma A.6, and suppose the event therein holds. Consider remote subgraph problem x with diversity measure div satisfying (P), and suppose that given k-point set, div's value is over set of I edges. Assume that div is minimization problem, is the case for all problems in Corollary A.2. The proof regarding maximization problems is by the same arguments.
Consider a set 5 size given by Lemma A.5. Let E be a set of I pairs of points (edges) in $ that realize div(S). By Lemma A.5, div(5) = (a.))e | - yl1 2 1 Therefore,
TPP) max div(S) 2 1. KCK-I(P).
(5)
Scr|ssi=k
Let S' C be set of size k. Let E", E be sets of l pairs of points in S' that realize div(G(())) and div(S'), respectively.
divc))())))((())))
Σ
|Gr Gyll
(2.V)EE
since div is minimization problem.
$ Σ (x,8)E
|Ga - Gyll
by Lemma A.6,
I Σ (1+ w/1 (PK
(x.))EE*
<(1 divv"))) (dc
by Equation (5),
<(1 + e))v)) + ET(P).
The other direction that div(G((")) 2 (1 - 2c) div(s) - eT() follows by the same arguments. Rescaling e concludes the proof.
To prove Lemma A.6, we use the following, which easily follows from (Gupta et al., 2003) (see also the full version of (Jiang et al., 2024)).
Lemma A.7. For every P C Rdd 0 < <e< 1 and k E N, there exists an
of P whose size is S k(2/e)ddim(())
Proof of Lemma A.6. Let N be an J0 KCC of P of size S (440/e)dddau()) given by Lemma A.7. For suitable target dimension O(e 2 log ]. the following holds: First, by the JL Lemma, with high probability, all the pairwise distances for points in N are preserved up to a factor OF1 1 + e. Additionally, for every E N, we have by Lemma 1.2 that with probability 1 - - e every x E PU Bly 20 (P)) satisfies |[G(z - b)ll < 6 (P)). Thus, by union bound, this holds simultaneously for all E N with probability at least 1 - e I Z 9 Suppose these events hold.
TO
Consider two points 22 E P, and let yı, 322 E N be their nearest net-points. Then, by triangle inequality,
| Gr
Gr2ll
< [[ - Gyi || + +|Ga2 - Gyell + |Gy - Gyzll
since ||G[r; - wi)l $ 6 (C,(P).
<12 ( -ell
by triangle inequality,
<12 e|( -vlll + ||,0 v2ll + || x2ll)
14

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
since |1,;
3/l S 20 Kk
(L -x2l
and since e < 1,
SeKC,(P) + (1+ +]||=] -221-
The other direction, that |Gz1 Gzall 2 (1 - c)] - x2ll - cKCC(P)) follows by the same arguments. This concludes the proof of Lemma A.6.
B. Problems with Large Optimal Value
In this section we show that large class of optimization problems, including many diversity measures, which have 'large" optimal value can be preserved via dimensionality reduction in a black-box way. We consider optimization problem of the form "pick the best subset of size k to maximize the "diversity" from each point to the set" (formalized below).
Theorem B.1. Consider an optimization problem of the following form: given (P, k. f) as input where P C Rd k E N.
and] f R + satisfying (z) - f(y)] S T.| - y|loo, let
opt P)
max
E(p,, CCPSS PEP
where S), f(pp) with up R with (Up); lpp s; for all i. Let Gaussian JL map G BRtx with suitable = O( D(E=>Xlog((,. + 1)/e)). For every P C R2d with ddim (P) >, with probability at least 2/3,
(opt(P) (Gt))( S (s diameter(P))
Proof. Set = diameter(P). Note that for any set of points P, the 1-center cost is (2(A). Thus, the case of Lemma A.6 implies that
Pr PVax, E P. ||Gr Gyll E || yll + 100) > 2/3
if we project to O(e-2. A Alog(1/s) dimensions (note we can replace multiplicative error with additive error since the additive error is proportional to the diameter). We condition on this event.
Now let and S' be the maximizing sets for OPT(P) and (PT(G(P)) respectively. Note that S' is random variable since depends on G. We will explicitly specify which of points being used evaluate and in what space (the original projected space).
From above, we have that
||lp - - - G&ill s1/000,
for all points p and 8; it follows that
Σ
S) Σ F(G), L |P| eA/100
pEP
PEP
since f is assumed to satisfy the lo Lipsschc
conercctiinooiitioon...omm condition. Similarly, we have
Σ F(Gp, G(S')
Σ S() L. PPI -PI
PEP
But by definition of optimality, we know
Σ F(p N Σ Fly,St
PEP
PEP
Σ
L -PI--000000
PEP
15

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
and similarly
Σ
F(Gp, G(S'))
Σ F(G,),G(S))
PEP
PEP
Σ
F(v,S) - L. [P] 12/110,,
PEP
we have
[OPT(P) OPT(G(P))
Σ F(p.S) Σ F(G).(((S)
PEP
PEP
SL |P| e2/50.
The first part of the theorem follows by rescaling and the 'moreover' part follows by the same arguments.
While Theorem B.1 is stated in quite general terms, there many natural choices of functions f. We give non-cxhaustive list below:
((x | which generalizes the Max k-coverage diversity measure (which corresponds to p oo). Note that in the context of Theorem B.1, Max k-coverage picks out the largest distance from input p to the set S, whereas the lp formulation combines all distances in smooth way.
f(x) d., which special case of the choice above, which in the context of Theorem B.1 averages the distance from every input point to distances to all points in S.
f(z) = median(z;), which can be thought of as picking the 'typical' distance from an input point to the set S, which maybe more robust to outliers.
In many cases of f stated above, it is true that OPT(P) = Q|[P) diameter(P)), leading to the following corollary. Corollary B.2. Consider the setting of Theorem B.1. of) (I[P| -diameter(P)) then we can achieve
[opt(P) - opt(G(P)) S é opt((P)
with probability at least 2/3.
Remark B.3. This result extends to preserving approximate solutions by the same arguments.
We highlight two cases where Corollary B.2 holds:
The maximum degree of the geometric graph defined by all pairwise distances between points in P under dimensionality reduction. This corresponds to (P, ||x|||] in Theorem B.I, where L 1.
The Max k-coverage diversity measure which also satisfies in Theorem B.1. This generalizes the maximum degree example, which the k = I case.
Corollary B.4. Consider the maximum k-coverage problem:
opt(P)
max SCP. mk
Σ
max ||p
s|]-
SES
PEP
Let a Gaussian JL map G E Ruxd with suitable 1 = O 2 log()/))). For every set P C Rdd with doubling dimension X with probability at least 2/3,
- opt < opi(P). -
Moreover, every (1 + E) appprxxmiet solution of opt is (1 + ((e)))-pproximmate solution opt (P).
16

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Additionally, since the maximum degree of the graph is special case of spanning tree, by the arguments have the following for maximum spanning tree.
Theorem B.5. Under the settings of Corollary B.4, with probability at least 2/3, the maximum spanning tree of G(P) is (1 + aapprooximannnnnn of the maximun spanning tree of P.
Moreover, the dependence the doubling dimension is tight for these problems, essentially because the optimum value closely tied the diameter of the set, so by Lemma A.4, we get the following.
Theorem B.6. Let n E N, there exists a set P of n points, such that for Gaussian JL map onto dimension t, the cost of maximum spanning tree, maximum degree, and maximum k-coverage is distorted by factor 92( log
C. Proofs in Section 2: Max Matching and Max-TSP for Doubling Sets
Theorem 2.3. Let 0
1 and d, N, and Gaussian JL map G Rexd with suitable t 2ke- llog :
Then for every set P C Rd with ddim(() = X, with probability at least 2/3, (1 + -approxiiaatin to the maximum k-hypermatching of G(P) is a (1 + apprrxiiaaiinooo to the maximum k- k-hypermatching of P.
Proof. We consider Gaussian JL map as Lemma 2.2, but with = = As proof of Theorem 2.1, is immediate that w.h.p.. (pt(G(P)) 2 (1 - opt Therefore, we focus on proving other direction.
Consider optimal k-hypermatching of G(P). We can decompose it to O(k) matchings M1...., M Thus, by Lemma 2.2,
opt(G(P)) = cost(G(M,,))
cost (M,) E opt mptx
$ opt(P) + e'm o'mmppommxx.mttteeee (P)
< (1 + (PP)
D. Proofs in Section 3: 22 Approximation Lower Bound
First we begin with some helpful probability statements.
Lemma D.1. Suppose NN 12) and let 7 O(1) We have
Pr([I=]12 S TVT) 2 exp(-O((log((/))))
Proof. Note that if |ay] S y for all then must have ||0/||2 S / lower bound the probability that [ax]] S 7 for all
i. From the density function of Gaussian, know that Pr(1z,] 7) O(7), so it follows that
Pr(vi,
J S 7) 2 0(7)* exp( (xx((=((llog()))))
The following a straightforward corollary of Lemma D.I. Corollary D.2. Let (0, 1),
log(n) (lg((17))
for sufficiently large constant C' > Ifr N' 4:) then
Pr[[|x]12 S TVt) 2 n o0//C)
Lemma D.3. Suppose NN(0 It), y N1 I--1) and fix V2. There exists an absolute constant C' >> 0 such that
Pr (llll2 57) 5 Ctt Pr (||zl1a S )
17

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Proof. We can decompose
Pr(Il/l22 >) Pr(llv122 5 + 2 llvla S r).
Note that the former least
Pr (1lvl22 S exp(-r3/4) Vol(B__10,,//22),
T--1
where BI-1 (0. is centered ball of radius T/ 2/ in R--1 and T--1 is the normalization constant of the Gaussian density function. On the other hand, if l|vl|2 2 7/v2, we can bound
ex)(-r-/4) Vol(BI-1(0,7))
Pr(r/v2 |1ull2 <)
T--1
O exp(--111) Ti-1
Vol(Bi-100,7/V2)
(6)
some sufficiently large constant C", Thus suffices to compare Pr([Iv]22 S <\/22) and Pr([]=r|22 S <T/V2). However, both ll/l2 and | are chi-squared random variables (with || having one more degree of freedom), and from their density function, it suffices show
10 11122 x1/2-16- dx (
2
((0-1)/2-1e--/ dz.
(Note that we have ignored the normalization constant since the ratio of the larger to the smaller can easily be seen to be bounded by exp(O(tt).)
Indeed, point wise, the function ///2-1 (1(-1)/2-1 for all > 1. To handle x S 1, we have fo x² dr k-1 multiplication term implies the left integral above is also larger over [o, 1]. Altogether, combining Pr(1lylle S T/v2) S cx)(O(t)) Pr(1a=l12 S T/v2) with Equation completes the proof.
1 so the 2
Lemma D.4. Lete E (0, 1) and SI. Sn be identically distributed and possibly correlated indicator variables satisfying
vi, E[S.] =
p 2 1/n0.1
vk 2 and distinct indices i,,..., E(S., Sig..
S.g...Sp. ...) S p) and
2 ((1/ee).
Let = Ei= S.. We have
Pr[[S - B[S] cE(S)) <
99
Proof. Fix m 2 2 an even integer. We first bound the moment E[STM). Note that for i, 2 1, S = S; since our variables are indicators. Let < S m. Since our random variables are also identical, by symmetry, we only have to understand the Sx] that we get the multinomial expansion. First, we can pick these indices in (?)
number of terms the form E[S,... [y] ways. Then by classic stars and bars, there are at most (m+t-11) < (m+hh) ways to assign these k indices all the m powers. This gives us
272
m + 1)) 1) k
E S
(n 4)
k
22m
0.000
k
k
18

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Since non-negative, know (e.g. see (Nil, 2021)) that
E||s
which by Markov's inequality implies
E E[S] m²
E s
Pr( - E(S]
n
m
Setting À = =E[S] emp and using our estimate above,
Pr([S
E[S] 2 =E[S])
22m
p))
(Emp) T
m
2
n 0.001k
12" km mm
m
2 m
since p 2 0.11
n 0.9 -.0000000kkg
Set m 0.99 (assuming n. 0.99 is an even integer. We omit floor/ceiling signs and a rounding up or down by 1 to ensure evenness, since both inconsequential.. We claim that for any h: S m.
22emm m
&
0.9m(m 00.001k S
k2
n 100
This is true if and only if
n 100 (2)²m)* < 1:2h -)
n 200/ (26² m) S k2 (.2.,_.mmm/--)000.000 (n m/h //n 0.901
Since 1/6², we have n. 2 n 0.4, and for sufficiently large n, have 2c2m S 0.999 so it suffices show
100/k+119 < 2: 0m4//
100 + 1.9
S 2 llg((k) 0.4m
logn
log
If 0.4m/k 2 100/k: + 1.9 then we are done. Otherwise, we have ..m/k < 100/k + 1.9 < 100/k + = 2
4m 100 2 n 0.98 for sufficiently large n. Then 100/k: + 1.9 < 1.95 for sufficiently large n and we have
100 k
logn n
1.9
< 1.95 1.95
and 2 log(k) 2 2. (0.98) log n 2 1.95 1.95log n, and we are done. Putting everything together, gives us
Pr([S - E(S) 2 =E(S]]
S
m
<
1
100
99
for sufficiently large n, as desired.
Clog(1/2) for a sufficiently large constant C' > O. Let FI. Fn/2 and ... Bn/2 be i...d. draws from N(O,, It). Consider bipartite graph H (A, B) with bipartition
Lemma 3.3. Let E 1). = (2==2) and Clog(1/e) < t < log(n)
A {xr,... In/2], }, = (vi.... .Vn/2)) Put an edge between x; E A and yj E B if II + 1yl12 S evt. With failure probability at most 1/n we have
deg(z1) E(deg(x; E(deg())))
19

---

Randomized Dimensionality Reduction for Euelidean Maximization and Diversity Measures
Proof. Ultimately our goal use the concentration inequality developed in Lemma D.4. Towards this, define the indicator variables S; [| + Vill2 I evi). The degree of is simply the sum of the S variables. Note that S, 's identically distributed but not independent of each other since they all depend 2 Furthermore, we know that Vi, E[S.] = p 2 1/n from Corollary D.2 by setting C' to be large enough in the definition of t. Thus we have checked the first two conditions of Lemma D.4.
The most interesting condition to check is the third hypothesis. For any distinct indices "
EiS,, ... -t.l = Pr(vii...... ik. 1f 22 + yirll2 S {vvt)).
We first transform this the event S ... St, into an equivalent but easier to handle event. Let U be the orthogonal matrix that sends 2 to scalar multiple of e1. the first basis vector. Note that U/ is random matrix that depends æ1 but not on any of the other of the Gaussians that we have drawn. By considering the density function of Gaussian, we know that U U1,,.. ... Uynn2 are i..d. Gaussians 21,-.' /2/2 again all drawn from (N0, It) (this fact is also referred to as the "rotational invariance' of Gaussians). Since U is an orthogonal matrix, we always have | + yill2 = ||U' + Uyill2. so
S. = 1| + velle S EV
1[] U2l S eV 1[1 + 2112 S SvV
where we again note that Uz, is a multiple of the vector e1. Now the crux is that for ||ا| + y lll2 S EVt to hold, it must also be the case that [|Ux] + =11l2 & evi, which implies that || 8vl must also hold, where & E R is the vector where simply remove the first coordinate of 2; (|Uxx + 2ill2 is sum of positive terms so if the sum is bounded, any partial sum must also be bounded by the same quantity). Thus,
Pr(Vii, de, 11 + yo l12 S EvE))
Pr(vi in. 1 la S =vt)).
However, the latter probability consists of independent events since the 2, are i.i.d. Gaussians N(0,, I-11. Thus,
Pr(vi...... in 1[1=1 + yi lla S EVεt) S Pr(1 S ev]))*
Since t = =2(1/=?) (and thus EVE = = (((1). Lemma D.3 implies that Pr(1 S eVt)= < C Pr([ + +3,, I =vv)===">
for a absolute constant C" > O. Now by setting C in the definition of t to be sufficiently large, we see that C"p S 0.001 satisfying the third condition of Lemma D.4. Thus all the hypothesis of Lemma D.4 hold and we are done.
Lemma 3.2. Let E (0, 1), 2 C ( for a sufficiently large constant C > O. Let F1, In be ii.dd draws from (NO, [)) With probability 2 exp( ((n))) least fraction of the 244 satisfy /| +e.
Proof. From standard concentration bounds for chi-squared variables, (see (Wainwright, 2019)), we know that any fixed xa satisfies | Vl 1 + with probability least say 1 g000 Since the x; independent, standard Cherooff bound implies that at least a 1 - e/100 x, satisfy ||z/|la/ Vi E 1 E except with failure probability at most exp(-S(n=")),
Lemma 3.4. Consider the setting of Lemma 3.3. If C' is sufficiently large constant then H has matching of size 2 n12(11 - c) with probability at least 1 - 1/n
Proof of Lemma 3.4. First we show that with high probability, all degrees of H are tightly concentrated. Indeed, using Lemma 3.3 and a union bound over all the (nn) vertices implies that with probability at least - 1/n all vertices have degrees within 1 + & of their expected degree. Condition on this event and set A E(deg(x1)) For every (i,j) E E, let zy = ((1 + =) -1, We can verify that for any 24 E A,
deg(r;) (1+
Σ žij
S
JER
20

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
since we know that deg(2;) S (1 +e) by conditioning. Thus all the constraints the vertices in A are satisfied and similarly check that all the constraints the vertices in B are also satisfied. Thus assignment is feasible and it has total value at least
Σ (,EE
-
E
E
(1+
EEA JEBI(i.)EE
1-E 1+E
Σ
2
|A[(L O(e))
The lemma follows.
Theorem 3.5. Let e E (0, == (2(1E23 and P {er. fer.... en be the standard basis vectors in TR. Let be log(n)
Gaussian JL map onto dimensions. If (1/(( 2 (-cxp(-S((nne) 1/n25, we have
o <t Clog(1/e) for sufficiently large constant C, then with probability
opt (GUm 2 (v2-s) opt max-ssp))
Proof. Split the basis vectors into = 1/e sets of en points each. Label the sets XI,..., ;1//e. consecutive pair X,, X1+1. there exists matching in the projected space of total weight at least en(2 =) between the pair (with the appropriate failure probability coming from Theorem 3.1). We condition the event that such a matching exists for all consecutive pairs in the projected space (this event happens with probability at least union bound).
e. By Theorem 3.1, for every
1/n by
Given this, we explicitly demonstrate a large weight tour in the projected space. First by following the matchings across all pairs of sets, we have en edge disjoint paths, each with 1/c edges. Each path has total weight at least (2 <)/E by our conditioning, so the total collection has weight least n²2 - +). Connect the endpoints of these paths to form tour. The extra added connections can only increase the cost of the tour. Thus, we have demonstrated one possible tour in the projected space of cost least n22 - E). However, any tour the original space, including the optimal maximum cost tour, has total weight n n2 since all distances are /2, proving the lower bound as desired.
E. 2-Approximation for Max TSP
We believe that maximum TSP behaves similarly to maximum matching, and a Gaussian JL map yields a (v2 + z)- approximation for maximum TSP with high probability. Such result would true assuming that for every set P C RR.. there is tour that is Tverberg graph. However, this is open question about Tverberg graphs that is still unproven (Pirahmad et al., 2024). We still able prove unconditional bound, of (2 + a)approoxiattion
Theorem E.1. Let 0 < & < 1, d N and a Gaussian JL map G ggxd for suitable O( - log -) For every P Rd. with probability at least 2/3, we have that mptmax-ss (G(()) is a (2 -ppproxximiaio of opt
To prove this theorem, we use the following.
Lemma E.2 (Andyk, 1999)). For every set P C Rd,, the cost of a uniformly random tour is (2 + + approximmaiio of max-axt (P) with probability ((e).
Proof of Theorem E.1. Consider a suitable number O(=-1) of uniformly random tours. After applying G, these are still uniformly random tours. Choose the number of random tours with probability 2/3, one of them is (2 2 apprrxximmtiionnn of max- (G))).. By our choice of the target dimension and union bound, with probability at least 2/3, the cost of all of these tours is preserved to factor + e. This concludes the proof.
F. Additional Experimental Results
See Table 2 for speedups obtained by dimensionality reduction for the problems we study, as well as Figures 3 to 6 for omitted figures from Section 5.
21

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Speedup by Computing
Problem
Dataset
in Projected Space
MNIST
11.41x
Maximum-Matching
CIFAR
75.07x
Basis Vectors
10.98x
MNIST
6.01x
Remote Clique
CIFAR
38.14x
Basis Vectors
7.50x
MNIST
13.73x
Maximum Coverage
CIFAR
121.34x
Basis Vectors
17.37x
Table 2. Speedups obtained by projecting the point sets onto dimension 20, compared to optimizing in the original ambient dimension. For Remote Clique and Max Coverage, we set the value & 10, although the same qualitative results hold for any average over 10 trials.
MNIST Remote-k-Ciin Cliiqu,
CIFAR Remote-k Kemote---Clique,
WHST
CEAD-Le CEAD
Loe khe Dam *
0.8
0,5
Rigs (velog lvs Hiadl
06-
Peclatoo Stree
0.5
0.3-
Dalatte
034
0.1
02-
56
0.5
Projection Dimension
Projection Dimension:
Projection Dimension
Figure 3. Relative emor versus projection dimension for remote-k-elique. We set 10 here (see Figure 4 for l: 20).
22

---

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
MNIST Remote- Ciique, ==
CIFAR Remote Clique, 20
Boohling
Clipue,
0.5
* Lorbstingnn
0.7-
NAST Gesris
CEXhikt
Ras Fvatee Roud)
0.6-
0.5-
0.5
0.44
0.2
00
0.0
Projection Dimension
Projection Dimension:
Projection Dimension.
Figure 4. Relative error versus projection dimension for remote-k-clique. We set k: = 20.
MNIST Mex-k- Coveragee
CIFAR Maw---Covveeappe k 10
* Lov Dwrbiiing Dum.
0.8-
MAST (Ba01)
C990 MA
Has thed the toudd
5.4
0.6-
0.3-
0.2-
0:3-
6.0-
0.0
Projection Dimension
Projection Dimension:
Projection Dimension
Figure 5. Relative error versus projection dimension for max-coverage. We set k = 10.
Mavek-Caveragee
Coverage,
WIST
CEAP- CEMP
*e Loe wwebaleee Dim Hi (velly Ihs teadl
0.8
2.4-
0.55
0.c-
6.3-
Belntte
62-
6-34
0.1
0.2
Projection Dimenston
Projection Dimonsion
Projection Dimension
Figure Relative error versus projection dimension max-coverage. We set 20.
23


Reviews:
[{"review_id": "vNQU8exNeP", "reviewer": "Reviewer_74V2", "summary": "This paper studies randomized dimensionality reduction for geometric optimization problems such as max-matching, max-TSP, and max-spanning tree. It introduces a novel approach where the reduction is based on the doubling dimension of the dataset instead of the dataset size. The authors prove that reducing the dimension to O(λX), where λX is the dataset's doubling dimension, is sufficient to preserve the value of near-optimal solutions. They provide both theoretical proofs and experimental results to validate this claim. The experiments show that this method maintains solution quality while significantly improving computational efficiency.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.\n\n**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.\n\nAs 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.\n\n**2) Comparison to manifold learning:**\nOur paper focuses on proving worst-case theoretical guarantees. We do this by using data-oblivious maps based on the Johnson-Lindenstrauss (JL) Lemma.\n\nIn 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.\n\nFor 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.\n\n[Ref 1]: Dimensionality reduction: theoretical perspective on practical measures. NeurIPS 19.\n\nWe also refer to the response to Reviewer jiNF for many works related to the JL lemma that have recently appeared in top ML venues.\n\n**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).\n\nWe 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.", "claims_and_evidence": "Some theoretical claims, particularly on the optimality gap after dimensionality reduction, lack detailed derivations.\nThe experimental validation is limited to specific datasets (e.g., MNIST, CIFAR). It is unclear how well the method generalizes to other domains, such as NLP or structured data.\nThe paper does not directly compute the doubling dimension (λX) but estimates it through experimental trends. This indirect approach makes it unclear how to determine λX efficiently in real-world applications.", "methods_and_evaluation_criteria": "The method relies on estimating the doubling dimension, but it is not clear how to precisely compute λX for arbitrary datasets. In some cases, especially for high-sparsity data (e.g., NLP embeddings), estimating λX may be difficult or computationally expensive.", "theoretical_claims": "The method assumes that estimating λX is feasible, but does not provide a practical way to compute it efficiently.\nIt would be helpful to discuss whether similar guarantees hold in non-Euclidean spaces.", "experimental_designs_or_analyses": "1.The paper mainly uses image-based datasets, which may not reflect the challenges of high-dimensional sparse data.\n2.The paper does not provide a direct computation method for λX but relies on experimental behavior to infer its impact. It is unclear how well this estimation method applies to other types of data.\n3.The paper mainly compares against JL transforms but does not benchmark against other adaptive dimensionality reduction techniques (e.g., PCA).", "relation_to_broader_scientific_literature": "The paper contributes to the intersection of dimensionality reduction and combinatorial optimization. It builds on the Johnson-Lindenstrauss lemma, extending it to optimization problems.", "essential_references_not_discussed": "The paper does not compare well with manifold learning techniques , which also reduce dimensions while preserving geometric structures.", "other_strengths_and_weaknesses": "Strengths\n1.Theoretical novelty: The paper introduces an innovative way to determine the target dimension using the doubling dimension.\n2.Computational efficiency: The method shows a clear advantage in reducing computational costs.\n3.General applicability: It applies to a variety of geometric optimization problems.\nWeaknesses\n1.Limited empirical validation: The experiments do not cover enough diverse datasets.\n2.Unclear computation of doubling dimension: The paper does not provide a direct method to compute λX, which limits its practical use.\n3.Missing comparisons: Other adaptive dimensionality reduction techniques (e.g., PCA, deep learning-based methods) are not compared.", "other_comments_or_suggestions": "Please see the above weakness", "questions_for_authors": "Please see the above weakness", "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": "Jk6MEK3Dqq", "reviewer": "Reviewer_6YCZ", "summary": "The paper studies randomized dimensionality reduction for a range of the Euclidean optimization problems, including max-matching,\nmax-spanning tree, max TSP, max k-coverage, and subgraph diversity. In particular, the paper relates the target dimension to the doubling dimension $\\lambda_X$ of the dataset $X$ and shows that $O(\\lambda_X)$ suffices to approximately preserve the near-optimal solution. The paper also provides a lower dimension bound for a $\\sqrt{2}$ approximation. Finally, the paper also gives an empirical evaluation that shows the speed-up of the proposed dimensionality reduction and demonstrates that the effects of doubling dimension is an empirically observable phenomenon which can be quantitatively measured.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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?\n\nWe thank the reviewer for their careful reading and comments.\n\nThe 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).", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The proof in the main body looks correct to me, but I did not carefully check the proof in the appendix. I have some question about the claim made in Table 1 (for details, see the below question).", "experimental_designs_or_analyses": "The experimental design looks reasonable to me.", "relation_to_broader_scientific_literature": "See \"Summary\".", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n- The paper is technically solid. The paper relates the target dimension to the doubling dimension $\\lambda_X$ and gives a careful analysis, which is interesting to me.\n\n- The paper gives a detailed empirical evaluation that demonstrates the power of the proposed dimensionality reduction and the effects of doubling dimension is an empirically observable phenomenon which can be quantitatively measured. \n\n- The organization of the paper is generally good and easy to follow.\n\nWeaknesses:\n\nI currently do not see any other major weakness of the paper.", "other_comments_or_suggestions": "See the next question.", "questions_for_authors": "In Table 1, the paper claims that they prove a $\\lambda$ dimension lower bound for these optimization problems. However, it seems to me they only give an $O(\\log n)$ lower bound, which corresponds to the special case ($\\lambda = \\log n$) but not for a general range of $\\lambda$?", "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": "3h19qMEf5E", "reviewer": "Reviewer_jiNf", "summary": "The paper studies several network design problems, including maximum weight matching, maximum TSP, and subgraph diversity on Euclidean doubling space. \nIn brief, the paper shows the Gaussian JL dimensionality reduction with $O(\\lambda \\log{(1/\\epsilon)} / \\epsilon^2)$ dimensions where $\\lambda$ is the doubling dimension on the Euclidean space, suffices to achieve $(1 + \\epsilon)$-approximation for these problems. The paper also develops lower bounds that show the dependence on $\\log{(1/\\epsilon)} / \\epsilon^2)$ is essential for $(\\sqrt{2} - \\epsilon)$-approximations.\n\nPreviously, similar theoretical results (e.g., reduced dimensions dependent on $\\lambda$) exist on approximate near neighbor search (Indyk & Naor 07) and clustering (Narayanan et al. 21, Jiang et al. 24).\nThough it studies several related problems, the main upper bound result of the maximum weight matching problem (Lemma 2.2), i.e., the reduced dimensions of $O(\\lambda / \\epsilon^2)$ suffices to achieve $(1 + \\epsilon)$-approximation, is the key tool to show similar results on other problems, including max TSP, max k-hyper-matching, max spanning tree, max k-coverage on Table 1.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.\n\n**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.\n\nIn 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.\n\n- [1] R. Duan and S. Petite. Linear-Time Approximation for Maximum Weight Matching. J. ACM 2014.\n- [2] G. Frahling and C. Sohler. Coresets in Dynamic Geometric Data Streams. STOC 2005.\n\n\n**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.\n\n**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.\n\n- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. ICLR 25\n- MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings NeurIPS 24\n- Sparse Dimensionality Reduction Revisited. ICML 24\n- Dynamic Metric Embedding into lp Space. ICML 24\n- Simple, Scalable and Effective Clustering via One-Dimensional Projections. NeurIPS 23\n- Fast Optimal Locally Private Mean Estimation via Random Projections. NeurIPS 23\n- Dimensionality Reduction for General KDE Mode Finding. ICML 23\n- Dimensionality reduction for Wasserstein barycenter. NeurIPS 21\n- Randomized dimensionality reduction for facility location and single-linkage clustering. ICML 21\n- Dimensionality Reduction for the Sum-of-Distances Metric. ICML 21\n\n**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. \n\n\n**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.\n\nWe 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! \n\nMany thanks,\n\nThe authors", "claims_and_evidence": "Unfortunately, I do not have expertise on these computational problems and the difficulty on showing their approximation so I could not judge the significance of the contributions of this work.\n\nHowever, I found an issue while trying to understand the proofs of Theorem 2.1.\n\nThe max match found on $G(P)$ differs from that found on $ P $ as the random projection matrix $ G $ distorts the pairwise distance within $(1 \\pm \\epsilon)$ error (say).\nHence, I do not understand how $opt(G(P)) \\geq cost(G(S))$ given that $S$ is the optimal solution in $P$ but $G(S)$ is not the optimal solution of $G(P)$ (Line 120).", "methods_and_evaluation_criteria": "The empirical results of max matching compares the quality and running time of the max matching solver on original data vs reduced dimension data. That makes sense since the contribution of the paper show that we can achieve similar results on reduced dimensional space.", "theoretical_claims": "I have not checked the proofs since I am not expertise in these problem.", "experimental_designs_or_analyses": "The empirical designs are quite straighforward and the size of data is small, $n = 1000$.\nSince max-matching solver has high complexity in $n$ (NP-hard in geometric space?), I wonder on the signifcance of the reduced dimensionality method vs. the fast approximation solutions of max-matching problem that run in $poly(n)$.", "relation_to_broader_scientific_literature": "I do not know since I am not familiar with these problems and its hardness to achieve $(1 + \\epsilon)$-approximation.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "I lean on weak reject as I am uncertain on the signifcance of the contribution. I will engage the discussion to understand the problem better and will change the decision based on other reviewers' comments.\n\n---------------\n\nI change the score to Weak Accept after reading the rebuttal messages.", "other_comments_or_suggestions": "As several theoretical results in the paper are derived from the maximum matching problem in Euclidean space, defining the max match problem and its $(1 + \\epsilon)$ approximation would give better to readers.\n\nLemma 2.4: a data set $P$ with radius $r$? $P$ covered by the ball of radius $r$.\nTheorem 3.5: $GP$ should be $G(P)$\nTheorem 4.1: $g: R^d \\mapsto R$ should be $g: R^d \\mapsto R^t$\n\nOne of the highlight contributions is showing the existence of a randomized dimensionality reduction for diversity maximization, why would this result be placed in the appendix?", "questions_for_authors": "Q1) What are the definitions of max matches and its $(1 + \\epsilon)$-approximation?", "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:

Meta-review: All three reviews of this work [74V2,6YCZ,jiNf] leaned towards acceptance with two Accept ratings and one Weak accept rating.

The reviewers appreciated several aspects of the work:
- The way of using doubling dimension to determine the target dimension for dimension reduction was considered innovative [74V2] and interesting [6YCZ]
- The advantage in computational efficiency was appreciated [74V2]
- The detailed empirical evaluation was appreciated [74V2]
- Applicability to several geometric optimization problems was appreciated [74V2]
- The paper was considered well organized and easy to follow [6YCZ]

However, several concerns were also raised:

- The lack of detailed derivation for some theoretical claims was criticized [74V2]
- Proof of one lower bound was noted to apply only to a special case [6YCZ]
- Limited experimental validation on specific (mainly image-based) datasets was criticized, leaving concerns about domain generalizability [74V2]
- One reviewer was unclear of the difficulty of showing approximations for the computational problems and hence on significance of the contributions [jiNf]
- An estimate of the doubling dimension was needed, but it was unclear how to efficiently compute it for arbitrary datasets in real applications [74V2]
- Discussion of guarantees for non-Euclidean spaces was desired [74V2]
- Limited comparison methods were criticized and benchmarking against more adaptive dimension reduction techniques like PCA was desired [74V2]; similarly, comparison to manifold learning techniques was desired [74V2]
- Additional experiments on larger/more diverse datasets were desired [74V2]
- An issue of clarity was noted for proofs of Theorem 2.1 [jiNf]
- There was concern whether the reduced-dimensional method yields significant improvement versus fast approximation solutions [jiNf]
- Better definition of the maximum matching problem and its (1+epsilon) approximation were desired [jiNf]

Authors provided rebuttals where they addressed some points, including providing discussion of the significance of their contributions (yielding a faster algorithm for weighted matchings), giving a definition of max-matching, and running a new experiment on the 20 newsgroups dataset. They also gave an argument against manifold learning methods and PCA, some discussion of the doubling dimension and whether it needs to be estimated well, and a brief sketch of a proof generalizability extension for the concern of [6YCZ] and a brief additional explanation for Theorem 2.1 for [j1Nf]. The feedback led to score improvements for [74V2,jiNf].

Overall, I find that some of the concerns identified by the reviewers above remain for the paper, particularly due to limited experimental validation. However, like the reviewers I appreciate the theoretical contributions. Thus, although the paper is a borderline case, ultimately I lean slightly towards acceptance.
Decision: Accept (poster)