The Intrinsic Dimension of Images and Its Impact on Learning
Authors: Phil Pope
Chen Zhu
Ahmed Abdelkader
Micah Goldblum
Tom Goldstein
Venue: ICLR 2021 Spotlight (2021)
Keywords: generalization
dimension
manifold
ImageNet
CIFAR

Abstract: It is widely believed that natural image data exhibits low-dimensional structure despite the high dimensionality of conventional pixel representations.  This idea underlies a common intuition for the remarkable success of deep learning in computer vision. In this work, we apply dimension estimation tools to popular datasets and investigate the role of low-dimensional structure in deep learning.  We find that common natural image datasets indeed have very low intrinsic dimension relative to the high number of pixels in the images.  Additionally, we find that low dimensional datasets are easier for neural networks to learn, and models solving these tasks generalize better from training to test data.   Along the way,  we develop a technique for validating our dimension estimation tools on synthetic data generated by GANs allowing us to actively manipulate the intrinsic dimension by controlling the image generation process. Code for our experiments may be found  \href{https://github.com/ppope/dimensions}{here}.

Published as a conference paper at ICLR 2021
THE INTRINSIC DIMENSION OF IMAGES AND ITS IMPACT ON LEARNING
Phillip Popel, Chen Zhu', Ahmed Abdelkader", Micah Goldblum', Tom Goldstein
Department of Computer Science, University of Maryland, College Park 2 Oden Institute for Computational Engineering and Sciences, University of Texas Austin (pepope, chenzhu) gumd. akader@utexas.com
{goldblumg tomg) @uud..du adu
ABSTRACT
It is widely believed that natural image data exhibits Now-dimensional structure despite the high dimensionality of conventional pixel representations. This idea underlies a common intuition for the remarkable success of deep learning in com- puter vision. In this work, we apply dimension estimation tools to popular datasets and investigate the role of low-dimensional structure in deep learning. We find that common natural image datasets indeed have very low intrinsic dimension rel- ative to the high number of pixels in the images. Additionally, we find that low dimensional datasets are easier for neural networks to learn, and models solving these tasks generalize better from training to test data. Along the way, we de- velop technique for validating our dimension estimation tools synthetic data generated by GANs allowing us to actively manipulate the intrinsic dimension by controlling the image generation process. Code for our experiments may be found here
INTRODUCTION
The idea that real-world data distributions can be described by very few variables underpins ma- chine learning research from manifold learning to dimension reduction (Besold & Spokoiny| [2019] Fodor 2002). The number of variables needed to describe a data distribution is known as its Irinsic dimension (ID). In applications, such as crystallography. computer graphics, and ecology, practitioners depend on data having low intrinsic dimension (Valle & Oganov 2210 (Debrru al.)
2002 Laughlin 2014). The utility of representations which are low-dimensional has motivated variety of deep learning techniques including autoencoders and regularization methods (Hinton &
Salakhutdinov 2006; Vincent et al. 2010; Gonzalez & Balajewicz, 2018: Zhu et al., (0118).
is also known that dimensionality plays a strong role in learning function approximations and non-linear class boundaries. The exponential cost of learning in high dimensions is easily captured by the trivial case of sampling a function on a cube; in d dimensions, sampling only the cube vertices would require 2d measurements. Similar behaviors emerge in learning theory. It is known that learning a manifold requires a number of samples that grows exponentially with the manifold's intrinsic dimension (Narayanan & Mitter 2010).. Similarly, the number of samples needed to learn well-conditioned decision boundary between two classes is an exponential function of the intrinsic dimension of the manifold on which the classes lie (Narayanan & Niyogi 2009). Furthermore, these learning bounds have no dependence on the ambient dimension in which manifold -eruuuld-strueturee datasets live.
In light of the exponentially large sample complexity of learning high-dimensional functions, the ability of neural networks learn from image data remarkable. Networks learn complex decision boundaries from small amounts of image data (often just few hundred or thousand samples per class). At the same time, generative adversarial networks (GANs) are able to learn image "mani- folds" from merely few thousand samples. The seemingly low number of samples needed to learn these manifolds strongly suggests that image datasets have extremely low-dimensional structure.
Despite the established role of low dimensional data in deep learning, little is known about the in- trinsic dimension of popular datasets and the impact of dimensionality on the performance of neural networks. Computational methods for estimating intrinsic dimension enable these measurements.

---

Published as a conference paper at ICLR 2021
50
k=3
k=5
k=10
Dimensionallyy Estimate
40
30
0
20
10-
MNIST
CIFAR-
CIFAR-10
COCO
ImageNet
Figure 1: Estimates of the intrinsic dimension of commonly used datasets obtained using the MLE method
with k = 3,5,, 5, 10, 20 nearest neighbors (left to right). The trends are consistent using different k's.
We adopt tools from the dimension estimation literature to shed light on dimensionality in settings of interest the deep learning community. Our contributions be summarized follows:
We verify the reliability of intrinsic dimension estimation generative adversarial networks (GANs), a setting in which we can a priori upper-bound the intrinsic dimension of generated data by the dimension of the latent noise vector.
high-dimensional data using
We measure the dimensionality of popular datasets such MNIST, CIFAR-10, and Im- ageNet. our experiments, we find that natural image datasets whose images contain thousands of pixels can, in fact, be described by orders of magnitude fewer variables. For example, we estimate that ImageNet, despite containing 224 x 224 x 3 150528 pixels per image, only has intrinsic dimension between 26 and 43; Figure
We train classifiers on data, synthetic and real, of various intrinsic dimension and find that this variable correlates closely with the number of samples needed for learning, On the other hand, we find that extrinsic dimension, the dimension of the ambient space in which data is embedded, has little impact on generalization.
Together, these results put experimental weight behind the hypothesis that the unintuitively low dimensionality of natural images is being exploited by deep networks, and suggest that a character- ization of this structure is an essential building block for successful theory of deep learning.
2 RELATED WORK
While the hypothesis that natural images lie on Goodfellow et al.] (2016) argue that the low-dimensional manifold assumption is at least approx- imately correct for images, supported by observations. First, natural images locally nected, with each image surrounded by other highly similar images reachable through image trans- formations (e.g., contrast, brightness). Second, natural images seem lie on a low-dimensional structure, as the probability distribution of images is highly concentrated: uniformly sampled pixels can hardly assemble meaningful image. is widely believed that the combination of natural scenes and sensor properties yields very sparse and concentrated image distributions, as has been supported by several empirical studies on image patches (Lee al. 2003 Donoho & Grimes 2005 Carlsson
dow-dimensione manifold is controversial,
et al. 2008). This observation motivated work on efficient coding (Olshausen & Field 1996) and
served as prior computer vision (Peyré) 2009). Further, rigorous experiments have been con- ducted clearly supporting the low-dimensional manifold hypothesis for many image datasets (Rud-) erman 1994; Schölkopf et al., 1998 Roweis Saul 2000, Tenenbaum et al.) 2000; Brand 2003); also (Fefferman al. 2016) for principled algorithms verifying the manifold hypothesis.
The generalization literature seeks to understand why some models generalize better from training data to test data than others. One line of work suggests that the loss landscape geometry explains why neural networks generalize well (Huang et al.) 2019). Other generalization work predicts that data with low dimension, along with other properties which do not include extrinsic dimension,
2

