Learning the optimal Tikhonov regularizer for inverse problems
Authors: Giovanni S Alberti
Ernesto De Vito
Matti Lassas
Luca Ratti
Matteo Santacesaria
Venue: NeurIPS 2021 Poster (2021)
Keywords: inverse problems
regularization
MMSE
optimal estimation
supervised and unsupervised learning
generalization estimates
Hilbert spaces

Abstract: In this work, we consider the linear inverse problem $y=Ax+\varepsilon$, where $A\colon X\to Y$ is a known linear operator between the separable Hilbert spaces $X$ and $Y$, $x$ is a random variable in $X$ and $\epsilon$ is a zero-mean random process in $Y$. This setting covers several inverse problems in imaging including denoising, deblurring, and X-ray tomography. Within the classical framework of regularization, we focus on the case where the regularization functional is not given a priori, but learned from data. Our first result is a characterization of the optimal generalized Tikhonov regularizer, with respect to the mean squared error. We find that it is completely independent of the forward operator $A$ and depends only on the mean and covariance of $x$.
Then, we consider the problem of learning the regularizer from a finite training set in two different frameworks: one supervised, based on samples of both $x$ and $y$, and one unsupervised, based only on samples of $x$. In both cases, we prove generalization bounds, under some weak assumptions on the distribution of $x$ and $\varepsilon$, including the case of sub-Gaussian variables. Our bounds hold in infinite-dimensional spaces, thereby showing that finer and finer discretizations do not make this learning problem harder. The results are validated through numerical simulations.

Learning the optimal Tikhonov regularizer for inverse problems
Giovanni Alberti
Ernesto De Vito
MaLGa Center, Department of Mathematics University of Genoa, Italy
MaLGa Center, Department of Mathematics University of Genoa, Italy ernesto. dew.ittooeeittouuug.....t
giovanni.. alberti Saberti@unn interrt@@iig...
Matti Lassas
Luca Ratti
Department of Mathematics and Statistics University of Helsinki, Finland matti. lassashhlskh
MaLGa Center, Department of Mathematics
University of Genoa, Italy luca. ratti@unigee..i..
Matteo Santacesaria
MaL.Ga Center, Department of Mathematics
University of Genoa, Italy
matteo. santacesariscumigg..t
Abstract
In this work, we consider the linear inverse problem y = Ar+E, where A: X + Y is known linear operator between the separable Hilbert spaces X and Y, a random variable in X and e is zero-mean random process in Y. This setting covers several inverse problems in imaging including denoising, deblurring and X- ray tomography. Within the classical framework of regularization, we focus on the case where the regularization functional is not given priori, but learned from data. Our first result is characterization of the optimal generalized Tikhonov regularizer, with respect to the mean squared error. We find that completely independent of the forward operator A and depends only on the mean and covariance of æ. Then, we consider the problem of learning the regularizer from a finite training in two different frameworks: one supervised, based samples of both and y, and one unsupervised, based only on samples of æ. both cases we prove generalization bounds, under some weak assumptions
the distribution of x and including the spaces,
case of sub- Gaussian variables. Our bounds hold thereby showing that finer and finer discretizations do not make this learning problem harder. The results are validated through numerical simulations.
Introduction
The aim of an inverse problem is to recover information about physical quantity from indirect measurements. Virtually imaging problems and modalities fall within this framework, including denoising, deblurring [14), computed tomography [4] and magnetic resonance imaging [1S]. Classi- cal and general approaches to solve inverse problems consist studying a variational (minimization) problem and can be divided into two classes.
The first is based on the so-called regularization theory [14.. The aim is to recover a single, determin- istic, unknown æt from noisy data y = F(x!) + by solving minimization problem
min dy (F(z).)) + (x)
(1)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

