Denoising and Regularization via Exploiting the Structural Bias of Convolutional Generators
Authors: Reinhard Heckel and Mahdi Soltanolkotabi
Venue:  (2020)
Keywords: theory for deep learning
convolutional network
deep image prior
deep decoder
dynamics of gradient descent
overparameterization

Abstract: Convolutional Neural Networks (CNNs) have emerged as highly successful tools for image generation, recovery, and restoration. A major contributing factor to this success is that convolutional networks impose strong prior assumptions about natural images. A surprising experiment that highlights this architectural bias towards natural images is that one can remove noise and corruptions from a natural image without using any training data, by simply fitting (via gradient descent) a randomly initialized, over-parameterized convolutional generator to the corrupted image. While this over-parameterized network can fit the corrupted image perfectly, surprisingly after a few iterations of gradient descent it generates an almost uncorrupted image. This intriguing phenomenon enables state-of-the-art CNN-based denoising and regularization of other inverse problems. In this paper, we attribute this effect to a particular architectural choice of convolutional networks, namely convolutions with fixed interpolating filters. We then formally characterize the dynamics of fitting a two-layer convolutional generator to a noisy signal and prove that early-stopped gradient descent denoises/regularizes. Our proof relies on showing that convolutional generators fit the structured part of an image significantly faster than the corrupted portion. 

Published as a conference paper at ICLR 2020
DENOISING AND REGULARIZATION VIA EXPLOITING THE STRUCTURAL BIAS OF CONVOLUTIONAL GENER-
ATORS
Reinhard Heckel
Mahdi Soltanolkotabi
Dept. of Electrical and Computer Engineering Technical University of Munich
Dept. of Electrical and Computer Engineering University of Southern California so 1 srltaaan coltanol@usc.e.
re reinhard. heckel@ee tummm de
ABSTRACT
Convolutional Neural Networks (CNNs) have emerged as highly successful tools for image generation, recovery, and restoration. A major contributing factor this success is that convolutional networks impose strong prior assumptions about natural images. A surprising experiment that highlights this architectural bias to- wards natural images is that one can remove noise and corruptions from natural image without using any training data, by simply fitting (via gradient descent) a randomly initialized, over-parameterized convolutional generator to the corrupted image. While this over-parameterized network can fit the corrupted image per- fectly, surprisingly after few iterations of gradient descent it generates an almost uncorrupted image. This intriguing phenomena enables state-of-the- thee-arrt CNN- based denoising and regularization of other inverse problems. In this paper we attribute this effect to particular architectural choice of convolutional networks, namely convolutions with fixed interpolating filters. We then formally character- ize the dynamics of fitting two layer convolutional generator to noisy signal and prove that early-stopped gradient descent denoises/regularizes. Our proof re- lies on showing that convolutional generators fit the structured part of an image significantly faster than the corrupted portion.
INTRODUCTION
Convolutional neural networks are extremely popular for image generation. The majority of im- age generating networks is convolutional, ranging from deep convolutional Generative Adversarial Networks (DC-GANs) (Radford et al.) 2015) to the U-Net (Ronneberger et al.) 2013). known that convolutional neural networks incorporate implicit assumptions about the signals they generate, such as pixels that are close being related. This makes them particularly well suited for modeling distributions of images. It is less well known, however, that those prior assumptions build into the architecture are so strong that convolutional neural networks are useful even without ever being exposed to training data.
well
The latter was first shown in the Deep Image Prior (DIP) paper (Ulyanov et al., 2018). Ulyanov al. 2018) observed that when 'training' standard convolutional auto-encoder such the popu- lar U-net (Ronneberger et al.) 2015) on a single noisy image and regularizing by early stopping, the network denoises the image with excellent performance. This based on the empirical observation that un un-trained convolutional auto-decoders fit a single natural image faster when optimized with gradient descent than pure noise. Many elements of an auto-encoder, however are irrelevant for this effect: A more recent paper (Heckel & Hand 2019) proposed a much simpler image generating network, termed the deep decoder. This network can be seen as the relevant part convolutional generator architecture to function as image prior, and can be obtained from standard convolu- tional autoencoder by removing the encoder, the skip connections, and perhaps most notably, the trainable convolutional filters of spatial extent larger than one. Thus, the deep decoder does not learned or trainable convolutional filters like conventional convolutional networks do, and instead only uses convolutions with fixed convolutional kernels to generate image.

---

