Dimensionality Reduction has Quantifiable Imperfections: Two Geometric Bounds
In this paper, we investigate Dimensionality reduction (DR) maps in an information retrieval setting from a quantitative topology point of view. In particular, we show that no DR maps can achieve perfect precision and perfect recall simultaneously. Thus a continuous DR map must have imperfect precision. We further prove an upper bound on the precision of Lipschitz continuous DR maps. While precision is a natural measure in an information retrieval setting, it does not measure "how" wrong the retrieved data is. We therefore propose a new measure based on Wasserstein distance that comes with similar theoretical guarantee. A key technical step in our proofs is a particular optimization problem of the L 2 -Wasserstein distance over a constrained set of distributions. We provide a complete solution to this optimization problem, which can be of independent interest on the technical side.
Paper Summary: The authors quantify the quality of a dimensionality reduction map in terms of its precision and recall. Taking a topological point of view, they derive several interesting results such as for sufficiently low dimensional mappings, perfect precision and recall is not possible simultaneously (Thm. 1, Prop. 2). They further quantify the tradeoff showing that for maps with perfect recall, precision rate decays exponentially (as a function of the ‘gap’ between the intrinsic and the embedding dimension of the input data) (Thm. 2, 3). They further refine their quality estimate from simple precision-recall tradeoff to essentially how bad are the recall elements in terms of their (Wasserstein) distance. They provide the analogous tradeoff bound for Wasserstein distance (Thm. 4).  Review:  * I want to disclose to the authors that I have reviewed a previous version of this manuscript *  I really appreciate that the authors have significantly improved their manuscript and in my view merit a publication.   Overall I really like the paper. The authors provide a nice theoretical perspective of what to expect from (sufficiently low dimensional) mappings from an information retrieval (precision/recall-type) perspective. This has significant implications in regards to what kinds of embedding results can one expect from popular visualization techniques such as t-SNE. This paper proves that any such embedding method cannot achieve both precision and recall simultaneously and therefore in a sense the practitioner should be careful in interpreting the embedding results from such visualizations.   While I have not checked the proofs is detail (due to short review time and the appendix is 17 pages long), I do believe that the proof ideas are correct.   I have a few minor suggestions which I really hope the authors would include in the final version of their manuscript.  - As mentioned in my previous review, in the context of manifolds, analyzing the case of m < n < N (where m is the embedding dimension, n is the manifold dimension and N is the ambient dimension) feels very awkward to the reader. After all you are destroying the injectivity structure. While this difference is now discussed in Sec. 4, it would be nice to include a short discussion on merits of studying such maps in Sec. 1.1. This could be nicely motivated it by giving examples of visualization maps like t-SNE, and would overall strengthen the message of the paper.   - There are some recent theoretical results on the cluster structures that t-SNE reveals. See recent work by Arora et al. “An Analysis of the t-SNE Algorithm for Data Visualization” in COLT 2018. I believe that a map that recovers correct clusters can be viewed as the one which has a specific precision/recall tradeoff. It would be nice to place Arora’s result for t-SNE in this paper’s context. I believe including a short discussion on this in Sec 4 would make the discussion more “up-to-date”.  - One main criticism I have about the current work that the authors don’t explore or emphasize the that practical significance of their results. It would be nice to include a more detailed experiments section where they study (sufficiently) low dimensional mappings and explore some of the precision/recall tradeoffs. Having a detailed experimental section will significantly strengthen the overall message and applicability and significance of this paper.  Minor comments/typos: - [line 80] “??” needs to be fixed. - [lines 136-137] “perfection” should be “perfect” - [Eq. 1] For completeness, define Gamma function. - [line 182] probabilities q1 and q2 are basically unreadable (because of the domain of integration), consider rephrasing it more aesthetically. - [line 197] “Gamma(P_U, P_f^-1(V))” Consider using a different symbol than Gamma (as it is already used in Eq. 1). - [line 234] “we then project these 10 dimensional…”, exactly what projection map is being used? Linear? Non-linear?  - [line 282-283] while the C^infy case of Nash embedding is for a quadratic polynomial, the result in [28] is a (smooth) approximation to the C^1 Nash embedding result where the polynomial is in fact linear.   ---- I have read the authors' response.