Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes the dual formulation of a two layer neural network, which makes the loss for training convex. The convexity guarantees the global optimality of training step compared to training on the primal loss function. The norm regularizer is applied to ensure the generalization. Then the paper gives explanation and experiments regarding the dual nn. 

However, I'm not sure what is the novelty of the work. On the theoretical side, I think Thm 1 is a straightforward computation of the dual function, and I cannot see if there's any novel technique beyond the common textbooks. I think if there's any dual computation in Sec 4.3 for nn with any number of layers, it could be more interesting. So far I don't think it's sufficient for ICLR.

Despite that, even if the majority of contribution is practical performance -- I cannot see what's the goal of the experiments. If this approach is better than the usual nonconvex nn formulation, at least we should see a clear difference. The solid and dash lines are really close to each other, in terms of computation time/epochs or error/loss I cannot see the advantage. The claims in experiment section are vague. E.g., "Zero duality gap", there should be a proof to justify it. I find the proof in appendix eq (12) that $p^* = d^*$. However, to use Slater's condition, is the primal problem convex? I cannot find the proof. (if this is proven I will definitely raise my score) If it's empirical, even the loss looks similar in the experiments, I'm not sure what setup guarantees a zero duality gap (what's the distribution of training samples, what's the underlying relation between x and y, what's the size of nn, etc.) This is really a theoretical claim, otherwise please say "small duality gap observed empirically".

Also it would be great to compare with neural tangent kernel works where GD finds the global optimum of nonconvex primal formulation with high probability. Based on NTK I'm not sure if convexity is so important. Regarding convex NN, this paper is also interesting.
https://openreview.net/forum?id=H1MW72AcK7

=============================== UPDATE =============================== 

Checked the proof again and want to confirm that, is it using the composition with pointwise maximum? If so I believe that it's correct, just be more detailed with the proof. Now I'm only concerned with the technical sophistication of the paper. Would be good to discuss deeper NN. Also good to make clear the advantage over other convex or nonconvex but optimizable formulations.
review_title: Need more theoretical novelty for ICLR, with doubts for the proof

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors propose a convex formulation for training a 2-layer neural network for reconstruction which should make training easier.

It’s nice to see some results in this domain which are provably convergent, especially since 2 layer NNs are universal approximations. I’m cautiously optimistic that this could open the door to more practically relevant results.

However, the NNs experimented with and the experiments done are relatively simplistic, so it’s hard to grasp how far away this is from practical results. It would also be nice if more effort was spent on contextualising these results within the wider scope of convex methods (e.g. infinite width 2 layer networks).

* The polynomial complexity on its own isn’t that interesting. The input dimension is in the hundreds of thousands, so even quadratic complexity would be highly limiting. It would probably be nice to make it clear that this is mostly of theoretical interest. Perhaps even write out a real estimate for l in the article.
* The main result is quite interesting even outside of regression. Would it be possible to extend it to other convex loss functions?
* Stating that the dual is easier to interpret than the primal is debatable. The primal is also locally linear around almost all points.
* Please make all images in figure 5 equally large.
* Is there a good reason results are not reported on the full FastMRI dataset? It would certainly make comparisons much easier and would contextualize the results. The current setup is not really reproducible.
* Overall I’m missing baselines to understand how relevant the results are. Adding a simple U-Net to the MRI case would disambiguate if this is a relaxation which is of theoretical importance, or if it’s actually giving good results. The images on their own are kinda useless for this.
* The “interpretable reconstruction” part is honestly somewhat debatable. Showing me a few hundred filters might give a tiny bit of insight, but I wouldn’t say it lets me interpret the reconstruction properly.
* Figure 1b is irritatingly not vertically centered
* Images in fig 3 suffer from similar issues. Overall images should be saved in exactly the resolution they are stored in (e.g. 28x28 for MNIST), this is especially important in articles whose whole purpose is to show imaging results. Also avoid linear interpolation between pixels.
* Has the number of sign patterns been ablated?

review_title: Convex Regularization behind Neural Reconstruction

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: Summary and Contributions: This paper aims to find convex alternatives for deep learning based image reconstruction problems. This is well motivated by medical imaging, where there is risk of hallucinating unseen pixels, and there is high demand for robustness of training and interpretability of the prediction. For a two-layer convolutional neural network with ReLU activation, with weight-decay regularization, that is non-convex, this paper establishes strong convex duality, where the dual optimization is quite tractable and interpretable. It also shows empirical results for MNIST denoising and MRI reconstruction that support the claims.

Overall, I enjoyed reading this paper. It is a solid work, very well written, and it has a balanced mix of theory and application, where the theory shows direct practical impact.

Strong points:
-   This paper is very well written and well organized. The motivation is very clear and sound.
-   The proposed convex duality framework is solid and it fits nicely an important application with minimal assumptions.
-   The interpretability offered by the dual network is very interesting. This is a novel and elegant view. In particular, the filters visualized in Fig. 4 are insightful to what a neural network learns. The clustering interpretation is also neat.
-  The experiments with MNIST and fastMRI are convincing. In particular, the experiments with MRI are important and practically valuable, since in medical imaging deep learning has become the standard method nowadays for reconstruction, and, no or little is known about the interpretability of existing methods.

Additional feedback and suggestions:
- The appendix (Fig. 9) includes experiments with impulsive noise that show SGD for convex dual network converges to a better training/validation loss than the non-convex network. It might be better to move this to the main paper, as this is the message that the paper is trying to convey?
- Typos and notation mismatch in the proof of Theorem 1 in the appendix: what is X in eq. 13? index j in eq. 12?
- In the final version, it would be also useful to add the filter visualization for the MRI reconstruction as well. It would be interesting to see how dataset dependent the learned filters are.
- I am wondering about the complexity of the dual optimization problem. Are there fast convex solvers for scaling up the computations? Also, about the required number of sign patterns, can the authors provide intuitions for the datasets used in the paper, say for MNIST? 

Correctness: The analyses are solid and the claims are correct. 
Relation to prior work: The paper has clearly discussed the connections with the previous works.
Reproducibility: The details of the experiments and the public datasets are included in the paper. Thanks also for sharing the code.

review_title:   

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper describes the interpretation of image restoration by fully convolutional neural network (FCNN) through the dual problem of neural network learning. Since the activation function is non-linear, it is generally difficult to interpret the main problem. In this paper, Authors consider a huge pattern of activation as samples and define the corresponding filter as dual parameters. As a result, when a finite number of sufficiently large filters is prepared, this becomes a convex dual problem of the primal problem. This dual framework itself is the work in [Pilanci & Ergen, ICML2020], and it is considered that the actual contribution of this paper was to apply it to the image resconstruction problem and discuss its interpretation.

The conclusions about the interpretation of FCNN were that the l2 penalty of the weight parameters was group lasso in the dual parameter and sparse regularization of the path, and that denoising was patch-based clustering and its linear filtering.

The interpretation of neural image restoration through the dual problem is very interesting and I think it is well written as a paper. It is nice that an application example of medical image restoration is also shown.

However, there are some recent studies that are considered to be very closely related to this paper, and the novelty of the conclusion itself of patch-based image processing seems to be weak. The papers that are considered to be closely related are listed below.

 --Convolutional sparse coding
Papyan, Vardan, Yaniv Romano, and Michael Elad. "Convolutional neural networks analyzed via convolutional sparse coding." The Journal of Machine Learning Research 18.1 (2017): 2887-2938.
**short summary** In the above paper, the CNN filters are interpreted as a patch dictionary, and the sparse feature map is interpreted as a coefficient. Image reconstruction by CNN is interpreted as patch-based sparse coding.

 --Low-dimensional manifold modeling of patches in a single image
Yokota, Tatsuya, et al. "Manifold Modeling in Embedded Space: A Perspective for Interpreting Deep Image Prior." ArXiv preprint arXiv: 1908.02995 (2019).
**short summary** In the above paper, the operation of extracting many patches from a single image is considered as embedding, and the low-dimensional manifold of patches embedded in the $k^2$-dimensional Euclidean space is learned by denoising auto-encoder. Image reconstruction by CNN is interpreted as low-dimensional manifold learning of patches.

 --Neural tangent denoiser
Tachella, Julián, Junqi Tang, and Mike Davies. "CNN Denoisers As Non-Local Filters: The Neural Tangent Denoiser." ArXiv preprint arXiv: 2006.02379 (2020).
**short summary** In the above paper, the noise removal by CNN is interpreted using the theory of neural tangent kernel, which has been attracting attention in recent years. The theory of neural tangent kernel shows that CNN can be interpreted as filtering using the similarity matrix between patches when the number of filters becomes very large. I feel that there is a relationship between increasing the number of filters in the above paper and increasing $ l $ in the dual representation of this paper.

I think it would be even better if the relationships between this paper and above papers are discussed in the manuscript.
review_title: Interesting but not enough discussion with related works

Meta-review: This paper is motivated by figuring out what regularization do popular neural network reconstruction techniques correspond to. In particular, this paper studies a convex duality framework that characterizes the global optima of a two-layer fully-convolutional ReLU denoising network via convex optimization. The authors use this regularization to interpret the obtained training results. The reviewers raised a variety of concerns regarding the tractability of the optimization problem (seems to be exponential in number of constraints), the utility for interpretation etc, significance of the results compared to existing literature. Some of these concerns were alleviated but not fully resolved. One reviewer had concerns about the correctness of the proof that was resolved based on the authors’ response. I share many of the above concerns. However, I do think having a computationally feasible way to figure out the exact regularization in these simple settings (at least with small dimensions) could provide some insights to guide further theoretical development.  Therefore I am recommending acceptance. However, I strongly urge the authors to further revise the paper based on the above comments.
Decision: Accept (Poster)