Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of estimating a linear functional of an unknown regression function lying in an RKHS, as well as optimal and adaptive design for estimating this. The paper proposes to use a ridge regression estimate together with design objectives that are variants of classical designs (e.g., $E$-, $A$-, etc. designs) that take into account the particular linear functional being estimated. The paper then derives finite-sample confidence sets for this linear functional. Finally, the paper presents methods and results for a number of practical applications with simulated data.
strengths_and_weaknesses: This paper presents a principled and novel approach to estimating a diverse range of interesting semiparametric quantities. I think this is an interesting and understudied problem, and I appreciate the emphasis on confidence sets rather than simply deriving convergence rates. I found the main paper (but not the Appendix!) fairly well-written. I have a few questions regarding the selection of the kernel and how this impacts the derived confidence sets (see below). The example applications are both compelling and illustrative, although, if I understand correctly, they all use simulated rather than real data.

Some typos:
1. Line 44: “depends among other things” -> “depends among other things on”
2. Line 80: “change in f compared noise” -> “change in f compared to noise”
3. The Appendix seems to have a lot of grammatical and writing errors. For example, the captions of Figures 4 and 5 don’t seem grammatical.
questions: 1. Lines 24-25, “$\nu_0$… is a positive definite operator. Depending on whether $\lambda$ is known or unknown…”: I suggest explicitly clarifying that the operator $\nu_0$ is always known. I initially thought it wasn’t, and hence got confused by Eq. (3). Also, how reasonable is the assumption that $\nu_0$ is known? For example, in the case when the constraint $\theta^\intercal \nu_0 \theta \leq \lambda$ encodes Sobolev smoothness of order $s$ (i.e., $\nu_0$ is diagonal with polynomially decaying entries in the Fourier basis) this is equivalent to knowing $s$, which is usually considered unknowable in practice. EDIT: After seeing the example constraint on lines 349-351, I realized I misunderstood the role of $\theta^\intercal \nu_0 \theta \leq \lambda$. I guess I suggest adding some explanation of the role of this constraint when it is first introduced around Lines 24-25.
2. Line 28, “$C^\intercal C$ is full rank”: Why is this necessary? It seems to me that estimating $C\theta$ would only become easier if $C$ is degenerate (and the same confidence intervals would still be valid, albeit loose).
3. Line 49: What is the $f$ in $f^\intercal \Phi(x) \geq 0$? Is this some function of $\theta$? Or a typo?
4. Line 64, “Let $S \subset \cal{X}$ be a finite set of selected evaluations s.t. $|S| = n$.” This notation seems to preclude querying the same point $x \in \cal{X}$ more than once. Is this intentional? EDIT: I later found that this was discussed in Section 6. However, I still suggest clarifying this around Line 64 to prevent confusion at this point.
5. Line 67, “one classically looks at the covariance of the residuals $C\theta - Ly$: Unless I am missing something, the formula given only agrees with the usual formula for covariance if $\mathbb{E}[C\theta - Ly] = 0$, i.e., if $Ly$ is an unbiased estimate of $C\theta$. This doesn’t seem to be the case in this paper. Maybe it should say “second moment of the residuals” rather than “covariance of the residuals”?
6. The choice of kernel(/bandwidth/feature map) could have a significant impact on the derived confidence intervals; can the author provide any guidance on this choice? Also, perhaps I missed this somewhere, but I couldn’t find what feature maps $\Phi$/kernel $k$ were used for the experiments.
limitations: As far as I saw, the paper doesn't discuss statistical optimality of proposed the algorithms (e.g., in a minimax sense). I would be especially interested in how tight the confidence intervals are (relative to the tightest possible), as well as understanding the conditions under which optimizing the scalar objectives proposed in Section 3.2 efficiently optimizing their population analogues.

