This is a very interesting paper, which presents a comprehensive theoretical analysis of metric dimensionality reduction. It describe existing distortion measures in terms of moments of distortions and give an average case performance guarantee for these moments of distortion. Also, an approximate algorithm with provable guarantees on metric dimensionality reduction is introduced. The main objection on this paper was the absence of empirical evidence to support the claims. The authors have conducted additional experiments in the rebuttal phase but there are missing details regarding the experiments. The authors are advised to improve the quality of their paper in light of the reviewers' comments and incorporate their recommended changes.

Summary and Contributions: The paper studies a variant of online ranking problem. In the offline settings preferred items belong to different groups, and one need to generate a sequence of items so that qualitatively speaking for each group R_t of items at least k_t elements appear high in the list. More formally they formulate the problem as an online version of the known "Generalized Min-Sum Set Cover" (GMSSC) task: In this problem, given a set U {1,...,n} of n items, in each step 1. The learner selects a permutation \pi_t items in U 2. The adversary selects a request R_t \subset U with demand k_t . The goal is to minimize the multiplicative regret, that is the ratio of the total cost to the cost of selecting a fixed optimal permutation \pi* in all steps.

The reviewers have some concerns that the rebuttal didn't fully address but they all like the paper and agree that it should be accepted at NeurIPS.

Summary: [19] has proposed recently an efficient iterative spectral (eigendecomposition) method (ISM) for the non-convex interpretable kernel dimensionality reduction (IKDR) objective in the context of alternative clustering. It established theoretical guarantees of ISM for the Gaussian kernel. The paper extends the theoretical guarantees of ISM to a family of kernels [Definition 1]. Each kernel in the ISM family has an associated surrogate matrix \Phi and the optimal projection is formed by the most dominant eigenvectors of \Phi [Theorem 1 and 2]. They showed that any conic combination of the ISM kernels is still an ISM kernel [Proposition 1] and therefore ISM can be extend to conic combination of kernels.

This paper proposes an efficient computation of kernel dimension reduction, extending the previous work [19] to much more general class of kernels. We think this extension has an impact both in theory and practice from the general applicability of the framework.

In particular, the additional experiment on optimizing the dimensionality reduced functions for the real-world example looks quite persuasive, and the explanation about adding a dummy variable to address odd dimensional functions is also super valid. I also appreciate the authors for providing the detailed content of the modified paragraphs that they will include for the mathematical examples. The only small remaining issue is that for my point 6, the authors didn't seem to understand that the issue with Section 4.1 is that some of the sample points in the validation set may (almost) coincide with those in the training set, and the authors should make sure that they have excluded points that are sufficiently closed to the training set ones when generating the validation set, and clearly state this in the main text. That being said, I have decided to improve my score to 7 to acknowledge the sufficient improvement shown in the rebuttal. This paper considers the problem of dimensionality reduction for high dimensional function approximation with small data.

The paper proposes an interesting dimensionality reduction method for function approximation by generalizing linear level set learning methods to non linear level sets using the RevNet model structure and by introducing a loss function designed to give preference to functions that are sensitive only to few non linear coordinates. The paper is well-written and easy to understand. The methodology is clearly described and the experimental results are convincing.

Analyzing relationships between objects is a pivotal problem within data science. In this context, Dimensionality reduction (DR) techniques are employed to generate smaller and more manageable data representations. This paper proposes a new method for dimensionality reduction, based on optimal transportation theory and the Gromov-Wasserstein distance. We offer a new probabilistic view of the classical Multidimensional Scaling (MDS) algorithm and the nonlinear dimensionality reduction algorithm, Isomap (Isometric Mapping or Isometric Feature Mapping) that extends the classical MDS, in which we use the Gromov-Wasserstein distance between the probability measure of high-dimensional data, and its low-dimensional representation. Through gradient descent, our method embeds high-dimensional data into a lower-dimensional space, providing a robust and efficient solution for analyzing complex high-dimensional datasets.

Originality: The authors' solve a problem left open in a previous paper and made strictly improve on previous work for approximation algorithms. They do so by giving new insights into structural properties of extreme points of semi-definite programs and more general convex programs. As far as I understand, the algorithms presented in the paper are not substantially new, but the analysis of these algorithms is novel. Quality: The paper seems complete and the proofs appear correct. The paper tackles interesting problems and reaches satisfying conclusions. They essentially close the book on the k 2 case, make significant improvements for k 2 and leave open some questions for structured data.

Recent work of Samadi et al. introduced the fair PCA problem where the goal is to find a projection that minimizes the error and furthermore the error is balanced across two groups in the population. The takeaway message from their paper was that adding one extra dimension is enough. Firstly, this paper resolves the main open question from the work of Samadi et al. by giving an algorithm that does not need to increase the dimension by one. Second, they push the framework fo fair PCA in some interesting new directions that allow for alternative notions of fairness and multiple groups. They improve the fairness penalty to be \sqrt{k} from k-1.