Convex Regularization behind Neural Reconstruction
Authors: Arda Sahiner
Morteza Mardani
Batu Ozturkler
Mert Pilanci
John M. Pauly
Venue: ICLR 2021 Poster (2021)
Keywords: neural networks
image reconstruction
denoising
interpretability
robustness
neural reconstruction
convex duality
inverse problems
sparsity
convex optimization

Abstract: Neural networks have shown tremendous potential for reconstructing high-resolution images in inverse problems. The non-convex and opaque nature of neural networks, however, hinders their utility in sensitive applications such as medical imaging. To cope with this challenge, this paper advocates a convex duality framework that makes a two-layer fully-convolutional ReLU denoising network amenable to convex optimization. The convex dual network not only offers the optimum training with convex solvers, but also facilitates interpreting training and prediction. In particular, it implies training neural networks with weight decay regularization induces path sparsity while the prediction is piecewise linear filtering. A range of experiments with MNIST and fastMRI datasets confirm the efficacy of the dual network optimization problem. 

Published as a conference paper at ICLR 2021
CONVEX REGULARIZATION BEHIND NEURAL RECONSTRUCTION
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, John Pauly Department of Electrical Engineering Stanford University {sahiner, morteza, ozt, pilanci, paulylestanford..euu
ABSTRACT
Neural networks have shown tremendous potential for reconstructing high- resolution images in inverse problems, The non-convex and opaque nature of neural networks, however, hinders their utility in sensitive applications such as medical imaging. To cope with this challenge, this paper advocates a convex du- ality framework that makes a two-layer fully-convolutional ReLU denoising net- work amenable to convex optimization. The convex dual network not only offers the optimum training with convex solvers, but also facilitates interpreting train- ing and prediction. In particular, it implies training neural networks with weight decay regularization induces path sparsity while the prediction is piecewise linear filtering. A range of experiments with MNIST and fastMRI datasets confirm the efficacy of the dual network optimization problem.
INTRODUCTION
In the age of AI, image reconstruction has witnessed a paradigm shift that impacts several appli- cations ranging from natural image super-resolution to medical imaging. Compared with the tradi- tional iterative algorithms, Al has delivered significant improvements speed and image quality, making learned reconstruction based on neural networks widely adopted in clinical scanners and personal devices. The non-convex and opaque nature of deep neural networks however raises se- rious concerns about the authenticity of the predicted pixels in domains as sensitive as medical imaging. thus crucial to understand what the trained neural networks represent, and interpret their reconstruction per pixel for unseen images.
Reconstruction is typically cast as an inverse problem, where neural networks are used in different ways to create effective priors; see e.g., (Ongie et al. 2020) Mardani al. 2018b) and references therein. An important class of methods are denoising networks, which given natural data corrupted by some noisy process Y, aim regress the ground-truth, noise-free data X, (Gondara, 2016 Vincent et al. 2010). These networks are generally learned a supervised fashion, such that a mapping
X' is learned from inputs {y, )n outputs (æ..) ) and then can be used in the inference phase on new samples ý to generate the prediction æ. = f()).
The scope of supervised denoising networks is so general that it can cover more structured inverse problems appearing, for example, in compressed sensing. In this case one can easily form a poor (linear) estimate of the ground-truth image that is noisy and then reconstruct via end-to-end denoising networks (Mardani et al., 20186 Mousavi et al., 2015). This method has been proven quite effective on tasks such as medical image reconstruction (Mardani et al.) 2018h Sandino al.] 2020 Hammmeniik et al. 2018). and significantly outperforms sparsity-inducing convex denoising methods, such votal-vaiation (TV) and wavelet regularization (Candès et al., 2006
Lustig ct al. 2008 Donoho 20066 in terms of both quality and speed.
Despite their encouraging results and growing use in clinical settings (Sandino et al. 2020 Ham-
mernik et al. 2018 Mousavi et al.) 2015), little work has explored the interpretation of supervised training of over-parannn wer-paramettriized neural networks for inverse problems. Whereas robustness guaran- tees exist for inverse problems with minimization of convex sparsity-inducing objectives (Oymak)
& Hassibi 2016 Chandrasekaran al. 2012), there exist such guarantees for predictions of

---

Published as a conference paper at ICLR 2021
non-convex denoising neural networks based supervised training. While the forward pass of a network has been interpreted as a layered basis pursuit from sparse dictionary learning, this approach lacks understanding of the optimization perspective of such networks, neglecting the solutions to which these networks actually converge (Papyan et al. (017). In fact, it has been demonstrated empirically that deep neural networks for image reconstruction can be unstable; i.e., small perturbations in the input can cause severe artifacts in the reconstruction, which can mask relevant structural features, which are important for medical image interpretation (Antun et al. 2020).
The main challenge in explaining these effects emanates from the non-linear and non-convex structure of deep neural networks that are heuristically optimized via first-order stochastic gradient descent (SGD) based solvers such as Adam (Kingma & Ba, 2014). As result, it is hard to interpret the inference phase, and the training samples can alter the predictions for unseen images. In other applications, Neural Tangent Kernels (NTK) have become popular to understand the behavior of neural networks (Jacot et al., 2018). They however strongly rely on the oversimplifying infinite-width assumption for the network that is not practical, and pointed out by prior work (Arora et al.] 2019), they cannot explain the success of neural networks in practice. To cope with these challenges, we present convex-duality framework for two-layer -nite-width denoising networks with fully convolutional (conv.) layers with ReLU activation and the representation shared among all output pixels. In essence, inspired by the analysis by Pilanci & Ergen (2020), the zero-duality gap offers a convex bi-dual formulation for the original non-convex objective, that demands only polynomial variable count.
The benefits of the convex dual are three-fold. First, with the convex dual, one can leverage off- the-shelf convex solvers to guarantee convergence the global optimum in polynomial time and provides robustness guarantees for reconstruction. Second, it provides an interpretation of the train- ing with weight decay regularization as implicit regularization with path-sparsity, a form of capacity control of neural networks (Neyshabur et al., 2015). Third, the convex dual interprets CNN- based denoising as first dividing the input image patches into clusters, based on their latent representation, and then linear filtering is applied for patches in the same cluster. A range of experiments per- formed with MNIST and fastMRI reconstruction that confirm the zero-duality gap, interpretability, and practicality of the convex formulation.
All in all, the main contributions of this paper are summarized as follows:
We, for the first time, formulate a convex program with polynomial complexity for neural image reconstruction, which is provably identical to two-layer fully-conv. ReLU network.
We provide novel interpretations of the training objective with weight decay as path- sparsity regularization, and prediction as patch-based clustering and linear filtering.
We present extensive experiments for MNIST and fastMRI reconstruction that our convex dual coincides with the non-convex neural network, and interpret the learned dual networks.
2 RELATED WORK
This paper is at the intersection of two lines of work, namely, convex neural networks, and deep learning for inverse problems. Convex neural networks were introduced in (Bach 2017 Bengio
et al. 2006), and later in (Pilanci & Ergen 2020 Ergen & Pilanci 2020a b).
Ergen & Pilanci 2020b) which put forth a convex duality framework for two-layer ReLU networks with a single output. It presents a convex alternative in a higher dimensional space for the non-convex and dimen-dim neural network. It is however restricted to scalar-output networks, and considers either fully-connected networks (Pilanci & Ergen 2020), or, CNNs with average pooling (Ergen & Pilanci 2020b). Our work however focuses on fully convolutional denoising with output dimension as large the number of image pixels, where these pixels share the same hidden representation. This is indeed quite different from the setting considered in (Pilanci & Ergen 2020) and demands a different treatment. could also be useful to mention that there are works in (Amos et al. [0177] Chen et al., 2019) that customize the network architecture for convex inference, but they still require non-convex training.
The most relevant our work are (Pilanci & Ergen 2020
2

---

Published as a conference paper at ICLR 2021
In recent years, deep learning has been widely deployed in inverse problems to either learn effective priors for iterative algorithms (Bora et al. 2017 Heckel & Hand (0188) , or to directly learn the inver- sion map using feed-forwarts networks (Jin et al. 20077|Zhang et 2017 In the former paradigm, either an input latent code, or, the parameters of deep decoder network are optimized to generate clean output image. A few attempts have been made analyze such networks explain their success (Yokota et al., 2019, Tachella et al. 2020)] Jagatap & Hegde] 2019). Our work, in contrast, belongs to the latter group, which is of utmost interest in real-time applications, and thus widely adopted in medical image reconstruction. Compressed sensing (CS) MRI has been a successful fit, where knowing the forward acquisition model, one forms an initial linear estimate, and trains a non- linear CNNs to de-alias the input (Mardani et al.] 2018a). Further, unrolled architectures inspired by convex optimization have been developed for robust de-aliasing (Sun et al. 2016 Mardani al.) 2018b, Hammernik et al., 2018 Sandino et al. 2020 Diamond et al.] (017). Past work however are all based on non-convex training of network filters, and interpretability is not their focus. Note that stability of iterative neural reconstructions has also been recently analyzed in Li et al. (2020); Mukherjee et al. (2020).
3 PRELIMINARIES AND PROBLEM STATEMENT
Consider the problem of denoising, i.. reconstructing clean signals from ones which have been corrupted by noise. In particular, with their corrupted counterparts Y = X. E, where noise E has entries drawn from some probability distribution, such as (0, o²) in the case of i.i.d. Gaussian noise. This is fundamental problem, with a wide range of applications including medical imaging, image restoration, and image encryption problems (Jiang al. 2018 Dong al. 2018 Lan et 2019).
given dataset of 2D images X. Nxhxw along
To solve the denoising problem, we deploy two-layer CNN, where the first layer has an arbitrary kernel size kt and appropriately chosen padding, followed by an element-wise ReLU operation denoted by (.)+. The second and final layer of the network performs a conv. by kernel to generate the predictions of the network. The predictions generated by this neural network with m first-layer conv. filters {u, am and recond-layer conv. filters {u,} can be expressed as
f(X) Σ Y 2 uu,++00
(1)
where @ represents the 2D conv. operation.
3.1 TRAINING
We then seek to minimize the squared loss of the predictions of the network, along with an fo-m penalty (weight decay) on the network weights, obtain the training problem
1 D 2
3
min
L U2)+ 2 Uū x.
[ 1 11512)
(2)
u EyER ByER
2
1=1
The network's output can also be understood in terms of matrix-vector products, when the input 1p=1 R**) where each patch matrix corresponds to a patch of the image upon which a convolutional kernel will operate upon. Then, we can form the two-dimensional matrix input to the network as Y' [Y,, Y, YNAu)" Nh and attempt regress labels X' Nkw, which is a flattened vector of the clean images X., An equivalent form of the two-layer CNN training problem is thus given by
is appropriately expressed in terms of patch matrices (Y, E R²*
1 D 1=1
B m
pº min
(r'u))44 - X + 2
Σ j=1
(1,,112+1u,1])
(3)
EER ERER
2
In this form, the neural network training problem is equivalent to 2-layer fully connected scalar- output ReLU network with Nhw samples of dimension k.2,, which has previously been theoretically analyzed (Pilanci & Ergen 2020). We also note that for a fixed kernel-size k the patch data matrix Y' has a fixed rank, since the rank of Y' cannot exceed the number of columns k
Thhe results contained here are general all types of conv., but refer the 2D case for simplicity.
3

---

Published as a conference paper at ICLR 2021
3.2 RELU HYPER- PLANE-PLANE ARRANGEMENTS
To fully understand the convex formulation of the neural network proposed in 22. we must provide notation for understanding the hyper-plane arrangements of the network. We consider the set of diagonal matrices
D = [Diag(1yruzo)) : ||u/|2 - 1}
This set, which depends on Y', stores the set of activation patterns corresponding to the ReLU non- linearity, where a value of indicates that the neuron active, while indicates that the neuron inactive. In particular, we can enumerate the set of sign patterns as D (D)) where depends on Y and is bounded by
6 (NNhu - -
S 2r
r
for r (Yn PPllanii & Hrgen 2020). Thus, é is polynomial in Nhw for matrices with fixed rank r, which occurs for convolutions with a fixed kernel size k. Using these sign patterns, we can completely characterize the range space of the first layer after the ReLU:
(YYu)++ : ||ul|2 I 13 = (D,Y'u: u: ||u|l2 I 1, (2D; 1JY 2 0, E [e]
With this notation established, we ready to present main theoretical result.
4 CONVEX DUALITY
Theorem 1. There exists m S Nhw such that if the number of conv. filters m + 1. the two-layer conv. network with ReLU activation has a strong dual. This dual is a minite-dimensioal convex program, given by
p" = d"
min 2DD-1jY' w. (2D.-1)Y'
Σ i=1
D,Y' 2,) X
+ 3
[125 + (|2zl12)
(4)
2
where refers to the number of sign patterns associated with Y'. Furthermore, given a set of optimal dual weights (w?, 2z) we can reconstruct the optimal primal weights as follows
11 (22)
wi + 0
Vil la
(ul, ut)
(5)
12)
x #0 0
It is useful to recognize that the convex program has 2tNhw constraints and 28k variables, which can be solved in polynomial time with respect to N,, and w using standard convex optimiz- For instance, using interior point solvers, in the worst case, the operation count is less than ( /b:2) 3x²), Note also that our theoretical result contrasts with fully-connected networks analyzed in (Pilanci & Ergen 2020), that demand exponential complexity in the dimension.
Our result can easily be extended residual networks with skip connections as stated next.
Corollary 1.1. Consider residual two-layer network given by
Srea(Y) = = U1)+ 00
We also pose the convex dual network 4 in similar fashion, where we simply regress upon the residual labels X,
4.1 IMPLICIT REGULARIZATION
In this section, we discuss the implicit regularization induced by the weight decay in the primal model (3). In particular, each dual variable w; or represents path from the input to the output, since the the product of corresponding primal weights is given by
[w)
w 4 0
u 1
2
2 #0
4

---

Published as a conference paper at ICLR 2021
11
V1
x
V22
Z2
mm
V
We-Zp
dp
Primal Network
(b) Dual Network
Figure 1: Primal and dual network interpretation. In the primal network, m refers to the number of conv. filters, while in the dual network refers to the number of sign patterns.
Thus, the the paths of the primal model. In particular, penalty is ascribed to ||wa 2 + || which in terms of primal weights corresponds to a penalty on |m:|]| (trll l2- This sort of penalty has been explored previously in (Ncyshabur et 2015), and refers the path-based regularizer from their work.
group-lasso penalty on the dual weights w, and z; induces sparsity in
4.2 INTERPRETABLE RECONSTRUCTION
The convex dual model 4 allows us to understand how an output pixel is predicted from particular patch. Note that in this formulation, each input patch regressed upon the center pixel of the output. In particular, for an input patch Vg the prediction of the network corresponding to the p-th output pixel is given by
f(y))
yp (w: 2:)
where d0 E {0. 1} refers to the p-th diagonal element of D,. Thus, for an individual patch y/r- the network can be interpreted as first selecting relevant sets of linear filters for that individual patch, and then taking sum of the inner product of the patch with those filters-a piece-wise linear filtering operation. Thus, once it is identified which filters are active for a particular patch, the network's predictions are given as linear. This interpretation of the dual network contrasts with the opaque understanding of the primal network, in which due to the non- non-linear ReLU operation is unclear how to interpret its predictions, as shown in Fig,
Furthermore, because of the group-lasso penalty (Yuan & Lin 2006) we and 2; in the dual objective, these weights are sparse. Thus, for particular patch y only a few sign patterns d(P) influence its prediction. Therefore, different patches are implicitly clustered by the network according the linear weights w, 2; which active for their predictions. A forward pass of the network can thus be considered as first a clustering operation, followed by a linear filtering operation for each individual cluster. As the neural network becomes deeper, expect that this clustering becomes hierarchical each layer, the clusters become more complex, and capture more contextual information from surrounding patches.
4.3 DEEP NETWORKS
While the result of Theorem 1 holds only for two-layer fully conv. networks, these networks are essential for interpreting the implicit regularization and reconstruction of deeper neural networks. For one, these two-layer networks can be greedily trained to build successively richer representa- tion of the input. This allows for increased field of view for the piecewise linear filters to operate upon, along with allowing for more complex clustering of input patches. This approach is not dissimilar to the end-to-end denoising networks described by Mardani et al. (2018b), though it is more interpretable due to the simplicity of the convex dual of each successive trained layer.
This layer-wise training has been found to be successful in variety of contexts. Greedily
5

---

Published as a conference paper at ICLR 2021
pre-training denoising autoencoders layer-wise has been shown to improve classification perfor- mance in deep networks (Vincent et al.) 2010). Greedy layer-wise supervised training has also been shown to perform competitively with much deeper end-to-end trained networks image classification tasks (Belilovsky et al., 2019; Nøkland & Fidnes) 2019). Although analyzing the behavior of end-to-end trained deep networks outside the scope of this work, we expect that end-to-end models are similar to networks trained greedily layerwise, which can fully be interpreted with our convex dual model.
EXPERIMENTS
MNIST DENOISING
Dataset. We a subset of the MNIST handwritten digits (LeCun al. 1998). In particular, for training, we select 600 gray-scale 28 x 28 images, pixel-wise normalized by the mean and standard deviation over the entire dataset. The full dataset of 10,000 images used for evaluation.
Training, We seek to solve the task of denoising the images from the MNIST dataset. In particular, add i.idd noise from the distribution (0, o²) for various noise levels, o {0.25, 0.5, 0.75). The resulting noisy images, Y, are the inputs to our network, and we attempt to learn the clean images X.. We train both the primal network (2) and the dual network (4) using Adam (Kingma) & Ba| 2014). For the primal network, we use 512 filters, whereas for the dual network, we ran- domly sample 8,000 sign patterns D; as an approximation to the full set of sign patterns Further experimental details can be found in the appendix.
Zero duality gap. We find that for this denoising problem, there no gap between the primal and dual objective values across all values of tested, verifying the theoretical result of Theorem the sign-pattern approximation, wherein we
1, as demonstrated select only 8,000 sign patterns for the dual network, rather than enumerating the entire set of & patterns. The illustrations reconstructed images in Fig also makes clear that the primal and dual reconstructions are of similar quality.
Fig. This is irrespective
Training loss
Testing loss
Voveraea Prinsl, de-
Conees S60 Daai, es 0.35
Cviirs 900 Dink, mise on-- 0.
lancorno
lowen 1015 taed wens
Conoee Baa node
Conces Dial,
Epach
Epach
(a) Train loss
(b) Test loss
Figure Train and test curves for MNIST denoising problem, for various noise levels
7
7
7
7
7
8
(a) a = 0.25
(b) 0.75
Figure 3: Test examples from MNIST denoising problem for two values of from primal (top) and dual (bottom) networks. From left to right, images are: (a) noisy network input, (b) ground truth, (c) network output.

---

Published as a conference paper at ICLR 2021
Interprefable reconstruction. Further, our knowledge of the dual network. In particular, we can visualize both the sparsity of the learned filters, and the network's clustering of input patches. Because of the piece-wise linear nature of the dual network, we can visualize the dual filters w; or 2; as linear filters for the selected sign patterns. Thus, the frequency response of these filters explains the filtering behavior of the end-to- end network, where depending on the input patch, different filters are activated. We visualize this frequency response of the dual weights w; in Fig. where we randomly select 600 representative filters of size 28 x 28. We note that because of the path sparsity induced by the group-Lasso penalty on the dual weights, some of these dual filters are essentially null filters.
interpret what these networks have learned using
Figure 4: Visualization of the frequency response for the learned dual filters {w,} for denoising MNIST. Representative filters (600) are randomly selected for visualization when o = 0.5.
The clustering of input patches can be detected via the set of sign patterns d!d) which correspond to non-zero filters for each output pixel p. Each output pixel p can thus be represented by binary vector d(r) E {0, 13s. We thus feed the trained network clean test images and interpret how they are clustered, using k-means clustering with & = 12 to interpret the similarity among these binary vectors for each output pixel of an image. Visualizations these clusters can be found in Fig. 5(a).
We can also use this clustering interpretation for deeper networks, even those trained end-to- end. We consider four-layer architecture, which consists of two unrolled iterations of the two-layer architecture from the previous experiment, trained end-to-end. We can perform the same k-means clustering the implicit representation obtained from each unrolled iteration, using the interpretation from the dual network. This result is demonstrated in Fig. ((b), where we find that the clustering more complex in the second iteration than the first, expected. We note that while this network was trained end-to-end, the clusters from the first iteration are nearly identical to those of the single unrolled iteration, indicating that the early layers of end-to-end trained deeper denoising networks learn similar clusters to those of two-layer denoising networks.
5.2 MRI RECONSTRUCTION
MRI acquisition. In multi-coil MRI, the forward problem for each patient admits y: QF + e,, = 1, ... ne where F is the 2D discrete Fourier transform, (Si ) are the sensitivity maps of the receiver coils, and is the undersampling mask that indexes the sampled Fourier coefficients.
Dataset. To assess the effectiveness of our method, we use the fastMRI dataset (Zbontar et al.) 2018 benchmark dataset for evaluating deep-learning based MRI reconstruction methods. We use subset of the multi-coil knee measurements of the fastMRI training set that consists of 49 patients (1,741 slices) for training, and 10 patients (370 slices) for testing, where each slice of size 80 80. We select f by generating Poisson-disc sampling masks using undersampling factors
R = 2, 4, 8 with a calibration region of 16 x 16 using the SigPy python package (Ong & Lustig 2019). Sensitivity maps S; are estimated using JSENSE (Ying & Sheng/ 2007a).
Training. The multi-coll complex data are first undersampled, then reduced to a single-coil complex image using the SENSE model (Ying& & Sheng 2007b). The input of the networks are the real and
7

---

Published as a conference paper at ICLR 2021
(b)
Figure 5: Visualization of k-means clustering for latent representations of trained MNIST denoising network when 0.75 and 12. (a) one unrolled iteration, (b) two unrolled iterations trained end to end; top row is the output of the first iteration, and bottom is the output of the second iteration.
imaginary components this complex-valued Zero-Filled (ZF) image, where we wish to recover the fully-sampled ground-truth image. The real and imaginary components of each image are treated as separate examples during training. For the primal network, we use 1,024 filters, whereas for the dual network, we randomly sample 5,000 sign patterns.
Zero duality gap. We observe zero duality gap for CS-MRI, verifying Theorem 1. For different R, both the train and loss of the primal and dual networks converge the same optimal value, as depicted in Fig. 6 Furthermore, we show representative axial slice from random test patient in Fig. reconstructed by the dual and primal networks, both achieving the same PSNR.
Liormnrr GET
LOU
Loven 500 and
Training loss
Tost nig 105s
Epoch
Epoch
(a) Train loss
(b) Test loss
Figure 6: Train and test curves for MRI reconstruction under various undersampling rates R.
CONCLUSIONS
This paper puts forth a convex duality framework for CNN-based denoising networks, Focusing on a two-layer CNN network with ReLU activation, convex dual program is formulated that offers optimal training using convex solvers, and gains more interpretability. reveals that the weight decay regularization of CNNs induces path sparsity regularization for training, while the predic- tion piece-wise linear filtering. The utility of the convex formulation for deeper networks is also discussed using greedy unrolling, There are other important next directions pursue. One such di- rection pertains to stability analysis of the convex neural network for denoising, and more extensive evaluations with pathological medical images to highlight the erucial role of convexity for robust- ness. Another such direction would further exploration into fast and scalable solvers for the dual problem.
8

---

Published as a conference paper at ICLR 2021
2x
2x
FINCZLE
PRN-317
MANUZE
4x
4x
(a) Primal Network
(b) Dual Network
Figure 7: Representative test knee MRI slice reconstructed via dual and primal network for under- sampling 2, 4. From left to right: ground truth, output, and noisy ZF input.
ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under grants IIS SSS-1888179 and DCCS-2037304 the National Institutes of Health under grants RO1EB009690 and R01EB0026136. Facebook Research, Adobe Research and Stanford SystemX Alliance.
REFERENCES
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Confer- ence on Machine Learning, pp. 146--55,222 2017.
Vegard Antun, Francesco Renna, Clarice Poon, Ben Adcock, and Anders Hansen. On instabilities of deep learning in image reconstruction and the potential costs of ai. Proceedings of the National Academy of Sciences, 2020.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pp. 8141-8150, 2019.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-68 681, 2017.
Eugene Belilovsky, Michael Fickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference on machine learning, pp. 583-593. PMLR, 2019.
Yoshua Bengio, Nicolas L Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. In Advances in neural information processing systems, pp. 123-130, 2006.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using genera- tive models. arXiv preprint arXiv:
2017.
Jonathan Borwein and Adrian Lewis. Convex analysis and nonlinear optimization: theory and examples. Springer Science & Business Media, 2010.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489-509, 2006.
Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The ge- ometry of linear inverse problems. Foundations of Computational mathematics, 12(6):805-844 -49, 2012.

---

Published as a conference paper at ICLR 2021
Yize Chen, Yuanyuan Shi, and Baosen Zhang. Optimal control via neural networks: A convex approach. In International Conference on Learning Representations, 2019. URL https:// openreview net/
Steven Diamond, Vincent Sitzmann, Felix Heide, and Gordon Wetzstein. Unrolled optimization with deep priors. arXiv preprint
2017.
Weisheng Dong, Peiyao Wang, Wotao Yin, Guangming Shi, Fangfang Wu, and Xiaotong Lu. De- noising prior driven deep neural network for image restoration. IEEE transactions pattern analysis and machine intelligence, 41(10):2305-233) 2318, 2018.
David L Donoho. 1306, 2006.
Compressed sensing. IEEE Transactions on information theory, 52(4):1289-
Tolga Ergen and Mert Pilanci. Convex duality of deep neural networks. arXiv:2002.09773. 2020a.
arXiv preprint
Tolga Ergen and Mert Pilanci. Training convolutional relu neural networks polynomial time: Exact convex optimization formulations. arXiv preprint orXiv:2006.14990 2020b.
Lovedeep Gondara. Medical image denoising using convolutional denoising autoencoders. In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), pp. 241-246. IEEE, 2016.
Kerstin Hammerii,, Teresa Klatzer, Erich Kobler, Michael P Recht, Daniel K Sodickson, Thomas Pock, and Florian Knoll. Learning a variational network for reconstruction of accelerated mri data. Magnetic resonance in medicine, 79(6)33055-3071, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEFE international conference on computer vision, pp. 1026-1034, 2015.
Reinhard Heckel and Paul Hand. Deep decoder: Concise image representations from untrained non-convolutional networks. arXiv preprint arXiv:18/0.03992 2018.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in neural information processing systems, pp. 8571- 8580, 2018
Gauri Jagatap and Chinmay Hegde. Algorithmic guarantees for inverse imaging with untrained network priors. In Advances in Neural Information Processing Systems, pp. 14832-14842, 2019.
Dongsheng Jiang, Weiqiang Dou, Lue Vosters, Xiayu Xu, Yue Sun, and Tao Tan. Denoising of 3d magnetic resonance images with multi-channel residual learning of convolutional neural network. Japanese journal of radiology, 36(9):666-5744 2018.
Kyong Hwan Jin, Michael T McCann, Emmanuel Froustey, and Michael Unser. Deep convolutional neural network for inverse problems in imaging. IEEE Transactions on Image Processing, 26(9): 4509-4522, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint 1412,6940 2014.
Rushi Lan, Haizhang Zou, Cheng Pang, Yanru Zhong, Zhenbing Liu, and Xiaonan Luo. Image denoising via deep residual convolutional neural networks. Signal, Image and Video Processing, pp. 1-8, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-22324 1998.
Housen Li, Johannes Schwab, Stephan Antholzer, and Markus Haltmeier. Nett: Solving inverse problems with deep neural networks. Inverse Problems, 2020.
Michael Lustig, David L Donoho, Juan M Santos, and John M Pauly. Compressed sensing mri. IEEE signal processing magazine, 25(2):72-82, 2008
10

---

Published as a conference paper at ICLR 2021
Morteza Mardani, Enhao Gong, Joseph Y Cheng, Shreyas S Vasanawala, Greg Zaharchuk, Lei Xing, and John M Pauly. Deep generative adversarial neural networks for compressive sensing mri. IEEE transactions medical imaging, 38(1):167-179, 2018a.
Morteza Mardani, Qingyun Sun, Vardan Papyan, Hatef Monajemi, Shreyas Vasanawala, John Pauly, and David Donoho. Neural proximal gradient descent for compressive imaging. In Advances in Neural Information Processing Systems, pp. 9573-9583, 2018b.
Ali Mousavi, Ankit B Patel, and Richard G Baraniuk. A deep learning approach to structured signal recovery. In 2015 53rd annual allerton conference on communication, control, and computing (Allerton), pp. 1333.1343, IEEE, 2015.
Subhadip Mukherjee, Sören Dittmer, Zakhar Shumaylov, Sebastian Lunz, Ozan Öktem, and Carola-Bibiane Schönlieb. Learned convex regularizers for inverse problems. arXiv preprint arXiv:2008. 02839, 2020.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015.
Arild Nøkland and Lars Hiller Eidnes. Training neural networks with local error signals. arXiv preprint FrXiiv1901.0060
2019.
F Ong and M Lustig. Sigpy: a python package for high performance iterative reconstruction. In Proceedings of the ISMRM 27th Annual Meeting, Montreal, Quebec, Canada, volume 4819, 19, 2019.
Gregory Ongie, Ajil Jalal, Christopher A Metzler Richard G Baraniuk, Alexandros G Dimakis, and Rebecca Willett. Deep learning techniques for inverse problems in imaging. IEEE Journal on Selected Areas in Information Theory, 2020.
Samet Oymak and Babak Hassibi. Sharp mse bounds for proximal denoising. Foundations of Computational Mathematies, 16(4))965-1022, 2016.
Vardan Papyan, Yaniv Romano, and Michael Elad. Convolutional neural networks analyzed via con- volutional sparse coding. The Journal of Machine Learning Research, 18(1):2887-2938, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. arXiv preprint 1912.009 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact tolynomial-time con- vex optimization formulations for two-layer networks. arXiv preprint arXiv:2002.10553. 2020.
Christopher M Sandino, Joseph Y Cheng, Feiyu Chen, Morteza Mardani, John M Pauly, and Shreyas S Vasanawala. Compressed sensing: From research to clinical practice with deep neu- ral networks: Shortening scan times for magnetic resonance imaging. IEEE Signal Processing Magazine, 37(1): 2020.
Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions. Optimization, 58(2):1331111,200
Jian Sun, Huibin Li. Zongben Xu, et al. Deep admm-ne net for compressive sensing mri. In Advances in neural information processing systems, pp. 10-18, 2016.
Julián Tachella, Junqi Tang, and Mike Davies. Cnn denoisers as non-local filters: The neural tangent denoiser. arXiv preprint arXiv:2006.02377 2020.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and
Léon Bottou. Stacked denoising autoencoders: Learning useful representations in deep network with a local denoising criterion. Journal of machine learning research, 11(12), 2010.
Leslie Ying and Jinhua Sheng. Joint image reconstruction and sensitivity estimation in sense (jsense). Magnetic Resonance in Medicine, 57(6); 1202, 2007a. doi: 10. 10.1002/mm..1244 URL htRl:ttts:::/// inee///////nnnnnnnnneeee hbtp::///orieeerbrrrrrrrrr.. Werrar.rrrrr
com
1002 21 145

---

Published as a conference paper at ICLR 2021
Leslie Ying and Jinhua Sheng. Joint image reconstruction and sensitivity estimation in sense (jsense). Magnetic Resonance in Medicine, 57(6): 1202, 2007b. doi: 10.1002/mm..22255
wileerrry.llyy........m.. com/ /tt///a////////eeee/ee/eae/s 1002 / /rrm 21245
Tatsuya Yokota, Hidekata Hontani, Qibin Zhao, and Andrzej Cichocki. Manifold model- ing in embedded space: A perspective for interpreting" deep image prior". arXiv preprint arXiv: 020,00990 2019.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1) 68(1):49-6) 2006.
Jure Zbontar, Florian Knoll, Anuroop Sriram, Matthew J. Muckley, Mary Bruno, Aaron Defazio, Mare Parente, Krzysztof J. Geras, Joe Katsnelson, Hersh Chandarana, Zizhao Zhang, Michal Drozdzal, Adriana Romero, Michael Rabbat, Pascal Vincent, James Pinkerton, Duo Wang, Nafissa Yakubova, Erich Owens, C. Lawrence Zitnick, Michael P. Recht, Daniel K. Sodickson, and Yvonne W. Lui. fastmri: An open dataset and benchmarks for accelerated MRI. CoRR, abs/18 05s/1811.08839 2018. URL /twp/aaavvvvv//v org/ abs 8 08839
Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang, Beyond gaussian denoiser: Residual learning of deep enn for image denoising. IEEE Transactions on Image Processing, 26 (7):3142-311 42555, 2017.
A APPENDIX
B
ADDITIONAL EXPERIMENTAL DETAILS
All experiments were run using the Pytorch deep learning library (Paszke et al. 2019). All primal networks are initialized using Kaiming uniform initialization (He et al. 2015). The losses presented are the sample and dimension-averaged, meaning that they differ by constant factor of Nha from the formulas presented in (2) and (4). All networks were trained with an Adam optimizer, with 31 = 0.9, 32 = 0.999, and 10 All networks had ReLU activation and had a final layer consisting of x convolution kernel with stride and no padding. For all dual networks, order to enforce the feasibility constraints of (4) we penalize the constraint violation via hinge loss.
B. ADDITIONAL EXPERIMENT: ROBUSTNESS FOR MNIST DENOISING
While for i.i.d. zero-mean Gaussian noise, training the primal and dual networks coineide, this may not necessarily be the case for all noise distributions. Depending on the distribution of noise, the loss landscape for the non-convex primal optimization problem may have more or fewer valleys-even if SGD does not get stuck in the exact local minimum, it may converge extremely slowly, mimicking the effect of being stuck a local minimum. In contrast, because the dual problem is convex, solving the dual problem is guaranteed to converge the global minimum.
To this effect, compare the effect of denoising with i.i.d. zero-mean Gaussian noise, a = 0.75, with that i.idd. exponentially distributed noise, with À = 1.15. The exponential distribution has higher noise variance, and also a heavier tailed distribution, and thus more difficult for the non-convex problem to solve. For both cases, we employ 25 primal filters, and 8, 8,000 sign patterns. The results of these experiments are shown in Figs R and 9 As we can see, for the Gaussian noise distribution, the primal and dual objective values coincide, but for the exponential noise distribution, the dual program performs better, suggesting the primal problem is stuck local minimum or valley. This suggests that when the data distribution is heavy-tailed, the convex dual network may be more robust to train than the non-convex primal network, due to lack of local minima.
We train both the primal and the dual network in a distributed fashion on a NVIDIA GeForce GTX 1080 Ti GPU and NVIDIA Titan X GPU. For both cases, we use a kernel size of 3 x 3 with unity stride and padding for the first layer. For the primal network, we train with a learning rate of μ 10 !, whereas for the dual network use learning rate of 10 3 We use batch size of 25 for all cases. For the beight-decay parameter we use a value of = 10 which is not sample-averaged.
12

---

