Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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.

The 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.

But, 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. 

The "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.

The 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.


Harris, F. J. (1978). On the use of windows for harmonic analysis with the discrete Fourier transform. Proceedings of the IEEE, 66(1), 51-83.

Simoncelli, E. P., & Olshausen, B. A. (2001). Natural image statistics and neural representation. Annual review of neuroscience, 24(1), 1193-1216.


Minor comments:

Several citations are in the wrong form (\citet instead of \citep) throughout the paper.

There is a link to a figure in the appendix that is broken on page 5

In 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.

Similarly, 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. 

Typos: "over-paramtrized" and "spacial" both on page 1.


After discussion:

The authors have addressed my concerns, so I am changing my decision from Weak Reject to Weak Accept.
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: 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.

Some questions that are not addressed, and I'd be keen to understand are:

1. What is the effect of a bias in a layer?

2. 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)?

3. 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?

Notes:

1. 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.

2. A number of typos, a missing equation reference etc. Please proofread.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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".
The 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.
The proofs are based on recent results for "lazy" training of over-parameterized networks, namely neural tangent kernels.

I 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.
While 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.
Nevertheless, the paper presents some limitations which should be addressed further in the paper:

* 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.

* 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.

other minor comments:
- Figure 2 "maintained on a large test set of images" more details are welcome, including on hyperparameter selection
- Section 1.1:
	* "demystifying" -> understanding?
	* different notations are used for the (same?) iterates, C^t and C_tau
- Section 2.3
	* "it follow that optimizing...": please clarify. I agree that the optimum is the same, but is the implicit bias from initialization the same?
- end of Section 3: early stoped -> stopped
- Section 4
	* after Definition 2, "this in turn implies that the jacobian spectrum ...rapidly": clarify, is it a consequence of the analysis?
	* after Thm 1: maybe give some insight about the proof and the use of NTK? also, discuss similarities or differences with the linear case


[1] Dabov et al. (2009) BM3D Image Denoising with Shape-Adaptive Principal Component Analysis
[2] Mairal et al. (2009) Non-local Sparse Models for Image Restoration
review_title: Official Blind Review #3

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)