Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper builds on the empirical observation of Li et al (2018) that training neural networks in a low-dimensional random subspace of the parameter space often achieves similar levels of train and test accuracies as training in the original parameter space when the subspace dimension is above a critical threshold. The main result is an application of Gordon's escape theorem showing that the critical threshold training codimension is the squared Gaussian width of loss sublevel sets projected onto a sphere around the initialization.
main_review: Gordon's escape theorem characterizes the probability that a given subset of the unit sphere $S\in \mathbb{S}^{D-1}$ has an empty intersection with a random $d$-dimensional subspace of $\mathbb{R}^D$. The randomness here is given by a standard Gaussian matrix and the random subspace is distributed uniformly on the Grassmann manifold w.r.t. the associated Haar measure. The probability of escape (i.e., no intersection) is characterized by a squared version of the Gaussian width of $S$. The Gaussian width is the expected value of the dual norm of a standard Gaussian vector, and for sets containing the origin it coincides with the more familiar notion of Gaussian complexity in statistical learning theory. 

The innovation in this paper is a straightforward adaptation of Gordon's result for estimating the success probability of hitting the convex hull of a loss sublevel set when training within a random subspace of the original parameter space. For the success probability to be large, the subspace codimension $D-d$ must be less than the squared Gaussian width of the desired training loss sublevel set projected onto a sphere around the initialization. The authors identify the latter as the critical threshold training codimension in relation to the observations of Li et al (2018) and empirically demonstrate a phase transition in the success probability in the loss-subspace dimension plane around this threshold. For a quadratic approximation of the loss, the authors give a bound on the threshold dimension in terms of the spectrum of the Hessian and distance to initialization.

The main strength of the paper lies in exploring the ramifications of the above for training within random and optimized subspaces starting from either a random initialization or after using some information from training the network in the full space (which the authors call "burn-in") that apparently brings the initialization closer to a desired loss sublevel set. This explains for instance why the threshold dimension decreases when more information is burned into the initialization. 

Question: 

Can you comment on the estimation of the threshold dimension for general losses (beyond the quadratic approximation)?

Minor nitpicking: 

-- The reference to Gordon's theorem both in Gordon (1988) which I believe is Corollary 3.4 and also in the Mixon (2014) blog state the result with coefficient for the exponential as 3.5 instead of 2.5. I can see how one gets the coefficient 2.5, but perhaps for the benefit of the reader, the authors should furnish a reference that accurately reflects their statement of Gordon's theorem in relation to the above.

-- In the second paragraph in page 1, the statement should be "... this threshold training dimension is equal to the dimension of the full parameter space minus the "squared" Gaussian width of the desired loss sublevel set projected onto the unit sphere around initialization." (include the squared?).

summary_of_the_review: The contribution is a straightforward application of Gordon's result weighing mainly on the empirical side. I believe nonetheless that the paper gives new insights for training in random subspaces. Overall, I like the paper and would be happy to raise my score based on the authors' response.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The modern deep neural networks are over-parameterized and it is possible to construct a smaller parameter space that delivers a similar loss value. If one investigates the dependency of the probability of achieving the desired loss values on training subspace size, one will observe a sharp transition. The dimension where this transition happens the authors call a threshold training dimension. The authors of this paper proposed a theoretical explanation of the existence of the threshold training dimension. In particular, using Gordon’s escape theorem the authors describe the dependence of the threshold training dimension on the initialization and final desired loss. The authors proposed new lottery subspaces for which the threshold training dimension is much higher than for other random subspaces.
main_review: Pros:

-- A new theoretical result that explains the existence of threshold training dimension.

-- The paper is well motivated and well structured. In particular, the authors showed in a toy example that the theoretical lower bound is close to the empirically observed value. The authors provided extensive experimental analysis of transition bounds for different random subspaces.

Cons:

-- The lottery subspaces, despite having smaller transition dimensions, encode a lot of information into the linear transformation matrix, therefore applications to compression can be limited.

-- The considered theory does not take into account optimization methods.

Questions and notes:

-- Figure 2, last column. The training threshold dimensions look similar for burn-in subspaces with different starting iterations. Therefore the argument that a better starting point decreases the threshold dimension does not look convincing. Does one burn-in step correspond to one batch update?

-- Section 2. Loss sublevel sets paragraph. l(f_w(x), y) -> l(f_w(x_n), y_n)