---

Published as a conference paper at ICLR 2021
characterize the generalization difficulty of classification problems (Naaayaaan & Niyogi 2009
In the context of deep learning, [Gong et al. (2019) found that neural network features are low- dimensional. Ansuini et al. (2019) further found that the intrinsic dimension of features decreases in late layers of neural networks and observed interesting trends in the dimension of features in early layers. In contrast Gong et al. (2019) and Ansuini al. (2019), who find that the intrinsic dimension of internal representations is inversely correlated with high performance, we study the dimensionality of data and its impact on performance, and we make similar finding. Zhu et al. (2118) proposed regularizer derived from the intrinsic dimension of images augmented with their corresponding feature vectors. Another line of work in deep learning has found that neural networks rely heavily on textures which are low-dimensional (Geirhos et al., 2018: Brendel & Bethge| 22019). Similarly, some have suggested that natural images can be represented as mixtures textures which lie on a low-dimensional manifold (Vacher & Coen-Cagli 2019 Vacher et al. 2020).
INTRINSIC DIMENSION ESTIMATION
Given a set of sample points P C RN,, it is common to assume that P lies on or near a low- dimensional manifold .M C RR- of intrinsic dimension dim(.M) d N. As measure of the degrees of freedom in a dataset, as well as the information content, there is great interest in estimat- ing the intrinsic dimension d. In the remainder of this section, we briefly describe the dimension estimation method we use in this paper, for further information, see (Kim et al. (2019) and references therein.
One of the main approaches to intrinsic dimension estimation is to examine neighborhood around each point in the dataset, and compute the Euclidean distance to the k nearest neighbor. Assuming that density is constant within small neighborhoods, the Maximum Likelihood Estimation (MLE) Levina & Bickel (2005) uses a Poisson process to model the number of points found by random sampling within a given radius around each sample point. By relating the rate of this process to the surface area of the sphere, the likelihood equations yield an estimate of the ID at a given point x as:
(x) vi (x) = k log (x
where (x) is the Euclidean (l2) distance from to its jth nearest neighbor. Levina & Bickel 2005) propose to average the local estimates at each point to obtain a global estimate mi En= (x.). MacKay & Ghahramani (2005) suggestion correction based on averaging of inverses
-1
n mp (2:)
log Tx(2x) Tj (xx)))
mik
n
nlk
where n is the number of samples. We use Equation (2) as our MLE estimator throughout this paper.
Since the geometry of natural images complex and unknown, we face two challenges when verify- ing the accuracy of MLE on natural image datasets. First, we need to choose a proper value of k. As shown by Kac & Ghahramani (2005), the positive bias of the corrected estimator Equation (2 increases as l increases, but the variance decreases. In order to navigate this biri-variance tradeoff, we try various values of k in Section 4 Second, in addition the aforementioned local uniformity assumption, MLE assumes that data arises as sequence of i.i.d. random variables which can be written as a continuous and sufficiently smooth function of a random variable with smooth density, which may may not be true for natural image datasets. While the truth of these assumptions is unknown on natural images, we verify the accuracy of our MLE estimates in a controlled setting in the following section.
We briefly discuss other notable techniques for dimensionality estimation. GeoMLE (Gomtsyan et al., 2019) attempts to account for non-uniformity of density and nonlincarity of manifold us- ing a polynomial regression of standard MLE based on distances to nearest neighbors in different sized neighborhoods. However, GeoMLE chooses approximate averages of (x:), instead of
3

---

Published as a conference paper at ICLR 2021
averaging its reciprocal like Equation resulting in potentially wrong maximum likelihood timator. As a result, we find its estimation deviates significantly from expected dimensionalities. TwoNN (Facco et al. 2017) is based on the ratio of the distances to the first and second near- est neighbors. Finally, the approach of (Granata & Carnevale 2016) considers the distribution of geodesic distances over the data manifold, approximated by distances through kNN graphs, com- pared to the distribution of distances over hyperspheres of varying dimension. Unlike MLE, our preliminary experiments suggest that these techniques do not provide reasonable estimates for some natural and synthetic images which are key to this work; see Appendix A.5 for further discussion.
4 VALIDATING DIMENSION ESTIMATION WITH SYNTHETIC DATA
Dimensionality estimates are often applied on "simple" manifolds or toy datasets where the dimen- sionality known, and so the accuracy of the methods can be validated. Image manifolds, by con- trast, are highly complex, may contain many symmetries and modes, and are of unknown dimension. In principle, there is no reason why MLF-based dimensionality estimates cannot be applied to image datasets. However, because we lack knowledge of the exact dimensionality of image datasets, we cannot directly verify that ML.E-basdd dimensionality estimates scale up to the complexity of image structures.
There is an inherent uncertainty in estimating the ID of a given dataset. First, we cannot be sure the dataset actually resembles a sampling of points on or near manifold. Second, there are typically no guarantees that the sampling satisfies the conditions assumed by the ID estimators we are using.
Towards a principled application of ID estimates in contexts of practical relevance to deep learn- ing, we begin by validating that MLE methods can generate accurate dimensionality estimates for complex image data. We do this by generating synthetic image datasets using generative models for which the intrinsic dimensionality can be upper-bounded a priori. We believe such validations are essential put recent findings in perspective (Gong al. 2019 Ansuini et al. 2019).
GAN Images We use the BigGAN variant with 128 latent entries and outputs of size 128 x 128 x 3 trained on the ImageNet dataset (Deng et al. 2009). Using this GAN, we generate datasets with a varying number of images, where we fix most entries of the latent vectors to zero leaving only d free entries to be chosen random. As we increase the number of free entries, we expect the intrinsic dimension to increase with d as an upper bound; see Section A. for further discussion.
In particular, we create several synthetic datasets of varying intrinsic dimensionality using the Ima- geNet class, basen ji, and check if the estimates match our expectation. As seen in Figure 2 we observe increasing diversity with increasing intrinsic dimension. In Figure 3 we show convergence of the MLE estimate on basenj j i data with dimension bounded above by d 10. We observe that the estimates can be sensitive to the choice of i as discussed in prior work; see Appendix A.2 for additional GAN classes.
Scaling to large datasets. We develop a practical approach for estimating the ID of large datasets such as ImageNet. In this approach, we randomly select fraction of the dataset as anchors. Then, we evaluate the MLE estimate using only the anchor points, where nearest-neighbor are computed over the entire dataset. Note that, when anchors are chosen randomly, this acceleration has no impact on the expected value of the result. See Appendix A.3 for an evaluation of this approach.
5 THE INTRINSIC DIMENSION OF POPULAR DATASETS
In this section, we measure the intrinsic dimensions of number of popular datasets including MNIST (Deng 2012). SVHN (Netzer et al. 201T), CIFAR-10 and CIFAR- (Krizhessky et al.) 2009), ImageNet (Degg et al. 2009), MS-COCO (Lin et al., 2014), and CelebA (Liu et al. 2015). Using three different parameter settings for the MIE ID estimator, we find that the ID indeed much smaller than the number of pixels; see Table 5 Notice that the rank order of datasets by di- mension does not depend on the choice of k. A comparison of of (SOTA) classification accuracy each respective datase with the dimension estimates suggests a negative correlation
Values from https: httppp:://ppppee http::/papppaewwieeeee hww.eeees..ccoccccooooo.oooo http:////////tt//c////////ck mage- o assi fication
4

---

Published as a conference paper at ICLR 2021
d= 8
d 16
d = 32
d = 64
d d= 128
Figure 2: Visualization of basenji GAN samples of varying intrinsic dimension.
14.
Dimensionaltty Estimate
1--10
11
10
Number of Sumples
Validation of MLE estimate on synthetic basen ji with d free entries. observe estimates to converge around the expected dimensionality of 10, Standard errors plotted with N 5 replicates over random samples of the data.
Figure 3:
between the intrinsic dimension and accuracy. In the next section, we take closer look this phenomenon through series of dedicated experiments.
INTRINSIC DIMENSION AND GENERALIZATION
Learning theory work has established that learning manifold requires number of samples that grows exponentially with the manifold's intrinsic dimension (Narayanan & Mitter (2010). but the required number of samples is independent of the extrinsic dimension. Specifically, the number of

---

that data of higher intrinsic dimension Published as a conference paper at ICLR 2021
Dataset
MNIST
SVHN
CIFAR-100
CelebA
CIFAR-10
MS-COCO
ImageNet
MLE (k=3)
7
11
9
13
22
26
MLE 5k=5)
11
18
33
MLE (k=10)
12
18
22
24
25
37
43
MLE (k=20)
13
19
23
26
26
36
43
SOTA Accuracy
99.84
99.01
93.51
99.37
88.55
The MLE estimates for practical image datasets, and the statc-of-the-art test-set image classification accuracy (for classification problems only) for these datasets.
Table I:
samples needed to learn well-conditioned decision boundary between two classes is exponential in the intrinsic dimension of the manifold on which the classes lie (Narayanan & Niyogi 2009).
We leverage dimension estimation tools empirically verify these theoretical findings using fam- ily of binary classification problems defined over both synthetic and real datasets of varying intrinsic dimension. In these experiments, observe connection between the intrinsic dimension of data and generalization. Specifically, we find that classification problems on data of lower intrinsic di- mensionality are easier to solve.
6.1 SYNTHETIC GAN DATA: SAMPLE COMPLEXITY DEPENDS ON INTRINSIC (NOT EXTRINSIC) DIMENSIONALITY
The synthetic GAN data generation technique described in Section 4 provides a unique opportunity test the relationship between generalization and the intrinsic/extrinsic dimensionality of images. By creating datasets with controlled intrinsic dimensionality, we may compare their sample com- plexity, that the number of samples required to obtain given level of test error. Specifically we test the following two hypotheses (1) data of lower intrinsic dimensionality has lower sample com- plexity than that of higher intrinsic dimensionality and (2) extrinsic dimensionality irrelevant for sample complexity.
To investigate hypothesis (1), we create four synthetic datasets of varying intrinsic dimensionality: 16, 32, 64, f extrinsic dimensionality: 32 32, and two classes: basenj ji and beagle. For each dataset we fix a test set of size N = 1700. For all experiments, we use the ResNet (width 64) architecture (He al.) [016). We then train models until they fit their entire training set with increasing amounts of training samples and measure the test error. We show these results in Figure 4 Observing the varying rates of growth, requires more samples to achieve a given test error.
For hypothesis (2), earry out the same experiment with the roles of intrinsic and extrinsic dimen- sion switched. We create four synthetic datasets of varying extrinsic dimensionality by resizing the images with cearest-neighhor interpolation. Specifically images of sizes 16, 32, 64, 128, 256, fixed intrinsic dimensionality of size 128, and all other experi- mental details the same. We show these results in Figure [5 Observing the lack of variable growth rates, we see that extrinsic dimension has little to no effect on sample complexity.
create 6 datasets of square, 3-channel
To the best of our knowledge, this the first experimental demonstration that intrinsic but not extrinsic dimensionality matlers for the generalization of deep networks.
6.2 REAL DATA: INTRINSIC DIMENSIONALITY MATTERS FOR GENERALIZATION
Next, we examine the sample complexity of binary classification tasks from four common image datasets: MNIST, SVHN, CIFAR-10, and ImageNet. This case differs from the synthetic case in that we have control over each dataset's intrinsic dimension. Instead, estimate via the MLE method discussed Section 3 To account for variable difficulty of classes, we randomly sample class pairs from each dataset and run the previously described sample complexity experiment. Note that these subsets differ from those used Table where the estimates are taken from the entire dataset and across all classes.
On these sampled subsets, we find the MLE estimates as shown in Table Note that these estimates consistent with expectation, e.g. MNIST is qualitatively simpler then SVHN CIFAR-10.

---

Published as a conference paper at ICLR 2021
100-
Acmurary
80
idim=16 16
id
idim=64
60
2000
4000
6000
8000
10000
Number Training Samples
Figure 4: Sample complexity of synthetic datasets of varying intrinsic dimensionality.
100.0
97.5-
92.5
3x16x116
87.5
3x32x32
3x61x64
85.0
3x1 3x126x120
8000
10000
Number of Training Samples
Figure 5: Sample complexity synthetic datascts of varying extrinsic dimensionality.
We conduct the same sample complexity experiment the previous section on the datasets. Because these datasets are ordinarily of varying extrinsic dimensionality, we resize all to size 32 x 32 x (before applying MLE). We report results in Figure 6 where overall observe trends ordered by intrinsic dimensionality estimate. These results are consistent with expectation of the relative hardness of each dataset. However, there are some notable differences from the synthetic case. Several unexpected cross-over points exist in the low-sample regime, and the gap between SVHN and CIFAR-I0 is smaller than one may expect based their estimated intrinsic dimension.
From these observations we conclude that intrinsic dimensionality is indeed relevant to generaliza- tion on real data, but is not the only feature of data that influences sample complexity.
MNIST
SVHN
CIFAR-10
ImageNet
A: =
7.5 (0.2)
8.5
11.4 (0.2)
15.4 (0.8)
A 9.8 (0.3)
(1.6
15.9 (0.2)
19.8 (0.9)
A 10.9 (0.4)
13.2 (0.1)
18.3 (0.3)
21.6 (1.0)
Table 2: Mean and standard error of estimated intrinsic dimensions for practical datasets under same resolution 32 x 32 x using different k's. These results are consistent with the test accuracies on these datasets under the same resolution.
6.3 REAL DATA: ADDING NOISE CHANGES DIMENSIONALITY AFFECT GENERALIZATION
In this section, examine alternative technique for changing the intrinsic dimension of real dataset: adding noise to images. Here we leverage the fact that uniformly sampled noise in [0, _] has dimension d. We thus add independent noise, drawn uniformly from fixed randomly oriented d-dimensional unit hypercube embedded in pixel space, to each sample in a dataset. This procedure ensures that the dataset has dimension at least d. Since the natural data and the hypercubes have high dimension, this procedure specifically increases dimensionality. We note that estimation enror may occur when there is insufficient number of samples to achieve
has low dimension,

---

Published as a conference paper at ICLR 2021
100
90
Acmurary
80
70
ciar10
Im Imagenet
moist
250
500
750
1000
1250
1500
1750
2000
Number Training Samples
Figure 6: Sample complexity of real datasets. Standard errors are shown N = class pairs.
a proper estimate. Since variation in images a dataset may still be dominated by non-noise directions, expect to underestimate the new increased dimensions of these noised datasets.
Starting with CIFAR-10 data, we add noise of varying dimensions, where we replace pixels at ran- dom in the image. We only add noise to an image once to keep the augmented dataset the same size as the original. We use the following noise dimensionalitics: 256, 512, 1024, 2048, 2560. The estimated dimensions of the noised datasets are listed in Table We see that intrinsic dimension in- creases with increasing noise dimensionality, but dimensionality does not saturate to the maximum true dimension, likely due to poverty of samples.
On these noisy CIFAR- 10 datasets, we again carry out the sample complexity experiment of the previous sections. We show results in Figure 7 We observe sample complexity largely in the same order as intrinsic dimension.
256
d
512
d 1024
1536
2048
d 2560
k
19.7
30.9
57.1
77.8
110.0
136.1
k
25.2
39.1
72.8
101.3
142.1
177.7
k 27.6
42.5
78.3
110.2
153.4
196.6
Table 3: Estimated intrinsic dimension of the CIFAR-10 dataset after adding different dimensions (d) of uniformly sampled noise using different k's. The estimated dimension consistently increases with d under different k's.
90
Accurncy
notse-dim 256
70
dim=511
noise dim=1 1024
noise-dim 1 1536
noise dim= di48
nolse-dim-22
200
300
400
500
600
700
800
900
1000
Number Training Samples
Figure 7: Sample complexity of noisy datasets. Standard errors are shown N 5 random subsets of the data.
6.4 MANIPULATING THE INTRINSIC DIMENSIONALITY OF FONTS
In this section, we describe a final technique for studying the effect of intrinsic dimensionality on sample complexity the recently proposed FONTS dataset (Stutz al. 2019). Beginning with collection characters and font types, termed prototype set by the authors, FONTS datasets are constructed using fixed set of data augmentations: scaling, translation, rotation, and sheering. In
8

---

Published as a conference paper at ICLR 2021
principle, these augmentations each increase the intrinsic dimension of the prototype set allowing us to synthetically alter the intrinsic dimension by varying the number of augmentations used.
We construct FONTS datasets in this way, FONTS- {0, 2, 3, 4]. where the suffix denotes the number transformations used in the data generation process. The MLE estimates on each of the datasets are given in Table
Consistent with expectation, we observe that MLE methods consistently resolve the increased dime- sionality of transformed datasets. Carrying out the sample complexity experiment of the previous section, we report results in Figure g
We observe again that, on the whole, sample complexity is ordered by intrinsic dimension.
FONTS-0
FONTS-1
PONTS-2
FONTS-3
FONTS-4
k: =
1.8 (0.1)
(0.1)
5.1 (0.2)
5.8 (0.2)
6,1 (0.3)
A: 2.7 (0.1)
(..)
6.9 (0.2)
7.8 (0.3)
8.3 (0.4)
k: 3.2 (0.1)
5.9 (0.1)
7.8 (0.3)
8.8 (0.4)
9.4 (0.4)
Table 4: Mean and standard enrrr of MLE estimates on the FONTS dataset under different number of trans- forms using different k's. Again, the ranks of the estimated IDs are consistent, and the estimated IDs increase with the number of transforms.
100.0
97.5
95.0
92.5
90.0
fonts
87.5
fonts 1
fants
82.5
tonts
200
400
600
800
1000
12000
1400
1600
Number of Training Samples
Figure 8: Sample complexity of FONTS datasets.
DISCUSSION
In this work, measure the intrinsic dimension of popular image datasets and show that the in- trinsic dimension of data matters for deep learning. While there may be many factors, such as class separation and the number of classes, which determine generalization, trinsic dimension is one of these important factors. Along the way, we introduce a technique for using GANs synthesize data while manipulating dimensionality. This technique useful not only for validating dimension estimation methods but also for examining the learning behavior of neural networks under conennion-coottllleed environment. dimension plays large role in learning on natural data. Our results support the commonly held belief that low dimensional structure underpins the success of deep learning on high-resolution data.
build the case that in-
addition to synthetic data, we verify that
These findings raise number of salient directions for future work. Methods for enhancing neural network learning on high-dimensional data could improve generalization on hard vision problems. To this end, deeper understanding of the mechanisms by which dimensionality plays role in learning may enable such methods. Additionally, our work indicates that different dimensionality estimation tools are better suited for different settings. Future work computing tighter and more reliable estimates specific to image data would allow the community to more precisely study the relationship between the dimensionality of image datasets and learning.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This work was supported by the DARPA GARD and DARPA QED programs. Further support was provided by the AFOSR MURI program, and the National Science Foundation's DMS division. Computation resources were funded by the Sloan Foundation.
REFERENCES
Alessio Ansuini, Alessandro Laio, Jakob H Macke, and Davide Zoccolan. Intrinsic dimension of data representations in deep neural networks. In Advances in Neural Information Processing Systems, pp. 611 1-6122, 2019.
Franz Besold and Vladimir Spokoiny. Adaptive manifold clustering. 1rXiv:1912.04869 2019.
arXiv preprint
Matthew Brand. Charting a manifold. In Advances in neural information processing systems, pp. 985-992, 2003.
Wieland Brendel and Matthias Bethge. Approximating cnns with bag-of-local-feature models works surprisingly well imagenet. arXiv preprint arXiv:1904.00760, 2019.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. arXiv preprint arXiv:1809, 1106, 2018
Gunnar Carlsson, Tigran Ishkhanov, Vin de Silva, and Afra Zomorodian. On the local behavior of spaces of natural images. International Journal of Computer Vision, 76(1):1-12, 2008
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 245-255. leee, 2009.
Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 29(6):141-14,, 2012.
Mathieu Desbrun, Mark Meyer, and Pierre Alliez. Intrinsic Parameterizations of Surface Meshes.
Computer Graphics Forum, 2002.
David I.. Donoho and Carrie Grimes. Image manifolds which are isometric euclidean space.
Journal of Mathematical Imaging and Vision, 23(1):5-24, 2005.
Elena Facco, Maria d' Ericco, Alex Rodriguez, and Alessandro Laio. Estimating the intrinsic dimen-
sion of datasets by a minimal neighborhood information. Scientific Reports, 7(1):12140, 2017.
Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4))933-104, 2016.
Imola K Fodor. A survey of dimension reduction techniques. Technical report, Lawrence Livermore National Lab., CA (US), 2002.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis. Matthias Bethge, Felix A Wichmann, and Wieland Brendel. Imagenet-trained cnns are biased towards texture; increasing shape bias im- proves accuracy and robustness. arXiv preprint arXiv:1811.12233 2018.
Marina Gomtsyan, Nikita Mokrov, Maxim Panov, and Yury Yanovich. Geometry-aware maximum likelihood estimation of intrinsic dimension. In Asian Conference on Machine Learning, pp- 1126-1141, 2019.
Sixue Gong, Vishnu Naresh Boddeti, and Anil Jain. On the intrinsic dimensionality of image representations. In Proceedings of the IEFE Conference Computer Vision and Pattern Recog- nition, pp. 3987-3996, 2019.
Francisco Gonzalez and Macicj Balajewicz. Deep convolutional recurrent autoencoders for learn- ing low-dimensional feature dynamies of fluid systems. arXiv preprint 1808..1808.000 0888.003446 2018.
10

