Embedding game: dimensionality reduction as a two-person zero-sum game
Authors: Kyle Luther
Venue: NeurIPS 2022 Submitted (2022)
Keywords: manifold learning
game theory
embedding
nonlinear dimensionality reduction

Abstract: Dimensionality reduction is often formulated as a minimization containing a sparse sum of attractive interactions and a dense sum of repulsive interactions $\sum_{ij} f(\Vert \mathbf{y}_i - \mathbf{y}_j \Vert)$ between embedding vectors. This dense sum is usually subsampled to avoid computing all $N^2$ terms. In this paper we provide a novel approximation to the repulsive sum by deriving a landmark-based lower bound and then maximizing this lower bound with respect to the landmarks. After inserting this approximation into the original objective we are left with a minimax problem where the embedding vectors minimize the objective by pulling on their neighbors and running away from the landmarks while the landmarks maximize the objective by pulling on the embedding vectors and running away from other nearby landmarks. We use gradient descent ascent to find saddle points and show that our method can produce high quality visualizations without ever explicitly computing any pairwise repulsion between embedding vectors.


Embedding game: dimensionality reduction as a two player zero-sum game
Anonymous Author(s)
Affiliation Address email
Abstract
Dimensionality reduction is often formulated as minimization containing sparse sum of attractive interactions and dense sum of repulsive interactions Eij flly, Yy between embedding vectors. This dense sum is usually subsampled to avoid computing all N terms. In this paper we provide novel approximation to the repulsive sum by deriving a landmark-basee lower bound with respect to the landmarks. After inserting this approximation into the original objective we are left with a minimax problem where the embedding vectors minimize the objective by pulling on their neighbors and running away from the landmarks while the landmarks maximize the objective by pulling on the embedding vectors and running away from other nearby landmarks. We use gradient descent ascent to find saddle points and show that our method can produce high quality visualizations without ever explicitly computing any pairwise repulsion between embedding vectors.
lower bound and then maximizing this
11
13
Introduction
14
15
Dimensionality reduction algorithms can be useful in a wide variety of contexts, Reducing the dimen- sionality of vectors can reduce the computational burden on downstream tasks such recognition or neighborhood searches. Reducing the dimensionality of inputs can also be a method to filter out unwanted variability in the original inputs. In the extreme case reduction to
18
17
18
dimensions, can be used to produce visualization of the input [14]. This is the case we will be concerned with in this paper.
19
20
21
Recent algorithms have yielded very impressive looking visualizations of complicated datasets [. Common each of these algorithms is objective function containing non- linear interactions between all (or nearly all) pairs of embedding vectors. There are a variety of approximations that have been proposed to approximate these all-pairs interactions. t-distributed Stochastic Neighbor Embedding (T-SNE) has taken inspiration from physical simulation and used the Barnes-Hut algorithm to eleverly discretize embedding space manner that allows for efficient approximation of all-pairt nonlinear interactions [13]. Large Vis and UMAP both use weighted edge sampling. At each iteration (or after several iterations), random subset of interactions are chosen (with higher weighted interctions more likely to be chosen) and the subsampled objective is instead optimized 8 [2]. PYMDE uses a similar idea, but instead samples negative edges uniformly at random and these edges are fixed throughout training [1] The tractable Latent Variable Model used
13
12
23
24
25
28
27
28
29
30
31
32 landmarks to approximate the repulsion and relied on sophisticated coarse graining scheme to
33
reduce the number of pairwise interactions
[1
34 In this paper we will use a landmark approach for approximating nonlinear all-pairs interactions. We
35 will derive lower bound to a sum of all- all-pairs interactions which we then maximize with respect to
36 the landmarks. We sill show that this requires much fewer landmarks than if we simply randomly
37 sampled some fixed set of landmarks. Our algorithm can be interpreted as a two player game where
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

(a) compute nearest neighbors for high inputs
(b) learn low-dim embeddings (#) and landmarrs (*)) with gradient descent ascent
(c) forces embedding
(d) forces a landmark
force
Repulsion force
Fy = de
de
dx
Figure 1: Diagram of our method. Each embedding is attracted to the neighbors we compute in step and repelled by all landmarks. There is no direct sebeeddng-embbeddin repulsion. Landmarks are attracted to all embedding vectors and repelled from all other embedding vectors. These forces are derived in Eqs. as the gradients of the objective in Eq.
the embedding vectors minimize the objective by pulling their neighbors and running away from 39 the landmarks while the landmarks maximize the objective by pulling on the embedding vectors 40 and running away from other nearby landmarks. We use gradient descent ascent and show that our
41 method can produce high quality visualizations.
Embedding Game
42
Our starting point closely follows 1 Minimum Distortion embedding vectors (MDE). We 44 assume we have a set of high-dimensional inputs {x, and we wish to produce a corre- 45 sponding set of low-dimensional embedding vectors {y.) which reveal interesting structure
in the original imputs. To accomplish this compute sparse set of neighborhood edges:
47 N = {(i,)) j is k-nearest neighbor of i}. We define two functions: f(d) will penalize large
distances between embedding vectors and g(d) will penalize small distances between embedding
49 vectors. We wish to find embedding vectors which minimize:
min
Σ S(ly: - yyll) + Σ 1
E - y2ll)
Like many dimensionality reduction objectives, this contains sum over N2 terms. One method 51 to avoid this unwieldy sum is simply to sample edges 88, [2) We proceed in different fashion the sum Perhaps the simplest landmark-based approximation is simply to set the landmarks to be randomly chosen samples 1 = Yi, Z2 = Yigi. and approximate the all-pairs sum with N Ein g(lly; Za l] This can actually be interpreted as another method of sampling edges. However we show in the Experiments section that this idea has several problems when using a small number (< 300) of landmarks.
50
52 by defining a set of landmarks {za)/- 1L and making a landmark-
approximation
54
56
58
yll Fortunately we can make a more powerful landmark basedd approximation if g(lly; -lll) defines positive semi-definite kernel function, in other words if the N x N matrix of pairwise interactions defined by g positive semi-definite for {y:)- Some examples of g satisfying this property are g(d) exp(-epp_p dd) and g(d) = 1/(1 + d Unfortunately our bound will not work with g(d) that go to infinity as - which are sometimes used in the literature. However we'll show that we can
59
60
61
82
leam high quality embedding vectors without this "infinite as d goes zero" property.
is positive semi-definite kernel function, then for any (y.).y and Key inequality: if o(lly; -l)
84
(2, H
Σ g(ll:; - zall) 1.0
Σ 1
g(ly;
I)ll)
Σ 9(1 zu 20 a.
(2)

---

66
We are unaware of this inequality being presented in the literature but we prove it in the Appendix. The key to our proof to replace g(lly, Yy with the inner product between high dimensional vectors Φ; Φj. This is allowed because of our assumption that defines kernel function. A useful 69 property our inequality is that with at most N landmarks, there exist z which yield equality, rather than inequality. This can be seen by simply setting the 2 Y; when
67
68
N. So long as we 71 have enough landmarks, our approximation should yield the same result as the original "all-pairs"
repulsion objective. Of course we hope that approximation is useful for L < N.
73 To generate our landmark -aaseed approximation the all-pairs sum in Eq. T we divide both sides of
74 Eq. 2 by Eab Iab and then maximize E / Eab with respect to z. This yields the tightest lower
75 bound to the sum Ei o(lly yyll)- We then replace the pairwise sum in Eq. 1 with our tightest
76 lower bound to yield the minimax problem we ultimately try to solve:
En.o I(lys; Zua
Σ f(ly: yyll) + Ea, 9(11z. 2oll) i.O
min
77 The denominator in the right-hand term contains LN interactions (between all landmark-embeddiing vector pairs) and the numerator contains 1.2 interactions (hetween all
pairs).
79
2.1
Gradient descent ascent (GDA)-based optimization
x: input vectors (shape: (n,m))
# k,1: num neighbors, landmarks
# f,g: attractive, repulsive penalty functions
edges knn_ tnn_edges(x,44 # nearest neighbors for each input
y laplacian, eigenmap (edges) # init embedding vectors
z = sample_ landmarks (y,1) # init landmarks as randomly chosen embedding
vectors
for i in range (n_iter):
# pairwise distances
yy norm (y [edges [0]]] y[edges[1]] ,dim=1) (1))
shape
(n*k)
yz cdist (y, # shape: (n,1)
zz cdist (2, shape: (1,1)
energy
f .yyy)ssm() + (g( / (zz) .sm () # Eq.
# gradients
e. backwardd
# updates
y eta_y / (y.grad**2) mean sqrt() y grad
2 eta_z / (z. (z.grad**2) mean () sqrt() z. grad
Algorithm 1: PyTorch-style pseudocode for embedding game
80 We provide Py Torch-style pseudocode in Alg. [ We use rescaled gradient descent-ascent algorithm to find saddle points of Eq. This rescaling is helpful as the embedding gradients much smaller 82 than the landmark gradients and the rescaling lets us set 7/y, 7 to be similar magnitudes. In principle this rescaling could lead to convergence issues, however this not problem practice.
84 As standard practice g I1, we initialize the embedding vectors using Laplacian eigenmaps [
85 This method sets y to be the 2nd and 3rd smallest eigenvectors of the normalized graph Laplacian 86 defined by the k-nearest neighbor graph. The y are rescaled so each dimension is unit variance. In practice we don't t find exact eigenvectors but rather 100 power iterations to approximate these
88 eigenvectors. We initialize the landmarks by randomly sampling embedding vectors after laplacian initialization.

---

SCRNA
Reddit
tirkged
of
redlesign
Platelet
narrenerdi
PB
gariconn
Granulscyse
Breokingbad
Tug Logioo1102
CDO
CD4
PoloriesFore Forum
LDV Surviial
landmark
CD14
Cricket
RaRasonshhy
Figure 2: embedding vectors (color) and landmarks (black) generated by algorithm three datasets.
90
Both in theory and in practice, choosing the learning rates for GDA problems can be much more complicated than for simple gradient descent problems. the experiments section we explore how various learning rate choices impact convergence.
91
88
2.2
Force-based interpretation of the game
is useful to consider the forces each player of the game. The force each embedding takes the form:
85
f = dy: = aI Σ M4 y
dE
02 Σ Dia
y: Za
jruNe yy yill
y: z,
96
where (11, are non-negative constants. The force has two sources: each embedding feels attraction its neighbors and repulsion from all landmarks. In practice, g' will decay with distance so the repulsion is strongest from nearby landmarks. In simple terms the embedding vectors run towards their neighbors and away from the landmarks.
97
98
99
100
Because the landmarks are maximing the objective, the force is now the positive gradient. This takes the form:
+ dE
dz = Σ ia
Yi
Zn
+ 82
Σ
Za
Zb
(5)
ly:
102
where B, B2 are non-negative constants. This force also has two source. Landmarks are attracted to the embedding vectors (but prefer close embedding vectors) and repelled by other landmarks. In simple terms the landmarks run towards the closest embedding vectors and away from the other nearby landmarks.
103
104
105
Visualization results
106
107
We show visualizations produced by our algorithm on three different datasets (i) the classic MNIST dataset (ii) single cell RNA dataset (iii) 25k reddit posts from 25 different subreddits. The resulting embedding vectors and landmarks are shown in Fig, 2 The penalty functions use are:
108
X
(dd = log(1111111111111 + d
g(d)
1 d2
110 is a hyperparameter which we tune for each datasct. The "log 1-plus" attractive penalty has seen successes in previous works distances less than than a more intuitive de penalty, which may be important the presence noisy neighborhood graphs. Our "cauchy" repulsive penalty is more unusual choice. Unlike other 114 works, g does not approach infinity as the distance goes to zero. This is important as our bound does not work when g(0) oc. However, this penalty still decays zero as d oc, meaning that repulsion is strongest between nearby vectors. We show empirically that we can generate high quality visualizations with this class of distortion function.
stick with it [8 []. Intuitively this function penalizes large
112
116
118 For every dataset we adopt the same learning rate schedule. We perform 3k GDA iterations with Fly 0.03, 772 0.3. We divide both learning rates by 10 and perform 3k more iterations. There is

---

Landmark-based clustering
Cluster
Cluster [breakingbad)
been thinking ... [13ReasonsMMh) the end the show sets up sone obvious story ... (13ReasonsMhy) on opisade 2 Hannah says Nrs Antilly the school
9
9
9
9
9
9
9
9
Cluster
Cluster
[Cricket] [Cricket] [Cricket]
know has quetas and Berhardien colored year
8
8
8
8
8
8
8
g
Modern English raintaining some statistics star players seen to have
Cluster
[ExhoContact]
new to this On day 3 of anicable difficu
2
7
7
)
7
7
7
7
[HoseDepot]
Hello I wanted know anyone took these class friends for years before
[EdNoContact]
Cluster
Cluster
[LDESurvival]
After hitting 99 I n finding myself not even vent This is seriously ennoyingT went to yellow cone Finally got the chopper tank today So decided
8
8
8
a
8
8
8
8
[LDESurvivel]
[LDESurVivat]
MNIST
Reddit 25K
Figure 3: Clustering derived by assigning each embedding the nearest landmark. We show random subsets of each cluster for the first four clusters in the MNIST dataset and the Reddit25K dataset
120
no stochasticity in our system as we are doing full batch updates, however the learning rate decay still seems helpful for improving the resulting visualization.
121
3.1
Datasets
123
MNIST The classic MNIST dataset contains 70,000 grayscale images of size 28x28, each containing single handwritten digit. The generated 2D visualization is shown for K 15 neighbors, L = 50 landmarks and À = 0.001.
125
126
ScRNA The scRNA dataset contains 40,000 PCA embedding vectors of single cell mRNA transcrip- tomes from COVID-19 patients. The input vectors are 30 dimensional. This dataset originates from and can be conveniently be download from []. We use K 15, L 150 and X 0.01.
127
25K Reddit Posts This dataset contains 25,000 reddit posts from 25 different subreddits (1000 posts 129
130
per subreddit). This is generated by sampling 25 subreddits from the larger I million post dataset which can be downloaded from Kaggle [6]. To generate feature vector for each post, we use the strategy detailed in 2 and create a weighted average of GloVe vectors used in the post. These 300 dimensional "post vectors" are then fed into our algorithm. We use K 15, I. = 150 and À 0.01.
131
132
133
134
3.2
Landmark-basee clustering
135
In each case the landmarks appear to tile the high density regions of embedding space. This suggests method cluster the data. Assign each embedding the closest landmark in embedding space:
136
G3 = argmin Ily; Z.,
137
One might expect similar results by running KMeans on the embedding vectors, but a difference is that we already have the landmarks (cluster centers) result of running algorithm. In Fig. we show randomly chosen inputs that are assigned to selected landmarks for the MNIST and Reddit post datasets. This can provide interesting way quickly visualize data. Instead of directly visualizing the embedding vectors, one can examine clusters derived from the learned landmarks.
139
141
Duality and learning rates
142
Choosing the learning rates for this problem is non-trivial because we have non-convex non-concave minimax optimization. However we provide a rule of thumb which is to choose the landmark learning rate sufficiently large relative the embedding learning rate. This is motivated by experiment and extrapolation from theoretical results on conconvex-concaat optimization.
144
146
Duality In general there is duality gap for our optimization in Eq. In other words the order of the optimization (min-max vs. max-min) is extremely important for this problem. In fact the reversed imax-min" problem admits completely degenerate set of landmarks. For any fixed set of landmarks
148
5

---

0g 0.00.
1 0.03
0g 1--00 0.1
0r - 0.3
fl 1.0
learning curves
6
By
1000
2000
Figure 4: Varying the landmark learning rate 7/ with the embedding learning rate fixed ?/y 0.03
(for the MNIST dataset). Too small, and the embedding vectors collapse to few points (7) = 0.01). Too large and the embedding vectors again appear to begin collapse, although not extreme here. There appears to be a window of learning rates where we observe nice clustering.
150
(z), the embedding vectors (y) can achieve O error by: one, setting the first sum Eq. to zero by collapsing to point y; = y; for all i, and two: setting the numerator of the second term in Eq. 3 to zero by running off to infinity. So for any fixed z, we have miny e(, 2) = and therefore max, miny 0. Ultimately we care about generating useful visualizations of data, so having all our embedding vectors collapsed at single point, infinitely far away from the landmarks, is not good.
152
154
155
I Leanning rates Intuitively we should set the landmark learning rate to be relatively fast compared to the embedding learning rate. This way, the landmarks can approximately perform max, cly, before the embedding vectors have chance to update appreciably. Then the embedding vectors can perform approximate gradient descent on the objective max; e(., z) and the algorithm is more likely to find solutions to the original min max problem.
156
157
158
160
Rigorously justifying this intuition, that setting "y < 1/2 will find a solution of min, max,, is rather challenging in the case of conconvex-nonconee nonconvex concave problem, this intuition (choose a fast learning rate for the inside- ) can be rigorously shown to be correct 77.. We'll show via experiment that this intuition seems to be useful.
161
objective like ours, In the simpler case of a
162
163
164
165
Experiment We run our algorithm on the MNIST dataset with = 15, = 100, and À = 0.001.
We'll fix 'y 0.03 and vary 72- Learning curves and visualizations after 2k iterations of Alg. T are shown in Fig. 4 Too small, and the embedding vectors collapse to a few points (72 = 0.01). Too large and the embedding vectors again appear begin to collapse, although not as extreme here.
187
168
169
There appears to be a window of learning rates where we observe nice clustering. This seems to be explained by our intuitions on the duality problem.
170
171
When 7/ is too small, the embedding vectors can begin to minimize first and perform miny e(-, z). which we argued can be 0 when the embedding vectors collapse to a point and move away from the landmarks. When 7)= is too large, then again the landmarks are not performing the inner loop maximization, and the embedding vectors again can perform min, e(,, 2). by collapsing to point. In Fig. | we see the embedding vectors begin to collapse, although its not as extreme as when 7)2 was large.
172
179
175
178
5
Comparison with sample-based techniques
177
178
We'll 'Il compare to two Exed-sample-berd based methods for approximating the all-pairs sum in Eq. [ The first method is used by (I] and simply samples L edges for each node. The second method randomly designates embedding vectors at the start of training to be the landmarks and replaces the sum using the landmarks. This method is not widely used in practice, and as we'll see it leads to surprisingly low quality visualizations. We call these methods "fixed-sample" because these edges/landmarks are sampled once at the start of training and then fixed for all subsequent iterations.
180
182
189
184 We evaluate each method a) qualitatively by looking at the resulting visualizations and b) quantitatively
by comparing the value of the "all-pairs" objective (Eq. [ using the generated embedding vectors. We observe that the mampled-edge-baseee algorithm seems to outperform our algorithm for fixed T., while the sample- landmark based algorithm dramatically underperforms.
186

---

188 Sampled edges At the start of training, we sample L edges (i.j) uniformly at random for each node
189 We call this set of edges N The pll-p sum Eij is then replaced with a sum over these edges
190 and reweighted by a factor N/L. So we optimize the objective:
N
min Σ S
f(ly;- vyll++++
Σ レンート
g(ly;: yyll))
L
191 Sampled landmarks At the start of training, we designate I. embedding vectors uniformly at random
192 to be landmarks. We call this set of embedding vectors E. We again replace the all all-pairs sum in Eq.
193
with reweighted sum over landmarks:
min Y
Σ ij
N I
TE E
Alyy: yyll)
(9)
By defining the set of negative edges W ((i,) : i 2,., N and j E 8}, we can rewrite Eq. 9 to look identical to Eq. 8 In other words the sampled landmark scheme be interpreted just
194
195
196
another method to sample negative edges.
Averaging over edge or landmark choices, both schemes yield unbiased estimators ( Nig-o
197
Σ ij But because these are chosen once at the start of training and then fixed, these actually yield zero variance but biased estimates. In other words both methods generates biased estimate of Ex; and its gradients. If our method exactly computed the global maxima with respect to the landmarks for a fixed set of embedding vectors, it could as well be regarded as a zero- variance biased estimate of the all-pairs sum. However, it does not find the global maxima, there is some variance in our estimates (due to for instance random initialization of the landmarks).
199
201
202
203
Experiment training details In all three experiments (sampled edges, sampled landmarks, and our method) we use the same hyperparameters. We train on the MNIST dataset. We use the f. described in Eq. 6 We set À 0.001. We use K 15 for the neighborhood graph. We compare
205
207 I. E (1.3, 3, 10, 30, T00, 300]. For the sampled edges and sampled landmarks experiment, we only have learning rate for the embedding vectors. We the same learning rate schedule for Jy in
209
both settings: we perform 2k iterations with f7 = 0.03, then 2k more with fy = 0.003. For the experiment using our method, we have the additional parameter 7)s and set at 7/s 107y.
210
5.1
Visualization (qualitative comparison)
The resulting visualizations are shown in Fig. S As the number of landmarks L increase beyond 30, both the optimized-landmark and sampled-edge algorithms yield nearly identical visualizations. This seems reasonable, as L increases each algorithm yiclds better and better estimate of the 215 all- pairs objective so beyond a certain threshold of L, all algorithms should ultimately yield the same visualizations. For L = 1, 10, 30 the optimized landmark algorithm suffers from degeneracies not seen in the sampled-edge algorithm. In particular we observe a number of "clusters" appear to collapse to single points.
213
217
219 Intuitively when there are more clusters than landmarks, there is no mechanism for the optimized landmark algorithm to prevent some of the clusters from collapsing. In the landmark algorithms there is no direct enbedding-embedeee of embedding vectors which are attracting each other, there is no outward repulsion preventing this cluster from collapsing to a point as we see in the cases L = 1,3, 10 where there are not very many landmarks. The sampled-edge method seems to provide a more robust mechanism for avoiding this embedding collapse.
221
repulsive forces. If there is no landmark inside a cluster
223
225
226
The
algorithm gave nearly complete embedding collapse for all L we tested note that at some point, for sufficiently large all three methods should yield the same result). All embedding vectors which were not designated as landmarks simply collapsed towards a single point
227
228
229
while the landmark vectors were repelled to an exterior ring around the origin. may seem surprising how different this result is from the sampled edges experiment, given that it can be interpreted as another way to generate negative edges. This result shows the importance of the exact method used
231
to approximate the all- all-pairs repulsive sum.
7

---

optimbeed landmarks
sammlled edges
sampled landmarks
68 997 cmbosdinng vectors
ambaskking
landmark
Figure 5: Comparing our optimized landmark method for approximating the all all-pairs repulsion in Eq. to simple edge-sampling and sampling methods. Black dots indicated landmarks (not relevant/present
sampled edges figures). The edge sampling method seems to outperform method for fixed I.. When don't have enough landmarks (I.=1,3110) embedding collapse to points. However our method much better than a simple random sampling of landmarks. When we randomly sample and fix landmarks, nearly all the embedding vectors which were not designated as landmarks collapse to single point, while the landmark vectors repel from each other and other embedding vectors.
clusters of
5.2 Quantitative Results
234 We also compare the sampled-edge and the optimized-landmart algorithms quantitatively in Fig. 6 We don't show the sampled-landman method is far worse than the sampled-edge optimized landmark methods. All curves in this Figure are for L = 10.
In (a) show the energy are actually optimizing (Eq. 3 for segimized-landmaate and Eq. 8 for sampled-edges). This indicates that both algorithms are at least optimizing the approximations, and the degeneracies observed in Fig. a not failure of the optimization routine. In (b) we show an unbiased approximation to the "true" energy at each iteration (Eq. T. This is done by randomly sampling a large number of edges from the all pairs sum, and these edges chosen i.i.d. at each iteration
238
240
242
For both orange and blue, the energy we optimize is less than the all-pairs energy, and this difference can be regarded as analogous to a gencralization gap. Each algorithm "overfits" to the energy we optimize, but this "overfitting" appears worse for method than the sampled edge method.
244
246
We observe that the sampled-edge algorithms yields lower all-pairs energy (the energy we truly wish to optimize). This is in agreement with the fact that the sampled edge method yields the highest quality visualizations with small number of sampled edges (Fig. (5) In (c) we plot the root-mean- squared error between the gradients of the approximate energy and gradients of the estimated true
248
250
energy. Our method produces a more faithful gradient estimate nearly all times in training. This
extremely surprising as the final true energy, after many gradient updates is lower for the sampled
252
edge method which gives a worse gradient estimate in terms mean squared error. This result shows how the exact details used to approximate the can be very important.

---

Coptimized
Calipairs
gradient error
15
15
embedding game
RMSIgalipair -gestimatel
sampled edges
10
10
energy
energy
5
2
0
2000 iter
4000
0
2000
4000
2000 iter
4000
iter
Figure 6: Quantitative comparison between our method (optimized landmarks) and sampled edge method. The left figure show the energy each method actually optimizes. The middle figure shows the "all-pairs" energy (Eq. 1).
Related Work
254
255
Landmark methods Instead of dealing with 22 nonlinear pairwise interactions, landmark based approaches instead designate small set of n landmarks, and instead work a smaller set with n.V iterations. Unlike our method where individual landmarks do not correspond to any particular sample, most landmark approaches use sampling designate certain samples as landmarks. For dimensionality reduction, landmark approaches have been applied ISOMAP by [ and to stochastic neighoor embedding vectors by [10]. Finally more sophisticated landmark sampling schemes have been used by [II].
258
257
258
259
260
Perhaps the most well-known class of landmark methods is the Nyström method [16], which is used to approximate N x N kernel similarity matrices g(x,, x,) with two smaller N x and n x n matrices. Our method actually can be understood from the kernel perspective. The heart of our method is approximating the sum over all pairs of interactions Eij ( xj) which we can interpret the inner product of the vector of all ones and the kernel similarity matrix 1 GGL.
263
264
285
286
267
Game formulations of learning This work falls into a category of works formulating well-established algorithms like multidimensional scaling, principle components analysis, and whitening as game This work is formulating a certain class of nonlinear embedding problems as game.
269
Discussion
270
271
This paper presents a novel method for approximately the all-pairs repulsive term present in many manifold learning algorithms. When the nonlinear repulsion terms are described by kernel function, we can derive lower bound for the all-pairs sum which we then maximize to find the tightest lower bound. We show that this optimization requires much fewer landmarks than would be required we instead just randomly designated embedding vectors to be landmarks. However, compared to sampling edges randomly this scheme still requires more computation to achieve comparable visualizations.
273
275
277
To make this method more useful, future work should find automated schemes for performing the minimax optimization, so a user does not have to specify learning rates. This might me much more challenging here than for a minimization problem because in general there is no guarantee that an increase or decrease in the objective means we are getting closer to a saddle point. In practice however, we observed success by setting larger learning rates for π) and smaller for Bl. This might suggest that finding a quick and robust inner loop maximization, with outer loop gradient steps could be a promising direction.
279
281
283
285
would interesting to apply our method to other regimes. In particular finding high dimensional embedding vectors. Additionally, exploring the behavior of this method in the online setting is promising, as our method for approximating a sum of all-pairs pairwise interactions does not actually require any pairwise distances between embedding vectors to be computed.
287

---

References
289
290
[1] Akshay Agrawal, Alnur Ali, and Stephen P. Boyd. diniiuum-distoiionn embedding. CoRR, abs/2103.02559, 2021.
[2] Sanjeev Arora, Yingyu Liang, and Tengyu Ma. A simple but Nough-to-beat baseline for sentence embeddings. In International conference on learming representations, 2017.
293
294
[3] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373 1396, 2003.
[4] Vin De Silva and Joshua B Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. In NIPS, volume 15, pages 705-712, 2002.
297
298
[5] Ian Gemp, Brian McWilliams, Claire Vernade, and Thore Graepel. Figengame: Pea as a nash equilibrium. arXiv preprint arXiv:2010.00554, 2020. 2020.
300
[6] Mike
Swarbrick https//www.kaggett www.gggeww.oo/aaaaaccccossnnenee
Jones.
Reddit
self
posts
dataset.
301
302
77] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
303
304
305
[8] Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction, 2020.
308
307
[9] Cengiz Pehlevan, Anirvan M Sengupta, and Dmitri Chklovskii. Why do similarity matching objectives lead to hebbian/anti beabian/ant-hhebbaan networks? Neural computation, 30(1):84-124 2017.
308
309
[10] Nicola Pezzotti, Thomas Höllt, B Lelieveldt, Elmar Eisemann, and Anna Vilanova. Hierarchical stochastic neighbor embedding. In Computer Graphics Forum, volume 35, pages 21-30. Wiley Online Library, 2016.
310
312
Lawrence K. Saul. A tractable latent variable model for nonlinear dimensionality reduction. Proceedings of the National Academy of Sciences, 1 117727)155033-5500 2020.
313
314
[12] Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high- dimensional data. Republic and Canton of Geneva, CHE, 2016. International World Wide Web Conferences Steering Committee.
315
316
317
[13] Laurens van der Maaten, Accelerating t-sne using tree-based algorithms. Journal of Machine Learning Research, 15(93):3211-3244 2014.
[14] Laurens Van Der Maaten, Eric Postma, Jaap Van den Herik, et al. Dimensionality reduction: comparative. J Mach Learn Res, 10(66-71):13, 2009.
320
321 [15] Aaron Wilk, Arjun Rustagi, Nancy Q Zhao, Jonasel Roque. Giovanny J Martínez-Colóón Julia L McKechnie, Geoffrey T Ivison, Thanmayi Ranganath, Rosemary Vergara, Taylor Hollis, et al. A single-cell atlas of the peripheral immune response patients with severe covid-19 19, Nature medicine, 2677):1070-1011 2020.
323
[16] Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2001.
326
Checklist
328
1. For all authors...
330
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We provide a game theoretic objective in Eq. 3 and show visualizations in Figure 2
331
332
(b) Did you describe the limitations of your work? [Yes] See discussion
10

---

334
(c) Did you discuss any potential negative societal impacts of your work? [No]
335
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
336
2. If you are including theoretical results...
338
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state the assumptions in section 2
339
(b) Did you include complete proofs of all theoretical results? [Yes]] In the appendix, prove our main theoretical result, that we can bound the sum of pairwise interactions
341
342
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [No] We provide Py style pseudo-code in the main text to run our algorithm.
344
345
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] In section and we provide these details
347
348
(c) Did you report error bars (e-g.. with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] These are small scale experiments,
351
taking no more than minute on a single GPU to complete
353
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
354
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite mnist, scRNA, and Reddit posts dataset
355
356
(b) Did you mention the license of the assets? [No]
357
(c) Did you include any new assets either in the supplemental material or as URL? [No]
358
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [No] We are using publicly available datasets
359
380
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] We are using publicly available datasets
381
362
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
364
365
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
388
Proof of Inequality in Eq. 2
389
370
We restate the claim first. If g(lly; yyll) is positive semi-definite kernel function, then for any (v. 1 and {z Pazi
371
Σ a(lly: lall) 1.0
S
Σ O0yy: ysll)
Eg(1 z. - 20 a.b
(10)
372 Proof: Because we have assumed that is a kernel, Mercer's 's theorem allows us to replace all the g()
373 with inner products between high dimensional vectors. Specifically for any {y:) ) and (zm)am)
there exist {Ø, ) and
(+/ Y such that
o(ly: z.ll) Φ. vb. g(ly,, y,ll) Φ. Φ
o(12z - 1 = $. 3b (11)
375
Now proof of Eq. TT is simple matter of proving vector inequalities. First we define the sums
376 Φ = Σ, Φ. and xb Ea Va. We can replace the sums of g with our vectors. So the left hand side
377 is
Σ 9(1l:: 2all) = (5. 15 (6, 252
(12)
ia
11

---

378
And the right hand side of Eq. 10
Σ Colly- - x,|l)
Σ
Ellza 2011) = 1|
(13)
0.b
Because Cos < 1, the left hand side is always less than the ride hand side so we have therefore 380 proved Eq. 10
12


Reviews:
[{"review_id": "gM4t2cAyHu", "reviewer": "Reviewer_aU48", "summary": "- This paper presents a new approximation approach for dimensionality reduction formulation.\n- Traditional dimensionality reduction is formulated as minimization of sum of attractive interaction and sum of repulsive interaction between embedding vectors. The proposed approach approximates the repulsive sum with maximizing the landmark-based lower bound w.r.t. landmarks to make it a minimax problem\n- The proposed approach is optimized by a gradient descent ascent approach. And the selection of the hyperparameters are discussed. Experimental results showed the proposed approximation gives high quality clustering.", "questions": "- Do you have any mathematical analysis of the learning rate selection besides the experiments?\n- Besides fixed iteration, maybe use energy difference as the termination condition of the loop?\n- For Figure 6, energy of sampled edges are almost identical for e_optimized and e_allpairs which indicates sampled_edges has a better approximation than embedding_game. Why do you need RMS(gradients) other than RMS(energy) to tell the approximation quality?", "limitations": "Authors did mentioned the limitations and looking forward to seeing the approach to be applied to dimensionality increase problem.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n- Clever formulation of the approximation in section 2\n- Clear interpretation of the math formulation, i.e. the embedding vectors run towards their neighbors and away from the landmarks....\n- Clear visualization to show the clustering quality\n\n# Weakness\n- Quantitative results are not impressive, proposed method performs worse than sampled-edge algorithms when sampling size is the same. the proposed approach needs more computation to achieve comparable results.\n- The discussion of the learning rate selection is not sufficient, neither with a mathematical analysis nor a more comprehensive combination (current work fix \\eta_y, any other options?)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F5NqhWJMqsb", "reviewer": "Reviewer_bFeS", "summary": "The paper addresses the problem of dimension reduction for visualization. It proposes a minimax objective for this problem with game theoretical interpretation. It also proposes a gradient descent-ascent (GDA)-like algorithm to solve this objective that uses non-randomly selected landmarks. They provide empirical results from running their method on the MNIST, scRNA and 25K Reddit Posts datasets.", "questions": "Questions on the objective/ formulation.\n - Equation 3 is obtained by dividing Equation 2 by $\\sum_{a,b}$, maximizing over $z$ and then plugging the inequality back into Equation 1. But this means that Equation 3 is a lower bound for Equation 1. Does it make sense then to minimize Equation 3 as a proxy for minimizing Equation 1?\n - The section on Duality (lines 147 to 154) is confusing in light of Equation 3. The paper says that there is duality gap in the optimization problem in Equation 3 that means that the ordering of optimization matters. From the von Neumann minimax theory, does this suggest that Equation 3 is not a two-player zero-sum game as stated?\n\nQuestions on Algorithm 1.\n - Line 143 says that the optimization problem is nonconvex-nonconcave. Therefore, is it suitable to use GDA as a basis for Algorithm 1 when GDA is known to converge to limit cycles or diverge in this setting? The paper cites Lin et al. (2019) On Gradient Descent Ascent (GDA) for Nonconvex-Concave Minimax Problems which points specifically to this issue. They also mention that it is difficult to set the learning rate so that the algorithm finds a solution. Given these issues, are there other algorithms that could be used instead of GDA?\n - Given the importance of setting the learning rate(s) for Algorithm 1, it could be useful to have this issue addressed in more detail. Lines 118-121 conclude that decreasing the learning rate improves the resulting visualization. It is generally the case, however, that using a smaller stepsize improves accuracy while increasing the iteration complexity of a method. Could the authors provide details such as maximum stepsize allowed for Algorithm 1 not to diverge? In Section 4, it is also unclear what is meant by setting \"the landmark learning rate to be relatively fast compared to the embedding learning rate\". Could the authors provide details on the relative size of the two learning rates?\n - The paper could be strengthened with more details on the efficiency of the method. For example, could the authors provide theoretical analysis to show the rate of convergence of their algorithm (i.e. a bound on n\\_iter in Algorithm 1)? In terms of empirical results, there could be more clarity given too. For example, it is unclear where the plots in Figure 6 came from (e.g. which dataset(s), the learning rate used, etc). Could this be clarified? Could the authors provide similar plots as in Figure 6 but with clock time taken in the x-axes? This is especially useful as the paper argues that one advantage of Algorithm 1 over KMeans is that it provides the landmarks as part of the process. Yet, like running KMeans, there is a cost associated with finding these non-random landmarks too.\n\nIs the code used for the experiments available publicly?", "limitations": "This work does not appear to me to have negative social impact.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n - The paper addresses an important topic: dimension reduction for visualization.\n - The paper is clearly written with only minor notation issues.\n - The approach of combining optimization and game theory is interesting.\nWeaknesses\n - Some questions remain on the validity of the proposed formulation of the problem and objective (Equations 3 and $E$ in equations 4 and 5).\n - More details needed for their proposed method (Algorithm 1).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A_rRVSEhDF", "reviewer": "Reviewer_a79m", "summary": "This paper proposes a min-max optimization-based dimension reduction technique that approximates the sum O(N^2) using fewer landmarks. They derived a landmark-based lower bound for the repulsion term and then tried to maximize that to approximate the objective. They showed that their optimization requires much fewer landmarks than taking randomly designated points as landmarks. ", "questions": "1. Could you explicitly elaborate in your paper on why the landmark-based approach should be taken?\n2. Have done any exploration on improving the min-max optimization technique for this setup?\n3. There is no mention of sample complexity. Do you have any suggestions on what size of L to use based on other factors like, the number of data points, initial dimension size, etc? If yes, please mention them in the paper.\n", "limitations": "Same as the weakness points.", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weakness:\n1. The authors have some strong assumptions for their derivations, whereas they did not explicitly mention when would their method fail.\n2. There was no analysis of time complexity for their algorithm.\n3. Their empirical evaluation, in many cases suggests that sampled edges are better. More empirical evaluation is required.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject