How do Minimum-Norm Shallow Denoisers Look in Function Space?
Authors: Chen Zeno
Greg Ongie
Yaniv Blumenfeld
Nir Weinberger
Daniel Soudry
Venue: NeurIPS 2023 poster (2023)
Keywords: Denoiser
Denoising
Neural network
Function space

Abstract: Neural network (NN) denoisers are an essential building block in many common tasks, ranging from image reconstruction to image generation. However, the success of these models is not well understood from a theoretical perspective. In this paper, we aim to characterize the functions realized by shallow ReLU NN denoisers --- in the common theoretical setting of interpolation (i.e., zero training loss) with a minimal representation cost (i.e., minimal $\ell^2$ norm weights). First, for univariate data, we derive a closed form for the NN denoiser function, find it is contractive toward the clean data points, and prove it generalizes better than the empirical MMSE estimator at a low noise level. Next, for multivariate data, we find the NN denoiser functions in a closed form under various geometric assumptions on the training data: data contained in a low-dimensional subspace, data contained in a union of one-sided rays, or several types of simplexes. These functions decompose into a sum of simple rank-one piecewise linear interpolations aligned with edges and/or faces connecting training samples. 
We empirically verify this alignment phenomenon on synthetic data and real images.

How do Minimum-Norm Shallow Denoisers Look in Function Space?
Chen Zeno Electrical and Computer Engineering Technion
Greg Ongie Department Mathematical and Statistical Sciences Marquette University
Yaniv Blumenfeld, Nir Weinberger, Daniel Soudry Electrical and Computer Engineering Technion
{chenzeno, yaniibbl8ccmppus techemciimmuuuttthiiin.no technion ac.il, eeggor..ongeemarquetteeoo edu nirwein@technion. ac.il, daniel wwwdryoggaalll.ooommm com
Abstract
Neural network (NN) denoisers are an essential building block in many common tasks, ranging from image reconstruction to image generation. However, the success of these models is not well understood from theoretical perspective. In this paper, we aim to characterize the functions realized by shallow ReLU NN denoisers in the common theoretical setting of interpolation (i.e., zero training loss) with a minimal representation cost (i.e.. minimal 8² norm weights). First, for univariate data, we derive closed form for the NN denoiser function, find contractive toward the clean data points, and prove it generalizes better than the empirical MMSE estimator a low noise level. Next, for multivariate data, we find the NN denoiser functions in closed form under various geometric assumptions on the training data: data contained a low-dimensional subspace, data contained a union of one-sided rays, several types of simplexes. These functions decompose into sum of simple rank-one piecewise linear interpolations aligned with edges and/or faces connecting training samples. We empirically verify this alignment phenomenon on synthetic data and real images.
Introduction
The ability reconstruct image from noisy observation has been studied extensively in the last decades, as useful for many practical applications (e.g.. Hasinoff et al. 2010).. In recent years, Neural Network (NN) denoisers commonly replace classical expert-based approaches they achieve substantially better results than the classical approaches (e.g.. Zhang et al.) (2017).. Beyond this natural usage, NN denoisers also serve as essential building blocks in a variety common computer vision tasks, such as solving inverse problems [Zhang et al.) 2021 I and image generation (Song and Ermon 2019 Ho al. 2020). To better understand the role of NN denoisers such complex applications, we first wish to theoretically understand the type of solutions they converge to.
In practice, when training denoisers, sample multiple noisy samples for each clean image and minimize the Mean Squared Error (MSE) loss for recovering the clean image. Since we sample numerous noisy samples per clean sample, the number of training samples is typically larger than the number of parameters in the network. Interestingly, even such an under-parameterizer regime, the loss has multiple global minima corresponding to distinct denoiser functions which achieve
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

loss on the observed data. To characterize these functions, we study, similarly to previous works (Savarese al., 2019 Ongie et al.) 2020), the shallow NN solutions that interpolate the training data with minimal representation cost, i.e., where the norm of the weights (without biases and skip connections) as small as possible. This is because we converge to such min-cost solutions when we minimize the loss with a vanishingly small e² regularization on these weights.
We first examine the univariate input case: building on existing results [Hanin] 2021]. we characterize the min-cost interpolating solution and its generalization to unseen data. Next, we aim to extend this analysis to the multivariate case. However, this is challenging, since, to the best of our knowledge, there are no results that explicitly characterize these min-cost solutions for general multivariate shallow NNs- except in two basic cases. In the first case, the imput data is co- co-linear [Ergen and Pilanci 2021]. In the second case, the input samples are identical to their target outputs, so the trivial min-cost solution the identity function. The NN denoisers' training regime is 'near' the second case: there, the input samples are noisy versions of the clean target outputs. Interestingly. we find that this regime leads non-trivial min-cost solutions far from identity even with an infinitesimally small input noise. We analytically investigate these solutions here.
Our Contributions. We study the NN solutions in the setting of interpolation of noisy samples with min-cost, in a practically relevant "low noise regime" where the noisy samples are well clustered. In the univariate case,
We find closed-form solution for the minimum representation cost NN denoiser. Then, we prove this solution generalizes better than the empirical minimum MSE (eMMSE) denoiser.
We prove this min-cost NN solution is contractive toward the clean data points, that is, applying the denoiser necessarily reduces the distance of a noisy sample to one of the clean samples.
In the multivariate case,
We derive a closed-form solution for the min-cost NN denoiser in multivariate case under various assumptions on the geometric configuration of the clean training samples. To the best of our knowledge, this is the first set of results to explicitly characterize a min-cost interpolating NN in a non-basic multivariate setting.
We illustrate a general alignment phenomenon of min-cost NN denoisers in the multivariate setting: the optimal NN denoiser decomposes into sum of simple rank-one piecewise linear interpolations aligned with edges and/or faces connecting clean training samples.
2 Preliminaries and problem setting
The denoising problem. Let E IRd be noisy observation of x E Rd, such that y = x + where x and are statistically independent, and [E{]] O. Commonly, this noise is Gaussian with covariance matrix I²1. The ultimate goal of a denoiser & (y) is to minimize the MSE loss over the joint probability distribution of the data and the noisy observation ("population distribution"), i.e., to minimize
C ( Ex, . | (y) x
(1)
The well-known optimal solution for ① is the minimum mean square error (MMSE) denoiser, i.e.,
x" (y) = Eg [x y] E arg min ||x a (z))l
(2)
Since we do not have access to the distribution of the data, and hence not to the posterior distribution, we rely on a finite amount of clean data { (z,, /N in order to learn good approximation for the MMSE estimator. One approach to assume an empirical data distribution and derive the optimal solution of (T) i.e., the empirical minimum mean square error (eMMSE) denoiser,
N
i 4cMMSE
(y) E arg min 2(y)
Σ
E
|| (v) - xx 11
(3)
N
If the noise is Gaussian with a covariance of o III, an explicit solution to the eMMSE is given by
ΣN En exp
|| -|y= 20
S AMMME (3)
(4)
ΣN exp
y y-2.m1" 1
20
2

---

An alternative approach to computing the eMMSE directly is to draw M noisy samples for each clean data point, as Fn,m In + Cn,m. where 6n.m ~ N (0, 00, are independent and identically distributed, and to minimize the following loss function
Loftliue, M (2)
1 MN
Σ
Σ
+ (y)nm) ITnl
(5)
Denoiser model and algorithms. In practice, approximate the optimal denoiser & (y) using parametric model ho (y), typically NN. We focus on a shallow ReLU network model with skip connection of the form
ho = Σ as lung y + bx]+ + Vy + k=1
(6)
where 0 ((0+) V) with 02 (bk, ak, ux) IR Rd Rd and E Rd V R We train the model on a finite set of clean data points { The common practical training method is based on online approach. First, sample random batch (with replacement) from the data S {#n J Then, for each clean data point 2n E B, we draw noisy sample yn = In + En. where Cn N (0, 2T) are independent of the clean data points and other noise samples. At each iteration & out of I iterations, we update the model parameters according to stochastic gradient descent rule, with a vanishingly small regularization term AC A0), that is,
0++1 0 V
|ho, (yn) 2,, nAVo,
B
Another training method [Chen et al. 2014 is based on an offline approach. We sample M noisy sample for each clean data point and minimize
(5) plus regularization term
Lottlnee M (0)
1 MN
Σ
ho (Yn,m) I,,1 AC (0)
Similarly to previous works [Savarese al., 2019 Ongie al. 2020 we assume an penalty on the weights, but not on the biases and skip connections, i.c.,
C(0) 2 (Iax + 1|wx|1?)
Low noise regime. In this paper, we study the solution of the NN denoiser when the clusters of noisy samples around each clean point are well-separated, setting which we refer to as the "low noise regime". This is rather relevant regime since denoisers practically used when the noise level mild. Indeed, common image-denoising benchmarks test on low (but not negligible) noise levels. For instance, in the commonly used denoising benchmark BSD68 (Roth and Black] (2009), the noise level a 0.1 is in the low noise regime Moreover, this setting is important, for example, in diffusion-basee based image generation, since the end of the reverse denoising process, new images sampled by denoising smaller and smaller noise levels
3 Basic properties of neural network denoisers
Offline v.s. online NN solutions. NN denoisers are traditionally trained in an online fashion 7 using finite amount of T iterations. Consequently, only a finite number of noisy samples used for each clean data point. We empirically observe that the solutions in the offline and online settings are similar. Specifically, in the univariate case, show in Figure that denoisers based on offline and
'The minimum distance between two images BSD68 is about 97 while image resolution d 481 x 321. Also, the norm of the noise concentrates around the value of vdo /481 321 0.1 =z 97. Therefore, the clusters noisy samples around each clean point are generally sela-sep.rated.
'Interestingly, it was suggested that the "useful" part of the diffusion dynamics happens only below some critical noise level (Raya and Ambrogioni 2023
3

---

NN denoiser eMMSE denoiser. We trained a one-hiidenr ReLU network with skip connection on a denoising task. The clean dataset has four points equally spaced in the interval [-5, 5]. and the noisy samples are generated by adding zero-mean Gaussian noise with o 1.5. We use À = 10-3 in both setting. The Figure shows the denoiser output a function of its input for: (1) NN denoiser trained online using (7) for 100K iterations, (2) NN denoiser trained offline using (8) with M = 9000 and 20K epochs, and (3) the cMMSE denoiser (4.
Figure 1:
VN-Denoiser- online
Ww-Denlisr--fffn
deneiser
Online training data
Prediction
-5
-2 Nolsy
5
online loss functions converge to indistinguishable solutions. For the multivariate case, we observe (Figure i Appendix (D) that the offline and online solutions achieve approximately the same test MSE when trained on subset of the MNIST dataset. The comparison is made using the same number of iterations for both training methods, while using much less noisy samples in the offline setting. Evidently, this lower number of samples does not significantly affect the generalization error. Hence, in the rest the paper, we focus on offline training (i.e., minimizing the offline loss Lottine Mr). ), as it defines explicit loss function with solutions that can be theoretically analyzed, in (Savarese) ct al. 2019 Ongie et al. 2020].
The empirical MMSE denoiser. The law of large numbers implies that the denoiser minimizing the offline loss Cofttine approaches the eMMSE estimator in the limit of infinitely many noisy samples,
CMMSS 2
(y) E arg ming
lim Loffine. (Ø)
(10)
M M-+00
Therefore, it may seem that for reasonable number of noise samples M, a large enough model, and small enough regularization, the denoiser we get by minimizing the offline loss (6) will also be similar to the eMMSE estimator. However, Figure [ shows that the eMMSE solution and the NN solutions (both online and offline) are quite different. The eMMSE denoiser has a much sharper transition and maps almost all inputs to a value of clean data point. This is because in the case of low noise the eMMSE denoiser approximates the one nearest-neighbor (1-NN) classifier, i.e..
lim McMME (y) xc (m:))
= arg min 11l - x]|
(11)
In contrast, the NN denoiser maps each noisy sample to its corresponding clean sample only in a limited "noise ball" around the clean point, and interpolates near-linearly between the "noise balls". Hence, we may expect that the smoother NN denoiser typically generalizes better than the eMMSE denoiser. We prove that this is indeed true for the univariate case in Section 4
Why the NN denoiser does not converge to the eMMSE denoiser? Note that the limit 1Tpp is not practically relevant for the low-level noise regime, since we need an exponentially large M in order to converge in this limit. For example, in the case of univariate Gaussian noise, we have that ((c > t) S 2 exp(- 2n2 Vt > 0. Therefore, during training, we effectively observe only noisy samples that are in bounded interval of size 20 /log M around each clean sample (see Figure D In other words, in the low-noise regime and for non-exponential M, there is no way to distinguish if the noise is sampled from some distribution with limited support of from Gaussian distribution. The denoiser minimizing the loss with respect to a bounded-support distribution can radically different from the eMMSE denoiser in the regions outside the "noise balls" surrounding the clean samples, where the denoiser function is not constrained by the loss. This leads to a large difference between the NN denoiser and the MMSE estimator.
A Alternatively, one may suggest that the NN denoiser does not converge to the eMMSE denoiser due to an approximation error (i.e., the shallow NN's model capacity is too small to approximate the MMSE denoiser). Nevertheless, we provide empirical evidence indicating it is not the case. Specifically, recall that in the low noise regime, the eMMSE denoiser tends to the neirhbr classifier, and

---

such a solution does not generalize well to test data. Thus, if the NN denoiser would have converged the eMMSE solution, then its test error would have increased with the network size, in contrast to what we observe in Figure 12 (Appendix D)
Therefore, in order to approximate the eMMSE with NN, it seems must have exponentially large M. Alternatively, we may converge to the eMMSE if we use loss function marginalized over the Gaussian noise. This idea was previously suggested by Chen et al. [014]] with the goal of effectively increasing the number of noisy samples and thus improving the training performance of denoising autoencoders. Therein, this improvement was obtained by approximating the marginalized loss function by Taylor series expansion. However, for shallow denoisers, we may actually obtain an explicit expression for this marginalized loss, without any approximation. Specifically, if we assume for simplicity, that the network does not have a linear unit (V = 0) and its bias terms are zero (c 0, 02 = 0), then the marginalized loss for Gaussian noise, derived in Appendix is given by
[
K Σ k=1
K
C C0,,0) 0) = Eay |1 (y) x²1² Eu.y
ak
y/+
E Eg yl
Σ
a
K
Ex
ago (20) xc 11
a a Hiy (wi, Wj o²)
(12)
where wt z0x ||wx|| || and H = 0, o.) are defined in Appendix A NN denoisers trained over this loss function will thus tend to the eMMSE solution as the network size is increased. However, as we explained above, this is not necessarily desirable, we only mention (12) to show exact marginalization is feasible.
Regularization biases toward specific neural network denoisers. To further explore the con- verged solution for offline training, we note that the offline loss function Loftiie, (0) allows the network to converge to zero-loss solution. This is in contrast to online training for which each batch leads to new realizations of noisy samples, and thus the training error is never exactly zero. Specifically, consider the low noise regime wwell-separated noisy clusters). Then, the network can perfectly fit all the noisy samples using a finite number of neurons (see Section 4 for a more accurate description in the univariate case). Importantly, there are multiple ways to cluster the noisy data points with such neurons, and so there are multiple global training loss minima that the network can achieve with zero loss, each with different generalization capability. In contrast to the standard case considered in the literature, this holds even in the under- sadder-parameteizeed case (where N NM, the total number of noisy samples, is larger than the number of parameters).
Since there are many minima that perfectly the training data, we converge to specific minima which also minimize the L regularization we use (even though we assumed it is vanishing). Specifically, in the limit of vanishing regularization C (0), the minimizers of Loftin.M (0) also minimize the representation cost.
Definition 1, Let hg IRd + Rd denote a shallow ReLU network of the form c For any function
f Rd + Rdd reulizable as a shallow ReLU network, we define its representation cost
K
R(F) = inf C(0) = inf 8: fh
Σ |aull s.t. ||wl|| = 1 Vk. f = has
(13)
and a minimizer of this cost, i.e. the 'min-cost' solution, as
f E argmin R(f) s.1. f(yn,m) wn Vn, m.
(14)
where the second equality in (3) holds due to the 1-homogeneity of the ReLU activation function, and since the bias terms are not regularized (see (Savarese et al., 2019, Appendix AJ). In the next sections, we examine which function we obtain by minimizing the representation cost R(f) in various settings.
4 Closed form solution for the NN denoiser function univariate data
In this section, we prove that NN denoisers that minimize R()) for univariate data have the specific piecewise linear form observed in Figure I and we discuss the properties of this form. We observe N
5

---

N clean univariate data points (zn [=n]==1r s.t. -00 < 21 < I2 <... < ZN < 00, and M noisy samples (drawn from some known distribution) for each clean data point, such that Bn.m 2n + ca.m- We denote by en the maximal noise seen for data point In, and by en the minimal noise seen for data point Fn, i.e.,
max n
= max Cn
C
min
min C,, m
(15)
and assume the following.
Assumption 1. Assume the data {In Jn is well-separated after the addition of noise, i.e..
Vn E [N - 1]: In + En
max
In+1 1 +
min
(16)
12 and max 0, min <0. O.
So we can state the following,
Proposition 1. For all datasets such that Assumption 7 holds, the unique minimizer of R(f)) is
21
y < I1 + +
Tn + min S S In + Cn
max
Ki((y)
1 Zx
(y
(Inn
en mmaxx Zns
Zn + En max < y < In+1 + cn+1
Pn+iten tc meaar
NN
y > UN + E
max
(17)
The proof (which is based on Theorem 1.2. in (Hanin 2021 can be found in Appendix B. As
can be seen from Figure [ the empirical simulation matches Proposition I Proposition states that (17) is a closed-form solution for (8) with minimal representation cost. Notice that the minimal number of neurons needed to represent fin using he (y) is 2N 2, which is less than the number of the total training samples NM for M 2.
In the case of univariate data, we can prove that the representation cost minimizer fip (linear interpolation) generalizes better than the optimal estimator over the empirical distribution (eMMSE) for low noise levels.
Theorem 1. Let y = x where x ~ Pe (x) and e ~ N (0, o²) where x and are statistically independent. Then for all datasets such that Assumption Iariiinnhoolee holds, and for all density probability dis- tributions pa (x)) with bounded second moment such that Pz (x) > for all x E [min, Tn, max, Trl), the following holds,
lim MSE (EMMMSE +
(w))
lim MSE (fiD (v)) a
See Appendix B.2 for the proof. We may deduce from Theorem that for each density probability distribution p (3)) there exists a critical noise level for which the the representation
minimizer Sip has strictly lower MSE than the eMMSE for all smaller noise levels (this is because the MSE continuous function of rr). The critical noise level can change significantly depending on p (x)). For example, if p (r) has a high "mass" in between the training points then the critical noise level is large. However, the density function has a low "mass" between the training points then the critical noise level is small. In Appendix D we show the MSE vs. the noise level on MNIST denoiser for NN denoiser and eMMSE denoiser (Figure 13) As can be seen there, the critical noise level in this case is not small (~~ 5).
Intuitively, the difference between the NN denoiser and the eMMSE denoiser is how they operate on inputs that are not close to any of the clean samples (compared to the noise standard deviation). For such a point, the eMMSE denoiser does not take into account that the empirical distribution of the clean samples does not approximate well their true distribution. Thus, for small noise, insists on "assigning" it the closest clean sample point. By contrast, the NN denoiser generalizes better since it takes into account that, far from the clean samples, the data distribution is not well approximated by the empirical sample distribution. Thus, its operation there near the identity function, with small contraction toward the clean points, as we discuss next.
'Nttcee that the training points in Figure 1 are used in the online setting and in the offline setting we observe less noisy samples.

---

Minimal norm leads to contractive solutions on univariate data. Radhakrishnan et al. 2018 have empirically shown that Auto-Encoders (AE, i.c. NN denoisers without input noise), are locally contractive toward the training samples. Specifically, they showed that the clean dataset can be recovered when iterating the AE output multiple times until convergence. Additionally, they showed that, as we increase the width or the depth of the NN, the network becomes more contractive toward the training examples. In addition, Radhakrishnan et al. [2018) proved that 2-layer AE models are locally contractive under strong assumptions (the weights of the input layer are fixed and the number of neurons goes to infinity). Next, we prove that a univariate shallow NN denoiser is globally contractive toward the clean data points without using the assumptions used by Radhakrishnan et al. [018)] (i.e., the minimizer optimizes over both layers and has a finite number of neurons).
Definition 2. We say that f I + Rd is contractive toward set of points J.V { on C IR if there exists real number 0 S < 1 such that for any y E y there exists i E [M] so that
(18) Lemma SiD (V) is contractive toward the clean truining points {æn 1N on y
Ilf f (x+) S ly x
=
R \ UnE[N-I1
The proof can be found in Appendix B33
Minimal norm leads to alignment phenomenon on multivariate data
In the multivariate case, min-cost solutions of 14) are difficult to explicitly characterize. Even in the setting of fitting scalar-valued shallow ReLU networks, explicitly characterizing min-cost solutions under interpolation constraints remains an open problem, except in some basic cases (e.g., co-linear data [Ergen and Pilanci 2021]).
As an approximation to (4 that is more mathematically tractable, we assume the functions being fit are constant and equal to 2n on closed ball of radius P centered at each Ins i.e., f(y) In for all |/y/ In II S such that the balls do not overlap. Letting (( p) denote the ball of radius o centered at æn. we can write this constraint more compactly as f(B(zn, p)) {xn). Consider minimizing the representation cost under this constraint:
min R(f) s.t. f(B(zn. p)) = { Vn [N]. f
(19)
However, even with this approximation, explicitly describing minimizers of (9) for an arbitrary collection of training samples remains challenging. Instead, to gain intuition, we describe minimizers of (19) assuming the training samples belong to simple geometric structures that yield explicit solu- tions. Our results reveal a general alignment phenomenon, such that the weights of the representation cost minimizer align themselves with edges and/or faces connecting data points. We also show that approximate solutions of (14) obtained numerically by training a NN denoiser with weight decay match well with the solutions of (19) having exact closed-fome expressions.
5.1 Training data on a subspace
In the event that the clean training samples belong subspace, show the representation cost. minimizer depends only on the projection of the inputs onto the subspace containing the training data, and its output is also constrained this subspace.
Theorem 2. Assume the training samples {m belong to a linear subspace S C Rdd and
ler Ps E ddxd denote the orthogonal projector onto S. Then any minimizer f of 19 satisfies (2) psf" (Psy) for all y E Rd..
The proof of this result and all others in this section is given in Appendix
Note the assumption that the dataset lies on subpaces is practically relevant, since, in general, large datasets are (approximately) low rank, i.e., lie on a linear subspace [Udell and Townsend 2019) In Appendix D we also validated that common image datasets are (approximately) low rank (Table I].
Specializing to the case co-linear training data (i.e., training samples belonging to a one-dimensional subspace) the min-cost solution is unique and is described by the following corollary:
7

---

60% y
ReLU boundaries
40p y5)
A06%)
boundaries
predicted denoiser
trained denoiser
S
Figure 2: Predicted (top row) and empirical (bottom row) min cost NN denoisers for = clean training samples in d = dimensions. The empricial NN denoisers were trained with weight decay parameter = 10 and M 100 noisy samples. As predicted by theory. the ReLU boundaries align either perpendicular to the triangle edges the obtuse (left panel), or parallel the triangle edges (right panel).
Corollary 1. Assume the training samples {In] are co-linear, i.e., In = Cy U. for some scalars
C1 < C2 < ... Cn where u E IR is unit-vector. Then the minimizer f of (19) is unique and given by 8 (y) uvbu cub(uu) y) where lR R has the same form the I-D minimizer 17) JīD
with Cn and max -
In other words, the min-cost solution has particularly simple form in this case: f*) uplu y). where is monotonic piecewise linear function. We call any function of this form a rank-one piecewise linear interpolator. Below we show that many other min-cost solutions can be expressed as superpositions of rank-one piecewise linear interpolators.
5.2 Training data on rays
As an extension of the previous setting, we now consider training data belonging to a union of one-sided rays sharing common origin. Assuming the rays well-separated (in sense made precise below) we prove that the representation cost minimizer decomposes into a sum of rank-one piecewise linear interpolators aligned with each ray.
Theorem 3. Suppose the training samples X belong to a union of T, rays plus sample at the
N1 J== U... U ()) In=I where x! = ue for some unit vector u, and constants < 9 < < ... < CN Assume that the rays make obtuse angles with each other
origin: X (0) U (x
(6)
(i.e., u, uk < 0 for all l + k). Then the minimizer f of 19 is unique and is given by
(" uish (u, y) + unbr(u
(20)
where de RR - R has the form of the 1-D minimizer
17 SīD with vn.
Cn max
min
Additionally, in the Appendix C.2.1 we show that this min-cost solution is stable with respect small perturbations of the data. In particular, if the training data is perturbed from the rays, the functional form of the min-cost solution only changes slightly, such that the inner and outer-layer weight vectors align with the line segments connecting consecutive data points.
5.3 Special case: training data forming simplex
Here, we study the representation cost minimizers for N d++ training points that form the vertices of a (N 1)-simplex, i.e., (N -1) 1)-dimensional simplex R2d (e.g., 2-simplex is a triangle, 3-simplex is tetrahedron, etc.). As will show, the angles between vertices of the simplex (e.g.. an acute versus obtuse triangle in = 3) influences the functional form of the min-cost solution.
Our first result considers one extreme where the simplex has one vertex that makes an obtuse angle with all other vertices (e.g., an obtuse triangle for N 3).
Proposition 2. Suppose the convex hull of the training points {x1, T2,..., xN) C Rd is (N 1)- simplex such that æi forms obtuse angle with all other vertices, i.e., (z, x1) T (x: x1) 0

---

for all i # with i.j 1. Then the minimizer f of 19 is unique, and is given by
(y) = =x1 Σ n=2
un Caonn(u (u (y x1))
(21)
where Un = 2i, -1
1| -m @n(t) = ( [t anl+ - It bnl+), with an = bn = =| x1ll and
8n ||0n 21 (bn an for all 2, .....N. N.
This result is essentially a corollary of Theorem 3 since after translating æ1 to be the origin, the vertices of the simplex belong rays making obtuse angles with each other, where there is exactly one sample per ray. Details of the proof are given in Appendix C.2
At the opposite extreme, we consider the case where every vertex of the simplex is acute, meaning for all n 1,... N we have (xz, - Fr,) (a: conjecture: the min-cost solution is instead sum of N rank-one piecewise linear interpolators, each aligned orthogonal to a different (N - ( -immensional face of the simplex.
Fn)) > for all i,j & n. In this case, we make following
Conjecture 1. Suppose the convex hull of the training points {a I2,..., ZN [awco R is (N - 1)-
simplex where every vertex of the simplex is acute. Then the minimizer f of 199 is unique, and is given by
N Σ
(y))=
UnDn(un zn))
(22)
n=1
where: is the projection of onto the unique (N 2)-dimensional face of the simplex not containing wni x is the weighted geometric median of the vertices specified by
nn x
T arg min mERd
En Zn
n=1
Un
-2 22,, 2n Un
2n xr
and (t())
sn anl+ -It -bt-bnl+) with an p. bn
||0, - 2n P. and 8n
20, x1|/ an).
Justification for this conjecture is given in Appendix C.3.2 In particular, we prove that the interpolator I given in (86) is min-cost solution in the special case of three training points whose convex hull an equilateral triangle. true general, this would imply a phase transition behavior the min-cost solution when the simplex changes from having one obtuse vertex to all acute vertices, such that ReLU boundaries go from being aligned orthogonal to the edges connecting vertices, to being aligned parallel with the simplex faces. Figure illustrates this for N 3 training points forming a triangle in d = dimensions. Moreover, Figure 2 shows that the empirical minimizer obtained using noisy samples and weight decay regularization agrees well with the form of the exact min-cost solution predicted by Proposition X and Conjecture
!|
In general, any given vertex of a simplex may make acute angles with some vertices and obtuse angles with others. This case is not covered by the above results. Currently, we do not have conjectured form of the min-cost solution in this case, and we leave this as an open problem for future work.
6 Related works
Numerous methods have been proposed for image denoising. In last decade NN-based methods achieve state-of-the-art results (Zhang al.) 2017 2021 See [Elad et [2023] for a comprehensive review of image denoising, (Sonthalia and Nadakuditi (2023) empirically showed double decent behavior in NN denoisers, and theoretically proved in a linear model. Similar to a denoiser, an Auto-Encoe -eoo-Enc (AE) is NN model whose output dimension equals its input dimension, and is trained to match the output to the input. For AE, the typical goal is learn an efficient lower-dimensional representation of the samples. RRadhakrishaan et al. [2018) proved that single hidden- layer AE that interpolates the training data (i.e., achieves zero loss), projects the input onto a nonlinear span the training data. In addition, |Radhakrishaan et al. (2018 empirically demonstrated that multi-layer ReLU AE is locally contractive toward the training samples by iterating the AE and showing that the points converge to of the training samples. Denoising autoencoders inject noise into the input

---

data in order to learn a good representation [Alain and Bengio 2014). The marginalized denoising autoencoder, proposed by Chen et al. [2014], approximates the marginalized loss over the noise (which is equívalent to observing infinitely many noisy samples) by using Taylor approximation. Chen et al. (2014) demonstrated that by using the approximate marginalized loss we can achieve a substantial speedup in training and improved representation compared to standard denoising AE.
Many recent works aim to characterize function space properties of interpolating NN with minimal representation cost (i.e., min-cost solutions). Building off of the connection between weight decay and path-norm norm regularization identified in Neyshabur et al. 2015 2017 Savarese et al. (019 showed that the representation cost of a function realizable as univarite two-layer ReLU network coincides with the L -norm of the second derivative of the function. Extensions the multivariate setting were studied in Ongie et al. (2020), which identified the representation cost of a multivariate function with its R-norm, a Banach space semi-norm defined in terms of the Radon transform. Related work has extended the R-norm to other activation functions Parhi and Nowak [202T) vector-valued networks Shenouda et al. [023). J and deeper architectures |aarhi and Nowak [002]. A separate line of research studies min-cost solutions from a convex duality perspective Ergen and Pilanci| [2021]. incuding
two-layer CNN denoising AEs Sahiner et al. [2021]. J. Recent work also studies properties of min-cost
solutions in the case of arbitrarily deep NNs with ReLU activation Jacot [0022] Jacot et al. 2022
Despite these advances in understanding cos- solutions, there are few results explicitly character- izing their functional form. One exception is Hanin [2021), which gives a complete characterization of min-cost solutions in the case of shallow univariate ReLU networks with unregularized bias. This characterization is possible because the univariate representation cost is defined in terms of the 2nd derivative, which acts locally. Therefore, global minimizers can be found by minimizing the representation cost locally over intervals between data points. An extension of these results to the case of regularized bias is studied in Boursier and Flammarion 2023]]. In the multivariate setting, the representation cost involves the Radon transform of the function a highly non-local operation - that complicates the analysis. Parhi and Nowak [202T] prove a representer theorem showing that there always exists a min-cost solution realizable as a shallow ReLU network with finitely many neurons, and Ergen and Pilanci (202T) give an implicit characterization of min-cost NNs the solution to convex optimization problem, and give explicit solutions in the case of co- co-linear training features. However, to the best of our knowledge, there are no results explicitly characterizing min-cost solutions in the case of non-colinear multivariate inputs, even for networks having scalar outputs.
Discussions
Conclusions. We have explored the elementary properties of NN solutions for the denoising problem, while focusing on offline training of a one hidden-layer ReLU network. When the noisy clusters of the data samples are well-scparated, there are multiple networks with zero loss, even in the case of theoretical works focused on the wver-parametrized regime. In the univariate case, we have derived a closed-form solution to such global minima with minimum representation cost. We also showed that the univariate NN solution generalizes better than the eMMSE denoiser. In the multivariate case, we showed that the interpolating solution with minimal representation cost is aligned with the edges and/or faces connecting the clean data points in several cases.
while having a different representation cost. In contrast, previous
Limitations. One limitation of our analysis in the multivariate case is that we assume the denoiser interpolates data on a full d-dimensional ball centered at each clean training sample, where d is the input dimension. In practical settings, often the number of noisy samples M < d. A more accurate model would be to assume that denoiser interpolates over an (M- - 1) -ddimensional disc centered at each training sample. This model may still be a tractable alternative assuming interpolation of finitely many noisy samples. Also, our results relate to NN denoisers trained with explicit weight decay regularization, which is not always used in practice. However, recent work shows that stable minimizers of SGD must have low representation cost Mulayoff et al. [2021). Nacson et al. [2023), and so some of our analysis may provide insight for unregularized training, as well. Finally, for mathematical tractability, we focussed on the case of fully-connected ReL.U networks with one hayde.-layer. Extending our analysis to deeper architectures and convolutional neural networks an important direction for future work.
10

---

Acknowledgments
We thank Itay Hubara for his technical advice and valuable comments on the manuscript. The research of DS was Funded by the European Union (ERC, A-B-CC B-B-C-Deep, 101039436). Views and opinions expressed are however those the author only and do not necessarily reflect those of the European Union the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of Schmidt Career Advancement Chair in AI. The research of NW was supported by the Israel Science Foundation (ISF), grant no. 1782/22. GO was supported by the National Science Foundation (NSF) CRII award CCF-2153371.
References
Guillaume Alain and Yoshua Bengio. What regularized auto-encoders learn from the data- getneeeeeraaingggg distribution. The Journal of Machine Learning Research, 15(1))3563-3593 2014.
Etienne Boursier and Nicolas Flammarion. Penalising the biases in norm regularisation enforces sparsity, arXiv preprint arXiv:2303.01353 2023.
Minmin Chen, Kilian Weinberger, Fei Sha, and Yoshua Bengio. Marginalized denoising auto- encoders for nonlinear representations. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning. volume 32 of Proceedings of Machine Learning Research, pages 1476-1484, Bejing, China, 22-24 Jun 2014. PMLR. URL https
//proceedings..o .ml. ppress/332/chengee html
Michael Elad, Bahjat Kawar, and Gregory Vaksman. Image denoising: The deep learning revolution and beyond survey paper. SIAM Journal on Imaging Sciences, 1693)115941164, 2023. doi: 10.1 10.1137/23M1545555
wtt.://////11/1/1111111. 1137/23M1/553
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterized neural networks. The Journal of Machine Learning Research, 22(1):9446-9708, 2021.
Boris Hanin. Ridgeless interpolation with shallow relu networks in 1d is nearest neighbor curvature extrapolation and provably generalizes on lipschitz functions. arXiv preprint arXiv:2109. 12960, 2021.
Samuel W Hasinoff, Frédo Durand, and William T Freeman. Noise-optimal capture for high dynamic range photography. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 553-560. IEEE, 2010.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 83:6840-6851, 2020.
William C Horrace. Moments of the truncated normal distribution. Journal of Productivity Analysis, 43:133-138, 2015.
Arthur Jacot. Implicit bias of large depth networks: notion of rank for nonlinear functions. In International Conference on Learning Representations (ICLR), 2022.
Arthur Jacot, Eugene Golikov, Clement Hongler, and Franck Gabriel. Feature learning in L-2- regularized dnns: Attraction/repulsion and sparsity. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 6763-6774, 2022.
B. G. Manjunath and Stefan Wilhelm. Moments caleulation for the doubly truncated multivariate normal density. Journal of Behavioral Data Science, 171): May 2021. doi: 10.35566/jbds/ v1n1/p2. URL //jbss. isdsa. org/ intp//ndex.... phpp www.b////rrteeeeiieeeeeeeeeeeeee
Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability: A view from function space. Advances Neural Information Processing Systems (NeuriPS), 34: 17749-17761, 2021.
11

---

Mor Shpigel Nacson, Rotem Mulayoff, Greg Ongie, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability in multivariate shallow relu networks. In International Conference on Learning Representations (ICLR), 2023.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory (COLT), pages 1376-1401 PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring gener- alization in deep learning. Advances in Neural Information Processing Systems (NeurIPS), 30,
2017.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning Representations, 2020. URL http:s///ppnrrreee....eee wttp::/wwwwweeeeerw//iiieeee
Rahul Parhi and Robert D) Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(1):1900-199, 2021.
Rahul Parhi and Robert Nowak. What kinds functions do deep neural networks learn? insights from variational spline theory. SIAM Journal Mathematics of Data Science, 4(2):464-489, 2022.
Adityanarayanan Radhakrishnan, Karren Yang, Mikhail Belkin, and Caroline Uhler. Memorization in overparameterized autoencoders. arXiv preprint arXiv:/810. 1ato:/800./003,,. 2018.
Gabriel Raya and Luca Ambrogioni. Spontaneous symmetry breaking in generative diffusion models. arXiv preprint arXiv:2305. htti:22305./9933,, 2023.
Stefan Roth and Michael J. Black. Fields of experts. International Journal of Computer Vision, doi: 10.1007/511263-000-0009999 s $11263-008-0197-0
82(2):205-229, 2009,
URL https://doi.. ortp/0..10/01
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John M. Pauly. Convex regulariza- tion behind neural reconstruction. In International Conference on Learning Representations, 2021. URL http:////pppppeeeeeeeweee/r/rrr/
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
Joseph Shenouda, Rahul Parhi, Kangwook Lee, and Robert D Nowak. Vector-valued variation spaces and width bounds for DNNs: Insights on weight decay regularization. arXiv preprint arXiv:2305. 16534, 2023.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Rishi Sonthalia and Raj Rao Nadakuditi. Training data size induced double descent for denoising feedforward neural networks and the role of training noise. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL httppst/s///openiii http:/pppererreeeeeeff.oormmmme ddderr//PVdd
Madeleine Udell and Alex Townsend. Why are big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, 1600 2019.
Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang. Beyond a gaussian denoiser: Residual learning of deep cnn for image denoising. IEEE transactions on image processing, 26(7): 3142-3155, 2017.
Kai Zhang, Yawei Li, Wangmeng Zuo, Lei Zhang, Lue Van Gool, and Radu Timofte. Plug-and play image restoration with deep denoiser prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10):660066374 2021.
12

---

A Marginalized loss
In this section, derive the marginal loss for the case of a 1-hidden layer ReLU neural network. The loss function is,
C. (0, 0) = Exyy
ag ( y/+
a a y|+ 1w) vl+ - 2 Σ
a. [.
[ yl+ ||0/|²
1=1
a az Bnyy [ 1w0, y]+] 2 Σ
T
Eny [ T aa:uo! y)++ E ||
K
K
k
a a Be Eyyla [100 y) (wo v]+11 - Σ
T
[Bylc [er T aa:wo! y)+ + I ||
2m
K
K
K
a Exz EEyic [m y)+ Eyia [[w]] y)++]] - Σ
En
[Eyle [ar as asslo y]+]] + E ||:0|1
im
K
K
Σ a
En
Eyjo [Io ul [wo y1+1] Σ Σ a a, 1En [nylr [[ b/++] Eng [[w,] x]+]]]
K
K
K
E (x)
Σ
a m x)
a,l [Byl la [Iw, 31+ +]+]]
1=1
K
a a Ex Eyle
[w u1+ Eyler [[w]] v/++1
1=1
We denote by
Hif (w,, wj, 0²) Ex Eygnn [ [w v1+1 Eyj [[]]] y]+1 Enj [[m]] y)++]
Note that H > 0 since H is covariance matrix. Thus we get,
K a,H. (wi, wy, 0²)
(0, F.g Σ and (1i) xr || - x
ΣΣ i=1
a
Lemma 2. In the case of the ReLU activation function and Gaussian noise the following holds,
t (in æz |wwl [ a) = ||wssll (1--0(- t0,
1 x + 40
where s,, Eb are the density and cumulative distribution of standard normal distribution, and
H = Eg (x, wi, Wi, w)) - Φ (ıo æ. (|wlll .0) Ō (10] x, ||w0 .o)
where,
(-ul(fd); 0,, D(..))) (z, Wi, 02) P 21 0, 0: (1,0) x(ti))) ( 012 + det (E) P(zi -11, 22 > -142; 0, E(.))
+ 1 (-11) μ1 1102212 H22 11H2
40
12
P
>> -M1 Ar An
A1222
Pg (-p2) =
V0z
P(z1 >
111, > M12; 0,
P1
2 -12; Auz Aez
F (-p1)
von
P(21
11, 22 - U2; 0, Σ)
13

---

Analytical Expectation
Amelytical Expeciation
730
530
430
230
130
2.45
(b)
Figure 3: Numerical evaluation of (23) Histogram of the sample average of (cLU(x) for 10000 Monte-Carlo samples. We denote by E the analytical expectation and by the sample average.
Figure (a) is for 1, = 5, the normalized error is LE-E = 0.0032%. Figure (b) is for
E
-1 a = 5, the normalized error
EE E
0.0059%.
and
[4]
w
x
(12]
w x
002 wwi ??
oww? wi
x(1)
111
012
012
022
oaw w
ww
o²
llwll
Σ-1
Notice that we denote by P (z1 > 02 > 0; (z.)), ( I(id) the probability that 21 > 0, 22 > 0 where (2), N (H(tt), (.))).
Proof. Let x ~ N (1,, )²), then
E
E -|
((F>))))))))))
E | 0] Pz>>
[x/r 0f (1- (--)
Note that given x > 0 the distribution of æ is truncated normal Horrace 2015 Therefore,
E [ata: > 0] + 1- (-
E [[+]+] (1 + 1r + opp (-#)
(23)
Note that given æ, y is Gaussian random vector. Therefore, given x,
wx N (w o² |
and we obtain. Eyja x [ v)+]
|| EEgia
[[0n] y]+]
u _ x
To,T.
||
1-
+
w x + top o4p
Let (2) be Gaussian random vector with
f1
/
[12
0'1
012
Σ
012
022
'Note that of.
14

---

then,
E [[=1]_|[>>] [22]+] E [[2]] [22] > 02 P( 20,2200) 0000)+a0>000.0000000000000000000
E 21 21
0, 22 0 22)
Given 21 > 0, 22 > the distribution of (21, ) is truncated multivariate normal distribution
Manjunath and Wilhelm 2021]. therefore,
E [2] 22 > 0, > 0]
d12 + 22 (-11) Fi (11) + 012 (-p2) (2) F/ (22)) f4-1;;,22
+ (011022-01200 - 122021 p(21 > -11, 22 122 Σ)
- (on (- + F1 (- (0 (- + F22 (-H22)
+ (o111) (-p1) + 012 (-12) + M1) (021 (-m1) + 022 (-w2) + p2)
0,
012 + det (Σ)
p(z 141 22 - 112; -12; 0| Fo (-11) μl2 + μi 0 F2 (-w2) + 11
(24)
where f(-W μr; E) density function of of Gaussian random vector with mean vector and covariance matrix E at the point 4e, and
1 f (Z), 22; 0, 2 dz1
(22) = P(Z1 > 111 Z2 > 0, Σ) 1 f (2), 22; 0, Σ) dz2
F1 = P(Z1 > 111, Z2 > u2; 0, 2)
We denote by A E thus,
1
exp (
(A11e) 2A1231 + A2223)
d21
m1
exp
2 12223
2
exp
- N1127 - A122122
dz1 =
2
10
1
A12
A7122
exp
22
exp
21 +
dsp
2
2 A11
A11
2A11
111
A2222 2
00
1
11222
exp
2
2 A22
22
+
2A11
exp
21
A11
dzi
A11
2/
2x
A
1
exp
22222 +
2A11
V
A11
P
2>
M11
A11
A11
Thus,
J.m f 02,, d21
1
1
A2222
2TT
A12 1
2T /dct
(Σ)
exp
2
A2222
2
2A11
V
ALi
P
<>
H11
A11
A11
A1222 1
exp
2/
2
>
- M1;
V2T022
2002
An
AA1
Similarly, we obtain,
1
1
A21 21
(21, 22; 0, E) day
exp
21
2
P
2
U2
v 22
2011
Ag2
A222
Therefore,
Vauz
P
2 > -11;
A1252 1
An A1l
F3 (22)
P(Zi
111, Z2 |22 0, E)
(-ا))
P -22; A3121
19 (oon
Asz Aza
F1
P(Zı > - 11, Zz > - p2: 0, Σ)
15

---

Analytical E Expectation
Analytical Expeciation
500
932
532
432
300
333
100
(a)
(h)
Figure 4: Numerical evaluation of (24) Histogram of the sample average of ReLU(22 (eL)))))))))))
for 10000 Monte-Carlo samples. We denote by E the analytical expectation and by E the sample
average. Figure (a) is for u
E
13 9
the normalized error is E
E 0.0093%.
17
8
Figure (b) is for f
Σ
10
2
1)
the normalized emror is EE-E| 0.0044%.
2
Next, present in Figures 3 and 4 numerical evaluation of Monte-Carlo simulations verity the analytical results.
23 and 24
As be seen, the
B Proofs of Results in Section
B.1 Proof of Proposition]
1
Proof. Let
= {Inn = In + Cn kn),, [M], [M]. -00 < σ1 < D2 < ... BN < 00
such that Assumption D hholds We define a reduced dataset, which only contains the noisy samples with the most extreme noises
D (zn + en )n (on en ,In),, E [N].
We define the e ppenllty on the weights,
K C K) Σ (||xX1 2 [|wm)1?)
According to Theorem 1.2. in Hanin 2021 since we have opposite discrete curvature on the intervals [21 cmax x2 epin]
EN eaaz EN eminn,
(he(v) hv(v)
xx) (,,
(JiD (v))
where
C. = inf V(y,,) ho(y)= = =x}
8.K
Also note that,
(ho(y) hol = x V(y,
= - UiD (v))
since fip (v) interpolates all the points in D. and if we assume by contradiction that C, info, (C (0, K) V(y,z) E D ha(v) = x then C. + info x (C (0, K) V(y. x) E D ho(y) J. thus contradicting Theorem 1.2. in Hanin 2021 Note that the minimal number of neurons needed to represent Jip (y) is 2N 2. So, if
2N then fip the minimizer of the
representation cost (i.c.. fiD arg min, R(f)).
16

---

B.2 Proof of Theorem 1
First we prove the following lemmas.
Lemma 3. Let de where E E R, o 0 then,
lim a. geMMSE (y) = -1--NN (y) a+0+
Proof. Notice that the following holds,
1-= 2
Iy- 2 2
min, 1N-
exp
2n
exp
exp
2
N
12
N
M- 12
min, 11 xt, 12
i=1
exp
20
Diml exp
20
exp
20
1/-0
min, 1g-22
exp
2
1== exp
y-
min. 1V 2m 2
In addition,
y x, 2
minn
by znl
[1
ly xa min, ly In 2
lim exp a+
{0
20²
by x. 1 * min, ly - F.n
so we obtain,
1y-2,1
exp
20
1
ly x; 2 min, 1/ Iz 12
lim
N
18-
0
xz
2 * minn 1y xz
===1 exp
20²
Therefore,
ΣN 2i exp
1y-z, 12
lim 3cMMSE (y) = lim a+00+
20
arg min by - In 2
a++
Σ exp
1y=2,1 12
arg min by xnl
-I-NN (v)
Lemma 4. Let y + ae where & E R. > 0 and N (0, 1) then,
lim MSE (BMMSSE (2)) a+0+
lim MSE (a'-NN (1)) a
Proof.
MSE (8EMMSE (1))
=E (acMMSE (v) - =)²]
=x)
= E (BMMMSE (v) - 1NNNN NN (V) + 2N-NN (3) - ==)
[B))++B((MMNN [[ (v)- -1 (1)) ??]
MSE (5 (v)) +
2E [
NN (v) =)) (BOMMSE (y) -1)- (2))
Note that,
3.MMSE (v)
It exp
Ig-wr
20
Em max, [ exp
y==
20
Σ 1==1 exp
1y-a;
ΣN exp
20²
20
1y=zy 20
Σ exp
= -max(x;)
maxfxz}
Σ #= exp
ly=2," 20
3
17

---

goMMSE (y)
2i=1 2i exp
1y=r
20
Σi=1 i== miny {2z}
N
exp
10-2,
20
Ei=l exp
1
Ex= exp
1y-2,l
1
2x²
2
.v.
1- 12
ii=1 exp
=min(3;)
min(ry}.
3
-i=1 exp
1y 1 2 -2
Similarly,
-N
NN (y) = arg min by - xil 1 max (2;)
-N-NN (y) arg min by x 2 min
thus 3M4 > 0 Vo > 0
LeMMSE (y) - 1I-NN (v) < Mo.
According to Lemma
lim a SOMMS (v) - INNN (2) a+0
almost surely. Note that,
NN En.y (BUMMSE (v) - 21 1N-NN (v)) = =Eg,e [BOMMSB - (x + oc)) ?
Therefore, by the Dominated convergence theorem we obtain
lim Ez,e a-0+
(*aMMSE (x + σE) -I-NN (x + oe))
Ex,e lim (2eMMSE (x + σE) - -NNNN (x + σE)) 2] ae)
=0
a a-+0+
Similarly,
lim Ez,e [( (x + oe) -x) (1eMMSE - a-0+
(x + oe)]]
=
E lim (+1-NN (x + σc) x) (* (z + ae) - -N-NN (x + dr)) = 0
-++
NN Since d MMSE (y) and a INNNN (y) are bounded and E [x] < co. Therefore, we get
lim MSE (fOMMSE (v)) lim MSE (a' NNN-NN (y)) a
Next, we prove Theorem
Proof. Assume, without loss of generality, that N = 2. Let Pa, (a) be a probability density function with bounded second moment such that Pz (x) > for all a E [zi, x2). According to Lemma 4
lim MSE (*eMMSE (v) a
lim MSE (aI-NN (v))
So need to prove that
lim MSE (#I-NN (2))
lim MSE (fi'D (y))
a-o
For the case of N = 2, the training set includes two data points (21, So we get,
-1-NN NN (y)
y <
21+32
Ø2
21+ Σ 4y
y<
fiD (v)
32-41 + A2 A (y (1-11 -1) +m
22
x2 + + y>12+A2
Ø22
18

---

where [M f1.m = A1 > O, [MM fm.m = A₂ < 0. Note that 1N-NN (v) = fiD (v) for
all y E (-00, + A1) U (z2 + A oo) and [|x] < oc, E | co. Therefore,
MSE (+ (v)) - MSE (fiD (v)) =
| dx 11
x2 dy (iI-NN (y) x) Pylz (3/2z) Pa (a)
(25)
-fo de
c dy (SiD (v) x)² Pule (u/2)) Pa (x)
(26)
First, we derive 25
r2t
dr
dy (5 (52-NN (1) - x)² Pale (u)z)) Pz (x)
II+
p
(I1 x))² Pylz (y|x) Pa (z) dydæ +
(x2 (02- - x)² Pula (y/z) Pa (z) dydr
21+
Ex
P
E
I + A1,
21 + x2
1)
(x) x)²
+ Ez PVEE
21 12
22 + A2 [=)) (02 x))
2
2
Note that,
P
y E
1 + A
T1 + 52
x
(x) - x)²
< E [2] - =z)² < <0
2
P
y
E
31
+ 82
22 + 22
2
(x2 x)
< E
(02 - x) < 80
2
thus by the Dominated convergence theorem we obtain
A2+
lim
dx
dy ($--NN (v) x)² Pule (2(x)) (x)
a-00
2I+
Ex
lim
P
Il + A 1, y E
31 + x22
x3) (x) - xr)² + Ez
lim
P
yE
xi 32
22 + 12 x))
(x2-x)²² x)²
a +-+
2
Ex
(x 5ı )²
E 31,
31 + 222
}
(x x2) 2
x E
x1 + 32
32
000
2
2
since Pz (x) > 0 for all x E [21, Ø2). Next, we derive 26
Sr dx Jattn (fiD (v) x)² Polr (y)z) Po (x)
m2t
Ex 1 A,, + A (fiD (v) -x)²
(m + Aul (fiD (o + ac) - 2)9
E Ex
Note that,
Eg,e [1 to [m1 + A1, + A2]) (fiD (z + σe) =)²] < Ez,e (fi oe) - =)]] < 00
thus by the Dominated convergence theorem we obtain
lim L dx c-0
ArtAA JzttAi dy (fiD (v) x)²² Pa x (y/xr) pa (x)
lim Ey,c [ fo A x2 + A2]} (SiD (a ac) - -x)²] =
c-001
Ez.c
lim 1 [11 + +1, + A2) (FiD (a + oc) x=)² =0 0
+0
19