---

Published as a conference paper at ICLR 2021
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Daniele Granata and Vincenzo Camevale. Accurate estimation of the intrinsic dimension using graph distances: Unraveling the geometric complexity of datasets. Scientific reports, 6:31377, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Geoffrey E Hinton and Ruslan R Salakbutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-577, 2006.
W. Ronny Huang, Zeyad Emam, Micah Goldblum, Liam Fowl, Justin K. Terry, Furong Huang, and Tom Goldstein. Understanding generalization through visualizations, 2019.
Jisu Kim, Alessandro Rinaldo, and Larry Wasserman. Minimax Rates for Estimating the Dimension of a Manifold. Journal of Computational Geomerry, 10(1), 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. University of Toronto, 2009. Master's thesis.
Daniel C. Laughlin. The intrinsic dimensionality of plant traits and its relevance to community assembly. Journal of Ecology, 102(1): 102(1):186-19))) 2014.
Ann B. Lee, Kim S. Pedersen, and David Mumford. The nonlinear statistics of high-contrast patches
in natural images. International Journal of Computer Vision, 54(1):83-103, 2003.
Elizaveta Levina and Peter Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in neural information processing systems, pp. 777-784, 2005.
Tsung-V Yi Lin, Michael Maire, Serge Belongie, James Hays, Pictro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft COCO: Common objects in context. In European conference on computer vision, pp. 740-755. Springer, 2014.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pp. 3730-3738, 2015.
David J.C. MacKay and Zoubin Ghahramani. Comments on 'maximum likelihood estimation of intrinsic dimension' by e. levina and p. bickel (2004), 2005. URL URLhtttp//www inference.
org. uk/ at///acaa///mmensiia.
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In Advances in neural information processing systems, pp- 1786 2010.
Hariharan Narayanan and Partha Niyogi. On the sample complexity of learning smooth cuts on manifold. COLT, 2009.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. URL http::/ufldd stanford... edu housenumbers. .df
hou.senumeers/nip2000
Bruno A Olshausen and David J Field. Natural image statistics and efficient coding. Computation Neural Systems, 7(2):333-333) 1996.
Network:
Gabriel Peyré. Manifold models for signals and images. Computer Vision and Image Understanding. 113(2):249 260, 2009.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290(5500) 2000.
Daniel L Ruderman. The statistics of natural images. Network: Computation in Neural Systems, (4):517-548, 1994.
11

