Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: == Summary ==

The paper studies the relationship between the intrinsic dimension of images and sample complexity and generalization. The authors suggest to use a variant of the MLE method of Levina & Bickel (2004), which is based on computing the distances to nearest neighbors in pixel space, which is fairly easy to implement and 

== Pros ==

- The authors aim to investigate two relevant hypotheses for the field of representation learning. 1) intrinsic dimension of images is much lower than extrinsic dimension, and 2) extrinsic dimension has little effect on sample complexity. 

- To test hypothesis 1), they use an estimator of the intrinsic dimension, and measure its fitness in a controlled setting for which the know the real intrinsic dimension (images generated by an state-of-the-art GAN). Hypothesis 1) is confirmed under this controlled setting and under a real scenario. 

- Section 5.1. shows the (inverse) correlation between intrinsic dimension and sample complexity, and shows that extrinsic dimension (i.e. number of pixels) has a much weaker correlation. This section aims to confirm hypothesis number 2).

- I also find interesting the experiments in section 5.2, which studies the (inverse) correlation between intrinsic dimension and generalization (i.e. test accuracy). 

== Cons ==

- Caption in Figure 3 states that the authors "observe the estimates to converge around the expected dimensionality of 10". However, the dimensionality estimate greatly depends on k, the number of neighbours used for each image. No variance/confidence interval methods are reported, in this figure, so it's unclear whether the differences between 12 and 10 are large or not (although they seem small if one compares against the extrinsic dimension of the images: 128x128x3).

- This paper uses yet another intrinsic dimension estimator, different from Gong et al. 2019 and Ansuini et al. 2019. It's unclear what's the impact of the estimator in the predicted value of the intrinsic dimension.

- One of the emphasized contributions of the paper is that it's "the first to show that intrinsic but not extrinsic dimensionality  matters for the generalization of deep networks" (page 6). As far as this reviewer is aware, indeed this paper is the first to measure intrinsic dimensionality *of images* and its relationship with generalization, but there are others that compare the intrinsic dimensionality of the final embedding with accuracy, showing the same conclusion (e.g. Gong et al. 2019, Ansuini et al 2019). Thus, the authors should be more specific when talking about intrinsic/extrinsic dimensionality (it refers to the image, not the embedding representation of a given deep neural network classifier).

- Both the intrinsic dimensionality of the images and the classifier will impact the accuracy. This paper only focuses on the former, while other papers focus on the latter. Since this paper is posterior to the aforementioned papers, it would be appreciated if the authors could comment on which intrinsic dimensionality shows larger correlation with generalization, and draw some relationship among them.

- Some figures can be hardly read if printed in grayscale (Figures 3, 6, 7, 8). I would suggest to use different line styles to better discern among curves in the plots, and using hatches in the histograms (Figure 1). 

- In the introduction, it seems that the authors missed important seminal works on autoencoders (e.g. "Reducing the dimensionality of data with neural networks" by Hinton and Salakhutdinov, 2016), since their references for autoencoders and regularization methods date back only to 2018.

- I have some minor concerns regarding computational cost. The authors use a fraction of images as "anchors" and compute the nearest neighbour against the rest of the images in the dataset. This still leads to a quadratic cost in the number of images in the dataset, which may become problematic with modern datasets (ImageNet or even bigger ones). Given that the dimensionality estimates don't change much (e.g. Figure 3), why not fixing the number of samples to a constant number (e.g. 1000)?

== Rationale for the score ==

Although I raised many points in my "Cons" section, many of these are more questions rather than specific issues that I have with the presented paper. The paper tackles an important question of interest for the ICLR community: how to estimate the intrinsic dimensionality of our datsets, and which impact does it have on generalization and sample complexity, and it does so with a quite convincing experimental setup. The method proposed by the authors could have important applications, such as estimating the number of required training samples for reaching a target accuracy.

I hope that the authors can address my questions/concerns during the rebuttal to increase my score.

*Update after discussion*: The authors have addressed all the points that I raised during the discussion. I appreciate the effort, and I'm increasing my score accordingly.
review_title: Tackling an interesting question, experiments could be improved

final_score: rating: 7: Good paper, accept
review_content: This paper studies the intrinsic dimension of image datasets and connects it to the generalization ability of deep neural networks. The three contributions are 1) measuring  intrinsic dimension of common image datasets (e.g., MNIST, CIFAR, ImageNet, COCO, CelebA), 2) demonstrating using GANs, for which one has control of the intrinsic dimension, the effectiveness of their dimension estimator for images and 3) tying intrinsic dimensionality to generalization performance. 

Strength:

I am actually a bit surprised that no existing work to my knowledge has carefully measured the intrinsic dimension of modern image datasets. A work of such provides important justifications for numerous work on understanding and designing CNNs based on low-dimensional assumptions.  Therefore, I appreciate the novelty and the significance of the work very much. 

