Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of learning the parameters of a two-layer ReLU network with a residual unit: given samples of the form $(x_i, y_i)$, with $y_i = B^*[(A^* x_i)^+ + x_i]$, the authors provide an algorithm that provably learns $A^*$ and $B^*$, as the sample size grows. It is crucially assumed that the entries of $A^*$ are non-negative and, by exploiting this fact, the learning problem is formulated via quadratic programming (QP): the authors show that there exist quadratic functionals whose minimisers can be used to deduce the ground-truth parameters. Furthermore, the QPs are re-written as linear programs (LPs), which are simpler to optimise and have the same solution space. Numerical results demonstrate the superiority of the proposed approach with respect to gradient descent methods.  
main_review: STRENGHTS:

(1) The problem is timely: residual networks have enjoyed great popularity in practical applications, but from a theoretical perspective, many basic questions about their optimization are still open. 

(2) The algorithm is novel and its computational complexity is polynomial in the number of samples, due to the QP (and, subsequently, LP) simplification. As for the dependence on the number of samples, the algorithm is consistent (the error vanishes, as the sample size grows), it significantly improves upon the vanilla linear regression and the numerical simulations also show a significant improvement over gradient descent.

----------------------------------------------------------------

WEAKNESSES:

(1) The whole paper (starting from the vanilla linear regression to the non-parametric learning of the two layers) is based on the fact that $A^*$ has positive entries. This assumption is rather restrictive, not particularly practical, and it simplifies the problem significantly. As the paper appears to rely strongly on this assumption, it is not clear at all to me whether the methods discussed here can still work for a more general choice of $A^*$. 

(2) The sample complexity is only briefly discussed in Appendix D: here, the authors provide some rather heuristic arguments to justify that the sample complexity is polynomial (as opposed to vanilla linear regression whose sample complexity is exponential). I understand that, ultimately, in order to get a convergence speed result, one has to make assumptions on the data distribution. However, I guess that also the vanilla linear regression is a consistent algorithm, so proving just consistency appears to be a rather low bar. In order to fully understand the power of the QP/LP simplification presented here, the authors should make assumptions on the data distribution and show sample complexity results (instead of only giving experimental evidence). 
summary_of_the_review: While I generally appreciate the problem tackled in this paper (provable optimization of two-layer ReLU residual networks) and the idea of re-writing the learning problem as a QP (or even LP), unfortunately the paper in its current status appears to be (slightly) below the acceptance bar, because of the weaknesses (1)-(2) mentioned above.

On the one hand, weakness (1) seems to be inherent to the approach pursued in the manuscript (but I would still appreciate if the authors could comment on it and suggest possible ways to overcome it). On the other hand, weakness (2) does not seem fundamental, but it would require additional work. I encourage the authors to pursue the direction of giving concrete sample complexity bounds since, in my opinion, it would add value to their paper. This would mean not only to show that the sample complexity is polynomial, but also to understand the degree of such a polynomial. It would also add value to provide simulation results that indicate a certain polynomial dependence of the algorithm on the number of samples (e.g., linear, quadratic, etc) -- even better if the simulation results confirmed the theoretical bounds.

A couple of other comments are below:

(a) The discussion on the computational complexity is deferred to Appendix B. I think that this part is actually important and I would suggest to discuss it directly in the main paper. This is especially important if the authors are able to obtain sample complexity bounds, since the computational complexity bounds would be complementary to them.

(b) The input distribution chosen for the numerical experiments (mixture of N(-0.1, 1) and U(-0.9, 1.1)) seems a bit ad-hoc. Do the results change for different input distributions? (say only Gaussian, only uniform, and as a function of the mean of the Gaussian and of the uniform distributions)

(c) Page 7. nonparamatric --> nonparametric
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper gives an algorithm for learning two-layer neural networks with ReLU activation (realizable case). The network also consists of skip connections to avoid the problems of identifiability. As a warm up, the authors first give a simple algorithms based on linear regression, whenever enough samples could be observed with all-positive and all-negative entries. 

They start with an algorithm for recovering the layer two parameters. For this step, they use the $\ell_2$ loss and show that its minimizer is unique and matches with the ground truth parameters under certain condition. Subsequently, the authors replace the expectation in the objective with an average over the samples (based on the empirical risk minimization principle), which they could write as a convex quadratic program without making any parametric assumption. Finally, they show that the quadratic program can be equivalently written as a linear program, which lets them recover the parameters of the second layer (in fact the inverse matrix of this weight matrix).