---

Published as a conference paper at ICLR 2021
Arthur Sard. The measure of the critical values of differentiable maps. Bulletin of the American Mathematical Sociery, 48(12):883 890, 1942.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as kernel eigenvalue problem. Neural computation, 1065):129--1399 1998.
David Stutz, Matthias Hein, and Bernt Schiele. Disentangling adversarial robustness and generaliza- tion. In JEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society, 2019.
Joshua Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319-22333 2000.
Jonathan Vacher and Ruben Coen-Cagli. Combining mixture models with linear mixing updates:
multilayer image segmentation and synthesis. arXiv preprint arXiv:1905.10629 2019.
Jonathan Vacher, Aida Davila, Adam Kohn, and Ruben Coen-Cagli. Texture interpolation for prob- ing visual perception. arXiv preprint mrxXi:20006606698, 2020.
Mario Valle and Artem R. Oganov. Crystal fingerprint space - novel paradigm for studying crystal- structure sets. Acta Crystallographicca Section A, 66(5):507-517, 2010.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and
Léon Bottou. Stacked denoising autoencoders: Learning useful representations in deep network with a local denoising criterion. Journal of machine learning research, 11((2), 2010.
Wei Zhu, Qiang Qiu, Jiaji Huang, Robert Calderbank, Guillermo Sapiro, and Ingrid Daubechies. LDMNet: Low dimensional manifold regularized neural networks. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018
12

---

Published as a conference paper at ICLR 2021
A VALIDATION OF ID ESTIMATES
In this section, we present additional discussion results and discussion relevant to the ID estimation and related validation experiments in Section
A.1 GAN PROPERTIES
We devise method for validating ID measurements in controlled setting using images generated by GANS. To justify this method, we first note that the image of R under locally Lipschitz function can be manifold with dimension at most d. Then, consider that the BigGAN generator, convolutional neural network with ReLU activations, is a function with this property (Brock et al. 2018
Specifically, BigGAN can be written as a composition of linear functions, translations, and ReL.U activation functions. Individually, these operations do not increase dimension, and by a composition property, their composition cannot increase dimensionality either. The more general fact that the image Rdd under a locally Lipschitz function can be manifold with dimension at most d follows from Sard's theorem Sard 1942).
A.2 CONVERGENCE FOR MORE GAN CLASSES
We include additional results on the estimation ID for synthetic GAN images from various Ima- geNet classes with d 10 free entries out of the 128-dimensional latent vector input the GAN; see Figures [0] and [1 below. As observed earlier in Section 4 the MLE estimates are sensitive to the choice k, where we expect the ID be close given the way we sample the latent vectors to use for the GAN. We note that for number of classes, all choices of ls we considered seem to underestimate the II).
Dimensionality Estimate
11
k=3
10
k=5
k=10
k=15
k=20
k=25
250
500
750
1000
1250
1500
1750
2000
Number of Samples
Figure 9: Validation of MLE estimates synthetic daisy data with d 10.
A.3 SUBSAMPLING FOR LARGE DATASETS
In Figure 12 we validate the anchor approximation on basenj i data of dimension 10 for varying anchor ratio a. Then, in Figure 13 we validate the anchor approximation tree-frog data with = 32 for varying while fixing the anchor ratio at a = 0.001.
A.4 RELATIONSHIP BETWEEN & IN THE MLE METHOD AND DATASET DIMENSION
The choice of & may affect the dimensionality estimates. To better understand this relationship, we conducted additional studies for the MLE method using synthetic GAN data generated as described in Section 4 Table 5 shows the estimation results for various and basenji data with d e {2, 8, 16. 32, 64, 128 We use fixed number of samples (n 10000). We observe that the estimated intrinsic dimension increases with k. and large values can yield overestimates for ID. These results agree with the work of Levina & Bickel (2005) who suggest that low values of & may
13

---

Published as a conference paper at ICLR 2021
3=3
Dimensionaliy, Estimate
k=4
10
k=5
k=10
k=
2=
250
500
750
1000
1250
1500
1750
2000
Number Samples
Figure 10: Validation of MLE estimate on synthetic soap-bubbles data with d = 10.
k=3
Dimensionality Estimate
k=4
10
k=5
k=10
15
k=20
k=
250
500
750
1000
1250
1500
1750
2000
Number Samples
Figure 11: Validation MLE estimate on synthetic co fee with 10 entries. Note that estimates do not converge around the upper bound of 10, which suggests that data generated from this class is not of full dimension.
produce estimator with higher variance while higher values of l produce estimator with higher positive bias. Given that we have access to large amounts of synthetic data, we opt for lower values of k in our work. We do choose particular value of and we report all experiments with multiple values.
a=1.000
Dimensionalit Estimato
a=0.500
12
==0.200
a=0.100
00000
10
250
500
750
1000
1250
1500
1750
2000
Number Samples
Figure 12: Validation of anchor approximation on basenji with 10.
14

---

Published as a conference paper at ICLR 2021
Dimensionally aallyyy Estimate
30
k=3
k=4
20
k=
k=10
15
k=15
k=
10
25
1000000
1200000
1400000
1600000 1800000
2000000
Number Samples
Figure 13:
Validation of anchor approximation on tree frog with d 32 and a 0.001.
k
d
2
4
8
16
32
64
128
3
1.1
2.6
6.1
10.5
16.0
20.0
20.0
4
1.5
3.6
8.2
14.0
21.0
26.0
26.0
5
1.7
4.1
9.3
15.7
23.5
28.7
28.5
6
1.8
4.4
9.9
16.6
24.9
30.3
29.9
7
1.9
4.6
10.4
25.8
31.2
30.6
8
1.9
4.7
10.7
17.6
26.4
31.7
31.1
9
2.0
4.9
10.9
18.0
26.8
31.9
31.5
10
2.0
5.0
11.1
18.2
27.1
32.1
31.7
15
2.1
5.3
11.6
18.8
27.8
32.3
31.7
20
2.2
5.5
11.8
19.0
27.9
31.9
31.3
25
2.2
5.7
12.0
19.2
27.9
31.5
30.8
Table 5: Additional results on the relationship between MLE dimensionality estimate synthetic basenji images with varying d.
A.5 COMPARING MLE TO OTHER ESTIMATORS IN CONTROLLED SETTING
To validate MLE in comparison to other estimators, evaluate three other dimensionality esti- mation methods: GeoMLE (Gomtsyan et al.) 2019), TwoNN (Facco et al.] 2017) and kNN graph distances (Granata & Carnevale, 2016). For GeoMLE, sample total of 20 bootstrap subsets (M 20) and use ki = 20, K 55 as recommended by Gomtsyan et al. (2019). To extend the kNN graph distance method to large datasets, we randomly sample a subset of samples (fixed to 10,000 for datasets with more than 10,000 samples) and use shortest graph distances to their & near- est neighbors estimate the IDs. Other settings are as default in the implementations of Granata &
Carnevale (016)).
First, we validate each method on datasets of uniformly sampled from d-dimensional hypereubes. We report these results in Figure [4] Each method works reasonable on low Now-dimensional cubes. We observed the Shortest Path method to give erratic estimates on cubes of higher dimension, and have omitted these. TwoNN has poor sample efficiency for higher dimensional cubes. Interestingly, GeoMLE estimates these high dimensional cubes well.
Next, report estimation results on basenjj-_l for TwoNN, kNN graph distance, and GeoMLE methods Figure [5] Comparing against the MLE results in Figure 3 we observe that each other method does not achieve accurate estimate in this sample regime, thus motivating focus on MLE. Notably, GeoMLE and TwoNN severely overestimate dimension, while the kNN graph distance method severely underestimates dimension.
On MNIST, CIFAR-10 10, SIFAR-100. and SVHN, the results of these other estimation methods also deviate from expectation (Table 6). For example, TwoNN assigns significantly higher dimension
15