Published as a conference paper at ICLR 2020
(a) fitting noisy image
(b) fitting clean image
(c) fitting noise
0.04
DD-O
0.02
0.03
MSE
MSE
0.03
DIP
MSE
0.02
0.01
0.02
0.01
0.01
0
10
10a
10
10
10
10a
10
102
10
iteration
iteration
iteration
Figure 1: Fitting an over perapameeteeeee Deep Decoder (DD-O) and the deep image prior (DIP) to (a) noisy image, (b) clean image, and (c) pure noise. Here, MSE denotes Mean Square Error of the network output with respect to the clean image (a) and fitted images in (b) and (c). While the network can fit the noise due to wver-parameterization, it fits natural images in significantly fewer iterations than noise. Hence, when fitting a noisy image, the image component is fitted faster than the noise component which enables denoising via early stopping.
original image
noisy image I9
BM3D 28.6dB
DIP 29.2dB
DD-U 29.6dB
DD-O 29.9dB
Denoising with BM3D and various convolutional generators. The relative ranking of algorithms in this picture is representative and maintained larger set of test images (see Ap- pendix A). DD-U is an under-parameterized deep decoder. DIP and DD-O are over-parameterized convolutional generators and with early stopping outperform the BM3D algorithm, the next best method that does not require training data.
Figure 2:
In this paper, study such simple, untrained convolutional network theoretically. We consider the over-parameterized regime where the network has sufficiently many parameters to represent an arbitrary image (including noise) perfectly and show that:
Fitting convolutional generators via early stopped gradient descent provably denoises "natural" images.
To prove this statement, we characterize how the network architecture governs the dynamics of fitting over peraameeetee networks single (noisy) image. In particular prove:
Convolutional generators optimized with gradient descent fit natural images faster than noise.
We depict this phenomena in Figure[ where we randomly initialized over-puraeeterized convo- lutional generator to an image via running gradient descent on the objective L(C) = [[G(C) y Here, G(C) is the convolutional generator with weight parameters C, and y is either noisy image, a clean image, or noise. This experiment demonstrates that an over-paramette over-parameterized convolutional network fits natural image (Figure(Tp) much faster than noise (Figure (e) Thus, when fitting the noisy image (Figure [T], early stopping the optimization enables image denoising. This effect strong that it gives state-of-the the-the-rrt denoising performance (see Figure 2 and Appendix A). Be- yond denoising, this effect also enables significant improvements in regularizng a variety of inverse problems such compressive sensing (Veen et al. 2018 Heckel| 2019).
1.1 CONTRIBUTIONS AND OVERVIEW OF RESULTS
In this paper we take a step towards understanding why fitting a convolutional generator via early stopped gradient descent leads to such surprising denoising and regularization capabilities.
2

---

Published as a conference paper at ICLR 2020
M
2
21
Figure
The 1st, 2nt, 6th, and 21th trigonometric basis functions in dimension n 300.
We first show experimentally that this denoising phenomena primarily attributed to con- volutions with fixed interpolation kemnlls, typically implicitly implemented by bi-linear upsampling operations in the convolutional network.
We then show that fitting an over-vvvreee wver-parameterized convolutional networks (with fixed convo- lutional filters) via early stopped gradient descent to signal provably denoises it.
Specifically, let E I be a smooth signal that can be represented exactly as linear combination the p orthogonal trigonometric functions of lowest frequency (defined in equation (5), Figure for depiction). A smooth signal is good model for natural image since natural images are well approximated by low-frequency components. Specif- icallyy Figure 4 in (Simoncelli & Olshausen (00T) shows that the power spectrum of natural image (i.e., the energy distribution by frequency) decays rapidly from low frequen- cies to high frequencies. In contrast, Gaussian noise has flat power spectrum.
Our goal is to obtain an estimate this signal from noisy observation = x - z where I is Gaussian noise. Let y G(C,) ) be the estimate obtained from early
z NO0, x stopping the fitting of two-layer convolutional generator to y. We prove this estimate achieves the denoising rate
x12 c
y
with constant. This rate is optimal up constant factor.
Our denoising result follows from detailed analysis of gradient descent applied fitting convolutional generator G(C) to a noisy signal y = x with x representing the signal and z the noise. We show that there weights ,i,.... Tn associated with the trigonometric basis function that only depend on the convolutional filter used, and which typically decay quickly from the low-frequency the high-frequency trigonometric basis functions. These weights in turn determine the speed at which the associated components of the signal are fitted. Specifically, we show that the dynamics of gradient descent are approximately given by
G(CC)) x Σ Wi (W,, (1- ,
Wi (w., ((1 noo))= 1).
error in litting sigual
fit of noise
The convolutional filters commonly used are such that the weights d1,..., Tn decays quickly, implying that low-frequency components the trigonometric expansion are fit- ted significantly faster than high frequency ones. So if the signal mostly consists of low- frequency components, we can choose an early stopping time such that the error fitting the signal is very low, and thus the signal part is well described, whereas at the same time only a small part of the noise, specifically the part aligned with the wow-frequeccy compo- nents has been fitted.
2 CONVOLUTIONAL GENERATORS
A convolutional generator maps an input tensor Bo to image only using upsampling and con- volutional operations, followed by channel normalization (a special case of batch normalization) and applications of non- -ine-lirairiies
Figure 4 All previously mentioned convolutional generator networks (Radford et al. 2015) Ronneberger et al. 2015) including the networks considered in the DIP paper (Ulyanov al. 2018)) primarily consist of those operations.
For motivating the architecture of the convolutional generators studied in this paper, we first demon- strate in Section 2.1 that convolutions with fixed interpolation filters are critical the denoising
3

---

Published as a conference paper at ICLR 2020
fixed kernels
learned kernels
Convolution ReI.U normalization
0.15
lin. combinations, sigmoid
0.1
0.05
o.2
Bo
B
B3
B
0.08
0.06
0.04
0.02
10a
10*
10
102
104
10
optimizer steps
optimizer steps
Left panel: Convolutional generators. The output is generated through repeated con- volutional layers, channel normalization, and applying ReLU non-linearities. Right panel: Fitting the phantom MRI and noise with different architectures depth d 5, for different number of over-parameterizzaioon factors (1,4, and 16). Gradient descent convolutional generators involving fixed convolutional matrixes fit an image significantly faster than noise.
Figure 4:
performance with early stopping. Specifically, empirically show that convolutions with fixed convolutional kernels are critical for convolutional generators to fit natural images faster than noise. In Section 2.2 we formally introduce the class of convolutional generators studied in this paper, and finally, in Section 2.3 we introduce a minimal convolutional architecture which is the focus of our theoretical results.
2.1 THE IMPORTANCE FIXED CONVOLUTIONAL FILTERS
Convolutions with fixed convolutional kernels are critical for denoising with early stopping, because they are critical for the phenomena that natural images are fitted significantly faster than noise. To see this, consider the experiment in Figure 4 in which we fit an image and noise by minimizing the least-squares loss via gradient descent with tional filters (see Section 2.2 below for precise description) and ii) conventional convolutional generator with trainable convolutional filters (essentially the architecture from the popular DC-GAN generators, Appendix B for details and additional numerical evidence). As illustrated in Figure the convolutional network with fixed filters fits the natural image much faster than noise, whereas the network with learned convolutional filters, only fits slightly faster, and this effect vanishes as the network becomes highly overparameterized. Thus, fixed convolutional filters enable un un-trained convolutional networks function as highly effective image priors. We note that the upsampling op- eration present in most architectures implicitly incorporates a convolution with a fixed convolutional (interpolation) filter.
convolutional generator with only fixed convolu-
2.2
ARCHITECTURE OF CONVOLUTIONAL GENERATOR WITH FIXED CONVOLUTIONS
In this section, we describe the architecture of the deep decoder (Heckel & Hand 2019), a convo- lutional network with fixed convolutional operators only, In this architecture, the channels in the (i + 1)-th layer are given by
B++1 = en (R(BeLL(U,B.C..))
i= i=0...,d-1
and finally, the output of the d-layer network is formed as
x BBBCCat1-
Here, the coefficient matrices C; E R and Ca+1 E RRikk contain the weights of the network. The number channels, k, determines the number weight parameters of the network, given by dk - koutk. Each column of the tensor B, C, E [g is formed by taking linear combinations of the channels of the tensor B, in a way that is consistent across all pixels, and the ReLU activation function is given by ReLU(t) tion which normalizes each channel individually and can be viewed as a special case of the popular batch normalization operation (loffe & Szegedy 2015). 2015).
max(0. t). Then, en(-) performs the channel normalization opera-
4

---

Published as a conference paper at ICLR 2020
The operator U, R is tensor implementing an upsampling and most importantly convolution operation with a fixed kernel. This fixed kernel was chosen in all experiments above as triangular kernel that U performs bi-linear 2x upsampling (this is the standard implementation in the popular software packages pytorch and tensorflow). As mentioned earlier this convolution with a fixed kernel is critical for fitting natural images faster than complex ones.
2.3 TWO LAYER CONVOLUTIONAL GENERATOR STUDIED THEORETICALLY IN THIS PAPER
The simplest model to study the denoising capability of convolutional generators and the phenomena that natural image is fitted faster than a complex one theoretically a network with only one hidden layers and one output channel i.e., ((C) E R". Then, the generator becomes
G(CC) ReL
where U E R is circulant matrix that implements convolution with filter In this paper consider the wver-parameterized regime where 2 2n. Note that scaling the i-th column of Co with non-negativ factor is equivalent scaling the i-th entry of the output weights с₁ with the same factor. We therefore fix the output weights C₁ = where note that both the generators with the fixed output weights and non-fixed output weights have the 2n. Next, because the matrix Bo Gaussian, with probability one,
1,...,,,-1,........ -1]/ -1//Vk. Next,
same range in the regime has full rank and thus spans R". It follows that optimizing over the parameter Co in C = Co is equivalent to optimizing over the matrix C E T We therefore consider the generator
G(C) = ReLUUUC)),
(I)
where [1, 1,
1j/vK is fixed and C E Rank is the new coefficient matrix we optimize over. Figure 11 in the appendix shows that even this simple two-layer convolutional net- work fits a simple image faster than noise. This is the simplest model in which the phenomena that convolutional networks fits structure faster than noise can reliably be observed. As consequence, the dynamics of training the model 11 are the focus of the remainder this paper.
WARMUP: DYNAMICS OF GRADIENT DESCENT ON LEAST SQUARES
As a prelude for studying the dynamics of fitting convolutional generators via a non-linear least square problem, we study the dynamics of gradient descent applied to a linear least squares problem. We demonstrate how early stopping can lead to denoising capabilities even with simple linear model. We consider a least-squares problem of the form
[(c) = lly - Jcl
2
and study gradient descent with constant step size 17 starting at Cu = 0. The updates are given by
C++1 = C, - v/(cc,,, VL(c) J J' y).
The following simple proposition characterizes the trajectory of gradient descent.
Proposition 1. Let J E Raxm be a matrix with left singular vectors Wi...., , Wa E R and corre- sponding singular values 2 2 2 on- Then the residual after T steps, r, y - Jc,, of
gradient descent starting at Co = 0
w; (W., (1 (1-1o?)
Suppose that the signal y lies in the column span of J, and that the stepsize is chosen sufficiently small (i.e., 17 S 1/ [|]](") Then, by Proposition| gradient descent converges a zero-loss solution and thus fits the signal perfectly. More importantly, gradient descent fits the components of y corre- sponding to large singular values faster than fits the components corresponding to small singular values.
To explicitly show how this observation enables regularization via early stopped gradient descent, suppose our goal is to find good estimate of signal from noisy observation
y 2,
5

---

Published as a conference paper at ICLR 2020
14
singular value ds
Jerlla
1.2
[|w] JJ., Ill
0.8
0.5
0.6
0.8
0.6
0
50 100
500
1,000
500
1,000
Figure Gradient descent on the least squares problem of minimizing I Jc, 11 where J 1100x100 has decaying singular values (left panel) and the observation is the sum of a signal component, equal to the leading singular vector w1 of J, and noisy component z ~ ~N (1/n)I), i.e. y Wi + z. The signal component wi is fitted significantly faster than the other components (right panel), thus early stopping enables denoising.
where the signal lies in signal subspace that is spanned by the p leading left-singular vectors of J. Then, by Proposition
1
the signal estimate after iterations, Jcr, obeys
JJc, x1112 S (1 " |xx|| + E(z),
E(z) = Σ ((1 ((1mnop) 1)2 (w,,,, z)²
(2)
Thus, after a few iterations most of the signal has been fitted (i.e., (1 (1-11) - ) is small). Furthermore, we assume that the ratio 0p/0p-1 sufficiently large so that the spread between the two singular values separating the signal subspace from the rest is sufficiently large, most of the noise outside the signal subspace
been fitted (i.e., ((1 no??" 1)2 for = p 1, ..).
In particular, suppose the noise vector has a Gaussian distribution given by x ~ N(0, ET). Then E(z) R sVR. so that after order log(e)/ log(1 (ooz)) iterations, with high probability,
Jc, - x112 S ||x||| + /
This demonstrates, that provided the signal lies in a subspace spanned by the leading singular vec- tors, early stoped gradient descent reaches the optimal denoising rate s s/p/n after a few itera- tions. See Figure for numerical example demonstrating this phenomena.
4 DYNAMICS OF GRADIENT DESCENT ON CONVOLUTIONAL GENERATORS
We now ready to study the implicit bias of gradient descent towards natural/structured images theoretically. Consider the two-layer network (introduced in Section 2.3) of the form
G(C) = ReLU(UC)v,
where v = 1,, - 1)/Vi, and with weight parameter C E Ba*k and recall that U is a circulant matrix implementing a convolution with kernel R". We fit the generator signal E R" by minimizing the non- non-linear least squares objective
1 lly G(C)
((C) =
with (early-stopped gradient) descent with constant stepsize 7) starting at random initialization Co of the weights. The iterates are given by
C,+1= = -)VCCC
(4)
In our warmup section on linear least squares we saw that the singular vectors and values of the ma- trix J determine the speed at which different components of the noisy signal y fitted by gradient descent. The main insight that enables us to extend this intuition to the nonlinear case is that the role
of the matrix J can be replaced with the Jacobian of the generator, defined as J(C) 36 G(C).

---

Published as a conference paper at ICLR 2020
10
0.8
10
0.6
0.5
10
10-1
10
3
10-3
120
140
160
180
100
200
300
120
140
160
180
0
100
200
300
(a) triangular kemel
(b) triangular dual kernel
(c) Gaussian kernel
(d) Gaussian dual kemel
Triangular and Gaussian kernels and the weights associated to low-frequency trigono- metric functions they induce, for generator network of output dimension n 300. The wider the kernels are, the more the weights are concentrated towards the low-frequency components of the signal.
Figure 6:
Contrary the linear least squares problem, however, in the nonlinear case, the Jacobian is constant and changes across iterations. Nevertheless, we show that the eigen-values and vectors of the Jacobian the random initialization govern the dynamics of fitting the network throughout the iterative updates.
For the two-layer convolutional generator that consider, the left eigenvectors of the Jacobian mapping can be well approximated by the trigonometric basis functions, defined below, throughout the updates. Interestingly, the form of these eigenvectors only depends on the network architecture and not the convolutional kernel used.
Definition 1. The trigonometric basis functions W Wi...ry are defined as
= 0
c0co((2rji/m)
1,..., n1/2
[w++
(5)
Vn
(-1y
n/2
(2iin(2))) n/2 1,....
Figure depicts some of these eigenvectors.
In addition to the left eigenvectors we can also approximate the spectrum of the Jacobian throughout updates by an associated filter/kernel that only depends on the original filter/kernel used in the network architecture.
Definition 2 (Dual kemel). Associated with kernel E
R we define the dual kernel
R"
u c u
COs -1 (t)
|ulla
Fg
with g(t)
t.
Here, for two vectors u, v E IR"", u @ v denotes their circular convolution, the scalar non non-linearity g is applied entrywise, and F is the discrete Fourier transform matrix.
In Figure 6 depict two commonly used interpolation kernels u, namely triangular and Gaus- sian kernel (recall that the standard upsampling operator is convolution with a triangle), along with the induced dual kernel o. The figure shows that the dual kernel induced by these kernels has few large values associated with the low frequency trigonometric functions, and the other values associated with high frequencies are very small.
With these definitions in place we are ready to state our main denoising result. A denoising result requires signal model-we assume a low-frequency signal that can be represented as a linear combination of the first p-trigonometric basis functions. Note that this is good model for natu- ral image since natural images are well approximated by low-frequency components. Specifically, Figure in (Simoncelli & Olshausen 2001) shows that the power spectrum of natural image (i.e., the energy distribution by frequency) decays rapidly from low frequencies to high frequencies. In contrast, Gaussian noise has flat power spectrum.

---

Published as a conference paper at ICLR 2020
Theorem 1 (Denoising with early stopping). Let x R" be signal in the span of the first p trigonometric basis functions, and consider a noisy observation
y = x 2,
where z is Gaussian noise with distribution No S D. for some variance 5² Z 0. To denoise this
"
signal, we fit two layer generator network G(C) ReLU(UC)y with,
2 Cun/C,
channels, for some > O, and with convolational kernel of the convolutional operator U and associated dual kernel a, to the noisy signal y. Here, Cu a constant only depending on the convolu- tional kernel u. Then, with probability at least 1 e e- n22, the reconstruction error obtained after
T loo(11 ///nn/ log(1 npp+t) iterations of gradient descent (4) with step size di S |F (Fu is the Fourier transform of u) starting from Co with ii.d W)),w?). entries, x bounded by
llyll2
vn is
2p elyyl12-
[[G(C+) xx12 (1 n))))" | + SV.
Note that for this choice of stopping time, provided that dual kernel decays sharply around the p-th singular value, the first term in the bound (i.e., (1 (o- 0) essentially vanishes and the error bound becomes O(s / The dual kernel decays sharply around the leading eigenvalues provided the kernel is for example sufficiently wide triangular Gaussian kernel (see 6
This result demonstrates that when the noiseless signal x is sufficiently structured (c.g. contains only the p lowest frequency components in the trigonometric basis) and the convolutional generator has sufficiently many channels, then early stopped gradient descent achieves a near optimal denoising performance proportional to 5 / P. This theorem is obtained from a more general result stated the appendix which characterizes the evolution of the reconstruction error obtained by the convolutional generator.
Theorem (Reconstruction dynamics of convolutional generators). Consider the setting and as- 7 but now with a fixed noise vector and without explicit stopping time. Then, for all iterates T obeying T S 100 and provided that k 2 Cun/E*, f some e (0, zt). with na
sumptions of Theorem
probability at least - e n². the reconstruction error obeys
||G(C,) - x112 S (1 - no ||x||
Σ (11 no?) - 1)2 (w, z3² + e||y|12
This theorem characterizes the reconstruction dynamics of convolutional generators throughout the updates. In particular, it explains why convolutional generators fit natural signal significantly faster than noise, and thus early stopping enables denoising and regularization. To see this, note that as mentioned previously each of the basis functions w; has (positive) weight o; >> 0 associated with it that only depends on the convolutional kernel used in the architecture (through the definition of the dual kernel). These weights determine how fast the different components of the noisy signal are fitted by gradient descent. As we demonstrated earlier in Figure 6 for typical convolutional filters those weights decay very quickly from low to high frequency basis functions. As result, when the signal x is sufficiently structured (i.e. lies in the range of the trigonometric functions with lowest frequencies), after a few iterations most of the signal is fitted (i.c., (1 - - is small), while most of the noise has not been fitted (i.e., ((1 n - 1)² s 0 for = p + 1...., Thus, early stopping achieves denoising.
The proof, provided in the appendix, is based on associating the following linear least-squares prob- lem with the non-linear least squares problem
1 GG(Ca) + J(cc vect - -y1
Lin (c)
8

---

Published as a conference paper at ICLR 2020
Here, voct(Co) R is vectorized version of the matrix Co, and J E R"xnk approximates the Jacobian of G(C) around the initialization Co. The linear leaat-squares problem is obtained by linearizing the non-linear problem around the initialization. In the proof we show that if i) the network is sufficiently over-parameterized and if ii) the network is randomly initialized, then the linearized problem is good approximation of the non-linear problem. We then show that the singular values of the Jacobian J are the trigonometric basis functions, and the singular values are the values of the dual kernel. The proof is then concluded by characterizing the trajectory of gradient descent applied to the linear least-squares problem above.
4.1 MULTILAYER NETWORKS AND MODERATE OVER- PARA--AEERAAATTTOOO
Our theoretical results rely on the finding that for wver-parameterized single hidden-layer networks, the leading singular vectors of the Jacobian are the trigonometric functions throughout all itera- tions, and that the associated weights (i.e.. the singular values) are concentrated towards the low frequency components. In this regime, the dynamics are well approximated by a linear model. This general strategy can be extended to multi-layer networks, however if the network is not highly over- parameterized, an associated linear model might not be a good approximation.
In order to understand whether our finding of low-frequency components being being fitted faster than high-frequency ones carries over to multi-layer networks and to the moderately over- parameterized regime, in this section, we study muli-layer networks in the moderately overparame- terized regime numerically. We show that for multilayer network, the spectrum of the Jacobian is concentrated towards singular vectors/functions that are similar to the low-frequency components. We also show that throughout training those functions do vary, albeit the low frequency components do not change significantly and the spectrum remains concentrated towards the low frequency com- ponents. This shows that the implications of our theory continue apply muli-layer networks.
In more detail, we take a standard one dimensional deep decoder with = 4 layers with output in R512 and with k: 64 channels in each layer. Recall that the standard tains layer ++1 from layer by linearly combining the channels of layer with learnable coefficients followed by linear upsampling (which involves convolution with the triangular kernel [1/2, 1, 1/2). The number of parameters is d x h²2 = 32 512, so the network is over- parameterized by a factor of 32. In Figure we display the singular values as well as the leading singular vectors/function of the Jacobian at initialization (t = 1) and after t = 50 and t = 3500 iterations of gradient descent. As can be seen the leading singular vectors (s = 1 5) are close to the trigonometric basis functions and do not change dramatically throughout training. The singular vectors corresponding to increasingly smaller singular values (s = 20, 50, 100, 150) contain increasingly higher frequency components but are far from the high- figh-frreuenny trigonometric basis functions.
dimensional decoder ob-
5 RELATED LITERATURE
As mentioned before, the DIP paper (Ulyanov al. 2018) was the first show that over- parameterized convolutional networks enable solving denoising, inpainting, and super-resolution problems well even without any training data. Subsequently, the paper (Heckel & Hand 2019) pro- posed much simpler image generating network, termed the deep decoder. The papers (Veen et al.] 2018 Heckel 2209 Jagatap Hegde 2019 Bostan et al. 2020) have shown that the DIP and the deep decoder also enable solving or regularizing compressive sensing problems and other inverse problems.
Since the convolutional generators considered here are mmage-generating deep networks, our work also related to methods that rely on trained deep image models. Deep learning based methods are either trained end-to-end for tasks ranging from compression (Toderici et al. 2016 Agustsson et al.)
2017 Theis et al. 2017 Burger et al. 2012: Zhang et al. (017)) to denoising (Burger et al. 2012 Zhang et al. 2017). 7), or are based on learning generative image model (by training autoencoder
or GAN (Hinonn & Salakhutdinov 2006; Goodfellow et al. 2014)) and then using the resulting
model solve inverse problems such compressed sensing (Bora et al.) 2017 Hand & Voroninski, 2018). denoising (Heckel et al. 2018), or phase retrieval (Hand et al. 2018), by minimizing an associated loss. In contrast to the method studied here, where the optimization is over the weights

---

Published as a conference paper at ICLR 2020
at f
at = 50
at 3500
0.1
0.05
0
104
0.05
0.1
10
200 400
0 200 400
200 400
0 200 400
(b)
(c) 2
(d)
(c) =
10
0.1
200
400
M
0.05
1M 1
(a) singular values
0
0.05
0.1
200 400
0 200 400
200 400
200 400
(f)
20
(h) 50
(i) S 100
Figure 7: The Singular value distribution of the Jacobian of a four-layer deep decoder after = 50 and t 3500 iterations of gradient descent (panel (a)). along with the corresponding singular vectors/function (b-i). The singular functions corresponding to the large singular vectors are close to the low-frequency Fourier modes and do not change significantly through training.
of the network, in all the aforementioned methods, the weights adjusted only during training and then are fixed upon solving the inverse problem.
A large body of work focuses understanding the optimization landscape of the simple nonlin- carities or neural networks (Candes et al.] [2015; Soltanolkotabi 2017 Alon Brutzkus & Globerson 2017 Zhong et al., 2017; Oymak 2018 Fu al. [018 Tu al. (016)) when the labels are created according to a planted model. Our proots rely on showing that the dynamics of gradient descent on an over- peee-parameterieed network can be related that of a linear network kernel problem. This proof technique has been utilized in variety of recent publication (Soltanolkotabi et al. 2018 Ven- turi et al. | 2019 Du et al. (2188 Oymak & Soltanolkotabi) 2019a b. Arora al. 2019 Oymak al. 2019). Two recent publication have used this proof technique to show that functions are learned at different rates: Basri et al.] (2019) have shown that functions of different frequencies are learned at different speeds, and Arora al. (2019) has provided theoretical explanation of the empirical observation that simple 2-layer network fits random labels slower than actual labels in the context of classification. A recent publication (Li al. 2019) focuses demonstrating how early stopping leads to robust classification in the presence of label corruption under a cluster model for the input data. Neither of the aforementioned publication however, does address denoising in regression setting or fitting convolutional generators of the form studied in this paper.
CODE AND ACKNOWLEDGEMENTS
Code to reproduce the experiments is available at http::://github.com//ii... overparraeeeerize.. cerdd_covollse connvolutiooallo oeeeerrrrtgeee
R. Heckel is partially supported by NSF award IIS-18 1816966, acknowledges support of the NVIDIA Corporation form of a GPU, and would like to thank Tobit Klug for proofreading previous version of this manuscript. M. Soltanolkotabi is supported by the Packard Fellowship in Science and Engineering, a Sloan Research Fellowship in Mathematics, an NSF-CAREER under award # #1846369, the Air Force Office of Scientific Research Young Investigator Program (AFOSR-YIP) under award #FA9550- 11155001----078, an NSF-CIF award #1813877, DARPA under the Learning with Less Labels (LwL..) program, and Google faculty research award.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Eirikur Agustsson, Fabian Mentzer, Michael Tschannen, Lukas Cavigelli, Radu Timofte, Luca Benini, and Luc V Gool. Soft-to-hard vector quantization for end-to-end learning compressible representations. In Advances in Neural Information Processing Systems, pp. 1141-1151, 2017
A. Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with Gaus- sian inputs. In International Conference on Machine Learning, 2017.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning. 2019.
Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In Advances Neural Information Pro- cessing Systems, 2019.
A. Bora, A. Jalal, E. Price, and A. G. Dimakis. Compressed sensing using generative models. In International Conference on Machine Learning, 2017.
Emrah Bostan, Reinhard Heckel, Michael Chen, Michael Kellman, and Laura Waller. Deep phase decoder: Self-calibrating phase microscopy with an untrained deep neural network. arXiv:2001.09803 [physics], 2020.
H. C. Burger, C. J. Schuler, and Harmeling. Image denoising: Can plain neural networks compete with BM3d? In JEEE Conference on Computer Vision and Pattern Recognition, pp. 2392-2399, 2012.
Emmanuel J. Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, 64, 2015.
K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian. Image denoising by sparse 3-D transform- domain collaborative filtering. IEEE Transactions on Image Processing, 16(8):2080- 2095, 2007.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances in Neural Information Processing Systems, pp. 2253-2261, 2016.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2018.
Haoyu Fu, Yuejie Chi, and Yingbin Liang. Local geometry of one-hiddeen-laer neural networks for logistic regression. arXiv: 2018.
I. Goodfellow, Pouget-Abadic, M. Mirza, B. Xu, D. Warde-Farley, Ozair, A Courville, and Y. Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-26880 2014.
Paul Hand and Vladislav Voroninski. Global guarantees for enforcing deep generative priors by empirical risk. In Conference on Learning Theory, 2018. arXiv:1705.07511
Paul Hand, Oscar Leong, and Vladislav Voroninski. Phase retrieval under generative prior. In Advances in Neural Information Processing Systems, 2018
Reinhard Heckel. Regularizing linear inverse problems with convolutional neural networks.
arXiv:1907.03100, 2019.
Reinhard Heckel and Paul Hand. Deep decoder: Concise image representations from untrained non-convolutional networks. In International Conference on Learning Representations, 2019.
Reinhard Heckel, Wen Huang, Paul Hand, and Vladislav Voroninski. Deep denoising: Rate-optimal recovery of structured signals with deep prior.
2018.

---

Published as a conference paper at ICLR 2020
G. E. Hinton and R. R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313 507, 2006.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 2015.
Gauri Jagatap and Chinmay Hegde. Algorithmic guarantees for inverse imaging with untrained network priors. In Advances in Neural Information Processing Systems, 2019.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. arXiv:1903.11680 2019.
Samet Oymak. Stochastic gradient descent learns state equations with nonlinear activations.
arXiv: 03019, 2018.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterizee nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning, 2019a.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparametterization:: Global conver- gence guarantees for training shallow neural networks. arXiv: 2019b.
Samet Oymak. Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. Generalization guarantees for neural networks via harnessing the low-rank structure of the jacobian. arXiv: 1rX55:190..0539., 2019.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv: [cs], 2015.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedi- cal image segmentation. Lecture Notes in Computer Science, 2015.
Ecro P Simoncelli and Bruno Olshausen. Natural image statistics and neural representation. Annual Review of Neuroscience, 24(1):1193-1216 2001.
Mahdi Soltanolkotabi. Learning ReLUs via gradient descent. In Advances in Neural Information
Processing Systems, 2017.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 2018
Lucas Theis, Wenzhe Shi, Andrew Cunningham, and Ferenc Huszár. Lossy image compression with compressive autoencoders. arXiv:1703.00395, 2017.
George Toderici, Sean M. OMalley. Sung Jin Hwang, Damien Vincent, David Minnen, Shumeet Baluja, Michele Covell, and Rahul Sukthankar. Variable rate image compression with recurrent neural networks. International Conference on Learning Representations, 2016.
Joel A. Tropp. freenfiienlly tail bounds for sums of random matrices. Foundations of Computa- tional Mathematics, 12(())389 4344, Aug 2011.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions linear matrix equations via procrustes flow. International Conference on Machine Learning, 2016.
D. Ulyanov, A. Vedaldi, and V. Lempitsky. Deep image prior. In Conference on Computer Vision and Pattern Recognition, 2018.
Dave Van Veen, Ajil Jalal, Mahdi Soltanolkotabi, Eric Price. Sriram Vishwanath, and Alexan- dros G. Dimakis. Compressed sensing with deep image prior and learned regularization. (XX6::800600643 2018.
L. Venturi, A. Bandeira, and J. Bruna. Spurious valleys in two-layer neural network optimization landscapes. Journal on Machine Learning Research, 2019.
12

---

Published as a conference paper at ICLR 2020
K. Zhang, W. Zuo, Y. Chen, D. Meng, and L. Zhang. Beyond Gaussian denoiser: Residual learning of deep CNN for image denoising. IEEE Transactions on Image Processing, 26(7):3142-3155, 2017.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one-hidden-layer neural networks. In International Conference on Machine Learning, 2017.
A DENOISING PERFORMANCE OF UNTRAINED CONVOLUTIONAL GENERATORS
In this section, we provide further details on the denoising performance of deep neural networks. We compare the denoising performance of four methods: i) the BM3D algorithm (Dabov et al. 2007) as a standard baseline for denoising, ii) the deep image prior (Ulyanov et al. 2018), which is a U-net like encoder-decoder convolutional architecture applied with exactly the parameters as proposed for denoising in the paper (Ulyanov et al., 2018), and early stopped after 1900 iterations, again with the same stopping time proposed in the original paper, iii) an padder-prramterrzzedd deep decoder with five layers and k- = 128 channels in each layers, trained for 3000 iterations (which is close convergence), iv) an over-vvevaae wer-parameterized deep decoder with five layers and k 512 channels in each layer, early stopped at 1500 iterations. We compared the performance of those four methods on denoising 100 randomly chosen images from the ImageNet validation set. The code to reproduce the results contains a list of the images we considered. Each image has 512 x 512 pixels and three color channels. We added the same random Gaussian noise to each color channel, because we are interested in evaluating the performance by imposing structural assumptions the image. Table [] below show that the overparameterized deep decoder with early stopping performs best for this task.
Noise level
20.60
Deep decoder with k=512 and early stopping deep decoder with k=128 without early stopping DIP BM3D
28.08dB
27.84dB
25.76 dB
25.52 dB
Table I: Average performance for denoising images color image with the same Gaussian noise added each color channel with BM3D and un- traired convolutional neural networks. The over- parameterized deep decoder performs best for this task.
B A NUMERICAL STUDY OF THE IMPLICIT BIAS OF CONVOLUTIONAL NETWORKS
In this section, we empirically demonstrate that convolutions with fixed convolutional kernels are critical for convolutional generators to fit natural images faster than noise. Towards this goal, we study numerically the following four closely related architectural choices, which differ in the gesaappliggnn-uusamppp
and convolutional operations which generate the activations in the (i + 1)-st layer, B,+1, from the activations in the i-th layer, B,:
i) Bilinear upsampling and linear combinations. Layer is obtained by linearly com- bining the channels of layer with learnable coefficients (i.e., performing one-timen tee-ttmcs-onee convolutions), followed by bi-linear upsampling. This is the deep decoder architecture from (Heckel et al.) 2018).
ii) Fixed interpolation kernels and linear combinations. Layer 1 is obtained by lin- early combining the channels of layer i with learnable coefficients followed by convolving each channel with the same 4x4 interpolation kernel that is used in the linear upsampling operator.
iii) Parameterized convolutions: Layer i is obtained from layer though convolutional layer.
iv) Deconvolutional network: Layer + 1 is obtained from layer though a deconvolution layer. This is essentially the DC-GAN (Radford et al. 2015) generator architecture.
13

---

Published as a conference paper at ICLR 2020
bilinear
fixed kernels
param. convs
deconvolutions
0.15
4
0.1
16
16
16
0.05
0
0.08
0.06
0.04
0.02
0
102
10*
10
102
10
10
102
10
10c
10
104
10
aptimizer steps
optimizer steps
optimizer steps
optimizer steps
Fitting the phantom MRI and noise with different architectures of depth = 5, for different number of over-parameteriiation factors (1,4, and 16). Gradient descent on convolutional generators involving fixed convolutional matrixes fit an image significantly faster than noise.
Figure 8:
To emphasize that architectures i)-iv) are structurally very similar operations, we recall that each operation consists only of upsampling and convolutional operations. Let T(c): RR" - R= be the convolutional operator with kernel c, let u the linear upsampling kernel (equal to u = [0.5, 1, 0.5] in the one-dimensional case), and let U: R + IR2n be upsampling operator, that in the one dimensional case transforms T2.. 2n. to [x1. 22, ...... 0j. each the architec- tures i)-iv), the (-th channel of layer i + is obtained from the channels in the i-th layer
Zn.
bit1. ReLU (Σ/=1 M(Cuje)b:) where the linear operator M is defined as follows for the four architectures
M(c) TT(),,, ii) M(c) cT)) iii) M(c) T(c), iv) M(c) T(c)U.
The coefficients associated with the i-th layer given by C, {cyj and all coefficients of the networks are {Cıze). Note that here, the coefficients or parameters of the networks are the weights and not the input to the network.
B. DEMONSTRATING IMPLICIT BIAS OF CONVOLUTIONAL GENERATORS
We next show that convolutional generators fixed convolutional operations natural or simple images significantly faster than complex images noise. Throughout this section, for each image or signal x" we fit weights by minimizing the loss
((C) -x
with respect to the network parameters C using plain gradient descent with a fixed stepsize.
In order exemplify the effect, we fit the phantom MRI image as well noise for each of the architectures above for 5-layer network. We choose the number of channels, k, such that the over-param werrparrameterization factor (i.c., the ratio of number of parameters dimensionality) is 1,4, and 16, respectively. The results in Figure R show that for architectures i) and involving fixed convolutional operations, gradient descent requires more than one order of magnitude fewer iterations to obtain good fit of the phantom MRI image relative to noise. For architectures iii) and iv), with trainable convolutional filters, we see a smaller effect, but the effect essentially vanishes when the network is highly over- peee-paramtteriee..
the network over the output
This effect continues to exist for natural images in general, as demonstrated by Figure I0 which depicts the average and standard deviation of the loss curves of 100 randomly chosen images from the imagenet dataset.
We also note that the effect continues exist in the sense that highly structured images with large number of discontinuities are difficult to fit. An example is the checkerboard image which each pixel alternates between 1 and O; this image leads to the same loss curves noise.
In our next experiment, we highlight that the distance between final and initial network weights is key feature that determines the difference of fitting natural image and noise. Towards this goal,
14

---

Published as a conference paper at ICLR 2020
natural image
noise
relative distance
0.008
0.6
0.006
0.4
0.004
0.002
0.2
50,000 1 109
50,000 1 10
optimizer steps
optimizer steps
Figure 9: The relative distances of the weights in each layer from its random initialization. The weights need to change significantly more to fit the noise, compared to an image, thus natural image lies closer random initialization than noise.
(a) fitting images
(b) fitting pure noise
0.08
0.1
0.06
0.05
0.04
0.02
0
10
102
10
10
102
10a
optimizer steps
optimizer steps
Figure 10: The loss curves for architecture i), convolutional generator with linear upsampling operations, averaged over 100 3 x 512 x 512 (color) images from the Imagenet dataset. The error band one standard deviation. Convolutional generators fit natural images significantly faster than noise.
we again fit the phantom MRI image and noise for the architecture i) and an over-paramettrizztion factor of 4 and record, for each layer the relative distance ||C (0) |/ ||, where c, are the weights at initialization (we initialize randomly), and c the weights the optimizer step t. The results, plotted in Figure g show that to fit the noise, the weights have to change significantly, while for fitting a natural image they only change slightly.
C THE SPECTRUM OF THE JACOBIAN OF THE DEEP DECODER AND DEEP IMAGE PRIOR
Our thcoretical results predict that for wer-parameterizedd networks, the parts of the signal that is aligned with the leading singular vectors of the Jacobian at initialization is fitted fastest. In this section we briefly show that natural images are much more aligned with the leading singular vectors than with Gaussian noise, which is equally aligned with each of the singular vectors.
(a) step function
(b) step function fit MSE
(c) noise
(d) noise fit MSE
1
0.5
0
200
400
10a
10a
102
100
200
400
10
10a
10a
10a
optimizer steps
optimizer steps
Figure 11:
Fitting a step function and noise with a two-layer deep decoder: Even for two-layer network, the simple image (step function) is fitted significantly faster than the noise.
15

---

Published as a conference paper at ICLR 2020
(a) deep decoder
(b) deep image prior
0.006
N=Noie
Noise
frequency
0.004
y I=I
y Im
0.002
0.5
0.2
0.4
0.6
0.8
[TT(0))1
-104
(0)))
-10
Figure 12: The distribution of the 2z-norm of the inner product of the Jacobian of a deep decoder (a) and deep image prior (b) at random initialization, with an image y = x" and noise y both of equal norm. For both deep decoder and deep image prior, this quantity is significantly smaller for noise than for natural image. Thus, natural image is better aligned with the leading singular tors of the Jacobian than noise. This demonstrates that the Jacobian of the networks is approximately low-rank, with natural images lying in the space spanned by the leading singularvectors.
Towards this goal, we compute the norm of the product the Jacobian at a random initalization, Co. with signal y this measures the extent to which the signal is aligned with the leading singular vectors, due to
1 VVvTT "ystTyll"= Σ of (w.,
where J(C,)= WEVT is the singular value decomposition of the Jacobian.
Figure depicts the distribution of the norm of the product of the Jacobian at initialization, J ((Cu), with an image y" or noise z of equal norm (ly=*I ||z||). Since for both the deep decoder and the deep image prior, the norm of product of the Jacobian and the noise (i.e., || T (Co)zl|) is it follows that a structured
significantly smaller than that with a natural image (i.e., || image much better aligned with the leading singular vectors of the Jacobian than the Gaussian noise. which is approximately equally aligned with any of the singular vectors. Thus, the Jacobian random initialization has an approximate low-rank structure, with natural images lying in the space spanned by the leading singularvectors.
16

---

Published as a conference paper at ICLR 2020
D PROOFS AND FORMAL STATEMENT OF RESULTS
The results stated in the main text are obtained from slightly more general result which applies beyond convolutional networks. Consider neural network generators of the form
G(C) ReLU(UC)v,
with E Raxk and E Rox* an arbitrary fixed matrix, and E IR*, with half of the entries equal +1/VE and the other half equal to -1/VE.
The (transposed) Jacobian of ReLU(Uc) is U diag (Uc)). (UC)) Thus the Jacobian of G(C) is given by
81 U" diagg(ReL
J²(C)=
(9)
un U diag(RelLU((uxa))
where ReLU' is the derivative of the activation function. Next we define notion expected Jacobian. Towards this goal, first define the matrix
Σ(U) = B [I(C))" (C)] E RR
associated with the generator G(C) = ReLU Here, expectation is over C with iid /V w²)
entries. Note that since the derivative of the ReLU non-linearity is invariant to the scaling of C, so the Jacobian J (C), but to be consistent throughout we take expectation over with iid N N(O, entries. Consider the eigenvalue decomposition of E(U) given by
2 w. Σ(U)= Σ
2=1
Our results depend on the largest and smallest eigenvalue of E(U), defined throughout
of
B B= of = U
With these definitions in place we are ready to state our result about neural generators.
Theorem 3. Consider a noisy signal y E R" given by
y y=x+z
where x R. is assumed to lie in the signal subspace spanned by the p leading singular vectors Wi,..., Wn E(U), and z E Rn is an arbitrary noise vector. Suppose that the number of channels obeys
(1+
(1+
Sa 4
318 15
k 2
cn eng
(10)
where is fixed numerical constant and & an error tolerance parameter obeying 0 < { < 1/v 32 1/132 log (2 Moreover, T is the maximal number of gradient descent steps, and we assume obeys 1 < T S
2²
We fit the neural generator G(C) to the noisy signal y E R by minimiz- nE=
ing the loss
L(C)= - - -yl
(11)
via running grudient descent starting from Co with i.i.d. N w²) entries, w ly c 2 size obeying 1) S 1/32. Then, with probability at least kk? x² - for all iterations T S T,
vnz Tr, and step
x G(C,)ll2 (1 "00)"" |x|12 +
Σ (11 no? 1)2 (w;, 2)² E1lyy12 (12)
17

---

Published as a conference paper at ICLR 2020
D.1 PROOF OF THEOREM! 2
Theorem 2 stated in the main text follow directly from Theorem 3 above as follows. We first note that for a convolutional generator (where U implements a convolution and thus is circulant) the eigenvectors of the matrix (U) are given by the trigonometrie basis functions per Definition | and the eigenvalues are the square of the entries of the dual kernel (Definition
2 To see this, we note
that as detailed in Section H
1 (1 (1-cos-) cos- ((1 (u; U1) {U))
/ (u Uz). |||u /|//////////
(13)
Because the matrix U implements a convolution with a kernel u that is equal to its first column, the matrix E(U) is again circulant matrix and also Hermitian. Thus, its spectrum is given by the Fourier transform of the first column of the circulant matrix, and its left-singular vectors are given by the trigonometric basis functions defined in equation ( and depicted in Figure
Furthermore, using the fact that the eigenvalues of a circulant matrix are given by its discrete Fourier transform we can substitute 3 ||U]| = |Ful| and = on > With the assumption T S 100 and using that noz
+ a T - 1 32 433
8
33,
Op
where we used the assumption
{ S 8 the condition (T0) is implied by the assumption k:
Cun/E.
gis with C, x q (see equation
where this assumption is made). This yields Theorem
D.2 PROOF OF THEOREM
Finally, we note that obtain the simplified final expression in Theorem T from Theorem 2 we also used the fact that for Gaussian vector z, the vector W z is also Gaussian. Furthermore, by the concentration of Lipschitz functions of Gaussians with high probability we have
Σ (11 no? 2)² (w 2) 1=1
((1 -o,?) 1)² (W (W
i=1
12
((1 - (111107) 1)²
71
(
2p
2
n
Here, equation (i) follows from (w,, z) being zero mean Gaussian with variance <²/n (since z (0, (s² /n) and Willz = 1). Finally, (ii) follows by choosing the early stopping time so that it obeys < log(1 /p/n)/ log(1 n1p+1) which in turn implies that (1 not)"* 2 1 vpln, for all > p. yielding that ((1 n)?)²= 1)² < p/n, for all i > p.
E THE DYNAMICS OF LINEAR AND NONLINEAR LEAST-SQUARES
Theorem 3 builds on general result on the dynamics of non-linear least squares problem which applies beyond convolutional networks, and that is stated and discussed in this section. Con- sider nonlinear least-squares fitting problem of the form
1 (())) ア ll.(()) -
-11
Here, f: R -> R a non-linear model with parameters O E N To solve this problem, we run gradient descent with fixed stepsize 77, starting from initial point Oo. with updates of the form
0 0, L(O,) where VL(0) = (0) -y)-
(14)
Here, T(0) E R is the Jacobian associated with the nonlinear map f with entries given by [T [())), 80,
(f) In order to study the properties of the gradient descent iterates 14 relate
18

---

Published as a conference paper at ICLR 2020
the non-linear least squares problem to linearized one in ball around the initialization og. We note that this general strategy has been utilized in a variety of recent publications (Du et al. 2018 Arora et al.; 2019; Oymak & Soltanolkotabi, 2019b Oymak et al. 2019). The associated linearized least-squares problem defined as
1 Lin (0) 2 (0)) + J(O 0o) y122
(15)
Here, J E Raxp, refered to the reference Jacobian, is a fixed matrix independent of 0 that approximates the Jacobian mapping at initialization, J (0%). Starting from the same initial point Po. the gradient descent updates of the linearized problem are
0 ++ 0, -nJ" (J(ON) J(O -00) -y)
= 0, -nJ"J (o. - 00) nJ" (f(00)-y))
(16)
To show that the non-linear updates (1) are close to the linearized iterates (6). we make the fol- lowing assumptions: Assumption (Bounded spectrum). We assume the singular values of the reference Jacobian obey
a S on Sa1 S 3.
(17)
Furthermore, we assume that the Jacobian mapping associated with the nonlinear model f obeys
S [I)(
for all E R
(18)
Assumption (Closeness of the reference and initialization Jacobians). We assume the reference Jacobian and the Jacobian of the nonlinearity at initializution I(0)) are en-close in the sense that
[T((0)) JJ| cu.
(19)
Assumption 3 (Bounded variation of Jacobian around initialization). We assume that within radius R around the initialization, the Jacobian varies by no more than e in the sense that
IJ(0) - J(0o)ll S 2 for all 0 E BR(0o),
(20)
where (o( (0: 10
0o1 RR is the ball with radius R around Oo-
Our first result shows that under these assumptions the nonlinear iterative updates (1) are intimately related to the linear iterative updates (T6). Specifically, we show that the residuals associated with these two problems defined below
nonlinear residual: := = f(0,) - ;- : (I (I-1JJ"²) ro.
(21)
linear residual:
(22)
are close in the proximity of the initialization.
Theorem (Closeness of linear and nonlinear least-squares problems). Assume the Jacobian map- ping J(0) E Ra associated with the function f(0) obeys Assumptions and ini- tial point Og E N with respect to a reference Jacobian E RR*NN and with parameters a, 3, cus e, and R. Furthermore, assume the radius R is given by
R. = 1|J'rool2
- + σ (eo (1+2)/33)) ||oo|2:
(23)
2
with T a constant obeying 1 IT S ZNE2, and J the pseudo-inved inverse J. We run gradient descent with stepsize 1) S to on the linear and non-linear least squares problem, starting from the same initialization 0.. Then, for all < T the iterates of the original and the linearized problems and their corresponding residuals obey
rr, Frl12 2 a
(Eo + e)llroll2
(24)
1
0.-
(en + e) (1+ 27) ||ooll
(25)
Moreover, for all iterates 7 T,
||0 0ull2 < R
(26)
2
19

---

Published as a conference paper at ICLR 2020
The above theorem formalizes that in a (small) radius around the initialization, the non-linear prob- lem behaves similarly as its linearization. Thus, to characterize the dynamics the nonlinear prob- lem, it suffices to characterize the dynamics of the linearized problem. This is the subject of our next theorem.
Theorem 5. Consider linear least squares problem 15 and let J = WEVT E R Ei=1 o, be the singular value decomposition of the matrix J. Then the residual r, after iterations of gradient descent with updates 16 is
(1 -o?)² ws (w,, ro)
(27)
Moreover, using step size satisfying 7) S of the linearized iterates (16) obey
|0.
0 1| =
(w,,
1 (1 no,))
(28)
d;
i=1
In the next section we combine these two general theorems to provide guarantees for denoising using general neural networks.
E. PROOF OF THEOREM 4 (CLOSENESS OF LINEAR AND NON-LINEAR LEAST-SQUARES)
The proof is by induction. We suppose the statement, in particular the bounds 24 25 and 26 hold for iterations S In Step I, we show that a weaker version of (26) holds, specifically that |0, 0p l1112 < R. Using this result, in Steps and we show that the bounds (24) and (25) hold, respectively. Finally, in Step IV we utilize Steps 1-III to complete the proof of equation (26).
We then show that they continue to hold for iteration four steps.
Step I: Next iterate obeys 0 (On). To prove 0, E Bn((o), first note that by the triangle inequality and the induction assumption (26) we have
100 - 00012 5|00, 0,-1l12 00,-1
00ll2:
R
0| 0, 0,- +
2
So to prove |10, 0oll2 R it suffices show that |0,, 0+-1ll2 R/2. To this aim note that
1
0, - 01-1 (C(
77
| (0 (0
(0.- 11, [I |r-1 -
J 111 + [[ J|l |F + 11 (0, 11,-111,---_ Fr-1ll2
-
J ||| + ( l,) 1|2 + 3|| Fy-1ll2
1 |Jrrol| + (( (e+ + +0)
- कي
82
(Eo + e)l(roll2
7)
R
2
20

---

Published as a conference paper at ICLR 2020
In the above (i) follows from Assumptions and 3 For (ii). we bounded the last term with the
induction hypothesis 24 the middle term with
[ 1T-1112 S [Toll2- and the first term with the bound
ll2
J (I 'yJJ"' y
E[ - - w roll2
ro)
S 2
rw) ro)
3 [ J'rollz
Finally, the last inequality follows by definition of R in (23 together with the fact that T 2 1.
Step II: Original and linearized residuals are close: In this step, we bound the deviation of the residuals of the original and linearized problem defined
e, r,
This step relies on the following lemma, which is variant of (Oymak al. 2019 Lem. 6.7).
Lemma (Bound on growth of perturbations). Suppose that Assumptions) 7 and 3 hold and that
0,.00 0r+1 E (6o). Then, provided the stepsize obeys S 1/8², the deviation of the residuals obeys
|cr+1ll2 S n/3(c (co + ||- + (1+ m(²) ||0|||2-
(29)
By the previous step, 0,, 0r+1 E (8)))). We next bound the two terms on the right hand side of (29 Regarding the first term, we note that an immediate consequence of Theorem 5 is the
following bound on the residual of the linearized iterates:
| S (1 - "aa""" ||roll2-
(30)
In order to bound the second term in 29 namely, ||e/|l2. we used the following lemma, proven later in Section E.I.I
Lemma 2. Suppose for positive scalars T,,, 0, 1/a2, the sequences F, and e, obey
8r i (1 - na?)² S (1 nT?)
(31)
C--1 + n
(32)
Then, for all T <
2nez we have that
1
Gr S 25 P
(33)
a
With these lemmas in place we now have all the tools to prove that the original and linear residuals
close. In particular, from Step I, we know that 0,, (g(0,) so that the assumptions of Lemmal
are satisfied. Lemma implies that the assumption 32) of Lemma 2 satisfied with g = 3( + c)
and the bound (30) implies that the assumption 31 of Lemma 2 is satisfied with p |rlllz- Thus,
Lemma implies that for all S 27pe
3 | 5
o + e)lloll
(34)
This concludes the proof of 24
21

---

Published as a conference paper at ICLR 2020
Step III: Original and linearized parameters are close:
First note that by the triangle inequality
and Assumptions 2 and
3 we have
[ JIl - [[((+)) - J(Oo)) + (l)(0.) J|| S +
(35)
The difference between the parameter of the original iterate 0 and the linearized iterate 0 obey
1 0, 0.112
VL(0,) - VLinn (0,)
T (0,)rr J
(| -J=) -F.)- 110 - -FF)ll
(co + FTelle + +11lee112
(EO + Σ
(1 - n1a")) m1(²))²
||rol12 + +
|eell2
1=0
t=0
1 - (1 - n
(co +
||ro|12 +
||e112
11a2
t=
(i0) (Eo +
|1oll2 + 2T 82
a (EO +e)l1oo122
na²
(co c) (1 + B²) ||roll2- na.
Here, inequality (i) follows from (35) and an application of Assumption inequality (ii) from (30)
inequality (iii) from 77 $ 1/8² which implies (1 na?? 2 0 and 34). This concludes the proof of the bound 25
Step IV: Completing the proof of 266
By the triangle inequality
|0 00ll <
0, 0
+ ++|00 0.111
@ JJrrllla + a² (co + c) (1 + 21 32) ||rollz
R/2,
where inequality (i) follows from the bound 25 which we just proved, and the fact that, from equation (36) in Theorem 3
(1 (1 -1
0 0
Σ (w; ro)*
of
(w;, ro) /0/
| ro
Finally, inequality (ii) follows from the definition of R in equation (33 along with 7 < T, by assumption.
22

---

Published as a conference paper at ICLR 2020
E.1.1 PROOF OF LEMMA 2
We prove the result by induction. Assume equation (33 holds for some We prove that then it also holds true for r + 1. By the two assumptions in the lemma,
c--1 4, S ne , + nET
S n6 er + n)((1 - >1
2 2p + -nna)pp
$ n
where (i) follows from the induction assumption
33
Summing up the difference of the errors gives
e
c++1
e
5
1=0
2p
$ TNE
+ n
- na
a²
t=
2p
1
(1- na?)
TTE
77
a²
ma²
I oz (122T +1)
P
S 2
a²
where the last inequality follows from the assumption that r S 2nje?"
1
E.2 PROOF OF THEOREM
The proof of identity 27 is equivalent the proof of Proposition ① note that
Regarding inequality 28
(WI,
T-1 Σ J
0, 0
V (i)(())) =
n/V
Σ CE(InNEe (I-
t=
1=0
1=0
(Ww,
Thus
(1 no?
vi, 0, - - = n ro)
Σ (1 no?)²²
n (w,,
(36)
no?
1=0
This in turn implies that
12
n
(wa,ro) 1- (1 no? )r
0
vi, 0, 00)
Ti
F PROOFS FOR NEURAL NETWORK GENERATORS (PROOF OF THEOREM 3
The proof of Theorem relies on the fact that, in the overparameterized regime, the non-linear least squares problem is well approximated by an associated linearized least squares problem. Studying the associated linear problem enables us to prove the result.
We apply Theorem 4 which ensures that the associated linear problem is a good approximation of the non-linear least squarest problem, with the nonlinearity G(C) = ReLÚ(UC)y and with the parameter given by 0 = C. Recall that is fixed vector with half of the entries 1/v I/Vk, and the other half -kv
As the reference Jacobian in the associated linear problem, we choose matrix Raxnk that is very close the original Jacobian at initialization, [CCo), and that obeys JJT
23

---

Published as a conference paper at ICLR 2020
E [[ The concrete choice of J is discussed in the next paragraph. We apply The- orem with the following choices of parameters:
log(
S gg0 c B2:
1 a² vnB 82
= on (E(U)) B B
co =
c
few comments on the intuition behind those choices: As shown below, a and 3 are chosen so that Assumption I satisfied. Regarding the choices of e, eo. and w, recall that the difference between the linear and non-linear residual is bounded by 2 2 (co c)]|roll2 (by Theorem 4). We want this error to be bounded by Elly|l2- This bound is guaranteed by our choice of e, by choosing eo such that it obeys 6o e, and by choosing w so that the initial residual bounded by ||roll2 S 2|1y|12- Note that I é holds by assumption (TO).
We next verify by applying series of Lemmas proven in Appendix ! that the conditions Theo- rem Jare satisfied (specifically, Assumptions 2 3 the Jacobians of the non non-linear map and the associated linearized map, be bounded and sufhciently close each other).
Choice of reference Jacobian and verification of assumption 2 We chose the reference Jaco- bian J that it is close to the random initialization J(Co) (with high probability), and thus satisfies assumption 2 Towards this goal, we require the following two lemmas.
Lemma 3 (Concentration lemma). Consider G(C) = ReLU(UC)) with v E R and U E g and associated Jacobian J(C) Let Rank be generated random with i.i.d. (0,,²) entries. Then,
&
2n
(C) S |U]
log
2=1
holds with probability at least 1-
To see that Lemmal iimplis the condition
we use the following lemma.
Lemma Oymak al. 2019 Lem. 6.4)). Let E ROXN N 2 n and let be x n psd matrix
obeying XXX Σ S 4 for scalar 0. Then there exists matrix E IRaXN obeying
Σ JJJ such that
S Co-
In order to verify the condition 19 note that using the fact that Σt of 1 by Lemma 3 with probability at least 1 - 5, we have
log (2n
((C E(U)] < ||
(eo/2)2
(37)
Combining inequality (37) with Lemma (applied with X (Co)), follows that condition (99 holds for the chosen value of 6n. concluding the proof of Assumption 2 being satisfied. This proof specifies the reference Jacobian as the matrix that is e--close to J(o)), and that exists
by Lemma
Verifying Assumption 1: To verify Assumption note that by definition JJJ E(U) thus trivially an (E(U)) > a holds. Furthermore, Lemma below combined with the fact that ||v||2 implies that |J]| < 3 and [C]]] < 3 for C. This completes the verification Assumption It remains show that the Jacobian has bounded spectrum:
Lemma 5 (Spectral norm of Jacobian). Consider G(C) = ReLU(UC)v with v E R and
U E Bank and associated Jacobian J(C) ( and lei J be any matrix obeying JJ" E [[(())T((C) where the expectation is over a matrix with iid (O,, entries. Then
[T(C]] < [|] and ||]] [|v|22 ||||]
24

---

Published as a conference paper at ICLR 2020
Bound on initial residual: For what follows, we require bound the initial residual. To prove this bound, we apply the following lemma.
Lemma 6 (Initial residual), Consider G(C) ReLU(UC),, and let C E Bunk be generated at random with ii.d. (0,,²)) entries. Suppose half of the entries of v are v/ VTT and the other half are -v/v kr, for some constant v > O. Then, with probability at least 1 - 5,
|[ &
|
Now, the initial residual can be upper bounded
3 ||roll2 < ||y||2 + +|G(Co))ll S 221xا122
(38)
where we used that, by Lemma
a² ||G(Co)]la S w 8 log 8) |U| S 11yll25
8 (oo((n/0))) - |yll|
(39)
Ba
Here, the second inequality follows from | 2 Vnl U| and our choice of the parameter w, and the last inequality follows from f S 1/ 1/ 32 log((n) /8) and a/3 S
Verification of the assumption requires us to control the perturbation of the Jacobian matrix around a random initialization.
Verifying Assumption 3:
Lemma 7 (Jacobian perturbation around initialization). Let Co be matrix with iid. N(),²²) entries. Then, for all C obeying
|C- CC-Co Coll S wi with R S 2 Vk.
the Jacobian mapping
D Dassociated with the generator G(C) = RcLU(UCCy obeys
J(C)) S l1 2/k |U]]
with prohability at least ne -
In order to verify Assumption 3 first note that the radius in the theorem, defined in equation 23 obeys
2 +
R =
J J'rolo
(co + c) (1 21/T3² ||rlll2
a
2 +
(co + c) (1 + 32) |roll2
a
a
2 (
1 |
2
(1 + 21/133))
2 2wv/mg
1 82
= 4 =1(1+ 2c (1 (1+211889) ) w 13 a3
a
a²
(m)
aa
f3
4w
2+ 23
TB²
a3
{ a2
Vk
w
16 B2
R.
Here, (i) follows from the fact that |
< _ ||olll2 (ii) from the bound on the initial resid-
2 ual 38 using that 6o c, well as choice of Moreover (iii) follows from the definition of and (iv) from the lower bound on k in assumption (10).
Note that since that
& a² I for this choice of radius R, by Lemma 7 we have, with || 1/VK, gz
{ Ea² 1 2 S a² (k 1/231/33
- < M 2/3
|U|
vk 16 16,32
8 c.
25

---

Published as a conference paper at ICLR 2020
holds with probability at least
- RR = NE
-2 22-17 ka
(
ne
6,
where in (i) we used (10) together with ç S v log 2n probability by our choice of a 3
Therefore, Assumption 3 holds with high
Verifying the bound number of iterations: Finally we note that the constraint the number
of iterations, T. T.T S 21ez. from Theorem 4 is satisfied under the number of constraints of Theorem
3²
by 2nje
TT
Concluding the proof of Theorem 3 Now that we have verified the conditions of Theorem 4 we can apply the theorem. This allows us to conclude that
[|G(C+)
x112 |G((C,) 2 yll2
||r, + z/12
|[, + 2 z - -T--i Frll2
[r, + z||2 + ||r, - Frll2
W [r 2|12 + El1y|12
(
W (I - -1)))) WT ro + =/// 1 2
(v)
W (I "/'3)* (GTCG())) -x) -(w (1-) 7 WT WW -1)= + +1[1rrobb
1
m1=)) w
x ||| + +1((11 -1(111)))) - 1) w" =/1 + +|[G(Co)]1 + 111y
x (1-
1
+
Σ ((1-n07 ((1-no 1)2 (w, z) El
Here, (i) follows from the triangular inequality, (ii) from Theorem 4equation (2 combined with our choice for and ||roll < | shown above. Moreover, (iii) follows from Theorem 5 (iv) from ro G(Ca) -y y = G(Co)
z. (v) from the triangular inequality. Finally, for (vi) we used
the fact that x E span ( ww, W2....; wp) combined with the fact that
| (I-r)E)) -/E²)*
WT] 1,
as well using the bound |[G(C)) lyllz proven in (39 This proves the final bound desired.
12 as
G PROOF OF PROPOSITION 1 AND EQUATION 2
The residual of gradient descent at iteration 7 is
r = y Jc.,
J(c - "1J"""Jcr y))
(Jcr-1
(I TJJJJ (y - -Jc-11)
(I "JJ"" JCoo)
= (I - "J
= (I - "W
where we used that oa = 0 and the SVD J = WEVT. Expanding y in terms of the singular vectors W, (i.e., the columns of W), as y = Σ, w, (w,,y), and noting that (I-)WS>W>
E,(1 -1o7)= "w, we get
rr Σ (1 - Tw: (W.,)),
as desired.
26

---

Published as a conference paper at ICLR 2020
Proof of equation 2 By proposition and using that and lies in the signal subspace
X -- Jc,
w. no²) (wi,))
w.((1 - n (W z)
By the triangle inequality,
||x 1x--cch Jcrl12 =
Σ w,(1 n0??)² x)
+
Σ
w. w,((1 -o??)² - (w; z)
==1
(1 - na no! | +
Σ
(11 nou 1)2 (w;, (w;,
where the second inequality follows by using orthogonality of the w, and by using (1 - no?) s 1, from v) I 1/0 This concludes the proof of equation
H THE EXPECTED JACOBIAN FOR CONVOLUTIONAL GENERATORS
We first prove the closed form expression of the expected Jacobian, more precisely of the matrix (UU) defined in (3.. By the expression for the Jacobian equation 9 we have that
J(O)JT(C) = Σ di (Uc:)))UU (lag(o'(UU)))
Σ o (Uo((UU))o'(Ucc)) @ UU
= = =d((C)ddiagg ( (UC) @ UU",
where @ denotes the entrywise product of the two matrices. Then,
[J(C) Σ o d'(Uus))'((Ue)) o UU".
(40)
Next, we have with (Daniely al. 2016 Sec. 4.2) and using that the derivative of the ReLU function is the step function,
E ('((es)o
"]]
2 (1 cos-o (
(u, uz}
/m)
||u u 11
Using that ||v112 1, we get
- 1 (1 (1-c0o cos-os- (u, U,}
E [I(O)
/T
(u;; Uz),
[u 2| (
where u, are the rows of U. This concludes the proof of equation 13
We next briefly comment on the singular value decomposition of a circulant matrix and explain that the singular vectors are given by Definition| | Recall, that U E Raxa is a circulant matrix, implementing the convolution with filter. Assume for simplicity that n is even. It is well known that the discrete Fourier transform diagonalizes U.
U
where F Caxn is the DFT matrix with entries
Fl = 225kk/n
j.k 0, O...,...,n.11 n
and Ü is a diagonal matrix with diagonal Fu, where u is the first column of the circulant matrix U. From this, we can compute the singular value decomposition of U by using that Fu conjugate symmetric (since is real) that
[un- = ú',
2=2...,
U U WEVT be the singular value decomposition of U. The entries of the left singular vectors are given by the trigonometric basis functions defined in (5) and the singular values are given by the absolute values of ú.
27

---

Published as a conference paper at ICLR 2020
1 PROOFS OF LEMMAS FOR NEURAL NETWORK DENOISERS (PROOFS OF AUXILIARY LEMMAS IN SECTION
1.1 PROOF OF LEMMA 7 JACOBIAN PERTURBATION AROUND INITIALIZATION
The proof follows that of (Oymak & Soltanolkotabi 2019b Lem. 6.9).
Step 1:
We start by relating the perturbation of the Jacobian perturbation of the activation patterns. For any C, C', we have that
[I(CC) - J(C'll S | max [I'((u)))) ('u,)"'
(41)
To see this, first note that, by ②
J(C) J(C') = [... u, (diag(o -
This in turn implies that
[|](C)) J(C') = - - ((10))-70)))0100)1111)))
= [o|(Uc) - d' (toe))/ieee.....oo/ooo/)o-o/o))) o
|1|| max [[o' (u] o' d'(u, d'))gig((v))
< ||v & UI max (u) C) o'
where for (i) used that for positive semidefinite matrices A, B, Amax (A Amax ()) max; B., This concludes the proof of equation 41
O
B S
Step 2: Step one implies that we only need control d'U,c)) around neighborhood of c/.
Since of the step function, we need to count the number of sign flips between the matrices UC and UC'. Let [v|z()) be the q-th smallest entry of v in absolute value.
Lemma 8. Suppose that, for all i, and q I k.
C"''' C' (r(a)
- S /q
|u.||
Then
max
(u C')l S 22g
Proof. Suppose that o' (u. C) and d'( have 2q many different entries, then the conclusion of the statement would be violated. We show that this implies the assumption is violated well, proving the statement by contraction. By the contradiction hypothesis,
|C c Z |
C'Il / /,,11
u
C
|
where the last inequality follows by noting that at least 2q many entries have different signs, thus their difference is larger than their individual magnitudes, and at least q many individual magnitudes are lower bounded by the q-th smallest one.
Step 3: Next, we note that, with probability least 1 ne- kgp the 9-th smallest entry of u C' E & obeys
u C'
m(g)
for all i 1,...,
(42)
u;
2k
28

---

Published as a conference paper at ICLR 2020
We note that it is sufficient to prove this result for 1. This follows from anti-concentratton of Gaussian random variables. Specifically, with the entries C' being iid (0 1) distributed, //'C//|l,,]] Ie are iid standard Gaussian random variables as well. We
the entries of g show that with probability at least - e ku4//2 at most entries are larger than 2k Let "s be the number for which P [1ge|| %) S 6, where g is standard Gaussian random variable. Note that 76 2 / 2 6. Define the random variable
5z = {0
if Igel S 76: otherwise.
with 5 = 2/c With E [ōo]
8, by Hoeffding 's inequality,
k
k
P
6 2 m
= P
8t Ebel 2 m/2
Se e 2222m(/22) e /2,
(43)
Thus, with probability at least - 12 no more than m entries are smaller than 78 2 The results now follows by taking the union bound over all i == 1,...,
kg2
9
2
We are now ready to conclude the proof of the lemma. By equation
- -
v/
|
max
o C) - -
v
U
2g
provided that
CC C/I s v 2k
with probability at least - ne ne- k2' Setting = (2 concludes the proof (note that the
assumption R S 1 v ensures 1 < k).
1.2 PROOF OF LEMMA BOUNDED JACOBIAN
By the expression of the Jacobian in equation
| [(C)((C)
o' (UU))diag()) (UC)) o UUT
||]| max loo d)diag(vv)) ||
where for (i) used that for two positive semidefinite matrices A,B, B, Amax (A C B) < Amax ()) max; B To prove the second inequality note that
JJ T E(UI
= -||v
BoNroo (LL o (UU*)
|U
Here, (i) follows from the fact that for two positive semidefinite matrices A, B, Amax (A 2 B) S
Amax A) max, B
I.3 PROOF OF LEMMA CONCENTRATION LEMMA
We begin by defining the zero-mean random matrices
S = ("((c)))((ūc))" -E [((((a))'((o))))) (ūOT).
29

---

Published as a conference paper at ICLR 2020
With this notation,
((C) -
Σ og (d(((r))o((( -B((((c))(( の (ÜÜ*)
--
Se.
To show concentration we use the matrix Hoeffding inequality, To this aim note that the summands centered in the sense that E |St] = 0. Next note that
(d'(Uc:)'(Uus)"
['((Ur))(((Ga)))) (Foo o (ÜÙ") 3 (dd(Uc))o'(( @ (ÜÚ")
-diag (d((Üc))7) UÜ diag (o((Ucz)
-B"
Similarly,
(d'(Uea)o'(ee))) (U,,)) E -B(((cc))O((c))))) R (ūū*) - E d(((oa))'((os))) @ (ÜO")
> B'BU..
Thus,
oフ B' 3 oF
Therefore, using A, == oz BU
we have
S =
and
A:
0²
A
B
To continue we will apply matrix Hoeffding inequality stated below.
Theorem (Matrix Hoeffding inequality, Theorem 1.3 (Tropp) 2011).. Consider finite sequence S; of independent, random, self-adjoini matrices with dimension n, and let {At] } be sequence of fixed self-adjoint matrices. Assume that each random matrix satisfies
E[Sa] =0 and S A3 almost surely.
Then, for all 1 120 0,
P
Σ S 2
2 <
2ne
noz
where o²
Σ
A
Therefore, applying matrix Hoeffding inequality get that
P
Se
2t
2t
< 2ne "+
which concludes the proof.
I.4 PROOF OF LEMMA (BOUND ON INITIAL RESIDUAL)
Without loss of generality prove the result for 1. First note that by the triangle inequality
Ir la [UC(v yll, [|o(UC) llyll--
30

---

Published as a conference paper at ICLR 2020
We next bound ||=(UC) Consider the i-th entry of the vector ( RR, given by ou CJv, and note that qj (o c,) o (uf cn-s))/|luill is sub-Gaussian with parameter
i... Playj S follows that
k/2 Σ
2 BVK
2e
S 2e 4
4
Thus,
P (o(uuC))] z
||:11223 S 2e 5
where we used that
= - Taking union bound over all entries,
P [|o 2 3"
S 2ne
Choosing 3 (8log(2n/0) concludes the proof.
31


Reviews:
[{"review_id": "SJxWlnNpFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 studies the theoretical reasons why a randomly initialized decoder or autoencoder like architecture can prove useful for image denoising, by using early stopping. The paper is clearly written and the proofs are interesting. It will be of interest to the community.\n\nSome questions that are not addressed, and I'd be keen to understand are:\n\n1. What is the effect of a bias in a layer?\n\n2. What family of noise types (in this work only additive Gaussian noise was considered) that will benefit from early stopping? What about multiplicative noise (\"shot noise\"), for example (which often arises in computational photography)?\n\n3. Unless I missed it, it was not clear to me that the analysis shed light on why a trained network performs much worse than a random network?\n\nNotes:\n\n1. Figure 1 could be improved by adding x-axis to both rows, and showing the exact difference in number of iterations between fixed learned filters. It seems that the difference happens in two ways: the natural images converge faster for fixed filters, *and* the noisy images converge slower; so that the gap between noisy and natural images is larger for fixed filters.\n\n2. A number of typos, a missing equation reference etc. Please proofread.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HklY2HdfqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 studies the situation in which a two-layer CNN with RELU nonlinearity is fit to a single image and the observation that it is able to fit a \"natural\" image in fewer iterations than a \"noisy\" image. Theorems on the convergence of this fitting are discussed and proven in the appendices. Intermediate results study the convergence of fitting a linear model to an image plus noise and fitting a single-layer CNN. Denoising is demonstrated on two images with additive white Gaussian noise and the approach under study is shown to provide a better signal-to-noise ratio than BM3D, another untrained denoising approach. The main result is that the use of upsampling via a fixed interpolation filter provides an inductive bias towards \"natural\" images.\n\nThe bibliography does a good job of positioning this paper within the recent set of articles exploring the curious behavior of fitting a CNN to a single image. The problem is interesting, timely, and surprising. The analysis does provide some insight into what is going on.\n\nBut, the paper would do well to embrace the Fourier domain and first discuss what is meant by \"natural images\" and \"noise\" in terms of their frequency content. In particular, something like Simoncelli and Olshausen (2001) could be used as a description of the spectra of natural images. Additive white Gaussian noise has a flat spectrum, which is never mentioned in the paper. Thus, the theoretical result mainly highlights the fact that natural images have a low-pass spectrum, while white noise has a flat spectrum, and CNNs using interpolation also have a low-pass spectrum in some sense. This makes sense from a frequency perspective, because interpolation increases the sampling rate of a signal without changing its frequency content, i.e., it adds high frequencies with no energy. \n\nThe \"trigonometric basis\" used in the paper, which consists of sines and cosines at each frequency, could be more cleanly described as a basis of complex exponentials, i.e., the Fourier basis, which doesn't require partitioning the basis into a cosine half and a sine half. The discussion of triangular and Gaussian smoothing functions has been very well explored in the signal processing literature discussing windowing functions and their Fourier transforms, e.g., Harris (1978). I don't think Figure 3 showing some sinusoids is necessary.\n\nThe main body of the paper goes into the 10th page, but the appendices make up another 18 pages. The main body of the paper does not include any of the proofs of the provided theorems. This seems rather excessive.\n\n\nHarris, F. J. (1978). On the use of windows for harmonic analysis with the discrete Fourier transform. Proceedings of the IEEE, 66(1), 51-83.\n\nSimoncelli, E. P., & Olshausen, B. A. (2001). Natural image statistics and neural representation. Annual review of neuroscience, 24(1), 1193-1216.\n\n\nMinor comments:\n\nSeveral citations are in the wrong form (\\citet instead of \\citep) throughout the paper.\n\nThere is a link to a figure in the appendix that is broken on page 5\n\nIn figure 7, one one set of y-axis labels is shown, but it appears that each subplot uses an independent y-axis, just without labels. Please plot them all on the same y-axis.\n\nSimilarly, figures 1, 4, and 6 show similar things on different y-axes when they could be plotted at the same scale on the y-axis to make them more easily comparable visually. \n\nTypos: \"over-paramtrized\" and \"spacial\" both on page 1.\n\n\nAfter discussion:\n\nThe authors have addressed my concerns, so I am changing my decision from Weak Reject to Weak Accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xrIN8NYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 paper provides a theoretical study of regularization capabilities of over-parameterized convolutional generators trained via gradient descent, in the context of denoising with an approach similar to the \"deep image prior\".\nThe authors show that when using appropriate upsampling operators, gradient descent biases the reconstructed images towards low-frequency components, while the noise components, which typically consist of high-frequency patterns, take longer to fit, so that early stopping can provide a useful bias for denoising.\nThe proofs are based on recent results for \"lazy\" training of over-parameterized networks, namely neural tangent kernels.\n\nI find the paper interesting and novel, as it is the first to my knowledge to study the implicit bias of optimization for such generator-based denoising approaches, and provides interesting theoretical and empirical denoising results.\nWhile the current results are for a simple architecture with one hidden layer, they may pave the way for a formal study of more complex architectures.\nNevertheless, the paper presents some limitations which should be addressed further in the paper:\n\n* in terms of denoising capabilities, it seems that the results for the non-linear, over-parameterized network are essentially similar to the linear case (with an appropriately designed operator J in Section 3). Are there any benefits to the non-linear case that I am missing? Whether or not this is a limitation of the study, it should be discussed further in the paper.\n\n* Some comments on the empirical results reported in Figure 2: (i) how are hyper-parameters chosen? this seems to be crucial for the effective use of such denoising strategies, and it is unclear how robust these methods are, e.g., to the early stopping time; (ii) there are other methods that only learn on the given image (thus without the need for a training set) which outperform BM3D [e.g. 1,2], it is unclear how the proposed methods compare to those.\n\nother minor comments:\n- Figure 2 \"maintained on a large test set of images\" more details are welcome, including on hyperparameter selection\n- Section 1.1:\n\t* \"demystifying\" -> understanding?\n\t* different notations are used for the (same?) iterates, C^t and C_tau\n- Section 2.3\n\t* \"it follow that optimizing...\": please clarify. I agree that the optimum is the same, but is the implicit bias from initialization the same?\n- end of Section 3: early stoped -> stopped\n- Section 4\n\t* after Definition 2, \"this in turn implies that the jacobian spectrum ...rapidly\": clarify, is it a consequence of the analysis?\n\t* after Thm 1: maybe give some insight about the proof and the use of NTK? also, discuss similarities or differences with the linear case\n\n\n[1] Dabov et al. (2009) BM3D Image Denoising with Shape-Adaptive Principal Component Analysis\n[2] Mairal et al. (2009) Non-local Sparse Models for Image Restoration", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the question of why a network trained to reproduce a single image often de-noises the image early in training. This an interesting question and, post discussion, all three reviewers agree that it will be of general interest to the community and is worth publishing. Therefore I recommend it be accepted. 
Decision: Accept (Poster)