for fidelity term dy: Y x Y - R and regularization functional J: X + [0, +00). The latter is chosen in order to mitigate the ill ill-posedness of the map F, and represent some a-priori knowledge on J. For instance, in the classical Tikhonov regularization we have (x:) = >||=|| for À >> O.
The second approach considers the unknown random variable and is based on statistical/Bayesian methods 23 45]. In this case one can recover the unknown using point estimators such as the maximum a posteriori (MAP) estimator, or extract richer information on the probability distribution of the unknown. In practice, the MAP estimator is found by solving a minimization problem of the same form as I.. The main difference is that the fidelity term and the regularizer are tailored to the statistical properties of the unknown and the noise, which are usually assumed to be known.
In recent years, machine learning techniques, and especially deep learning, have shaken the field of inverse problems by providing the hasis for data-driven methods that have outperformed the state-of-the-art in most imaging modalities B 43). The most successful methods take inspiration 34
8 17 40): the physical model given by the forward map F is assumed to known while the regularizer (or the gradient updates related to it) is learned from a training set. While these approaches have shown impressive results in applications, solid theory behind their successes lacking. In view of the many sensitive applications where these methods are already being employed, e.g. in medical imaging, it is of utmost importance to fill this theoretical gap better understand the strengths and limits of data-driven imaging modalities. Moreover, many inverse problems are naturally formulated in
from regularization theory [10] 26
2
36 21
22 27
39
spaces [5 45 37), and their discretization must be carefully treated due their ill- ill-posedness 23
14
25
Hence, it is of main interest to provide theoretical analysis in the infiniteddimensione setting.
In this work, we consider the problem of learning regularizer for a linear inverse problem in the framework of statistical learning theory, which is the natural setting to derive precise theoretical guarantees. This is part of the growing research area of learning an operator between infinite dimensional spaces [46, 13 32 31. We study the case where the measurements are modeled by linear, possibly ill-posed, forward map, and the penalty term is generalized Tikhonov regularizer 477.
More precisely, let A: X + Y be bounded linear operator between the separable real Hilbert spaces X and Y. We consider the inverse problem
y = Ax +
which consists of the reconstruction of æ from the knowledge of where e represents noise. We assume that x is a random variable on X with mean μ and covariance Σ,z, and the noise e, independent of the variable 2, is a zero-mean random process on Y with covariance Σe, (see Section 2 for more details). The operator A is typically injective but its inverse may be unbounded: typical examples include denoising (A is the identity) and deblurring (A is convolution operator).
We aim to recover the unknown via generalized Tikhonov regularization. For a quadratic fidelity term dy : Y x x - TR, the minimization problem
min dy (Ax, y) + x
h)ll
(3)
has a unique solution (y) called the generalized Tikhonov reconstruction. Here the pair (h, B). where h E X and B: X - X is a positive bounded operator, is considered as free parameter that we call regularization pair. For example, the operator B can be smoothing operator in 1.2, as a negative power of the Laplacian, so that B-1 is a differential operator, yielding classical regularization in Sobolev spaces. We want to characterize and learn the optimal pair (h, B) with respect to the expected, or mean squared, error
L(h, B) = Ez,y RV) - -11
Our first contribution is a complete characterization of the minimizers of L.. In particular we find that (H, s is a global minimizer (and unique if A is injective), which shows that the best regularizer is completely independent of the forward operator A and depends only on the mean and covariance of xr This is consistent with the known linearized minimum mean squared error estimator in the finis-adimeniioal case (24), but it is usually not taken into account in the machine learning approaches to inverse problems mentioned above. The extension to the infinitediimensionll case not straightforward due to the presence of unbounded operators in inverse problems.

---

Since the computation of the expected error requires the full distribution of r and y, we study how this can be approximated from finite training set. We suppose to have access to a sample of m pairs {(0,, Uj) } drawn independently from p. In view of the results on the expected error,
we consider two alternative ways to learn a regularizer pair (hy, Bx) from a training set z: either by minimizing the empirical risk [12] (supervised learning), by using the empirical mean and covariance of { (unsupervised learning). In both cases, we prove generalization bounds for the sample error [Lgg B₂) L(p, )/ Under some natural compactness assumptions on the class of regularization pairs, we prove that the sample error has the asymptotic behavior
[L B₂) I(, |
mm
with high probability, in both the supervised and the unsupervised approaches. We stress the point that these bounds hold in the infinite-dimensionall setting, or, in other words, they do not depend the discretization of the signal and of the measurements.
theoretical findings with some numerical experiments. For ID denoising problem (i.c. A is the identity operator) we replicate the asymptotic bound (4) at different discretization scales. Moreover, we find that the unsupervised approach, despite yielding the same rate clearly outperforms the supervised one.
Finally, complement
The paper is organized as follows. In Section 2 we introduce the main notation and technical assumptions that will be used throughout the paper, including several examples. Section 3 presents the main results for the minimization of the expected error, while Section 4 devoted to the study of the sample error. Numerical experiments are the subject of Section Concluding remarks and discussions are reserved for Section G
2 Setting the stage
2.1 The random objects x and
As mentioned in the introduction, we formulate (2) as statistical inverse problem, where and & are not deterministic but random. Let us start with the description of the prior on r.
Assumption 2.1. Let ær be a random variable precisely, æ is square-integrable, so that its expectation E X and its covariance Eg: X - X is trace-class operator. We assume that Eg is injective.
probability space (Ω, P) taking values in X. More
Without loss of generality we can always assume that Σg is injective (i.e., x is non non-degenerate), since otherwise it would be enough consider the inverse problem only in (ker Ex)) C X.
Let us consider some common examples of priors arising in inverse problems.
Example 2.2 (Gaussian random variables). general class of priors arises when considering Gaus- sian random variables. We recall that x is a Gaussian random variable if for all v E X, (z, v) is a real Gaussian random variable and, by Fernique's theorem, x square-integrable 7 Since E,; X - X is self-adjoint, positive and trace-class, we can write its singular value decomposition (SVD) as
V Σ of(v,e))xe
VEX,
where {ERJE is an orthonormal basis X, Σx of < too and (α,ex) ~ N σx), where Σx Mx is the mean of v. In other words,
x x= Σ TRORES
(5)
where ag are i.i.d. standard Gaussian variables. This shows that, in infinite dimension, since og - the variations of x along the direction eg become smaller and smaller as 1: - +00.
This abstract construction reduces to a smoothness prior by suitably choosing the covariance operator. Example 2.3 (Smoothing priors). Let X LTT)), where T /zd is the d-dimensional torus and d > 1. Let A denote the Laplace-Ba Belttrcm operator T which is simply the classical Laplace
3

---