---

since
+ lim 1 1 + 0c [x A1, 22 + A2]) 1 for [x1, 22]]
c+0+
21 11
lim -+
fiD (z +
11 S x S 32
322
I > D2
B.3 Proof of Lemmal
Proof. First we prove that for all y Un 1]
Fn4 1
miin
(iD(y) y. We find the
intersection between the line (i)(v) = y and the linear part of 17 (the third branch)
In+1 In
(y (In + 6x
+ Inn = y
(27)
In+1 n+1
(In + emaxx
(In+1 In) (y (In en
) + In (In+1 cut (on
cx mux))
(In+1
min
(In + cn
max
(28)
In (In+1 + Eatl (In + mxxx) (2n+1 2nn (I,, + max
y (cnin
C
mmax
(29)
In (In+1 + (n+1)
In+1 (In + En max
y (cmin
En
max
(30)
min In n+1
In+1 1n
max
y min
En
max
(31)
In 1
n+1
min
(32)
elax
nn+1
Note that
In+1<
max
min
En
n
max
maax
mln n+1
In+1 + min
(33)
Since,
T In+1 max
In n+
min
Tp + En
max
(34)
max
n+1
(In, + 6n max)
mamax
Ea+1)
In+16n
xn-111
(35)
(In + En max
en+1
E
max < In 1
max
(36)
In + n
max
min n+t
< Tn+1
(37)
+ En
max < In+1 min
(38)
which holds according Assumption] 1
In+1cn max
min
< Fa+1 + ct+1
(39)
emax
In+16n
max
Fn ex+1
min
< (xn+1 + min
(mmax
6+1
min
(40)
In n+1
min
min n+1
(In+1 6R
min n++1
(41)
In < Ta+1
6n max
+ 6241
(42)
En + max < In+1 + n+1
(43)
which holds according Assumption I
Next we prove that fiD(y) is contractive toward a set of the clean datapoints (a,, ) on In the case where y E (-o0, 21 + cminn] or y UngiN| +
UnEIN-11
Zatic Za ail
cua memin
emin, 2 + emax] ory E JaN + maxx 0o) fin(v) E fa LN therefore 18] holds for all 0 S a < 1.
In the case where UnEIN- + en #1+15
max x,, Catt
we choose
I (y) (xx))
Ent1 + m - (xn + cmax) (y - (xn + mmax))
Fnt1 Tn
(44)
20

---

100
Xaet
Neap C103
Figure 5: Illustration of Sip(y).
There exists 0 71 < 1 such that
Fn
In+1 Fn
(y (In, + em max)) In 719
(45)
In+1 +
-++1
min
- (In + maax)
since for y E Une[N- [onn + max
(iD(y) is bellow the line f(v) because
(i)(V) an affine function with slope larger than and liD( Enat 6.4
In C.
ciia mil3
Therefore there exists 0 < on <
[ii (v) f (x,)) = In+1 + e (xn, + emaxx
In+1 Fn
(y (In + = S ny - In S 01 (y - Inn)
(46)
since,
113/ Fn S 01 (y xn)
(47)
01 2 1/ - In
(48)
In
In the case where Une[N-1
Bntt max
N, [ pp Int1
min n++l we choose i = 1,
min
1sD (v) (In+1)] = Int1
Tn+1 - Fn
(y (rn + maxx) - In
(49)
Int1
min
n+1
(In + en
emax)
There exists 0 72 < 1 such that
Tnt1
Un+1 Inn
(y (Ixz + ((ax)) + In 2
y
(50)
Fn+1
n+1
min - (In + max)
9/2
#n+16 max -2
min
since for y E UnE(N -1] 1](
Int1 + minnl fin(y) above the line f(y) = y because
fip (v) is an affine function with slope larger than I and fip! Therefore there exists 0 < 02 <
2n 20 G.
minc
mma 60
mii
[Íi (v) - f (fa+1)) = Fnt1
Øp-1 En
(y (In + ( - xn (51)
Ent1 + n+1
(In + e
maxx
< Fnt1
S a2 (Int1 - y)
(52)
since,
1 -1 2) S 02 (In+1 y)
Ent1
(53)
7/2
a2 > Int1 1 y
(54)
In+1 - y
Therefore
18 holds for max(aj, a2).
21

---

C Proofs of Results in Section 5
Let : Red be any function realizable as a shallow ReLU network. Consider any parametriza- tion f given by f(y) Σx= ax(w;, y b+l++ + Vy cc We say say such a parametrization is a min- imal representative of f if || 1 and a + 0 for all k 1,.., K, and R(f)) = Ek=1 || ll2- In particular, the units making up a minimal representative must be distinct in the sense that the hyperplanes describing ReLU boundaries H₂ = {z R : by 0} are distinct, which implies that no units can be cancelled or combined.
We will also make use of the following lemma, which shows that representation costs are invariant to a translation the training samples, assuming the function suitably translated.
Lemma 5. Let f _2 Rd be any function realizable as a shallow ReLU net satisfying norm ball interpolation constraints f (zB p)) = { for all n = L, I.... N. Let To E R Then the function
fly To) + Zo such that R(g) Rf)) and g a.. + Fo; p)) = {ar + σo) for all g 1 N.
Proof. First we show (B(,,, + no: p)) = fan + Fo } for all n I...., N. Fix any and let Bax,, + zo: p). Then y = y + Dg for some y' E (a p), and so g(v) = f(y') + To = In + 20.
as claimed.
To show that R(g) R(f), let f(y) Σk an anww y bxl+ + Vy + c be any minimal representative of f. Then
(
ag w (y x0) + bel+ + V(y 2o) +
(55)
x=1
K
ag
un T y + bel+ + Vy+c +
(56)
k=1
with by = by w xo and ē = c x0 Vxo. And so R(g) I Σk |aa|12 1|2 = -R(f). parallel argument with the roles of g and reversed shows that R(f) R(g), and so R(f) R(g).
In particular, this lemma shows that if (1y) is nolm-ball interpolating representation cost minimizer of the training samples [mn)a= then g' = (y--o 2o) + is a norm-ball interpolating min-cost solution of the translated training samples (z,, mo |
C.1 Training data belonging to subspace
The proof of Theorem 2 is a direct consequence of the following two lemmas:
Lemma 6. Suppose the clean training samples {xn ) belong to a r-ddimensional subspace S C Rd. and let Ps denote the orthogonal projector onto S. Let f(y) be any function realizable as a shallow ReL.U network satisfying f( (B(xn, = {ma) for all n. = 1,..., N. Define g(y) = fsr().). Then g B (2(,,, P)) {mn} for all = 1,... N, and R(g) R(f), with strict inequality if f + g-
Proof. First, for any y B( p) we have gly) Psf(y) =PsØn Fn. Therefore, gBB(nn, p)) = ( { for all n I,..., N.
Now, let f(y) = Σk1 axww y + bn]+ + Vy + e be a minimal representative of f. Then Σx= Par (wv y + bu]+ P(Vy c). Since |Palll < <|aax|l for all k, we have
Q(v)
R(g) S Ek 1 |sax & I ||au|| = R(f).
Now we show of * implies R(g) < R(f). Observe that if any of the outer-layer weight vectors ag & S then |Saa < ||as]l, which implies R(g) < R(f). Hence, it suffices to show that f * g implies some as & S.
First, consider the case where P&V V and Psc c. Then in this case + g if only if (Psaa - au)(unT y + bu]+ * for all y E IRd, which implies Psaą + a for some kt or equivalently a S.
22

---

Next, assume either V&V & V or Psc + Fix any training sample index n, and let A,, denote the index set of units active over the ball n. p). Then, since f is constant for all y E B (. p). the Jacobian f Eie a V for all y (2 p). This gives V - LieA, a₁ a. Therefore, if PsV V # V then at least one of the a & S. On the other hand, if Psc & c then for all y B(In:)) p) we have
f1)
Σ (bbl kE
E (arw) +V
Σ bbastc=
E
bbas+e nn
kE
kE
kEAp
which implies - &n. -KKA, byag, and since H, S this implies some as $ S, proving the claim.
Lemma 7. Suppose the clean training samples {æa J belong to an r-dimensional subspace S C. RR, and let Ps denote the orthogonal projector onto S. Let f be any network satisfying [(B(r,:))) = }- Define h(y) = f(Psy). Then h (an, = {mn) and R(h) R(f), with strict inequality if h + f.
Proof. Define (B p)) = (y E Rdd Psy E B( p)), i.e., the set of points in Rdd whose {wn). Also, by properties of norm-balls, we have B(xn: P) C Ps (B(r. p)). Therefore, (a p)) = {mn} for all n = 1,..., N.
projection onto S is contained in (a p). Then clearly h(P5'(((a (B(x,, p)))
Next, let fly) = Ex=I as axwwg + bul+ + Vy + e be a minimal representative of f. Then K
h(y) ビ (Psw)))))) T "y bk]+ Vssy + c. Since || s |||w>]| for all k, have R(h) < > ||ax|] Pswall S E |ax | = R(f).
Finally, we show that if f * h, then R(h)- < R(f). Observe that if any of the inner-layer weight vectors wy & S then |uwkl < ||wx|l. which implies R(h) < R(f). Hence, suffices to show we & S. First, consider the case VPs = V. Then f of h if and only
that * h implies PsWE& # wg for some k. or cquivalently, wy & S. Next, consider the case VPs * V. Fix any training sample index n, and let A, denote the index set of units active over B (Z,,, p). Then,
since f(y is constant for all y E B(æn: p). the Jacobian 0f(x) ΣkEA, W. + V = 0 for all
y B,, p). This gives V = =x a.w. Therefore,
Ps V (i.c., at least one row of V is not contained in S) then at least one of the wa $ S, proving the claim.
Finally, we now give the proof Theorem 2 and Corollary
1
Proof of Theorem be the case that f (T) = fs (Psy) for all Rd since otherwise the representation cost of f
Let f be any min-cost solution. Applying both Lemma 6 and we see must
could be reduced.
Proof of Corollary ! Suppose is one-dimensional, i.e., S = span(u) } for some unit vector z E Rdd.
Theorem shows we can express any min-cost solution f*
K
(z)) = Σ a mnslsnn Ty y + bxl+ + vuu' T " + cu = uolu') T)
1=1
where
o(t) =
Σ anlss + bx]+ + ut +
is such that R(f*) R(d). Therefore, minimizing the representation cost subject to norm-ball interpolation constraints reduces to a univariate problem:
min R(Ø) s.l. Φ((c. Ca + p)) = Ca
where en u In. The minimizing 6² is unique and coincides with the 1-D denoiser fip in 17 with nn Cn. and max
min miin p.
23

---

C.2 Data along rays
We begin with key lemma that central the proof of Theorem
Lemma 8. Suppose {u.)i=1 C IR is collection of n unit vectors such that u, uj < 0 all + j, and w is unit vector such that u, > 0 for all i ,,,,, Lel a E Rd be any veclor. Then,
u (u w) < |||||
Before giving the proof of Lemma we first prove auxiliary result.
Lemma Let a E IRd be unit vector, and suppose {u: C RR a collection of unit vectors such that u > 0 for all and u. u, for all + j. Let b u.u. a. Then ||b a/2| 1/2 with strict inequality if n 1.
Proof. It suffices to show bT a 2 b b, since if this is the case then
1
b - a/21 = / (b (b-a)) V b bTa a 4
aaaa a
(57)
2
which also holds with strict inequality when 6 a'abb' b b.b.
First, if n 1, then b CJuju, and bJ6 a uu un a a auujua a bTa Now assume > 1. Then we have
n
b a Σ
u. u;u
(58)
a i u
(59)
a u unu
(60)
(61)
The first and last equalities hold by definition. The second equality holds because each is unit vector. The last inequality holds because for +
(aTu;) (U, a, (u, a) < 0,
since u, uj < 0 and a w. a uj by assumption.
Now we give the proof of Lemma
Proof of Lemma
Let v D t a a/u. Then we have
S Σ u (u w) = v w
WLOG, we may assume ||a|| = 1, in which case the lemma reduces to showing S = v w < 1. By the Cauchy-Schwartz inequality, it suffices show ||l||| < 1. Toward this end, let us write v
U+ V_ where v4 = Eiu, a>a |u alu: Eisu, a> u and v_ Ei., a<o |u u,
Σ EiuJact u.u (-a). By Lemma we have ||u a/21| < 1/2 and ||l a/21 S 1/2, and so
||
||+ + V-
(62)
10+ a/2 v_ + a/2
(63)
||+ a/2 + || + a/2
(64)
1.
(65)
24

---

Also, if either of the index sets 4 := fi u a > 0) or I- := fi u a < 0} has cardinality greater than one then the lemma above guarantees ||0+ a/21l 1/2 10+ a/21 1/2, and so || 1, which gives 5 < 1.
It remains to show S < when + or T_ has cardinality less than equal one, i.e., |+ S 1 or 1-- S L. We consider the various possibilities:
Case 1: [4| = I- = Then a and so w 1.
Case 2: |+| 1 & |T_| 0 or |-| 0 & ||_| 1. Then |u; a/u; for some and |u3 al = 0 for all # i. By way of contradiction, assume that S = v w = |uu a a/u, w = 1. Since Wi a, and are all unit vectors, the only way this is possible is if | al = 1 and u,
which implies u and u, ws and so -- However, this shows that u. u, for all j + i, contradicting our assumption that u. u, < 0 for all i + j. Therefore,
this case as well.
Case 3: |4| = |-11= Then v = |u, a alu; + |u] a u, for some i 4 and j E L_, and so
| || I1|u a alu; + [ a/u,ll
(66)
= ||(uuu u, a
(67)
I ||uuu] uzu
(68)
where the last inequality follows by the fact that ||a|| 1. Finally, since the matrix u.u, uy u is symmetric, its operator norm l! u,u,7 || coincides with the maximum eigenvalue (in absolute value). Eigenvectors in the span of u, and u have the form v = c,u, + cj where Gi Cj satisfy the
equation
(u,u, u (or, + cyuy) X cyuz))
(69)
where À E F is the corresponding eigenvalue. Expanding and equating coefficients gives the system
1 A u U
u uj 1+
[
0
0
(70)
1
X
which has non-trivial solutions iff
(1 - A) + A) (u, uz)² 2== =0 = x =
(n. u,)
(71)
and so |a| < 1. Therefore, ||0|| S | - uuuu
1 as claimed. And so S < ||1||| < 1.
R
PaW
R2
W
W
R
Ry
Figure 6: Illustration of "unit splitting" technique used in proof of Theorem] If ReLU unit is active along two rays (left panel), it can be split into two units with lower representation cost by projecting its inner-layer weight vector onto the two rays separately (right panel).
Proof of Theorem Let f be any representation cost minimizer. We prove the claim by showing that if f fails to have the form specified (20) then is possible to construct a norm-ball interpolant h whose units aligned with the rays that has strictly smaller representation cost than f*.
25

---

be any minimal representative of f". By properties of minimal representatives, none of the ReLU boundary sets {y R un y by = 0} can intersect any of the norm-balls centered at the training samples, since otherwise f would be non-constant on one of the norm-balls. Also, we may alter this parameterization in such way that the active set of every unit avoids the ball centered at the origin Bo := ((0, p) without changing the representation cost. In particular, suppose the active set of the kth unit contains Bo. Then, using the identity [4+ = - - [-1++ for all E IR, we have
First, let f')
as(mn) y + bk]+ ( y + by)
y bk]+
for all y E Rd. The active set of the reversed unit - -al--w y byl+ does not intersect Bu- Therefore, after applying this transformation to all units whose active sets contain Bu, we can write S --- g" + where g" is sum of ReLU units whose active sets do not contain Bo and is an affine function that combines the original affine part Vy + with sum of linear units of the form as (w + by (2) arising from the transformation above. However, because of the interpolation constraint (Bo) = {0), and by the fact that no units in g" are active over Bg, for all y E Bo have
(z) 9" (y) E(y) ((y) 0
(72)
which implies L = O, i.e., (1) g²(y) for all y. Finally, note that the inner- and outer-layer weight vectors on the reversed units change only in sign. Therefore, this re-parameterization does not change the representation cost, and so is also a minimal representative.
Now construct new norm-ball interpolant h as follows. Let fi be the function defined as the sum of all units making up the re- re-parametrized f that are active on at least one norm-ball centered on the 9th ray. Also, let Pt- s RRdd denote the orthogonal projector onto the éth ray. Define = Ei= he where h2(y) := Pi (Py)). Put in words, h is constructed by "splitting" any units active over multiple rays into sum of multiple units aligned with each ray; see Figure 6 for an illustration.
First, we prove that h satisfies norm-ball interpolation constraints. Let a w y + b]+ denote any unit belonging to ft. Since this unit is active on a norm-ball centered on ray E, this implies that w us > O, and since the unit is inactive on Bo we must have 0. Also, because we assume u, um. < for any m * f, see that the projected unit P.affu w Pry + b)+ Pral(w T ug)u. y +b+ is active on norm-balls centered on ray l and inactive on norm-balls centered on any other ray. In particular, if belongs to norm-bail ball centered ray then hm (y) 0 for all m o f. Therefore, if y E B(x p)
where In denotes a training sample along ray l, then
h(y) Σ Ehm(v) hm)
(73)
ho(y)
(74)
Pefe(P:y)
(75)
P.f(Pry)
(76)
-P
(77)
= x
(78)
which shows that h satisfies nolm-ball interpolation constraints, as claimed.
Next, we show that if h # f³, then h has strictly smaller representation cost. Let u(y)
al alw + bj. denote any ReLU unit belonging to f", Since we assume ||/]|| = 1, the contribution of unit u to the representation cost of f* is ||]]. . Let R C {1, 2,., L} index the subset of rays for which unit is active over at least one norm-bal ball centered that ray. In constructing the interpolant h, the unit u get mapped to a sum of R units:
Σ Pia((PwW) T y + b]+
EER
whose contribution to the representation cost of h is bounded above by
C
Σ |Pall]]
Σ |uo allu? w/.
26