---

Published as a conference paper at ICLR 2021
estimate MNIST than to CIFAR-100 100, which contradicts both intuition and the results of other estimators. We set and number of bins to 1000, and use default settings for all other parameters including MAX.-
TwoNN Estimates on d-Hybercubes
Dimensimalliy Estimate
50- d=
40 6:
30
10
10000
20000
30000
40000
50000
Number of Samples
Shortest- Poortest-Paahhe Estimates d-Hybercubes
d=2
Dimensionsllty Estimate
30
d=8
25-
d-16
15-
10
2000
4000
6000
8000
10000
Samples
GeoMLE Estimates d d-Hbbercubes
80
dd2
limensiorality Estimate
70
60
16
50
d-
d=
40
30
20
10
2000
4000
6000
8000
10000
Number of Samples
Figure 14: The TwoNN, Shortest Path, and GeoMLE methods on d-dimensional Hypercube data. Each method estimates low-dimensional cubes well, validating their implementation.
Dataset
MNIST CIFAR-10
CIFAR-
SVHN
MLE 5)
21
18
14
GcoMLE (k) = 20,k2 55)
96
93
TwoNN
15
11
9
kNN Graph Distance
7
7
8
Table Additional estimators on popular datasets.
16

---

Published as a conference paper at ICLR 2021
TwoNN Estimates on basenji 10
Dimensionaliy Estimate
14-
13-
12-
10
250
500
750
1000
1250
1500
1750
2000
Number Samples
Chortest-Path Estimates on basenji 10
14
Dimensionality Estimate
12
10
4-
250
500
750
1000
1250
1500
1750
2000
Number of Samples
GeoMLE Estimates on basenji
80
Dimencionaltty Eetimate
70
10
30
20
10
250
500
750
1000
1250
1500
1750
2000
Number of Samples
Figure 15: The TwoNN, Shortest-Path, and GeoMLE methods on basenji. ]i_10 data. The esti- mates do not converge around the expected value of d 10 in this sample regime.
17