Once layer 2 is learnt, the original problem reduces to that of learning the single layer non-linearity. They write the objective as a sum of weight estimator and a function estimator. They show that the minimizer of this loss is achieved when the estimated weight matrix is a diagonal matrix times the ground truth and the function measures the difference between the true nonlinear function and the scaled wright matrix. Again, they learn the function non-parametrically using a quadratic program, which they equivalently write as a linear program to get the scaled weight matrix. The scaling factors in the diagonal matrix can then be learnt using a linear regression.

Finally, the authors conduct extensive experimentation to validate that their algorithms performs superior to the vanilla SGD-based algorithm. They also show that their algorithm, especially the QP algorithm is robust to noise.
main_review: Strengths: The proposed techniques are simple and lead to easy-to-implement algorithms. Also, it is interesting to know that an algorithm apart from the SGD works well for learning the parameters. The theoretical results are well-supported by experiments.

Weakness: One concern I had is that the authors solve the problem of learning the layer 2 parameters by learning its inverse matrix. Computing matrix inverse may bring in numerical issues and ill-conditioning problem. I would have liked if the authors had done some experiments regarding this. Are there cases where learning the weight matrix itself instead of its inverse may lead to better performance? Another limitation of the paper is that there are no finite-sample guarantees, as opposed to asymptotic guarantees.
summary_of_the_review: Understanding theoretical properties of neural networks is a major unsolved problem in learning theory. Considering that, this paper makes an important progress using simple algorithms and techniques. Although setting is somewhat simple, I felt the results should be encouraged. It would be interesting to extend this result to more complicated classes of neural networks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the author describes an algorithm that learns a two-layer residual unit/network with ReLU activation in a teacher-student setup, under the assumption that the first-layer weights are nonnegative (without specific assumption on the data distribution), and shows that the student network is able to recover the teacher parameters in the infinite data limit (Theorem 6.2 and 6.3). 
main_review: The paper is in general in good shape, I've not checked the details of the proof, but the main lines of arguments and numerical results in Section 7 look compelling. Related previous efforts are appropriately discussed. 

From a technical perspective, this paper contains some interesting ideas that are, I would say, inspired by previous efforts but adapted to the problem under study.

Since one of the major contributions of this work is that the results do not rely on strong assumptions on the data distribution, it would be of interest to provide numerical experiments on more "realistic" data and tasks (instead of the toy model presented in Section 7).
 
summary_of_the_review: The major novelty and contribution of this work lies in the study of the residual unit model, without relying on the assumption on the (specific) data distribution. The paper contains some interesting ideas that would be of interest in the study of more involved neural network models.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: 
This paper considers the special case of two-layer ReLU residual units and introduces a nonparametric convex approach to optimize the training objective. The experiments also highlight the effectiveness of the proposed approach with respect to SGD applied to the original non-convex training objective. 


main_review: The paper is mostly well written, however, there are issues requiring further discussions and explanations. See below for my detailed comments:

* Can the authors comment on the ground truth parameter assumption? This does seem quite restrictive to me since it precludes any scaling/permutation invariance which is one of the main challenges in neural network training problems. Is this really necessary for the analysis if so where exactly?

* The authors cited a series of papers training shallow neural networks via convex optimization, e.g., (Pilanci & Ergen, 2020), what are the advantages/disadvantages of the proposed method here compared to the ones in these papers? I think there should be a detailed discussion regarding this comparison?

* In Appendix B, the authors provided a complexity analysis of the algorithm, however, I think they should also include a comparison with respect to the standard SGD applied the non-convex training problem and some baselines e.g., (Pilanci & Ergen, 2020) also proposed a convex approach with a polynomial complexity in the problem parameters.

* After solving the nonparametric problem is there a way to recover a proper two-layer Residual network parameters? Does that require solving additional problems? If so can you provide some details, e.g., computational complexity?

* Since the proposed method is nonparametric, how do you obtain the estimates during the inference time? Do you need to solve additional optimization problems?

* I appreciate the experiments provided to verify the theory, however, there should have been some experiments on real benchmark datasets. Are there any specific reasons preventing such experiments, e.g., the scalability of the algorithm to larger datasets?  

-Pilanci M, Ergen T. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. ICML 2020
summary_of_the_review: I think that the main contribution of this paper is incremental due to the following reasons. First of all, the model seems to be so simple that it even doesn't allow permutation and/or scaling invariance. Moreover, the paper lacks satisfactory comparative experimental analysis.
review_title: null

Meta-review: In this paper, the authors propose a non-parametric approach for learning a two-layer neural net. I agree with the authors and reviewers that this is a timely problem. However, the solution in this paper come short of achieving this goal. In particular, the assumtions are very strong and cannot be generalized (e.g., non-negativity). The authors also need to better spell out the sample complexity.
Decision: Reject