Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: Here are my key reservations about the paper and the scope of its novelty:

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

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


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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

main_review: Originality:

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

Quality:

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

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

Clarity:

The numerical simulation procedure is explained well and details are provided. In general the paper is well organized.

What is the level of noise that is used in the experiments?
Is there any reason why the excess risk increases when the discretization increases from 64 to 256 (especially for supervised learning)?

Is $c \in K$ on line 129 a typo?

Significance:

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

##############################

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

limitations_and_societal_impact: The authors adequately discuss the limitations of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

Focusing 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$. 

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

For 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}}$.
main_review: The main results of the paper are a generalization of well known results in finite dimensions to an infinite-dimensional settings.
The main ideas which underlies the proofs are also derived from the finite dimensional setting. 
E.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.
In this respect, the results are not surprising and perhaps, one could claim, are not very exciting.

However, as the authors demonstrate, the move to infinite-dimensions has many technical difficulties and is a highly non-trivial task.
Special 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. 

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

Having said the above, I do feel that the style and presentation of the paper could be improved. I add some concrete suggestions/comments below:

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

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

- Line 53: Presumably one also wants for the noise $\varepsilon$ to be independent of $x$. I think this is also used later on.

- 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.
I can say the same about Example 2.6. However, this is a matter of personal taste and I leave it to the authors discretion.

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

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

- Line 129: Shouldn't it be $v \in K$?

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

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

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

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

- Line 190: It would be to have all assumptions written together in one place.

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

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

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

Line 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).

Line 325: "e.g. with deep learning methods". I am not sure I see the connections. Again, would be happy for a clarification.

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

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

Line 552: what do you mean by independence of $x$ and $\mu$? $\mu$ is deterministic.

Line 558: "such functional" -> "such a functional"




limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Strength
This 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. 

Weakness
1. 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.
2. 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. 
3. 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.
4. 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.


---- after rebuttal ----

I appreciate the author's feedback. After reading the response and other reviews, I would like to keep my rating for this paper.
limitations_and_societal_impact: I don't think there is a limitation or potential negative societal impact of this work.
review_title: null

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)