Slice, Dice, and Optimize: Measuring the Dimension of Neural Network Class Manifolds
Authors: Stanislav Fort
Ekin Dogus Cubuk
Surya Ganguli
Samuel Stern Schoenholz
Venue:  (2021)
Keywords: input space
random hyperplane
optimization
robustness
dimension
codimension
manifold

Abstract: Deep neural network classifiers naturally partition input space into regions belonging to different classes. The geometry of these class manifolds (CMs) is widely studied and is intimately related to model performance; for example, the margin is defined via boundaries between these CMs. We present a simple technique to estimate the effective dimension of CMs as well as boundaries between multiple CMs, by computing their intersection with random affine subspaces of varying dimension. We provide a theory for the technique and verify that our theoretical predictions agree with measurements on real neural networks. Through extensive experiments, we leverage this method to show deep connections between the geometry of CMs, generalization, and robustness. In particular we investigate how CM dimension depends on 1) the dataset, 2) architecture, 3) random initialization, 4) stage of training, 5) class, 6) ensemble size, 7) label randomization, 8) training set size, and 9) model robustness to data corruption. Together a picture emerges that well-performing, robust models have higher dimensional CMs than worse performing models. Moreover, we offer a unique perspective on ensembling via intersections of CMs. Our core code is available on Github (link in the PDF abstract).

Under review as a conference paper at ICLR 2021
SLICE, DICE, AND OPTIMIZE: MEASURING THE DI- MENSION OF NEURAL NETWORK CLASS MANIFOLDS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep neural network classifiers naturally partition input space into regions belong- ing to different classes. The geometry these class manifolds (CMs) is widely studied and is intimately related to model performance; for example, the margin is defined via boundaries between these CMs. We present a simple technique to estimate the effective dimension of CMs as well as boundaries between multiple CMs, by computing their intersection with random affine subspaces of varying dimension. We provide theory for the technique and verify that our theoretical predictions agree with measurements on real neural networks. Through extensive experiments, we leverage this method to show deep connections between the ge- ometry of CMs. generalization, and robustness. In particular we investigate how CM dimension depends on 1) the dataset, 2) architecture, 3) random initialization, 4) stage of training. 5) class, 6) ensemble size, 7) label randomization, 8) training set size, and 9) model robustness to data corruption. Together picture emerges that well-performing, robust models have higher dimensional CMs than worse performing models. Moreover, we offer a unique perspective on ensembling via intersections of CMs. Our core code is available Github.
INTRODUCTION
Training neural networks to classify data is a ubiquitous and classic problem in deep learning. In K- way classification, trained networks naturally partition the space of inputs into K regions, Ss. C R.D
X Dropss
Aon Bresticase
short divections
1.0
probectity
0.5
dranciist Drpee
0.6
daaaateld
0.44
Rt
0.2
dis 188
Intersection
Nove
co12)
BM + Xo
Random cutting plane
dest
10P
Curting plane dimerston
SGD trajectory
recchd
be in Ve.
Target lnss
27.0 277
10)
X
6
Target manifold
{x st. NN (X) [horse] 2 0.90
10a Curting plane dimersion
Figure 1: An illustration of finding point in the intersection between a random cutting plane of dimension deut and a high-confidence manifold of effective dimension dmauiffld-- If the deut 2o Disput dmanifold, there likely exists an intersection between the two. We use optimization from a random point (image) X on the deut. affine subspace to find point in the intersection using gradient descent. The panels on the right show an example of the dependence of the probability and loss at the optimized point based on the deut- The higher dimensional the cut, the less constrained the available images X are, and the more likely we are to find one of high class confidence.
containing points that the network confidently predict have class k. We call these regions class manifolds (CMs) of the neural network. In this paper, we analyze the high high-dimensional geometry of these CMs, focusing primarily on their effective dimensionality.

---

Under review as a conference paper at ICLR 2021
To estimate the dimension of these CMs, employ optimization on random d-dimensional sec- tions of inputs space to beat the curse of dimensionality (Bellman, 1957) in order to seek out high- confidence regions that would be unlikely to be discovered at random with other diagnostic tech- niques. Through a theoretical analysis of high-dimensional geometry we link the success of such constrained optimization to the dimension of the target CMM. Also, through extensive experiments, we leverage this method to show deep connections between the geometry of CMs, generalization, and robustness. In particular we investigate how CM dimension depends on 1) the dataset, 2) ar- chitecture, 3) random initialization, 4) stage of training, 5) class, 6) ensemble size, 7) training set size, and 8) model robustmess to data corruption. Together a picture emerges that well-performing. robust, models have CMs that have higher dimension than inferior models. Moreover, we offer unique perspective on ensembling via intersections of CMs.
3
Oker
6.4
0.2
42--225222 22.5222
217221
Bubscell
Boboreff
Clves
Obece
Clyer
Clycc
Nov pon werten
3.0
12
152-13
522
13 1..
C.tting pans dimandon
cuesing plano dimenntos
Cutting pane dimendion
cutting place Simencion
Cutting plane dimeraton
Figure 2: Maximum probability of single classes of CIFAR-10 10 reached on cutting planes of dimen- sion d. The figure shows the dependence of the probability of single class of CIFAR-10 (y-axes) reached on random cutting hyperplanes of different dimensions (x-axes). The results shown are for a well-trained (> 90% test accuracy) ResNet20v1 on 100. Each dimension d is repeated 10x with random planes and offsets, and d50% is extracted using a fit. The d50% < 3072, which implics that the class manifolds are surprisingly high dimensional (3072- d50%) ). Indeed their dimensions are all in excess of 3000.
Related work. There has been a lot of research into understanding linear regions of neural networks, both trained and untrained. Montúfar et al. (2014) studied the number of linear regions in deep neural networks, Raghu et al. (2016) looked at their expressive power with depth, while Serra et al. (2017) tried to bound and count them. Hanin & Rolnick (2019b) showed that deep ReLU networks have surprisingly few activation patterns, and Hanin & Rolnick (2019a) did the same for the linear regions in the input space. The spectral properties of neural nets were studied in Rahaman et al. (2018), and the stiffneess of the functional approximations defined through gradient alignment was coined in Fort al. (2019). While revealing interesting aspects of neural network input space and activations space behavior, the methods used so far have not been able beat the curse of dimensionality - they have stayed local, and analyzed either one- or two-dimensional sections of input space.
The exploration of constrained optimization on random, d-dimensional planes in the weight space was employed successfully in Li al. (2018) estimate the intrinsic dimension of loss landscapes. Fort & Scherlis (2019) extended this analysis geometrically, and Fort & Jastrzebski (2019) used this and several other insights to build a geometric model of the low-loss basins weight-space basins.
Another closely related area of research concerns adversarial examples and robustness. Goodfel- low et al. (2014) first noted that there exist points input space very close to test examples that are mispredicted by neural networks, suggesting CMs of different classes can come very close to each other. Gilmer et al. (2018) showed that the existence of adversarial examples is related to the dimensionality of input space and the accuracy of the classifier. Ford et al. (2019) further link this interplay between dimensionality, generalization, and adversarial robustness to more general corrup- tion robustness. In similar spirit Salman et al. (2019) produce more robust models by convolving neural networks with Gaussian noise in input space. Whereas these studies are local, the techniques discussed in this paper primarily concerned with global properties of CMs.
2

---

Under review as a conference paper at ICLR 2021
2
METHODS
We seek to determine the effective dimensionality of CMs. To that end, consider neural networks whose last layer is softmax yielding normalized probabilities for given input, p(X). Typically these networks have been trained using cross entropy loss,
((p(X). P) = -p (p-oogp((X))
(1)
We define a class manifold for class is as the pre-image, Sy = = ((px > Pthreshold ). We seek to identify the effective dimension of Sn by introducing the cutting plane method (see also Fig. 1):
The Cutting Plane Method: For a neural network (NN) mapping input X E R. into probabilities (XX) E RC take a random d-dimensional affine hyperplane defined by orthonormal basis vectors given by rows of M E Rax D and point Xo E IR Inputs in this hyperplane are parametrized by 0E Hd as (0) 0M Xo. Given target probability vector Piarget. we seek to optimize the cross entropy loss, ((p(X(0)) Plarget) with respect 6. This will identify points constrained the affine subspace (M, Xo) that have probabilities as close as possible to Prarget. We study the dependence of Cmin and Pmin (the loss and probability following optimization) on the dimension d. We show this analysis estimates the effective codimension of the preimage of Ptarget: {X s.L. (X) = Ptarget
We use Adam (Kingma & Ba, 2017) to minimize L with respect to 0, starting from 0, = O, which corresponds to an initial random input X {(6) Xo. Through optimization, we take 0o - Ōmin- The Mmin defines an optimized input Xmin mmin M + Xo and corresponding output Prinal (X) that is as close as possible to Prarget while confining X to the random affine hyperplane defined by (M, Xo). We discuss the weak effect of sparsity of M in 11.
The optimization thus starts with tuple (NN, d, M, Xo) and maps it to the final probability vector Pinal and the associated Linal- By analyzing the dependence of Piiall and Cinal on the dimension d of the random hyperplane pre-image in input space of a region around Prarget in output space (Fig. 1).
access information about the effective dimensionality of the
2.1 CLASS MANIFOLDS (CMS) AND MULTI-WAY WAY CLASS BOUNDARY MANIFOLDS (CBMs)
There are several interesting choices of Plarget. Consider Prarget = (0, 0,...,,............. 1,...,,,.0 0), or a 1-hot vector on single class k. Then the pre-image of Prarget is the CM Sg. The cutting plane method enables us to estimate the effective co- oo-dimension of Sy by computing the dimension d' at which we reliably obtain Pfinll whose k' tt component is close
within some tolerance (Fig. 2).
The formulation in Equation allows us to also study regions that lic in between classes. For example, by setting Ptarget (2) 2, O,......,, 0), our optimization finds regions of input space that lie on a class boundary manifold (CBM) between classes and 1. We can even find multi-way CBMs. For example, a three-way CBM between classes 0,1, and corresponds to Pearget 3: 33 O,...,0) 0). We can also study the region where all classes have equal probability by set- ting Prarget ( 1 ......,)))) t) ..... to study the intertwined geometry of multiple CMs and their boundaries. See Fig. 6 for results on multi-way CBMs.
where C' is the number of classes. Thus our method opens the door
2.2 EXTRACTING THE CRITICAL CUTTING PLANE DIMENSION AND CM CO-DIMENSION d50%%
Given a particular class target vector Piarget (i.e. Prarget = O1, 0) corresponding to the CM Se with k 1), we perform the cutting plane experiment multiple times for random X, and M for a sweep of different values d. We obtain a final probability vectors Pmin as a function of cutting plane dimension d, shown in Figures I and 2. For CMs for single class manifold S% we plot the k'th component Pmin- For small values of d the affine cutting plane will not often intersect Sy and Pmin will be far from Ptarget. For large dimensions, e.g. d = D, the subspace is now the full space of inputs, and we can therefore always find a point on the plane such that Pmnin Rs Prarget- For intermediate values of d, the k 'tt component of pmin will gradually increase with d. To extract
3

---

Under review as a conference paper at ICLR 2021
single cutting plane dimension from this data 1) fit an empirical curve to the data (Equation 6; typically a good fit), 2) use the resulting distribution fit parameters' mean and covariance to get set of valid fitting functions, and 3) extracting the range of values of d' where these functions cross p = 50%. We call this value d50%- (In some cases, we use other probability thresholds (25% and 75%) and we note that the figures.) This cutting plane dimension the effective co-dimension of the CM Sg. Thus the effective dimension of the CM Sy is D d" (as derived in Section 3).
3 A THEORY FOR ESTIMATING CM DIMENSION THROUGH CUTTING PLANES
Here we provide justification for the idea that d50% obtained through the cutting plane method actu- ally estimates the effective co-dimension of the CM Sy (or multiway CBMs), by analyzing what
Dimpat = 2
D Dimpus =3
D iipput = 3 dent
D imput = 3
deut 1
deut =
deut 2
dmanifold
dmanifold
=
Amaniffld
d manifoll 2
Figure 3: An illustration of the way affine subspaces of dimensions da and dg intersect each other. If the dimension of the space d + dB 2 D, the subspaces will likely intersect, while otherwise they typically do intersect. If know D and dA, we can use the existence of an intersection tool to bound dg 2 D dA-
the cutting plane method would yield for simple model of the CM affine hyperplane itself. To understand the relationship between the cutting plane dimension d50% and the CM hyperplane dimension, need to review the intersection theory of random affine hyperplanes.
3.1 INTERSECTION THEORY OF TWO RANDOM HYPERPLANES
For two hyperplanes (affine subspaces) of dimensions dA and dg that are randomly oriented and offset in ambient vector space of dimension D. what is the condition their dimensionalities that would make it highly likely that they intersect? The answer is
d + dp 2 D.
(2)
In algebraic geometry, this statement is known as dimension counting, and is equivalent to the state- ment that the co-dimensions of hyperplanes are at most additive under intersection (Bourbaki, 1998) (recall that the co-dimension of hyperplane of dimension d in a space of ambient dimension D is
D d). More precisely,
max(codim (A), codimod)))))) B)) S codim(A n B) S (A4) + codim(B).
Rewritten in dimensions, this means that D dim n B) lies between D min(dA, dp) and D (d, + dg). For the subspaces A and B intersecting transversally, which happens generically, the codimensions add exactly, satisfying the upper bound and therefore leading to Equation 2. illustration of what such intersections can look like for D = 2 and D) 3 are shown in Figure 3.
In the cutting plane method, we control the dimension d of a randomly chosen cutting hyperplane and use constrained optimization to find an intersection of this hyperplane with CM in order to estimate its dimension dn. The dimension da d500% where we can first reliably find a high confidence image of the target class will be the codimension of such CM. The dimension of the CM will therefore be dg = these results yield the exact dimension dg of the CM when it is hyperplane of dimension dg- However for more general CM's, the estimated d. D di00% is to be interpreted as an effective dimension of the CM and d5,0% itself is the effective co-dimension of the CM.
d5u%. Based on the intersection theory of random hyperplanes,
3.2 THEORY VS NUMERICAL EXPERIMENT
In Section A.2 we analytically derive the expected closest distance between two such affine subspaces. The result is the for dA + da 2 D it is O (they itersect),
4

---

Under review as a conference paper at ICLR 2021
while for dA + dg D the B]( this analytic result to reality, we ran numerical experiment using automatic differentia- tion in JAX (Bradbury al., 2018) where generated random affine subspaces of dif- ferent dimensions and measured their closest approach using optimization to locate the place. The numerical results presented in Figure 4 match the analytic predictions well.
To compare
Space D 1000. target n 500
3.3 LONG AND SHORT DIRECTIONS RELATING THEORY TO EXPERIMENTS
(Fima) (Pinal dizancce tatareet
0.10
Experiment
Fitn" - 857.0 Thwory
0.08
0.06
A hyperplane of dimension d has infinitely extended directions and D d directions of size O. Among the extended dimensions, we can move arbitrarily far and still find ourselves in the hyperplane. Conversely moving even infinitesimally in the remaining D-d directions will strictly lead leaving the plane. In our experiments, this will be the case only approximately. In case of class man- ifolds, no directions will be infinitely thin or long, how- ever, many will be much thinner than others. What we are measuring is therefore not strictly a dimension (the man- ifold will always have the full dimension D) but rather effective dimension (Vershynin, 2015). However, our hy- perplane model works well in practice.
0.02
0.00
25
50
75
100 325
Cutting plane dimensiond
Figure 4: Distance between random affine subspaces numerical experi- ments theory from Eq. 4. The fig- ure compares the distance between two subspaces of dimensions d & n in a D- dimensional space. The numerical ex- periment in JAX is in blue, theory in red, and numerical fit in yellow.
4 EXPERIMENTS
We now describe experiments validating our random cutting plane method of identifying the dimension of CMs and connections be- tween these measurements, generalization, and robustness. The details of the architectures, datasets and precise training procedures are de- tailed in the Appendix Section 1. The major- ity of our experiments are done with a standard ResNet20v1 on CIFAR-10 and CIFAR-100.
soreere 1000 from mor2
200
Part den
10
10
20 30
10
4.1 RE-INITIALIZATION
Figure 5: Left panel: Comparison of the cutting plane dimension needed to get 50% of the target class (d for two independently initialized and trained ResNets on CIFAR-10, showing the stabil- ity of our method. Right panel: Comparison of the d00z for SimpleCNN and ResNet on CIFAR- 10 and CIFAR-100 100 with real and randomized la- bels.
AND RE-TRAINING STABILITY
For our technique to have predictive power, cut- ting plane results should be stable under reini- tialization and retraining of a model. Given fully trained model, running a sweep over cutting plane dimension d several times should produce consistent results. We verified that our method is stable, shown in Figure 5 where compare the 150% dimensions extracted from single class regions of CIFAR-10, as well several regions between 2, 3 and 4 classes. The results consistent between the two runs.
4.2 SINGLE CLASS MANIFOLDS
The main object of interest for us are the high-confidence single class manifolds. We present our results for well-trained ResNet20v1 on CIFAR-10 in Figure 2, and for CIFAR-100 in Figure 18. We also show results for a SimpleCNN on CIFAR-10 in Figure 17. The results show that the d50% is very small compared to the dimension of the input, suggesting that the class manifold dimension is actually very high, close to the full 3072 dimensions for CIFAR- 10. The connection between d' and the manifold dimension is derived in Section A.2.
5

---

Under review as a conference paper at ICLR 2021
4.3 CLASS BOUNDARY MANIFOLDS BETWEEN MULTIPLE CLASSES
As described in Section 2.1, our method allows us to study the dimensionality of boundary manifolds in between multiple classes as well. We show results for a well trained ResNet20v1 on CIFAR- 10 (> 91% test accuracy) for several selected sets of classes in Figure 6. In particular, we look at the region between all 10 classes, where the network is equally uncertain about all classes. There, we
primarily focus the loss (as described in Equation 1) in the bottom row of Figure 6
Data
0.5
0.5
2.5
0.5
fl:
Dat
0.6
Dat
3.2
6o
0.0
0.0
0.6
0.0
4.0
3.75
1gg21
Nin logid)
legit)
loge2)
3.50
Data
Dats
Eata
2.15
2.0
100
1300
100
10
1000
100
150
1092
Cutting plare dimersoon
Cutting (lare Simersion
Outting plane dimerzion
CLeSTn plano dinercios
Cutting poine dimensiin
Figure 6: Maximum probability and minimum loss (y-axes) of in-between-classes regions of CIFAR-10 reached on cutting planes of dimension d (x-axes). The results shown are for a well- trained (> 90% test accuracy) ResNet20v1 on CIFAR-10. Each dimension d is repeated 10x with random planes and offsets. The last column shows the results for the 10-class region where the network assigns equal probability to each class.
4.4 TRAINING ON RANDOM LABELS
Due to the structure of the training data and the neural network prior, we expect the learned class manifolds to inherit a lot of structure from both. To disentangle the role of the class label, we trained a ResNet20v1 on CIFAR- 10 with randomly reshuffled labels. As shown in Zhang et al. (2017), we can reach 100% training accuracy on random labels. However, shown in Figure 5 and 12 the CMs learned in such way have a significantly higher d50% and therefore smaller dimension. Since these models completely fail to generalize, this result is consistent with the hypothesis that generalization and class manifold dimension are intimately related.
4.5 THE EFFECT OF TRAINING SET SIZE
During the course of training, neural network has to learn to partition the D-dimensional space of inputs into generalizable regions of high class confidence that contain both the training points (by training) and the test points (by generalization). To see the role of training set size, repeated our cutting plane experiments for networks trained to 100% training set accuracy on subsets of CIFAR- 10 of size 250, 500, 1,500, 5,000, 15,000, and 50,000 images (=full training set) and added a final point where we used data augmentation on top of the full training set. The bigger the training set, the smaller the doo% and therefore the larger the dimension of the CMs, as shown in Fig. 7. This trend held across all classes, and continued from the full training set to the training set and augmentation. Thus again, better generalization is associated with higher CM dimensionality. We hypothesize that the larger number of training points might allow the learned partitioning of the input space to connect previously disconnected and lower dimensional CMs through interpolation, thereby effectively increasing CM dimensions with training set size.
4.6 THE EFFECT OF DATA CORRUPTION
We measure the effect of cutting plane dimension on out-of-domain robustness of neural networks. Robustness to Gaussian noise was found to be useful predictor for general robustness as well as adversarial robustness (Ford et al., 2019; Yin et al., 2019). For this reason, we first measure the ro- bustness of Wide-ResNet models to Gaussian noise applied at test time, where noise is sampled from a Gaussian with 0.05 standard deviation for each pixel independently. Left panel of Fig. 8 shows the correlation between the cutting plane dimension and error due Gaussian noise, calculated as the accuracy on corrupted data minus the accuracy on clean data. We see that the models with smaller cutting plane dimension, and therefore higher CM dimension, are more robust to this type of noise.

---

Under review as a conference paper at ICLR 2021
Cutting plane Cutting plane
Class
Class 2
Class
10a
Class
10a
10a
10a
10
102
10a
10a
aasss
Class 6
Class 7
10a
Class
Class
10a
10a
102
10a
10a
10
250
5:00
5.59
54
15k
50k
aug
250
500
1.50
5K
15k
50k
aug
250
5.00
1.5k
5K
15k
50K
250
500
1.5
5K
15k
50k
aug
750
15
5
155
50K
aug
Train set size
Train set s20
Train set size
Train set size
Train set size
Figure 7: Comparison of the cutting plane dimension needed to get 50% of the target class for
ResNet trained to 100% training accuracy on subsets of the training set of CIFAR-10 (mean and standard deviation of two networks). The bigger the training set, the smaller the d50% meaning that its easier to find high confidence images, and that their manifolds increase dimension. The trend continues with the addition of data augmentation (aug).
Next, we calculate the correlation between the cutting plane dimension and the accuracy on CIFAR- 10-C (Hendrycks & Dietterich, 2018), which includes different corruption types applied at test time (right panel of Fig. 8). These results together show that the cutting plane dimension of neural networks is correlated with their robustness to a variety of test-time distortions. Again, higher class CM dimension leads to better performance in terms of robustness.
CIFAR-10
CIFAR-10
CIFAR-10
7.0
4.5
4.5
Entrr Euerrduss
4.0
Ereer du contuption
6.5
Enne dua
Coussbin note,
4.0
Enor dut 30
6.5
3.5
6.0
6.0
20
21
22
23
24
22 Cutting plane Alas
21
23
24
29
31 52
29
30
32
Curting NADE dizs
Cutting plane dipe
Curting plane digs
Figure 8: The effect of cutting plane dimension on model robustness to test-time distortions. The left panel shows the error due Gaussian noise applied at test time vs. cutting plane dimension needed to get 50% of the points to target classes 0 and 1. The right panel shows the effect of the cutting plane dimension on error due to corruptions CIFAR-10-C. Models with lower cutting plane dimension are more robust to both Gaussian noise and to distortions in the Common Corruptions Benchmark.
4.7 EVOLUTION OF DIMENSION WITH TRAINING
We study the effect of training on the high confidence manifolds in Figure 9. The early epochs heavily influenced by the initialization. After a small amount of training, there seems to be an intermediate stage when it is very hard to find high confidence class manifolds (dis%, is high, and therefore the manifold dimension is low). Towards the end of training, dis% goes down for all classes (detailed Figures 16, 18 and 17). The non-monotonic behavior of the dimension points towards something unusual happening in the intermediate stages of training, and it could be related to the host of phenomena pointing towards the high impact of early stages of training.
4.8 MODEL ENSEMBLING
We found that model ensembling (taking N independently trained models, giving them the same in- put, and averaging their predicted probabilities) leads to class manifolds of lower dimension, as well as between-class regions of lower dimension. The bigger the ensemble, the lower the dimension, as shown in a summary plot in Figure 10. This is atypical, as all other methods of improving perfor- mance (e.g. larger training set, more training (towards the end)) correlated with higher dimensional CMs. This suggests that ensembles might be doing something geometrically distinct from the other methods. This could be related to the observation that, unlike other techniques, deep ensembles combine models from distinct loss landscape basins Fort et al. (2020).
7

---

Under review as a conference paper at ICLR 2021
Single class regions
Hax by of clss
Mix probabiltyy of class
No5
Eutinn dimention
Cutting mmeestionn
3000
75%
2500
50%
25%
2300
Zo1
1000
25%
1000
25% level
100
0.00
109
6:00
10
0.4
training (epoch)
Stage training (ust
Figure 9: The effect of training the dimension of cutting plane necessary to reach particular probability. The two left panels show the maximum probability of class reached for cutting planes of different dimensions (y-axes) for different stages of training of ResNet20v1 axes). The probability 25% level is highlighted. The right panel shows d25%%; d5p9% and di for the average of all single class regions. We see intermediate stage of training when high confidence regions become hard to find. Towards the end of training, the dimension of the manifolds grows. The breakdown by classes is shown in Figure 16.
CIFAR-10 (x-
Cutting plane dis
1.00
80
60
Eraentl 2
Iranbsus
40
Mean of classes
hepatann
Nalvo
Ensemble size
FELEORT
Foxr 3m13
The effect of model ensembling the dimension 50% needed to reach 50% accuracy averaged over all CIFAR-10 classes (individual results Fig. 13) for ResNet20 trained for 50 epochs. Across all classes, the larger the ensemble, the higher the 550% and therefore the lower the class manifold dimension. A naive model of addition of codimensions between models is overlayed, showing a surprisingly good fit for small ensembles. The right panels show section of the input space for 3 single models (top row) and 3 ensemble sizes (bottom). The colors indicate 4 different classes 50%. The elongated high-probability structures disappear with ensembling.
Figure 10:
5 CONCLUSION
We propose a new method for estimating the dimension of both class manifolds and multi-way class boundary manifolds in the space of inputs for deep neural neural networks. To circumvent the curse of dimensionality, we use optimization constrained to randomly chosen affine subspaces (hyperplanes) of varying dimension. This allows us to extract the effective dimension of the class manifolds as well regions between classes. We study the manifold dimension as function of 1) architecture, 2) dataset, 3) the amount of training, 4) dataset size, 5) data augmentation, 6) label randomization, 7) robustness to noise and perturbations, and 8) ensemble size. The ubiquitous correlation between higher class manifold dimension and better performance and robustness along the many axes tested points towards an intimate link between the geometry of the input space class partitioning and generalization. Ensembling, decreases the manifold dimension, and is the only technique amongst the ones we explored that does so, suggesting that its beneficial effects might be geometrically distinct from other ways of improving performance.
the other hand, both increases performance and
Overall the development of full theory of deep learning poses a difficult intermediate theoretical problem: understanding the shape and evolution over training of complex nonlinear maps from high D-dimensional imput spaces to high C-dimensional class probability spaces. By slicing, dicing and optimizing such high dimensional nonlinear maps using our cutting plane method, we hope our work opens the door to developing a more veridical geometric perspective on the nature of nonlinear maps leareed by deep neural network classifiers.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Richard Bellman. Dynamic Programming. Dover Publications, 1957. ISBN 9780486428093.
N. Bourbaki. Algebra I: Chapters 1-3, Actualités scientifiques et industrielles. Springer, 1998. ISBN 9783540642435. URL https:ttpp... pttttts::/bookee /books googl e cttbbookks1111015992222000000000
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman-Milne. JAX: composable transformations of Python+NumPy programs, 2018. URL http: com/ google/jax.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation policies from data. arXiv preprint arXiv:/805.09501, 2018.
Deng, Dong, R. Socher, L.-J. Li, Li, and L.. Fei-Fei. ImageNet: Large-Scale Hierarchical Image Database. In CVPR09, 2009.
Nic Ford, Justin Gilmer, Nicolas Carlini, and Dogus Cubuk. Adversarial examples are natural consequence of test error in noise, 2019.
Stanislav Fort and Stanislaw Jastrzebski. Large scale structure of neural network loss landscapes, 2019.
Stanislav Fort and Adam Scherlis. The goldilocks zone: Towards better understanding of neural network loss landscapes. Proceedings of the AAAI Conference on Artificial Intelligence, 33:
3574-3581, Jul 2019. ISSN 2159-5399. doi: wtw.9//aai.v3001.3333333033 //dx. www.doii.ooo.oo.. 10.gg/10.1000 160.//aaiaaa.... http:/aaa...vv..1....... 333101.33113574.
URL http:
Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A new perspective on generalization in neural networks, 2019.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape per- spective, 2020.
2020.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Watten- berg, and Ian Goodfellow. Adversarial spheres, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 14Xiv:14/2.6572. 2014.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks, 2019a.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns, 2019b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition, 2015.
Dan Hendrycks and Thomas G Dietterich. Benchmarking neural network robustness to common corruptions and surface variations. arXiv preprint arXivv1807.01660 2018.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. CoRR, 50s/1502.03167, 2015. URL http://ablp. db http://uunaaaaaeeaeea corr ctaer/corr1500 5002 html # Iofffe15..
uni-trier de/db/////
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced search). URL http: httb:://wwwt wwwww//wwwww..../ cs wwrontorooo.ooooo edu/-krizz 2 cifar.d html.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http::t/:///n
lecun. com/ exdb pondb/mnai mnist/.
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes, 2018

---

Under review as a conference paper at ICLR 2021
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks, 2014.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the ex- pressive power of deep neural networks, 2016.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks, 2018.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang. Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed clas- sifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 11292- 11303. Curran Associates, Inc., 2019. URL http::/ nips cc/paper/ 9307 prrovabyy robust-dees pdf.
waterrrrrrrrrrllllyyyaraa hhg.rpacclllllaaaaaacccccccccsse fiers.
smoothed-classe
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks, 2017.
Roman Vershynin. Estimation in high dimensions: A geometric perspective. Applied and Numerical Harmonic Analysis, pp. 3-66, 2015. ISSN 2296-5017. doi: http:// doi. org/ 10. 1000000//00 900---38--331 3-9-1111111 9- 19949-9949449
URL
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haherland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nel- son, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 10. 1592-019-0666-2
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist novel image dataset for benchmark- ing machine learning algorithms, 2017.
Dong Yin, Raphael Gontijo Lopes, Jon Shlens, Ekin Dogus Cubuk, and Justin Gilmer, A fourier per- spective on model robustness in computer vision. In Advances in Neural Information Processing Systems, pp. 13276 13286, 2019.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016.
Wide residual networks.
arXiv
preprint
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization, 2017.
10

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 DETAILS OF NETWORKS, DATASETS AND TRAINING
In this paper we use two architectures: 1) S i simp lCNNN which is a 4 CNN with 32, 64, 64 and 128 channels, ReL.U activations and maxpool after each convolution, followed by fully- connected layer, and 2) ResNet as described in He et al. (2015) with batch normalization on (loffe & Szegedy, 2015). We use 5 datasets: MNIST (LeCun & Cortes, 2010), Fashion MNIST (Xiao et al., 2017), CIFAR-10 and CIFAR- 100 (Krizhevsky et al.). and ImageNet Deng al. (2009). The ResNet trained for 200 epochs using SGD+Momentum at learning rate 0.1, dropping to 0.01 epoch 80 and 0.001 at epoch 120. The L2 norm regularization is 10 In one experiment, use data augmentation as described in 1. For our robustness experiments, we used the Wide-ResNet models (Zagoruyko & Komodakis, 2016) available in 2. We trained 11 different sizes of Wide- ResNet models (WRN-28-2 to WRN-28-12) with AutoAugment. Each model was trained from 15 different random veight-initializations for better statistics. We used the following hyperparameters to train each model: learning decay of 0.1, weight decay of 5e-4, cosine learning rate decay in 200 epochs, and AutoAugment (Cubuk al., 2018) for data augmentation.
A.2 DETAILED DERIVATION OF THE CLOSEST APPROACH OF TWO AFFINE SUBSPACES
Let us consider a situation in which in a D-dimensional space we have randomly chosen d- dimensional affine subspace A defined by point Xo RDD and a set of d orthonormal basis vectors { that we encapsulate into matrix M E RdxD, Let us consider another random n--dimensional affine subspace B. Our task is find point X E A that has the minimum L2
X X- X In words, we are looking for a point in the d-dimensional subspace that is as close as possible to its closest point in the n--dimensional subspace B. A point within the subspace A is parametrized by d-dimensional vector Edd by (0) LM + Xo e A. This parametrization ensures that for all choices of 8 the resulting X E A.
distance to the subspace B, mathematically X= argminn XEA X argmin
Without loss of generality, let us consider the case where the n basis vectors of the subspace B are aligned with the dimensions D n, D - n + 1, I,....,J D - n the short directions of the subspace B. A distance from point X to the subspace B now depends only on its coordinates 2....... Therefore (xX, B) Ein X?. This the case because of our purposeful choice of coordinates.
...,. D of the coordinate system. Let us call the
remaining axes
Given that the only coordinates influencing the distance are the first values, let us, without loss of generality, consider R subspace of the original TR.' only including those. Then the distance
between point within the subspace A parametrized by the vector 0 is (2( = @M + X
Given our restrictions, now the 8 Rd. .M R and Xo E Rd. The distance / attains its minimum for 0z(² (ØM- + Xu) MT Ö, producing the minimality condition 0* M _x--
There are now cases:
1. The overdetermined case, d > In case d 8- to (d - 8 = d d+ n Diddimensional family of solutions that attain 0 distance to the plane B. In this case the affine subspaces A and B intersect and share (d + D)-dimensional intersection.
= D n, the optimal 0* = -X, belongs
8. In case of 8" = -x,M- After plugging this back to the distance equation, we obtain Ø is 12 (x((()), B) =
unique solution case,
D n, the solution is unique
X, M + xx 2 - Xo + X 0. The square (in this case) matrix M and its inverse
M cancel each other out.
far10_
resnet py
Pttpps: :// thub. http://www..cttttooeeeeeeeeeeeee

---

Under review as a conference paper at ICLR 2021
3. An underdetermined case, d In case of d there is generically intersection between the subspaces. The inverse of M is now the Moore-Penrose inverse M Therefore the closest distance is 0 is (0*)), B) - X,M+ + Xa] Before our restriction from D - dimensions, the matrix M consisted of d D-dimensional, mutually orthogonal vectors of unit length each. We will consider these vectors be component-wer random, each component with variance 1/vD to satisfy this condition average. After restricting our space to s dimensions, M's vectors got reduced components each, keeping their variance 1/vD. They are still, in expectation, mutually orthogonal, however, their length got reduced to V5/VD. The (transpose) of the inverse M+ consists of vectors of the same directions, with their lengths scaled up to vD/ V5. That means that, in expectation, M M is a diagonal matrix with d diagonal components set to 1, and the remainder being 0. The matrix (I M M) contains (s - d) ones on its diagonal. The projection [X M M2 is therefore of the expected value of (x (s d)²/D. The expected distance between the d-dimensional subspace A and the d-dimensional subspace B is, in expectation
y VD-n-d
n n d D;
E [d(A, B)] x
VD
(4)
n+ D.
We ran a numerical experiment using automatic differentiation in JAX (Bradbury et 2018) where we generated random affine subspaces of different dimensions and measured their closest approach using optimization to locate the place. The numerical results presented in Figure 4 match the analytic predictions in Equation 4 well.
A.3
EMPIRICAL FIT FUNCTION
The empirical fit function we use extract the critical dimension of the cutting hyperplane d50% is shown in 6.
B
(5) It is sigmoid function that depends logarithmically on the dimension d and can be offset from O at for low d and from = 1 for high d. That is the case as sometimes the neural networks we analyzed would not have any regions of particular class reaching all the way to 100%. In other cases, even optimization in a line d = 1 would be able to get to a > 10% (for 10 class classification).
A, A+ exp (- log(d/C)/D)
For fitting the loss L(d), we utilized the fact that the cross-entropy loss depends logarithmically on p. and therefore used
B
L(d; = - log A
(6)
1+ exp (- (olooolo//C//D
In both cases A, B. C and D are free fit parameters. We used SciPy optimizer (Virtanen et al., 2020) to find the parameters and their covariance.
A.4 CUTTING PLANE AXIS- ALIGNMENT THE EFFECT OF SPARSITY
When choosing the matrix M that defines the span of the subspace in which we are optimizing, we can choose to make the rows of M sparse. On one end, each basis vectors might generically be non- zero in each of its components, while on the other end, single non-zero element per basis vector allowed. Geometrically, this corresponds to the alignment of the subspace with the axes (pixels and their channels for images) of the input space. Figure 11 shows the effect of the sparsity of M on the resulting d25%% d50%, d7s% and d90%- The sparser the M, the higher the dimension needed to reliably reach the 25%, 50%, 75%, and 90% class confidence region respectively. The effect of sparsity is visible, however, it is 1) not very significant (changing the dimension by small part of the total D = 3072 for CIFAR-10), and 2) its effect disappears for even small amounts of non-zero elements in M.
A.5 TRAINING ON RANDOMLY PERMUTED LABELS
For training on randomly permuted labels of the training set, we observe the critical dimension d5 to rise significantly, meaning that much higher dimensional cutting plane is needed to reliably
12

---

Under review as a conference paper at ICLR 2021
Axis-alignment cutting plane
120
Cutting plane dimension
c=0 at 90%
100
50%
80
cm0 at 25%
60
Original
Asis-digned (1)
Parielly algnnd (100)
Unaiigned (3072)
40
20
109
10a
102
10a
Non-zero elements (max 3072)
Figure 11: The effect of axis aligmment of the cutting planes. The figure shows the cutting plane dimension necessary to reach 4 thresholds levels (the data lines) of class 0 probability (y-axis) from random starting point for well trained ResNet20v1 non-zero elements of the basis vectors the random cutting plane (x-axis). For a small number of non-zero elements, single pixels are varied, while for 3072 non-zero elements (the maximum value), all pixels are varied jointly. The axis-aligned random cuts require higher dimensions to hit the same accuracy regions class O.
10. We vary the number of
intersect a class manifold. The breakdown by class for ResNet20v1 CIFAR-10 and CIFAR-100 shown in Figure 12. The comparison to semantically meaningful labels is shown in Figure
A.6 ENSEMBLING
The effect ensembling on the critical dimension d50% broken down by class shown in Figure 13. For each of the 10 CIFAR-I0 10 classes, the d50% grows with ensemble size, which is unlike any other performance-improvee
techniques (such as data augmentation, and more training) we experimented with. A simple model predicting the resulting d50% for an ensemble of size n by assuming that the class manifold codimensions add works surprisingly well for small ensemble sizes in Figure 13. The intuition for why that might be the case is illustrated in Figure 10.
A.7 ADDITIONAL CUTTING CURVES FOR CIFAR-10 AND CIFAR-100
Two additional detailed cutting plane results can be found this subsection: SimpleCNN on CIFAR-10 in Figure 14, and ResNet20v1 on CIFAR-I00 in Figure 15.
A.8
DIMENSION AS FUNCTION OF TRAINING STAGE
While Figure 9 shows the aggregate effect of training epoch on the the critical cutting plane dimen- sion averaged over all single-class regions, the detailed per-class results can found Figure 16 for ResNer20v1 on CIFAR-10 10 (two indepdently initialized and trained models), in Figure 17 for SimpleCNN on CIFAR-10, and in Figure 18 for ResNet20v1 on CIFAR-100.
13

---

Under review as a conference paper at ICLR 2021
2,2
Alac Las bela!
Lata c-10
Uat cifll
Lan or
0.5
02
0.2
0.8
Data exto
65
022
1000
103
1020
103
1000
10 Catting plare timersoo
1500
100
1020
Cuttiig Pane simmsiinn
Cutting plane dineriist
Outting pane dinerdion
Cutting plae simersion
Civoc
Caes
Caos
3.0
1030 ne Bdt
112 c-sin Bus opt
1972 Denk Bux Legh)
1144 be (o!1)
w00 tena cock))
0.4
0.0
2.2
-isssaa cabal
Jia3a Ln. Jis crlay
Al. 16d sl10 cea bcisl
diu
di M cusciial
ossc-iB
0.5
0.2
0.0
1000
300
2020
102
1200
25
1000
200
3000
Figure 12: Maximum probability reached on cutting planes of different dimensions for all 10 target classes of CIFAR-IO (top row) and CIFAR- 100 (bottom row) for a ResNet20v1 trained to 100% training accuracy on randomly permuted class labels. The d50% is consistently higher and therefore the dimension of the high confidence manifolds is lower than for semantically meaningful labels (Figure 2), suggesting geometrically very different function being learned.
Class
Class
4
Cutting d5
80
125
80
Naive
125
100
80
60
100
75
60
40
40
50
40
20
50
Nalve
20
25
12345 45
10
12 3
45
10
12345
10
12345
7
12345
7
Class
Class
Cass
Class 8
Class 9
Cutting dege
80
200
125
250
80
60
150
100
200
150
75
100
50
20
Naive
50
Naive
25
Naive
50
Neive
20
Nave
12345
12345
12345
12345
12345
Ensemble size
Ensemble size
Ensemble size
Ensemble size
Ensemble size
Figure 13: The effect of model ensembling on the dimension d50% needed to reach 50% accuracy of 10 CIFAR-10 classes. The results shown are for ResNet20v1 trained for 50 epochs each. Uni- versally across all classes, the larger the ensemble, the higher the 450% and therefore the lower the high confidence manifold dimension. A naive model of addition of codimensions between models is overlayed, showing a surprisingly good fit for small ensembles.
14

---

Under review as a conference paper at ICLR 2021
Class
0lss
Clos
Cass
3.5
Mev poth
64
12
-22hw14
Beacett
Bracedd
Chec?
Osec
Cam
Casc
Mavi pis marted
0.8
pily
02
220
019 0131
019 0-11
1ia p:11
L09 2-10
30
100
15
1000
200 1020 Custing dimoraton
Cutting simonsion
Cutting plana dimorala
Cutting dimerston
plane
Figure 14: Maximum probability of single classes of CIFAR-10 10 reached on cutting planes of dimen- sion d. The figure shows the dependence of the probability of single class of CIFAR- 10 (y-axes) reached on random cutting hyperplanes of different dimensions (x-axes). The results shown are for well-trained (> 76% test accuracy) SimpleCNN on CIFAR-IO. Each dimension d is repeated 10x with random planes and offsets.
Class
dass
Class 19
Clss 29
Cuss 57
Hi
0.3
0.2
6117 UMt C-12
Dut c-1o
Clts 5t
Obver
Casc 29
Cacs
1.0
Doooe prth prth
0.8
C4
0.2
-2-222211
Der exc79
10 100
102
100
CLtlnn dimaniion
cutiing plane dimorotes
Outing ditersion
Cutting slane di
Cuszing plane dimersin
Figure 15: Maximum probability of selected single classes of CIFAR-100 reached on cutting planes of dimension d. The figure shows the dependence of the probability of single class of CIFAR- 100 (y-axes) reached on random cutting hyperplanes of different dimensions (x-axes). The results shown for well-trained (> 67% test accuracy) ResNet20v1 on CIFAR-100. Each dimension d is repeated 10x with random planes and offsets.
Class O
C
Closs
Clus 2
Clos 4
feurd
Bard
Curtro d 6
2500
3300
25%
290 und
2300
1300
10
Noc
Coos
Caeen
Coos
Coos
3350
23% CiLinE
20% pri-ns
2500
1550
1145
5.3
300
0.4 0.
0.2
5.4
5.6
(rstning Roat
Stage brairing anl)
Sluge buining Sest soc)
Slage buring ileat
Figure 16: The cutting plane dimension needed to reach 25% probability for the 10 classes of 10 as function of training stage for 1 averaged over two initializations and runs.
15

---

Under review as a conference paper at ICLR 2021
Icard
Not found
found
furdd 25% Lo2
Not found
No: fourd
Cutting peree mm
25th cwo
25% cml
25% ced
25% ced
2300
2300
1300
1300
196
Clsss
Cliss
Class
Class e
Cbe
foond
Nolloorr
3350
2200
1200
110
23
Zags tralning llast ace)
Stage of training bast aod)
Stags oftraning rist acc)
Stage of training (tast aod)
Stage oltra tist acc)
Figure 17: The cutting plane dimension needed reach 25% probability for the 10 classes of CIFAR-10 as a function of training stage for a SimpleCNN.
fourd
Rund
Motfourd
Net fonnd
Not fourd 25% c4
25% cod
25% co39
25% 2-25
2500
1300
honfrund
25% um2
Cleo 49
Clocs 16
The 64
Our plaeeeeeeed 69
3300
2300
1300
55
337
6" 205
128
6" 21.0
Stags buiningg Boak u531
Stags buining Texk 003)
slage buiring (lat 203)
Slags training Dext ucd
stage of traning a00)
Figure 18: The cutting plane dimension needed reach 25% probability for 10 randomly selected classes of -IFAR-100 as a function of training stage for fully trained ResNer20v1.
16


Reviews:
[{"review_id": "yETsvdDxtb-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 proposes to understand the behavior of deep networks for classification tasks by studying the dimensionality of the \"class manifolds\", i.e., regions in the data space that are mapped to the same one-hot output. To measure such dimensionality, the paper proposes a method that is based on intersecting the class manifold with a random affine subspace of varying dimension. The idea is that when there is a intersection then the dimension of the random affine subspace is roughly the codimension of the class manifold. The paper then studies how different factors in data, architecture, training, etc., affects such dimensionality.\n\nStrength:\n\nThe development of the paper is solid in the sense that it studies the effect of a wide range of design choices (see the list 1) - 9) in paper abstract).\n\nWeakness:\n\nThe whole paper is based on the assumption that each \"class manifold\" is a low-dimensional manifold. However, the paper did not provide a justification for this assumption nor do I think it is a valid assumption. \n\nThe manifold assumption is a fundamental assumption for machine learning and data science, and that assumption is made for *data*, rather than *classes learned by neural networks*. One intuitive justification for that assumption in the case of data is that if I take a data point (say an image) and I do a perturbation, then if the perturbation is in a direction that is \"meaningful\", say by a translation, rotation and distortion, then the class label for that data point remains the same, but if you go towards another direction then likely the image is no longer meaningful and the class label changes. However, this same line of argument does not seem hold for the class manifolds learned by neural networks: if I consider a random input to a network then because the decision boundary is piecewise linear, it is with high probability that you can go towards all directions and maintain the class label. \n\nIf the low-dimensionality assumption is not valid, then the premise of the entire paper becomes problematic: the intuition given in Fig. 1 is no longer valid, and the theory in Sec. 3 is no longer meaningful. \n\nEven if the low-dimensionality assumption is true to some degree, the proposed dimension estimation is still very much problematic: both the intuition in Fig. 1 and the theory in Sec. 3 are based on assuming that such low-dimensional manifold is (close to being) linear. But the ability of deep networks for performing complicated nonlinear mapping, which is the key to its great success, likely makes such low-dimensional manifolds to be highly nonlinear. Therefore, a discussion of how such nonlinearity affects the proposed dimension estimation is quite necessary but is missing. \n\nAdditional comments:\n\n- How is X_0 in the cutting plane method generated? It is said in the paper that it is generated at random, so perhaps that means a i.i.d. Gaussian vector, but presumably the variance of the Gaussian distribution could have an impact on the result as it captures how far the affine subspace is from the origin.\n\n- Sec. 3.1, which contains the main theoretical result of the paper, is presented in vague terms (e.g., what is \"highly likely\", under what statistical model?). Perhaps it is better to make it precise by writing the result as a theorem. \n\n\n**Update after rebuttal**\n\nI would like to thank the authors for the detailed rebuttal, but my feeling now is that the rebuttal is making it even more complicated and sometimes conflicting with itself. I believe the paper needs some careful rewriting and updates to clarify its points and assumptions. \n\nConcretely, the paper is built upon the premise that each class manifold is a submanifold with dimension lower than that of the ambient space. I pointed out in my review that this premise may not hold at al, therefore the paper is fundamentally problematic. Then, R2 in one of his/her responses raise the same question, perhaps after reading my question. Then, I see a difference in response to R2 and my comments. For R2, the response is \"The intrinsic dimensionality of class manifolds is absolutely the full dimension of ambient input space\", which is effectively acknowledging that my critique is valid. However, the response to me is \"This is very easily refuted by the ubiquitous and universal existence of adversarial examples\". I don't really see why there is a discrepancy here. Besides, the argument that is used to refute my argument, namely existence of adversarial examples implies class manifolds are lower dimensional than the ambient space, is apparently wrong and can be easily refuted. By and large, the existence of adversarial examples only means that the decision regions are thin at every location, I can totally have a fine mesh of the data space that achieves this. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "stM_DT1BmVj", "reviewer": "AnonReviewer4", "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": "This work aims to study the characteristics of the class manifolds provided by a multiclass classifier. In particular, the main goal is to determine the effective dimensionality of these manifolds for the case of neural networks that outputs normalized probabilities. To achieve this, authors introduce the cutting plane method that, following some assumptions, allow them to relate the dimensionality of a random affine hyperplane to the effective dimensionality of the manifold for each class. Authors support their main findings including extensive experimentation. \n\nThe theoretical foundation behind the paper seems to be sound, however, as a disclaimer, this research area is not close to the main expertise of this reviewer. In terms of writting, the exposition is clear, however, my main doubt is related to the process to infer the manifold dimensionality for a whole class using a process that depends on each specific instance. It will be good to clarify this point and also the computational complexity involved during the process. \n\nAs a recommendation, it will be great to test the method using an artificial case with known ground truth about the effective dimensionality of the class subspaces, so it will be possible to directly validate the findings of the cutting plane method. The current analysis focuses on the case that the cutting plane dimension leads to 50% of the target class (d_50%), which is not the only choice, specially considering that a highly relevant goal is to quantify the effect of manifold dimensionality on generalization. The use of metrics or scores related to generalization will lead to valuable conclusions.\n\nIn summary, this is an interesting area of research to shed lights on the process used by learning models to transform from input space to class-probability space. In particular, the potential relation between manifold dimensionality and generalization is worth to pursue. This work will be of interest to ICLR and I recommend to be accepted as a poster contribution. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "GU2A1lGl86H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 proposes an empirical method for estimating the dimensionality of a class manifold, defined here as a collection of points for which the last (softmax) layer of a neural network maps them to a membership probability vector associated with a specific class. Their approach involves the generation of a randomly oriented 'cutting plane' of dimension $d$, passing through a randomly generated source point. The authors note that if the sum of the dimensions of the class manifold and the cutting plane exceeds the full spatial dimension, the chance of an intersection of the two is high.  Conversely, if the sum falls short of the full dimension, the chance of an intersection is very low. \n\nUsing a gradient descent technique starting at the source point, a location within the cutting plane is sought that minimizes the cross entropy loss between it and a target class membership vector representing the class manifold. A low minimum loss would indicate a likely intersection ($d$ too high), whereas a high loss would indicate a likely miss ($d$ too low). Although the dimension of the class manifold is in general unknown, the process is iterated for many choices of the initial cutting plane, and many choices of the cutting plane dimension $d$. The value of $d$ achieving the median loss value is chosen as the estimate of dimensionality.\n\nIn their experimental validation of the approach, the authors examine the effects on the estimated manifold dimensionality due to various factors, including data noise, label noise, training set size. Interestingly, their method also allows them to produce an estimate of the class boundary dimensionality by specifying the average of two class one-hot vectors as the target probability vector.\n\nPros:\n-----\n\n1) This is an interesting approach to the problem of dimensional modeling.  Estimation of dimensionality using cutting planes, without an explicit parameterization of the subspace, is an attractive idea that (if performed efficiently and reliably) could be particularly impactful. A strong point of the model is that it considers as its 'class manifold' the regions of deep latent space that have sufficient probabilities of being in one or more classes of interest. The method thus supports assessments of dimensionality in border regions in an elegant way.\n\n2) The optimization procedure proposed does seem practical enough - each optimization run is efficient, and the number of runs can be tailored to an execution budget.\n\n3) The paper is generally well organized and presented. The descriptions are clear and accessible.\n\nCons:\n-----\n\n1) As acknowledged by the authors in the caption of Fig 2, the dimensional estimates seem much higher than the typical estimates of intrinsic dimensionality as determined by local estimators (e.g. LID / Levina & Bickel, etc). This discrepancy could be due to a number of factors that are not taken into account: curvature of the class manifold, its boundedness, its disconnectedness, etc. All these factors could cause the gradient descent to terminate at high cross-entropy loss values, which would drive the estimate of dimensionality too high (even approaching the representational dimension of the latent space?).\n\n2) Following from 1), some of the conclusions reached from the experimental analysis are not fully convincing. For example, in 4.5 an inverse relationship is reported between the training set size and the 'effective' dimension. However, non-uniformity of distribution within the manifold could lead to configurations that trap solutions at unrealistically-high values of $d$.  In 4.6, adding Gaussian noise to each pixel is a full-dimensional transformation that is known to strongly bias the local intrinsic dimensionality upward, to unrealistically high values.\n\n3) Again following from 1), the authors have not situated their work with respect to the recent literature on the use of intrinsic dimensional estimation in deep learning settings. For example, local intrinsic dimensionality has been proposed as a characterization of learning performance (Ma et al, ICML 2018), adversarial perturbation (Ma et al, ICLR 2018, Amsaleg et al, WIFS 2017), and in GAN-based image infilling (Li et al, IJCAI 2019). How does their estimator compare in practice to other estimators already in use?\n\nOther comments / questions:\n---------------------------\n\n1) The paper should be more self-contained in places. For example, Equation 6 is referred to in the main paper, but appears only in the appendix.\n\n2) Like distances distributions themselves, loss functions may exhibit a bias due to the local intrinsic dimensionality. Discuss?  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7ujhxXE04Oo", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors propose a cutting plane method, inspired by intersection theory from algebraic geometry, to analyse the properties of neural networks. Specifically, the method allows to estimate the dimensionality of the class manifolds induced by the networks. An empirical analysis shows that the estimated dimensionality correlates with the generalisation performance and the robustness of neural networks, thus opening the door to potentially new perspectives on deep learning theory.\n\nThe paper is well structured and clearly written. Also, the authors are planning to release the code to reproduce their experiments. Last but not least in terms of importance, the paper provides an original and novel method for the analysis of the properties of neural networks. In fact, while previous works have used a similar strategy to estimate the intrinsic dimensionality of the loss landscape in the weight space (see cited works in the paper), this work focuses on the analysis of neural networks in the input space.\n\nIn general, there are no major issues with the paper. However, there are some points that need to be discussed, which can be helpful (i) to identify more precisely the conditions about the validity of their results and (ii) to relate with other existing work on the analysis of deep learning using spline theory. Please, see below for more detailed comments and also suggestions to increase the quality of the paper.\n\nBased on these considerations, I recommend for the acceptance of the paper with an initial score of 6. I'm willing to considerably increase the score and award the authors, if they can address my questions.\n\nDETAILED COMMENTS\n\nPlease, let me make two simple pedagogical examples to analyse the behaviour of the proposed method and to possibly seed further thought. \n\nFIRST EXAMPLE\n\nConsider a two-dimensional real space, where the class-manifold is a line. Then, generate a second line by randomly sampling its intercept and slope coefficient and refer to them as the line parameters. Now if you consider the parameter space of this second line, you have two regions, one of zero measure, which contains all the cases where the two lines are parallel, and the remaining one, which contains all the intersecting cases. This means that the two lines are almost always intersecting each other. Consequently, the estimated dimension of the class-manifold is correct.\n\nSECOND EXAMPLE\n\nConsider the same example as before, but now the class-manifold is a parabola. Similarly to the previous example, there are two regions, namely the ones defined by the intersecting and the non-intersecting cases between the parabola and the randomly generated line, but differently from the previous one, both regions have non-zero measure. Therefore, we may end up to generate lines that do not intersect the class manifold. This would result in considering a higher dimensional object (in this case a plane) to guarantee the intersection with the parabola. Consequently, we would underestimate the dimension of the class manifold. \n\nThis phenomenon can be even more pronounced when moving to higher dimensions. Therefore, I agree with the authors that the whole analysis is exact when considering hyperplanes. But what are its limitations when moving to the nonlinear regime? How can we guarantee that the estimated dimension is accurate? It seems that the proposed method provides a lower bound on the true dimensionality of the class manifolds. Is that correct? If so, when can this bound be tight?\n\nAlso, there is some recent line of work trying to analyse the behaviour of deep leaning in terms of decision boundaries and their curvatures from the perspective of spline theory [1-2]. Could you please discuss this and add the explanation in the paper?\n\n\nSUGGESTIONS TO INCREASE THE QUALITY OF THE PAPER\n\nI proceed following the order of the sections.\n\nSection 2.2. Is it possible to provide the full details of the algorithm to estimate the cutting plane dimension, like an algorithmic table? Also, where is Equation 6 (in the appendix)? What are the mean and covariance parameters?\n\nSection 3.1. Can you be more precise when you use the terms 'highly likely' and 'generically' and discuss what happens in the nonlinear regime?\n\nSection 3.1. D-(d_A+d_B) should be 2D-(d_A+d_B)?\n\nSection 3.1. Can you rephrase the sentence \"For the subspaces A and B intersecting transversally...satisfying the upper bound and therefore leading to Equation 2\" and make it more clear? Specifically, which upper bound and how does this lead to Equation 2?\n\nSection 3.2. Can you consider to remove it, as the purpose is not clear and it does not seem to introduce any additional information?\n\nSection 3.3. Can you make an example to explain the difference between dimension and effective dimension?\n\nSection 4.3. Is there any concrete insight on the analysis of the class-boundary and multi-way class-boundary manifolds? I would appreciate to see more discussion on that.\n\nSection 4.6. Is there any specific reason why you chose to show only class 0 and 1 in Figure 8? Can you provide the figures for the other classes as well, maybe in the appendix?\n\nSection 4.7. Similarly to Figure 8, can you add the other cases for Figure 9? Always for this subsection, which initialisation did you use in the experiments? This is an important information that could be of interest for those studying initialisation strategies for deep learning?\n\nSection 4.8. Do you have any experiment with ensemble of classifiers with different architectures? If so, do the same findings hold? May it be possible that you are underestimating the dimension of the class manifold in the set of experiments shown in the paper? \n\nSection 4.8. Can you provide a plot of the generalisation performance versus the ensemble size? Or better correlating the cutting plane dimension with the generalisation performance for the different ensemble size?\n\n[1] Balestriero and Baraniuk. A Spline Theory of Deep Learning. ICML 2018\n[2] Balestriero et al. The Geometry of Deep Networks: Power Diagram Subdivision. NeurIPS 2019\n\n#########################\n\nUPDATE\n\nThe discussion phase has highlighted several major issues: \n1. There has been a significant conceptual shift in the problem definition (i.e. from estimating the intrinsic dimensionality of the class manifold to quantifying its geometrical properties). \n2. I'm not convinced about the validity of some arguments/statements used by the authors to support point 1. For example, the statement \"The intrinsic dimensionality of class manifolds is absolutely the full dimension of ambient input space, but this is a completely uninteresting observation\" is not fully supported and I'm not even sure that is true.\n3. Furthermore, the paper is still in its original form. It has been difficult to keep track about the modifications that the authors should do.\n\nTo conclude, the article is not ready for publication, yet and therefore recommend for its rejection. \n\nI encourage the authors to further investigate the topic and carefully consider whether the statements provided in the discussion phase are true.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to study the dimension of the Class Manifolds (CM) which are defined as the region classified as certain classes by a neural network. The authors develop a method to measure the dimension of CM by generating random linear subspaces and compute the intersection of the linear subspace with CM. All reviewers agree that this is an interesting problem and worth studying. 

However, there are major concerns. One question raised by several reviewers is that the goal of this paper is to analyze the dimension of the region that has the same output for the neural network; while the method and analysis are for a single datum. It is not clear if the obtained result is what the paper really aimed at. Another issue is the experimental results are different from that of local analysis. The dimension estimated by using the method in this paper is much higher. 

Based on these, I am not able to recommend acceptance. But the authors are highly encouraged to continue this research.

Decision: Reject