Weaknesses:

My main concern is that the work appears underdeveloped in its current form and does not convincingly justify its conclusion. In particular, estimation of intrinsic dimension of dataset is the foundation for the development of this work, but the discussion for it is very shallow:

1. It is not clear why (1) provides an estimate of intrinsic dimensions. Under what assumptions is it derived? For example, is it assuming that the manifold is mostly flat or does it also work when manifold is curved?

2. There is no discussion on the effect of k and how it should be selected. What could go wrong if I pick k to be too large or low small? Will it result in over-estimation or under-estimation of the dimension? 

3. How is the dimension of the subspace/manifold affects the choice of k? This question is relevant to Table 1 where the comparison of dimension for different datasets are based on the same k = 5, 10 or 20, but likely the best choice of k is different for different datasets. I'd also suggest an experiment in the GAN setting where such effect is demonstrated through experiments, perhaps with a figure similar to Fig. 3 but with a fixed number of samples and varying n in the x-axis. 

4. Estimation of intrinsic dimension from data has been extensively studied (see e.g. [a, b, c]), and many recent works have used such notions to develop robust deep learning methods [d, e]. There should be a explanation on why (1) is picked over the other choices, e.g., are they better choices than those used in [d, e]?

a. Maximum Likelihood Estimation of Intrinsic Dimension, 2004
b. Estimating the intrinsic dimension of datasets by a minimal neighborhood information, 2017
c. Local Intrinsic Dimensionality I: An Extreme-Value-Theoretic Foundation for Similarity Applications, 2017
d. Dimensionality-Driven Learning with Noisy Labels, 2018
e. CHARACTERIZING ADVERSARIAL SUBSPACES USING LOCAL INTRINSIC DIMENSIONALITY, 2018

Overall, I am not fully convinced as to whether the estimation of the intrinsic dimension from this paper is a faithful and good enough characterization of the true intrinsic dimension. My suggestion is that the paper provides a review of existing dimension estimation methods,  clearly points out the pros and cons of each (conceptually and perhaps also by experiments), explains the reason for the specific choice in the paper, and provides some discussion on the properties of the specific dimension estimation method. 

Minor comment:

- A key challenge in estimating intrinsic dimension of images in e.g. ImageNet is that they lie in relatively high-dimensional subspaces and suffer more from curse of dimensionality. Therefore, it may be beneficial to use data augmentation for generating more sample points, which may help to improve the precision of estimation. 

- Fig. 3 is not color blind friendly, maybe consider using different line types. 

- Sec. 5, first line: establish -> established


**Update after rebuttal** 

I would like to thank the authors for the additional details provided in the rebuttal and revised version. All my concerns have been adequately addressed. Given the importance of the topic and the development is reasonably solid, I would like to recommend for its acceptance. 
review_title: Interesting work on dimension of images but the development can be more solid

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ## Review

### Summary

The paper proposes an empirical analysis of the dimension of natural images of multiple datasets.
The contributions are:
1. A validation for nat. im. of previously proposed dimension estimation methods (using GAN to control the intrinsic dimension of the generated im.)
2. A confirmation that intrinsic dimension of nat. im. is lower than the dimension of their pixel space
3. That the lower the intrinsic dimension the easier the learning (for neural net)

### Strengths

* The paper is well-written and easy to follow. 
* The data analysis pipeline is convincing.
* Up to my knowledge there is no such a clear statement about the dimension of natural image 

### Weaknesses

* The results are not sufficiently discussed. I think the idea that nat. im. are low-d is more controversial than it is presented. It is sometime proposed that image patches (which are more likely to be textures) are low-d (eg Brendel & Bethge ICLR 2019). In relation, to neural net learning, these are known to be biased toward textures (Geirhos et. al. ICLR 2019). So among your contribution 3/ can be true while 2/ is not (but then what would explain your finding ?). I mean that in fact 3/ is more due two the low-d of textures than the low-d of nat. im. (which would still be too high).Complementary to this, it is suggested that natural images can be viewed as mixture of textures which belong to different low-d manifold (Vacher & Coen-Cagli, arXiv 1905.10629; Vacher et. al., NeurIPS 2020). 

### Minor comments

* None



