Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths
 - The paper addresses an important topic: dimension reduction for visualization.
 - The paper is clearly written with only minor notation issues.
 - The approach of combining optimization and game theory is interesting.
Weaknesses
 - Some questions remain on the validity of the proposed formulation of the problem and objective (Equations 3 and $E$ in equations 4 and 5).
 - More details needed for their proposed method (Algorithm 1).
questions: Questions on the objective/ formulation.
 - 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?
 - 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?

Questions on Algorithm 1.
 - 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?
 - 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?
 - 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.

Is the code used for the experiments available publicly?
limitations: This work does not appear to me to have negative social impact.
review_title: null

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Weakness:
1. The authors have some strong assumptions for their derivations, whereas they did not explicitly mention when would their method fail.
2. There was no analysis of time complexity for their algorithm.
3. Their empirical evaluation, in many cases suggests that sampled edges are better. More empirical evaluation is required.
questions: 1. Could you explicitly elaborate in your paper on why the landmark-based approach should be taken?
2. Have done any exploration on improving the min-max optimization technique for this setup?
3. 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.

limitations: Same as the weakness points.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: - This paper presents a new approximation approach for dimensionality reduction formulation.
- 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
- 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.
strengths_and_weaknesses: # Strengths 
- Clever formulation of the approximation in section 2
- Clear interpretation of the math formulation, i.e. the embedding vectors run towards their neighbors and away from the landmarks....
- Clear visualization to show the clustering quality

# Weakness
- 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.
- 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?)

questions: - Do you have any mathematical analysis of the learning rate selection besides the experiments?
- Besides fixed iteration, maybe use energy difference as the termination condition of the loop?
- 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.
review_title: null

Meta-review: metareview: While the reviewers agreed that the paper addresses an important topic, and combining optimization with game theory is interesting, the reviewers had a number of concerns regarding the validity of the proposed formulation of the problem, lack of theoretical justification for using GDA, strong assumptions, lack of complexity analysis, and limited empirical evaluations. Unfortunately, those concerns were not fully addressed by the author response.
confidence: Certain
Decision: Reject