Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spaces
Authors: Mojmir Mutny
Andreas Krause
Venue: NeurIPS 2022 Accept (2022)
Keywords: experiment design
active learning
confidence sets

Abstract: Optimal experimental design seeks to determine the most informative allocation of experiments  to infer an unknown statistical quantity. In this work, we investigate optimal design of experiments for {\em estimation of linear functionals in reproducing kernel Hilbert spaces (RKHSs)}. This problem has been extensively studied in the linear regression setting under an estimability condition, which allows estimating parameters without bias. We generalize this framework to RKHSs, and allow for the linear functional to be only approximately inferred, i.e., with a fixed bias. This scenario captures many important modern applications such as estimation of gradient maps, integrals and solutions to differential equations. We provide algorithms for constructing bias-aware designs for linear functionals. We derive non-asymptotic confidence sets for fixed and adaptive designs under sub-Gaussian noise, enabling us to certify estimation with bounded error with high probability.

Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spaces
Mojmír Mutný
Andreas Krause ETH Zürich krausea. ethz,
ETH Zürich mo mo.mmi.. www.mminf.fnn.nmmmmmmmm..... etwz.
Abstract
Optimal experimental design seeks to determine the most informative allocation of experiments to infer an unknown statistical quantity. In this work, we investigate the optimal design of experiments for estimation of linear functionals in reproducing kernel Hilbert spaces (RKHSs). This problem has been extensively studied in the linear regression setting under an estimability condition, which allows estimating parameters without bias. We generalize this framework to RKHSs, and allow for the linear functional to be only approximately inferred, i.e., with fixed bias. This scenario captures many important modern applications, such as estimation of gradient maps, integrals, and solutions to differential equations. We provide algorithms for constructing bias-aware designs for linear functionals. We derive non-asymptotic confidence sets for fixed and adaptive designs under sub-Gaussian noise, enabling us to certify estimation with bounded error with high probability.
Introduction
Optimal Experimental Design (OED) aims to determine data collection schemes designs to efficiently estimate unknown quantities of interest given limited resources (Chaloner and Verdinelli, 1995). As common, input. A design is usually either an (adaptive) policy for querying the oracle, or a (nonadaptive) fixed allocation of query budget different oracle inputs. OED has rich history and close relations the field of bandits (Szepesvari and Lattimore, 2020) and active learning (Settles, 2009).
model experiments via oracle that yields (noisy) response given
We consider the regression setting, where observations fixed input X' be obtained via the noisy oracle by:
0 ( + where E X
(1)
and T. denotes the inner product in Hilbert space Ha: is independent, sub- sub-Gaussian noise with known variance proxy o², and is bounded element from a separable reproducing kernel Hilbert space H., from kernel with a bound V/0 I X where Vo Hd - H₂ is positive definite operator. Depending on whether is known or unknown, we will propose different estimators. The bound the total effect and its parameters if
norm constraint (under Vo) be interpreted the Hilbert space finite dimensional. For infinite dimensional spaces this assumption can model the additional constraint regularity. For example, for kernels that induce Sobolev spaces, it explicitly bounds the total squared derivatives of functions quantities known to govern complexity of approximation diffieulty. The exact bound depends the specific definition of k, but if two spaces are isometrically isomorphic, the difference can be absorbed to Vo to induce the desired prior regularity, e.g., the regularity of the derivatives. Here assume that kernel and the operator Vo are known due to prior analysis and/or first principles modeling of the system.
In contrast to the classical ED task of estimating 0 (see Fedorov and Hackl, 1997), are interested in estimating a projection of f. Namely, let C H. > R be a known linear operator. The map C is
In most cases, but not all, Vo is chosen to be the identity.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

such that C C is full rank p. where CT denotes the adjoint. Our goal is to identify an estimate of C# efficiently, i... with low query complexity or with a maximal reduction of uncertainty given a fixed query budget T.
The formalism above captures, occurs as subroutine in, numerous practical problems. For example, evaluation at specific target points, integration and differentiation are all linear operators, among many other useful linear functionals. Other examples include ordinary or partial differential equations operators, spectral transforms, and stability metrics from control engineering. In Section 7 we detail several example applications.
A naive approach would be first obtain an estimate i of 0. and compute Ct. However, the appeal of estimating linear functionals directly is that the number of unknowns of interest may be much lower than for the original overall unknown element & (which might even be infinit-diimensonnl Consequenlly, we would hope that the query complexity of reducing the variance of the estimate CO scales in the dimension of the range of C, which p. For example, when focusing on finite- dimensional RKHSs, the operator C RT + IR, where m is the dimension of Hę becomes a matrix. In this work, we study the cases where p < m, and show that the estimation error can indeed scale with and the geometry of the query set {P(z))e E X7. The estimation bias plays a central role in this work as for very large m estimating C9 might not be possible up to any precision. The difficulty depends among other things the richness of the query set X' as we will detail later in Sec. 3.
Sequential Experiment Design Apart from classical experiment design, where we first commit to what set of queries x we choose, referred to fixed design, we also consider sequential design, where the selected queries depend on past observations. Suppose for example, we are gathering data to test whether the null Hg: O (1x) 2 0 for all x E X' or otherwise. We can incrementally gather evidence and check whether the null hypothesis has already been rejected. As our data depends on prior evaluation points it forms an adaptive design. In this work, we develop confidence sets for both fixed and adaptive designs - which are of paramount importance in the context of sequential experiment designs, e.g., to define stopping rules of adaptive hypothesis testing problems.
Contributions A) We consider objectives for experiment design for linear functionals in general RKHS spaces, which carefully take the bias of the estimator into account. B) We provide bounds on the query complexity required to reach c accuracy estimate linear functionals with high probability. C) We construct novel non-asymptotic confidence sets for linear estimators of linear functionals of RKHS elements, both for fixed and adaptive designs, where queries are independent of previous noise realizations, and where they are not, respectively. D) We demonstrate the improved inference error due specially defined designs and new confidence sets on the problems of learning differential equations, linear handits, gradient maps estimation, and stability verification of non-linear systems.
2 Background and Related Work
Linear Estimators Let S C X' be a finite set of selected evaluations s.t. |S| = n, potentially repeated. We focus on linear estimators of the form L R2 - IR,, where Ly is estimating CO. An estimator is understood here as the algorithm to find the random estimate Ly. Notice that given S, L is not a random quantity; the randomness rather comes from the realizations y. To choose the estimator L. one classically looks at the second moment of the residuals C# Ly, EL) LE((COLy)) Ly) Ly) J, where the argument signifies how the random variable y is transformed (noise is averaged)
E(L) = LL + (LX- - C)00 (LX- - T where E(L) E RPKP,
(2)
and the matrix X contains stacked evaluation functionals of the RKHS X,, = (x)x) for x E S C X. We will then seek a way to transform y via estimator L such that the second moment of residuals minimized in certain sense.
Importance of Bias and RKHS Classical experimental design studies estimation of C : 1 + RP where the RKHS is finite dimensional (Pukelsheim, 2006) and X E x On top of that, they consider only estimators which are unbiased for any 8, in other words, LX C. While, with finite dimensions, this simplification might be reasonable, for infinite dimensionial RKHSs, bias is inevitable and must be controlled. Consider the case of estimating the gradient of continuous function f. We can nearly never learn it up to arbitrary precision from noisy point queries. However, estimation up small error is always possible and sufficient. Estimating (=) from points close to fx( will incur small bias but larger variance as the change in f compared noise e is small. Hence balancing these two sources of error is crucial for informative design in RKHSs.

---

Experiment Design: Classical Perspective Consider an m dimensional version of the model in (I). Then, among all unbiased estimators, linear least-squares estimators minimize (2) under the Löwner order due to the famed Gauss- theorem. Unbiasedness in this form is synonymous with estimability, which means that by repeating the evaluation in X, arbitrary precision can be reached (Pukelsheim, 2006). The second moment of residuals then becomes W. CviCT,
where .f denotes a generalized pseudo-inverse and = =x=x.. The matrix W is often referred to as the information matrix. Gaffke (1987) and Krafft (1983) note that estimability implies that Wt is non-singular. We relax this condition and allow the estimator to have a bias; this means that we cannot in general reduce the error arbitrarily by repeating the measurements. In fact, our extension uses the fact that W as defined above will not be singular even if estimability condition is not satisfied. We will show that the matrix W can still play the role of the information matrix.
Experiment Design: Modern Challenges Mutný al. (2020) experimental design to estimate the Hessian of an unknown RKHS function, while Kirschner et al. (2019) use it to estimate the gradient of it for use in Bayesian optimization. Perhaps most related, Shoham and Avron (2020) study over- parametrized experimental design for one-shot active deep learning and analyze the bias in connection experiment design, similarly in the seminal work of Bardow (2008). They do not consider bias arising from the limited design space nor do they treat linear functionals. More broadly, the uncertainty propagation is studied in the Bayesian framework in the field of probabilistic numerics for linear and nonlinear operators (see Cockayne et al., 2017; Owhadi and Scovel, 2016, and citations therein).
Confidence sets Unlike classical statistics, our focus is non-asymptotic confidence sets regression estimators. They can be found in, c.g., Draper and Smith (2014) and Abbasi- Yadkori et al. (2011), 1), for fixed and adaptive designs, respectively. Our goal is to define the confidence sets in the appropriate norm such that their width scales with the dimension of the range of C, i.c., p. and the geometry of (+(x) | E X), but not directly dim(H.)) nor number of data T. Mutný et al. (2020) derive non-asymptotic confidence sets that scale in p. but grow with the number of points T as they do not the appropriate norm (see Appendix B.4). Similarly, Khamaru et al. (2021) study estimators for adaptively collected data, and propose asymptotic confidence sets for their estimators. Without specific condition, their confidence sets can grow with T, however, they consider more general noise distributions apart from sub-Gaussian as we do here.
3 Estimation and Bias
In this section, we motivate the linear estimators and identify information matrices. Information matrices are the inverses of second moment matrices of residuals E as in Eq. (2). They are an important object in the analysis of the error of the estimators and their confidence sets. Also, they depend on the evaluations that define the estimator L, X. Maximizing the information matrices as a function of the chosen observations and their proportions X gives rise to optimal experimental designs.
Further, we identify quantities that influence the bias of the estimators. We study two estimators: the least-norm estimator (interpolation), when the bound |00|y, is unknown but finite, the ridge regularized least squares estimator, where |00ly S -1 is known. Both estimators are motivated as minimizing the error residuals E in trace norm under these two bound assumptions.
3.1 Estimators
Interpolation As apparent from Eq. (2), without the knowledge of an explicit bound on the norm 0, the worst case over & causes the optimal estimator to minimize only the trace of the bias. This leads to minmization of (C - LX),, 1/2 in Frobenius norm, leading to the familiar interpolation estimator,
C == Lyy CV, x K
where K= = -- T
The second moment of residuals can then be expressed as
+ 1 -CCCC
E(L,) I o² XV
variance
where Px = - 1T 1/ (V. 1/2 1/2
D)V is a scaled projection matrix. Unlike as in the classical ED treatment, the second moment has two terms: bias and variance. If the span of the scaled projection operator lies the null space of C, the bias (classically) vanishes. To control the error of estimation, need to control both terms. For the special case of interpolation estimator,
bias
3