---

(a) Training samples along rays
(b) Perturbed training samples
Figure 7: Change in unit alignment of minimal representation cost solutions under perturbations of training samples belonging to rays. The red lines represent the ReLU boundaries of the representation cost minimizing solution satisfying norm-ball interpolation constraints. For the unperturbed samples in (a), all ReLU boundaries align perpendicular to the rays. For the perturbed samples in (b), the ReLU boundaries align perpendicular to the line segments connecting successive samples.
If [R] > 1, then by Lemma guarantees C' < ||a]]. And if R = then C'= |u, a a w & ||all. with strict inequality unless w, belong to the span of ug. This implies that any min-cost solution must have all its units aligned with the rays, i.e., f must have the form (1) = E/= (u, y). where each dy is a univariate function. The representation cost of any function f in this form is the sum of the (1-D) representation costs of the Φe. Therefore, Φe must also be the I-D min-cost solution of the norm-ball constraints projected onto ray f, and so must have the form specified by (I7).
C.2.1 Perturbations of samples along rays
As an extension of the above setting, suppose the training samples along rays (2) have been slightly perturbed, i... consider training samples a!!) (5) + +cl for some vectors el with ||c!0) < 8 for some sufficiently small > In particular, we make the following two assumptions:
(A1) Let A. = ( =/12, -n-1)
N be the collection of difference vectors between successive
perturbed points along the fth ray (with x 0). Assume that for all U2 Ae and for all Uk A with k * L, we have v 22 0.
(A2) If is any halfspace not containing the origin that contains the ball B(xh p). then H also contains all successive balls along that ray, i.e., H contains B( (2) p) for m
(2) belong to rays that satisfy the conditions of Theorem then for Note that if the original points o: sufficiently small 5 the perturbed samples x!!) will satisfy assumptions (A1) (AA))(A) above.
We show in this case the norm-bal ball interpolating representation cost minimizer is a perturbed version of the min-cost solution for the unperturbed samples identified in Theorem 3 In particular, the ReLU boundarics align with the line segments connecting successive points along the rays. See Figure 7 for illustration in the case of L rays.
Proposition 3. Suppose the training samples X a perturbation data belong to union of rays plus a sample at the origin, i.e., X = {0} (Tn 1 m= U...UU.U .. @@a Jn= where ((() = ( u: +
(n)
for some unit vector ue constants 0 < c( C2 <... C and vectors (2) Assume (AI)&
(8)
(E)
above hold. Then the minimizer f of (19) is unique and is given by
(0) Σ
(
(79)
27

---

where (2)
2 - and On (t) sn (lt an!
(1)
1t -t
with on p. ((()
2 "
(0) (1) [ E 1--11 - P. and 5n = En E / (19) On (0)
(8)
(E)
(E)
Proof. Let f be any min-cost solution. Following the same steps as in the proof of Theorem 3 there a minimal representative of f having the form (z) = En ag (ung y + bb]+ where the active sets of all units in this representation have empty intersection with the ball p),
Let S% denote the sum of all units in f whose active set boundary {y R w y by - 0} intersects the line segment connecting the training samples x((e) and ( By assumption (A2), this equivalent to the sum of units that are active over balls B@ p) for m 2 n, and inactive for the balls with m n., In particular, for y E B( .p), we have (z) Emmn fm (y). This implies
(2) x00) for all y E B(Z p), and so on, such that for all n I,... N₂ we have f/a (y) In x n- for all E B( :p).
S ( (y) T. for all y B(x P)). Likewise, f/( ( (y) 222
(0)
interpolating function h having representation cost less than and define P un (6) )uhh)) T, the orthogonal projector onto the span of the difference vector Fh
Now show how construct
equal f Let uh (4) #14) [0
Note that the map y P (z) is projection onto the affine line connecting samples T n-1 and Fn Consider the function
L
h
where
( ( S y
Put in words, h is constructed by aligning all inner-layer and outer-layer weights of units in f* with the line segment connecting successive data points over which that unit first activates. See Figure for illustration.
f=
h == h1 + h2
B
S2
S
((X) X1
hy Xi
B
((x) kg
Align units
B₁
Ay(1)
S
S
4, = 4,0)) =
fG x AG) 0
Ay 0
0
46) = PPA(Pp))
f
Figure 8: Illustration of "unit alignment" technique used in the proof of Proposition 3 The left panel shows an interpolant f whose ReLU boundaries (shown here as dark blue and dark red lines) are not aligned with the line segments S₁ and S₂ connecting successive training samples. The right panel shows how a new interpolant h can be constructed by projecting units in f onto the line segments S and S2, which reduces the representation cost.
Now show that h satisfies norm-ball interpolation constraints. By assumption (A1), the function (0) non-zero only on the norm-ball balls B(a(() .p) for m 2 n. This implies that for all y E B(*("),
have h(y) Emsa h (z))
Observe that h (( p)) = (0) since all functions (0) are zero on B(0, p). Also, for all y
((x(((); () we have p(d y E B(=((); : p). and so
h(y) h (y) P 10 (P 4) = P (0 x1
28

---

Similarly, the only terms in h active for y E B ; p) are h and (2) for which h ()) =n m/
(1)
and h (1) = P!! 5/ (0) y + (0)) = P2 (x)) x1 = 2 a This gives
h(y) h (v) 10 (v) m!
Iterating this procedure for all n ,,., N₂ we see that if y E B(xh .p) then (y) =x(
(1()) and so hyy) = Emga hm (y) In claimed.
Following steps similar to the proof of Theorem 3 we can show that R(h) R(f*) and with strict inequality if h # ft. First, if any unit u (y)
a w + b]+ in f is active over balls centered on
multiple rays R 21. then in the construction of h the unit u gets mapped sum of multiple units:
Σ FR
u (u "aw"" (u!! (y x bl+
for some ne with 1 S ne S N₂. The contribution of the sum of these units the representation cost of h is less than or equal to C= E(ER Tal(uu??))) ww By assumption (A1), we know for all p & l and for all m, n. Therefore, by Lemma we know < ||a]]. This shows f cannot have any units active over balls centered on different rays, since otherwise h has strictly smaller representation cost. Therefore, we have shown f as f = Σí= Σn f( Additionally, we see that h = f i.e., all inner- and outer-layer weight vectors of units in f/ are aligned with u!! since otherwise the representation cost of f could be reduced. Therefore, TT y). Minimizing the wil separately under interpolation constraints, we arrive at the unique solution given in (79).
(ul)) uu
each fú must have the form f (y) = un (6) w/ ((um))
C.3 Simplex Data
C.3.1 Simplex with one obtuse vertex
Proof of Proposition Consider training samples 21, 22,..., EN IRd whose convex hull is (N 1)-simplex such that #1 makes an obtuse angle with all other vertices, i.e., (xx, - -2)) T 21 <
for all n 2. .... N. By Lemma [5] f is norm-ball interpolating min-cost solution if and only if (x(y) f xx) 2 is norm-ball interpolating min-cost solution for the translated points 0 Ii..... IN I1 Rdd The latter configuration satisfies the hypotheses of Theorem 3 with single training sample per ray. Therefore, the min-cos, solution g of the translated points has units whose inner- and luter-layer weight vetors are aligned with In 3τ. n ..., N, and likewise for f³, since it is translation of g"
C.3.2 Simplex with all acute vertices
Justification of Conjecture / For concreteness we focus on the case three points I 22 Dg E Rd whose convex hull is an acute triangle, and let B1, B2, B3 be open balls of radius p centered 3,, 22, 23 (respectively).
Let be any norm-ball interpolating min-cost solution, and let f(y) Ex ax(w] y + bu] V t be any minimal representative of f.
First, by properties of minimal representatives, none of the ReLU boundary sets H = { E Rd we + by = 0} intersect any of the balls centered at the training samples. Also, the active set of each unit must contain either one or two norm-balls, since otherwise the unit either inactive over all balls or active over all balls, in which cases the unit can be removed or absorbed into unregularized linear part while strictly reducing the representation cost. By "reversing units", as in the proof of Theorem 3 we may transform the parameterization in such a way that the active set of every unit contains exactly one ball, and do this without changing the representation cost.
After this transformation, we may write
f ==
fi
f2 fz +
29

---

where fo is sum of units active only on the ball B; and no others, and where l(y) = Ay - b is an affine function. Then we have
Vy E Bi,
f(y fi + Ay + b 11
(80)
Vyz E B2,
f = f2( + Aye + b = 22
(81)
Vys E B3,
f(ys) fa(Us) + Ays + b 33
(82)
and so,
Vyi B1, fi(y1) #1 b Ay
(83)
Vyz E B2, f2( = 22 - b Ay
(84)
Vya B3,
fa(ys) 33 b Ay3
(85)
Finding the min-cost solution then amounts to minimizing of the representation cost of fi, f2. fs subject the above constraints. This is made challenging by the fact that the constraints coupled together by the parameters and of the affine part. However, under the assumption A= 0, we prove below that the min-cost solution must have the conjectured form f given (86). However, since we cannot priori assume A = O, this does not constitute full proof.
Before proceeding, give lemma that will be used to lower bound R(f) (assuming A 0).
Lemma 10. Suppose g is sum of ReLU units such that = 0 on closed convex region C' C RRd and g is constant and equal to on a closed ball C Rd. and g has minimal representative where all its units are active on B. Then
2|
R(g) 2 disr B, C)
where dist(B, C) millyB, 1y 1 æ||.
Proof. Let g >x a& [ y + bx]+ be a minimal representative where each unit is active on B. For to be constant on B it must be the case that Σx a = 0. Let = Yo be any value for which [lāg(g)) (gy)) |, the operator norm of the Jacobian of g. is maximized. Since g is piecewise linear, we see that its Lipschitz constant Lip(g) = [[0g(yo)]l Let Lo be the set of indices of active units at yo so that 0g (yo) = E a& and let I, be the complementary index set. Then because Σn awwo = 0, ΣKEL, a& ||. Therefore,
we have Eker, w EkEr, a. and ExE a
Lip((g 21(0g( 2
Σ a w kelo
Σ w. kelo
+
Σ a w
kel:
a w = R(g).
Finally,
(g g(x)l ly 2
|c|
|cl
Lip(g)
max DEC
yyy
dist dist(B, C)
Combining this with the previous inequality gives the claim.
Now, returning the proof of the main claim, for n 1, 2, 3, let C, be the closed convex region given by the intersection of all closed half- half-planes containing the balls B, and Bg. a n and k o j * By assumption, fa vanishes on Cn and fa is constant and equal x, the closed ball B,, So, by Lemma 10, we see that
21( bl
R(Fn)
2
8n
where 6, dist(Bn, On). Therefore, for all b dd we have
3
2 In
bl
R(J) R(f))+ R(f)) + R(fa) N
8
30

---

Let E E R be the minimizer of
2 n bll
min BER
8n
Then plugging in b above, have the lower bound
2 n2 x
R(f)
on
which is independent of b.
Finally, simple calculations show that the conjectured min-cost solution f specified in (86) has representation cost achieving this lower bound. Therefore, under the assumption A 0, is min-cost solution.
Now we prove that, in the special case where the convex hull of the training points is an equilateral triangle, the norm-ball interpolator f* identified in Conjecture [ min-cost solution (though not necessarily the unique min-cost solution). In this case, we may also give f a more explicit form, as detailed below.
Proposition 4. Suppose the convex hull of the training points $2, 33 E IR is equilateral triangle. Assume the norm-balls B, == (1: p) centered at each training point have radius << I,, -xull/ (2, 1,2,3. where 2o 3 (x1 + x2 + xx) is the centroid of the triangle. Then minimizer f of (19) is given by
(2) u1 (u] (y- x0)) + u2 (y xo)) + uudaa (ug (y) xx0) + xo.
(86)
where (t) = sn((t ([t anl+ - It bnl+) with un = 2. -o
- an = =b1 xo ll + p. bn =
| woll p. and || -woll/(0 (bn -a,)
Proof. By translation and scale invariance of min-cost solutions, without loss of generality we may assume 1 22 33 E Rd are unit-norm vectors and mean-zero (i.e., the triangle centroid æ0 = 0). In this case, the assumption on P translates to p < 1/2. Additionally, it suffices to prove the claim in the case 2. This because, if 11, 22 3y E Rd are the vertices of an equilateral triangle whose centroid is the origin, then these points
contained in two-dimensional subspace S C IR. And we let P E R2x2 be a matrix whose columns are an orthonormal basis for S, then by Theorem 2 f min-cost solution if and only if fyy f PTP y). where fo IR22 IR2 is min-cost solution under the constraints [BP Zn, P)) = {P En for all 1, 3. Therefore, the problem reduces to finding a min-cos cost solution of the projected points PT PT PT xz PT convex hull is an equilateral triangle in IR2..
PTx D3 E RR² whose
So now let f 2R2 + R be any min-cost solution under the assumption #1, 22 2z E TR2 are unit-norm, have zero mean, and p < 1/2. By reversing units as necessary, there exists a minimal representative of f that can be put in the form f(y) = fzy + fz(y) + fa(y) + Ay + c, such that (x) is a sum of ReLU units, all of which are active on B,, and all of which are inactive on B, for j * n.
Let Q be the reflection matrix Q 2x x T I, which reflects points across the line spanned by æ1- In particular, y E B₁ then Qy E B₁ while if E Bg then Qy E By (and vice versa). Also, Qæi 21, Q 23, and Q Ø2. Define g(y) 2 (f Q- ((q)). Then it is easy check that g satisfies interpolation constraints, and since Q is unitary, we have R(g) < R(f). Furthermore, since f is a min-cost solution, we must have R(g) R(f). Additionally, since none of the units making up f are active over more than one ball, neither are the units making up which implies no pair of units belonging to g combine to form affine function. Therefore,
f {[f)++ + (.-(R(()) f Q-))===) = +
may write g = g1 (y) 92(U) + 9x + By + v. where B = A + Q AQ, such that each gn is a sum of ReLU units, all of which are active on B,, and all of which are inactive on Bj for j
Let U a rotation matrix by 120 degrees such that æa Un, as = Ur, and a. = U2g Consider the symmetrized version of g given by h(y) = (g(v) + ((U) - -
31

---

Since for all y E Bn we have Uy E Ba+1 (with indices understood modulo 3). it is easy to verify that h satisfies interpolation constraints. Also, since U is unitary, we have R(h) I R(g) S R(f). which implies R(h)= R(f) since f is a min-cost solution. Again, since none of the units making up g are active over more than one ball, neither are the units making up h, which implies no pair of units belonging to h combine to form an affine function. And so, we may write h(y)
h (y) + (3)) + h3 + C + u, such that each ft is sum of ReLU units, all of which are active on B.. and all of which are inactive on B3 for + n.
Observe that u -
+ )0 = 0. Also, we have C =
3 (B -U-
This implies C' commutes with U, because it is easy to see that C = U- Additionally, C commutes with Q. because it easy to see B Q BQ, and by properties of rotations/reflections we have UQ= QU-!, which implies
1 1
Q c'cQQ
BQ + QUQ+QUUUUQQQUUQ U QU
3
1
Q 1U00-~00U-UUUQQ00000-00000
1 1 (UQ
3
1 BUBUQQQQQUI BQQ +UQ BUQU
Q BQ+ UU BQU B
1 [ + UBU U 3)
[B U 2 BU + UU BU)
3
= =C
which shows C' commutes with Q. Now we show that any matrix C' that commutes with both U and Q is a scaled identity matrix. Let wं denote a unit-vector perpendicular to I such that {01 3 form an orthonormal basis for R22 First, we know Q has eigenvectors æ; and at with eigenvalues 1 and 11, respectively. And so QC21
Cx1, while QC2t CQ=t which implies Cz. aæ and Cat = baT for some a, b E IR, i.e., and o are eigenvectors of C with eigenvalues a and b, respectively. Furthermore, we have CUx; UC2; = aU and CU*+ UC*1 = W0Z. This implies Ux, and Un are also eigenvectors of C' with eigenvalues a and b, respectively. But since +1 and V are linearly independent, and likewise so are aT and Uz the only way this could be true is if a b, i... every vector in 8² is an eigenvector of C for the same eigenvalue E R which implies = >I for some À E IR.
CQ==
-Cx1
Figure 9: Ilussrattoon of ReLU boundaries (in red) of original interpolant f (left), the function g (middle) obtained by enforcing reflection symmetry, and the function h (right) obtained by enforcing both reflection and rotation symmetry.
Therefore, have shown that every min-cost solution f maps min-cost solution h of the form
h h1 + (22 + h2( + AI
32

---

for some À E R. where each h, is sum of ReLU units, all of which are active on B, and all of which are inactive on Bj. J # n. In particular, h,) I,, xy for all y E B, and h, (3) = 0 for all E On, where C₁ is the intersection of all half-planes containing the balls Bj, j # n.
This means
write hyy) Ex= axwwy y + bx]+ + AI and hm = EREA, ax m y
bal+ for some index sets A2, partitioning {1...., }} so that R(h) = Σx= ax Ex=1 ELEA, |as]|- ||- Let R-(-) denote the representation cost of function computed without an unregularized linear part, i.c., define Ro analogously to At except where the model class he in (6) constrained have V O. Then, since the realizations of the h functions considered above do
not have a linear part, see that ΣKEA,. ||xı|| (h,h,) and so R(h) > E | M Ro (h1) Ro Ro(h)).
Now we show how lower bound Ro (h.) for all n = 1, 1,2, 3. Let 2 denote a unit-vector perpendicular to In such that {I,,, x,, } form an orthonormal basis for R??. Consider the univariate functions h!ll (t) x; hr (xx,t) and hn (t) == (z,,) h., ( + xn,) Here A!! is the projection of h onto the line spanned by Øn. and hn is a projection onto the line perpendicular to En passing through the point Vn. In particular, by the constraints on hn, we see that ty and h1 satisfy the constraints
0 ift -122+p
(!((()
(87)
1 At ift> 1-p
and h1 (f) = At [t| S.
Claim 1: For all n = 1,2,3, Ro(hn) 2 Ro(h!!) + Ro(h))) Proof: Let hr (1) Ex as l y +
bu]+ + e be any realization of ha, whose representation cost is C Σx (1ax|12 - |/ 112). Then realizations of Ai!l and 1/t are given by
(1) = x, (x,tt) [(x az) wx)t + bkl+ + x.
(88)
h1 (t) = (o hn ( t T
xxn)= = [<((t)aa)(((tt)) Twok) wx)t + by + wo xnl+ + (2 c,
(89)
whose representation costs Cll and CL,, respectively, are given by
C Σ 2 [oe az)² 22 + (xx,, w)
(90)
b
c+ Σ (
T )2 2 + ((x+)) wx))))
(91)
and by the Pythagorean Theorem we see that C' = Cll + C+, Therefore, C² (o(l!!)) + (o and finally minimizing over all realizations of fnn gives the claim.
Claim 2: For all 1,2,3, (h!l))
1-
where 8 3-1- p and 112 p.
B-a
Proof: By results in Savarese et al. 2019
Ro
(P!ll) > Ro(r) where p(() is the function satisfying the
same constraints as hill given in (87) while linearly interpolating over the interval / E [a. 3 From
the formula Ro(p) = max [] Ip" (() di, Ip'
(xx) + +p'( [-)-o)) as established in Savarese et al. 2019
we can show directly that (p) 3-a
1-18
which gives the claimed bound.
Claim 3: For all 1,2,3, (h > [J].
Proof: The function q()) with minimal Ro-cost
satisfying the constraint (1) -A for -Ast + p|+ + Ap. which has Ro-cost l
14
S p is single ReLU unit plus a constant: q(1) =
33

---

Putting the above claims together, we see that
A
1 Aa
Ro (k,) 2
+
+ |
(92)
B
3 a
2 1(3 +a)
+ |
(93)
B a
(1(++a)
KI
(94)
B
2
20 |
(95)
3-a a
2
(96)
3 -a
a
where in the last inequality we used the fact that 3/2 - 2p > O. Therefore, R(f)= R(h)) Rhih)) Rh()2) Ro(ha)
2a > 0 since a = -1/2 + p < and 8 - a
Ø-a
Also, the function f" given by B-a
S = Si + f2 + S3
where
Tr |م y - a]+ - [xx y 3]+)
f1
3 -
satisfies norm-ball interpolation constraints and R(f*)
3-a 6.
Hence, f is con- solution.
34

---

D Additional simulations
We train a one-hidden-layer ReLU network without skip connection using the setting used in Figure As can be seen from Figure [0 we get similar result for the NN denoiser with and without the skip connection. Therefore Appendix D.I use ane-hidden-layer ReLU network without skip connection.
NN Denolser online
WN-Denolser offline
Online denoiser
Prediction
-2
-4
Noisy data
NN denoiser vs eMMSE denoiser. We trained lle-hidden-layer ReLU network on denoising task. The clean datasct has four points equally spaced in the interval [-5, 5], and the noisy samples are generated by adding zero-mean Gaussian noise with 1.5. use 10 in both setting. The figure shows the denoiser output as a function of its input for: (1) NN denoiser trained online using 7 for 100K iterations, (2) NN denoiser trained offline using with M 9000 and 20A epochs, and (3) the cMMSE denoiser 4
Figure 10:
D.I MNIST
We use the MNIST dataset to verify various properties. First, the offline and online solutions achieve approximately the same test MSE when trained a subset of the MNIST dataset (Figure [I]. Second, to show that the fact that NN denoiser does not converge to the eMMSE denoiser is not due approximation error (Figure [2). Lastly, to present the critical noise level which representation cost minimizer fip has strictly lower MSE than the eMMSE, for all smaller noise levels (Figure 13)
Online
0.8
Offline with M=100
Offline with M=10
MSC
0.6
0.4
0.2
2000
4000
6000
8000
10000
Iterations
Figure 11: Online setting vs offline setting for MNIST denoiser. We train a one-hidden layer ReL.U network subset of N 100 MNIST images for 10K iterations. We use Gaussian noise with zero mean and a = 0.1.
35

---

0.0070
0.0089
Test loss
0.0068
0.0067
0.0066
0.0065
10000 20000 30000 43000 50000 00000 70000 80000
Layer width
Figure 12: Test loss vs. layer width for MNIST denoiser. We train a one hidden layer ReLU network MNIST denoiser task using] 7 for 93K iterations with fixed learning rate. We Gaussian noise with zero mean and = 0.1. The figure shows the test loss vs. layer width.
0.7
0.5
0.4
0.3
0.1
eMNSE
0.0
Naise std Lo)
Figure 13: MSE vs. Noise std. We train a one-hidden layer ReLU network on subset of N 100 MNIST images (the range of each pixel is [0, 1J) for 10K iterations with fixed LR. We Gaussian noise with zero mean. The figure shows the MSE vs noise std (σ) for NN denoiser (orange line) and for eMMSE denoiser (blue line). Note that the eMMSE is dependent on a (4). For low noise levels, the eMMSE output is one of the training set images. For moderate noise levels, the eMMSE output is weighted sum of the training images. For high noise levels, the eMMSE output is the mean of the training set images.
D.2 Three non-colinear training samples
We show in Figures 14 and 15 that for N 3 training points from the MNIST dataset that forming triangle in d = 2 dimensions the empirical minimizer obtained using noisy samples and weight decay regularization agrees well with the form of the exact representation cost minimizer predicted by Proposition 2 and Conjecture
D.3 Empirical validation of the subspace assumption
We validated that the following image datasets are (approximately) low rank:
CIFAR10
CINIC10
Tiny ImageNet (a lower resolution version of ImageNet, enabling us to use SVD)
BSD denoising benchmark composed from 1600 patches of size 40XX cropped from 400 images [Zhang et al. 2017)
36

---

Theory:
-1
Direction
Direction
Figure 14: Function space view of a denoiser, trained for MNIST data points (Acute Angle). Here, compare empirical results (left) with our theoretical results (right). We compare the function-space view for inputs from the data plane, with respect to the model output in each of the data directions. For the empirical results, label, and under the condition that they form an acute triangle (64%, for this figure). We trained a single-layer FC ReLU network with linear residual connection for 1M epochs, with weight decay of 1E 8 (as described in our model), and ADAM optimizer with learning rate 1E - 5.
choose 3 random MNIST data points under the same
Table 1: We applied a Singular Value Decomposition (SVD) for each of the above datasets, and calculated the relative number of Singular Values (SV) needed to achieve given percentile of the energy (for the average vector).
Dataset
95%
99%
99.9%
CIFARIO
0.8%
7.5%
30%
CINICIO
1 1%
23%
41%
Tiny ImageNet
1.6%
20%
36%
BSD
0.1%
1.6%
4.5%
As can seen from Table Tal the datasets that we used are (approximately) low rank.
37

---

Theery-
Direction
Direction 1
-1-
23-
Figure 15: Function space view denoiser, trained for MNIST data points (Obtuse Angle). Here, we compare empirical results (left) with our theoretical results (right). We compare the function-space view for inputs from the data plane, with respect to the model output in each of the data directions. For the empirical results, we added single data point to the two previously chosen for Figure 14 under the condition that the three points form an obtuse triangle (95%, for this figure). We trained single-layer FC described in Figure 14 As predicted, the function we have converged to for data forming an obtuse triangle noticeably different form the function we converged to when the data was forming acute triangle.
38


Reviews:
[{"review_id": "JNRa5vsH0x", "reviewer": "Reviewer_4XGM", "summary": "This paper looks at the denoising problem and compares the neural network denoiser to what the paper calls the eMMSE denoiser. The eMMSE denoiser is the optimal denoiser (in function space) given finite data and known noise distribution. In contrast, the Neural Network denoiser has access to a finite number of copies of each of the finite data points and minimizes the empirical noise. \n\nThe paper shows that even in simple settings (univariate data), the minimum norm neural network denoiser has better generalization than the eMMSE denoiser, as it interpolates in between the data points whereas the eMMSE denoiser acts as a nearest neighbor denoiser. The paper further explores some other settings such as low rank and data on rays. \n\n", "questions": "1. The paper presents the network with a skip connection, but as far as I can tell, the skip connection version is not studied in the paper. As $R(f)$ (Definition 1, Equation 19) is without the skip connection. \n\n2. The denoiser in Corollary 1, what would be the neural network representation of that function with ReLU activation?\n\n3. The fact that the online denoiser and the offline are equivalent is interesting. Do you have any intuition as to why the offline captures the online phenomena despite having much fewer samples?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main strength of the paper is finding the explicit form of the minimum norm two-layer denoiser. This is interesting as it identifies the best point in function space that can be represented as a two-layer network. Hence gives the global minimizer for the neural network which is traditionally not easy. Hence this is important. \n\nOther strengths of the paper include that they show these denoisers are contracting and generalize better than some \"optimal\" denoisers. ", "weaknesses": "The are a few weaknesses of the paper. \n\n1) I think the presentation of the paper can be improved significantly. In many cases, the paper switches between functional representations of the function and the parametric representation of the function. While both are interesting, it would be nice to have to a clear distinction between the two and a way of translating from one representation to the other. \n\n2) While the results of the paper are interesting, there are limitations in the types of data that they consider. Specifically, univariate data, data on a line, and data on the union of lines are the cases in which the paper can identify the min norm solutions. While these cases are interesting and I understand that more general cases are challenging. Hence I don't think it is needed to solve more general cases. However, if the paper could extract some insights from these theoretical cases that might apply to more general cases, this would help strengthen the paper. \n\n3) I think the related works section is missing various theoretical works on denoising. [A-D] look at denoising via factorizations which fit in nicely with the low-rank structure that the paper looks at, and [E] looks at denoising regression case. \n\n\n[A] Raj R. Nadakuditi. OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage. IEEE Transactions on Information Theory, 2014\n\n[B] Marc Lelarge and Léo Miolane. Fundamental Limits of Symmetric Low-Rank Matrix Estimation. In Proceedings of the 2017 Conference on Learning Theory, 2017 \n\n[C] Antoine Maillard, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Perturbative Construction of Mean-Field Equations in Extensive-Rank Matrix Factorization and Denoising. Journal of Statistical Mechanics: Theory and Experiment, 2022 \n\n[D] Emanuele Troiani, Vittorio Erba, Florent Krzakala, Antoine Maillard, and Lenka Zdeborov’a. Optimal Denoising of Rotationally Invariant Rectangular Matrices. ArXiv, abs/2203.07752, 2022\n\n[E] Rishi Sonthalia and Raj Rao Nadakuditi. Training data size induced double descent for denoising feedforward neural networks and the role of training noise. Transactions on Machine Learning Research, 2023\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__Response to the weaknesses points:__\n\n__C: (1)__ the paper switches between functional representations and the parametric representation\n\n__R:__ We are not sure what is the source of the confusion. For parametric representation we only use $h_{\\theta}$, as defined in Equation 6 in Section 2. For function space representation only use $f$, as defined in Definition 1 in Section 3 (and we focus on $f$ from that point onwards). This was also the standard notation in previous works (e.g. Savarese et al.). \n\n__C: (2)__ insights from the theoretical results which apply to a general case\n\n__R:__ We generalized Proposition 2 to the case of obtuse Simplex (See the “global” response), and this provides an explicit solution to a high-dimensional case. We believe that this result will facilitate deriving generalization guarantees of NN denoisers. One interesting insight we deduce from our results on the obtuse simplex is that the NN denoiser (in this case) is bounded, which is a desired property for a denoiser. \n\n__C:__ (3) The related works section is missing various theoretical works on denoising\n\n__R:__ The papers [A]-[D] indeed also consider the denoising problem with a low-rank prior on the signal, but mostly focus on optimal MMSE denoising, and do not consider neural networks. Our main focus is the structural properties of neural network denoisers because this sheds light on their generalization properties. As denoising is a very large topic, we have simply referred the reader to general surveys on the denoising problem (e.g., the one by Elad et al. 2023) in order to keep the paper focused. The paper [E] is indeed relevant to neural networks, and we will add a discussion on the results obtained in this paper on the double-descent phenomenon in a rank-1 denoising setup in the revised version. \n\n\n__Answers to the questions:__\n\n__C: (1)__ The skip connection version is not studied in the paper\n\n__R:__ There appears to be some misunderstanding. As stated in Definition 1, the representation cost is defined for $h_{\\theta}$ as defined in Equation 6, which is a shallow ReLU network __with a skip connection__. All later results find minimizers of $R(f)$ as defined in Definition 1, and therefore also assume shallow ReLU networks with a skip connection. \n\n__C: (2)__  What is the neural network representation of the denoiser in Corollary 1?\n\n__R:__ Suppose the collinear points $x_n = c_n u$  are ordered such that $c_1 < c_2 < … < c_N$. Then a neural network representation of the denoiser in Corollary 1 is:\n\n$f^*(y) = \\sum_{n=1}^{N-1} a_n u ([u^T y - (c_n + \\rho)]\\_+ - [u^T y - (c_{n+1} - \\rho)]\\_+)$\n\nwhere \n\n$a_n = (c_{n+1}-c_n)/(c_{n+1}-c_n-2\\rho)$ and $\\rho$ is the radius of the norm-ball constraints (i.e., we assume the denoiser maps every point in the ball of radius $\\rho$ centered at $x_n$ to the point $x_n$). \n\n__C: (3)__  An intuition as to why the offline captures the online?\n\n__R:__ On an intuitive level, the cause is the exponential tail of the Gaussian distribution. Given that the number of noisy samples per image in the offline setting is large enough, we need exponentially more noisy samples per image in the online setting in order to get a different solution.\n"}, {"review_id": "f95yWudX4j", "reviewer": "Reviewer_qSF7", "summary": "The elementary properties of NN solutions for the denoising problem have been explored, with a focus on offline training of a one hidden-layer ReLU network. When the noisy clusters of the data samples are well-separated, there exist multiple networks with zero loss, even in the case of under-parameterization, while having a different representation cost.  In the univariate case, a closed-form solution to such global minima with minimum representation cost has been derived. It has also been demonstrated that the univariate NN solution generalizes better than the eMMSE denoiser. In the multivariate case, it has been shown that the interpolating solution with minimal representation cost is aligned with the edges and/or faces connecting the clean data points in several basic cases.", "questions": "Please see and address the weaknesses. ", "limitations": "I think the authors have well discussed the limitations. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The NN solutions is studied in the setting of interpolation of noisy samples with minimal representation cost, in a practically relevant “low noise regime” where the noisy samples are well clustered. \n\nIn the univariate case, a closed-form solution for the minimal representation cost NN denoiser is derived and shown to have better generalizition behavior than the empirical minimum MSE  denoiser. \n\nIn the multivariate case, a closed-form solution for the minimal representation cost NN denoiser in multivariate case under various assumptions on the geometric configuration of the clean training samples. Moreover,  a general alignment phenomenon of minimal representation cost NN denoisers is illustrated in the multivariate setting. ", "weaknesses": "Weakness 1: Empirical effectiveness.  This paper proposes a shallow denoiser and analyizes its theoretical performance. \n\nW1.1 Despite the interesting theoretical properties of the shallow denoiser, it is not clear whether the proposed model performs well in real image denoising applications due to the lack of sufficient empirical evaluation and analysis. \n\nW1.2 In the multi-variate settings, the authors consider training data on a subspace. However, it is not clarified in which typical settings this subspace assumption holds. Thus, the empirical reasonability of the subspace-based analysis is not well addressed. \n\nWeakness 2: The theoretical findings may be not sufficiently new. For example, the NN solution is shown contractive towards the clean data points, which has already been empirically observed in Autoencoders by Radhakrishnan et al.  [2018]. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__Response to the weaknesses points:__\n\n__Weakness 1.1:__\n\n__C:__  Is the proposed model perform well in real image-denoising applications?\n\n__R:__ Practically successful image-denoising architectures are deep and not fully connected. On such architectures, it is very challenging to obtain any theoretical guarantee without very strong assumptions (e.g. working in a linearized regime, such as the neural tangent kernel), especially before understanding simpler architectures. Therefore, deep learning theory papers researching a new question usually start with the simplest relevant model, as we do here. Specifically, in this paper, we have focused on a shallow NN denoiser, which is both simple enough to start a theoretical inquiry, yet rich enough to provide insightful conclusions about modern denoisers architectures. \n\nOne such insight that we proved is that the minimizer is contractive towards the training points (for univariate data). This is akin to phenomenons shown empirically in diverse settings (multilayer Auto-Encoders, CNNs, and FCNs [C]). It is an interesting future research topic to empirically verify that practical image denoisers are also locally contractive toward the training points (Please see our answer to Weakness 2 for an additional explanation regarding the novelty of this result).\n\nAnother interesting insight is that the NN denoiser is bounded, which is a desired property for a denoiser. This property hold in all our results, and also in the generalized Proposition 2 to the case of obtuse Simplex (See the “global” response), which provides an explicit solution to a high-dimensional case. \n\n\n__Weakness 1.2:__ \n\n__C:__  In which typical settings this subspace assumption holds?\n\n__R:__ In general, natural images are commonly assumed to lie on a low-dimensional nonlinear manifold [A]. There are several applications where the images are assumed to lie on a subspace (linear manifold). For example, in face recognition and handwritten digits, classical algorithms use PCA and achieve good results, which indicates that the data lies on a linear subspace. \n\n__Weakness 2:__ \n\n__C:__ The NN solution is shown contractive towards the clean data points, which has already been empirically observed in Autoencoders.\n\n__R:__ Our results differ from [B] in the following: \n\n* [B] focused on __empirically__ showing contractivity, while we __proved__ it. We believe there is value in proving important empirical observations, especially in deep learning, where the lack of established theory is a well-recognized problem.\n\n* [B] also proved that 2-layer auto-encoder models are contractive, but under rather __unrealistic__ assumptions: (1) the weights of the input layer are fixed and (2) the number of neurons goes to infinity. In contrast, in our theoretical results in the univariate case, the minimizer of the representation cost is contractive towards the training samples without these assumptions (i.e., the minimizer optimizes over both layers and has a finite number of neurons).\n\n* [B] used a weaker definition of contraction. Specifically, [B] only showed __local__ contraction, based on the eigenvalues of the Jacobian (linearization of a dynamical system). In contrast, we show __global__ contraction towards the training samples (the word “locally” in definition 2 in the submitted paper is a typo).\n\n* [B] examined auto-encoder models, while we examine denoisers models (i.e., auto-encoders trained with noisy inputs).\n\nWe will clarify this in the revised paper. \n\nIn addition, we have several new theoretical findings. For example,\n \n* we prove Generalization results for the univariate case (better generalization than the eMMSE).\n\n* A closed-form solution for the minimizer of the representation cost __in the multivariate case__. As far as we know, there are no such results in the literature, even for networks having scalar outputs.\n\n[A] Pope, P., Zhu, C., Abdelkader, A., Goldblum, M. and Goldstein, T., 2021. The intrinsic dimension of images and its impact on learning.\n\n[B] Radhakrishnan, A., Yang, K., Belkin, M. and Uhler, C., 2018. Memorization in overparameterized autoencoders.\n"}, {"review_id": "BD50b2X8LS", "reviewer": "Reviewer_kiMs", "summary": "This paper studies how two-layer ReLU denoising networks look like when minimizing common losses such as the empirical minimum mean square error, an empirical alternative that draws finitely many noisy samples, as well as representation costs that find the data interpolating function with minimal norm of the weights. It is proven that - for univariate data - representation cost minimizers generalize better than empirical minimum mean square error minimizers in the low noise regime. Moreover, the solution to the representation costs is explicitly stated in the univariate case as well as in the multivariate case for specific geometric configurations, including one conjecture. Small numerical experiments illustrate that theory is correct and the conjecture is justified. ", "questions": "- Please clarify in what way your work extends previous characterizations of minimal representation cost solutions.\n- And just out of curiosity - if \"Savarese et al. [2019] showed that the representation cost of a function realizable as a univariate two-layer ReLU network coincides with the L1-norm of the second derivative of the function\" (and assuming that the second derivative of a ReLU network has some meaning like the total variation of the (step-function-like) first derivative), doesn't proposition 1 follow from this quite directly? ", "limitations": "The authors have addressed the limitations well. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and easy to follow despite its theoretical nature\n- It characterizes several interesting and important properties of shallow denoising networks in the low-noise regime for univariate data.\n- It gives inspiring insights on the behavior in the multivariate case (under particular assumptions). \n- It encourages further research in the investigated direction by posting one (partially open) conjecture, as well as by accurately stating several limitations (tight to very interesting directions of future research). \n- It contributes to our understanding of denoisers in function space", "weaknesses": "I am not familiar enough with the explicit characterization of networks that minimize representation costs to judge the novelty and impact of the contribution. I was a little surprised to read \"Hanin [2021] gave a full characterization of univariate representation cost minimizers subject to data interpolation constraints\", and that there are follow-up extensions, which seem very relevant to the paper at hand. \n\nBeyond this, except for the limitations that have already been stated by the authors themselves, I do not see any major weaknesses. In practical terms, I am now curious to what extent larger (deeper + more sophisticated, e.g. convolutional or normalization including) models inherit some of the shown properties, but can understand that this goes beyond the scope of the paper. Also, is the M<<d problem discussed in line 333 a reason why adversarial examples exist? The strict interpolation on a ball would prevent them. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__Response to the weaknesses points:__\n\n__C:__ Do larger models inherit some of the shown properties?\n\n__R:__ There are several properties that we hypothesize to hold for larger models (but it goes beyond the scope of this paper). (1) We generalized Proposition 2 to the case of obtuse Simplex (See the “global” response). An interesting insight we deduce from our results on the obtuse simplex is that the NN denoiser (in this case) is bounded, which is a desired property for a denoiser. We hypothesize it is also true for larger models. (2) We proved that the minimizer is contractive towards the training points (for univariate data). This is akin to phenomenons shown empirically in diverse settings (multilayer Auto-Encoders, CNNs, and FCNs [A]). We hypothesize that larger models are locally contractive towards the training points.\n\n[A] Radhakrishnan, A., Yang, K., Belkin, M. and Uhler, C., 2018. Memorization in overparameterized autoencoders.\n\n__C:__ is the M<<d problem discussed in line 333 a reason why adversarial examples exist?\n\n__R:__ It is an interesting point. You are right, if the denoiser output is constant and equal to $x_n$ on a ball of radius $\\rho$ around $x_n$, then the adversarial would be prevented altogether. It is an interesting future research topic to empirically verify if NN denoisers are more robust to adversarial attacks when we increase the number of noisy samples per image. \n\n__Answers to the questions:__\n\n__C:__ Please clarify in what way your work extends previous characterizations of minimal representation cost solutions.\n\n__R:__ For univariate data, the characterization in Hanin [2021] is possible because the representation cost reduces to the L1-norm of the 2nd derivative of the function, as shown in Savarese et al. [2019]. Since the 2nd derivative only acts locally, the minimum representation cost can be found by minimizing this quantity separately over intervals between data points. In the multivariate setting, the representation cost is more complicated, and involves the Radon transform of the function – a highly non-local operation – that complicates the analysis. Parhi and Nowak [2020] prove a representer theorem showing that there always exists a minimum representation cost interpolant realizable as a shallow ReLU network with finitely many neurons, and Ergen and Pilanci [2021] give an implicit characterization of representation cost minimizers as the solution to a convex optimization problem. However, to the best of our knowledge, there are no results in the literature explicitly characterizing representation cost minimizers in the case of multivariate inputs, even for networks having scalar outputs. Therefore, for this paper we had to develop new tools and approximations. To simplify the problem, we assume norm-ball interpolation constraints (Equation (19) in the paper), in place of finite noisy realizations. This type of approximation is novel, and allows us to give explicit characterizations of representation cost minimizers under specific geometric assumptions on the training points. Thank you for your comment, we will add this discussion to the revised paper.\n\n__C:__ Doesn't proposition 1 follow from Savarese et al. [2019] directly?\n\n__R:__ Savarese et al. [2019] considered the case of shallow ReLU networks with an unbounded number of neurons. In Proposition 1 we found an explicit form to the minimizer of the representation cost with a __finite__ amount of neurons. In addition, Savarese et al. [2019] consider the case of one hidden layer ReLU network __without__ a skip connection. Lastly, in the case of denoising, Hanin’s [2021] result guarantees a unique minimizer for the representation cost.\n"}, {"review_id": "QfoSYtK2PT", "reviewer": "Reviewer_7Tj7", "summary": "The paper studies the shape and properties of one layer networks on a denoising problem. Specifically, the authors compute a closed-form solution for a NN trained offline with regularization and show that its ability to generalize is better than the eMMSE estimator -- which acts as a piece-wise constant function -- in a low-noise regime and in 1d. Then they provide results on multivariate cases where the training data points are contained in a lower dimensional subspace, showing that the image of the network is also contained in the subspace, and deriving closed-forms for specific cases where the data are aligned.", "questions": "* Could the authors illustrate what happens in practice (in 1d or in higher dimension) when the noise level increases ? In particular, do we still have a gain using a NN rather than the eMMSE ?\n\n* Is it possible to give bounds on $\\sigma$ for which theorem 1 is valid ? Otherwise, could the authors provide MSE curves highlighting the difference between NN and eMMSE depending on $\\sigma$ (in the case where the noisy samples support are disjoint and in the general case) ?", "limitations": "The limitations are addressed by the authors. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Regarding the presentation, the paper is clearly written and each theoretical result is well-explained, making the reading easier. Regarding the content, the theorems seem new and provide interesting insights on the behavior of simple networks on the denoising problem. The authors provide a complete study of the univariate case when the noise level is reasonable, and give insights on what happens in higher dimensions. Numerical illustrations support the theoretical claims.", "weaknesses": "The study is limited to low noise levels (noisy samples supports can't intersect), and it would have been interesting to have the authors opinion on whether removing assumption 1 change or not the behavior shown in figure 1 (theoretical development or even empirical illustrations). In particular, theorem 1 is valid in the limit when $\\sigma \\to 0$, while we would have preferred a \"threshold\" (as the authors mention, there exists a threshold for the strict inequality but it is potentially very small).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__Answers to the questions:__\n\n__C:__  What happens in practice when the noise level increases?\n\n__R:__ Please see Figure 1 (in the pdf file attached to the 'global' rebuttal) for the MSE of NN denoiser and eMMSE vs $\\sigma$ (the noise level). As can be seen from Figure 1, the NN denoiser performs better for noise levels in which we still have visible information in the noisy image.  \n\n__C:__ Is it possible to give bounds on which theorem 1 is valid?\n\n__R:__ Given the probability density function of x (the clean image) we can calculate the critical noise level for which Theorem 1 holds. The critical noise level can change significantly depending on the probability density function of x. For example, if the probability density function has high “mass” in between the training points then the critical noise level is large. However, if the density function has low “mass” between the training points the critical noise level is small.\nPlease see Figure 1 (in the PDF file) for the MSE curves. As can be seen the critical noise level in this case is large ($\\sigma$ ~ 5).\n"}]

Author rebuttal:
We thank the reviewers for the helpful feedback and remarks, and for your interest in the paper. We have addressed all of them, and we will revise the paper, ‌as detailed below. The rebuttal is in comment-response (C/R) format.

Also, ‌after the initial submission we have strengthened some of our results:

1) In Theorem 3, we have removed the restriction $L \le 3$. In other words, we generalized it to an arbitrary number of $L$ rays making obtuse angles with each other. 

2) Using the above result, we generalized Proposition 2 to the case of an obtuse simplex (i.e. one point in the training data that forms an obtuse angle with all other points).

3) We proved Conjecture 1 in the special case that the training set forms an equilateral triangle. 

We believe these results will further strengthen the paper, and therefore plan to add them to the final version (unless there is any objection).


Meta-review: The paper studies the structure of neural network denoisers. It provides closed form solutions for optimal neural network denoisers in two settings (i) for univariate data, and (ii) for multivariate data with structure. In particular, for univariate data it gives an expression for the optimal two layer denoiser in the interpolation (zero training error) regime with weight decay, and proves that for small noise this denoiser has better generalization error the eMMSE denoiser (nearest neighbor). 

 Reviewers expressed appreciation for the paper’s theoretical results -- in particular, for its closed form expression for the optimal denoiser,  and for identifying scenarios where neural nets outperform empirical MMSE. Points of discussion include technical limitations of the results (small noise), and the limited effectiveness of shallow denoisers in practice. The latter is less of a direct concern for this paper’s theoretical contributions, although it would be useful to have theoretical insights into the structure of deep denoisers. After considering author responses, reviewers converged to a recommendation to accept. Denoising is important in its own right, and a critical building block for generative models and inverse problem solvers. The paper provides clear theoretical insights, and raises some conjectures which could inspire future work.
Decision: Accept (poster)