Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focuses on an interesting and important problem in machine learning: For a given set of data around a low-dimensional manifold embedded in a high-dimensional R^D, how can we estimate the intrinsic dimension (ID) of the manifold. The traditional estimator based on the nearest neighbor statistics cannot be applied to large datasets due to the complexity and suffers from the curse of dimension. In this paper, a normalizing flow (NF) based method is proposed, which solves the problem by using the following steps: 1) Add Gaussian noise with different variances to the dataset. 2) Estimate the density functions for noisy data with different variances by a set of NFs. 3) Estimate the ID from the eigenvalues of Jacobian matrices of tranformations defined by NFs.
strengths_and_weaknesses: Strengths:

Authors use the structure and property of NFs in a very clever way and show that we can obtain the information on ID from eigenvalues of Jacobian matrices of NFs. As far as I know, the eigenvalues of the Jacobian matrices of are rarely noticed in the research on NFs. In addition, the method is technically sound, and experiments also demonstrate the effectiveness of the proposed method.

Weaknesses:

The main weakness of the paper comes from that the justification of the proposed method is not well formulated. See below for details.
questions: On the justification:

1) The main "theoretical" basis of the method is Observation 1, but it is just an "observation" instead of a theorem (even an "informal" theorem). So there's a lot of ambiguity here. What are definitions of variability and direction of variability? What does small/large variability mean? How can we quantify the variability? As an example, does the variability of a standard Gaussian distribution have the same magnitude for all directions? If so, how about the uniform distribution or other isotropic probability distributions?

2) In addition, does Eq. (8) mean that the "variability" is a constant for any position for a standard Gaussian distribution? Can we choose the target distribution of f^{-1}(x) as uniform distribution or other isotropic probability distributions?

3) The similar question for Observation 2: Why can the conclusion on the Gaussian distribution be extended to a general noisy data-manifold?

As a summary, I believe the observations are reasonable, and the method developed based on the observations really works. But more thorough analysis and explanations are required. I hope to see two theorems (even informal theorems based on some specific assumptions) in the revision.

Some other comments:

4) In Lines 43-50, a very interesting problem is proposed: The dataset may be on a union of manifolds, and the local ID is more useful than the global one in this case. But all experiments in this paper are on estimation of global ID. Can the NF method be applied to estimation of local ID? Is there any difficulty?

5) It seems that the intrinsic noise is assumed to be Gaussian and spatial homogeneous. Will the performance of the algorithm be greatly affected if the assumption does not hold?

6) Besides the "dimension number", people are also interested in the component related to each dimension. Can we get, for example, the projection of data on the dimensions, from eigenvectors of Jacobian matrices of NFs?

7) The paper is highly related to the SoftFlow proposed in [22]. In SoftFlow, one NF is trained for different noise magnitudes with the noise magnitude being a parameter of the NF. This technique may be also helpful for this paper since SoftFlow can easily obtain the structure of the data independent of noise.
limitations: Authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper discusses the use of normalizing flows for estimating the intrinsic dimensionality (d) of the data sub-manifold embedded in high-dimensional ambient space ($\mathbb{R}^D, d < D$). The authors claim the proposed method based on flows is scalable and accurate compared to some standard techniques, e.g., nearest neighbor searches. The proposed method is based on a PCA-like rule, i.e., an eigendecomposition of a covariance transformation, by approximating the non-linear flow as a linear map with a Jacobian. The authors propose two techniques that can estimate whether a certain eigenvector is an on-manifold direction or not: the first is simply checking out the magnitude of the corresponding eigenvalue and the latter is judging the sensitivity of eigenvalues by injecting some noises. The authors validate their proposed method experimentally, compared with the nearest neighbor and another flow-based approach (LIDL) for some simple examples and StyleGAN2 manifolds.
strengths_and_weaknesses: [Strengths]

The main idea of this paper is simple and principled. It can be derived from the fundamental principle of linear algebra, thus easy-to-follow. The paper is generally well-written, while there are some confusing points (see minor comments). The proposed method outperforms other competitors including LIDL (which might be the SOTA so far), for some synthetic examples.


[Weaknesses]

I am not fully convinced with the proposed method, especially whether it can be used for a more complicated manifold regarding both in terms of accuracy and scalability (see major comments 1 and 2). In addition, I cannot find strong applications of the proposed method (see major comment 3). 

questions: [Major comments]

1. It seems the estimated intrinsic dimensionality is highly dependent on the manifold approximation performance of flows (i.e., the generative power of flows). Thus, it is not entirely clear whether the proposed method is suitable for extremely-complicated high-resolution datasets. Note that the method requires a down-sampling of StyleGAN-generated images (from $(1024, 1024, 3)$ to $(64, 64, 3)$), and fails to correctly estimate the dimensionality of such a generated manifold ($d=64$ but $\hat{d}=53$).

2. While the authors state the proposed method is scalable, there is no theoretical analysis as well as experimental demonstration regarding it. Because the proposed method should train a set of $N$ flows, it is not entirely sure it is indeed cheap. Please elaborate more.

3. What would be the killer application of the intrinsic dimensionality estimation? Can it be used to, e.g., improve generative performance, find disentangled representations, or detect anomaly samples correctly? It will be nice if the authors state some possible applications of the proposed method by demonstrating a proof-of-concept experiment regarding it.

[Minor comments]
1. It is not clear why $\beta_i$ should be used.

2. In the pedagogical example 4.1, it is not clear why the eigenvalues of on-manifold directions are different (see Fig. 1 (a)) while the underlying sub-manifold is a 2-sphere.

3. Observation 2 is not clear because (9) does not contain the injected noise $\sigma$ explicitly (while one may infer $\lambda^{(i)} = 1/ \sqrt{\sigma_{0}^{2} + \sigma_{i}^{2} + \sigma^{2}}$). 

4. In line 159 of page 4, the authors mention $\beta_i / \alpha_i = \lambda^{(i)}$ must be much larger for large variability directions, while in Observation 1 they mention large eigenvalues correspond to directions of small variability.


limitations: The authors state the limitation of the proposed method in the Discussion section, e.g., the possible computational cost (which is consistent with this reviewer’s major comment 2) and the theoretical assumption on the boundness of the data manifold. In my opinion, the former is not fully addressed, thus should be elaborated more for a convincing presentation of the manuscript. The latter seems to be addressed well by proposing some practical solution to deal with the bounded data, e.g., $0.68 * x_{max}$ for image data.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a novel NF-based algorithm to estimate intrinsic dimension. The algorithm is based on the observation that large variability is connected to small eigenvalues of the Jacobian, and that the variance of intrinsic noise can affect where the eigenvalue changes significantly. To estimate intrinsic dimension, this paper fits the Jacobian, and further uses two sigmoidal functions to fit the thresholding function that should have a plateau. Empirically, this paper compares the algorithm with prior methods on several experiments where the true intrinsic dimension is known. 
strengths_and_weaknesses: I am not an expert in the area of estimating intrinsic dimension, so I would like to leave the evaluation of originality and significance to other reviewers. I think this paper is clearly written, and the intuition is easy to follow. 

The methodology of this paper is one major strength. Using NF to estimate intrinsic dimension seems to be an interesting idea to me. The Jacobian matrix and its eigenvalues offer a nice way to investigate the sensitivity (variability) for each direction. In short, the entire section 4 makes a lot of sense to me. I especially like the idea of adding different magnitudes of Gaussian noises and training separate NFs. 

Empirically, the proposed algorithm can indeed estimate intrinsic dimension very accurately and outperform prior methods, which is another strength. 

Despite the above strengths, I think this paper lacks some key points. On the theory side, the algorithm does not come with theoretical guarantee, for example, approximation properties or (probabilistic) error bounds. Also, the choice of NF $f$ and noise magnitudes $\bar{\sigma}_n^2$ can potentially affect results by a lot, but there is neither theoretical nor empirical discussion on these. Finally, there is no such experiment that the proposed algorithm finds the intrinsic dimension in a practical problem (e.g. of a real dataset) and lead to successful application (e.g. help fixing the latent dimension of a generative model). 
questions: - What is the theoretical guarantee of the proposed algorithm? This question can include a lot of things, such as average-case guarantee or worst-case guarantee, bounds on errors or failure probabilities, etc. Do you have answers to at least one of these questions?

- What is the complexity of the proposed algorithm? 

- Do you have some assumption on the NF model, as different NF models behave very differently? Are there differences if you test different NF models in your experiments?

- How did you choose $N$ and noise magnitudes $\bar{\sigma}_n^2$ for $n=1,\cdots,N$? Is there a theoretically optimal schedule? What is the affect of changing this schedule, either theoretically or empirically?

- Does your algorithm lead to successful, practical applications that use intrinsic dimensions? For example, after running the proposed algorithm, you can find the correct latent dimension for a GAN model, and it outperforms other latent dimensions. 
limitations: The authors indicate there is no negative social impact as this is a theoretical paper, which I agree with. 

-----------------------------

After rebuttal, I decide to increase my score to 6.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a new approach termed ID-NF to estimating intrinsic dimensionality based on normalizing flows which can scale to large datasets and high dimensions ($64\times64\times 3$).  
ID-NF first specifies a dataset $\mathcal{D}=x_i, x_i\in \mathbb{R}^D$, $K$ samples $x_1^*, \dots, x_K^* \in \mathcal{D}$, and $N$ noise levels $\bar \sigma_1^2 <\dots <\bar\sigma_N^2$. 
For each noise level, ID-NF injects noise $\epsilon_n\sim \mathcal{N}(0, \bar\sigma_n^2 I)$ to the data and use an NF $f_n$ to learn the distribution $q_{\bar\sigma_n^2}$. Then ID_NF calculate the eigenvalues ${\lambda_n^{(i)}(x_k^*)}$ of $J_{f^{-1}_n}(x_k^*)$ for each $k=1,\dots,K$ and compute $\hat\lambda_n^{(i)} = \frac1K \sum_1^K \lambda_n^{(i)}(x_k^*)$.
By fitting $\hat\lambda_n (\sigma^2) = \frac{\beta_i}{\sqrt{\alpha^2_i + \sigma^2}}$ with $\alpha_i, \beta_i$, ID-NF use {$\alpha_i$} to estimate intrinsic dimension.  
strengths_and_weaknesses: **Strengths**:
* To the best of my knowledge, the intrinsic dimensionality estimation method based on NFs is novel. 
* Detailed experiments on pedagogical examples, low-dimensional synthetic examples, and high dimensional images generated by StyleGAN show the effects of this method. 

**Weakness**:
* The paper approximate the NFs with $f^{-1}(x) \approx f^{-1}(x^*) + J_{f^{-1}}(x^*)(x-x^*)$, thus the distribution of $x$ should be approximately Gaussian. Then the Observation1 and 2 holds. This is valid locally, but not globally. I think this gap is not well addressed in the paper. 
* Training NFs is expensive.  For $N$ noise levels, ID-NF should train $N$ NFs to approximate $q_{\sigma_n}$, which is quite expensive. Computing eigenvalues of $J_{f^{-1}}$ for many high-dimensional samples ($10^4$ for 2d-styleGAN  and $2\times 10^4$ for 64d-styleGAN) is also expensive.
* Algorithm4 computes mean eigenvalues of $J_{f^{-1}}$. I think for different samples $x_k^*$, eigenvalues of $J_{f^{-1}}(x^*_k)$ correspond to the variability along the directions indicated by eigenvectors, so how is the averaging operation performed? 

**Minor**:
* Line188: grea*ter.
* Line159: As I understand, $\beta_i/\alpha_i$ should be larger for *small* variability directions? 

questions: * I think Table1 is not a fair comparison, since the dimensionality estimated by ID-NF is naturally around an integer, but LIDL seems not. 
limitations: Limitations seen above. Societal impact: none
review_title: null

Meta-review: metareview: This paper discusses the use of normalizing flows for estimating the intrinsic dimensionality of the data sub-manifold embedded in high-dimensional ambient space. The idea of using NFs to estimate the intrinsic dimensionality via analyzing the eigenvalues of the Jacobian matrices is novel. The method is technically sound, and the paper presents detailed experiments on pedagogical examples, low-dimensional synthetic examples, and high-dimensional images generated by StyleGAN, which show the effects of this method.

confidence: Certain
Decision: Accept