Reviews:
[{"review_id": "gscnZknTqwA", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nStrength:\n\nI 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. \n\nWeaknesses:\n\nMy 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:\n\n1. 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?\n\n2. 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? \n\n3. 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. \n\n4. 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]?\n\na. Maximum Likelihood Estimation of Intrinsic Dimension, 2004\nb. Estimating the intrinsic dimension of datasets by a minimal neighborhood information, 2017\nc. Local Intrinsic Dimensionality I: An Extreme-Value-Theoretic Foundation for Similarity Applications, 2017\nd. Dimensionality-Driven Learning with Noisy Labels, 2018\ne. CHARACTERIZING ADVERSARIAL SUBSPACES USING LOCAL INTRINSIC DIMENSIONALITY, 2018\n\nOverall, 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. \n\nMinor comment:\n\n- 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. \n\n- Fig. 3 is not color blind friendly, maybe consider using different line types. \n\n- Sec. 5, first line: establish -> established\n\n\n**Update after rebuttal** \n\nI 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. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "SPHoj_xdLXu", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "== Summary ==\n\nThe 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 \n\n== Pros ==\n\n- 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. \n\n- 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. \n\n- 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).\n\n- I also find interesting the experiments in section 5.2, which studies the (inverse) correlation between intrinsic dimension and generalization (i.e. test accuracy). \n\n== Cons ==\n\n- 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).\n\n- 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.\n\n- 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).\n\n- 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.\n\n- 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). \n\n- 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.\n\n- 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)?\n\n== Rationale for the score ==\n\nAlthough 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.\n\nI hope that the authors can address my questions/concerns during the rebuttal to increase my score.\n\n*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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "OK53E1yTD0H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Review\n\n### Summary\n\nThe paper proposes an empirical analysis of the dimension of natural images of multiple datasets.\nThe contributions are:\n1. A validation for nat. im. of previously proposed dimension estimation methods (using GAN to control the intrinsic dimension of the generated im.)\n2. A confirmation that intrinsic dimension of nat. im. is lower than the dimension of their pixel space\n3. That the lower the intrinsic dimension the easier the learning (for neural net)\n\n### Strengths\n\n* The paper is well-written and easy to follow. \n* The data analysis pipeline is convincing.\n* Up to my knowledge there is no such a clear statement about the dimension of natural image \n\n### Weaknesses\n\n* 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). \n\n### Minor comments\n\n* None\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-GLhzawIsF", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe 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.\n\nI 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, \n\n\n\n*Review\nPros include:\ninnovative use of GANs to generate synthetic data of bounded intrinsic dimension\nwell written and easy to read\ncoherent story\n\nCons:\nlimited analysis and discussion of the role of the image class (particularly in ImageNet) on the MLE estimate of intrinsic dimension\nSome details not listed in the paper, including the metric for the distance between images used to compute the MLE ID estimate\nNon-sequitur in the analysis of the role of image extrinsic dimension in classifier generalization; see comments below.\n\n\nIn 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.\n\n>>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.\n\nIn 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.\n\n>>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.\n\nIn 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.\n\n>>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.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)