---

we will control the second term separately using a bias condition, and the variance term will be controlled by the information matrix W we will see in Section
W W+XX)= = (CV, x K-V,, --)
(4)
The ridge regularized estimator is motivated by using VT. I x- and minimizing then the trace of this upper bound, leading to an estimator,
Regularized Regression
CÂ Lay CV (Ao'I+ k)
Like above, we can give an upper bound on the second moment of the residuals. Conve- niently, this estimator automatically balances the error due to variance and bias in one term: E(L,)) C00 CT - x can express the above bound in a more concise form, and subsequently its inverse motivates the definition of the information matrix for the regularized estimator,
x - CT, Using the matrix inversion lemma, we
W (X = ( +X
3.2 Design objectives: Scalarization
The information matrices such as in (4) and (6) represent the inverse of estimation error, and the goal of optimal design is to maximize them (hence minimizing the error) with a proper choice of X. As the Löwner order is not a total order, we need to resort to some scalarization of the information matrices, thus we solve maxx / (X)). where f is the scalarization IR? - IR. We focus on two common forms of scalarization and refer to them as E- and A-design (Pukelsheim, 2006).
* fe(W)== = Amin( ()) - when constructing non-asymptotic high probability confidence sets;
. (WW (/ when minimizing mean squared enror of estimation.
Other popular criteria include D, V. and G-designs (Chaloner and Verdinelli, 1995), which we do not consider due to space considerations, but can be equivalently used should the experimenter have reason for it. If p 1, C an element in Hg and the design problem degenerates into a special case known c-optimality due to Elfving (1952) and, as W E R. no scalarizations are needed.
Robust Designs The linear functionals are sometimes unknown, or parametrized by an unknown parameter y as C.y, where belongs to known set I. If we were to construct design that has low estimation error for the worst case selection of y, we can maximize the information in the following
worst case metric maxx inr I (CC,,, X K -x= CC)) " for the interpolation estimator
(and analogously for ridge regression). If the original function f(W) is concave, then is the function defined as the infimum over the compact index set I, which is true for the design criteria considered this work (Boyd and Vandenberghe, 2004).
Fixed Designs and their Confidence Sets
In RKHS spaces, especially infinite dimensional ones, the extimability without bias is too restric- tive. Given a finite evaluation budget T, we can only construct a discrete design X : Hr + RT. and there where, given a finite query budget, C# cannot be learned to arbitrary precision, most prominently gradients and integrals among many others.
Estimate (C²)
Projected truth Projected
Confidence
Adaptive Confidence Sets
many practical examples,
8
Figure I: A two dim. example. Left: fixed design with our and projected confidence sets from two dimensions. Right: Adaptive confidence sets com- pared with projected ones due Abbasi-Yadkori and Szepesvari (2012). In this example C = (1,0) and 0 0.
Estimation with Bias and Interpolation Es- timator Our goal is to establish a condition on the design space X such that the estimation with the interpolation estimator is possible up to certain bias measured under the Euclidean norm. We measure the bias scaled by the magni- tude of the Frobenius norm of the estimator and call this the relative w-bias. This condition will allow us to balance the error due to the bias and noise.
Definition 1 (Relative y- bia).... Let C: Hr - R. The estimator L on the design space X is said to have relative v-bias if
|C L2 1/2 1/213 $ x² |

---

The Illll corresponds to the Frobenius norm of the maps H. - Hy. Due to the cyclic property of the trace, we can take the adjoint of the operator and calculate the quantity by taking a trace px matrix instead. If v = 0 and dim(Hx) = m, as we show in Lemma in the Appendix, this is equivalent to the classical estimability condition due to Pukelsheim (2006). The left. hand side corresponds to the classical bias bias(L+y) = [|E[[ 2 2 of an estimator L, under the Frobenius norm. This is exactly the quantity that L, minimizes. The classical bias cannot be improved by repeated measurements allocations thereof. Using relation which we show formally in Proposition 5 in Appendix B, can bound the bias(L | 1 C S Amin (W/t)=/2v/V3
To check whether the condition (7) is satisfied given a design space X, one needs to evaluate the trace. Finding the value of p x p matrix, however, depends strongly on the form of the operator C, and general recipe cannot be provided. Due to Riesz's representer theorem, and fact that the range of C is
imite-dimensionall this is always possible. For example, for an integral operator J ((x) q(x;) )zz,
using shorthand = K- y. it holds that Ly Σx=1 k(zz, 2; ),,d, where we used n points. Notice that we used only evaluations of kernel x to do this calculation. Also notice that calculation of (7) reduces to the calculation of the maximum mean discrepancy (Gretton et al., 2005) between the empirical distribution (defined on X), and ((z) for this example. The general recipe is to (locally) project the Hilbert space on a truncated the check involves a solution to linear system, but this is not always necessary.
basis C pm (2) with size and, in that case,
4.1 Confidence sets
To construct confidence sets for both estimators considered, we split them into two categories: fixed designs, where the evaluation queries do not depend on the observed values y, and adaptive designs, where the queries (xx;) may depend on prior evaluations yi-1,... 91. Proofs are in Appendix B.
Theorem 1 (Interpolation - Fixed Design). Under the regression model in Eq. (1) with T data point evaluations, let â be the estimate as in (3). Let X satisfy the bias from Def. I with W, = (CV) 1/2 1/2 ) Then,
P p((C0- - 10000 2 -(VE(
V ))
(8)
W,
vX
where Vi = 1/- (XV - 1/2 and E(6) = p + 2 (vplog()) 2
+ log (3))
Notice that in order balance the source of the error due to bias and variance with high probability, we need to match a /E() VX. Repeating the queries in X T times reduces a by 1/vT but leaves the bias v/ as well as Wt. unchanged. This is because with the interpolation estimator the noisy repeated queries are averaged, which can be interpreted as a reduction in variance. Hence, by balancing / v/VÀ VÀ with a / [(T)//TT we balance the bias and variance such that they are of the same magnitude. It does not make sense to repeat measurements more times if the bias dominates the error of estimation. A detailed example of estimating the gradient with fixed bias is given in See. 7.2.
We derive confidence sets for the regularized estimator of Eq. (5), albeit without the relative bias.
Proposition 2 (Regularized estimate Fixed Design). Under the model in Eq. (l) with data point evaluations, let 02 be the regularized estimate as in (5). Then (22(v/2 (vplog()) + log (t)).
P (1010- 0) W. 2 >VE(0) vE(0)++1) <
6, where ((δ) 2
Notice that, since the regularized estimator is designed to balance the bias and variance automatically, we do not need specifically control the bias, which is contained within the information matrix W x- Despite this elegant property, the regularized estimator involves a more challenging analysis. The main motivation study the interpolation estimator is to understand the lg error show in Section 6.
5 Adaptive Design and Confidence Sets
To provide confidence sets for adaptively collected data, we need to project the data in X onto C, where we will denote the projection by Z further on. With the data projected, we can reason about the reduction of the uncertainty of C0 for each point separately, since to each & (<x:)) we can associate unique in RP.
5

---

Definition 2 (Projected data). Let z(r) E IRP, projected data, be vector field s.t. ((r))) (x))VV + (zx), where x C X' and j(æ)) E H.. |S] = nt, such that CV = 0.
Classically, the adaptive confidence sets are understood only for C I, i... the identity (Abbasi- Yadkori et al., 2011). In fact, we can always derive confidence sets for C# from confidence sets for 6 as they only project the ellipsoid be unnecessarily large, as the confidence parameter scales as (ddim(Hx)) in general (see Figure for visual example).
smaller dimensional space. However, their resulting size may
The martingale analysis of Abbasi-Yadkori Yadkori et al. (2011) and de la Peña et al. (2009) specifically assumes that information matrix V., (where C I) can be additively decomposed to information matrices due to a single evaluation Vr = Σi= (x;))(())) each at a different time. With the matrix WA.,. this additive decomposition is not always possible. Therefore, to utilize the martingale analysis, which requires this additive property, we consider different information matrix, which upper bounds Wx- The information matrix we use, 22,, is constructed from the projections z(z;), which have the necessary additive property. gives rise confidence sets, where, under the ellipsoidal norm, their size scales as (p)) The estimation error depends on f2, still, but under this norm, the confidence parameter and information matrix are decoupled in a similar way as for the fixed design.
Theorem 3 (Ridge estimate Adaptive Design). Under the regression model in Eq. (1) with t adaptively collected data points, let xx, be the regularized estimate in (5). Further, assume that Z is as in Def. where X, = Z.C + J. /. Then for all 2 0.
|C0 (0(00-0)11 s2x
1 det(S2x.))/22
$ 122log log
+1
i det(AS)2/2
with probability 1 - 6, where Ω2,t 02 Z Z, + AS and S =
The matrix Z, can be calculated by solving a least-squares problem (projection), whereupon CVJ1/2,, J, = 0 as needed by Definition 2. Notice that, on one hand, the above confidence pa- rameter grows only when Z is large, but the same time, the ellipsoid shrinks only in that case as well. Also, the ellipsoid above is necessarily smaller than the one with the information matrix WA as WA 3 S2 (Lemma in Appendix). This means we can use the same confidence parameter to give a bound for Il-llw... Notice that the estimator the same as before, i.e., 0x using to define the regression, only the information matrix changes. We also present a visual comparison in Figure 1 on simple example, showing that our fixed and adaptive sets are tighter than projected non-asymptotic sets. Using the shorthand (ō) to define the confidence parameter in (9), we can in fact bound the error as |C((,, l]ll S Amin (Rx,,) (,2,)(6)) It depends on m = dim(H.) only via 22 The dependence of the confidence parameter can be at most ([v + T)),, see Lemma 4 in Appendix B. The value of Amin Amiin( (f2,,))= depends on the geometry of the set {T(x)) E X} and the projection operator C as we show in Section 6.3. Note that the lower bound of (Szepesvari and Lattimore, 2020, Ex. 20.2.3) does not apply here, since it makes statement only about the information matrix W,.
6 Convex Relaxations, Geometry and Dimensions
Suppose are given candidate set of experiments, i.e., unique subset of evaluations S C X, | n and a budget T of total queries. We seek an allocation X, where the rows of X contain potentially repeated evaluations from S. How many times should we repeat each experiment in order to find maxx /(W (X))? To address this, experimental design literature relaxes this discrete optimization problem, and optimizes over fractional allocation 1) E A", where the number of repetitions for (xx;)) is recovered by rounding [n T". With this interpretation, the objectives in Sec. 3.2 can be written as
1)" = arg max 7EA"
(DW 1/2xs)) = = X.ICCV.'x.DD))X.... DD
(10)
where D(v) is the diagonalization operator that produces a diagonal matrix with vector 7 on the diagonal and Xs contains non-repeated elements in S. We have stated the problem above for the interpolation estimator and dim < oc, but it naturally generalizes to kernelized estimators, albeit in less concise form (see Appendix C).

