Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies empirical risk minimization (= minimizing training error) in two-layer neural networks under mean squared error, in the mildly over-parameterized regime where the number of network parameters is linear in the sample size. The main contributions of the paper include: 1) a symmetric LeCun initialization, 2) under which neighborhoods of the initial hidden layer weights include a global minimum with zero error, and a 3) constraint optimization problem whose KKT points are approximate global minima of the empirical loss.
main_review: + Writeup quality: I think there is room for improvement. Here are some suggestions:
- Repetitions: there are several instances. For example, the jacobian is defined twice, in lines 37 and 108. Feature matrix is defined in lines 55 and 110. Remark 1, “When d>2, Theorem 1 is applicable to narrow networks with m<n” is stated right before the theorem in line 122.
- Clarity: some wordings are sloppy. For example, the challenges listed in lines 64-72 are not very precise. What do you mean by a “solution”? To me, a solution corresponds to a particular network parameterized by weights (w,v). Then how can a network be “expressive”? Expressiveness is a property of a class of functions, not a single function. Therefore, I do not completely understand what you mean by “expressive solutions” in these three bullet points.
+ Some other minor comments on the writeup:
- Footnote 1, page 1, do you mean Chen et al.?
- Line 58: whether *an* global-min
- In algorithm 1, step 1, “i” only needs to go through 1,...,m/2, right?
- Figure 5 and 6 are difficult to read; it helps if you use larger font sizes.
- The quality of the plots are not great, and they can be fixed easily. For example, in Figure 6, why not dedicate the whole space to the plots by including the legend inside the figure? You certainly don't need to repeat “Test acc: Our training regime with ” in every legend for every curve.
+ Assumptions: Assumptions 1 and 3 are reasonable. Assumption 2 is very confusing. On one hand, it requires the nonlinearity to be zero at the origin (sigma(0) = 0). On the other hand, it requires sigma(0),sigma’(0),...,sigma^{n-1}(0) to all be non-zero, which is a contradiction. I assume this is a typo -- please clarify. I also found the assumption -- at least the way it’s currently stated -- to be odd in the sense that the requirements on the nonlinearity become more stringent as the sample size increases.
+ Statement of Theorem 1 is a bit confusing. Isn’t “every stationary point” in line 133 redundant? Because you follow up by saying that the gradient at that point is zero. Also, because the theorem statement does not quantify epsilon whatsoever, I assume that it holds for any epsilon. Then, the second part of the theorem essentially reads as: “no spurious local minima if v is not elementwise zero”. Does it not contradict landscape results in the literature that establish existence of bad local minima? In any case, it would be helpful if you add a discussion on that.

Weakness:
- The paper merely focuses on the optimization aspect, that is, minimizing the training loss, and ignores the more important problem (from ML perspective) of generalization. It would have been helpful if the authors include a discussion on the implications of these results on the generalization error as well.
- Also, the paper does not provide any convergence guarantees; therefore, the claims about the “trainability” of models with m < n in the introduction are not well supported.
- The “trainability” results -- ignoring the fact that there are no computational const analysis or guarantees in the paper -- suggest that the proposed initialization+PGD framework for solving the constrained problem will only (if at all) yield a epsilon-subotimal minima if the hidden weights remain epsilon-close to the initialization. This, in essence, is not desirable as it does not allow learning representations which is crucial in deep learning. Also, this is conceptually similar to the requirements in the NTK / lazy regime, with the difference that those results offer precise convergence rates.
- Experiments: A lot of important information about the experimental setting is missing. What is the learning rate scheme for SGD? What is the initial learning rate? What is the mini-batch size? Have you tried initialization schemes other than LeCun’s? Also, the plots look very noisy to me, as they are only averaged over two independent runs. Figure 5 is very confusing. How does “constraint size” come into play in “regular training”? As far as I understood, according to line 271, this is just “unconstrained GD-based method with LeCun’s initialization”, where no constraints are in effect. In figure 6 in section 4.2, if the goal is to “further evaluate your theory”, why is the “test accuracy” plotted, and not the “training loss”?