operator on [0, 1] with periodic boundary conditions. For 8 > d. the operator
(1- L LT + 22 (
trace class, and can be used to define the Gaussian distribution NO (1 -)- . In the notation of Example 2.2 the SVD of (I A)-
)* is given by of (1 4m 4-| and (x 22rrk-t with
k zd This enforces smoothness prior 2, depending the parameter s, which controls the decay of the Fourier coefficients of x (see [33 Appendix BJ and (7).
Let us now discuss the model for the noise E. Assumption 2.4. Let E = (E) be (linear) random process Y with zero mean and such that its covariance Mg:: Y + Y defined by [[ = ( w)y is bounded and injective.
Notice that the injectivity of Eg implies that noise is present in all directions of Y, whereas the boundedness of f. allows us to regard the random process E as bounded (linear) operator from Y into (92,
(((,,P)). P). The reader is referred to [T6] and to Appendix A. I for additional details on random processes in Hilbert spaces. We mention here some basic properties that will be needed for the following discussion.
Remark 2.5. Even if may not belong to Y almost surely (see Example 2.7 below), it is always possible to view it as an element larger space, as we now discuss. Let K be a separable Hilbert space and :: K Y be an injective linear map such that (K) is dense in Y and
1. Eg o K + K is trace-class
where we identify y* = but we do not identify K" with K, and we regard x* as the canonical embedding Y K* The restriction of æ K is a Hilbeet--Schmidt operator from K into (2, P). hence there exists unique square-integrable random vector taking values in K* such that E = (e, k) x for v E K. is easy to show that the random vector has zero mean and its covariance operator is L" o Σg o K K", since
(e,,, e) x- (e, w) x-x = (le,()) = Seuw,ww)r
U. t E K.
random variable is always random process, as we now describe.
Example 2.6. A simple example of this abstract construction consists of considering a random variable e. In this case Eg is trace-class itself, that almost surely. As discussed in Example 2.2 for Gaussian variables. this means that, since + 0. the expected amplitude of the noise in the direction ej goes as k co. For instance, the choice of Σ. = (1 - A) as in Example 2.3 corresponds to smaller noise levels for higher Fourier modes.
choose K Y and and E Y
A random process allows for considering noise that is uniformly distributed in all directions.
Example 2.7 (White noise). The Gaussian white noise e is random process on such that for any E Y it holds that is standard Gaussian variable (mean 0 and variance 1), so that Σg Heuristically, the notation of Example 2.2 this corresponds to 0 = for every k; and so by (
Ok (0,
so that & Y with probability whenever is infinite dimensional (see, e-g., 16 In view
of Remark 2.5 it is possible to consider larger space K" so that e E K* almost surely. For
concreteness of explanation, we focus on the case when Y = TTd, typical framework in
imaging. A possible choice for the space K the Sobolev space H (T²) with d/2 (see [25 ) so that the canonical embedding v: H' (T*) + (TT is HiibeettSchhiitt operator, hence (6) is satisfied and e can naturally be seen element of H ===((T) (T
2.2
The new formulation of the inverse problem and of the regularization
As a consequence of Assumptions 2.4 since may not belong Y, the inverse problem ? must be interpreted from a different perspective, namely considering y as the stochastic process yo (Ar, u)y + E, on Y by formulating the problem as an equation in K"
Ax EE,
It is worth observing that K and i always exist: it is enough to choose them, independently of e, so that the embedding K > Y is
which implies that t" De is trace class, since D. is bounded.

---

x ie. (y. x) = (Ar, ((e))) + (E, K. for E K, where ::: Y + K is the natural embedding. We denote the joint probability distribution of (z.y) on X K* by
We now provide a consistent formulation of the quadratic functional appearing in (3). The goal is to replicate what would be the natural choice in finite dimensional context, i.e.
min />1//(Ax - y) + |
Unfortunately, Y is infinite dimensional, the first factor is in general not well-defined, since for example for Gaussian processes E Im E with probability 0 [ Thus, we need to write this minimization problem in different formulation. We start by stating the assumptions make on B. Assumption 2.8. Let assume that B: X + X is a bounded positive operator such that
Tm (ABB) C Tm(Ee().
It is worth observing that, whenever Y is infinite dimensional, then (m((ee) Ç Y since Egi is compact. Furthermore, (9) requires, in some sense, the operator AB: X + Y to be at least as "smoothing" the operator Egt: K - Y. For instance, in the case when AB and Egg. have the same left-singular vectors, this condition means that the singular values of AB should go to 0 at least as fast as the singular values of Egt.
We are now ready to rewrite the functional in (8) The penalty term involving B B= h) suggests the change of variables = h + Bx', The corresponding minimization problem for z' reads
min r'eX
جا, (A(hh + Bx') y)1 1|2'11
(10)
This expression does not require the injectivity of B. By formally expanding the first factor we obtain
|3 1/2 A/=''11 13
1/2(y) 2/ Ah), Eg ABx')y + + (/2 Ah)ll
Let us analyze these three terms separately:
1. Since Σg is aelf-adjoint we have ||Σ 1/2 AB'' = -2= AB='AB'' AB'x)) which is well-defined because (mAB) C Im,),) thanks to (
2. The second factor is formally equivalent to 2 - Ah, A. ABr')r. which is not well- defined as scalar product in Y since y may not belong to Y. However, since E K"* and Σ-1 ABRx' ((K) by (9), this scalar product be interpreted as the duality pairing 2y L" Ah, -1 AAB K-*K-
The third factor |Σ 1/2 (2 Ah)l independent of æ, and so it irrelevant for the minimization task: thus, we remove it. This is key step in infinite dimension, since, as mentioned above,
2/1/2yll = +oo almost surely. See Remark 3.8] for additional details on this aspect.
This discussion motivates the introduction of the following functional, formally equivalent to (10). For y E K*, we deñine the regularized solution of the inverse problem as å h + B&', where
f' arg min | 1/2 ABr 2 - Ah, (E.r)=+AB) ABr') x + ||
(11)
zee
The minimizer exists and is unique, and gives the following expression for
(y) = + Bå' B(BA', AB - ((2s) (" Ah), ("
(12)
where R: K* X is bounded affine map. See Proposition A.2 for all the details. Note that ((E1)- K* + X is well-defined thanks to 9
3 The optimal regularizer
The regularization approach described so far based on the choice of and B. classical regularization theory, these are chosen depending on the prior knowledge of the problem under consideration. In the data-driven approach we consider in this work, h and B are learned from training data. In this section, we let learning come into play and consider the problem of determining
5

---

the optimal h and B, under the assumptions that the distributions of x and are fully known. More precisely, this allows for the explicit computation of the expected error
T(h, B) = (xx)))> (v) - = =IIx = Rer,el Rn, Ax + - x11x=
which quantifies the mean square error that our regularization functional (11) yields. Optimal choices of h- and 1 are those that minimize L(h, 13), and are characterized in the following result.
Theorem 3.1. Let X and Y and be separable real Hilbert spaces, A: X + Y be bounded linear operator, x: and & satisfy Assumptions [n/ and 2.4 be independent, and and i. be as in Remark 2.5 Suppose B x1/2 satisfies Assumplion 2.8
Consider the minimization problem
min (Ex.) [Iae:a)>p<[IBBa Bl))) - x x112]],
(13)
h.B
where the minimum is taken over all B satisfying Assumption and and over all h E X. Then (B* h²)
a global minimizer of (13 / if and only if
h² = μ
and
B l2e A) = Exrl A)
=== ==='²² is always a global minimizer, and is unique if A is injective. Furthermore, for every minimizer (h², B, the corresponding reconstruction map is independent of B and, all y E K*, given by
In particular,
R - ++ E1 A AE + +xx ((2
AAp)
(14)
= = (AE, -x)) (A) An))
(15)
The proof is in Appendix A.3. Some comments on this result are in order.
By assumption 2" (AE,,' + Σx) is an injective compact operator from Y to K", so that inverse is not bounded, however it is possible to prove that A A + E-))- extends to bounded operator from K into X. With a slight abuse of notation, we denote this extension in the same way, so that (15) makes sense for all y E K*
(A"(A,,
To prove this result, we first consider the minimization in [3 over all possibile affine maps, which yields the so-called Linearized Minimum Mean Square Error (LMMSE) estimator of x. Then, it is possible to show that such optimal affine functional of the form R BB for suitable 3 and ht. In finite-dimensionss context, such result is direct consequence of the expression of the LMMSE estimator (see, e.g., 24 Theorem 12.1]). Theorem 3.1 generalizes this result to the
case.
In the case of Gaussian random variables, the expression of the optimal regularizer R* coincides with the maximum posteriori (MAP) estimator. Nevertheless, our result does not require any assumptions on x and æ being Gaussian (see the discussion in 19 20
The minimum expected loss can be computed as
(hh,B") = tr (E (2 A AE + 1x)-1>//
(16)
as is reported in Appendix A.3.
It is worth observing that the optimal regularization parameters B / and h+* = 1l are
independent of A and and depend only the mean and the covariance of x.
4 Finding the optimal regularizer: the sample error
The computation of the optimal regularizer proposed in the previous section through the minimization of the expected loss L requires the knowledge of the joint probability distribution p of and y. In this section, we suppose that p is unknown, ( but we have access to sample z = {(z,, y,) of m pairs (,, E X x K drawn independently from the joint probability distribution p. and study how to learn estimator (ha, B2) of the optimal parameters (h* B*). We propose two alternative ways to learn an estimator based on a training sample z. For the ease notation, from now omit the dependence z.
Mooe precisely, we only assume that D, is known.

---

1. Supervised learning: (hs. Bs) is determined by minimizing the empirical risk L, namely
(hs. Bs) argmin i(h, B), (h,B)ee
İ(h, B) m Σ
1
(17)
where O is a suitable subset of X X).
2. Unsupervised learning: since the best parameters are h" = and B = I//2 natural estimator
provided by means of the sample {az} alone as follows:
hu = f
1
J
Bu Bu= Ex 1/2
E= 2 (ag 1 (z,- P.)
(18)
In both cases, we evaluate the quality of (h, B) in terms of its excess error L(h, B) BB)
4.1 Supervised learning: empirical risk minimization
There exist several techniques to show the convergence of the empirical risk minimizer to the optimal parameter, involving tools such as the VC dimension and the Rademacher complexity (see, e.g., [44]), which require some compactness assumption on O. Here, we fix Hilbert space H with compact embedding j: H + X having dense range. For @1 > 0, set
, = (ih): h E H, | S ei), O₂ = [j B E HS(H", H), || (B) S ei). (19)
and define θ as the set of pairs {(h, B) E , x 92 : B is positive). Here, HS(H", .H) denotes the space of Hillbet-Schhide operators from H to H. We further assume that
a) the map j can be decomposed as j = jz hı where J1: H + X and j2: X + X are compact and satisfy
8k
O, being (k())) the singular values of jı;
(20)
whereas je is such that
Im(Ajz) S Im(2..).
(21)
b) The optimal parameter (h*, B*) (j,, />/²) belongs to e.
Assumption a), and in particular (20). allows us to explicitly compute the covering numbers, whereas (2I) ensures that Assumption holdd uniformly for each positive operator B E O2. For example, when H = H (T-) and X = H are Sobolev spaces the one-dimensional torus, assump- tion a is satisfied if = 0 - 02 > 0. As consequence, assumption (b) can be interpreted as an priori regularity assumption on the problem. Such hypothesis can be relaxed by introducing the approximation error, namely, the rate at which the space θ approximates x C(X, X) as the radius @ grows to Such an analysis, which easily follows from the range-density property of j. is not treated here.
Finally, we assume that both the inputs and the outputs are bounded, i.e.
supp(p) Bz(e2), ball of Z X K* of radius 02-
(22)
Theorem 4.1. Under the above conditions, let (hs, Bs) be defined by and take 0. We have
|L.ss. Bs) L(ht,B*)1 C1 + c2vTT
20/41
mo.
(23)
m
with probability exceeding 1 e_T, being 0 < s' < where C1, C22 mg are independent of m and
The proof of Theorem 4.1 is reported in the Appendices A.4 and A.5. The approach is inspired by [1] Proposition 4] and is suited for much broader class of learning problems: by adapting Lemma A.6, is possible to extend the current approach non-quadratic regularization functionals.
prominent example of H satisfying 20 comes from Sobolev spaces. Consider, e.g., X (TT) where TV is the d-dimensional torus, and иº (TT). If a O, the embedding of in X is compact, and its singular values show polynomial decay 20 with a/d.
7

---

4.2 Unsupervised learning: empirical mean and covariance
is possible to recover an approximation of the optimal parameter (h", )²) only by taking advantage of a sample of the output variable { 1 Since this technique does not require matched couples of inputs and outputs, we refer to it as an unsupervised learning approach. In order to prove bound in probability for the sample error, in this section we assume that x: is u-sub-Gaassian random vector, i.e.,
As pointed out in 18
(24) where ,> (x,, (ar, P)] It its known 488 that [[[[]]]]]] is finite for all p O, so that has finite mean and its covariance operator Σg is trace-class. Gaussian random variables are a particular instance of sub-Gaussian random variables by Fernique's s theorem 77. Note that, in infiniteddimensional spaces, bounded random vectors in general are not sub-Gaussian.
Ye X, (a, x)x is a real uubb-Gasssian r.v., i.e. ((x,,))xll S (Vpll
1p
We further assume that the injective operator Eg has a bounded inverse, thus Σ, AE, is invertible. This is satisfied for example if is the white-noise, since Σ, = I. We also require that A" (2" (Ee + AE,A")) defined on (" ("(Y) C K*, extends to a bounded operator from K into X.
Theorem 4.2. Under the above conditions, let (hv, Bu) be defined by 18 and take T > 0. Then,
[L Bu) 11) C3 + CAVT m 2 mo
(25)
mm
with probability exceeding e where mo. Cy and c4 depend only on E., Dg and A.
The proof of Theorem 4.2 is based on several concentration estimates reported in Appendix A.6. The rates we obtain can be meaningfully compared with recent results in supervised learning: see 6 35
5 Numerical simulations
We report some numerical results obtained from the supervised and unsupervised strategies for denoising problem, using synthetic data. The goal of these experiments is twofold: on one hand, we want to study the asymptotic properties of the regularizers learned with the techniques proposed in Section
4 as the sample size m grows, verifying Theorems 4.1 and 4.2 On the other hand, we want to assess that those properties, obtained in infinite-dimen dimensionl setting, do not suffer from the curse of dimensionality. We do so by introducing finer and finer discretizations, and showing that the theoretical bounds do not degrade as the dimension of the problem increases.
5.1 Problem formulation and discretization
We consider a denoising problem on X Y (T'),, being T' = R/Z Z the one-dimensional torus, which consists in determining signal x from the noisy measurement y + and thus corresponds to the case A = /. We define a statistical model both for e and for æ, which we use for the generation of the training data. In the learning process, though, we do not take advantage of the knowledge of the introduced probability distributions, apart from the covariance operator of the noise Σg. In accordance with Assumption 2.4] we assume that E is random process on Y. and in particular we consider a white noise process, i.c. with zero mean and Σ. = I²I. We consider a noise level of 5%, namely, the standard deviation o is set the 5% of the peak value of the average signal. In different tests, we employ different white noise processes with different distributions, including the Gaussian (cfr. Example 2.7) and the uniform distributions. Regarding x, we assume a Gaussian distribution with fixed mean μ and covariance Σn, where μ = 1 - 12x - 1| and 1/1 is convolution operator.
In order discretize the described problem, we fix N 0 and approximate the space X by means of the -idimensional space generated by a ID-pieel basis. As a consequence, the functions in and Y are approximated by vectors in R and the linear operators by matrices in IR NxN More details on the discretizations and on the random process generation are reported in Appendix A.7.
5.2 Implementation and results
We denote 0 (h, B). The workflow of the numerical experiments is described follows:
8

---

M--M
Superien
129
Excoee
(a)
(b)
(c)
Figure 1: Decay of the excess risks [L(0s) L(0") and |L(Oe) [(8*) in three different cases:
Gaussian variable r and (a) Gaussian white noise (b) uniform white noise and (c) white noise uniformly distributed w.r.t. the Haar wavelet transform. We also report standard deviation error bars.
10
Ecoees
10
10f
10"
10f
Sample
Sample
Sample
(a)
(b)
Figure 2: Comparison of decay the excess risks (L(0s) L(0*) and [L(Ov) -((0)) with N 64 and N 256, in same three statistical models as in Figure 1
1. Fix the discretization size N, define the optimal regularizer Rg. Compute L(0").
2. For each selected value of the sample size
generate the samples { )
minimize the empirical risk [()) to find 0s:
compute the empirical mean and covariance ý.. Ex find Op; compute the excess risks [L(0s) L(0*)) and |I(fu) ((
3. Show the decay of both computed quantities m increases.
We compute the mean squared errors L()"), L(Os) and L(Ou) according to the definition of L, thus avoiding the use of test set. Moreover, we perform the minimization of the empirical risk analytically, thanks to the explicit expression of the regularization functional provided by (12) (see Appendix A.7). As a final remark, the generalization bounds in Theorems 4.1 and 4.2 can be reformulated in expectation. Thus, verify the expected decay, we repeat the same experiment 30 times, with different training samples for each size m and taking the average in each repetition
In Figure T we present the outcome of the numerical experiments, conducted under different statistical models for and E. The sample size ranges between 3- 10 and 3 100. In all the presented scenarios. the decay of the excess risk both in the supervised and in the unsupervised cases agrees with the theoretical estimates, showing decay of the order 1/ym.. Finally, in Figure 2 we show that the theoretical results are equivalently matched by numerics when the discretization size is increased.
Additional details regarding the results of the numerical experiments reported in Appendix A.7. Moreover, in Appendix A.8 we replicate the presented numerical study for a different example,
All computations were implemented with Matlab R2019a, rumning on a laptop with 16GB of RAM and 2.2 GHz Intel Core i7 CPU. All the codes available ht hhtpp:t//// hupp:://githut httm://oaarmiiiitoooo//oooo

---

namely, a deconvolution problem for ID signals. In this case, A is a convolution operator with respect continuous kernel, whose inverse in general unbounded.
Conclusions and limitations
We studied the problem of learning a regularization functional for an inverse problem between infinite dimensional spaces. This problem has received huge interest in recent years due to the successes in several imaging modalities. Our work provides theoretical support machine learning approaches in sensitive applications such as medical imaging.
We have considered the case of linear inverse problem that is solved via generalized Tikhonov regularization. This involves an unknown operator B and a signal h, both to be learned from data. We proposed two learning strategies, one supervised and one unsupervised. Surprisingly. the regularizer learned with the unsupervised strategy has the same (or slightly better) generalization bounds than the supervised one. Furthermore, the unsupervised approach does not need the knowledge of the forward operator A nor that of the distribution of the noise This motivates the development of more advanced unsupervised approaches to the problem, e.g. with deep learning methods (see [26 27 34 36 )9)).
found that
The analysis presented here possible thanks the simple form of the regularizer. Our work does not cover, for instance, the case of sparsity promoting regularization functionals (18) or more general convex or non-convex penalty terms arising from deep learning methods. Some results regarding optimal (non-quadratic) regularizers associated with different priors can be found e.g. in [19 20 9 which nevertheless deal with finite-dimensional setting. Extensions to more general regularizers will be the subject of future studies.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the Air Force Office Scientific Research under award number 1186555200117022 GSA, EDV, LR and MS members of GNAMPA, INdAM. GSA is supported by a UniGe starting grant "curiosity driven".. ML is supported by Academy of Finland, grants 273979 and 284715.
References
[1] Adler and O. Öktem. Solving ill-posed inverse problems using iterative deep neural networks. Inverse Problems, 32412): 2017.
[2] J. Adler and O. Öktem. Learned primal-dual reconstruction. JEEE transactions on medical imaging, 3726)3332-1333, 2018.
[3] S. Arridge, P. Maass, O. Öktem, and C.-B. Schönlieb. Solving inverse problems using data- driven models. Acta Numerica, 28: 1-144, 2019.
[4] L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and
structural results. Journal of Machine Learning Research, 3NNov)4463-482, 2002.
[5] R. Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
[6] G. Blanchard and N. Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18(4):971-1013, 2018.
[7] V. I. Bogachev. Gaussian measures. Number 62. American Mathematical Soc., 1998.
[8] T. A. Bubba, M. Galinier, M. Lassas, M. Prato, L. Ratti, and S. Siltanen. Deep neural net- works for inverse problems with pseudodifferential operators: An application to limited-angle tomography. SIAM Journal on Imaging Sciences, 14(2):470500 2021.
[9] M. Burger and F. Lucka. Maximum a posteriori estimates in linear inverse problems with log-concave priors are proper bayes estimators. Inverse Problems, 30(11):1 30(11):114004, 14004, 2014.
[10] L. Calatroni, C. Cao, J. C. De los Reyes, C.-B. Schönlieb, and T. Valkonen. Bilevel approaches for learning of variational imaging models. In Variational methods, volume 18 of Radon Ser. Comput. Appl. Math., pages 252-290. De Gruyter, Berlin, 2017.
10

---

[11] B. Carl and I. Stephani. Entropy, compactness and the approximation of operators, volume 98 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge. 1990. ISBN 0-521-3301 14- doi: 10:1017/CH0997005118877447
URL https://doi. http://d0o...r111111011111
C809780511897467
[12] Cucker and S. Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 1011)11149) 2002.
[13] M. V. de Hoop, M. Lassas, and C. A. Wong. Deep learning architectures for nonlinear operator functions and nonlinear inverse problems. arXiv preprint urXiv 2019.
[14] H. W. Engl, M. Hanke, and Neubauer. Regularization of inverse problems, volume 375.
Springer Science & Business Media, 1996.
[15] C. L. Epstein. Introduction to the mathematics of medical imaging. SIAM, 2007.
[16] J. N. Franklin. Well-posed stochastic extensions of ill-posed linear problems. Journal of mathematical analysis and applications, 31(3):682-716, 1970.
[17] D. Gilton, G. Ongie, and Willett. Deep equilibrium architectures for inverse problems in imaging. arXiv preprint arXiv:2102.07944, 2021.
[18] M. Grasmair, M. Haltmeier, and O. Scherzer. Sparse regularization with lq penalty term. Inverse Problems, 24(5):055020, 2008.
[19] R. Gribonval. Should penalized least squares regression be interpreted maximum posteriori estimation? IEEE Transactions on Signal Processing, 59(5):24552240,, 2011.
[20] R. Gribonval and Machart. Reconciling" priors" &" priors" " without prejudice? Advances in Neural Information Processing Systems, 26:2193 2201,,2221122202 2013.
[21] K. Hammernik, T. Klatzer, E. Kobler, M. P. Recht, D. K. Sodickson, T. Pock, and F. Knoll. Learning a variational network for reconstruction of accelerated mri data. Magnetic resonance in medicine, 3966:330553377,, 2018.
[22] A. Hauptmann, J. Adler, S. R. Arridge, and O. Oktem. Multi-scale learned iterative reconstruc- tion. IEEE Transactions on Computational Imaging, 2020.
[23] Kaipio and E. Somersalo. Statistical and computational inverse problems, volume 160. Springer Science & Business Media, 2006.
[24] S. M. Kay. Fundamentals of statistical signal processing. Prentice Hall PTR, 1993.
[25] H. Kekkonen, M. Lassas, and S. Siltanen. Analysis of regularized inversion of data corrupted
by white gaussian noise. Inverse problems, 30(4):045009, 2014.
[26] E. Kobler, Klatzer, Hammernik and T. Pock. Variational networks: connecting variational
methods and deep learning. In Pattern recognition, volume 10496 of Lecture Notes in Comput. Sci., pages 28 1993, Springer, Cham, 2017. doi:
URL https
7/doi 10. 1007 00109977-33902
[27] E. Kobler, A. Etfland, K. Kunisch, and T. Pock. Total deep variation for linear inverse problems. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[28] H. Koch, A. Rüland, and M. Salo. On instability mechanisms for inverse problems. arXiv preprint arXiv:2012.00185, 2020.
[29] V. Koltchinskii. Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d' Eté de Probabilités de Saint-Flour XXXVIII-2008, volume 2033. Springer Science Business Media, 2011.
[30] V. Koltchinskii and Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, 23(1):100-133 2017. ISSN 1350-7265. doi: 10.3150/ 15-33. URL httpp:ttppss. //tp: org. 110....155/1--B..7350
[31] N. Kovachki, Z. Li, B. Liu, K. Azizzadenesheli, Bhattacharya, Stuart, and A. Anandkumar. Neural operator: Learning maps between function spaces. arXiv preprint arXiv:2108.0844 2021.
[32] Lanthaler, Mishra, and F. Karniadakis. Error estimates for deeponets: A deep learning framework in infinite dimensions. arXiv preprint arXiv:2102.080 2021.

---

[33] M. Lassas, E. Saksman, and S. Siltanen. Discretization-invaiann Bayesian inversion and Besov space priors. Inverse Probl. Imaging, 3(1):87-122, 2009. ISSN 1930-8337. doi: 10.3934/ipi.2009.3.8
URLpttps: //doi org wtt.o////....////ppppee 393.//99.24000000 2009.300.33.. 3.87
[34] H. Li, Schwab, S. Antholzer, and M. Haltmeier. Nett: Solving inverse problems with deep
neural networks. Inverse Problems, 36(6):065005, 2020.
[35] J. Lin, A. Rudi, L. Rosasco, and V. Cevher. Optimal rates for spectral algorithms with least- squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48(3): 868-890, 2020.
[36] S. Lunz, O. Öktem, and C.-B. Schönlieh. Adversarial regularizers in inverse problems. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 851 (525,, 2018.
[37] F. Monard, R. Nickl, and G. P. Paternain. Consistent inversion of noisy non-abelian x-ray transforms. Communications on Pure and Applied Mathematics, 7445):04551099, 2021.
[38] J. L. Mueller and S. Siltanen. Linear and nonlinear inverse problems with practical applications. SIAM, 2012.
[39] S. Mukherjee, S. Dittmer, Shumaylov, Lunz, O. Öktem, and C.-B. Schönlieb. Learned convex regularizers for inverse problems. arXiv preprint arXiv:2008.0288: 00283, 2020.
[40] S. Mukherjee, O. Öktem, and C.-B. Schönlieb. Adversarially learned iterative reconstruction for imaging inverse problems. arXiv preprint 1.Xi::2103.16111 2021.
[41] F. Natterer. The mathematics of computerized tomography. SIAM, 2001.
[42] N. H. Nelsen and A. M. Stuart. The random feature model for input-output maps between banach spaces. SIAM Journal on Scientific Computing, 43(5):A3312-A3243 2021.
[43] G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. Dimakis, and R. Willett. Deep learning techniques for inverse problems in imaging. IEEE Journal on Selected Areas in Information Theory, 1(1):39-56, 2020. doi: 10. (O00ISAA...0220299155..6
[44] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[45] A. M. Stuart. Inverse problems: a Bayesian perspective. Acta Numer, 19:451-559, 2010. ISSN 0962-4929. doi: 010017/00962292900000000 URL httpt::////oi..... 00tp://///0..rr11111111177 $0962492910000061
[46] Tabaghi, M. de Hoop. and I. Dokmanić. Learning schatten-von neumann operators, arXiv preprint 1911v:1901.1000 2019.
[47] A. N. Tikhonov. On the solution of ill-posed problems and the method of regularization. In Doklady Akademii Nauk, volume 151, pages 501-504. Russian Academy of Sciences, 1963.
[48] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
12


Reviews:
[{"review_id": "yKdzgo6jMI9", "reviewer": "Reviewer_SbHe", "summary": "The paper considers solving linear inverse problems of the form $y=Ax+\\epsilon$, where $A:X\\to X$ denotes a bounded linear operator. The setup is a Bayesian setup with known distribution of source and noise. To solve this problem the paper focuses on using generalized Tikhonov regularization and solving the following optimization: $\\min_x  d_Y(Ax,y)+\\|\\|B^{-1}(x-h)\\|\\|^2$. Let  $R_{h,B}(x)$  denote the unique solution of the mentioned optimization and define $L(h,B)=E_{x,y}\\|\\|R_{h,B}(x)-x\\|\\|^2$. For a given problem, the question is what is the optimal choice of $B$ and $h$ in terms of minimizing $L(h,B)$. The main result of the paper is to provide a full characterization the minimizers of $L(h,B)$ and show that $(\\mu,\\Sigma_x^{1/2})$ is a global minimizer of $L(h,B)$. (Here, $\\mu$ and $\\Sigma_x$ denote the mean and covariance of the input, respectively.) The paper also studies the case where instead of the actual source and noise distributions we have access to training data. In that case it studies two different methods for learning $(h,B)$ from data. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Here are my key reservations about the paper and the scope of its novelty:\n\n1) The main result of the paper is an extension of a known result for finite-dimensional spaces to infinite-dimensional spaces. The authors do not motivate the necessity and relevance of such as extension. The problems they describe in the Introduction are already addressed by the prior art. Moreover, the extension, as far as I can tell, is very technical but straightforward. \n\n2) The title of the paper is misleading. The paper focuses on a very specific type of regularization, namely generalized Tikhonov regularization. Clearly, this type of regularization is not optimal for many structured sources of interest. Constrained to this specific (and non-optimal) regularization, the paper characterizes the optimal parameters of the regularizer. This is far from \"learning the optimal regularizer\". Moreover, for finite-dimensional data, there are known results in the literature (not cited in the paper) on Bayesian high-dimensional linear regression that in fact characterize the optimal regularizer dependent on the source distribution, at least in the cases of noise-free measurements. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "qdibMrKDta7", "reviewer": "Reviewer_NW21", "summary": "The paper studies the linear MMSE in infinite-dimensional systems. Specifically, given an observation $Ax +\\varepsilon$ where $A$ is a known linear operator and $\\varepsilon$ is some form of noise, one wants to estimate $x$, which minimizes the mean squared error.\n\nFocusing on regularization, the paper asks what is the optimal regularizer with respect to the mean squared error. It is shown that, when constrained to Tikhonov regularization, the optimal regularizer has a rather simple form which depends only on the statistical properties of the system and, in particular, is independent from the operator $A$. \n\nThe authors also address the problem of approximating the regularizer, based on a finite sample. They show two approximations schemes: A \"supervised-learning\" scheme, based on minimizing the empirical risk and an \"unsupervised-learning\" scheme, which is based on the particular form the optimal regularizer was found to have.\n\nFor both schemes, the authors show that as the sample size $m$ tend to infinity, the approximation error decays at the expected rate $\\frac{1}{\\sqrt{m}}$.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main results of the paper are a generalization of well known results in finite dimensions to an infinite-dimensional settings.\nThe main ideas which underlies the proofs are also derived from the finite dimensional setting. \nE.g, in order to find the LMMSE, the authors equate the Gateaux derivative to 0, instead of the 'regular' derivative, as is done in the classical proofs.\nIn this respect, the results are not surprising and perhaps, one could claim, are not very exciting.\n\nHowever, as the authors demonstrate, the move to infinite-dimensions has many technical difficulties and is a highly non-trivial task.\nSpecial care must be taken when discussing the type of spaces involved in the problem, the type of linear operator between those spaces and even the form of admissible randomness. Indeed, even the correct formulation of the problem is not immediate, since in general one should not expect $A$ to have a bounded inverse. \n\nThe paper is well written, and the authors do a rather good job in motivating the formulation of the problem and the definitions. The math itself is very elegant and it could even prove useful for other, similar, problems. I think it can fit well with the theme of conference.\n\nHaving said the above, I do feel that the style and presentation of the paper could be improved. I add some concrete suggestions/comments below:\n\n- Above all, I feel that the analogy to the finite-dimensional case is important and is not highlighted enough in the paper. Some of the results obtained in the paper transform into simple exercises in optimization, when one considers well posed problems in finite dimensions. In my opinion, it would be beneficial to show (or atleast state) those proofs in the paper, followed by a discussion of the technical difficulties which arise when one moves to infinite dimensions.\n\n- I can appreciate nice math, hence my score. However, in the broader scope of the field, if possible, I would be happy for some motivating examples where one would actually want to consider the specific problems introduced in the paper. The authors mention denoising, deblurring, computed tomography and magnetic resonance imaging. As far as I understand none  of those examples is both 'infinite-dimensional' and 'linear'. Can the authors comment on this point?\n\n- Line 53: Presumably one also wants for the noise $\\varepsilon$ to be independent of $x$. I think this is also used later on.\n\n- Line 109: After reading Examples 2.3 I do not feel like I understand the problem better. I mean, Example 2.2 is kind of canonical, so it's nice to keep in mind, but I am not sure what purpose Example 2.3 is supposed to achieve.\nI can say the same about Example 2.6. However, this is a matter of personal taste and I leave it to the authors discretion.\n\n- Line 123: I feel that Remark 2.5 is very important and actually fundamental to the paper. Why is only a remark and not an actual part of formulating the problem? (Again, this is a matter of personal taste).\n\n- Line 126: I do not understand the comment that $K$ is not identified with $K^*$. In general, those are not isomorphic spaces and cannot be identified. The same comment repeats again, later in the paper.\n\n- Line 129: Shouldn't it be $v \\in K$?\n\n- Line 151: Since $v \\in K$. I think $\\langle Ax, v \\rangle_Y$ should be $\\langle Ax, \\iota(v) \\rangle_Y$. It's ok to omit the embedding, when it's clear from the context, but this has to be stated somewhere and it would help the readability if it would be consistent throughout the paper.\n\n- Line 161: \"to be at least as smoothing\". This sentence is too vague. I feel that saying something concrete would be more helpful for the reader here.\n\n- Line 164: I tried to understand why the main result is constrained to a linear map between Hilbert spaces, rather than, say, Banach spaces. As far as I see, the display beneath Line 164, where the authors expand the error, is the main reason for that. Can the authors comment on that? If this is so, it might be worthwhile to add a small discussion on this point.\n\n- Line 187: \"The optimal h^*\". As will be shown in Theorem 3.1, there could be more than optimal $h$. The word 'the' is then not appropriate here.\n\n- Line 190: It would be to have all assumptions written together in one place.\n\n- Display beneath Line 194: It's not very common to write \"A = B in some subspace\". I think that using a restriction sign \"|\" or just a projection operator would be more familiar.\n\n- Line 232: The quantity in this line is first defined as $\\rho_1$ but treated as a different letter in the following display. (Embarrassingly, I am not sure what is the other letter. Perhaps it is a different font of \\rho?).\n\n- Display beneath Line 232: The notation $\\mathrm{HS}\\left(\\cdot, \\cdot\\right)$ was not properly defined. Presumably, it means the space of Hilbert-Schmidt operators. However, later in the Appendix a different notation is also used for this space ($\\mathcal{L}_{HS}$), which might create some confusions.\n\nLine 271: I am not sure whether I agree with the statement in this line. The authors show that the strategies are equivalent when $s' \\to \\infty$, which seems like a degenerate case. Perhaps the authors mean to think about $s$ as being largish and then say that for any 'reasonable' $m$ the two bounds are close? Anyways, I would be happy for a clarification. To me, it seems that the 'unsupervised' method is superior (which is supported by the experiments).\n\nLine 325: \"e.g. with deep learning methods\". I am not sure I see the connections. Again, would be happy for a clarification.\n\nAppendix A.1: On one hand, I am happy that the authors added this appendix. It supplies some intuition, definitions and examples. On the other hand, I'm not sure what purpose it actually serves since all the necessary material was presented in the main paper and this appendix was never referenced in the main text.\n\nProposition A.2: As far as I can see, these are just the same assumptions, used before. This brings me back to the suggestion of having one place to gather all assumptions.\n\nLine 552: what do you mean by independence of $x$ and $\\mu$? $\\mu$ is deterministic.\n\nLine 558: \"such functional\" -> \"such a functional\"\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "kvrHEJzOXFu", "reviewer": "Reviewer_Q7iT", "summary": "This paper studies the learning of the optimal generalized Tikhonov regularizer for linear inverse problems. Optimality is investigated with regards to the mean-squared error.\n\nThe authors show that the optimal parameters are independent of the forward operator and additive noise. Next they look into how the optimal parameters can be learned from finite data for the supervised and unsupervised setting. They bound the excess risk for both settings. Both these bounds turn out to be similar. Lastly, the authors verify the theoretical bounds through numerical simulations.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThe results seem novel and I have not seen these kinds of results for the generalized Tikhonov regularizer before. However, the significance of the bounds could be better appreciated if they are compared to similar results in the literature. Similar could be done for the proof strategies. More generally, the related work could be strengthened by discussing relevant theoretical work on learning regularizers.\n\nQuality:\n\nThe similarities between the bounds in Theorem 4.1 and Theorem 4.2 are interesting. As the authors mention, the bounds become equivalent when s tends to infinity (line 271). Please can the authors explain in more detail what this means with regards to linear inverse problems? For example, does it connect to the forward operator, the noise, the ill-posedness of the problem, etc?\n\nThe numerical simulations nicely support the claims in Section 4. Another important finding is that the optimal regularization parameters are independent of the forward operator and additive noise. Do the authors also have experiments that show the same decay as in Figures 1 and 2 when different (non-identity) forward operators and noise levels are used? This is intriguing because in practice, when solving inverse problems, often the regularization parameters depend on the ill-posedness of the inverse problem.\n\nClarity:\n\nThe numerical simulation procedure is explained well and details are provided. In general the paper is well organized.\n\nWhat is the level of noise that is used in the experiments?\nIs there any reason why the excess risk increases when the discretization increases from 64 to 256 (especially for supervised learning)?\n\nIs $c \\in K$ on line 129 a typo?\n\nSignificance:\n\nI believe the results and insights in this paper are important and insightful. I also agree with the authors that the community can build upon this work by further investigating unsupervised methods and other regularizations that have more complex forms. \n\n##############################\n\nAfter author response: Thank you for responding to my comments. After reading all the reviews and author responses, I will keep my rating. I believe that the proposed changes by the authors will provide multiple clarifications and improve the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately discuss the limitations of their work.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "11"}, "extra_text": {}}, {"review_id": "SIc8QIgUU_y", "reviewer": "Reviewer_N3Qr", "summary": "This paper considers solving the inverse problem with a quadratic regularizer. It shows that the optimal parameters for the regularizer, in terms of achieving the smallest reconstruction error, are given by the mean and covariance of the true signal distribution. The paper also provides upper bounds for excess risk (expected error) for the estimated parameters learned from a training data set in either a supervised or unsupervised manner.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\nThis paper considers solving the inverse problem with a quadratic regularizer (generalized Tikhonov regularization). The problem is formulated rigorously in the context of functionals. There are two parts of theoretical results provided by this paper.  Firstly, it shows that the optimal shifting and scaling parameters in the regularizer should be the mean and covariance of the true signal distribution. Secondly, when the distribution is not available, the paper suggests two ways to learn those parameters from data and provides upper bounds for the excess risk. The results are verified through experiments. \n\nWeakness\n1. The paper shows the optimal parameters for the regularizer are the mean and covariance. By plugging them into the objective, it reduces to the objective of MAP, up to a scalar factor. It would be better to discuss this connection in the paper.\n2. Theorem 4.1 relies on the assumption (a), which introduces another Hilbert space H and corresponding maps j1 and j2. It seems unnatural and abstract to me to introduce those notations even for the purpose of bounding covering numbers. It would be better to discuss how this assumption fits into the practice. \n3. It is interesting that the unsupervised method outperforms the supervised one in terms of both theory and simulation. Considering that the supervised method requires additional data of y and more computation, the value of using the supervised method is further decreased. The information from y or the error seems unnecessary in estimating h and B, while the paper doesn't provide any discussion on this.\n4. In the numerical analysis, the paper only considers a simple case where A=I. That seems not enough since A is really an important component of the inverse problem. The experiments with a more general A are necessary and helpful in justifying the theoretical results.\n\n\n---- after rebuttal ----\n\nI appreciate the author's feedback. After reading the response and other reviews, I would like to keep my rating for this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think there is a limitation or potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a basic problem in optimal estimation, whose answer is well-known in the finite-dimensional case, and extends the characterization to inifinite-dimensional settings. In particular suppose we are given an observation of the form $A x + \epsilon$ and our goal is to estimate $x$ and achieve minimum mean-squared error. This paper studies the problem of characterizing the optimal regularizer, when constrained to a Tikhonov regularization scheme. They show that the optimal regularizer is independent of $A$ (this depends crucially on the assumption that $x$ and $\epsilon$ are independent) and moreover they give finite-sample guarantees for being able to approximate it. While the results are not surprising, there are many subtleties that just don’t happen in the finite dimensional case (e.g. $A$ will not in general have a bounded inverse). Overall the paper studies an important problem, makes a solid contribution and is well-written. 
Decision: Accept (Poster)