Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a combinatorial view of optimizing shallow (two-layer) ReLU networks. The authors show that optimizing a shallow ReLU network is an NP-hard combinatorial optimization problem, and existing optimizers such as gradient descent are performing some local combinatorial search. The authors then present a greedy search method to exploit the combinatorial optimization nature, and it outperforms gradient descent in experiments. 
strengths_and_weaknesses: **Strengths**
1. The combinatorial modeling perspective of the learning process of shallow ReLU networks is novel and interesting.
2. The theoretical analysis and insights presented in this paper seem sound. For example, the authors present explains the relationship between the NP-hard difficulty found in this paper and the recent theoretical results that optimizing overparameterized deep networks is feasible in polynomial time. 
3. Empirical results are provided to ground the theoretical findings. The proposed greedy search method for shallow ReLU networks is interesting. 

**Weaknesses**
See "Questions"
questions: 1. Is it possible to compare other optimizers like SGD?
limitations: The limitations are addressed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: 
This paper uses methods from polyhedral combinatorics to study the optimization landscape of Shallow ReLU networks. 
By associating a proper combinatorial object (zenotope) with an instance of minimizing the training error of a ReLU the authors show 
that hardness results may be non robust and might break under small perturbations. Another contribution is to use the zenotope  
to introduce a local search algorithm and demonstrate experimentally that it can outperform local search. 
strengths_and_weaknesses: I like the idea of analyzing hard instances arising from NP hardness proofs. However the paper falls short to prove or disprove whether 
NP hardness results are robust in the sense that they may hold for non-degenerate data sets (that can be obtained by random perturbations). Without a resolution of this I find the contribution of the paper to be below the bar of NeurIPS.
questions: If I recall correctly, the paper of Vu regarding the hardness of training shallow networks argues that the hardness results there should persist even if the training points are in general positions. Doesn't this indicate that the optimization problem for perturbed data sets should be hard as well? Personally I think it would be surprising (though not impossible) if the hardness results for training shallow networks would break under (small amounts of) noise. 
limitations: A lack of a proof of a new fact of significance.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper illustrate that the global optimization of a two-layer ReLU network can be characterized as a combinatorial search over the vertices of the zonotope which is isometric to all feasible activation patterns. This perspective is utilized to show that the global optimum of two-layer ReLU network is discontinuous with respect to the training data. They also interpret the overparametrization as the random sampling over the zonotope vertices. A novel heuristic algorithm of greedy local search over the zonotope vertices is introduced and numerical results show its advantage over the gradient descent method. 

strengths_and_weaknesses: Strength:
- The idea of connecting the optimization of ReLU networks with vertices in the zonotope is very interesting. 
- The numerical comparison between the greedy local search heuristic and gradient descent algorithm illustrate the strength of the proposed heuristic algorithm. 

Weakness:
- This is a theoretical paper but the theoretical contribution of this paper is hard to interpret. There are no formalized theorem or proposition in the paper. It will be very helpful if the author can organize their main contributions into theorems. 
- The authors show that when the training data is in general position, the global optimum of the training set is continuous with respect to the training data. But what is the implication of this result?  
- The discussion of over-parameterization in section 4.2 only provides a heuristic that the random vertex selection can work and this is only numerically verified. Some solid analysis about why the random vertex selection works will greatly strengthen the paper. 

questions: The authors shall formalize their main results in the theorem or proposition environment. 

For Figure 3, as the proposed greedy local search heuristic is a randomized algorithm and the initialization of the gradient descent is at random, the authors shall plot the heat map of multiple trials instead of showing the result for a single trial. For instance, in the lower part of the figure 3, by increasing the number of units from 16 to 32, the final training accuracy of mGLS decreases. This may result from the random seed. 

Some literature are missing. The concept of zonotope is utilized in the optimization of two-layer ReLU network in [1,2]. The global optimization of the training problem two-layer ReLU networks with the standard $\ell_2$ regularization can also be formalized into the search over all possible activation patterns, see [3,4].