I don't foresee any negative social consquences of this work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the optimal design problem for a linear model of which the slope resides in a reproducing kernel Hilbert space. Different from the vanilla linear models, regularization needs to be considered in the model studied in this paper. The observed covariance matrix of the residuals is inverted as the Fisher information matrix. A-optimum and E-optimum are considered. Confidence sets are estimated via normal and chi-squared distributions. Experimental design algorithms in the literature are discussed. My main concern is that beyond general discussions the paper may not provide sufficient new results for the high standard of NeurIPS.
strengths_and_weaknesses: Strengths:
* comprehensive discussion of the application background
* The problem of optimal design for linear models in RHKS is important and of interest to a broad audience.
* The problems in Sections 7.2 and 7.3 appear to be new and significant applications of kernel methods.

Weaknesses:
* There might not be sufficiently new results, especially compared against the high standard of NeurIPS.

=====================================

After reading other reviews and the author(s)'s responses, I realize that this paper does have sufficient contributions to the community of optimum experimental design. The extension of experimental design problems in infinite dimensional Hilbert space seems a significant breakthrough for the community. I am happy to raise my score and am OK with the acceptance of this paper.
questions: I find some writing problems, some rendering the relevant sections difficult for me to follow:

* the term "simple reverting law with a known gain" in Line 366.
* the term "uncertain" in Line 368.
* script "O" from Line 371 to Line 391, while this symbol was overloaded before as the big-O notation.
* some notations are not consistent. For example, C: p*m from line 41, L: p*n from line 65, X: n*n from |S|=n in line 64, but LX=C from Line 75 makes a contradiction.
* the V0 norm, in Lines 118-119 is not defined.
* A design does not maximize Tr(W), but 1/Tr(W^{-1}).
* In Lines 125 and 126, the transpose of X is left-multiplied to K, while in lines 127 and 133, it is X that is left-multiplied to K.
* I believe that the matrix V0 in Equation (5) is not defined.
* It seems that X is a matrix, but it is used as a space in Section 4.
* The concepts "support" and "allocation" need to be defined, e.g., in Proposition 5.
* In Theorems 1 and 6, matrices V-dag are overloaded to denote different objects.
* In the proof of Theorem 6, Ik and script I both represent the identity matrix.
* Instead of using an upper bound of the Chi-square probability for Theorems 1 and 2, why not just use its quantile function?
* It seems to me that Sections 7.2 and 7.3 are the focus of the paper. If this is the case, would bringing them to the beginning of the paper be better?
limitations: Limitations:
There is no obvious limitations about the methodologies studied.

Negative societal impact:
This paper is about a theoretical research, which has no direct negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of optimal design for estimating linear functionals in the nonparametric models restricted to the RKHS setting. Apart from optimal design points, the paper also constructs non-asymptotic confidence sets for the linear functional estimators under light-tailed noise settings.
strengths_and_weaknesses: Optimal design is definitely an important topic for statistics and machine learning. The specific topic considered in this paper also tries to advance our understanding of optimal design from linear models to nonlinear models by focusing on RKHS. This is definitely a welcome contribution and might have some impact in the future.

The results are quite novel to me, in particular the part on interpolation estimators. To my best knowledge (I may be wrong here though), this seems to be the first paper considering infinite-dimensional/nonparametric models for optimal design for estimating linear functionals. There are several earlier works on optimal design for nonparametric function estimation but they did not consider linear functionals.

The theoretical results of this paper are sound and the writing is succinct and clear.
questions: I do not have very specific comments or questions for the authors. But several papers are recommended to be cited:

1. Optimal design using SoS hierarchy: https://arxiv.org/pdf/1706.04059.pdf

2. Nonparametric function estimation: https://arxiv.org/pdf/1812.05553.pdf https://www.sciencedirect.com/science/article/abs/pii/016771528490066X

There could be more and the authors are also suggested to dig more into the literature and survey more in future versions, as I believe this could be an important service to the machine learning community.


limitations: The potential limitations are appropriately discussed.
review_title: null

Meta-review: metareview: There is a wide consensus among reviewers, after the discussion period, that this submission has strong and novel results compared to the existing literature on experimental design, which paves the way for confidence intervals that do scale in the dimension of the underlying possibly infinite dimensional Hilbert space of the problem. 
confidence: Certain
Decision: Accept