Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The work shows a scenario that the classical MDS algorithm fails. "When the derived matrix has a significant number of negative eigenvalues," the classical MDS algorithm tends to fail when the number of dimensions increases sufficiently large. Then the work designs an algorithm with improved performance bound and shows the potential on practical applications.
main_review: Pros:

1. The writing is good and gives clear explanations and detailed background for derivations, which are beneficial for both experienced and non-experienced readers.

2. The analysis results seems reasonable to me.

3. The resulting algorithm applies the Dykstra's method to iteratively projection onto the space of hollow matrices and achieve a fast solution procedure.

Concerns:

1. In MDS, typically people use a small number of dimensions for embedding. So the scenario of failures described in the paper seems rare, which may limit the practical significance of the results in the work.

2. In literature, there are known issues on the classical MDS. For example from https://en.wikipedia.org/wiki/Isomap, "following the connection between the classical scaling and PCA, metric MDS can be interpreted as kernel PCA." ... "However, the kernel matrix K is not always Positive Semi-Definite. The main idea for kernel Isomap is to make this K as a Mercer kernel matrix (that is positive semidefinite) using a constant-shifting method, in order to relate it to kernel PCA such that the generalization property naturally emerges." Is there any relationship between the paper's finding and this known issue of non-PSDness? How to compare the proposed algorithm and the kernel PCA algorithm? It is preferred to see some discussion on this point in the rebuttal phase.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: A new decomposition of the classical multidimensional scaling (cMDS) error term is generated and used to get additional insights of the method. 
As I first came across the draft, I naively thought; “Well, cMDS is extremely well known, how can one innovate on such topic?”. Moreover, the departing justification stating cMDS does not excel in non-linear mappings wasn’t that great; I mean cMDS ASSUMES Euclidean space and linearity so it was no wonder that used out of its natural scope it may be suboptimal. But I am very glad to say that the authors proved my naivety wrong very quickly! There is a very clear contribution, the paper is strongly supported, and reading enjoyable.

STRENGTHS
+ The unusual “late comer”. Innovating in a method which is so well known is difficult.

WEAKNESSES
+ There are some unclear decisions and justifications but it is somewhat contradictory that I’m criticizing this when, I in the place of the authors, I would very likely have proceed equally… Notwithstanding, I’m indicating this below, in case a second thought can be given
+ There is an unconventional mixture of theoretical claims with experimental testing whereby some “theoretical proofs” are complemented with heuristics verified experimentally, but actually not theoretically proven.

main_review: + ln 68-71: These advantages are a bit simplistic (and yet I would claim them equally!). The 3rd one is particularly weak; the error term guides the optimization but it does NOT measure the quality of the solution. The same error value can represent wildly different solutions. A better measure of quality of the embedding is the pairing between embedded vs real distances (analogous to a QQ-plot). And of course, this is not the only one, there are other measures of the quality of a solution e.g. topological stability, etc. 
+ ln 99-101: Ok but this seems a bit circumstantial. Can we guarantee that such relation holds for other tasks? Again, the quality of the embedding cannot be measure from the error.
+ Perhaps I’m wrong on this but in Definition 1, I think a limit to d is missing, otherwise as long as d=n+1 there will always be a valid solution as one can form the n simplex, and hence every matrix D will eventually be EDM.
+ ln 216-217: Sorry but this is NOT an analysis of complexity. You are very likely right, but unless you prove it formally or at least empricially, I would suggest to remove claims about running times.
+ “unconventional mixtures of theoretical claims with experimental testing”;
  * ln 228: I am unused to accept an heuristic as a part of a theoretical proof, unless the heuristic is itself theoretically proven (at which point, of course it ends being an heuristic).
  * ln 239: Well, something that is formally proven doesn’t need any additional experimentation, does it?
+ There is almost no discussion.
+ There is no conclusions section.