[1] Bach, Francis. "Breaking the curse of dimensionality with convex neural networks."
[2] Misiakos, Panagiotis, et al. "Neural Network Approximation based on Hausdorff distance of Tropical Zonotopes."
[3] Pilanci, Mert, and Tolga Ergen. "Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.”
[4] Wang, Yifei, Jonathan Lacotte, and Mert Pilanci. "The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions."

limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of optimizing a shallow ReLU network. The authors characterize the combinatorial structure of this problem via a zonotope whose vertices correspond to the feasible activation patterns of the network for a given training dataset. They use this characterization to provide some new insights and results on shallow ReLU optimization. In particular, they show that a necessary condition for the global optimum of a shallow ReLu network to be discontinuous is for the training dataset to have non-trivial affine dependencies. This implies that existing NP-hardness results do not trivially apply to datasets in general positions (i.e., no non-trivial affine dependencies between training examples). They also explore the relationship between over-parameterization and optimization difficulty. They provide empirical evidence that over-parameterization increases the likelihood that a randomly chosen vertex will contain a good solution. They propose a polynomial-time vertex selection algorithm which finds the global optimum using only $\Omega(2 N)$ parameters, which improves over existing bounds on the amount of over-parameterization needed. They further introduced a greedy local search heuristic which outperforms gradient descent on  some toy datasets.
strengths_and_weaknesses: Strengths:
- Novel characterization of the optimization of shallow ReLU networks which enabled the authors to provide interesting and novel results which further our understanding of neural networks training, and can be useful for future research.
- Paper is well written with results clearly presented overall (the clarity of some sections can be further improved, see Questions for details)
- A helpful overview of the mathematical concepts used is provided in the appendix.

Weaknesses:
- Results only apply to shallow ReLU networks.
- The proposed greedy local search heuristic is too expensive to be used in practice on large real-world datasets.
- Empirical results only on toy datasets, and no comparison with other existing works.
questions: Questions:
- Why no results on real-world datasets are provided? Is the proposed heuristic already too expensive for datasets like CIFAR-10?
- Why do you use GLS on the synthetic data and mGLS on the MNIST and Fashion MNIST derived data, and not mGLS on both?
- What is meant by "ill-conditioned" on line 299? it is helpful to include some empirical results to illustrate this point.

Suggestions:
- Include timing results in the comparison of gradient descent and mGLS.
- Add a comparison with the heuristic algorithm of Dey et al. (2020).
- Change the x-axis of the Fashion MNIST to over-parameterization factor, in both Figures 2 and 3.
- Paragraph on lines 202-209 is not very clear. It would be good to provide further details with formal mathematical descriptions of the two cases. 
- Typo in Eq. (3): $2 (a_i - 1) \rightarrow (2 a_i - 1)$
limitations: The authors discussed limitations of their work in the conclusion. There's no direct negative societal impact as this work is mostly theoretical.
review_title: null

Meta-review: metareview: Thank you for your submission to NeurIPS. 

This work presents a combinatorial view of training two-layer ReLU networks.

The reviewers and I, after the author response, are in agreement that there are interesting and strong contributions in this work. Namely, it is shown that global optimization of a two-layer ReLU network can be characterized as a combinatorial search over the vertices of a zonotope. This is used to show that the global optimum of two-layer ReLU network is discontinuous with respect to the training data. Four knowledgeable reviewers recommend accept/borderline accept, and I concur, in light of the contributions made.

The reviewers also noted some minor weaknesses: In particular, the reviewers noted that 
(1) results only apply to two-layer ReLU networks
(2) proposed greedy local search heuristic is too expensive to be applied on modern datasets.


Please take into account the updated reviewer comments, including suggested additional references, when preparing the final version to accommodate the requested changes.




confidence: Certain
Decision: Accept