---

6.1 Optimizing allocations: experiment design algorithms
Given a subset S, the problem (10) can be approximately solved using either convex optimization methods or a greedy algorithm. A comprehensive review of methods constructing designs 17" and rounding techniques to get X is beyond the scope of this work, and not the core issue addressed in this work. We briefly review two versatile approaches for completeness (more details in Appendix C).
Greedy selection Firstly, one can greedily maximize the scalarized information matrix with the update rule 7/+1 1+I + I 5, arg max f (Wx ( (+f7 ti + ==10)) where f refers to the scalarization and 5, to the discrete measure corresponding to the feature map ((x).. Due to the form of the update rule, try, always an integer.
6.2 Convex optimization
Alternatively, convex optimization can provably solve the problem to optimality. Specifically, we look for an allocation using convex optimization methods max f(W (D))))/22))) where E {t, A). Care needs to be taken when selecting S, as we discuss in Appendix C. The most common algorithms for ODE problems are the Frank-Wolft algorithm (Todd, 2016) and mirror descent algorithm (Silvey et al., 1978). Additionally, semi-definite reformulation of the above optimization problems can be given as we shown in Appendix C.3. Optimal designs found via convex optimization need to be rounded in practice. State-of-ai rounding techniques are discussed by Allen- Zhu et al. (2017) and Camilleri et al. (2021) for finite and infinite dimensional spaces, respectively. The exhaustive cover of rounding techniques is out-of-scope of the current work.
6.3 Estimation error and its dimension dependence
If we were bound the squared error of estimation in high probability, the importance of the scalarization Amin (W;) becomes apparent. Using the Cauchy Schwarz inequality, we get
c(e - 12 S Amin (W;) (W/) c(E - -0) w, -
Amin (W+(n*))- (o (oVE(6)+vVV)
T
where the term due Proposition scales as (p)) when properly balanced. Using the optimal alloca- tion 1)",, the number of repetitive evaluations is equal to TT" Inverting the relation above yields a query complexity of the order T = O ( Amiu (Wi ) The optimal value Amnin (Wi (17)) represents problem dependent quantity that measures the difficulty of estimation and captures the geometry of the set { (x))² E S C X3. It cannot be bounded in general, but it has an elegant geometric interpre- tation. In particular, it corresponds to the square inverse of the diameter of the largest inscribed ball in the corvex hull of symmetrized (Ø(x) ja E S} in the range of C (Pukelsheim and Studden, 1993).
At first glance, calculating this quantity might seem complicated, but with an example is apparent. For example, if (xx) = x s.t. ||<|| < (unit l2 ball in RT") and C = v, where v is a unit vector (p = 1), the inverse diameter of largest ball we can inscribe in direction of inside ||==| < equates to 1, which is independent of d. This is not surprising, since it represents an "easy" design space, where for any direction one
find action aligned with that coincides with the optimal design. This is true even if C has more rows. On the other hand, if we assume evaluation in the I ball ||a||] < and C is vector of ones (again p 1). Then the diameter of the inscribed ball is proportional the inverse square height of simplex, namely, m despite p 1. Hence, despite the confidence parameter being (1), the complexity depends primarily on the geometry of this set.
To give more exotic example, if C = V (z), and the design space are points with fixed length steps in all unit derection (I: (x + + e, where h is the stepsize and e; are principal vectors in Rd we can show that Aman W1 < dh - (hh)), leaving the overall complexity learn a gradient to scale with d instead of the dimensionality of the RKHS which can be infinite. All formal proofs and references provided in Appendix D.
Applications
We now discuss concrete applications that benefit from our contributions. Details of the experiments, and further applications, e.g., in statistical contamination, can be found in Appendices and F. We provide information about optimization and rationale in choosing the and Vo in C and F respectively.
7

---

Tw4
7-16
Tw32
est. G (Elo08)
naiey cbser. dessign
Total Fator
(stomach))
65
true (Kindd)
uncer. de
1ime (dhv5)
equaily spaced design
10
6o
10
1F/T
16
10
tensfom
random-ret
300
Concentration
steo-sice
(a) Pharmacokinetics
(b) Gradient estimation
(c) Controller stability
Figure? 2: Experiments: a) Pharmacokineties We compare the equally spaced design (black) with the optimized design (yellow). The optimized design mimics the classical pharmacokinetics approach of spreading the initial measurements more densely after the initial dose (Gabrielsson and Weiner, 1995). For us, this rule elegantly emerges from first principles. general, these trajectories follow a decaying pattern the examples in light purple. The uncertainty in cs due to the unknown dynamics y is depicted shaded region. b) Gradient estimation. The upper plot shows the total error of (*()) can certify with high probability as function of the step-size h for finite difference design. The minima of these errors exactly correspond to step-sizes derived from the bias- varrinnr trade-off we proposed for the interpolation estimator. With increasing T', noise can be reduced more, and hence bias of the design needs to decrease accordingly. hence the decrease in the step size (e.g., red red->green), e) Stability: We report the upper bound on the Lyapunov function in the whole operating domain, as a function of data points. The color coding (explained in the text) represents different data acquisition algorithms while dashed lines correspond to the confidence sets from prior work. Our confidence sets (solid) provide a tighter upper bound as a function of the number of data points, and allows faster termination, which happens when the upper bound zero
7.1 Linear bandits with finite number of arms
A special but important theoretical consequence of our adaptive confidence set is an improved regret bound for the upper confidence bound (UCB) algorithm (Auer, 2002) for linear bandits when the set of queries X' is finite. The queries are known actions in the bandit literature (Szepesvari and Lattimore, 2020). The UCB algorithm is procedure which iteratively queries the action according to x; arg max max & ((x), where C, is confidence set for 0 in round 4. Different to this, in our analysis of the UCB algorithm, we use the confidence sets due to Theorem 3, which are confidence sets for the projections o(x)) TO directly. We construct [X'] confidence sets, one for each of the linear functionals C₁ = (xr), and denote them by cfe(2)). The UCB algorithm then just becomes 24 arg max max y. We now analyze its cumulative regret Ry ==
(xx,)) 8, where x² = arg max,ex ((x) 0, and 0 is the true unknown pay-off vector of the bandit game.
Theorem 4. Let E TRd be an unknown pay-off vector, and a set of actions x E X such that |2| < co. Then the cumulative regret of the UCB algorithm is bounded by
Rr S OWVTolog(T((A + +))5)) with - probability.
Thus, our adaptive confidence sets for linear functionals yield regret bound that is factor of vd tighter than the standard bound. Note that this does not break the known lower bound (dd'T) for X' being the unit ball in Rd from Rusmevichientong and Tsitsiklis (2010), as we gain a logarithmic dependence on |x'). For an covering of the extreme points of the unit ball in Rd, one needs |X| & (I/e)" points, Icading to regret scaling as (tdv/Tlog(//ee + <T). Choosing e = 1/T would, for a fixed T. recover the lower bound up to logarithmic terms. Using standard doubling-trick techniques, one can provide anytime result. However, for different query sets (such as the I ball), whose extreme points (i.c., number of vertices) are finite (equal to d), these results can vastly improve the regret bounds. There are alternative algorithms based on arm-elimination, which achieve this regret bound, e.g., the algorithm of Szepesvari and Lattimore (2020), the SupLinRel algorithm of Auer (2002), and the algorithm of Valko et al. (2014). The proof of Theorem 4 is deferred to Appendix G, but it is straightforward application of previous results.
The above technique can be extended to infinite dimensional RKHS, where the role of dimension played by, ?r called maximum information gain (Srinivas et al., 2010), defined in Appendix G. The
8

---

remaining challenge is to bound the e-covering of extreme points of the set ( E [-1, C
Hy. where [-1, 1, 1] is the continuous action set. If all evaluation operators have | I| = 1, for all
E [-1, 1], such as for Matérn kernels (Mutný and Krause, 2018), we can use covering numbers of unit balls in these spaces as the upper bound on this number. These spaces are known to be isometrically isomorphic Sobolev spaces (Wendland, 2004), and the bounds on covering numbers of unit balls are known be of order ( ) where E N, 8 > d/2, refers to regularity of the Sobolev space (Cucker and Smale, 2002). This yields a bound on the cumulative regret of the order O( /CCddrTT Tog where C(d) can depend on dimension.
7.2 Gradient maps
Gradients of any order are linear operators. We can express the gradient at z as dimension-wise evaluation of the following operator V. ( 0) = (V,((z)) =: CO. Clearly, estimability is nearly always impossible, since any evaluation infinitesimally away from will be insufficient to eliminate bias. Thus our estimates will invariably be biased for any function with infinite Taylor expansion. Yet, while estimating the gradient from evaluations very close to the original x: leads to low bias, it at the same time increases the variance, since the difference in the functional value between the two point evaluations is very small compared to the noise magnitude. Given a finite budget or desired accuracy, the best we can do is to find the best design with optimal bias-variane trade-off given the kernel K, budget T, and noise variance finite difference designs {T(x + he:)}. where h is the stepsize and e; are unit vectors. In Fig. 2b, we plot the total error with high probability with the budget 7 as function of the step-size h. Notice that the lowest error occurs exactly when the variance of observations scaled with the confidence parameter is equal to the relative (two lines cross).
We consider a class of parametrized
7.3 Learning linear ODE solutions and their parameters
solution to a linear ordinary differential equation (ODE) u satisfies & uu( = Mu(t) + s(t), where
M a linear operator and s(t) is the non-homogeneous term. Assume that the solution to the equation
(() (()) 'u is member of a Hilbert space H.. then Tu == ( M(()) Φ(1) T s({) for
t e [to, t1]. Hence, the differential equation becomes a linear constraint for estimating u from samples. In fact, due to differential equations being fully specified by initial conditions, the only unknowns are due to initial conditions. To reveal the linear functional here, one needs to consider the solution to the differential equation, which can be written as u T s(t) + C vt where e E Hre \span (T) belongs to the null space of T. In this case, we span it with rows of C. Consequently, the unknown element can be found as Clu 1 s). Thus, what needs to be estimated from samples, is the linear projection Cu, since CT s known a priori. In Appendix F, we discuss implementation and calculation of the opera- tor C on a discretized domain. Also note that, Z itself induces a Hilbert space Hig containing the solu- tions u (González et al., 20. However, as we will see, for robust designs it is sometimes convenient to pick a larger Hilbert space H., s.t. H. C His and then apply the differential equation constraint.
Robust Design As specific example, consider an example of a pharmacokinetic model capturing the concentration of medication in blood and stomach via differential equations: (d/dt) cf, - ac. and (d/dt)c,- = bc.- - deg for t E [to, f1]. where c, and G are the concentration in stomach and blood respectively. The goal of this analysis is to infer y = (a, b. d) from the measurements of the blood concentration levels with fixed, but perhaps noisy, initial conditions (Gabrielsson and Weiner, 1995). To apply the above procedure, we need fixed differential operator T, to define the operator C,,, However, 7 is itself unknown. Instead, we can give a generally plausible set of 7 E T, initial condi- tions of concentration in blood (0) O, and norm constraints on the initial stomach concentration (c,(0) Canse) )2 < X (prior Vo) in order to apply our framework. We use the squared exponential kernel to embed trajectories and consider robust A-optimal design (as in Sec. 3.2) by maximizing the worst case metric yn 1/ /Tr(C,, ( (CC) with the regularized estimator. This way, the design appropriate for any y. After estimating the trajectory, we can use the estimated trajectories (given 7) to optimize for ry via the maximum likelihood. Fig. 4a presents the concentrations and c, with their estimates and uncertainties due to the unknown 7. We show the equally spaced (black) and optimized designs (yellow). The more accurately we can infer the trajectory, the more accurately we can estimate 7, which we quantitatively show in Appendix E in Fig. 4b, where we decrease the MSE of estimating by a factor of 10 in comparison to equally spaced design.

---

7.4 Sequential Design: Certifying Lyapunov Stability
Consider a non-linear system with x E I& such that 4 ==(t)== = f()(t), == ( +) u(x(t), t), where the rows of A, Hi for i E [d] model the system dynamics and (x))t)) are known evaluation functionals of Hx. We assume that the control laws u(x(t), t) can be written as u(x(t), t) (z(( t). We want to understand whether given a control law B stabilizes the above system. A common approach to create an estimate À of A from data samples of trajectories, and use the controller compensates the imprecise estimation of A with A, see below for an example. With this choice of u, the system can be written as 4.
Å P. where P is often a simple reverting law with a known gain that
(), where the A A A is the residual error in estimating A. We can certify the stability of the resulting system using a known quadratic Lyapunov function as commonly done in control theory, in this case, using V(z, t) (x(t) (te((t) (xx(t) - [t)( Classical stability theory dictates that if the total time derivative of V.
at =(((()= = (A À ())()(1), = (A P))((((),,
(11) negative for all xtt) E O then we can guarantee stability in the operating region of æ e O (Khalil, 2002). The above condition defines a linear operator C, (x - Fret) Σ -(x) operating on the unknown A for each æ E O. The linearity is best seen with vectorization as 0 vec(A). using the shorthand =f) r(t) (t), EA
dv/di = (ar(t) (() Σ(À - ())(x((1, () + ov/al,
vec(Ez((1) [> T)T
vec(A) C²O. The operator
is parametrized by x. C₂ for each x E O. Even for continuous domains x E O, C2 usually has low-rank structure, which can be calculated and depends on the size O and the size Hy. If the rank of the operator is small (e.g.. the operating space is small) then we can certify negativity of Eq. (11) faster than learning the whole A. In other words, we reduce uncertainty only where we need as in the seminal work of Berkenkamp et al. (2016). We can sequentially query data points from x and check whether C20 < 0 for all æ.
Consider a two dimensional nonlinear system from Lederer et al. (2021).
dr dt
1
sin (TT22)
x + 1 1+ exex(-22x1) -1 + 0.5
+
cos (OS(TT1))))))
The reverting controller is PD(x(t),t) = -K(x - Ixe((t)) + (d/dt)xret. where the refer- ence trajectory corresponds a circle star(t) (sin(t), cts( The Lyapunov function is V (xx(t) (eat))))((tt) (x(t) - Fre((t)). We assume that can set the system to initial condition <0))) and observe a noisy observations of the state y(0 + A) at rapid sampling times A. From these, we create a derivative oracle, (d/d()ar(() R (a(1 + -) - =(())/ A, common approach in nonlinear data-driven control (Umlauft et al., 2018). We use this example to showcase our adaptive confidence sets. We follow an adaptive stopping rule, where we query new data points if negativity cannot be certified. Due to this adaptive stopping rule, the data is adaptively collected.
We compare our confidence sets (solid) with the classical confidence sets of Abbasi- Yadkori et al. (2011) (dashed) and report upper bounds on the supremum over x E O of Eq. (11) in Fig. 2c. The operating region is a "tube" around the circular reference trajectory [t)(()) We see that our confidence sets shrink much faster than the classical confidence sets, since we can eliminate redundant information by projecting onto C. Fig. 2c compares random sampling of datapoints from the whole domain (random) and the operating region (random-ref) and sampling according to uncertainty in the dynamies in the whole domain (unc) and within the tube around the reference trajectory (unc-ref). As expected, focused exploration methods work much better. However, and more importantly, the tightness of our confidence sets enable much quicker stability certification (termination). Note that the classical confidence sets may even grow in the cases where redundant information for estimation of C inserted into the estimation, e.g., with random sampling.
8 CONCLUSION
We considered the problem of learning a linear function of an element in a reproducing kernel Hilbert space. We addressed the challenging case where linear estimators incur non-nggligible bias and provided confidence sets for the two most commonly used linear estimators. We demonstrated the generality of our approach and the tightness of our confidence sets on several challenging applications. We believe our results lay important foundations for principled and efficient experiment design in complex real-world settings.
10

---

Acknowledgement
This project has received funding Swiss National Science Foundation through NFP75 and this publication was created as part of NCCR Catalysis (grant number 180544), a National Centre of Competence Research funded by the Swiss National Science Foundation.
References
Abbasi-Yadkorts Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320.
Abbasi- Y. and Szepesvari, C. (2012). Online learning for linearly parametrized control problems. PhD thesis, University of Alberta.
Agrell, C. and Dahl, K. R. (2020). Sequential bayesian optimal experimental design for structural reliability analysis. arXiv preprint arXiv:2007.0040.
Allen-Zhun Z., Li, Y., Singh, A., and Wang. Y. (2017). Near-optimal design of experiments via regret minimization. In Proceedings of the 34th International Conference Machine Learning, volume 70 Proceedings of Machine Learning Research, pages 126-135, Sydney, Australia.
Auer, P. (2002). Using confidence bounds for exploitation-exxllraiion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422.
Bardow, A. (2008). Optimal experimental design of ill-posed problems: The meter approach. Computers & Chemical Engineering, 12(1-2):
Beck, A. and Teboulle, M. (2003). Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 3173):1671175
Berkenkamp, F., Schoellig, A. P., and Krause, A. (2016). Safe controller optimization for quadrotors with gaussian processes. Robotics and Automation (ICRA), 2016 IEEE International Conference pages 491-496. IEEE.
Betke, U. and Henk, M. (1992). Estimating sizes of convex body by successive diameters and widths. Mathematika, 39(2):47-257.
Boyd, S. and Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
Cakmak, S., Astudillo Marban, R., Frazier, P., and Zhou, E. (2020). Bayesian optimization of risk measures, Advances in Neural Information Processing Systems, 33.
Camilleri, R., Jamieson, K., and Katz-Samuels, J. (2021). High-dimensional experimental design
and kernel bandits. Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1227-1237. PMLR.
Chaloner, K. and Verdinelli, (1995). Bayesian experimental design: A review. Statist, Sci., 10(3):273-304.
Cockayne, J., Oates, C., Sullivan, T., and Girolami, M. (2017). Bayesian Probabilistic Numerical Methods. ArXiv e-prints, stat.ME 1702.03673.
Cucker, F. and Smale, S. (2002). On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1-49.
de la Peña, V. H., Klass, M. J., and Lai, T. L. (2009). Theory and applications of multivariate self-normalized processes. Stochastic Processes and their Applications, 119(12):4210 4227.
Draper, N. R. and Smith, H. (2014). Applied Regression Analysis. John Wiley and Sons.
Elfving, G. (1952). Optimum Allocation in Linear Regression Theory. Annals of Mathematical Statistics, 23(2):255-262.
Fedorov, V. V. and Hackl, P. (1997). Model-Oriented Design of Experiments Valerii V. Fedorov Springer. Springer-Vette New York.

---

Gabrielsson, J. and Weiner, D. (1995). Pharmacokinetic and pharmacodynamic data analysis. Trends in Pharmacological Sciences, 16(4):143.
Gaffke, N. (1987). Further characterizations of design optimality and admissibility for partial parameter estimation in linear regression. Ann. Statist., (5(3):942-955)
González, J., Vujačié, I., and Wit, E. (2014), Reproducing kernel hilbert space based estimation of systems of ordinary differential equations. Pattern Recognition Letters, 45:26-32.
Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. (2005). Measuring statistical dependence with hilbert-schmid norms. In International conference on algorithmic learning theory, pages 63-77. Springer.
Huszár, and Duvenaud, D. (2012). Opeimally-weighted herding is bayesian quadrature. arXiv preprint arXiv: 1664.
Khalil, H. (2002). Nonlinear Systems. Patience Hall.
Khamaru, K., Deshpande, Y., Mackey, L., and Wainwright, M. (2021). Near-optimal inference in adaptive linear regression. arXiv preprint vrXiv:2107.02266.
Kirschner, Mutný, M., Hiller, N., Ischebeck, R., and Krause, A. (2019). Adaptive and safe bayesian optimization in high dimensions via one-dimensional subspaces. ICML 2019.
Krafft, O. (1983). A matrix optimization problem. Linear Algebra and its Applications, 51:137- 142.
Laurent, B. and Massart, P. (2000). Adaptive estimation of quadratic functional by model selection. Annals of Statistics, pages 1302-1338.
Lederer, A., Capone, A., Beckers, T., Umlauft, J., and Hirche, S. (2021). The impact of data on the stability of leaming-based control. Conference on Learning for Dynamics and Control.
Leykekhman, D., Vexler, B., and Walter, D. (2020). Numerical analysis of sparse initial data identification for parabolic problems. ESAIM: Mathematical Modelling and Numerical Analysis.
Mutný, M., Johannes, K., and Krause, A. (2020). Experimental design for orthogonal projection pursuit regression. AAA/2020.
Mutný, M. and Krause, A. (2018). Efficient high dimensional bayesian optimization with additivity and quadrature fourier features. In Neural and Information Processing Systems (NeurIPS).
Owhadi, H. and Scovel, C. (2016). Toward machine Wald. In Springer Handbook of Uncertainty Quantification, pages 1-35. Springer.
Pukelsheim, F. (2006). Optimal Design of Experiments (Classics in Applied Mathematics) (Classies in Applied Mathematics, 50). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
Pukelsheim, F. and Studden, W. (1993). E-optimal designs for polynomial regression. The Annals of Statistics, pages 402-415 415.
Rasmussen, C. and Williams, C. (2006). Gaussian processes for machine learning, vol. 1. The MIT Press, Cambridge, doi, 10:501290065044001899
Rusmevichientong, P. and Tsitsiklis, J. N. (2010). Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411
Settles, B. (2009), Active learning literature survey. University Wisconsin-Madison Department of Computer Sciences.
Shoham, N. and Avron, H. (2020). Experimental design for overparameterrize learning with application to single shot deep active learning. arXiv preprint UrXiv:2009.12822
Silvey, S., Titterington, D., and Torsney, B. (1978). An algorithm for optimal designs on a design
space. Communications in Statistics Theory and Methods, 1799399379
12

---

Srinivas, N., Krause, A.. Kakade, S. M., and Seeger, M. (2010). Gaussian process optimization in the bandit setting: No regret and experimental design. International Conference on Machine Learning.
Szepesvari, C. and Lattimore, (2020). Bandit Algorithms. Cambridge University Press.
Todd, M. J. (2016), Minimum-Voluna Ellipsoids: Theory and Algorithms. SIAM, mos-siam series optimization edition.
Umlauft, J., Pöhler, I.., and Hirche, S. (2018). An uncertainty-based control Iyaрunov approach for control-affine systems modeled by gaussian process. IEEE Control Systems Letters, 2(3):483-488
Valko, M., Munos, R., Kveton, B., and Kocak, T. (2014). Spectral bandits for smooth graph functions. In International Conference on Machine Learning, pages 46 54.
Wendland, H. (2004). Scattered data approximation, volume 17. Cambridge university press.
Zhang. F. (2011). Matrix Theory: Basic Results and Techniques. Springer Science & Business Media.
13

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] No. Theory paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URI.)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] It's insignificant. I just used a personal machine.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'ne using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "gGt887aP7yj", "reviewer": "Reviewer_Bcdv", "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.", "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.\n2. 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).\n3. Line 49: What is the $f$ in $f^\\intercal \\Phi(x) \\geq 0$? Is this some function of $\\theta$? Or a typo?\n4. 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.\n5. 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”?\n6. 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.\n\nI don't foresee any negative social consquences of this work.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nSome typos:\n1. Line 44: “depends among other things” -> “depends among other things on”\n2. Line 80: “change in f compared noise” -> “change in f compared to noise”\n3. 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NzA14FGddDA", "reviewer": "Reviewer_61h2", "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.", "questions": "I find some writing problems, some rendering the relevant sections difficult for me to follow:\n\n* the term \"simple reverting law with a known gain\" in Line 366.\n* the term \"uncertain\" in Line 368.\n* script \"O\" from Line 371 to Line 391, while this symbol was overloaded before as the big-O notation.\n* 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.\n* the V0 norm, in Lines 118-119 is not defined.\n* A design does not maximize Tr(W), but 1/Tr(W^{-1}).\n* 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.\n* I believe that the matrix V0 in Equation (5) is not defined.\n* It seems that X is a matrix, but it is used as a space in Section 4.\n* The concepts \"support\" and \"allocation\" need to be defined, e.g., in Proposition 5.\n* In Theorems 1 and 6, matrices V-dag are overloaded to denote different objects.\n* In the proof of Theorem 6, Ik and script I both represent the identity matrix.\n* Instead of using an upper bound of the Chi-square probability for Theorems 1 and 2, why not just use its quantile function?\n* 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:\nThere is no obvious limitations about the methodologies studied.\n\nNegative societal impact:\nThis paper is about a theoretical research, which has no direct negative societal impact.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* comprehensive discussion of the application background\n* The problem of optimal design for linear models in RHKS is important and of interest to a broad audience.\n* The problems in Sections 7.2 and 7.3 appear to be new and significant applications of kernel methods.\n\nWeaknesses:\n* There might not be sufficiently new results, especially compared against the high standard of NeurIPS.\n\n=====================================\n\nAfter 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7UWisBCLR8D", "reviewer": "Reviewer_tM79", "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.", "questions": "I do not have very specific comments or questions for the authors. But several papers are recommended to be cited:\n\n1. Optimal design using SoS hierarchy: https://arxiv.org/pdf/1706.04059.pdf\n\n2. Nonparametric function estimation: https://arxiv.org/pdf/1812.05553.pdf https://www.sciencedirect.com/science/article/abs/pii/016771528490066X\n\nThere 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.\n\n", "limitations": "The potential limitations are appropriately discussed.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.\n\nThe theoretical results of this paper are sound and the writing is succinct and clear.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept