Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

The 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. 

As 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.

In 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. 
review_title: Slice, Dice, and Optimize: Measuring the Dimension of Neural Network Class Manifolds

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

Strength:

The 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).

Weakness:

The 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. 

The 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. 

If 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. 

Even 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. 

Additional comments:

- 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.

- 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. 


**Update after rebuttal**

I 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. 

Concretely, 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. 

review_title: Interesting and solid work, but the fundamental assumption seems problematic

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

Using 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.

In 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.

Pros:
-----

1) 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.

2) 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.

3) The paper is generally well organized and presented. The descriptions are clear and accessible.

Cons:
-----

1) 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?).

2) 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.

3) 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?

Other comments / questions:
---------------------------

1) 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.

2) Like distances distributions themselves, loss functions may exhibit a bias due to the local intrinsic dimensionality. Discuss?  

review_title: Dimensionality estimates are too high?

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

The 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.

In 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.

Based 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.

DETAILED COMMENTS

Please, let me make two simple pedagogical examples to analyse the behaviour of the proposed method and to possibly seed further thought. 

FIRST EXAMPLE

Consider 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.

SECOND EXAMPLE

Consider 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. 

This 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?

Also, 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?


SUGGESTIONS TO INCREASE THE QUALITY OF THE PAPER

I proceed following the order of the sections.

Section 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?

Section 3.1. Can you be more precise when you use the terms 'highly likely' and 'generically' and discuss what happens in the nonlinear regime?

Section 3.1. D-(d_A+d_B) should be 2D-(d_A+d_B)?

Section 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?

Section 3.2. Can you consider to remove it, as the purpose is not clear and it does not seem to introduce any additional information?

Section 3.3. Can you make an example to explain the difference between dimension and effective dimension?

Section 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.

Section 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?

Section 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?

Section 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? 

Section 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?

[1] Balestriero and Baraniuk. A Spline Theory of Deep Learning. ICML 2018
[2] Balestriero et al. The Geometry of Deep Networks: Power Diagram Subdivision. NeurIPS 2019

#########################

UPDATE

The discussion phase has highlighted several major issues: 
1. 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). 
2. 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.
3. Furthermore, the paper is still in its original form. It has been difficult to keep track about the modifications that the authors should do.

To conclude, the article is not ready for publication, yet and therefore recommend for its rejection. 

I encourage the authors to further investigate the topic and carefully consider whether the statements provided in the discussion phase are true.
review_title: Slice, Dice, and Optimize: Measuring the Dimension of Neural Network Class Manifolds

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