Published as a conference paper at ICLR 2021
Mencoees mare Sieed Corver SGD 3asl
Muccoeer SiD sted77
Cancer 5G2 asled
6x100
Traiiing loss
Tecting loss
3x10-
3x10
Epoch
(a) Train
(b) Test loss
Figure 8: Train and test curves for (luusiaa-ddsttrbucee noise with 0.75. The primal and dual optimization problems perform similarly well.
Conmin NET UuIREN
3x10
Training lost
Teatiigg loss
2x20
2x/00
30"
30'
300
20
100
200
20
Epoch
Epoch
(a) Train loss
(b) Test loss
Figure 9: Train and test curves for exponentially distributed noise with 1.15. The primal fails to learn as well as the dual.
B.2 MNIST DENOISING
We train both the primal and the dual network in distributed fashion a NVIDIA GeForce GTX 1080 Ti GPU and NVIDIA Titan X GPU. For both cases, we use a kernel size of 3 x 3 with a unity stride and padding for the first layer. For the primal network, train with learning rate of f 10-3, whereas for the dual network we use a learning rate of = 10-5 We use a batch value of 10-5, which is
size of 25 for all cases. For the weight-decay parameter samplc-averaged, and which is sufficiently large so to prevent overfitting on the training set, as demonstrated in Fig, [ which indicates that test performance is similar to training performance.
B.3 ABLATION STUDY FOR THE NUMBER OF SIGN PATTERNS
For the MNIST denoising problem, also considered the effect of changing the number of randomly sampled sign patterns to approximate the solution to the dual problem. The experimental setting this ablation study is identical the one of Section 5.1, namely, a primal network with 512 conv. filters, and additive i..d zero-mean Gaussian noise with variance o². For the noise standard deviations of 0.5 and a = 0.1, we compare the test and training loss found by the primal network with that of the approximated dual network with varied number of subsampled sign patterns.
Figures 10 summarizes our results. In particular, with higher amounts of noise, a larger number of sign patterns required to be sampled in order approximate the primal problem. With σ = 0.5, the dual problem requires approximately 4000 sign patterns to achieve zero duality gap, while with 0.1, the dual problem requires only 125 sign patterns.
13

---

Published as a conference paper at ICLR 2021
trainiy Neraa briniig las
herr bornin Ite
3x30"
3x32"
Training loss
Teising
137
Number subsampled sign patterns
Number subsampled sign patterns (b) Test loss, 0.5
(a) Train loss,
2at buneey Iove Yand buiiing lio
Zex lookig sao har aaourg lit.
Training loss
Testing
2x3
32 Number of subsampled sign pattorns
3>
It Number of subsampled sign patterns
12
(c) Train loss, 0.1
(d) Test loss, 0.1
Figure 10: MNIST denoising with additive Gaussian noise and a E {0.5, 0.13. Ablation study for the number of sampled sign patterns for the dual problem, compared to the primal problem with 512 filters.
B.4 MRI RECONSTRUCTION
The fastMRI dataset has data acquired with n., = 15 receiver coils. We train both the primal and the dual network single NVIDIA GeForce GTX 1080 Ti GPU with batch size of As our primal network architecture, we use a two-layer CNN with the first layer kernel size 7 x 7, unity stride and a padding of with skip connection. For the training of the primal and dual networks, networks are trained for 25 epochs. A learning rate of µ = 10-3 is used for the primal network, and learning rate μ 10-1 is used for the dual network with weight-decay parameter
10-5
B.5 LEARNED CONVOLUTIONAL FILTERS FOR MRI RECONSTRUCTION
Similar to the visualized dual filters for MNIST reconstruction, can also visualize the frequency response of the learned dual filters for the MRI reconstruction network, which we observe in Figure We see that these filters select for variety frequencies, but are quite different visually from those for MNIST reconstruction.
11
C PROOF OF THEOREM
We note that, mentioned in the main paper, is equivalent to 3 Thus, to prove the theorem, it sufficient to show that (3) is equivalent to (4). This proof follows directly from Theorem from
Pilanci & Ergen 2020
Before delving into the details, the roadmap of the proof can be sketched follows:
14

---

Published as a conference paper at ICLR 2021
Figure 11: Visualization of the frequency response for the learned dual filters (w,) for MRI recon- struction. Representative filters (250) of size 80 x 80 randomly selected for visualization when R = 4.
1. Re-scale the original primal problem the final layer weights
3 to an equivalent form with é-rreuularization on
2. Use Lagrangian duality to eliminate the final layer weights and introduce new dual vari- able obtain an intractable, yet equivalent convex program.
3. Use Slater's condition form the strong dual problem, which is semi-infinite convex program.
4. Use the ReLU sign patterns {D:M=z finitely parameterize this semi-infinite program, and then form the bi-dual to obtain the finite, convex, strong dual.
We begin by noting that (3) is equivalent to the following optimization problem:
p' min
| X 11 + 3
l0y
1=11
This is because, without changing the predictions of the network, we can re-scale u, by some scalar Yi > O, granted that we also scale vy by its reciprocal 1/7/- Then, we can simply minimize the regularization term over 75, noting that
min 7
112+ //5/ 21 l2/vyl
(10)
From this we then obtain the equivalent convex program
m
m
p" min
min u, ER YyR 2
Σ
Y ('u;)+0;
x.
17 112 + +0g//512
(11)
1=1
1 ER
min min
Σ (Y'
3
|| 12|uz1
(12)
u,ERt² 0
2
j=1
1=1
9 noting that this does not change the optimal objective value. Then, from ② we can form the equivalent problem via Langrangian duality. In particular, we can first re-parameterize the problem
Then, we can simply restrict | I 1 to obtain
m
min min |r 2 + 3 Σ
lo s...T (Y'u,)++8 - X!
(13)
| v,r 2
And then introduce the Lagrangian variable x
1 ;
m
p" min min max 11r11
Σ
by x TTX
Σ
(''u))
(14)
|uy 1 Byr
15

---

Published as a conference paper at ICLR 2021
Now, note that by Sion's minimax theorem, we switch the inner maximum and minimum without changing the objective value, since the objective is convex in Uj r and affine in 2, and obtain
p
1 min max min 2 211m112 + B
1/l+
z x z
Σ
(Y'u
(15)
I llas1
j=1
Now, we compute the minimum over r to obtain
m
by + 2 x. - _T= m
p
min |
max min - 2
By 2 1= +
(''u))+
(16)
and then compute the minimum over bj obtain
p
min I| 1 | (Yu,) so
max
2 11= x:11 + |
(17)
We note that this semi-infinite program 17] is convex. As long as 3 > 0, this problem is strictly feasible (simply set 0), hence by Slater's condition strong duality holds, and therefore we can form the dual problem
p" d" = 1=T (Y'u)+ 1 v/
max
-
x
1 2
(18)
Now, this dual problem can be finitely parameterized using the sign patterns {Di)-= using the pointwise maximum of the constraint. We thus have
d" = max
|=
x 1 1x.11
+
2
8.1.
max
1z D.Y u1 S
(19)
xE
I SI (2D,
D-Y'u0
We can split this absolute value constraint into two constraints, and maximize in closed form over by introducing Lagrangian variables a; a/;
d' max
12 X 2 1
0,20
0,20
(20)
s.t. Y IT (2D: 1)a; + Y"T D s BBVi E M4
Y"T (2D: 1]a
Y"T
D < 3 Vi E |4]
We then form the Lagrangian
- x 3 1 x
1
1
d' := max min
0,20 220,0/20
2/20
A (13 (
(2D: - -1)a + Y D1=112)
(21)
Σ (33-11 (TTT (2D; - I)a - Y -Ta -TTDDz2
Noting by Sion's minimax theorem that strong duality holds, we can take the strong dual of the Lagrangian and not change the objective value. Flipping max and min, and maximizing with respect to 2,0;, and of yields
d' =
min X
Σ ADDY' -XD,'',
X.D.''z)) - x. Σ
Xa + X
(22)
X/20
||w, 11s1
zi =51
(2D. (.)D-11)'',23
(2D,-))Y'z;20
16

---

Published as a conference paper at ICLR 2021
We lastly note that we perform change of variables w, A,w; and 2; X22,, and then minimize over X and X to obtain the final convex, minee-dimensionll strong dual.
d'
min (DD.-))Y w, 20 (2D:-1)Y's: 2,20
Σ 1=1
(wy 2i) x 2 3
w 12 + ||
(23)
2
Thus, have that strong duality holds, i.e. p¹ d= By theory in semi-infiite programming. we know that m² + 1 of the total & filters (w;, zi) are non-zero at optimum where m < NNww (Shapiro
2009
Pilanci & Ergen 2020).
Furthermore, we can use the relationship in 5 also verify this result. In particular, note that in the general weak duality setting, we must have that d' S p". Now, suppose we have optimal weights {u,, oz )]]]]= for the solution to the dual problem 4 obtaining objective value d" Then, using the relationship in we can re-form the primal weights to (3) repeated here for convenience:
22)
wi + 0
(u) 0,)
(24)
12
* 0
V
Now, substituting these into the primal objective, we have
p=
Σ YY' (Y'u))+
x
8
Σ
m
||y + 10y13)
(25)
ER eyER
i=1
8
Y' u - -x111+
Σ
|1 + lua1
(26)
1=1
Σ
D,Y'(u; (wn - 21) - x.113
3
Σ
(1
113 Vllue:lll??
(27)
+ 2
Σ
(I z
V
12 + 1++11112 11
(28)
i= 40
Σ
(ww - -2,) - x111 + 3 Σ | 212 + ||
(29)
dd
(30)
Thus, p" d This combined with the weak duality result d' S p" yields that d' = =p", as desired.
D PROOF OF COROLLARY
In this circumstance, we simply need re-substitute the same objective as (4), with our new labels as X Yu. where Y, E V is flattened vector of the input image. Then, we simply have the problem given by
P [10ill2 l| + ||2:112)
d'
min (2D. (2D.-1Y''.22 w.20 2
Σ D.Y' - 2.) (X. 1 + 3
(31)
1=1
Thus, the general form of the convex dual formulation still holds with a simple residual network.
17

---

Published as a conference paper at ICLR 2021
E EXTENSION TO GENERAL CONVEX LOSS FUNCTIONS
The results Theorem and Corollary can be extended to any arbitrary convex loss function L(X, X.). In particular, consider the non-convex primal training problem
min L EyER* 1 (Y' X:)
(1ul13 (1s)t)
(32)
ER
for m 2 mn as defined previously. Then, this problem has a convex strong bi-dual, given by
p
min 1DD w. (2D. 22D.-1)Y'2,2> 2,20
L
D, (,Y zi), x.) -z)),
(1e0s112 (|2:lla)
(33)
The proof for this strong dual is almost identical to that in Appendix C. In particular, we first define the Fenchel conjugate function
(z) max m L(z, X()
(34)
Now, note that we can re-write 32) in re-scaled form as (9:
m Σ
m
p
min 1|u $
(Y'u)) u1,, x + +
Σ
lzyl
(35)
j=1
j=1
The strong dual of (35) is then given by
p = max - (z) s.t. |2 & V//ull 1
(36)
using standard Fenchel duality (Boyd et al. 2004). We can further re-write the constraint set in terms of sign patterns done in the proof in Appendix C. Then, can follow the same steps from the proof of Theorem 1, noting that by -enchel-Moreau Theorem, L L (Borwein Lewis, 2010). Thus, obtain the convex-bi dual
min (2D: 10,-1)Y'u;20 w.20 (2D; 1,20
L
Σ 1=1
(, x.), 3 ||0:112 + 1122112)
Σ 1=1
(37)
as desired.
F FAILURE OF STRAIGHTFORWARD DUALITY ANALYSIS FOR OBTAINING A TRACTABLE CONVEX DUAL
In this section, we discuss how straightforward duality analysis will fail to generate a tractactable convex dual formulation of the two-layer ReLU-activation fully-conv. network training problem. In particular, we will follow an alternative proof to that in Appendix C, omitting the re-scaling step, and demonstrate that the dual becomes intractable.
We begin with 3
m I
8 m
p² min
Σ j=1
(1 112 + 11,
(38)
MYERA?
j=1
eyER
We can re-parameterize the problem as
p" min min 5
|r| 2
Σ
|1,,11++00
s.t. > (Y'u))+ -X
(39)
uyERt* ER
18

---

Published as a conference paper at ICLR 2021
And then introduce the Lagrangian variable
p' min min max EyeR** 6,ER
1 + 2
Σ
|
+2 +z T
x
>
(Y
(40)
j=1
j=l
Now, use Sion's minimax theorem to exchange the maximum over and the minimums over r and Vy.
p min max min m, 2
211m112
1
8
m
[1ee
+ (0513) + + TTTTx x
m Σ
Y'uu)+
(41)
1=1
Minimizing over r, we obtain
8 m
m
p" min max min
Mj by 2
-11=113
Σ j=1
[1y11 10,1 + x T - Σ
Y u2 (42)
2
jm1
Now, minimizing over Uj, obtain the optimality condition that vj substituting this, obtain the problem
= (Y'uu)) Vj. Re-
p min max 1 1z X
I 2
Σ
1 13 +
2
2 (Y'u))+)) (43)
2B
j=1
This problem is not convex, hence strong duality does not hold (we cannot switch and min without changing the objective), and we cannot maximize over z in closed form since the optimiality condition for is given as
3 2
((Yuu;)) (X',)))
3
Thus, standard duality approaches fail to find tractable dual the neural network training problem
3). In particular, the re-scaling step (9) and the introduction of sign patterns (19) are detrimental to render our analysis tractable.
19


Reviews:
[{"review_id": "u0b_9McfcIA", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nHowever, 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.\n\nDespite 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\".\n\nAlso 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.\nhttps://openreview.net/forum?id=H1MW72AcK7\n\n=============================== UPDATE =============================== \n\nChecked 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "qOO6ih469fg", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nThe 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.\n\nHowever, 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.\n\n --Convolutional sparse coding\nPapyan, 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.\n**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.\n\n --Low-dimensional manifold modeling of patches in a single image\nYokota, Tatsuya, et al. \"Manifold Modeling in Embedded Space: A Perspective for Interpreting Deep Image Prior.\" ArXiv preprint arXiv: 1908.02995 (2019).\n**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.\n\n --Neural tangent denoiser\nTachella, Julián, Junqi Tang, and Mike Davies. \"CNN Denoisers As Non-Local Filters: The Neural Tangent Denoiser.\" ArXiv preprint arXiv: 2006.02379 (2020).\n**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.\n\nI think it would be even better if the relationships between this paper and above papers are discussed in the manuscript.", "extra_scores": {}, "extra_text": {}}, {"review_id": "oNuarmgCdQ7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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.\n\nStrong points:\n-   This paper is very well written and well organized. The motivation is very clear and sound.\n-   The proposed convex duality framework is solid and it fits nicely an important application with minimal assumptions.\n-   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.\n-  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.\n\nAdditional feedback and suggestions:\n- 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?\n- Typos and notation mismatch in the proof of Theorem 1 in the appendix: what is X in eq. 13? index j in eq. 12?\n- 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.\n- 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? \n\nCorrectness: The analyses are solid and the claims are correct. \nRelation to prior work: The paper has clearly discussed the connections with the previous works.\nReproducibility: The details of the experiments and the public datasets are included in the paper. Thanks also for sharing the code.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GWwQiRnz6_-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a convex formulation for training a 2-layer neural network for reconstruction which should make training easier.\n\nIt’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.\n\nHowever, 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).\n\n* 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.\n* The main result is quite interesting even outside of regression. Would it be possible to extend it to other convex loss functions?\n* Stating that the dual is easier to interpret than the primal is debatable. The primal is also locally linear around almost all points.\n* Please make all images in figure 5 equally large.\n* 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.\n* 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.\n* 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.\n* Figure 1b is irritatingly not vertically centered\n* 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.\n* Has the number of sign patterns been ablated?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)