+ It is becoming more and more common to move the proofs to supplementary material, and the authors adhere to this practice. I disclose here that I very much dislike this practice, specially when the proofs are central to the research, and not a complement. Moreover, here the appendix are 7pgs!! If you truly needed 13+7=20pgs to communicate your research then perhaps a conference was not the right target for this research. But having said that, it is of course ultimately the authors decision, and I’m just being a grumpy old man! Please ignore my outburst, and proceed as you please.
+ I have been unable to inspect the code in detail as it seems to be in Julia (JLD) which is a language I do not master. Sorry.

limitations_and_societal_impact: Not included, but limitations of cMDS are well known and I do not think any evaluation of the societal impact is needed for this research.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the problem of multidimensional scaling (MDS) for embedding data into Euclidean space and perform a theoretical error analysis of the classical muldimensional scaling (cMDS) algorithm. Their main result decomposes the error of cMDS into 3 components, which they use to explain the behaviour and degradation of the cMDS error with respect to the embedding dimension. Then, they propose an algorithm, based on their theoretical findings, and show that it outperforms cMDS on standard image classification datasets.
main_review: ## Originality

The authors mention in the abstract that a theoretical analysis for cMDS on non-Euclidean metrics is lacking. Can the authors mention the error analysis on Euclidean metrics and detail how their approach differs from the literature, as well as the difference between their algorithm and the ones mentioned in l.84.

## Quality

Section 3 would benefit from a toy example where the 3 components of the errors are plotted with respect to the embedding dimension to validate the authors interpretation and the different weights between C1-C3. Maybe refer to Fig. 1 and use it to illustrate the discussion.

l. 102: The authors claim that they provide an "efficiently computable algorithm" but I do not see any argument in the paper supporting this claim such as a complexity analysis, comparison with other approaches, or benchmarks of computational time. l.216-217 mention that the major computational step is a spectral decomposition, is it affordable in large dimensions ? What are the complexity for the type of matrices considered (is it sparse, dense, structured matrices) ?

l. 231: The authors mention that solving eq. (3) is much more computationally intensive than their approach, can they explain the reasons as well as an order of magnitude for the difference (i.e. is it 10, 100 times more expensive) ? Similarly, they mention another approach by Qi and Yuan but do not do any comparison with them.

Figure 1: Why is the squared error so large ? Should it also not be normalized by ||D||_F^2 ?

l.84, the authors refer to several papers which aim to address the robustness with respect to noisy data but do not compare their approach with the literature in the experiments of section 4.

In the classification paragraph in section 4, why are the authors using a simple 3 layer feed-forward neural network ? Image classification taks are traditionally done using a convolutional neural network.

## Clarity

The paper is not very well written as it lacks clarity in several places, mostly in section 4.

What is the motivation for using the characterization by Hayden and Wells ?

I do not think that the presentation of Lemma 1-5 in the main text really supports the discussion. When describing the idea of the proof of Thm. 1, the authors could say that each of the three terms are identified to C1, C2^2 and C3, and point to the Supplementary Material.
On the contrary, the interpretation of these terms is central and would deserve a paragraph title for each to be clearly identified.

In Section 4, the discussion around Figures 1 and 2 is very confusing: the captions do not contain enough informations to understand the figures alone (they should at least define the terms in the legend). The organization of the figures is also confusing and it may be preferable to either discuss the decomposition of the error earlier in section 3 or organize the figures according to the datasets (e.g. for the Portugal one, having one panel for the decomposition and a second for the algorithm performance).
In Figure 2: the contribution would be clearer is the authors clearly identify their algorithm in the legend of Fig. 2. I do not understand as well what is the "Lower" curve and why the associated error is below the true solution.

The classification paragraph in section 4, the associated supplementary material, and the caption of Figure 3 lack informations to really understand and reproduce the experiment of the authors.

Minor comments:
- l. 120 "if and only if"
- l. 121: Please define the space in which $\mathbf{1}$ and $s$ live.
- Definition 2: I found it confusing that the notations do not exactly match the one given in eq. (5).
- l.161: Recall that $S\circ S$ denotes the Hadamard product
- l.174: "we can see that C1"
- l. 233: "Here we use"

## Significance

The error analysis of the authors explains the behaviour of the cMDS error, which is validated experimentally in Fig. 1. In Section 4, the authors show that their new algorithm outperform cMDS and does not degrade with respect to the embedding dimension.
limitations_and_societal_impact: The paper would benefit from a conclusion section summarizing the main contribution of the authors and discussing the strengths and limitations of the study.

The authors could also discuss potentially negative societal impacts if the method is applied for discriminative purposes on image datasets.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the classic embedding method known as multidimensional scaling and focus on the so called STRAIN  and SSTRESS objectives, both designed for embedding a given squared distance matrix into a lower dimensional space, often for visualization, but potentially also for reducing problem size for downstream tasks. 

The idea is that the SSTRESS is the better objective to optimize as it captures how well the distances of the embedded data points approximate the input distances, but computationally hard, so maybe it is enough to just use the solution for the simpler STRAIN objective, that boils down to Singular Value Decomposition and that may work fine.

The paper analyzes the solution of STRAIN in terms of the more relevant SSTRESS objective, and shows a decomposition of the error of the STRAIN solution as measured with the STRESS objective and analyzes this objective to understand what happens.
The punchline is that if the input distance matrix is not Euclidian (no data set with these pairwise distances exist in any dimension), then the SSTRESS error of the embedding achieved by optimizing STRAIN can  actually increase with increased embedding dimension. A property that seems counterintuitive as a higher dimension should allow improved embeddings. The paper shows  experimentally that this phenomena actually occurs in practice as well and that the performance is nicely explained by the error decomposition proved and discussed in the paper.
In particular the experiments show that the classic Isomap embedding has this issue. 
Furthermore, if these STRAIN embeddings are used for a simple downstream task like standard classification, the results become increasingly worse as the embedding size is increased.

main_review: While the STRAIN objective may make most sense for Euclidian inputs and the failure is analyzed for non-euclidian, the experiments also show that just adding noise to the input distances may greatly worsen the results of using STRAIN based embeddings.  Based on the error decomposition the authors propose a way to fix the problem with the STRAIN objective, while maining the computational efficiency of the STRAIN method.
The fix improves the embedded distances, and improves the results for downstream tasks as the performance decrease significantly less, but it still seems there may better methods if a downstream classification task is the goal, and for me the experiments with the downstream task is more a proof of the failure of the STRAIN method to produce useful embeddings than that the new method is good solution for the dimensionality reduction problem. 

In short, the paper shows that using STRAIN embeddings based for instance on IsoMap or other non-euclidean metrics to make a (semi) low dimensional embedding for instance for  downstream tasks is not good idea and should discourage practitioners from doing so, at least without proper thought. The error decomposition is computable and can be used to gauge into the potential issues with applying the STRESS optimization. 


Technically the theoretical results seem sound and interesting and the analysis and result very relevant.
I think the same is true for the experiments shown in the paper. 

A few things that may be improved/changed
- For the plots the y-axis is different in every plot which makes the pattern look identical on many experiments which cheated the viewer (me)  before I noticed. 
- The claims of roughly constant of C3, C4, ... may be a slight exaggeration but the experiments shown they are clearly lower order so that may be okay. Actually C1 seems just as constant in the experiments. 
- For very low dimensional embeddings it seems interesting things are happening and here it seems that STRAIN may still be useful at least on the data sets considered. Maybe a few comments on why that may be would be helpfull from a geometric or eigenvalue spectra kind of perspective. 


Overall I think this line of research that explains the performance of well known algorithms is relevant and important. 

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This seems to be a strong theoretical contribution to NeurIPS, although both some of the reviewers and myself suspect it is less relevant for practical usage.
Decision: Accept (Poster)