Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: [Summary] This paper focuses on training convolutional neural networks (CNNs) by using convex optimization techniques. By taking the dual of the nonconvex training problems, (and the dual of its dual), the main contribution of the paper is to show the strong duality between the convex problem and its original nonconvex training problems. This result has been proved for multi-layer CNNs with one ReLU layer and three-layer CNNs with two ReLU layers.

[Pros] This paper presents interesting results on the convex equivalent formulation for the training problems in deep learning. This result could potentially lead to new algorithms for training the network. The convex formulation also reveals the hidden regularization property of the original nonconvex training problems, such as the group L_1 norm regularizer. 

[Cons] 1. This paper is an extension of previous work (Pilanci & Ergen, 2020) that provides an exact convex formulation for training two-layer fully connected ReLU networks. This paper extends this work to CNNs, multi-layers, but still has a very strong limitation on the number of ReLU layers: only one ReLU layer for multi-layer CNNs and two ReLU layers for a three-layer CNN. Also, it is not clear what are the technical difficulties in extending the previous results (Pilanci & Ergen, 2020) to this work. 

2. Since the modern neural network is often over-parameterized, which is also true in Theorem 2.1 as the number of filters $m$ needs to be relatively large compared to the number of data points, the nonconvex training problems can usually be solved to a global solution, either in practice or in theory under certain conditions. It's more interesting to see why the solution obtained has good generalization property, which is not discussed in this paper. 

3. This paper only uses toy examples in the experiments. For example, only n = 99 training samples are used in the MNIST experiments, which makes the results not that convincing. 

Minor comment: 
1. Adding the main idea in proving Theorem 2.1 (the strong duality) after Theorem 2.1 will be helpful for the reader to follow. Also, the authors could briefly mention why only taking the dual with respect to the output weights instead of all the network parameters in deriving eq. (3). This is different from the standard approach to computing the dual problem.
 
2. The notatin is very complicated, making the main results like Theorem 2.1 difficult to follow. For example, $w_i$ are used as the optimization variables in the convex problem (4), while $w$ is also used as an optimization variable in the original problem (1). Also, what are $j_{1i}$ and $j_{2i}$ in Theorem 2.1? Why only $m^*$ filters can be constructed from the solution of the convex problems in Theorem 2.1? 

3. typo in the first sentence right after Theorem 4.1: gIt


%%%%%%%%%%%% After rebuttal %%%%%%%%%%%%%%%%%%%%%%%%%%%%
I appreciate the great efforts the authors have made in responding to the comments. Most of my comments have been well addressed, so I have increased my score. Nevertheless, another important question is in the over-parameterization setting, why the solution obtained by the convex approach has good generalization property. This question is not addressed in the rebuttal. Probably it is too much to have this in one paper and can be an interesting question for future work. 
review_title: Official Blind Review #3

final_score: rating: 7: Good paper, accept
review_content: The paper studies the non-convex optimization problem of training CNNs with ReLU activations under different choices for the CNN architecture, and shows how these can be framed as convex problems with a poly time complexity w.r.t. relevant variables. The derived convex problems provide valuable insights on how the CNN architecture induces different weight regularizers by giving them in explicit form -- these show a rich connection between the architecture and regularizer.

I believe the contributions are significant and two-fold. First, the convex problems are solvable with reasonable time complexities (polynomial in all relevant parameters) even for networks with two non-linear layers -- this is in contrast with the cost of optimizing ReLU fully-connected networks, where an exponential dependency on the input dimension if the data matrix is full rank, hence global optimization of CNNs seem more likely to have practical implications than that of fully-connected networks. The condition for strong duality to hold seems quite restrictive, though, and further discussion on it would be valuable.

Second, it further expands what is currently known about how network architectures induce different regularizers on the parameters, showing that precise characterizations for CNNs with ReLU activations. The induced regularizers have a rich variety, including \ell_1, \ell_2, nuclear and Frobenius norms.

The fact that the theoretical results hold for classification losses is also valuable, and the experimental results are very appreciated. I think the CIFAR experiments in Appendix A.2 are more interesting and relevant than the MNIST one in the main body (esp. considering the time cost of convex opt. vs SGD), and swapping them would make Section 6 more appealing -- alternatively, shrinking Section 5 could possibly open up space to have Figure 4 in the main body of the paper.

Also, additional discussion on the induced regularization would be fruitful in making the paper more clear: in prior work that analyzes linear deep networks, the induced penalties are on the parameters of the induced linear predictor, and the same cannot be said for CNNs with ReLU activations and the induced penalties found here due to the binary diagonal matrices D. Making this distinction (which is mostly technical) more explicit would help readers in understanding how the derived penalties relate to ones given in prior work.

Minor comments:
- typo in beginning of last paragraph of Section 4 "gIt"
- missing mathbb/mathbbm/mathds/etc for indicator functions, towards end of Theorem 2.1's statement
- the equations would be easier to parse if the output weights were placed before the ReLU, e.g. w_j (X_k u_j)_+ instead of (X_k u_j)_+ w_j in Eq 1
- what are the sign patterns I_ijk in Theorem 4.1?
- Fig 1 and 2 seem to have wrong aspect ratios (horizontal stretching) and too much negative vspacing in their captions: Fig 2 occludes overlaps the caption of Fig 1 and there is almost no space between the caption of Fig 2 and Section 6
- inconsistent reference style: some entries in the bibliography have editors while other don't, same for doi etc