Overall, in my opinion, the merits of the paper outweigh the drawbacks. However, given my detailed comments above, the paper is borderline. Therefore, I vote for a marginal accept. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tries to understand neural network (NN) expressivity (interpolability) and trainability, i.,e effectiveness of (proposed) training procedures in the underparameterized regime, i.e, m < n, where m is the width of the NN and n is the number of samples, albeit for 1 -hidden layer neural networks and activation functions (except ReLUs).

The problem is important since, a majority of existing literature focuses on the performance in the overparamterized regimes or expressivity alone.

Under some assumptions on the architecture of the NN, the activation function and when $m > \frac{2n}{d}$ and $m < n$, they show by careful initialization of the weights (mirrored Lecun initialization), any stationary point is a minima of the training loss in a small radius around the initialization. Furthermore, they propose a modified projected Gradient descent algorithm, whose stationary points approximately, minimize the training loss (with probability 1). 
main_review: The use of the Inverse Implicit function theorem in this context seems new to analyze the loss landscape around the initialization and show the existence of the global minima in a ball around the initialization.
In addition, they show that under the assumptions, narrow networks can be trained with a modified projected gradient descent algorithm, that ensures to preserve the properties of the Jacobian matrix around the initialization.
The initialization is simple and these techniques seem to be useful in analyzing the m < n regime.

However, below are some questions and some concerns:
1) I believe expressivity in the sense defined by Telgarsky 2016 and related papers (Chatziafratis et al. 2019,2020) provide a function and (family of functions resp.) where shallow networks (where the depth can be greater than 1 but o(L) , where L is a parameter indicating composition of functions), require exponential width to express these functions, which signifies some fundamental benefits/limitations of deep/shallow networks. Here the problem is to study trainability and interpolation properties of narrow networks (which are still beneficial).
2) Can the assumption about the even number of neurons be removed? Let's say by setting the weight in the middle to be 0?(naively), so that initialization holds.  
3) Does the same method and initalization work in practice with ReLU neurons?
4) What can be said about the d=1 and d=2 cases? when m < n? Of course, in practice it is interesting to analyze behavior in high-dimensions, but it would be interesting to understand the challenges here.
5) The IFT as far as i understand guarantees the existence of a radius around w_0 (maybe a small radius). Can something be said about the radius, as the Theorem 2 uses this radius in the constraints. Also, it seems like sometimes a larger radius helps in the test-accuracy for some problems. What would be the advice on setting the radius?
6) Finally, it is not clear if PGD always converges for non-convex problems. In practice, what are some things that are useful in the aspect?

References:
Telgarsky, Matus. "Benefits of depth in neural networks." Conference on learning theory. PMLR, 2016.
Chatziafratis, Vaggos, et al. "Depth-width trade-offs for relu networks via sharkovsky's theorem." arXiv preprint arXiv:1912.04378 (2019).
Chatziafratis, Vaggos, Sai Ganesh Nagarajan, and Ioannis Panageas. "Better depth-width trade-offs for neural networks through the lens of dynamical systems." International Conference on Machine Learning. PMLR, 2020.

limitations_and_societal_impact: See above for limitations. The authors have adequately addressed the social impact of their work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies narrow 1-layer neural networks with respect to their expressivity and trainability. More precisely, the authors prove a lower bound for the width of such networks so that in the optimization landscape one global minimum does exists and can be found by using a specific training regime based on a mirrored LeCun's initialization. Several numerical experiments show superiority of this approach for such classes of neural networks.
main_review: Ensuring trainability of narrow neural networks is of key importance when "small" networks are required due to, for instance, limited memory. This paper not only provides an analysis for the 1-layer setting, but also very nicely combines it with expressivity considerations, which is intriguing both from a conceptual viewpoint and also beneficial for solving this problem. The authors are able - in the considered setting - to also introduce a training regime for which they can prove success in the sense of reaching the global minimum. Interestingly, they here rely on a mirrored LeCun's initialization, which now for the first time is linked with expressivity as well. Hence, to my mind, this is a relevant paper from various viewpoints. 

