Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape

Thanks for your helpful comments. We address all of your concerns and hope that our response clarifies your questions on our work.

The key contribution, mild overparameterization level is only achieved for data of dimension 1. For the data with general dimension the counting method seems intractable.

We address the high-dimensional case in Theorem 5. One consequence of this result is that for high-dimensional data $(d_0 \geq n)$, if $d_1 \geq \Omega(1)$, then most activation regions have no bad critical points. This is a mild level of overparameterization since $d_0d_1 \sim n$.

The authors are welcome to elaborate more on how to generate their analysis to high dimensional data or even deeper networks.

We have added a new Appendix H which generalizes our analysis to deep networks. Our methods for the shallow case can be applied to deeper networks by considering gradients with respect to individual layers. We find conditions on the activation patterns of each layer which ensure that the gradients will be full rank.

However, Corollary 8 still focuses on the ”non-empty activation regions”. If most activation regions are indeed non-empty, why not drop the term ”non-empty”?

Indeed, if $d$ is large relative to $n$, then most activation regions will be non-empty. We include the term non-empty here to emphasize that our result is not just being applied to empty activation regions which trivially do not contain any critical points.

Among the related works being provided in the first section, can you compare your work with Liu (2021)? They seem to provide a stronger result.

Liu (2021) shows that in a given activation region, all local minima are global within the given region. This means that for a critical point $\theta$ within an activation region $\Omega$, $\theta$ is a global minimizer of the loss restricted to $\Omega$, but there could still exist $\theta' \notin \Omega$ which attains a smaller loss than $\theta$. In contrast, we show that in most activation regions, all critical points are global minima over the entire loss landscape. We are proving a proving stronger statements about the critical points themselves by incorporating information about the activation patterns.

When $d_0 = 1$, Theorem 5 already provides some strong results, why do we bother deriving Theorem 10?

In the one-dimensional case, most activation regions are empty (in contrast to the high-dimensional case where every activation pattern is realized). We provide a more refined analysis by focusing specifically on the non-empty activation regions, characterizing them, and showing that most of them have a full rank Jacobian.

I thank the authors for providing the feedback. They have addressed my questions and I will keep my score.

We thank the reviewer for their valuable feedback and suggestions, which we address below. We hope that our response and updated manuscript address your concerns and you consider raising your score.

Unfortunately, the scope of this paper looks rather limited. The paper studies a single-hidden-layer model and only the first layer is trained. Hence, given an activation region, the prediction is linear in W, which makes the Jacobian matrix constant in the region and it makes proofs much easier. For Sections 5-6, the authors show results specialized to one-dimensional input space. I question if these proof techniques could be extended to deeper networks and higher-dimensional input space.

The paper only considers differentiable local minima, which misses the possible existence of non-differentiable local minima. In fact, Laurent & von Brecht (2018) show that in the hinge loss case, local minima can only occur at the non-differentiable boundaries except for flat regions. Is there any hope of including non-differentiable points into the analysis?

We have added appendices to address non-differentiable critical points and trainable output weights (Appendix G) as well as the deep case (Appendix H). Although our focus has been on the two-layer case, our techniques can be used to understand more general settings. Even when looking at non-differentiable points of activation regions, we can show in the case of one-dimensional input data that most activation regions contain no spurious minima.

To generalize to the deep case, one can compute gradients with respect to individual layers of the network and find conditions on the activation patterns for which the gradients are full rank. We demonstrate this technique in Appendix H.

We would also like to note that we consider a different setting from Laurent and von Brecht by considering the square loss rather than the hinge loss. When we restrict the hinge loss to a given activation region, the loss is locally given by an affine function, so there are no critical points on the interior of the region. In contrast, when using the square loss, the loss restricted to an activation region is given by a quadratic function, so a more careful analysis is needed.

Most results in the paper only prove that for most activation regions, "all critical points are global minima”. If we take a closer look at it, the theorems do not talk about the existence of critical points in these regions; they may or may not exist. Therefore, the statements cannot rule out the following pathological scenario: critical points do not exist at all in the fraction of the linear regions and the fraction of the regions contain bad local minima. In order to make the results stronger, a more complete characterization of the existence of critical points should be helpful.

We address the issue of the existence of global minimizers in Theorem 12, where we show that with one-dimensional inputs, most activation regions contain global minimizers. In the one-dimensional case, we are able to show that $d_1 \sim n \log n$ is sufficient parameterization for most regions to have a full rank Jacobian and for the existence of global minima, with the existence of global minima requiring a constant factor of additional parameterization. For the higher-dimensional case, we provide experiments (in Appendix E.2) which confirm that approximately linear scaling of $d_1$ with $n$ is sufficient for most regions to contain global minima.

Some directly relevant citations are missing

Thanks for highlighting these references. We have added pointers to these works in the introduction.

We thank the reviewer for their helpful comments which we address in our comments below and in the additions to our paper. In light of these improvements, we hope that you might consider increasing your score.

The setting described at the beginning of section 3 is different from a typical 2-layer ReLU network in that only one weight matrix is considered as parameters. It would be helpful to clarify whether including $v$ in the parameter space changes the conclusions in Theorem 5.

We focused on computing the gradients with respect to the input weight matrix rather than the output head to facilitate our analysis. However, we would like to emphasize that our results showing that $\nabla_W F$ is full rank also imply that $\nabla_{(W, v)}F$ is full rank, since the former is a submatrix of the latter. In particular, our conclusions still hold when we include $v$. We have added a new Appendix G in which we analyze the effect of parameterizing $v$ as well as an extension to non-differentiable critical points.