review_title: Interesting work

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
The authors report a novel application of GANs to validate the maximum likelihood estimator (MLE) of the intrinsic dimension (ID) of image data sets. Then they use the MLE ID estimator to characterize the intrinsic dimension of several commonly used computer vision data sets, and link the data set ID to the generalizability of trained classifiers.  They provide additional experiments that support the notion that it is intrinsic dimension, and not extrinsic dimension (i.e. # of pixels), that governs the performance of a binary classifier on these data sets. Also, they verify that dimension plays a large role in learning on natural data.

I found the paper to be clearly written, with only a few minor typographical errors in the writing, and the subject to be of practical usefulness to the deep learning community.  However, I do feel that the authors should perform a few additional experiments (I think they are reasonably simple) to improve the understanding of the results. I think this might be a topic of great interest to the computer vision community since this paper describes a novel application of GANs to study the sample complexity of convolutional neural networks, 



*Review
Pros include:
innovative use of GANs to generate synthetic data of bounded intrinsic dimension
well written and easy to read
coherent story

Cons:
limited analysis and discussion of the role of the image class (particularly in ImageNet) on the MLE estimate of intrinsic dimension
Some details not listed in the paper, including the metric for the distance between images used to compute the MLE ID estimate
Non-sequitur in the analysis of the role of image extrinsic dimension in classifier generalization; see comments below.


In section 5.1, the authors use the method of image reshaping using nearest-neighbour interpolation to increase extrinsic dimensionality of images. A comparison of the generalization performance of classifier models on data sets with different extrinsic dimensionality is thus made.

>>The authors make the claim that generalization performance depends on intrinsic, but not extrinsic, the dimensionality of images. However, the method of image reshaping using interpolation seems to be reversible (i.e. lossless), and thus their generated images should have identical information content independent of extrinsic dimension.  For example, images collected using a high-resolution camera can not be faithfully reproduced by interpolation of images taken by a low-resolution camera.  It would be more interesting to consider the realistic scenario where images of lower dimension are generated by lossy downsampling of higher resolution images and to then characterize whether either generalization performance or intrinsic dimension were related to extrinsic dimension. I would guess that the intrinsic dimension of natural images is actually higher when they have a higher extrinsic dimension since there might be more fine details captured within images of high resolution.  Conceptual example: I might argue that the number and location of wrinkles on people’s faces is a variable that increases the intrinsic dimension of a facial photo data set, but only if the images are sufficiently high resolution to see the wrinkles.

In section 5.2, the authors downsample images of 5 randomly chosen class pairs from each real-world data set and then 1) compute MLE estimates of ID for each data set, and 2) compare the sample complexity of a binary classification problem on each.

>>It is interesting that while ImageNet MLE ID (k=5) is 38 and CIFAR-10 MLE ID (k=5) is 21, the MLE ID estimates (which are made using k=3 instead of k=5 or another previously used value; a choice not explained by the authors) for the low-resolution 5-random-class-pair samples of each data set are 15.4 and 11.4, respectively.  It seems that the ID of the two datasets are much more similar after the resolution-reduction and class-sampling, suggesting that intrinsic dimension of image data sets is strongly determined by either extrinsic dimension or the number (and kind) of classes present. The authors should comment on this fact.  Furthermore, given these observations, the authors should make some effort to determine which process (i.e., the lossy image reshaping, or the random sampling of 5 class pairs) contributes the most to the apparently much greater reduction in MLE ID that ImageNet suffers compared to CIFAR-10 in this experiment, and whether there are specific classes in ImageNet that contribute more to the intrinsic dimension of the data set than others. Perhaps the authors could simply compute the MLE ID estimate for the different classes of ImageNet (with and without image reshaping to 32x32x3), and then state which 5 class pairs were randomly chosen for the experiment in section 5.2.   These additional computations might explain the “unexpected cross-over points” mentioned in the paper.

In sections 5.3 and 5.4, the authors perform additional experiments showing that the intrinsic dimension (in this case modulated by either adding fixed-dimensionality noise or by applying image augmentation techniques) is associated with generalization performance of deep learning models.

>>In the discussion, the authors write “While there may be many factors, such as class separation and the number of classes, which determine generalization, we build the case that intrinsic dimension is one of these important factors.“  I think it might be true the intrinsic dimension is actually determined by both extrinsic dimensions and by inter-class and intra-class image diversity (i.e., number of classes and varying hardness of each class during classification). As I mentioned above, the authors could perform several simple experiments using their existing experimental framework to test this hypothesis, and I think doing so would significantly improve the quality of the paper.  Despite this point, I find the paper to be of acceptable quality.

review_title: The authors report a novel application of GANs to validate the maximum likelihood estimator (MLE) of the intrinsic dimension (ID) of image data sets. Then they use the MLE ID estimator to characterize the intrinsic dimension of several commonly used computer vision data sets, and link the data set ID to the generalizability of trained classifiers. Also, they verify that dimension plays a large role in learning on natural data.

Meta-review: There was a consensus among reviewers that this paper should be accepted as the authors addressed reviewers' concerns in the discussion phase. This paper is well-written and easy to read. It provides a coherent story and investigation on two important hypotheses: that natural images have a lower intrinsic dimension than the extrinsic dimension (e.g. the number of pixels) and that a lower intrinsic dimension lowers the sample complexity of learning. These results appear to be novel and significant for the ICLR community as it provides justifications for numerous work on understanding and designing convolutional neural networks based on low-dimensional assumptions.
Decision: Accept (Spotlight)