Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The draft is a vector extension of [1] on studying how to approximately solve the global optima of a two-layered Relu network. The key of the analysis is to enumerate all possible sign patterns of the ReLU unit generating from specific data. Once we have the enumeration, we can also enumerate the linear area separated by ReLU, and the whole optimization problem will become a non-convex quadratic optimization problem. The non-convex quadratic can be approximately solved with its convex dual (or exactly under some conditions), or we can relax it to a copositive program (which might still be NP-hard to solve). With some assumption on the data, the sign pattern of the ReLU is a singleton, then we will have efficient algorithms to exactly recover the global optima of the two-layered network.

I like the idea of linking 2-layer NN with copositive programs, the writing is good, and the proofs seem to be correct.
However, I feel that the study on the whiten case with a singleton ReLU sign pattern is really not useful. When all the sign patterns of the ReLU are pinned, the representation power of a two-layered network reduces to a linear model (in a polyhedron). And if the representation power is equivalent to a linear model, why not reparameterize it linearly? The specific case lost all the existential meaning for a ReLU unit. (prove me wrong by showing it is better than linear in experiment.) 

Overall, this is a good extension of [1], but the improvement in complexity only works in trivial case.

Minor issues:
1. (Algorithm 1, (b)) The uj gj is undefined. The sj^(k) is not used anywhere.
2. (equation at the bottom of p.18) Misisng sqrt{}
3. Compleity below Section 4.2: enumeration takes O(n^r), but solving a copositive program is still NP.
4. (Algorithm 1) It takes me a while to realize how the Frank-Wolfe algorithm works for the $\sum_i|Vi|\leq t$ constraint. Maybe it can be more clear.
5. (Writing) There are many reference to appendix without specific section number... Please add them.

[1] Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks. Mert Pilanci and Tolga Ergen
review_title: Good extension, but studying the whiten case is not useful (concerns answered in the author feedback).

final_score: rating: 7: Good paper, accept
review_content: ## Summary
The paper proposes a convex formulation for shallow neural networks with one hidden layer and vectorial outputs. This is an extension on a line of previous works (Ergen & Pilanci, 2020a) and (Ergen & Pilanci, 2020b) where similar results have been established for the case of scalar outputs. A Frank-Wolfe algorithm for finding the global optimum of the resulting convex program is proposed and evaluated on smaller datasets. 