summary_of_the_review: Overall, I would recommend accepting the paper. It contains interesting theoretical results explaining the existence of threshold training dimensions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper aims to provide a theoretical explanation for recent observations (lottery tickets, training in random subspaces, spanning pruning) that deep neural networks can be trained using fewer parameters than necessary. They provide the theoretical explanation using the so called Gordon escape theorem from high-dimensional geometry, which says that there is a phase transition in the success probability of training as the training dimension exceeds a threshold and this threshold is rather tight. This is supported by experiments on various benchmark datasets that seem to exhibit this phenomena of this phase transition. 
main_review: Strengths:

Theory:
This paper introduces a novel concept using the Gordon escape theorem to understand the effect of training in lower-dimensional random subspace of the NN weight space, especially after a burn-in period. Specifically the theorem shows the existence of a phase transition in the success probability of training and this is supported by the experiments as well. 

Experiments:
They also provide a new training/pruning method based on this phenomena, which performs better than other existing training methods, especially in low-training dimensions

Weaknesses:

The theorem is a first such characterization, but it is not clear as to the difficulty of estimating the threshold dimensions for more than quadratic loss functions, potentially when involving deep ReLU networks for instance. It would be nice to have a discussion of the challenges for at least shallow networks (1 hidden layer ReLU network for example).

Another clarification is in Eq 2.2, the randomness of A is from a Gaussian distribution. In the statement of Gordon escape theorem it would be useful to clarify what "uniformly from a Grassmanian mean"? Are there any restrictions on how the random subspace is generated? 
As a continuation, in the Lottery subspaces algorithm, the matrix U is generated by the dynamics of GD on the loss function. Does the Gordon escape theorem still apply for this random process?

Is it possible to infer in the pruning algorithm and the Gordon escape theorem, how the trainable network depends on depth or width of the original network? It would be interesting to see at least experimentally the change in depth/width for large classes of problems, as this ties in with numerous results on expressivity that say in general , increasing depth is more useful than increasing width (from the lens of expressivity alone!).

It would be useful if the authors can clarify the dependence on the ratio D/d, in the w.h.p statements.


summary_of_the_review: In summary, the authors provide a theoretical explanation for many recent results that support training on a lower-dimensional subspace of the NN weight space and the back the theoretical claim via experimental results that show the existence of such phase transitions. Although, a lot remains to be said, this paper raises more interesting questions and I think this will be of value to the deep learning community.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies DNNs training when restricted to a random affine subspace (centered either at the initialization point $x_0$ or at a point $x_t$ obtained by training an unrestricted network for $t$ steps, which they call burn-in), and the probability that a loss lower than $\epsilon$ can be reached with a subspace of dimension $d$. They observe a sharp transition between pairs $(\epsilon,d)$ where this probability is either almost $0$ or $1$. They observe that the lower the dimension, the less likely one is to reach a loss $\epsilon$.

The authors show that this transition can be understood in terms of the Gaussian width of the projection of the sublevel set $S(\epsilon)$ to the unit ball around the center point $x_0$ (or $x_t$), which they call the local angular dimension. Gordon's escape theorem makes it possible to bound the transition between the two phases as a function of the local angular dimension.

Calculating the local angular dimension of the sublevel sets of the loss of DNNs is difficult, instead the authors study a quadratic loss, giving an approximation for the local angular dimension in this case. They then compare the empirical transition and the bound on the transition in terms of the local angular dimension between the two phases and find a good agreement with the theory.

Finally they propose a notion of lottery subspaces inspired by the lottery tickets paper and compare their results.
main_review: The article is well written and clear. It studies an interesting phenomenon with mix of empirical and theoretical results.

The empirical experiments are detailed and illustrate clearly the transition they are studying.

The theoretical results are nice and explained well. It is not much more than a corollary of Gordon's escape theorem, but I know of no previous work using it in this context.

The example analysis for quadratic loss is important, it gives an idea of how one could compute the local angular dimension in practice. I think the authors have missed an opportunity here to draw a link with the loss of DNNs. With the MSE loss and in the NTK regime (with a specific initialization and sufficiently many neurons in the hidden layers), it has been shown that the loss landscape around the training path is approximately quadratic (https://openreview.net/pdf?id=SkgscaNYPS), with spectrum equal to the spectrum of the NTK Gram matrix. In this setting, the local angular dimension of the sublevel sets of the DNN loss should be well approximated by the local angular dimension of the quadratic approximation. This would make it possible to compare the empirical transition with your theory in the DNN case directly.
summary_of_the_review: The article is clear and well written. It studies an interesting phenomenon with mix of empirical and theoretical results. The theoretical results are clear and interesting though they are direct consequence of Gordon's escape theorem.
review_title: null

Meta-review: This paper presents new insights for training on random subspaces of low dimension, with several theoretical and experimental contributions. This is a paper that would be interesting to many people doing research in deep learning, both from the theoretical and practical side.
Decision: Accept (Poster)