Overall I find the contributions to be significant and suggest acceptance.

---

I thank the authors for the response, which addresses my questions. I still believe that the paper provides valuable contributions and insights.
review_title: Valuable insights on regularization induced by CNN models, solid contribution to CNN global optimization

final_score: rating: 7: Good paper, accept
review_content: Summary:
The paper considers several types of CNN and proposes convex reformulations for non-convex problems of training these networks. As a result a polynomial complexity is shown for the training problem. The results are also interpreted as implicit regularization induced by the choice of the architecture. Finally, numerical experiments are made to support the theoretical findings and show that in the predicted regime, SGD for the original problem converges to the global minimizer given by the convex reformulation.

Evaluation:
On the one hand it is good to know that the vast list of the analyzed architectures are amenable to convex reformulations and polynomial complexity of their training. On the other hand, the main techniques to obtain these results were developed in (Pilanci & Ergen, 2020), which is already published at ICML 2020 https://proceedings.icml.cc/static/paper_files/icml/2020/2660-Paper.pdf. I believe that the results are of interest also to the ICLR community, so I'm leaning more to the accept side.

Pros:
1. Good to know that many CNN architectures can be trained in a polynomial time and which implicit regularization they introduce. 
2. In comparison to (Pilanci & Ergen, 2020) the exponent of the polynomial in the complexity bound could be much smaller than the dimension. In this sense, as far as I understood, the convolution operation helps to get better complexity estimate.

Cons:
1. The proof of the main result (Theorem 2.1) looks as a verbatim of proof of the main result (Theorem 1) of (Pilanci & Ergen, 2020). The only difference is that now there are may X_k's and a summation over k.
2. The proofs of the other results are not completely clear.
a. Proof of Theorem A.1. Why the first reparametrization is equivalent? Why strong duality holds?
b. Proof of Theorem A.2 also is lacking details.
c. Similarly for Appendix A.5.
d. Proof of Theorem A.3. First line. Why are there $m^*$ pairs of such vectors?
3. The clarity could be improved
a. What is precisely meant by "circulant matrix generated by the elements of u"?
b. In Sect. 1.2 what is "stride"?
c. In Theorem 4.1 what are "sign patterns"?
d. It seems that in (13) somewhere $\beta$ is missing.
e. First paragraph of Appendix A.6, there is an undefined reference.

Minor comments:
1. Extra "g" in the first line after Theorem 4.1.
2. In (17) there is an extra summation over $k$ in the $\lambda$-term.
3. There should be comma between 6 and 7 in the first line of Sect. 6.

review_title: Borderline paper: some novel results, but too close techniques to a previous work

Meta-review: The paper introduces convex reformulations of problems arising in the training of two and three layer convolutional neural networks with ReLU activations. These formulations allow shallow CNNs to be training in time polynomial in the number of data samples, neurons and data dimension (albeit exponential in filter lengths). These problems are regularized in different ways (L2 regularization for two layers, L1 regularization for three layers), providing new insights into the connection between architectural choices and regularization. The paper also provides experiments showing convex training of neural networks on small datasets.  

Pros and cons:

[+] The theoretical results show that globally optimal training of shallow CNNs can be achieved in time fully polynomial, i.e., polynomial in the number of data samples, neurons and data dimension. This is significant theoretical progress, since the corresponding results for fully connected neural networks require time exponential in the rank of the data matrix. There is, however, an exponential dependence on the filter length (or the rank of the patch matrix). In particular, the computational complexity is proportional to $(nK/r_c)^{3r_c}$, where $n$ is the number of data points. While CNNs do use relatively small filters, this becomes prohibitive even when $r_c$ is a moderate constant. E.g., the experiments use filters of length $3$. Here, the comments of the reviewers about generalization may be appropriate; perhaps experiments that evaluate the performance of these networks in terms of generalization may show the disadvantages of using very small filters. 

[+] The work provides interesting and rigorous insights into the relationship between architecture and implicit regularization, with different network architectures leading to different regularizers (L1, L2, nuclear). Developing these insights for deeper architectures could lead to important insights even in situations where the convex relaxation is challenging to solve efficiently. 

[+] Although the theoretical results require overparameterization, in the sense that strong duality holds when the number of filters is large relative to the number of data points, the authors convincingly argue that this degree of overparameterization is commensurate with, or even smaller than, the degree of overparameterization present in many experimental/theoretical works in the literature. 

[+/-] The paper is mathematically precise and is written in a rigorous fashion, but is occasionally heavy on notation. The paper could be more impactful on empirical work on neural networks if it could provide more intuition about how the various forms of equivalent regularization arise from different architectures. 

All three reviewers express appreciation for the paper’s fresh insights into global optimization of shallow CNNs and the connection between architectural choices and regularization. The AC recommends acceptance. 

Decision: Accept (Spotlight)