## Explanation of Rating
Overall, the paper tackles an important problem, is technically sound and well-written. I recommend acceptance of this paper, but have some smaller doubts which are mainly due to the incremental nature of the results (see detailed comment #1) and the strong assumptions for the proposed relaxation to be exact (see comment #2).

## Detailed Comments
1. My main concern with the paper is, that it is a direct extension of the results from (Ergen & Pilanci, 2020a) and (Ergen & Pilanci, 2020b) to the vectorial setting and therefore lacks novelty. Therefore, I feel the results presented in this paper might be better suited for a journal version of these previous works. 

2. The tightness guarantee for the relaxation requires the number of hidden neurons to be larger than the number of data points. In practice, this assumption is often not satisfied. The paper would be stronger if there was some theory (e.g. a duality gap analysis) that quantifies how the quality of the relaxation degrades as the number of data points is increased.  



review_title: Incremental generalization of recent results in the convexification of neural networks to vector outputs

final_score: rating: 7: Good paper, accept
review_content: Summary: This paper generalizes the results of Pilanci and Ergen (2020) showing that the non-convex optimization problem corresponding to the training of a one-hidden-layer muti-output ReLU neworks can be solved using convex programming. In particular they show that the problem has (I) a finite convex bidual that can be solved efficiently using some variant of the Frank-Wolfe algorithm and (II) a convex strong dual given by a copositive program. Unfortunately in the general case the complexity is exponential in the rank of the data matrix. A spike-free assumption is introduced that facilitates things and allows polynomial time algorithms, however this assumption is pretty strong and I doubt it is useful in practice as it makes the training 'almost' equivalent to training a linear classifier. Some references are missing as the problem is related to the low-rank matrix factorization problem. The notation in some critical parts of the paper is not clear and makes reading difficult.

I would like to start saying that I am open to increasing my score (**Update: score updated after author feedback**) if the authors are able to clarify notation and add references/discussion, because I think that the essential contributions of this paper are important

Pros:
1. Quality/Significance: The paper continues the vein of previous convex reformulations of the training of ReLU networks of Pilanci-Ergen (2020), extending the results of the single output case to multi-output which is arguably the interesting case in contemporary applications of Deep Learning. It opens the way to certified global optimality of solutions via convex programming of ReLU networks, and provides insight into the fundamental complexity of the optimization problem in nonconvex (factored) vs
convex form.

2. Originality: There are few papers trying to understand the connections between the nonconvex formulation of the training of ReLU networks with convex formulations that provide certified optimality. For this reason I find the paper original although it builds upon previous work exploring this idea. Most papers deal with heuristic or ad-hoc arguments of convergence of GD/SGD in the non-convex formulation with many assumptions that might not hold in practice or that are cumbersome.

3. Clarity: The "text" part of the paper is clearly written and the pace seems good. However there are crucial points where I could not understand the notation (see cons).

Cons:
1. **This has been fixed in an updated version and is now not a problem** Clarity: I could not really understand the optimization problem (9) and (11) because the variable $i$ appears as an optimization variable $\min_{i \in [P]}$ but it does not appear in the optimization objective? In the objective the letter $i$ is used but as an index in the summation $\sum_{i=1}^P$ which makes things really confusing. It appears that $i$ is not really an optimization variable and perhaps what the authors meant is that the constraint in (9) and (11) should read $V_i \in K_i \forall i \in [P]$? at least this is what I would find most natural. This should be clarified and corrected if needed.  

2. **This has been fixed in an updated version and is now not a problem** Clarity: It is not so clear how Algorithm 1 follows the Frank-Wolfe template. As I understand an initial value of $t$ is chosen and then the inner minimization problem is solved. Following this a new value of t is chosen and so on. So in the inner minimization problem the constraint set (assuming my understanding in the previous point) is $\sum_{i=1}^P ||V_i|| \leq t$ . Then the step (a) looks like the LMO but it is not clear where is the constraint \sum_{i=1}^P \| V_i \|_ enforced? It looks like the FW update necessarily modifies only one $V_i$ and that the solution can be obtained from the LMO corresponding to only one constraint ||V_i||_ \leq 1 is this the case? I think it is enforced through the constraint $\|u\|_2 \leq 1$.
It would be great if the authors can confirm and flesh out the intermediate steps in the appendix, which does not explain much besides the algorithm in the main text. This would make it more accesible.

3. **The authors argue in rebuttal that ReLU networks on spike-free data is still different from a linear classifier, some experiments were added** Significance: The Spike-free assumption seems to simplify things but it might be unrealistic. what is even more evident is that
it is somehow equivalent to learning a linear classifier as it implies that $(XU)_+ = XU$ so the network is actually $XUV^T$ so it is equivalent to $XA$ with $A=UV^T$. Under this identification it is well known that the variational formulation of the nuclear norm
implies that the regularizer $\|U\|_F^2 + \|V\|_F^2$ is equivalent to the nuclear norm of the unfactored matrix $A$. There are multiple works studying this that should be mentioned and it should be acknowledge that the spike-free assumption is more convenient for simplifying the analysis, rather than realistic (or it should be argued why it is ok to do the assumption).  Also it is not clear in the statement of the theorem what is the relation to spike-free. Does whitened $X$ imply spike-free $X$?

4. Significance: Theorem 2 is a simple consequence of this "spike-free" simplified setting and corresponds to the solution of the proximal operator of the nuclear norm.

5. Significance: the previous two points suggest that the important results here are those corresponding to general $X$ matrix. Unfortunately in that case the complexity is exponential in the rank of the data, which I guess is just the "real" dimensionality of the data? for example if data is collinear this would be 1 and it is not surprising that the problem would become easier. It looks like the proposed algorithms are currently only of theoretical interest.

6. **Authors have answered this in the revision** Experiments: exp 5.1: Perhaps add here the corresponding plots for the 0-1 error? it would be great to understand if the solution obtained with convex programming translates to better misclassification error compared to sgd. Currently how much time does the convex program take to solve? compared to SGD
do you think there is any benefit given that SGD seems to find good solutions in the overparametrized case?

7. **Authors have answered this in the revision** Experiments: exp. 5.2. same as before: what happens with the misclassification error? what stops you from doing the computation on all the data? memory?
Does the red cross mean that the soft thresholded SVD is solved in less than one second?

References:
1. Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition
Ricardo Cabral, Fernando De La Torre, Joao P. Costeira, Alexandre Bernardino; Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2013, pp. 2488-2495
2. Geometry of Factored Nuclear Norm Regularization. Qiuwei Li, Zhihui Zhu, Gongguo Tang
3. Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo

+ many references therein

overall I would be happy to recommend acceptance if the previous issues were adressed in a succint way.

**Update** After author feedback many of my concerns have been addressed, in particular the optimization problem
templates are much easier to understand now as well as the derivation of the algorithm. Also some important differences
between linear classifiers vs ReLU networks on 'Spike-free' data have been clarified. These were my main concerns and thus I am inclined to raise my score. 
review_title: An important study advancing our understanding of the optimization of neural networks

final_score: rating: 7: Good paper, accept
review_content: This paper showed that a two-layer vector-output ReLU neural network training problem is equivalent to a finite-dimensional convex copositive program. Based on this connection, the authors gave the first algorithm that finds the global min of the network training problem, which has running time polynomial in the number of samples but exponential in the data matrix. For CNN, the running time is only exponential in the filter size, which is usually a constant. The authors also described circumstances in which the global min can be efficiently found by soft-thresholded SVD; provided a copositive relaxation that is exact for certain cases. The effectiveness of the proposed algorithms is verified in experiments.

I think this is a good theory paper that shows an interesting connection between two layer network training and copositive program. My questions/concerns are as follows:

1. What’s the role of the regularizer in the current analysis? Does the result extend to the setting where the loss function does not have a regularizer? 
2. The current analysis seems to be restricted to two-layer neural networks. I understand the analysis of multiple layer neural networks can be potentially much more difficult. It would be good if the authors can add some discussion on the possibility of extending the analysis to more general multiple-layer nets. 
3. The current paper focuses on minimizing the training loss. In practice, people usually use over-parameterized neural networks which has an infinite number of global min for training loss. It’s believed that SGD works well because SGD has an implicit bias which tends to converge to a global min that also generalizes well. So I think it would be good if the authors can check the generalization performance of the proposed new algorithm. 
4. Since the algorithm in this paper is limited to a two-layer ReLU neural network, which is rarely used in practice. So I wonder what’s the general implication/message of this paper to the practical ML community.
5. A closely related paper [Ge et al 2018] also studies two-layer ReLU neural networks with vector-output. Under the assumption of symmetric distribution and more output dimension than hidden neurons, they gave a tensor decomposition algorithm that can recover the ground truth parameters in polynomial time. It might be good to compare the current paper and their result.
https://arxiv.org/abs/1810.06793
review_title: an interesting theory paper that shows connection between two-layer ReLU network training and convex copositive program

Meta-review: This paper extends an earlier work with scalar output to vector output. It establish a relationship of two-layer ReLu network and convex program. The result can be used to design training algorithms for ReLu networks with provably computational complexity. Overall, this is an interesting idea, leading to better theoretical insights to computational issues of two-layer ReLu networks. 
Decision: Accept (Poster)