I just have a few minor comments, in addition, to the comments in the next part:
* Various articles are wrongly used. This would be good to check again.
* Line 22/23: It would be helpful to say where \theta on the right hand side of (1) appears. This is only mentioned later on.
* The writings in the figures is too small such as in Figure 1.
* The term expressivity is used often, but in a vague sense. It would be nice to be more precise about what is meant, and in particular, include a definition for the term "strong expressivity".


The authors addressed my comments successfully, and I will keep my (positive) rating.
limitations_and_societal_impact: Limitations:
* The current analysis is only for 1-layer neural networks. This I don't see as a problem, since first it is highly difficult to derive results of such a type and thus nice to see that at least in this setting this is possible, and second in Subsection 3,4 the authors do point out some ideas on how to extent is to deep networks.
* The current analysis is only for smooth activation functions, and, in particular, does not include the ReLU. If a review is requested, I would ask the authors to comment on possibilities on how to include the ReLU in their analysis. 

Societal Impact:
* This analysis and the provided training algorithm are a key step towards memory-efficient, yet trustworthy neural networks.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers narrow (width<input dimension) neural networks with one hidden layer. In particular, they consider a special intialization scheme and show that as long as the network width $m$ is at least $\frac{2n}{d}$ where $n$ is the sample size and $d$ is the dimension, then such network can memorize full samples. Moreover, they propose a constrained formulation of the training problem and show that every KKT point is approximately a global minimizer, so the trainability is guaranteed. They also conduct experiments to support these theoretical findings.
main_review: Originality: 
The expressivity and trainability of neural networks have been studied for long, yet most of existing works focus on 'large' networks and the setting considered in this paper is rather less touched. It's quite surprising at first glance that such small networks can memorize full samples.

Quality: 
The proofs are intuitive and written in a friendly manner. Proof sketches are good. The use of IFT is clever. However, the mirrored LeCun’s initialization is purely technical and only serves to make $f(w_0;v_0)=0$ for the use of IFT.

Clarity: 
This paper is overall well-written and easy-to-follow.

Significance: 
In my opinion, the results of this paper are interesting from a theoretical viewpoint, but lack potential impact on practice. The reasons are twofold. First, memorization of training data is not the main concern of practical algorithms, and actually most algorithms can fit training data easily. Generalization of such narrow neural networks is more important, and in fact a seemingly promising direction, as narrow networks should have smaller complexity. Second, such 'compact' network structure is rarely used in practice, and the results don't appear to be able to help explain the success of deep learning.

Other comments:
The section on extension to deep networks seems unnecessary.

The first result of this paper is merely memorization of training data, rather than expressivity as claimed by the authors. Expressivity measures the ability of the model to express various functions.

As a result, the authors should also cite previous works on memorization of training data, such as 
'Understanding deep learning requires rethinking generalization',
'Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity'.
Since this paper discusses 'expressivity' of narrow neural networks, previous works on this topic should be included in the bibliography as well, for example:
'The expressive power of neural networks: A view from the width'.

limitations_and_societal_impact: The authors address the limitation of this work that only neural networks with one hidden layer are considered. It would be better if authors can include generalization results or at least a discussion on this topic.
review_title: null

Meta-review: This paper considers the loss landscape of relatively narrow neural networks with 1 hidden layer. Specifically, the regime is that the width is at least the number of datapoints divided by the input dimension. The authors prove the existence of a global optimum that perfectly fits the training data, with at least a small neighborhood around this point within which training converges. The reviewers agree that this is an valuable contribution, with the width of the networks in question large enough to be interesting while being far from existing work, which often focuses on extremely wide networks. While nets with just 1 hidden layer are of course quite simple, this is nonetheless an advance from prior literature. I accordingly recommend acceptance. The reviewers note that the authors do not offer convergence guarantees except in the vicinity of the optimum, which should be made clear in the abstract and introduction to avoid any possibility of misunderstanding to the reader.
Decision: Accept (Poster)