While smooth critical points are global minima in most of the activation regions, it is not clear what the volume of these regions are. In particular, results in this paper do not rule out the possibility that the small number of regions with bad local minima make up most of the parameter space.

Some of the methods we used to enumerate the activation regions with full rank Jacobian can be adapted to compute the volumes of such regions. We have added a new Appendix F illustrating this. For the one-dimensional case, we compute the volume of each activation region as a function of the dataset. We also bound the amount of parameterization needed for most of the parameter space (by volume) to have full rank Jacobian in terms of the separation between the data points. For the higher-dimensional case, we introduce an anticoncentration property of the data. Under this property, we prove that the portion of the loss landscape with full rank Jacobian is large by volume.

Despite interesting theoretical results, there is not much discussion on the implication on neural network training. As the authors also mention, this paper has not formalized how most regions having not bad local minima in their interior leads to gradient descent’s success in finding the global minima.

From an optimization perspective, one significant benefit of most regions having full rank is that the neural tangent kernel in those regions is strictly positive definite. This means that while the parameters of the network remain in those regions, gradient flow will decay the square loss at an exponential rate.

The beginning of the second paragraph of section 6 states that a ReLU with one input with bias is equivalent to a ReLU with two input dimensions and no bias. Could the authors add a bit more explanation, as this equivalence does not seem straightforward?

For a neural network on one-dimensional data with bias, each neuron is a function of the form $x \mapsto b + wx$. Instead, we could think of the data point $x$ as an element of 2-dimensional space, writing it as $(1, x)$. Then the mapping is of the form $(x_1, x_2) \mapsto bx_1 + wx_2 = (b, w)^T(x_1, x_2)$. The same trick applies in higher dimensions as well.

``Are the constants in the bound known? Can they be quantified in experiments?"

For the one-dimensional case, we include the constants in our bounds for Theorems 10 and 12. For the high-dimensional case, we rely on a bound from Bourgain et al. [1] which states that the probability of a random $d \times d$ matrix being singular is at most $(1 / \sqrt{2} + o(1))^d$. Recovering the exact constant from this bound is challenging. However, the exact scaling can be checked experimentally, as we demonstrate in our experiments in Section 7. For example, Figure 3b shows that if we use the scaling $\frac{n}{d_0} = 2$, then $d_1 \approx 7$ is sufficient for at least 80 percent of activation regions to have no bad critical points. Note also that for fixed $\epsilon$, if $\frac{n}{d_0} \gg 1$, then Theorem 5 implies that $d_1 = \frac{n}{d_0}$ is sufficient for most regions to have a full rank Jacobian.

This paper shows that most activation regions do not have bad local minima in their interior. Do there exist non-differentiable points that are local minimizers? If so, will these points cause problems for gradient descent?

Indeed, there can exist non-differentiable critical points which are local minimizers of the loss. We have added Appendix G to address this question, where we establish that in most activation regions, the set of spurious non-differentiable critical points forms a low-dimensional subset of the region.

Thanks for your helpful comments and suggestions. We address each of your points below.

The assumption of 2-layer network with fixed last layer weights is restrictive and impractical. The paper only discusses differentiable critical points, but there can be a lot of indifferentiable critical points depending on network settings.

We have added appendices to address non-differentiable critical points and trainable output weights (Appendix G) as well as the deep case (Appendix H). Although our focus has been on the two-layer case, our techniques can be used to understand more general settings. Even when looking at non-differentiable points of activation regions, we can show in the one-dimensional case that most regions have no spurious local minima. To generalize to the deep case, one can compute gradients with respect to individual layers of the network and find conditions on the activation patterns for which the gradients are full rank. We demonstrate this technique in Appendix H. In Appendix F we now also discuss the volume of activation regions, providing further insight in regard to the comment "most of the landscape".

It seems to me that in figure 9(b) GD does not converge to good local minima when network is only mildly overparameterized, despite at initialization the Jacobian has full rank. Can you explain this? Does this contradict your theoretical findings?

This experiment agrees with our theoretical results in the sense that when the network width $d_1$ scales linearly in the sample size $n$, gradient descent converges to a global minimizer with high probability. The amount of parameterization necessary for convergence to a global minimizer appears to be a constant multiple of the amount necessary for a full-rank Jacobian at initialization.

How do you determine whether a Jacobian matrix is full rank?

We compute the Jacobian and its rank with PyTorch. The method torch.linalg.matrix_rank computes the SVD of the Jacobian and counts the number of singular values which are larger than a fixed machine tolerance.

For figure 9(a) is the network overparameterized at all? The experiment setting for figure 9 is not clear to me. Can you elaborate on this, just like what you did for other figures?

Yes, the network is overparameterized in this experiment because the number of parameters is given by $m = d_0d_1$, where $d_0$ is the input dimension and $d_1$ is the hidden dimension. Here the dataset, MNIST, consists of images represented by 784-dimensional vectors. Hence the hidden dimension (network width) does not need to be large for the network to be overparameterized. We have updated the paper to clarify this by adding the comment "The number of network parameters matches the training set size $n$ when the width satisfies $d_1=n/d_0$, where for MNIST the input dimension is $d_0=784$."