CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions
Authors: Juan M Cardenas
Ben Adcock
Nick Dexter
Venue: NeurIPS 2023 spotlight (2023)
Keywords: active learning
regression
arbitrary data
leverage scores
Christoffel functions
generative models
Magnetic Resonance Imaging (MRI)
Physics-Informed Neural Networks (PINNs)
TL;DR: We introduce a general framework for active learning in regression problems that allows for general types of data and optimal sampling via so-called generalized Christoffel functions.

Abstract: We introduce a general framework for active learning in regression problems. Our framework extends the standard setup by allowing for general types of data, rather than merely pointwise samples of the target function. This generalization covers many cases of practical interest, such as data acquired in transform domains (e.g., Fourier data), vector-valued data (e.g., gradient-augmented data), data acquired along continuous curves, and, multimodal data (i.e., combinations of different types of measurements).  Our framework considers random sampling according to a finite number of sampling measures and arbitrary nonlinear approximation spaces (model classes). We introduce the concept of \textit{generalized Christoffel functions} and show how these can be used to optimize the sampling measures. We prove that this leads to near-optimal sample complexity in various important cases. This paper focuses on applications in scientific computing, where active learning is often desirable, since it is usually expensive to generate data. We demonstrate the efficacy of our framework for gradient-augmented learning with polynomials, Magnetic Resonance Imaging (MRI) using generative models and adaptive sampling for solving PDEs using Physics-Informed Neural Networks (PINNs).

CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions
Ben Adcock Department of Mathematics Simon Fraser University ben Sen_adcock@sfu.c ca
Juan M. Cardenas Department of Mathematics
Simon Fraser University
juan_manuel cardenas@sfu.com ca
Nick Dexter
Department of Scientific Computing
Florida State University nick dexter@fsu.ceem edu
Abstract
We introduce general framework for active learning in regression problems. Our framework extends the standard setup by allowing for general types of data, rather than merely pointwise samples the target function. This generalization covers many cases of practical interest, such as data acquired in transform domains (c.g., Fourier data), vector-valued data (c.g., -ughinnte data), data acquired along continuous curves, and, multimodal data (i.e., combinations of different types of measurements). Our framework considers random sampling according to finite number of sampling measures and arbitrary nonlinear approximation spaces (model classes). We introduce the concept of generalized Christoffel functions and show how these can be used optimize the sampling measures. We prove that this leads to near-optimal sample complexity in various important cases. This paper focuses applications in scientific computing, where active learning often desirable, since it is usually expensive to generate data. We demonstrate the efficacy our framework for sradient-augment
learning with polynomials, Magnetic Resonance Imaging (MRI) using generative models and adaptive sampling for solving PDEs using Physics-Informe Neural Networks (PINNs).
Introduction
The standard regression problem in machine learning involves learning approximation to function f* D S RRd - from training data (0.))) D R. The approximation sought in set of functions F, typically termed model class, hypothesis set approximation space, and is often computed by minimizing the empirical error (or risk) over the training set, i.e.,
T
f E arrgmin JEF TI
P.0.)
In this paper, we develop a generalization of this problem. This allows for general types of data (i.e., not just discrete function samples), including multimodal data, and random sampling from arbitrary distributions. particular, this framework facilitates active learning by allowing one to optimize the sampling distributions to obtain near-best generalization from as few samples possible.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Motivations
Typically, the sample points 0, in the above problem are drawn i.i.d. from some fixed distribution. Yet, in many applications of machine learning there is substantial freedom to choose the sample points in a more judicious manner to increase the generalization performance of the Iearned approximation. These applications often highly data starved, thus making good choice of sample points extremely valuable. Notably, many recent applications of machine learning in scientific computing often have these characteristics. An incomplete list of such applications include: Deep Learning (DL) for Partial Differential Equations (PDEs) via so-called Physics-Informnn
Neural Networks (PINNs)
39 61
[05 1 deep learning for parametric PDEs and operator learning [17
49 53 66 73
75 118: machine learning for computational imaging 15 79
84
88 100
and machine
learning for discovering dynamics of physical systems
24 25
109
In many such applications, the training data does not consist of pointwise samples of a target function. For example, in computational imaging, the samples are obtained through integral transform such as the Fourier transform in Magnetic Resonance Imaging (MRI) or the Radon transform in X-ray Computed Tomography (CT) [3 2545) In other applications, each sample may correspond to the value of f (or some integral transform thereof) along a continuous curve. Applications where this occurs include: seismic imaging, where physical sensors record continuously in time but discrete spatial locations; discovering governing equations of physical systems, where each sample may be a full solution trajectory [09]; MRI, since the MR scanner samples along a sequence of continuous curves in k-space 80 89 and many more. In other applications, each sample may be a vector. For instance, in gradient-augmented learning problems- with applications
PINNS for PDBs (4 120
T03 98 99], as well as various other DL settings (36] - each sample a vector in 1 containing the values of f and its gradient at 0z. In other applications, each sample may be an element of a function space. This occurs in parametric PDEs and operator learning, where each sample is the solution of PDE (i.e.. an element of Hilbert space) corresponding to the given parameter value. Finally, many problems involve multimodal data, where one has C > different types of training data. This situation occurs in various applications, including: multi- imaging systems (3 such as parallel MRI (which is ubiquitous in modern clinical practice) [5] [9]: PINNs for PDEs, where the data arises from the domain, the initial conditions and the boundary conditions; and multifidelity modelling [44 102
and learning parametric PDEs in Uncertainty Quantification (UQ) 99 56 78
82
1.2 Contributions
In this paper, we introduce general framework for active learning in which
1. f" need not be a scalar-valued function, but simply an element of a Hilbert space X;
2. the data arises from arbitrary linear operators, which may be scalar- vector-valued;
3. the data may be multimodal, arising from C' 2 1 of different types of linear operators:
4. the approximation space IF may be an arbitrary linear or nonlinear space:
5. sampling is random according to arbitrary probability measures;
6. the sample complexity, i.e., the relation between F and the number of samples required to attain near-best generalization error, is given explicitly in terms of the so-ca so-called generalized Christoffel functions of F:;
7. using this explicit expression, the sampling measures can be optimized, leading to essentially optimal sample complexity in various cases.
This framework, Christoffel Sampling for Machine Learning (CS4ML), is very general. Indeed, we are unaware of any other active learning strategy that can simultaneously address such broad class of problems. It is inspired by previous work on function regression in linear spaces [2] 34 57 60 and is also a generalization of leverage score sampling [II 32, 41 46 (50 85) for active learning. See Appendix for further discussion. generalizes these approaches by (a) considering abstract objects in Hilbert spaces, (b) allowing for arbitrary linear sampling operators, as opposed to just function samples, (c) allowing for multimodal data, and (d) considering general linear or nonlinear approximation spaces. We demonstrate its practical efficacy on diverse set of test problems. These are: (i) Polynomial regression with gradient-augmented data, (ii) MRI reconstruction using generative models and (iii) Adaptive sampling for solving PDEs with PINNs. Our solution to (iii) introduces general adaptive sampling strategy, termed Christoffel Adaptive Sampling, that can be applied to any Da-based regression problem (i.c., not simply PINNs for PDEs).

---

2
The CS4ML framework and main results
2.1 Main definitions
Let F,P) be probability space, which is the underlying probability space of the problem. In particular, our various results hold in probability with respect the probability measure P. Let X be a separable Hilbert space and X S X be normed vector subspace of X, termed the object space. Our goal is to learn an element (the object) f E Xg from training data. We consider a multi-modal measurement model in which C' > different processes generate this data. For each c = 1,..., C, we assume there is measure space (Dc.Ac, Pc), termed the measurement domain, which parametrizes the possible measurements. We will often consider the case where this is probability space, but this not strictly necessary for the moment. Next, we assume there are semi-inner product spaces Y = I,....C.. C, termed measurement spaces, to which the measurements belong, and mappings
Le De o Y.), c c=
where (Xx, Ye) denotes the space of bounded linear operators Xo - Ye. We refer Le as sampling operator for the cth measurement process. Note that we consider the sampling operators L. as fixed and specified by the problem under consideration. However, we make the following assumption, which states that we have the flexibility to query each sampling operator at an arbitrary point in the measurement domain.
Assumption 2.1 (Active learning) For each c, we may query (o()) any 0 De.
This assumption is direct extension of that made in standard active learning (see Example 2.3 below). It holds in all our main examples. Given this assumption, our approach is to selecting sample points to draw them randomly according certain sampling measures p1y....; PC (defined on Di,..., Do, respectively), which can then be optimized to ensure as good generalization as possible. To this end, we also make the following assumption.
Assumption 2.2 (Sampling measures) Each sampling measure Pe is probability measure on (De,Ad that is absolutely continuous with respect to Pa. and its Radon-Nikodym derivative is positive almost everywhere. In other words, dduc(0) = (f) dpp for some measurable function Ve D. + IR that positive almost everywhere and satisfies JD. Ve (0) (p)
We now define the training data. Let m.,.... me be the (not necessarily equal) measurement numbers, i.e., me is the number of measurements from the eth measurement process. Let θ Ω De be independent valuue random variables, where O pee for each c. For each 1....,C, let Occ. = I,..., me, be independent realizations of θg. Then the training data is
me
[(Otc, Vic) M 1i where ysce (o(O:s)(f)) E Y., i= =,...,, me C.
(2.1)
Later, in Scction we also allow for noisy mcasurements. Note that we consider the agnostic learning setting, where f & F and the noise be adversarial, as this setting is most appropriate to the various applications considered (see also (50].
Example 2.3 (Active learning in standard regression) The above framework extends the standard active learning problem in regression. In the classic regression problem, D C I is domain and = D2(D) is the space of square- integrabt functions f* D > IR with respect to a measure p. Note that P is considered fixed it is the measure with respect to which
measure the error. To embed this problem into the above framework, we let X,- C(D) be the space of continuous functions on D,
1, the measurement domain D. = D equal to the domain of the function, P1 P and the measurement space Y I (with the Euclidean inner product). We then define the sampling operator L, (0)( (0) as the pointwise evaluation operator. In particular, for a measure μ Mi satisfying Assumption 2.2 the training data (2. is (O,, I" (Q:)) with O mi.id. J.. Hence, the aim is to choose the measure (or equivalently, its Radon- Radon-Nikodyy Nikodym derivative 1/) to ensure as good generalization possible.
Next, we let I C X be a subset within which we seek to learn S We term FP the approximation space. Note this could be a linear space such as a space of algebraic or trigonometric polynomials, or nonlinear space such the space of sparse Fourier functions, space of functions with sparse
3

---

representations in a multiscale system such as wavelets, the space corresponding to single neuron model, or a space of deep neural networks. We discuss a number of examples later. Given IF and f E Xg, in this work we consider an approximation f E defined via the empirical least-squares fit
argmin f E
(o(e) live Lo(Okc)(1)
(2.2)
JEP
me
However, regardless of the method employed, one cannot expect to learn f from 2.1 without an assumption on the sampling operators. Indeed, consider the case Le = 0, Vc. The following assumption states that the sampling operators should be sufficiently 'rich' to approximately preserve X-norm. As we see later, this is natural assumption, which holds many cases of interest.
Assumption 2.4 (Nondegeneracy of the sampling operators) The mappings L. are such that the maps De - Ve + (f) are measurable for every í E % Moreover, the functions Do + +,,,0 (f)(1 are integrable and satisfy, for constants
S 3 < oc,
all s Σ / ((,(0) dp.(0) S BIS
Vf E X
(2.3)
In order to successfully learn f from the samples 2.J we need to (approximately) preserve nondegeneracy when the integrals in (2.3) are replaced by discrete sums. Notice that
C Σ
/|| < E
v(Orc) LL (10(0)
AS E Xo:
(2.4)
where E denotes the expectation with respect to all the random variables (i,e),e-- Our subsequent analysis involves deriving conditions under which this holds with high probability. We shall say that empirical nondegeneracy holds with constant 0 < 1 for draw (Ore)ie if
mhe
(1 (1-c)alffl3 S
Lo (o())) (1+ +18+1 VfeF-E, (2.5) v(Oic)
mc
where F Ff fi. f2 E F}. See Appendix A for some background on this definition.
Finally, need one further assumption. This assumption essentially says that the action of the sampling operator L, on is nontrivial, in the sense that, for almost all f E D.. there exists a f e F that has nonzero measurement (O) This assumption is reasonable, since without it, there is little hope to fit the measurements with an approximation from the space F.
Assumption 2.5 (Nondegeneracy of F with respect to I.)) For each = 1,...,C and almost ev- ery 0g De, there exists element fe such that (f.) + 0.
2.2 Summary of main results
The goal of this work is to derive sampling measures that ensure quasi-optimal generalization bound from as little training data as possible. These measures are given terms of the following function.
Definition 2.6 (Generalized Christoffel function). Let X, be normed vector space, W be semi- inner product space, (D, A. p) be a measure space, L: D + B(%o, Y) be such that the function D - 0 + (f) measurable for every Xo and IF Xo. + {0). The Generalized Christoffel functioo of If with respect to L is the function
K (F) sup(
f EEE, f+0, 0E D.
F {0). then we set K (0) = O. Further, we also define <(F) = Jp (P)
In the standard regression problem (see Example 2.3
Definition 2.6 reduces
(0) = sup (up() L3(D)* : F, / /0 0 D.
(2.6)

---

This is well-known object, which is often referred to as the Christoffel function when F is linear subspace. It also equivalent (up scaling) to the leverage score function. See Appendix for further discussion. Definition extends these notions from linear subspaces to nonlinear spaces and from pointwise samples to arbitrary sampling operators T..
To state our main result, we also need the following. Given a > 0 we define the shrinkage operator V
To X + X by (f) min
X.
Theorem 2.7. Consider the setup of Section 2.1 where F F
is a union of E N subspaces of dimension at most n E N. Let Ke C l,...; C. be as in Definition 2.6 for (D, A. p) = Aes Pe) and L = Le. Suppose that the (FF FF) are integrable, define
dp)(0) = (F(F -
(F FF), c= c=1,...,C,
(2.7)
and suppose that
mc = a KF F)
F) (oog(nd/0)) c=1...,,C C
(2.8)
for some 0 8 < 1. Then the following hold.
(i) Empirical nondegeneracy (.5) holds with 1/2 with probability at least 1 1-6. 6.
(ii) For any f E Xo. Il S L, the estimator f f= (if),, where f as in (.2 satisfies
E|I f11ix - (3/o) inf I| f1 +
(2.9)
JE3
(ii) The total number of samples m = mm + ... + mc is at most log-linear in nd, namely,
m S (8/a) nd log(2nd/o).
(2.10)
The choice (.7) is particular type of importance sampling, which we term Christoffel Sampling (CS). In particular, for the standard regression problem (see Example 2.33 the resulting measure is
du²(2 (1) x K(F (V) dp(u).
(2.11)
where KF (v) is as in (2.6) with replaced by F F. As we discuss in Appendix A.2 this
is equivalent to leverage score sampling for the standard regression problem (see, c.g.. 22 34
32 46 60). Therefore, Theorem 2.7 can be considered a generalization of leverage score sampling from standard regression significantly more general types of linear, multimodal measurements. Specifically, it considers the general setting of arbitrary Hilbert spaces X, nonlinear approximation spaces F, and C > 1 arbitrary, linear sampling operators Lg taking values in arbitrary semi-inner product spaces Y. To the best of our knowledge this generalization is new. We remark, however, that Theorem 2.7 is also related to the recent work [43). See Appendix A.3 for further discussion.
The sampling measure 2.7 is 'optimal' in the sense that it minimizes a sufficient condition over all possible sampling measures Me (see Lemma 4.6). Doing so leads to CS and Theorem 2.7 The measurement condition (2.10) states that CS leads to a desirable sample complexity bound (2.
that is at worse log-lineas in nd. In particular, when d 1 (i.c.. IF is linear space) the sample complexity is near-optimal (and in this case, one also has F - F = IF). In general, the bound 10.10 is near-optimal in terms of when d is small (and independent of n). Unfortunately, d can be large in important cases such as sparse regression. In this case, however, the linear dependence on d in (2.10) which follows from (.88 via the crude estimate Σ (F - F) < 6nd can be lessened by using the specific structure of the approximation space. See Appendix A.4
Theorem 2.7 is a simplification and combination of our several main results. In Theorem 4.2 consider more general approximation spaces, which need not be unions of finiteddimensionll subspaces. See also Remark 4.5 Finally, we note that ff only differs from ff by a shrinkage operator, which is technical step needed to bound the error in expectation. See Section An 'in probability' bound can be obtained without this additional complication, albeit with less suceinet right-hand side.
3 Examples and numerical experiments
Theorem 2.7 shows that CS can be near-optimal active learning strategy. We now show its efficacy via a series of examples. These examples also highlight how the generality of the framework allows it to tackle wide range of problems. We consider cases where the theory applies directly and others
5

---

10
10
tes: eroor BLA)
1n0: erce FILF)
1oo: ercer BLD
10
10
10
10
10
10"
10FT 10" 10
10
10
10 10a
Figure 1: CS for gradient-augmentee polynomial regression. Plots of the average regression enorr versus mn for MCS and CS for -aggeeett--emmmeeeeeeeeeeeeeedde polynomial regression of the function (*( exp( exp(-(0)+ + +0.. +0a) (2d))
for = 2, 4, (left right). both cases, we use scaling m [max [n., n (n)) / 1)]. this and other figures, the solid lines show the mean value and the shaded region indicates one standard deviation. Sec Scction B.5 for for further details.
where it does not. In all cases, present performance gains over inactive learning, i.c., Monte Carlo Sampling (MCS) from the underlying probability measure. Another matter we address is how to sample from the measures 2.7 in practice, this being very much dependent the problem considered. Full experimental details for each application can be found in Appendices B B
3.1 Polynomial regression with gradient-augmennte data
Many machine learning applications involve regressing smooth, multivariate function using a model class consisting algebraic polynomials. Often, the training data consists of function values. Yet, as noted in Section 1.1 there are many settings where one can acquire both function values and values of gradient. this case, the training data takes the form {0., ((,)), [( C Rd. x Rd+11 As explain in Appendix B.J this problem fits into standard Gaussian measure on Rd
framework with C = 1, where p is the H,((C (I2) ) is the Sobolev space of weighted square-interrable functions with weighted square qquare-ntterabbee first-order derivatives and Y = Rd+1 with the Euclidean inner product. It therefore provides a first justification for allowing non-scalar valued sampling operators. Note that several important variations on this problem also fit into our general framework with C 1. See Appendix B.7
We consider learning a function from such training data sequence of nested polynomial spaces F1 C F2 C .... These spaces based hyperbolic cross index sets, which are particularly useful in multivariate polynomial regression tasks 37]. See Appendix B.2 for the formal definition.
In Fig. | we compare gradient-augmentte polynomial regression with CS versus MCS from the Gaussian measure p. See Appendices B.3
B.3 for details on how we implement CS this case. CS gives dramatic improvement over MCS. CS is theoretically near-optimal in the sense of Theorem -i... it provably yields log-linear sample complexity since the approximation spaces are linear subspaces in this example. On the other hand, MCS fails, with the error either not decreasing or diverging. The reason is the log-linear scaling, which is not sufficient to ensure generalization error bound of the form (2.9) for MCS. As demonstrate in Appendix [B.6] MCS requires much more severe scaling of m with n to ensure a generalization bound of this type.
3.2 MRI reconstruction using generative models
Reconstructing an image from measurements is a fundamental task in science, engineering and industry. In many applications - in particular, medical imaging modalities such as MRI - one wishes to reduce the number of measurements while still retaining image quality. As noted, techniques based on DL have recently led to significant breakthroughs in image recovery tasks. One promising approach involves using generative models [6 20 671. First, generative model is trained database relevant images, e.g., brain images the case of MRI. Then the image recovery problem is formulated as a regression problem, such (.2). where F is the range of the generative model. Note that in this problem, the training data consists of a finite set of frequencies and the corresponding values of the Fourier transform of the unknown image.
As we explain in Appendices C. this problem fits into our general framework. In Fig. we demonstrate the efficacy of CS for Fourier imaging with generative models. In this example, the

---

40
Incrnee PSSTR (10)) frusse 20
PSN0 20
10
10
3mm/
92
73
80
15
0.55
1.25
9.25 7.0
Image nimbee
sampling peroentag
Figure 2: CS for MRI reconstruction using generative models. Plots of (left) the average PSNR vs. image number of the 3-dimensional brain MR image for both CS and MCS methods at 0.125%, 0.375%, and 0.625% sampling percentages, (middle) the average PSNR computed over the frames 30 90 of the image vs. sampling percentage for both CS and MCS methods, and (right) the empirical function K used for the CS procedure.
generative model was trained database of 3D MRI brain images (see Appendix This experiment simulates 3D image reconstruction problem in MRI, where the measurements are samples of the Fourier transform of the unknown image taken along horizontal lines in k-space (a sampling strategy commonly known as phase encoding). The active learning problem involves judiciously choosing m horizontal lines in k-space enhance the generalization performance of the learning procedure. In Fig. 2 we compare the average Peak Signal-to-Noise Ratio (PSNR) versus frame (i.e., 2D image slice) number for CS versus MCS (i.e., uniform random sampling) for reconstructing an unknown image. We observe significant improvement, especially in the challenging regime where the sampling percentage (the ratio of the number of measurements the image size) is low.
This example lies close to main theorem, but is fully covered by it. See Appendix space (the range of generative model) is not a finite union of subspaces. However, it known that certain generative models (namely, those based ReLU activation functions)
+ The
subsets of unions of subspaces of controllable size [16]. Further, we do not sample exactly from (2.7) ) in this case, but rather empirical approximation to it (see Appendix C.4). Nevertheless, our experiments show significant performance gain from CS in this case, despite it lying strictly outside of our theory.
This application justifies the presence of arbitrary (i.e., non non-pointwise) sampling operators in framework. is another instance of non-scalar valued sampling operators, since each mcasurement is vector of frequencies values along horizontal line in k-space. Fig. conssierss C = sampling operators. However, as we explain Appendix C.7 the important extension of this setup to parallel MRI (which is standard in clinical practice) be formulated in our framework with C' > 1.
3.3 Adaptive sampling for solving PDEs with PINNS
In our final example, we apply this framework to solving PDEs via Physics- Inforre-I Neural Networks (PINNs). PINNs have recently shown great potential and garnered great interest for approximating solutions of PDEs 42 105 112). It is typical in PINNs to generate samples via Monte Carlo Sampling (MCS). Yet, this suffers from a number of limitations, including low accuracy.
35] to devise new We use this general framework combined with the adaptive basis viewpoint adaptive sampling procedure for PINNs. Here, a Deep Neural Network (DNN) with n nodes in its penultimate layer is viewed as an element of the linear subspace spanned the functions defined by this layer's nodes. Our method then proceeds as follows. First, we use an initial set of mi samples and train the corresponding PINN VI = V Then, we use the adaptive basis viewpoint to construct subspace F1 with V F1. Next, we draw m2 mi samples using CS for the subspace F1, and use the set of m = my samples to train new PINN v = 22 using the weights and biases of Vi as the initialization. We then repeat this process, alternating between generating new samples CS and retraining the network, to obtain sequence of PINNs V,, V2... approximating the solution of the PDE. We term this procedure Christoffel Adaptive Sampling (CAS). See Appendices DD. for further information.
7

---

15"
50.00
712
Figure 3: CAS for solving PDEs with PINNs. Plots of (left) the average test enror E(u" versus the number of samples used for training tanh and sigmoid 5 50 DNNs using CAS (solid linc) and MCS (dashed line), (middle) the samples generated by the CAS for the tanh 5 50 DNN and (right) the samples generated by CAS for the sigmoid x DNN, The colour indicates the density the points.
In Fig. 3 we show that this procedure gives a significant benefit over MCS in terms the number of samples needed to reach given accuracy. See Appendix [D5 further details the experimental setup. Note that both approaches use the same DNN architecture and are trained in exactly the same way (optimizer, learning rate schedule, number of epochs). Thus, the benefit is fully derived from the sampling strategy. The PDE considered (Burger's 's equations) exhibits shock formation as time increases. As be seen in Fig. CAS adapts the unknown PDE solution by clustering samples near this shock, to better recover the solution than MCS.
As we explain in Appendix D.2 this example also justifies C >> 1 in our general framework, as we have three sampling operators related to the PDE and its initial and boundary conditions. We note, however, that this example falls outside our theoretical analysis, since the sampling operator stemming from the PDE nonlinear and the method is implemented in an adaptive fashion. In spite of this, however, still see nontrivial performance boost from the CS- CS-based scheme.
4 Theoretical analysis
In this section, we present our theoretical analysis. Proofs can found in Appendix E
4.1 Sample complexity
We first establish a sufficient condition for empirical nondegeneracy (2.5) to hold in terms of the numbers of samples m. and the generalized Christoffel functions of suitable spaces.
Definition 4.1 (Subspace covering number). Let (X, |1x be maasiiseminormeee vector space, F be subset of X, n E No and 2 0. A collection of subspaces Er...., Fa of of dimension at most n is a (Il-llx- n, t)-subspace covering of F if for every f E F there exists j j E (1...., ...... d) and fy E F, n F such that |l fillx < t. The subspace covering number (FF, Il-IIg. n, of the smallest d such that there exists (II-Ilx, n. f)nnn..tsss.. t)-subspace covering of F consisting of d subspaces.
In this definition, consider eero-dimensional subspace singleton {x) C X. Therefore, the subspace covering number ((F,, 11- 0, f) is precisely the classical covering number A A(F, Il t). We also remark that if F = -p= F, is itself a union of d subspaces of dimension at most n. then (IF,, I1-llx n', d for any 2 0 and n' 2 n.
We now also require the following notation. If C X, set B(F) (ffIlfilx E E(J)).
Theorem 4.2 (Sample complexity for empirical nondegeneracy). Consider the setup of Section 2. Let F Xo, E No. 0 6, < 1 and Fi, ......... Fa be a (Il-III, t)-subspace covering of B(F F).
where /ae/2 and III D ess sussu (..) /
/v(O))) Suppose that
me 2 Ce/2
ess sup K K (F)))()) log(2d max (n, 1)/8), Ve= (4.1)
Orupe
where 0222 is in
E.6 and F = U Then 2.5 holds with probability at least 1 - 6.
8

---

This theorem gives the desired condition (4.1) for empirical nondegeneracy (.5)) It is interesting understand when this condition can be replaced by one involving the function K, evaluated over IF rather than its cover E. We now examine two important cases where this is possible.
Corollary 4.3 (Sample complexity for unions of subspaces), Suppose that IF - F U|=1 F3 is union of d subspaces of dimension at most n E N. Then (4.1) is equivalent to
mc 2 Ce/2 o ess sup {K.(F (O)0) (0)) log(2nd/6); c= C.
Brupo
Corollary 4.4 (Sample complexity for classical coverings). Consider Theorem 4.2 with 0. Then (4. is implied by the condition
C. m. 2 ce/2 a-t ssssup (K.(F (F)))-()))))((0)) log(2d/6), e
Orupo
Remark 4.5 Theorem 4.2 is formulated generally in terms of subspace coverings. This is done so that the scenarios covered in Corollaries 4.3 and 4.4 are both straightforward consequences. Our main examples in Section are based on the (unions of) subspaces case. While this assumption is relevant for these and many other examples, there are some key problems that do not satisfy it. For example, in low-rank matrix (or tensor) recovery [27] (38 T08 117]. the space F of rank-r matrices (or tensors) is not a finite union of saite-dimensionall subspaces. But tight bounds for its covering number are known [26 [06], meaning fits within the setup of Corollary 4.4
4.2 Christoffel sampling
Theorem 4.2 reduces the question of identifying optimal sampling measures to that of finding weight functions Ve that minimize the corresponding essential supremum in (4.1). The following lemma shows that this is minimized by choosing Ve proportional to the generalized Christoffel function.
Lemma 4.6 (Optimal sampling measure). Let L. F, (FF) and r(FF) < oc be as in Definition 2.6
Suppose that for almost every 0 E D there exists f E F such that l())(f) # 0. Then ((ssup(())())///// 0-ip
2 s<(F)
for any measurable v D >> IR that is positive almost anywhere and satisfies Sp v() dp(() 1. Moreover, this optimal value is atlained by the function v² (0) ((F))))/<(F) 0 D.
In view of this lemma, to optimize the sample complexity bound
4.1 we choose sampling measures
(0) (F) (0) (F)
I.
(4.2)
As noted, we term this Christoffel Sampling (CS). This leads to sample complexity bound
m. 2 Ce/2 aa at..a_k..kk.. (F) l2g(2d m 1)/5), c I,...,C. C.
(4.3)
In the case of subspaces (or union thereof with small d), this approach leads to a near-optimal sample complexity bound for the total number of measurements m == mi +... mm.
mc.
Corollary 4.7 NNearopptmal sampling for unions of subspaces). Suppose that F - = L a union of d subspaces of dimension at most n E N. Then Σ Kc(F FF S Bdn. Therefore, choosing the sampling measures as in (4.2) with F = - and the number of samples me I Ce/2 a 1. .lFFF F) log(2nd/8) leads the overall sample complexity bound
m S Ce/2 (8/a)) -n-d log(2nd/8).
We note in passing that Ee= (F-FF 2 an/p whenever dim(Y, < E N, Ve. See Theorem E.4 Therefore, the sample complexity bound least Oc. (n log log(nd/8)).
worth comparing these bounds with MCS. Suppose that the pe's 's are probability measures, in which case MCS is well defined. For MCS, we have V. = 1, Ve, and therefore the corresponding measurement condition is
me 2 Ce/2 a-.1 (F) max 1)/06), c=
where (FF = ess esssupa-p, K. (0) > (F). Comparing with 4.3). we conclude that the benefit of CS over MCS terms of sample complexity corresponds to the difference between the supremum of the Christoffel function (i.e., (F) and its average (i.e., k.. (F)). Thus, if K, has sharp peaks as it does, for instance, in Fig. 2 one expects significant improvement from CS over MCS.

---

4.3 Generalization error bound and noisy data
Thus far, we have derived CS and shown parts (i) and (iii) of Theorem 2.7 In this section we establish the generalization bound in part (ii). For additional generality, we now consider noisy samples
Vic ((())))())) + esc E Ye: i i= 1=,,.... Th c= 1..... C,
(4.4)
where the ete represent measurement noise (see Remark [Er term). We also consider inexact minimizers. Specifically, we say that f E is a y-minimizer of (222) for some 7 > 0 if it yields value of the objective function that is within of the minimum value. For example, f may be the output of some training algorithm used to solve (2.2)
Remark|E.6Jfor some further discussion on the noise
Theorem 4.8. Let 0- e, < 1 and consider the setup of Section 2.7 except with noisy data 4.4) Suppose that (4. 1 holds and also that Po(Do) < oc, Ve. Then, for any I E Xo and a 2 |[ llx the
estimator f = To (f), where f is a y-minimizer of 2.2 satisfies
E - f1 $
1 (1-c)a)
43
inf I1
f11x + 40
+
12
N + (1 (1-c)a²
4
JEB
(1 c-c
where N = >e
PD( mr
leiell:.
cmml
5 Conclusions, limitations and future work
We conclude by noting several limitations and areas for future work. First, in this work, we have striven for breadth- i.e., highlighting the efficacy of CS4ML across a diverse range of examples - rather than depth. Our aim is to show that the well-known ideas for active learning in standard regression (e.g.. leverage score sampling) can be extended to very general setting. We do not claim that CS is the best possible method for each example, and as such, our experimental results only compare against (inactive) MCS. In each application considered. there are other domain- strategies that are known to outperform MCS. See [5] 6 22, 55 74 104 [II] and references therein 3 in the case of PINNs. CS is a general framework. and is arguably more theoretically grounded and less heuristic than some such methods. Nonetheless, further investigation is needed to ascertain which method is best in each setting. In similar vein, while Figs. B show significant performance gains from our method, the extent of such gains depends heavily the problem. In Appendices (nd we discuss cases where the gains far more marginal. In the PINNs example in particular, additional studies are needed to see if CAS leads to benefits across a wider spectrum of PDEs. Moreover, there is the intriguing possibility of using CS as the starting point for more advanced active learning schemes- - for example, by generalizing the linear- sample sparsification techniques of [32] or the 'boosting' techniques of (58).
for Fourier imaging, and [00 52
51
86
Second, as noted previously, a limitation of our theoretical analysis is the log-linear scaling with respect to the number of subspaces d (sce Theorem 2.7] part (iii).. While this can be overcome in cases such as sparse regression (see Appendix A.4) we expect a more refined theoretical analysis may be able to tackle this problem in the general setting. Another limitation of our analysis is that the sample complexity bound in Theorem 4.2 involves Ke evaluated over the subspace cover F., rather than simply F IF itself. We anticipate this can also be improved through a more sophisticated argument. This would help close the theoretical gap in the generative models example considered in this paper. Another interesting theoretical direction involves reducing the sample complexity from log- lon-linear to linear (when FF is linear subspace), by extending, for example, [32]
Finally, we reiterate that our framework and theoretical analysis are both very general. Consequently, there are many other potential problems to which we can apply this work. As noted, the main practical hurdle in applying this framework to other problems is to determine how to sample from the optimal measure (2.7) or some computationally tractable surrogate. Some other problems of interest include low-rank matrix or tensor recovery, as mentioned briefly in Remark 4.5 sparse regression using random feature models, as was recently developed in [64, active learning for single neuron models, as developed in [50], and operator learning [17 73. These are interesting avenues for future work.
10

---

Acknowledgments and Disclosure of Funding
BA acknowledges the support of the Natural Sciences and Engineering Research Council of Canada of Canada (NSERC) through grant (GPIN-20211611661 ND acknowledges the support of Florida State University through the CRC 2022-2023 FYAP grant program.
References
[1] Adcock, S. Brugiapaglia, and G. Webster. Sparse Polynomial Approximation of High- Dimensional Functions. Comput, Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2022.
[2] B. Adcock and J. M. Cardenas, Near-optimal sampling strategies for multivariate function approximation on general domains. SIAM J. Math. Data Sci., 2(3):607-630, 2020.
[3] B. Adcock, J. M. Cardenas, and Dexter. CAS4DL; Christoffel adaptive sampling for function approximation via deep learning. Sampl. Theory Signal Process. Data Anal., 20(21):1-29, 2022.
[4] B. Adcock, J. M. Cardenas, N. Dexter, and S. Moraga. Towards optimal sampling for learning sparse approximation high dimensions. A. Nikeghbali, Pardalos, Raigorodski,, and T. M. Rassias, editors, High Dimensional Optimization and Probability, volume 191. Springer Optim. Appl., 2022.
[5] B. Adcock and A. C. Hansen. Compressive Imaging: Structure, Sampling, Learning. Cam- bridge University Press, Cambridge, UK, 2021.
[6] Adcock, A. C. Hansen, C. Poon, and B. Roman. Breaking the coherence barrier: new theory for compressed sensing. Forum Math. Sigma, 5:e4, 2017.
[7] H. Aggarwal, M. P. Mani, and M. Jacob. MoDL: Model-based deep learning architecture for inverse problems. IEEE transactions medical imaging, 38(2):394-405, 2018.
[8] A. Alaoui and M. W. Mahoney. Fast randomized kernel ridge regression with statistical guarantces. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[9] A. K. Alekseev, I. M. Navon, and M. E. Zelentsov. The estimation of functional uncertainty using polynomial chaos and adjoint equations. Internat. Numer. Methods Fluids, 63):3)328 341, 2011.
[10] A. C. Aristotelous, F. C. Mitchell, and V. Maroulas. ADLGM: An efficient adaptive sampling deep learning Galerkin method. J. Comput. Phys, page 11 111944 2023.
[11] H. Avron, M. Kapralov, C. Musco, C. Musco, A. Velingker, and A. Zandieh. Random Fourier features for kernel ridge regression: approximation bounds and statistical guarantees. Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 253-262. PMLR, 2017.
[12] H. Avron, M. Kapralov, C. Musco, C. Musco, Velingker, and A. Zandich. Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1051-1063, New York, NY, USA, 2019. Association for Computing Machinery.
[13] H. H. Barrett and K. J. Myers. Foundations of Image Science. Intersinntrsccience, Hoboken, NJ, 2004.
[14] C. Basdevant, M. Deville, P. Haldenwang, J. Lacrouix, J. Ouazzani, R. Peyret, P. Orlandi, and Patera. Spectral and finite difference solutions of the Burgers equation. Comput. Fluids, 14(1):23-41, 41, 1986.

---

[15] A. Berk. Deep generative demixing; Error bounds for demixing subgaussian mixtures of Lipschitz signals. In ICASSP 2021-2021 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pages 4010-4014. IEFE, 2021.
[16] A. Berk, S. Brugiapaglia, B. Joshi, Y. Plan, M. Scotte, and O. Yilmaz. A coherence parameter characterizing generative compressed sensing with Fourier measurements. IEEE J. Sel. Areas Inf. Theory, 303):502-512, 2023.
[17] K. Bhattacharya, N. Hosseini, B. Kovachki, and A. Stuart. Model reduction and neural networks for parametric PDEs. J. Comput. Math., 7:121-157, 2021.
[18] J. Bigot, C. Boyer, and P. Weiss. An analysis of block sampling strategies in compressed sensing, IEEE Trans. Inform. Theory, 62(4)) 2016.
[19] J. Blechschmidt and O. G. Ernst. Three ways to solve partial differential equations with neural networks-a review. GAMM-Mitteillngen, 44(2)=2202100)) 100066, 2021.
[20] A. Bora, A. Jalal, Price, and A. G. Dimakis. Compressed sensing using generative models. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pages 537-546. PMLR, 06-11 Aug 2017.
[21] C. A. Bouman. Foundations of Computational Imaging: A Model-Based Approach. SIAM, Philadelphia, PA, 2022.
[22] C. Boyer, P. Weiss, and J. Bigot. An algorithm for variable density sampling with block- constrained acquisition. SIAM J. Imaging Sci., 1Q2:108001117,, 2014.
[23] S. Brugiapaglia. S. Dirksen, H. C. Jung, and H. Rauhut. Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs. Appl. Comput. Harmon. Anal., 53:231-266 2021.
[24] S. L. Brunton and J. N. Kutz. Data-Driven Science and Engineering. Cambridge University Press, 2 edition, 2022.
[25] S. L. Brunton and J. N. Kutz. Machine learning for partial differential equations. CoRR, abs/2303.17078, 2023.
[26] J. Candès and Y. Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Trans. Inform. Theory, 57(4):2342-2359, 2011.
[27] E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Found. Comput. Math., 76):77777,, 2009.
[28] C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Zang. Spectral methods: Fundamentals in Single Domains. Springer, 2006.
[29] S. Chatterjee and A. S. Hadi. Influential observations, high leverage points, and outliers in linear regression. Starist. Sci., 1(3):379-411 415. 1986.
[30] S. Chen, R. Varma, A. Singh, and J. Kovačcević. A statistical perspective of sampling scores for linear regression. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 1556-1560, 2016.
[31] X. Chen, J. Cen, and Q. Zou. Adaptive trajectories sampling for solving PDEs with deep learning methods. arXiv:2303. 15704, 2023.
[32] X. Chen and E. Price. Active regression via linear-sample sparsification. In A. Beygelzimer and D. Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 663-695. PMLR, 2019.
[33] I.-Y. Chun and B. Adeock. Compressed sensing and parallel acquisition. IEEE Trans. Inform. Theory, 63(8):4860 4880-488,2888222222 2017.
12

---

[34] A. Cohen and G. Migliorati. Optimal weighted least- methods. SMAI J. Comput. Math., 3:181-203, 2017.
[35] E. C. Cyr, M. A. Gulian, R. G. Patel, M. Perego, and N. A. Trask. Robust training and initialization of deep neural networks: An adaptive basis viewpoint. In Jianfeng Lu and Rachel Ward, editors, Proceedings The First Mathematical and Scientific Machine Learning Conference, volume 107 of Proceedings of Machine Learning Research, pages 512-536, Princeton University, Princeton, NJ, USA, 2020. PMLR.
[36] W. M. Czarnecki, S. Osindero, M. Jaderberg, Swirsze7, and R. Pascanu. Sobolev training for neural networks. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[37] Düng, V. Temlyakov, and T. Ullrich. Hyperbolic Cross Approximation. Adv. Courses Math. CRM Barcelona. Birkhäuser, Basel, Switzerland, 2018.
[38] M. A. Davenport and J. Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE J. Sel. Topics Signal Process., 10(4):602-622, 2016.
[39] T. De Ryck and S. Mishra. Generic bounds on the approximation error for physics-informed (and) operator learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[40] P. Deora, B. Vasudeva, S. Bhattacharya, and P. M. Pradhan. Structure preserving compressive sensing MRI reconstruction using generative adversarial networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 522- 523, 2020.
[41] M. Derezinski, M. K. K Warmuth, and D. J. Hsu. Leveraged volume sampling for linear regression. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[42] W. E, J. Han, and A. Jentzen. Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations. Commun. Muth. Stat., 5(4):349-380. 2017.
[43] M. Eigel, R. Schneider, and P. Trunschke. Convergence bounds for empirical nonlinear least-squares. ESAIM Math. Model. Numer. Anul., 56(1):79-104, 2022.
[44] M. S. Eldred, L. W. T. Ng. M. Barrone, and S. Domino. Multifidelity uncertainty quantification using spectral stochastic discrepancy models. In Roger Ghanem, David Higdon, and Houman Owhadi, editors, Handbook of Uncertainty Quantification, pages 991-1036. Springer, Cham, Switzerland, 2017.
[45] L. Epstein. Introduction to the Mathematics of Medical Imaging. Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics, 2nd edition, 2007.
[46] T. Erdelyi, C. Musco, and C. Musco. Fourier sparse leverage scores and approximate kernel learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 109-122. Curran Associates, Inc., 2020.
[47] M. Fanuel, J. Schreurs, and J. A. K. Suykens. Nyström landmark sampling and regularized Christoffel functions. Mach. Learn., 111:2213-2254 2022.
[48] S. Foucart and Rauhut. Mathematical Introduction to Compressive Sensing. Appl. Numer. Harmon. Anal. Birkhäuser, New York, NY, 2013.
[49] A. Gajjar, C. Hegde, and C. P. Musco. Provable active learning of neural networks for parametric PDEs. In The Symbiosis of Deep Learning and Differential Equations II, 2022.
13

---

[50] A. Gajjar, C. Musco, and C. Hegde. Active Learning for Single Neuron Models with Lipschitz Non-Limearinn Linearittsiies. In Francisco Ruiz, Jennifer Dy, and Jan- willem van de Meent, editors. Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 4101-4113, PMLR, 2023.
[51] Z. Gao, T. Tanf, L. Yan, and T. Zhou. Failure-informed adaptive sampling for PINNs, part II: combining with re-sampling and subset simulation. ar32::2302.0133 2023.
[52] Z. Gao, L. Yan, and T. Zhou. Failure-informed adaptive sampling for pinns. SIAM Journal on Scientific Computing, ([4)):A1711A199))) 2023.
[53] M. Geist, P. Petersen, M. Raslan, R. Schneider, and G. Kutyniok. Numerical solution of the parametric diffusion equation by deep neural networks. J. Sci. Comput., 88:22, 2021.
[54] X. Geng and L.. Zeng. Gradient-enhanced deep neural network approximations. J. Mach. Learn. Model. Comput., ((4))733-11, 2022.
[55] Gözeü, Mahabadi, Y.-H. Li, E. Ilcak, T. Çukur, Scarlett, and V. Cevher. Learning- based compressive MRI. IEEE Trans. Med. Imag., 37(6): 2018.
[56] L. Guo, A. Narayan, and T. Zhou. A gradient enhanced ε -iiiimmzzation for sparse approxima- tion of polynomial chaos expansions. J. Comput. Phys., 367:49-64, 2018.
[57] L. Guo, A. Narayan, and T. Zhou. Constructing least-squares polynomial approximations. SIAM Rev. 62(2):483-508, 2020.
[58]
Haberstich, A. Nouy, and G. Perrin. Boosted optimal weighted least-squares. Math. Comp., 91: 91:1281-1315, 2022.
[59] K. Hammernik, T. Klatzer, E. Kobler, M. P. Recht, D. K. Sodickson, T. Pock, and F. Knoll. Learning a variational network for reconstruction of accelerated MRI data. Magn. Reson. Med., 796):305553371 2018.
[60] J. Hampton and A. Doostan. Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression. Comput. Methods Appl. Mech. Engrg., 290:73-97, 2015,
[61] J. Han, A. Jentzen, and W. E. Solving high high-dimensiional partial differential equations using deep learning. Proc. Natl. Acad. Sci. U.S.A., 115(34):8505-851) 2018.
[62] B. Hanin. Which neural net architectures give rise to exploding and vanishing gradients? Advances in Neural Information Processing Systems, pages 582-591, 2018.
[63] Hanin and D. Rolnick. How to start training: The effect of initialization and architecture. In Advances in Neural Information Processing Systems, pages 571-581 2018.
[64] A. Hashemi, H. Schaeffer, R. Shi, U. Topcu, G. Tran, and R. Ward. Generalization bounds for sparse random feature expansions. Applied and Computational Harmonic Analysis, 62:310- 330, 2023.
[65] K. Hc. X. Zhang, Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[66] C. Heiß, I. Gühring, and M. Figel. A neural multilevel method for high-dimensional parametric PDEs. In Advances in Neural Information Processing Systems, 2021.
[67] A. Jalal, M. Arvinte, G. Daras, E. Price, A. G. Dimakis, and J. Tamir. Robust Compressed Sensing MRT with Deep Generative Priors. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14938-14954 Curran Associates, Inc., 2021.
[68] A. Jalal, S. Karmalkar, A. Dimakis, and E. Price. Instance-optimal compressed sensing via posterior sampling. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 4709 4720. PMLR, 18-24 Jul 2021.
14

---

[69] X. Jin, S. Cai, H. Li, and George Em Karniadakis. Nsfnets (navier-stoke) flow nets): Physics- informed neural networks for the incompressible navier-stokes equations. J. Comput. Phys., 426: 109951, 2021.
[70] J. Kaczmarzyk, P. McClure, W. Zulfikar, A, Rana, H. Rajaei, A. Richie-Halford, S. Bansal, D. Jarecka, J. Lee, and S. Ghosh. neuronets/noorainer. 0.4.0, October 2022.
[71] T. Karras, Aila, S. Laine, and J. Lehtinen. Progressive growing of GANs for improved quality, stability, and variation. In International Conference on Learning Representations, 2018.
[72] D. P. Kingma and J. Ba. Adam: a method for stochastic optimization. arXiv: 1412.6922 2017.
[73] N. Kovachki, Li, Liu, K. Azizzadnesheli, Bhattacharya, Stuart, and A. Anandkumar. Neural operator: Learning maps between function spaces with applications to PDEs. J. Mach. Learn. Res., 24:1-99 1-7, 2023.
[74] F. Krahmer and R. Ward. Stable and robust sampling strategies for compressive imaging. IEEE Trans. Image Process., 23(2):612-622 622, 2013.
[75] G. Kutyniok, P. Petersen, M. Raslan, and R. Schneider. A theoretical analysis of deep neural networks and parametric PDEs. Constr. Approx., 55:73-125, 2022.
[76] D. J. Larkman and R. G. Nunes. Parallel Magnetic Resonance Imaging. Phys. Med. Biol., 52(7):R15, 2007.
[77] J. B. Lasserre and E. Pauwels. The empirical Christoffel function with applications in data analysis. Adv. Comput. Math., 45: 15::1499-166, 2019.
[78] Y. Li, M. Anitescu, O. Roderick, and F. Hickernell. Orhogonal bases for polynomial regression with derivative information in uncertainty quantification. Int. J. Uncertain. Quantif., 144):997- 320, 2011.
[79] D. Liang, Cheng, Z. Ke, and Ying. Deep Magnetic Resonance image reconstruction: inverse problems meet neural networks. IEEE Signal Process. Mag., 37(1):141-151 2020.
[80] Z. Liang and P. C. Lauterbur, Principles of Magnetic Resonance Imaging: A Signal Processing Perspective. IEEE Press Series on Biomedical Engineering. Wiley- IEEE Press, New York, 2000.
[81] J. Liu and Z. Liu. Non-iterative recovery from nonlinear observations using generative models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 233-243, 2022.
[82] B. Lockwood and D. Mavriplis. Gradient-based methods for uncertainty quantification in hypersonic flows. Comput. & Fluids, 85:27-38, 2013.
[83] L. Lu, P. Jin, Z. Pang, G. Zhang, and G. E. Karniadakis. Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators. Nat. Mach. Intell., 3:218-229, 2021.
[84] A. Lucas, M. Iliadis, R. Molina, and A. K. Katsaggelos. Using deep neural networks for inverse problems in imaging: beyond analytical methods. IEEE Signal Process. Mag., 35(1):20-36, 2018.
[85] P. Ma, M. W. Mahoney, and B. Yu. A statistical perspective on algorithmic leveraging. Mach. Learn. Res., 16:861-911, 2015.
[86] 7. Mao and X. Meng. Physics-informed neural networks with residual/gradient- brasdd sampling methods for solving partial differential equations with sharp solutions. Applied Mathematics and Mechanics, 44(7): 1079-100681184 2023.
based adaptive
[87] M. Mardani, F. Gong, J. Y. Cheng, S. S. Vasanawala, G. Zaharchuk, L. Xing, and J. M. Pauly. Deep generative adversarial neural networks for compressive sensing MRI. IEEE transactions medical imaging, 38(1):167-179) 2018.
15

---

[88] M. T. McCann and M. Unser. Biomedical image reconstruction: From the foundations to deep neural networks. Foundations and Trends@ in Signal Processing, 13(3):283-359, 2019.
[89] D. W. McRobbie, E. A. Moore, M. J. Graves, and M. R. Prince. MRI: From Picture to Proton. Cambridge University Press, Cambridge, 2nd edition, 2006.
[90] G. Migliorati. Polynomial approximation by means of the random discrete L projection and application to inverse problems for PDEs with stochastic data. PhD thesis, Politecnico di Milano, 2013.
[91] G. Migliorati. Adaptive approximation by optimal weighted least squares methods. SIAM J. Numer. Anal, 57(5):2217-2245, 2019.
[92] G. Migliorati. Multivariate approximation of functions on irregular domains by weighted least-squares methods. IMA J. Numer. Anal., 41(2):12933-1111, 2021.
[93] G. Migliorati, F. Nobile, and R. Tempone. Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points. Multivariate Anal., 142:167-182, 2015.
[94] C. Musco and C. Musco. Recursive Sampling for the Nyström Method. In I. Guyon, U. Von Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, 2017.
[95] A. Naderi and Y. Plan. Beyond independent measurements: General compressed sensing with gnn application. In NeurlPS 2021 Workshop on Deep Learning and Inverse Problems, 2021.
[96] A. Narayan. Computation of induced orthogonal polynomial distributions. Electron. Trans. Numer. Anal., 50:71-97, 2018.
[97] P. Nevai. Géza Freud, orthogonal polynomials and Christoffel functions. case study. J. Approx. Theory, 48(1):3-167, 1986.
[98] T. O'Leary-Roseberry Chen, U. Villa, and O. Ghattas. Derivative-informedd neural operator: an efficient framework for high-dimensional parametric derivative learning. 4rXiv:2206.10745, 2022.
[99] T. O''Laryy-Rsseeee Roseberry, U. Villa, P. Chen, and O. Ghattas. Derivative-informed projected neural networks for high- high-dimensional parametric maps governed by PDEs. Comput. Methods Appl. Mech. Engrg., 388(1): ( 114199, 2022.
[100] G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. G. Dimakis, and R. Willett. Deep learning techniques for inverse problems imaging. JEEE J. Sel. Areas Inf. Theory, 1(1):39-56, 2020.
[101] B. Ordozgoiti, A. Matakos, and A. Gionis. Generalized leverage scores: Geometric interpre- tation and applications. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 17056-17070. PMLR, 2022.
[102] B. Peherstorfer, K. Willcox, and M. Gunzburger. Survey of multifidelity methods in uncertainty propagation, inference, and optimization. SIAM Rev, 60(3):550-51,, 2018.
[103] J. Peng. J. Hampton, and A. Doostan. On polynomial chaos expansion via gradient-enhanced
1 4y-minimization. Comput. Phys., 310:440-45 458, 2016.
[104] C. Poon. On the role total variation in compressed sensing. SIAM J. Imaging Sci., 8(1):682- 720, 2015.
[105] M. Raissi, Perdikaris, and G. Karniadakis. Physics-informed neural networks: deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. J. Comput. Phys., 378:686-707, 2019.
[106] H. Rauhut, R. Schneider, and 7.. Stojanac Low rank tensor recovery via iterative hard thresholding. Linear Algebra Appl., 524:220-262, 2017.
16

---

[107] S. Ravishankar, J. C. Ye, and J. A. Fessler. Image reconstruction: from sparsity to data-adaa -ata-adaptive methods and machine learning. Proc. IEEE, 108(1):86-109) 2020.
[108] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions linear matrix equations via nuclear norm minimization. SIAM Rev., 52(3):471-501, 2010.
[109] S. H. Rudy, S. L. Brunton, L. Proctor, and J. N. Kutz. Data-driven discovery of partial differential equations. Sci. Adv., 3(4), 2017.
[110] C. M. Sandino, J. Y. Cheng, Chen, M. Mardani, J. M. Pauly, and S. S. Vasanawala. Com- pressed sensing: from research clinical practice with deep neural networks. IEEE Signal Process. Mag., 31(1):117-127, 2020.
[111] F. Sherry, M. Benning, J. C. De los Reyes, M. J. Graves, G. Maierhofer, G. Williams, C.-B. Schönlieb, and M. J. Ehrhardt. Learning the sampling pattern for MRI. IEEE Trans. Med. Imag., (9311)):3111 10 40214,21,220 2020.
[112] J. Sirignano and K. Spiliopoulos. DGM: A deep learning algorithm for solving partial differential equations. J. Comput. Phys., 375:1339- 1364, 2018.
[113] K. Tang, X. Wan, and C. Yang. Das: A deep adaptive sampling method for solving partial differential equations. arXiv preprini arXiv:21 14..3888, 2021.
[114] T. Tang and T. Zhou. On discrete least-squares projection in unbounded domain with random evaluations and its application to parametric uncertainty quantification. SIAM J. Sci. Comput., 36(5):A2272-A223) 2014.
[115] J. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput, Math., 12:389 434, 2012.
[116] M. Uecker. Parallel Magnetic Resonance Imaging. arXiv:1501.06209.22 2015.
[117] M. Vidyasagar. An Introduction Compressed Sensing. Comput. Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019.
[118] S. Wang, H. Wang, and P. Perdikaris. Learning the solution operator of parametric partial differential equations with physics-informed DeepOnets. Sci. Adv., 7(40))eabi8605, 2021.
[119] P. Woodruff. Sketching as for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014
[120] J. Yu, L. Lu, X. Meng, and G. E. Karniadakis. Gradient-enhanced physics-informed neural networks for forward and inverse PDE problems. Comput. Methods Appl. Mech. Engrg.. 14823, 2022.
17

---

A Further literature and discussion
In this appendix, we provide some additional discussion that relates work to existing literature.
A.1 Classical Christoffel functions
Let IF be linear subspace of the Hilbert space X (D) The Christoffel function of IF is the function + (0), where
|S
fE u 0. 0 D. 1
K (F) = sup
This is clearly a special case of Definition 2.6 with X. C(D and D. BXx,, R) given by (())(f) = f(0). The Christoffel function is classical object in approximation theory, most typically associated with the case where space of algebraic polynomials 197). Note that K (FF) is precisely the diagonal of the reproducing kernel of IF in X. It also follows immediately from Lemma E.
(FF Σ [f((0))
for any orthonormal basis {/i}= of F.
A.2 Relation to leverage scores and leverage score sampling
Let D be domain with a measure À (typically the Lebesgue measure), F be class of functions f: D - and p be probability measure over with Radon-Nikodym derivative p = dp/ dA. Then the leverage score is defined
(() (FF sup [(()))p(0) Ifll
E FEF1
(A.1)
where - (1(0)) dx(0) Jo (0) dp(0). See, e.g., [46] and references therein. Like with CS, leverage score sampling is type of importance sampling where one draws samples randomly according to the probability density proportional T (or, often in practice, some casy-to- compute upper bound 7). We remark in passing that leverage effective resistance or coherence motivated sampling in the literature. Note that in the literature on leverage scores, the empirical nondegeneracy condition 2.5 is sometimes referred to as the subspace embedding condition (see, e.g., (19)).
sampling is sometimes known as
It is readily seen that I special case of Definition 2.6 different ways to formulate this.
Let X = L2) Then there are several
Consider D equipped with the measure and L(0)(S) -r(00))))((00000 (o) Then nondegen- eracy 2.3 holds with a = 3 = and we have
(F) = sup [(()) |I
f.E.
=: Kx(0).
(ii) Alternatively, consider equipped with the measure and set I((O(J) = [(0)- Then nondegeneracy (2.3) holds with
and we have
[( 1I.
((F) sup
ff fEE. Kp()).
Notice that (a) = r(F, (0) is precisely the leverage score A. Conversely, K2(0)
differs from the leverage score (A.I) by the factor p()). Whether to include p(0) in the definition is one of convention. What is important is that both (i) and (ii) lead to exactly the same Christoffel sampling sampling measure 1 in (2.1T). which is equivalent leverage score sampling for the standard regression problem. Indeed, this measure is
dy²(0) x K. (0) d2
dX(0)
18

---

for case (i) or
T(P,p)(0) p(0) p(0)d)(0) = =(F.
(p) Ko(0)
for case (ii).
(Statistical) leverage scores are an old concept 20 that have recently found many applications in machine learning, including randomized numerical linear algebra [119), kernel methods 12 46
47 94], active learning [2
46 85], data analysis [77] and beyond. Leverage scores are
perhaps most commonly encountered in the discrete setting. Here the matrix leverage score of a matrix matrix A RNNx Nxn is defined as
(Ax) |
(A)(1) max wER
a! (A A) aa i i= N,
(A.2)
Arz0
where a, is the ith of A. This is also special of Definition 2.6 Indeed, let X RV and = R. both equipped with the Fuclidean inner product, D = (1,.... N) be equipped with the uniform measure p. (z) = z; for a vector I (z.) E EN and
F {Az E C
Then 2.3 holds with a 3 = (notice that is the uniform measure, not the uniform probability measure) and the generalized Christoffel function satisfies
LLOOE |
FER, 1 SER = sup {
(Ax) ||x|
(1F) = sup
EEER"
At 4 (())
There are a number of generalizations of leverage scores in the literature. See, e.g., [OT. However, to the best of our knowledge, none of these are similar to the setting considered in this paper (in particular, Definition 2.6
A.3 Other related work
Our general framework and results are related to recent work 43 Here the authors consider approximating functions in arbitrary (linear or nonlinear) approximation spaces (model classes) via an empirical least-squares regression based on a gemi-norm that depends on (random) variable E Y C Rd In a similar spirit Theorem 4.2 and Theorem 4.8 4 establishes sample complexity and generalization error bounds, and then use the former to optimize the sampling measure. Specifically,
43 Thm. 2.8 and Cor. 2.9] is similar to Theorem 4.2 with = 0 (i.e., the case of classical coverings as opposed to subspace coverings) and 43 Thm. 2.1 is similar to Theorem 4.8 albeit without the additional technical steps used in the proof of Theorem (48 to obtain an expected error bound involving only the X-norm on the left- and right- sides.
This framework related to our framework with C' 1 sampling operators and with being Banach space of functions. In fact, it is somewhat more general in this case: (i) no inner product structure assumed and, (ii) each measurement (which are implicit in the semi-norm in could belong to different space. Note that one could readily incorporate (ii) into our framework, by making the target space Y. depend on 9.. However, (i) leads fundamentally weaker sample complexity guarantees. For example, in the case of a linear subspace F, the bounds in 43 scale log-cubically
in n dim(F), i.e., like e- n² -og(n) (see (43. Sec. 3.1 whereas the results in this work are log-linear, i.e., e- n log(n) (see Corollary 4.7). and therefore near-optimal. A similar suboptimal log-cubic scaling also arises in the case where IF is a nonlinear space of s-sparse expansions in an orthonormal basis (see [43 Sec. 3.2]). See Appendix A.4 for more this example.
As noted, the root cause of this suboptimal scaling (i). In our framework, we impose that X is a Hilbert space and each Y, is semi-inner product space. This allows us to use matrix concentration techniques (specifically, the matrix Chernoff bound (115)) in combination with the technique of subspace coverings (Definition 4.1 to obtain better sample complexity bounds. We remark in passing that the special case of
in our main sample complexity bound Theorem 4.2 (which, as noted above, is similar to 43 ) does not require an inner product structure, i.e., it holds if X is a Banach space and each V, a semi-normed vector space. However, if applied to the case of linear subspaces, it would also lead to suboptimal sample complexity estimates much as in 43 Sec. 3.1].
19

---

A.4 The case of sparse regression
In this section, we briefly discuss the application of our general framework to sparse regression. For convenience, we shall assume that X = (D) is the space of weighted square sntrre-nteegralee functions f: C, X = C(D), C I, Y Y C with the Euclidean inner product and L1 the pointwise evaluation operator (f)) = f()). However, the following discussion can be readily generalized general setting considered in Section 2.1
Let = 1- C X collection of elements in X, where E N. We assume that this is a Riesz such that
system, i.e., there exist constants 0 < S
N
N b
Σ
Ve E.
i=1
==1
Note that a = b b= if and only if Φ is an orthonormal system. Now let 1 < N and define
F F=
Σ
cod: : a E CC,,V. SC (1.... N), |S| =
iES
Then the set of all s-sparse expansions in the system क. this case, we refer to (.. as a sparse regression problem. Notice that empirical nondegeneracy Eq. (2.5) is in this case equivalent to the Restricted Isometry Property (RIP) [88 for the matrix A m (0, (O,))
m.N E Cm
Several remarks in order. First, notice that F, F. F2s- Second, F, is union-of-subspaces model. Indeed, F, is precisely union of d (>) subspaces, each corresponding particular choice of support set S C (1...., N]. [S] = When N and are large, this is a large number, which makes the bound in Corollary 4.7 meaningless.
However, in this case, we can obtain a more appealing bound. Notice that the generalized Christoffel function
1f(0)) [[f(lig(D))
K (O))(0))
max sC(l....N)) [8
S-
Eadi a E C,
FES
is a simple argument to see that
s max 10:(0)1 1I
I....,N
Therefore,
max ({F,)(0) a R(O), R(0)= i=1.....NN
(0)
The function K. serves two purposes. First, it can be used to upper bound <(F.) SD K (IF.) dp((), i.e., the term appearing the estimate in Corollary 4.7 Second, can also be used as convenient surrogate from which to sample, computing K(0) is typically easier than computing the true Christoffel function K (O).
Suppose now that || | ess eussup (0) < K for all i = ,,...,N N. In this case, & is
known bounded Riesz system
23 Then
(F. (0) <s.a k((0) S a
Using this and the well-known estimate d = (M) < (cN/s)², we deduce from Corollary 4.3 the sample complexity bound
m 2 Ce/2 s- (- log (e.ss)/s) + log(s/8)).
This is a substantial improvement on the bound implied directly by Corollary 4.7] which depends
linearly on = (?). It also improves the bound of 43 Sec. 3.2] from log-cubic to log-quadratic (recall the discussion in Appendix A.3) However, the reader will note that it is not optimal, since m
scales log-quarratically s. One can improve this bound log-linear by using a more sophisticated
argument specific to the sparse regression case. See, e.g., [4] 23 48) and references therein. The
20

---

extent to which this argument can be extended to the most general setting of our framework is problem for future work.
Unfortunately, many Riesz systems of practical interest are not bounded. this case, one has the sample complexity bound
m 2 Ce/2 R. a aa.a.... 8. (s- (sslog(eN/s) + log(s/6)),
(A.3)
where
max (p))))d((())
il
The bound A.33 grows hog-qudratticalyy in 8, as desired (it can also be improved to log-linear as mentioned above). However, the constant й may depend on N. We refer to 4 for an extensive discussion on this issue. It is notable that R can be estimated numerically. In cases of interest such as sparse multivariate polynomial regression, either bounded or mildly growing N [4].
B Polynomial regression with gradient-augmented data
In this appendix, we describe the example considered in Section 3.1 Let f RRd - R. In the gradient-augmennted learning problem, we consider training data of the form
{ {0,, (0, (0=))(())) J
where (for convenience) 0.f" = f and 0 = 0f /00; otherwise.
B.1 Formulation terms of the general sampling framework
We now describe how formulate the gradient-augmented learning problem special case of the general framework. Let C = 1, D) = D2 = (Ra p) where 2 and be the tensor-product Gaussian measure on Rd, i.e. dp = (2/) 2 1110 d0. Then we let
= (R*) = (a.l E (TR))
be the Sobolev space of weighted square-integrable functions with respect to P with weak first-order derivatives that are also square square-integrabl with respect to p. This a Hilbert space with inner product
(f.g)x
Σ Rd
9.)(
Next, we let Xg- C¹ (D) and be the Hilbert space
Y -C )2)
where (1 the Euclidean inner product. Then, we define the sampling operator L:D - B(Xy, Y)
as
L(0)(f) (a)f(e))
(B.1)
Notice that
J. IZ(0)(II dp(0)
Σ ( = |151(2300) +
Σ
10 10:f1l2300 = =11f1lag(00
k= Bd
Thus, Assumption 2.2 holds for this example with 3
B.2
The approximation space: multivariate Hermite polynomials
The standard Hermite polynomials Hx(x) are eigenfunctions of the Sturm-Liouville problem
(wn') 2kwu O.
where w(x) =e= They orthogonal on IR with respect to this function, specifically,
Hn(x) (z))(()))) nle
21

---

They satisfy the three term recurrence with (o = 1, H1(x) = 2z and
(1)1(x) nrH - 2n 2nH " 1,2,
(B.2)
and their derivatives satisfy the relation H7 0 and
Hr -
1.2....
(B.3)
See, e.g., 28 Sec. 2.6.2] for standard properties of Hermite polynomials.
It is more convenient for our purposes to consider the standard Gaussian (probability) measure IR, i.c.
dp(0)
22T c 2 dA.
Then the orthonormal Hermite polynomials (sometimes known as the "probabilists" version") are given by
n (0)
V2 Hn, (0/v2).
Manipulating (B.2).
that the orthonormal Hermite polynomials satisfy r00(0) (0) (0)=0)
and
10) vn (n
71
1/ 1 n 1,2,
(B.4)
Also, we have Vi v2 V2 H (0/V2) V2" 2nH 2 (0/v2),. and therefore vi6 0 and
(0) = v n = = 1,2.....
(B.5)
Using this, we readily deduce that the functions
On v'n (0)
= 1.11,.....
VI+n
form an orthonormal basis of the space
H (R)
(ʃ T.) 1' (R)))
i... the Sobolev space of gquare-integrabbe functions R (with respect to p) with square- integrable (weak) first derivatives.
We extend to d dimensions via tensorization. We let
dp(0)
1011 d0
V2n
and consider the tensor Hermite polynomials
(0) ten (01) Viz (0a),
== (u:) E No. 0 0= (0.) E Rd.
Leveraging what did in the one- din-dimensional case, then construct orthonormal basis of the Sobolev space
(R") {s E (2 O& 13(R"), 1....,d d)
as (Dylueng, where
V ② VI+ +
v = (vi) E No.
We conclude by defining the approximation space F. Fix an index p E No and let
S S= S, v= $= (vi) No II (M + 5p+1) C No.
(B.6)
1=1
This is the so-called hyperbolic cross index set, which is particularly well suited for multivariate polynomial approximation [ Using this, we define the linear approximation space
F span & : # E S} (Rd).
Notice that Assumption 2.5 holds for this choice of Indeed, contains the constant function f(0) 1, V0 e Rd which satisfies Lf0)(f) (1,0.
.........01........... 0) * 0.
22

---

B.3 Numerical solution of the regression problem
We now describe the numerical solution the regression problem (2.2) in this case. Let ...... Pm Rd be sample points and D + R be measurable and finite and positive almost everywhere. Then this problem takes the form
f argmin fEZ
Σ k=0
1usk 0xf(0.)1.
(B.7)
(0,)
where Vik: = (0,) + ei is the kth component of the ith measurement of f*. For convenience, assume the ordering {u² ,..., vn) Let f E F be arbitrary and write f = ->> c vi and = (ci) Then
1 ras( (Axc)s
V Vu(0))m
where
As
(v(0.
Ou Du (0:)
Also, let
m
1
yokk
Vv(,))m
im
and set
AAo
660
A =
b
Ad
ba
Then
m
1
Vik (v.( = ||Ac - -b112
(0,))
k=
Thus, the algebraic least-squares problem
E argmin Ac bl(2
(B.8)
<EC*
equivalent to B.7). 7 in the sense that every solution of this problem yields a solution f Σ" 2, of B.7 and vice versa.
Notice (B.8) an mdd + 1) algebraic least-squares problem, which can be easily solved using standard linear algebra software once the matrix A has been computed. This is done using the relations B.4 and (B.5).
B.4
Christoffel sampling
We now explain how to perform CS in this example. Directly sampling from the measure 2.7 is potentially difficult for this problem, since simple characterization of the generalized Christoffel function (8) is lacking. However, we observe that
(F) ((F < (())
(B.9)
d d+1 1
where
Σ d
1 (0x) 12
|uh, (0:)12
((F) I Σ [())
0.
17k
1 ||2/|
PES
#ES k=0
VES k=
(B.10)
See Lemma
E.
Notice that
J ((F)(O) dp(()) Σ
Σ
O (.0 dp(0)
Σ || [10011i73(00)) n,
23

---

since the functions 4, are orthonormal. Therefore, we can use (F) to construct sampling measure as
dīí(0) (()) dp()) K ( dp(0).
n
Since ess su o (K(E))))/(()) S. Corollary 4.3 implies that sampling from ji yields optimal, log-linear sample complexity. As it so closely related the generalized Christoffel function (see (B.9) ) we continue to refer to this as Christoffel sampling.
One sample from by observing that it is additive mixture 34 of tensor pansortproduct probability measures, each of which can be sampled from efficiently 196] However, we opt for a simpler approach based 2 92] involving finite grids and discrete measures. Let Z (zi ) D grid of
N points, with each point 2 drawn i.i.d. from the measure Then, we now replace the measure p by the finite measure
p
Σ 82.
(B.11)
N
After doing this, the Christoffel function becomes a discrete function supported on the grid Z, which can be expressed
"
(FF)
ΣΣ @xx;(=)1
E Z,
j=1
where {x, 1==1 is orthonormal basis of IF with respect the discrete H3 (In)-inner product. Now define the matrix
Bp
BR = (1 0w oz
B
Bd
ijml
Consider the QR factorization B = Q., where Q = (9t)) E C(d+1)Nxn has orthonormal columns and R C" is upper triangular. Then the jth column of Q contains precisely the values 0xX; (2:). i 1,.... N, k 0, O,...,. d. Using this, we get
((F)(z)) N
14 i= I...,,N. N.
Notice that
/ (())))
94tNN
and therefore
K (F) v(2)
1
Hence, we can compute the function (FF) over the grid Z and then use this to sample from the optimal measure μa, which in this case is the discrete measure with y if
(Z) nN
P(O 2,)
i= 11 N.
B.5 Additional experimental details
As described in Appendix [B.4] we first draw random grid from the measure p. In our experiments, we choose the number of grid points N 50, 000. Note that this grid is drawn once, prior to any subsequent computations. In Fig. [ we compute a test error as the relative Sobolev norm error over this grid. This done using the following expression:
|f --11mmm (IRd)
Ed_ N Li=l Oxlf= (z)) En
E(f*)
(B.12)
115 11 (Rd)
Σ
(0)1+
k=
N

---

1015
MUS
Contition aumberr connl
10
MCS
A))
109
MCS
Confition aumber cond.
025
CS5
CS
10P
10
10
104
10"
109
10"
109
200
400
600
800
500
1000
1500
2000
2500
600
1000
1500
Figure 4: CS for gradient-augmentte polynomial regression. Plots of the average condition number cond(A) versus for MCS and CS for gradient-augmented polynomial regression for d 2, 8 (left right). In both cases, we the scaling m |max (n, , n log(n)) (d 1)].
The experiments shown in Fig. proceed as follows. First, generate sequence of hyperbolic cross index sets (B.6) of orders S P1 < P2 < ... < Pt. Second, for each I,..., L, we choose my according to the scaling
m max n log(n))/(d
(B.13)
where n. 15p Then, we draw m samples randomly using either MCS or CS (as described above), compute the approximation using (B.8) and then compute the error using BB.1 We then repeat this process for a total of T 25 trials.
The graphs in Fig. and this appendix show the geometric mean (the main curve) and plus/minus one (geometric) standard deviation (the shaded region). The reason for using the geometric mean because the errors are plotted in log-scale on the y-axis. See [1] Sec. A.1] for further rationale behind this choice visualization.
These experiments were conducted on 2012 MacBook Pro with 2.7 GHz Intel Core i7 CPU and 16 GB of DDR3-1600 RAM running MATLAB R2020b. Total runtime for these experiments was roughly three days.
B.6 Further experiments and discussion
Let S a' < 3' be the optimal constants in the empirical nondegeneracy condition 2.5) In this example, for collection of sample points 0I...., ... Om. these are given by
a' inf
Oxf(0.)) :ff ffEF IIflx $ v0,))
171
m
8' = sup
Owf(0.)) E [lfll <
v(O.)
m
(here we recall that F F, since is a subspace). By expanding / E F in the orthonormal basis ( : S) readily deduce that
d (A),
B' maxx
ma)x (A).
Thus, these constants can be computed numerically. Moreover, their ratio 3'/a' cond(A) is precisely the 2-norm condition number of A. In Fig. we plot cond(A) for both schemes using the same experimental setup in Fig. I As predicted by theory, CS leads to bounded condition number for all m, that is at most roughly 102 magnitude. However, MCS leads to an exploding condition number. This indicates that the scaling used Eq. (3.13) is not sufficient to ensure good generalization bound, which is the reason for the poor performance of MCS in Fig.
To examine this further, in Fig. 5 we perform the following experiment. For each value of n n2. 1= 1,..... L, we compute the minimum value m my such that cond A) < tol, where tol = 10. This is done follows. We first set n/(d + 1) and compute cond(A). If cond( A) > tol, we increment m by one, draw new samples, re-compute cond (A) and check whether cond d) S tol. not, we repeat this step. Finally, repeat the whole process for total of T 25 trials.
25

---

MCS
MCS
MCS
CCS
CCS <n.log(n)
login))
<nllggn)
1500
1500
mlogieh/id
1500
mlogle3/dd
1000
500
500
500
100
200
300
400
500
200
400
600
800
1000
200
400
600
800
1000
Figure 5: CS for wradient-augmente polynomial regression. Plots of minimum value of m that which yields condition number cond( ()) tol for both MCS and CS, where tol 10 and = 2, 4, (left to right).
In Fig. 5 we show the results of this computation for MCS and CS. We plot both the arithmetic mean (the main curve) and plus/minus one standard deviation (the shaded region). As is evident, the CS scheme leads to a much less severe scaling. Further, as predicted by our main result, this scaling behaves as v. log(n). On the other hand, MCS exhibits a severe scaling. When d = 2, for examples, one needs over 2000 sample points whenever n 2 30. Notice that this exceedingly poor scaling for polynomial regression with MCS has been widely documented in the non-grann -ongrrddient augmented setting [57 90 [14]. These experiments show gradient-augmented sampling also suffers from similar effect.
As noted in Section 5| limitation of this approach is that the benefit it delivers depends very much on the problem setting. For example, suppose we change the domain D to the bounded hypercube D 1, 1jdd and consider polynomial regression using orthonormal polynomials with respect the uniform probability measure on D. These polynomials can be constructed using censor-product of the one-dimensional Legendre polynomials, much as was done in the previous case with the Hermite
polynomials. In particular, analogous recurrence relations to (B.2 and B.3) hold [28 Sec. 2.3],
which allows for efficient construction the least-squares matrix A once more. Fig. 6 we display the approximation errors and condition numbers for MCS and CS for this problem. The comparison
with Fig. and Fig. is striking. Especially in higher (d 2 4) dimensions MCS performs nearly as well as CS, both in terms of the approximation error and condition number. This behaviour is also reflected in scaling computations. which are shown in the third row of Fig. 6 In low dimensions, MCS suffers from worse scaling that CS, but it is nowhere domains. Moreover, as the dimension increases the scalings become much closer. Note that these observations well known in the non-gradient augmented setting [57 90
severe in the case of unbounded
B.7 Variation involving C
We conclude this appendix by briefly describing several variations on the gradient- aughented regression problem that take advantage of the multimodal (C > formulation of the general sampling framework.
Partial gradient samples
In some of the aforementioned applications, one may only be able afford fewer gradient samples than function evaluations [56] [03]. This can be handled as followed. Let C' 2, m, be the number of function only samples and m2 the number of gradient- augmented samples. Then we define gradient-augmentee
X = H [ Dj D2 = Rdd P1
V1 (C, (+.)2) Y, = (cd+), +22) and
(f) (0), (2))))²) (cx
where co 1/v2 and ck otherwise. Then we have
Σ
[1(0)()) dp. (((P)) + Σ
|0 10.5 = -I
Thus, empirical nondegeneracy holds 2.5 before.
26

---

evv AIE)
Ledt enc 811)
10"
Lext ecc $1.)
Eest anc 51.)
1011
10'1
10"
Choditio minde cnail.)
1014
10.31
Oxsdition minder enall.))
104
X0SS
Cuedition mieder onal)a)
XXS
Condition wieder cnddia)
C3
C5
10
124
10
200
403
600
500
1000
200
400
600
800
500
1008
1900
2000
2500
600
1000
1500
ACCS
MCS
MCC
MCS
1002
1000
1000
1200
890
500
500
500
-estiil +
600
000
100
100
-00
400
100
400
200
200
Figure 6: CS for gradient-augmented polynomial regression. Plots of the polynomial regression error (top row), condition number (middle row) and scalings (bottom row) for d 1, 8 (left to right) when using the Legendre polynomials on [-1, 1] instead of the Hermite polynomials on D R These rows recreate Figs. and respectively, this setting.
Hierarchical sampling
limitation of the standard CS is that it well suited to hierarchical approximation. Often in practice, rather than a single approximation, one may wish to compute sequence of approximations
f2. it nested sequence of subspaces F1 C Fz ... using a nested sequence of samples well suited this problem, since when the subspace changes from F5 to F 1 so does the generalized Christoffel function. Therefore the existing points are drawn from the wrong distribution for optimal sampling
[0:121 C [ C-. Standard CS
new subspace FR+1-
means to overcome this problem was presented in [91] (see also 2). It can be cast into our general framework using C' n dim(F) sampling operators. These works consider the unaugmented learning problem. However, it is readily extended to the
setting.
The basic idea is to define the ith sampling measure
(0) = dp(0), (0) Σ 10 (0)3 R=0
i= i..,..,
(B.14)
Notice that this is probability measure, since the u are orthonormal in H. (R."). Then, assuming that m kn for some & E N, we draw m, k samples i.i.d. according to μ4 for each = 1..... giving m samples total. We omit the full analysis of this case, but we remark in passing that this leads to near-optimal sample complexity. This is due, in essence, to the fact that
Σ (0) K(F(O),
where (FF) is as in B.10). The key point is that B.14 is well suited to hierarchical approximation, since it draws & samples corresponding to each basis function b If the subspace = span h,,, i= 1,....n) n is augmented to IF' span ( = n²',, where n 2 then we can recycle the existing samples, and draw additional samples for the new basis functions & h,,, i n n 1,.... n'.
See 91 for further details.
27

---

C Fourier imaging with generative models
We consider discrete imaging scenario where the object to recover a d-dimensional image of size n x ... x n. this paper, we consider 3D imaging, i.e., d =
In this appendix, describe the example considered in Section 3.2
Let N = n and f E C.N be the complex-valued vectorized image. Let CNNN be the matrix of the d-dimensional Discrete Fourier Transform (DFT) of length n with normalization F*F I. In (subsampled) Fourier imaging, one selects m I N frequencies (typically, m < N), which correspond
of F. Let Q {I...... ......, NN. [ m, be the set of frequencies sampled. Then the noisy measurements the unknown image f take the form
Fo te,
where e C is noise and Ps E Cm is the row selector matrix, i.e., Pa selects the rows of F corresponding to the indices in Q
C.1 Formulation in terms of the general sampling framework
Depending the imaging modality, it may be possible to select individual frequencies according to some sampling strategy. However, in applications such as MRI, this may not be possible. Typically, the scanner is only allowed sample along piecewise smooth curves in frequency space (80 89 Fortunately, as we now describe, both models can be cast in our general sampling framework.
Let X Xo CN with the Euclidean inner product and norm and C 1. Let AI...., Am S {I...., _N be a partition of (L...., N. i..., U A = [I.....,N] N... For convenience, we assume the A, have the same cardinality, i.c., |A,1 p. Vi. Then we let D = (I...., M., P be the uniform probability measure on D and = C with the Euclidean inner product. Next, we define the sampling operator
L:D-B(CM,O0
by
(C.1) In other words, L(i) is the linear operator that outputs the Fourier transform of an image x at the frequencies in the ith partition element A, Observe that Assumption ho4ds = 3 = 1. Indeed, for any x E C we have
V
EC, E
holds for this example with
M M Σ (L)(
M [Fxx,
J. [())(2) do(0)
= Σ Σ JIJEA;
|Fx1| 2 ||
(C.2)
With this in hand, our goal now to design a suitable sampling measure /s on = f1. M}. that each random draw from y corresponds to sample of frequencies from the corresponding partition element. Let us first describe two examples.
Example C.1 (Sampling individual frequencies) Suppose the modality allows for sampling one frequency at a time. Here, we let M = N and define A; = {i), 1, N....N..
We consider Example C.1 later in Fig. example.
Fig. in the main paper is, however, based on the following
Example C.2 (Sampling horizontal lines in k-space) Phase encoding is common sampling strat- egy MRI. Here one fully samples the first k-space direction and subsamples the others. Thus, the scanner traverses piecewise smooth trajectory in k-space. Mathematically, this can be formulated as follows. Let d = 3 for concreteness (other values of d can be easily handled), N = n2 and M n²a 3D frequencies are naturally enumerated over the set of multi-indices {I,..., n) Now consider a partition A 12 1 & i 1,..., n,, of this set defined by
(2) j (1,...,n)}.
Thus, A indo consists of k-space values along a horizontal line with y-z coordinate (1,12)) We now let Ajyt C (1....,, N) be the image A/ with respect whatever ordering is used convert triples (i,j. k)) E (1...., 3 to single indices in {1,..., N} (in our experiments, we use lexicographical ordering). Then the sets An2 define partition of (1....,A)
N). .... as required.
28

---

Note that the above formulation is by no means limited to these two examples. Many other popular sampling strategies can equally well be considered. This includes radial line sampling, spiral sampling and various other strategies used in practice. We remark in passing that the setup described here is closely related to the block sampling setup in compressed sensing. See [8 22
Remark C.3 It is worth noting two extensions of this setup. First, in practice one may wish to consider overlapping partitions A..... ...... AM. Here, one requires small modification of the sampling operators to ensure Assumption 2.4 holds. For an index E {l...., N letry r, E N be the number of partition elements in which j appears, i.e., r = (i: j E A.)l. Then define
(()) = v ((Fr)) VTi)jed,-
(C.3)
We now argue as in to deduce that empirical nondegeneracy holds with a = 3 1.
Second, it is sometime useful in practice to allow the partition elements to have different cardinalities, ie.. A = Pi, i I..... ... This can be handled straightforwardly by zero padding. Let Y C³, where p = max;=1,... M {.:}. Then we define L(t) CN + CP by appending p; zeros to the vector defined in (C.I) (or (C.3) if the partition overlapping).
C.2 The approximation space: compressive imaging with generative models
The approach considered in this paper is based on the work 20) which introduced the generative compressed sensing framework. Their subsequent work on posterior sampling further delved into the problem (68] In compressed sensing, the primary objective is to leverage the inherent structure in the solutions of underdetermined systems of noisy linear measurements. Most of the existing literature in this field focuses on imposing various forms of sparsity, such as standard sparsity, joint sparsity, hierarchical sparsity, or block sparsity 15 48. However, the generative compressed sensing framework takes a different approach. It assumes that the solutions to these problems lie near the range of generative model G: R RRN. By employing well-trained generative model G that is relevant to the reconstruction task at hand, one can solve an optimization problem to reconstruct images or other signals. In this case, the approximation space F range (G) R. i.e., the range of the generative model G. This space can be seen as a low-dimensional manifold embedded in nigher-dimensione space. Even for simple DNN models this space is typically nonlinear, and certainly for the complex models considered for the experiments related to this section.
Importantly, the generative compressed sensing framework is not limited image reconstruction but has broader applicability. The recent work [15] extends the analysis from 200 to the problem of demixing with subgaussian matrices. Other notable contributions include variational networks generative adversarial networks trained with least-squares and pixel-wise / cost functions generative adversarial network frameworks for structure preserving compressive sensing MRI and model-based approaches combined with regularization and unrolled network architectures Furthermore, recent study considers the semi-parametric single-index model with generative prior under a Gaussian measurement assumption [8I]. These studies, along with other diverse works, demonstrate the impressive versatility of the generative compressed sensing approach.
59,
87,,
40
C.3 The generalized Christoffel function
Let C X, where, as stated above, X CN with the Fuclidean inner product. Denote the Fuclidean norm by I|. Then the generalized Christoffel function is defined by
|1100111 1lfI
M sup Ejes, (F :
((F) sup
E IF
(C.4)
IIfI?
for i E fl,..., M). Since D = (l,.... B....... M) is a discrete set, we consider discrete probability
measures. Denote such a measure by (p,) i.e., 1ee..I~-ffffiifii to the Christoffel function gives the values
iifP(I i) pra Then sampling according
P. = (i) Mx(F)*
iE (1....,MM M).
where
1 M = M
<(F) = / K (IF)())p(())
Σ (())
i=1
29

---

Algorithm Computing K
input: Generative model G, number of iterations i, input distribution on the domain of G, DFT matrix F. initialize: K =
for 1 to do
Generate two i.i.d. realizations /2 via the generative model, i.e., Si G(z;) for zi misdd Compute a; M MMEja jea, 1 g) //]lll for g = fi -f2 and i = 1,.... ........ M
for i= = 1 to MM do
Replace ((i)= = max R (i), )
end for end for output: Vector K with updated entries.
Note that the corresponding weight function is
(1) x(FF)
(11)= Mp,
iE (1....,,M.
In order to apply 7.eorem4422 to this example, we need to identify a (subspace) cover F,U. of the set F- IF, where, as above F, the range of a generative model. It is therefore important to first ask when the set IF IF admits such a cover for reasonable value of d (since d appears logarithmically the bound). This question has been addressed [95] Lem. 3.1] the case of ReLU generative models (see also [16] Lem. S2.2]). Roughly speaking, if G R² RN has L layers and the widths of its hidden layers are O(p), then F F can be covered exactly with log(d) S pL subspaces of dimension 2p.
There are two factors that prohibit direct application of Theorem 4.2 to this example. First, the generative models we use are not simple ReLU DNNs. Second, even if they were, identifying the aforementioned union of subspaces that form the cover and computing the constant K (F) is likely computationally infeasible, since grows exponentially in pL.
As noted in Section 5 however, we believe the estimate involving K K(F) in Theorem 4.2 to be non-sharp, and conjecture that it should suffice consider ( F) instead. Therefore, in what follows, we compute with (an approximation to) the former. Thus, this example, the theory does not completely apply. Nevertheless, noted,
significant benefits from CS for this example.
C.4 Numerical approximation to the generalized Christoffel function
In view of (C.4) computing (F F) involves solving M (nonlinear, nonconvex) maximization problems over the input space IR" of the generative model G. This is extremely computationally expensive, since both and M are large in practice. In our examples, M = n² (Theorem C.I or 128, and p 1024 (see next).
M n (Theorem C.2 where
Therefore, in this work we consider a different approach, which is based on an iterative, random sampling procedure for computing an approximation K to K. This procedure is presented in Algorithm T and involves repeated random samples from the input distribution of the generative model to construct candidate elements fi - fz E F F. It has the advantages of being simple and not computationally intensive. Morcover, as examples show, sampling from the resulting K achieves the objective of significantly outperforming MCS.
The convergence of Algorithm 1
in computing K can be seen in Fig. 7 where the relative Eg error of the iterates are computed with the final K after the algorithm returns.
C.5 Additional experimental details
The experiments in Figures 2 & g were conducted using single generative neural network model
trained on brain MRI data. The braingen-O. 1.0 generative model was obtained from hhttps
//gi tgithub.cr www.///erooneee///raaaaeeeeeeoeo http:///rrraaddddmoooeeeeeeeeeee
and was trained using the nobrainer
30

---

10
100
10'
10
relabive
1
2
10
10
200
400
600
800
1000
200
400
600
800
1000
iterations
Sterations
Figure 7: Convergence of the relative &a error of iterations of Algorithm in computing K for (left) Example
and (right) Example C.T
70 available under Apache License, Version 2.0. This model trained using progressively growing strategy [71] for generation of -W-eiihtted brain MR scans. The model takes as input a latent vector IR 1024 here generated by sampling from the standard normal distribution. i.c. N(, 1). 1...., 1024. The output dimension of the selected braingen-O0 1. model N n2 where
framework
128.
First we generate K using 1000 iterations of Algorithm To generate the results, we chose an image from the range of the generator using random seed 11345'. We then 20 random trials
reconstructing this image with the same computed K, solving problem (2.2) using 5000 iterations of the Adam optimizer (72), implemented in TensorFlow. A constant learning rate multiplier of 100 was used to improve the convergence in the gradient update step. The experiments were conducted on single computer with an AMD Ryzen 9 5950x, 64 GB of DDR4-3600 RAM, and NVIDIA GeForce RTX 3090 Ti. The total runtime for these experiments was approximately weeks. In Fig. 2 we consider the setup of Example C.2 In Fig. wee consider the setup of Example C.1 As in Section B.5 our error plots display the mean PSNR value and also shaded region corresponding to one standard deviation. The PSNR is defined as
MAX VMSE
PSNR 20 -l0000
where MSE is the Mean Squared Error
N
1 MSE
N f
Σ
-
A.
1=1
Here f is the ground truth image, f is its reconstruction and MAX is the maximum possible pixel value of the image, here equal to 255.
C.6 Further experiments and discussion
In Fig. consider the strategy of sampling horizontal lines in k-space, see Example C.2 Fig. we perform the same experiment with the strategy of sampling individual frequencies in k-space, see Example C.T While CS with line sampling performs similarly CS with individual frequency be seen to have 15-20% drop image reconstruction quality over MCS individual frequency sampling k-space.
sampling, MCS line sampling in k-space
Although, as noted, the theory does not directly apply to this example, it is worth examining the relevant constants to gain some further insight into the performance of CS over MCS. For MCS, Theorem 4.2 suggests that the sample complexity depends on the term
OMCS ess ess K(F
Ri(
K( (1),
ioup
1=.....
31

---

soveag PONK: (80)) on frimom 20-33
40
PSNR
70
1005
0,599 MCSS
2005
32
50
70
80
3.25
0.5
0.75
1.25
1.75 2.0
Imagee mimbbr
sanpling percentage
Figure 8: CS for MRI reconstruction using generative models. Plots of (left) the average PSNR image number of the 5-dimensional brain MR image for both CS and MCS methods at 0. 0.125%, 0.375%, and 0.625% sampling percentages, (middle) the average PSNR computed over the frames percentage for both CS and MCS methods, and (right) the empirical function K used for the CS procedure. In this figure, we consider Example C.I instead Example C.2 which was used in Fig.
of the image vs. sampling
Table Values of Cucs and Ccs for experiments with Examples
C.2
Example
C.1
Example C.2
CMcs
3.2794x 10
4616.4
Ccs
7.6029
3.9595
i.e. the maximum of the approximate Christoffel function K. Conversely, for CS it suggests that the sample complexity depends on its average, i.e.,
Ccs = = (
M Σ K F)))..
In Tab report these values for the two experiments. As is evident, CS leads to greatly reduced constant both cases over MCS, which is in agreement with the general improvement in PSNR for this method. We note, however, that these constants do not capture all the phenomena seen in the experiments. For example, MCS performs worse for Example than it does for Example C.1 Yet the size of the constants would suggest otherwise. This is an interesting gap between the theory and practice.
C.7 Variations involving C'>
The setup described so (sampling the Fourier transform) a discrete model for so-called single- coil MRI. However, modern MR scanners typically employ parallel coils. Here, multiple receive coils acquire Fourier measurements parallel. Let 2 1 be the number of coils. Then one can model the measurements in parallel MRI as
Pr. + c.
Here by E Cm are the measurements in the eth coil, Ωe S [ (I,...,,N N) with [a = m. and S, is diagonal matrix, known as the sensitivity profile of the coil. See, e.g., [76 [16..
This is multimodal sampling model that can be cast into our framework. Indeed, we replace the single sampling operator (C.I with C sampling operators defined by
(z) v M/N((FS,)))))
CP, E c= c= l,..,,
Note that empirical nondegeneracy (2.5) is easily shown to be equivalent to the condition
a < 1(S))a SB, =i=l....
32

---

Sensitivity profiles are often designed so that this property holds with moderate a, B. Note that practice the sensitivity profiles are not known, and have to be computed either via calibration pre-scan or learned during the process of recovering the image. See, e.g., 5 Sec. 3.5.2-3.5.3) and references therein.
D Solving PDEs using PINNs
In this appendix, we provide further details for the example considered in Section 3.3 involving solving the nonlinear Burger's equation using PINNs. As mentioned, we implement CS adaptive manner for this example, using a strategy we term Christoffel Adaptive Sampling (CAS). This strategy not only applies the numerical solution of PDEs, but to any regression problem with DNNs and general, multimodal data. We then apply this to the numerical solution PDEs through the framework of PINNs.
D.1 PINNs for solving PDEs
Consider spatial domain D C Ie and time interval I = (1, where d 2 1 and T 2 0, respectively, Then we seek to learn an unknown function u" x [0, T) : C given as the solution PDE of the form
Lu f in D x I 1n in (0)
on OD x (0,
Here C is differential operator in the space and time variables, is known initial condition and Wp a known boundary condition. Throughout this section, we use f to denote the right-hand side of the PDE and u" to denote the target function (instead of f*), as is customary in the numerical PDE literature.
The general idea behind PINNs 69 105 is to consider training data of the form
(((x), 19), [24 Km u ((((), 4), n" (1l, 4)) (((,), (2), n² (2), 13)m
where (xd, (8) E D x (0, are sample points in the interior of the domain, (c4,4) 4) E x {0} are sample points at the initial condition and (x,, +b) e aD x (0, T] are sample points on the space-time boundary of the domain. Typically, these sample points generated via MCS. One then seeks minimizer of the problem
ml
Lu(x, (4) f(x 12)1
(((),)) (u(2),))P
min uEU
Ml
Ab
m7
th) upb tb)1
774
where U is class of DNNs Rd x x R and X₁ Ao > 0 are hyperparameters that control fitting the PDE versus fitting the boundary/initaal conditions. Note that we write and u E U throughout this section instead of IF and F. to avoid confusion with the right-hand side of the PDE.
D.2 PINNs formulation in terms of the general sampling framework
We now show how to reformulate PINNs in terms of the general sampling framework. Since there are three types of data, we let C' Then we define D, D (0,T). D3 D {0) and D3 = 0D x (0, 27, and let Pt, and Pa be measures on these domains. We then consider the sampling operators
(u) Lu((), y (z,t) E D1 [2)0(()) = Vigu()). y (x,1) E Dr y (z, E Dg.
(D.1)
(a())u) = Vlu(O),,
33

---

Next, we let v. Dr + R and Me be as in Assumption 2.2 Finally, for each = 1, 2, 3, we draw me samples (i) where ic (Xie: Tec,, and consider the weighted regression problem
me To (o(()) (=(()))( (
min WEU
(D.2)
mc
Vo
There are several factors that prohibit direct application of CS to (D.2) The first is that the sampling operator L1 is potentially nonlinear, since it involves the generally nonlinear PDE operator L. This means that there is no theoretical basis for the use of CS. However, even if it were linear (e.g.. for linear PDE), it could be very difficult compute the generalized Christoffel functions Kv(U) in practice, since evaluating (U) at a single point 0 involves solving a maximization problem over the space U class of DNNs). The second, and arguably more critical issue, is that PINNs typically implemented in the highly overparametrized regime, where the number of DNN parameters greatly exceeds the amount of training data. CS is designed provide sampling measures that ensure "good' recovery over the whole of the space U. But this is an extremely conservative approach for DNN-based learning problems, since only certain DNNs are likely to be encountered in training.
We tackle these problems in reverse order. For the second, we present an adaptive sampling approach for deep learning. This is described in the next subsection. Note that this does not assume the underlying problem is a PDE. Our presentation follows the lines of the general sampling framework. Having done this, we then describe its application PINNs, including suitable modifications of the sampling measures and loss function that take into account the nonlinearity of the PDE operator.
D.3
CAS for deep learning with general, multimodal samples
In this section, we consider DL based general, multimodal samples introduced in our general sampling framework. What follows is an extension of a method first introduced in [3], which in turn is based on ideas from [35]. Let X be Hilbert space of functions RR: + Id and U C X be class of DNNs of a fixed architecture. As Section
2
we consider sampling operators
Le De B(%, Wo), e= c=
where the Ye are Hilbert spaces. We also write u² E X for the unknown function we seek to learn.
We now describe the adaptive sampling method. This exploits the so-called adaptive basis viewpoint of DNNs, developed in [35] Let n E N be the number of nodes in the penultimate layer of the network architecture used to define U and, for convenience, assume that the output is not subject to a bias term, just weight. Therefore, can write any E U as
u = C H,
(D.3)
where H Rdd R. is a DNN of the same architecture as u, except for the final layer, and C (cy) R the weight matrix on the output layer. Now let u, : Rdd - be the ith component of u, = ,,...,d2, and H₁ Rd - R be the ith component of H, i = 1,...,?. n. Then we can express hy as
Uj Σ Ciy
Hi,
j == l........ d2.
1=1
In particular, each Vj is an element of the subspace span ( (H...., Hn).
Now consider an initial DNN â (()) ( obtained via standard (random) initialization
strategy. Write â as in D33 as
()) (((0)) (0)))
let (0) = (H)
y and consider the subspace
( span
10)0 17(00))
so that ( E H j 1.... dg. Let Pu ()) S n. We now perform CS using this subspace. In other words, we define sampling measures
(0) Ka (H)()) (0)
du (0) =r (0) dp)()),
c= 1=1,.a C,
Po
34

---

then, for each e, we generate m. sample points Oee i.i.d. from _i= and generate samples as
Vic (w"))) i 1...... m c= c=l....,C.
Given these samples, we then train a new DNN by applying a standard optimizer to the minimization problem
min ueU
llvee (w)
(1) (O i=1
Let (1) E U be resulting DNN. The idea now is repeat this process by drawing (2) m1)
(1)
new
samples using CS for the new subspace H()) and then using the full set of m! samples to compute
DNN a(2). Continuing in this way, we generate sequence of DNNs a(L), a(2),
U
approximating the unknown function u". To be precise, consider step / 1. Let (t-11) be given, write
= 11-1),
(11-1) (H )
and define
H span (7(1-1)
A(-"),
P1-1 dim (1)
We use this to construct sampling measures
K.
du (0) (0)
(
c= 1,...,c C2
Pt-1
and then, for each we generate m me (1-1) new sample points O i = me (1-1) + me
i..dd from p (1-1) and corresponding samples
yic (u)),)(uu),
m (1-1) + I,..., m c L..,.,,
We then combine these with the existing ma (t-1) samples, giving total of m!! samples for each c, and then use this to train new DNN via the minimization problem
Mice Lo(O
min
REU
Mc
i=1
Vc (Ote)
We write (1) for the resulting DNN.
D.4 CAS for PINNS
Our aim now is to apply the CAS method in the previous subsection to PINNs. In this case, we set dj d and d2 1. As we now describe, we make one main modification CAS in this case, which is replace the true generalized Christoffel functions Ke with surrogates K2 that are more amenable to computations.
Recall that C' = 3 in this case and that the sampling operators are as in D.I. To define K₁ we simply forget the differential operator C and define
[1(2,)) l E II 11- (x, D (0,T). | (D.)
K (1) sup
Next, for the initial (c 2) and boundary (c 3) data, we define
h =OV-DNNO }
1)2
(x) sup
(x, E D2 D (0)
| 22, (Dz)
and
(1( sup
[1(2, 1)
h H (a,t) E D3 = 0D x (0,T).
|1Al122 (Ds)
35

---

Let (0 and ai denote the corresponding weight function and sampling measures, i.e.,
(x, (x, v dp,(zz)) t), (x, (Z,
c c= 1,23.
(D.4)
P1-1e
Then at step of the procedure, we generate me (1)
(1-1) new sample points (Xio; Tio), i
me
(I-1) +....., me i.i.d. from Pe ((1-1) and compute the corresponding samples
Vic. Lo(Xio Tic)("), i i= == +1,...
m 1,2,3,
where the Le are as in (.I.) We then combine these with the existing me (1-1) samples and use this to train a new DNN via the minimization problem
3
min
Uhe Lo(Xier (u))
(D.5)
UEU
mc
(0
We term this method for PINNs. is summarized in Algorithm 2
Steps 2-3 of this algorithm require some further explanation. First, as in previous examples (see Appendix we introduce finite grids Ze = hrc c 1, 3, to represent the domains De- 2, 3. This is to enable efficient sampling from the measures Plc, which
discrete measures defined over the corresponding grids. See the next section for the construction these grids.
Second, recall from Lemma E.1 that in order to compute the functions K we need to construct orthonormal bases for space
span(fF (1 ..... ((
over the finite grids Z Previously, in Appendix B..4, we did this via QR factorization. However, the dictionary [. ( Ji=1 generated in Step 1 of the algorithm is often numerically redundant. Therefore, in this case we use a truncated SVD instead. Specifically,
N..N
1 - VN=
Bg
ijj=
then we compute its SVD V. and define the numerical dimension
Pt-1cc maxfi oze/o1c > & NJ..
Using this, we now obtain an orthonormal basis over the grid Ze using the first Pt-1.c left singular vectors, i.c. the first pi-1,e columns of Uc. Given this basis, we can then compute the function K2 ())( over the grid via Lemma
E.1
To precise,
K ( (2)))) =
Σ 1=1
i= i= 1,....,, No. (U.)
and the corresponding measures Le are given by 0 Go if
P(O zie)
i= 1,..,,,, No.
11-
D.5 Additional experimental details
In this section, we describe the setup for our experiments. The problem we consider is the Burger's equation with D = 1), 1,
Lu = 0,u + udzu (0.01/T)0mnu,
and initial and boundary conditions
u(z, 0) - sin(TT)), E D,
36

---

Algorithm 2 CAS for PINNS
input: PDE operator L, initial and boundary condition u; and ub. Class of DNNs U with fixed architecture, no bias the output layer and penultimate layer of with N. Finite grids Ze
[Zic]i=) C De. where Ne 2 N, C c= 1,2,3, numbers of samples = m < m (1)
(2)
< me < <...
3, and tolerance 8tal 0.
initialize: Initialize the DNN (0)))
for / = 1 to t do Construct the dictionary {
A " via the relation
a (1-1)
(1) Construct the sampling measures fi C 1,2,3, as D.4
For each c = 1, 2, 3, draw ml m (1-1) m sample points (Xi,es Ti,)). = me + 1,.... mc
(1-1)
(1)
Train the DNN ((() E by applying a standard optimizer to D.5 with initialization a (1-1)) end for output: A sequence of DNN approximations (01) (2, 7 to u.
and
u(-1,t) = ((1,t) 0, t (0,
respectively. As mentioned, we employ three finite grids
21 = { ((a1) E (-1, x (0,
Ni 16, 000,
Z2 No { {(0,2 (2) No 6 (-1,1) x {0),
N2 2000,
No Z3 (2 i==1 (1s,,tt)) / E (-1,1) x (0, 1].
N3 2000.
Following Appendix these are generated once beforehand by MCS with respect to the uniform measure over each domain.
We now describe further aspects of our experiments.
Methods considered. As in previous appendices, we compare CS with MCS. Specifically, we consider DNNs trained using training data constructed via CAS (i.e., Algorithm 2). and DNNs trained from standard training data obtained via MCS from the uniform measure over each domain. As in previous example, we labels these as *CS' and 'MCS', respectively. For Algorithm 2 we use the threshold parameter 8eat 10-6, since our computations are performed in single precision.
Choice of architectures and initialization. We consider fully-connected DNNs with activation function L 2 hidden layers and an equal number of N > 1 nodes per hidden layer. We term these N DNNs. Since we are solving a regression problem, we assume the output layer not subject to p. We also set the bias to be zero in this layer. For the activation function A. we consider either the Rectified Linear Unit (ReLU), hyperbolic tangent (tanh), Exponential Linear Unit (ELU), or sigmoid.
These are defined as follows:
ReLU:
p(x) = max xr 0),
2xr
tanh:
p(x) = 22 +1
ELU:
p(x)
{x x 0,
- : < <0,
sigmoid:
p(z)
1+ ex
Note that we choose DNNs with fixed number of nodes N for each layer. Moreover, we also focus on DNNs with depth L such that the ratio L/N is small. This is motivated by results in 62.. To be precise, L/N- 0.1 in our experiments.
For the initialization strategy, we consider weights and biases with entries drawn from the Normal initialization with mean 0 and variance 0.1. Having in mind the size of architectures described in this
37

---

Table 2: Number of samples per iteration for each domain
parameter
Number of samples me
(!)
2
3
4
5
6
7
8
9
C
400
1350
2300
3250
4200
5150
6100
7050
8000
2
100
200
300
400
550
650
750
850
1000
C= 3
100
200
300
400
550
650
750
850
1000
Total
600
1750
2900
4050
5300
6450
7600
8750
10000
work, this initialization leads smaller variance than commonly used initializations used PINNS such as the well-known Xavier and He Normal initializations. Besides, it has been shown that is an effective choice for function approximation, see 66 65]. In all our experiments, the DNNs were initialized with the same seed to compare the effect of varying the samples.
Optimizers for training and parametrization. We use Adam the optimizer in combination with an exponentially decaying learning rate with respect to the number of epochs. For both CAS and the procedure based on MCS, train the networks following schedule number of epochs, described as follows:
n (0) 5000, n =
121
For the CAS strategy, we train the networks for (1) epochs on each new set of samples, using the weights and biases from the previous set as initialization. We repeat this procedure 9 times, i.e. we train for a total of 225, 000 epochs. For MCS, we train the network for total of 225, 000 epochs as well, stopping every (1) epochs add more data points drawn from the uniform distribution, and continuing to train from the previous point.
Training data and design of experiments. To measure the performance of these methods, present the average testing error and run statistics over 20 trials for both sampling strategies. We train our DNNs over set of training data consisting of the values
3 Ull(Xio: Tio), u(Nior Tim) m c=1
For each 1,2,3, we generate each data set of size me (1) with 0 < me <... < me < <... < me (9) we sample 20 i.i.d. sets of points { m)
from the sampling measures for each strategy. The
precise values for the numbers of samples m (1) given in Table
Testing data and error metric. Let u² be the solution of the PDE and á be a DNN approximation to We compute the (discrete) relative error
ExEzI (2( 0(2)12
Exez' (u* 6(2)12
E(u") = V Σ.Ez. 1u- (2))2
Σ.Er. (=)1²
where Z = 2 ZZ Zz. and M = M1 + M2 + My. Here, for each = 1,2,3, Z is a test grid of size M,, with points drawn randomly from the uniform measure over the corresponding domain. We set Mi = 8000, M2 1000 and M3- = 1000 in this work.
To generate the training and testing data, we have to evaluate the true PDE solution over the corre- sponding grids. We compute this solution to an accuracy of 10 using the numerical solver BURG- ERS SOLUTION, which is implemented in [14). This is available from https: //ppop/e///ppeeeee///e math. sc eedu/Buruee bearkkrddtnnsrrc/bbee wtt.srrrouurgrreooottiiioooo bourgers_solutee license.
html under the GNU LGPL
Plots. As in Appendix B.5 our error plots display the geometric mean enror value and a shaded region corresponding to one (geometric) standard deviation. We also plot the points generated by the final iteration of CAS. We visualize the density of these points using the package densityScateerChrr in MATLAB using "ksdensity" as density method and a E [0.2, See httpps:/wwet http:::/wwwwwwwwwwtteeee www.wwwwwwwwss..ommm www.///ttaameet..i.eeea cowm://mttaaeeettal//lleeeeeeeet
15528-dennityycattrrhaaa''ss tid=Ft_dii__e rc3 BaadddFxrre_beeaaa/aa for more details.
38

---

28
LOSE- 0I7O1 El
66
0.39
4.
44
40
48
035
JACC
6003
1.30
$5.30
1004
Figure 9: CAS for solving PDEs with PINNs. Plots of (left) the average test error E(u") versus the number of samples used for training ReLU and ELUS 5 50 DNNs using CAS (solid line) and MCS (dashed line), (middle) the samples generated by the CAS for the ReLU 5 50 DNN and (right) the samples generated by CAS for the ELU x DNN. The colour indicates density the points.
Enst error (l
101
42
42
S.C.A.
00d0 3NC25
0.15
0.0
0.40
Test GTTOF (l(o))
0.40
46
4.
035
82
172
0.2
2.-
0.5
0.2
0.2 04
0.5
0.
Figure 10: CAS for solving PDEs with PINNs. Plots of (left) the average samples used for training 3 DNNs using CAS (solid line) MCS (dashed line), (middle) the samples generated by the CAS for the tanh (top) and ReLU (bottom) 3 x 30 DNNs and (right) the samples generated by CAS for the sigmoid (top) and ELU (bottom) 3 x 30 DNNs. The colour indicates the density of the points.
E(u") versus the number
Implementation, hardware and compute time. Our experiments have been implemented in TensorFlow version 2.5. This implementation has been inspired by works [9].
The computations were performed in single precision using NVDIA Tesla P100 GPUs Compute Canada's Cedar compute cluster. To be precise, each node used in these experiments has CPU cores and 128GB of memory and four Tesla P100 GPUs with 16GB memory. See https:://occ. alliancecan. ca/ ca/wiki/Cedar for further information.
The compute time is roughly one day for the computations involving the p 3 x 30 and 5 x 50 DNNs and 2 days for those involving the p x 100 DNNs. Therefore, the total compute time approximately four days.
39

---

58
Test arror Bl
44
-4-00rid1e 10 203255
4.
1091
100
$5.33
10004
62
1088 0ID0R
BELUTE KECUST 100
4.8
Figure 11: CAS for solving PDEs with PINNs. Plots of (left) the average test error Euu") versus the number of samples used for training 10 x 100 DNNs using CAS (solid line) and MCS (dashed line), (middle) the samples generated by CAS for the tanh (top) and ReLU (bottom) by CAS for the sigmoid (top) and ELU (bottom) 10 x 100 DNNs. The colour indicates the density of the points.
DNNs (right) the samples generated
D.6 Further experiments and discussion
In Fig. we show the same results in Fig. except using the ReLU and ELU activation functions instead. Here, none of the methods lead to decreasing test error as the number of samples increases, although the errors for MCS
somewhat larger than those of CAS. As is evident from the plots of the samples points, CAS fails to adapt the sampling measures to the PDE solution in this experiment, unlike in the case of Fig. 3
This experiment indicates that the performance CAS in relation to MCS is heavily influenced by the choice of architecture. To further explore this phenomenon, in Fig. 10 and Fig. I1 we consider 3 x 30 and 10 x 100 DNNs, respectively. In the former case, we once more see no decrease in the test error for the ReLU and ELU activation functions. The test eтror for the tanh and sigmoid activation functions does decrease with increasing m. Yet, CAS leads only to a marginal benefit over MCS for the tanh activation, and leads to worse performance for the sigmoid activation. As can be seen from the plot of the points, the CAS fails to adequately cluster the points in the case of the latter.
In Fig. we consider x 100 DNNs and see decreasing errors for the tanh and sigmoid activations, with CAS giving better performance than MCS. For ELU activation function, while the error (slowly) decreasing, CAS actually performs worse than MCS. Once more, for the ReLU activation function, we see no convergence.
The discrepancy in performance between the different activation functions is mirrored when we examine the training loss. In Fig. 12 we show the training loss versus number of epochs. For the best- gest-performing tanh and sigmoid activations, we see significant decrease of the training loss, whereas for the other activations we see slower or sometimes no decrease. Note that all DNNs are trained using the same hyperparameters. This behaviour is in some senses unsurprising, since the worst-performing activation functions are only piecewise smooth and the training loss involves PDE operator. Another notable feature is that MCS generally attains smaller training error than CAS. Therefore, there scope further improve the performance of CAS by improving the training procedure.
40

---

109
10
10
10"
10
10
3821 20.5AS
217 43383
107
10
TLU 20303
107
100
10-
Kowel
10*
0.5
1.5
10a
0.5
1.5
2.5
-307
Mi 189-AS
10
viganed 18 IN---A
16a
SEU 39 LMB-AA
167
200
10a
10
10
10
12.0
10a
Figure 12: Plots of the training loss versus the number of epochs for the CAS and MCS methods with 5 x 50 DNNs using 20 trials. The vertical black lines indicate the number of epochs at which more samples are added the training.
Finally, in Fig. we plot the functions K., c 1,2, 3, that are used generate the sample points at the final iteration (see Appendix D.4]. Here, once again we see that the tanh and sigmoid activation functions lead to functions K₂ that peaked according to the behaviour of the true PDE solution u". However, the ReLU and ELU activation functions fail to capture this behaviour.
E Proofs of the theoretical results
In this appendix, we give the proofs of the results from the main paper. We commence with the following lemma, which gives several properties of the generalized Christoffel function that will be needed later.
Lemma F.1 (Properties of K (F)) The generalized Christoffel K (see Definition 2.6 has the following properties.
41

---

3.4
300
02
46
40
84
048
47
44
%
-.5
03
0.30
3002
V
2.0%
100
42
100
44
0.00
Figure Plots the functions Kos 2, right), that are used the generate sample points in the final iteration of CAS in the case of the 5 x 50 DNNs with tanh, sigmoid, ReLU and ELU activation functions (top to bottom). In the third column, the blue and red curves correspond to the x = and x = -1 boundaries, respectively.
(i) Let F be a finite-dimensione subspace of X. Then
(( S Σ (L(A)(A))&
(E.1)
for any orthonormal basis [ of F. Furthermore, if has dimension p then
(OF)(O) (((()((A))
In particular, E.1
holds with equality when dim
(ii) Let F1,Fy C X. Then
K (F) max ((F.)()),
42

---

(iii) Le,F2 be finite minite-dimensionae subspaces of X. Then
+ (F) + (F2))
(iv) Let F S X and ((F) = U//1l/ll ff I [00)) Then
((B(F)) = ({F)(O).
Proof. We commence with the proof of (i). Write f RR + as f Eis acl for & with
E la 2 = |1 Then
Σ L(((()))
- = (()(()))
and therefore
(() & Σ (1(0)
For the lower bound, let (ei,..., c,] be an orthonormal basis of Y. Fix j E {l...., p} and consider Ei= cafe, where = (ey, (f)) Then
2 Ke,, ((00010)1)))))
1
(L()))) = Σ te, 11000000
We also have
|
(ej, ((0)(1)))x)
Therefore, we deduce that
(FF) 2 Σ Keg, L(0)(f))xl
1=1
Since j was arbitrary, we now sum over j and use Parseval's identity to obtain
PK(F)(0) > Key, L() ((()()
as required.
Part (ii) follows immediately from the definition of K. Now consider (iii). Write F
G1 @ G2, where G = Fj and G2 = F, nFj satisfies G2 1 G1. Let f E F, f * O, be arbitrary and
write 91 + 92 for 9: G 1, Then
(f)
(1)
12 ((2(0)
|1
1191 12 ||02|1
(I((0) + [(2)
2
11
$ 2 (()))))))))))))))))))))))))))))) (O)
2 2((((F)) + ((F2)
where in the last step we used the fact that C2 C F2. Since f was arbitrary, the result now follows. Finally, consider (iv). By the definition of K, B(F) and linearity.
((B(F)) = sup
[ fEFMO)}
((()
f 12,101 -x())))
= sup
(())
11/112
required.
43

---

For the remaining results it is useful to introduce some additional notation. Let
be the overall measurement space, Note that this is Hilbert space, when equipped with suitable norm. If y = (yie) is arbitrary element of Y, we take this norm to be
me
1
Σ
yice
De be the tensor-product space and write (0se) for an arbitrary element of D where 0ic E Dr for ..... me and c 1, I,....C Then we define the overall sampling operator
Now 1et m mi + +... mc, D = 0 Di=i
Veclleeclmm Lnollcc) (
M : D (%%, Y), 0 (0te)
(E.2)
Note that the operator on the right-hand side given by
(0 Y.
fe Xo
Further, we note that the nondegeneracy condition is equivalent to
all.f1i -
Il S B A E xn_
(E.3)
Here 7 & C
me 111
Me is the probability measure the full sample (0te) := =
Next, given measurements as in 2. Or we define the scaled measurements ÿ = (Die) E Y by
The
Vies
i= I...... Mey c= L.....,CC
(E.4)
Vo Ve((rr))m
Then, with M as defined in E.2 the regression problem 2.2 is equivalent to
argmin jEP
((O)
(E.5)
With this hand, we now prove Theorem 4.2 Theorem 4.2 when F is itself subspace,
For this, first useful prove special case of
Lemma E.2 (Special case of Theorem 4.2 for subspaces). Consider the setup of Theorem 4.2 where F is a subspace of dimension at most Suppose that
mc 2 Co
ess ess sup (K.(()(0)/vv(()) log(2n/8), Ve 1....,C Bm-p
for some O < where
log(1 +7) - -1 Then 2.5 holds with probubility at least 8.
Cy =- (11+
(E.6)
Proof. The proof of the result in this case is a straightforward application of the matrix Cherooff bound [15] Let { be an orthonormal basis for Write arbitrary F - cffi. so that [ x = || where e = (c)). E " Then
1
|M))
(,,) (fw)
c=1
1=1
me
mc i=1 (rse)))
c=1
j.k=l
C
c
Σ
Xic c.
1m1
44

---

where Xic are the independent, self-adjoint, n x random matrices with
d (.000,
Xic ma.)((O.))
JAk=1
Thus, the result is equivalent to the condition
mc
me
(1 cja S Amin
Xse
I Amax
X
1 (1+ c),.
c=l 1=1
Notice that X ž 0 and, due to
(E.3
C
C ΣV
S Amin
EXic
S
Amax
EXic
S.B.
1=1
c= 1=1
Now, with / Ei= ah FF, we have
1 c'x (oVo(Oio)
(LWW)) S
Ke (e
(Oz)
Thus,
Amax Amax(Xic) S me (Fs)su((KK())))))))
B~pe
almost surely. The result now follows from the matrix Chernoff bound.
Proof of Theorem 4.2 Let f E B(F F). Then there is j E {I.....d} and fz E F, n B(F F) such that ||ʃ - fلll S t, where t = / /c/2.. Observe that
[ + (IM fi)ll > (I 2 (M( Now, with probability one,
fi>l
(.(O))) B)ll S Ill fyll s ox
mc 1=1 (eic)
Using this and the fact that B 2 we deduce that
[I + 3e/2 > (I (I axe/2.
Now let E be the event
F and note that our goal is show that P(E) 2 1 1 8. By linearity, E is equivalent
(1 (1-e)a 1/ V (1+
c) IM < (1++)8, Af e B(F FF) Hence, by the above argument, we have
PEE P
0 Ej 1=1
where E, the event
(1 < 5
AfE E
By the union bound
P(E") P(E))
Suppose first that n 2 1. Then (OF & (F) and the condition 4.1 on the m. and Lemma E.2 give that P(E S 5/d.
The gives the result for n 2 1.
For 0, we have that F (fi) is singleton. Notice that IF, C span((F)) and K. (T)) =
K (span(()) Hence we may apply Lemma E.2 with n. 1. We deduce once more that
P(E5) < 6/d. This gives the result for = 0 as well.
D
45

---

Remark E.3 (The norm in Theorem 4.2) Write F' = -B(F -B).- Then it follows from the definition of the Kg that
- S2ll S eaSSuPappe (F E1)/u((0)1111 f2l1x. V/1,22 EF.
Therefore, the cover in Theorem 4.2 could be constructed with respect the X-norm, up change in the constant f. Notice that the quantity that bounds Il f2ll in terms of | fellx involves the generalized Christoffel functions K2(F', IF') and weight functions Ve. Therefore, sampling according to the generalized Christoffel function (on a slightly modified set) also minimizes this constant, and therefore the size d of the cover in Theorem 4.2
Proof of Corollar 4.3 clearly
IF
Li a union of d subspaces of dimension at most n, then U
B(F F) =f F.
follows that ( provides [II-II|, n, -sssuspaace covering of B(F - IF) ) for any 0. Hence
we may apply Theorem 4.2 with this cover. Since 1 F, F - F in this case, the result now
follows immediately.
Proof of Corollary 4.4 When n 0, the sets Fj {f}} are singletons and we must have F S
B(F - F) by definition of the covering. Hence F C B - F), which gives that ()) s
(B (O). Using Lemma E.1 deduce that Kg (0) S KF ()) This implies the result.
Proof of Lemma44. 4.6
Since K (F) is integrable, the quantity x(F) is well defined. Also, ((F)(0) > 0
almost everywhere, due the assumption on L and F.. In particular, <(F) 0. It follows that D² is measurable, positive almost everywhere and integrable with So of (0) dp(O) 1. Clearly,
(()(((()//> (0)} <(F).
8mup
now show that this is the optimal value. Let v be any other such function. Then
/ ((F) v(0) dp(0) = -f ((F) x((F).
ess supp
8rup
v(0)
This gives the result.
Proof of Corollary 4.7 We first prove the result when d = 1. Let (fi be an orthonormal basis for F1 -F. Then Lemma E. gives that
K. -FFFFF)(()) < |1.(0))))))
Therefore,
C Σ1 /
n K.(F ())) (0)
(F F) F)=
(1)(())()) dp.(O).
Assumption 2.4 and orthonormality now imply that
(I F) <
l < Bn.
Now suppose that d > 1. Lemma E.
gives that
K.(F F)(0) = max K. K.(F))(0)
ji.....d
46

---

and therefore
(((F-F(()))
Ke (F Σ
j=1
Using the result for d get
(F F) Bnd,
as required.
Remark E.4 (Lower bound on D c= (F - F)) Suppose that dim S p E N, Vc. Then
Lemma E gives, for subspace G with an orthonormal basis {9:)
K. ()) 2 (o)())
Using this and following the steps of the above proof, we deduce the lower bound
Σ Ko(F F) 2 om/p.
For this, first require the following lemma. Lemma E.S. Suppose that a realization 0 = (0ic) E D of the Oie gives that
Finally, prove Theorem 4.8
a'l1fll & (IM())()
F
(E.7)
for some a' O. Then any y-minimizer f of (.2 satisfies
11 - 1'1 I inf SEP
|15* 115- f1lx Va
-
2
/ l|āllz +
7
Va
where ==
Ie esc
Proof.
Let f F. We write
- - s 11 - fllx 11 fllx
< (I) O]lly 1| Sllx
$ $1/Vo -ūll + 1/Vao'll M(0) ||5 flxx
We now use the fact that o is a 7-minimizer and the fact that y = M(O)(f)) to get
Il fl1lx < 2/ M(H)(() ø| || 4/Va
<
- + + 11f fllx + t\/Va'
as required.
Proof of Theorem
4.8
Let E be the event
Y Due Theorem 4.2 and the given assumptions, we have that P(E)) S 6. Now recall that 7 is the probability distribution of full draw O Then
c) | < IMMO)) S (1+0)1512
E| f11 = / || f1l dr +
|1 f dr.
F
In the first integral, we use the fact that To is contraction get
|l - fllx (Ta To(fllx llf fllx
47

---

In the second integral, we use the fact that [
S to get
|1 fllx 2o.
Therefore, obtain
E -
/ 11 - f1xx dr 4025.
(E.8)
J
Now, for the first term, we fix f E IF and apply Lemma E.5 Since a' (1 c)a whenever E holds, we get
I [1I5 11f
f11xan
I 115 (155 (1- c)a
4
[f
(1 - c)a |E +
72 (1 - c)a ) dr.
For the second term, Assumption
2.4
and F.3 get
1 11f E
4,
fl S 4
1
|l
fllx
(1
e)-
16
me
472
+ (1 E)a
letelle
duc(Os)
me
Dd vol0.)
(1 - E)a
and therefore
/ 11 -111- dr S
43
|1 -1
(1
(e-
16
472
+
leiel (a(le) + (1 c)a
))x
cml
Combining this with E.8 and recalling that f was arbitrary now gives the result.
Remark E.6 As noted, the noise bound Theorem 4.8 assumes Pc(Do) < Jo. this fails, one may also bound the noise term by assuming the noise takes the form
Le(9:c)
i = 1, me: c= C,
for some E X with ||اl|x < 1. In this case, one has
E
E
1
LL (c
-/ D.
([(()) dp.(0) Blgg
mc
Hence Theorem 4.8 holds with N = 311g112. For other ways to estimate the noise term under different noise models, see, e.g.,
Proof of Theorem 2.7
Part (i) follows from Theorem 4.2
Corollary 4.3
and Lemma 4.6 with the
(arbitrary) value from Corollary 4.7
/2. Part (ii) follows from part (i) and Theorem 4.8 Finally, part (iii) follows
48


Reviews:
[{"review_id": "Mj7CyVt3AH", "reviewer": "Reviewer_9pYz", "summary": "The authors introduce an active learning framework for regression problems based on the concept of generalized Christoffel functions. The proposed approach is applicable to a broad range scenarios and it is evaluated on several scientific computing tasks.", "questions": "Although the manuscript lists 118 references, I think it lacks a more thorough in-text discussion with other available active learning strategies. Which literature gaps are addressed? Which scenarios are not entirely covered by standard methods? \n\nAs a final minor observation, the left plot in Fig. 2 present some difficult to distinct line patterns which could be improved.", "limitations": "The manuscript states sufficiently its limitations.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The manuscript present a comprehensive explanation over the main ideas behind the proposed CS4ML framework. The main motivation is relevant (active learning for diverse data scenarios) and the authors point promising directions for further investigations.\n\nThe work is well organized, which is especially important for theory focused contributions. I also praise the detailed provided supplementary material.", "weaknesses": "The experimental section, although tackling diverse tasks, unfortunately compares the proposal only to an inactive learning strategy (Monte Carlo sampling), which diminishes the relative impact of the introduced method. I appreciate this point being highlighted as a limitation by the authors, but it does leave the reader wanting a bit more.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for these excellent comments. We will discuss them in reverse order:\n\n### ``Although the manuscript....''\n\nIn terms of active learning, the main contribution of this article is to extend certain active learning techniques (namely, leverage score sampling) to much broader types of measurements.\nThe majority of past work on active learning considers pointwise samples of a target function. In fact, we are unaware of any works that systematically tackle more general types of measurements like we do in this paper. This is the main gap in the literature we aim to address.\n\nWe fully agree, though, there should have been a more thorough in-text discussion of the active learning literature in the paper. Some of this discussion can be found in Appendix A. **As also discussed in our global rebuttal, we will move parts of this to Sections 1 and 2 of the final paper. We will also add more discussion as relevant.**\n\n### ``The experimental section,...''\n\nFor the reasons described above, we are not aware of other active learning techniques for which we could make a 'global' comparison across all three examples. As we commented briefly in the conclusion section (Section 5), there has been much previous research on problem-specific active learning strategies that outperform Monte Carlo sampling. However, the main aim of our article is not necessarily to achieve state-of-the-art performance in each example. Rather, it shows how a single active learning technique (Christoffel sampling), which also comes with theoretical guarantees, can improve against inactive learning across a broad spectrum of problems. \n\nAs we mentioned in our global rebuttal, it is important to compare different strategies. But we think such a comparison is well beyond the scope of the current article. It is likely that comprehensive comparisons in each of our three applications could each make for paper on their own. For example, there have been a slew of recent papers on sampling strategies for PINNs (Example 3 in our paper). We cite these in Section 5. To perform a robust comparison, we would need to consider each method in comparison to CS across a range of different PDEs, rather than just the Burger's equation problem we consider in this article to show proof-of-concept. This is certainly worth doing, due to high level of current interest in PINNs for PDEs. Similarly in MRI, there has been a large amount of past research on sampling strategy design (we also cite this in Section 5). A thorough comparison would need to consider different datasets -- i.e., not just brain images, but other types of common MR image datasets such as knee or abdomen images -- and different MRI modalities (i.e., single versus parallel MRI), as well as different generative neural network architectures.\n\nAs also mentioned in our global rebuttal, another interesting question for future work is whether one could use CS as a starting point for devising even more advanced active learning methods. In general, this could involve using either the linear-sample sparsification techniques of [32], as briefly mentioned in Section 5, or by using 'boosting' techniques (Haberstich, Nouy \\& Perrin). Or, there could be domain-specific tools one could employ to improve the performance of CS in a particular application (e.g., PINNs or computational imaging).\n\nIn summary, we think that these are very interesting questions for future work, but that they are well beyond what we can feasibly achieve in this article. Nonetheless, it is worth elaborating on this matter in the revision. **To address this issue, we will expand the discussion in Section 5 on other active learning strategies for the main examples and re-emphasize the main contributions of CS4ML to this problem.**\n\n### ``As a final...'' \n\nGood point. We will also improve the left plot of Figure 2."}, {"review_id": "6FefrkButF", "reviewer": "Reviewer_tt34", "summary": "The paper proposes a framework for active learning (here meaning that the user controls the sampling strategy according to which the locations of the measurements are made) designed to handle various cases of regression (vector-valued, multimodal, and more).\n\nTo do so, it introduces the concept of generalized Christoffel functions, that will drive the choice of sampling strategies.\nA statistical analysis of the risk associated to the empirical risk minimizer associated to the square loss is conducted, showing that a log-linear number of observations (with respect to quantities related to the geometry of the hypothesis space) allows for efficient training using the Christoffel sampling strategy.\n\nNumerical experiments on three different problems (all cast inside the cs4ml framework) complement the approach, showing improvements over the naive Monte-Carlo sampling.", "questions": "I found the notation to be quite heavy and not intuitive at all. I suggest to change the name convention adopted here - while all notation choices are arbitrary, they need to be driven by simplicity and logic. In particular:\n\n- I suggest adopting $x_{ic}$ for the measurement locations, to be conform to the classical $y = f(x) + \\epsilon$ regression statistical model. Anything evoking something we usually put inside a function call or put measures on is ok ($\\theta_{ic}$ ?).\n- It feels weird not to have the random variable $Y_c$ living in the space $\\mathbb{Y}$. Measurements could be $y_{ic}$ instead of $b_{ic}$.\n- To lower the number of different letters, the true function associated to the generating process could be $f^\\star$, and the candidates could be $f$ (instead of $u$), keeping the estimate $\\hat{f}$.\n- In the regression literature, hypothesis spaces are usually referred to as $H$ or $F$. If the measurements locations are $x$, the name of the object space has to change as well.\n- In definition 2.4, you introduce yet another variable name $\\mathbb{V}$ that could just be the variable name of the hypothesis space, to improve clarity.\n\nOther questions/comments:\n\n- Where do you use non-boundedness of the measurement operators ? Could you not use the standard notation that elements of $\\mathcal{L}(\\mathbb{X}, \\mathbb{Y}_c)$ are bounded linear operators ? Usually unbounded operators are not defined on the whole space $\\mathbb{X}$ but only on their domain.\n\n- Could you comment on the need to parameterize the measures using two other measures ? $\\mathrm{d}\\mu_c(y) = \\nu_c(y) \\mathrm{d}\\rho_cc(y)$ ? In the end, we first choose $\\rho$ then take $\\nu$ according to the CS strategy, so what is the influence different choices of $(\\rho, \\nu)$ yielding the same $\\mu$ ?\n\n- Empirical nondegeneracy as presented in Eq. 2.5 is a void concept, unless $\\alpha' \\approx \\alpha$ and $\\beta' \\approx \\beta$ are made precise.\n\n- In Theorem 2.5, the symbol you use for the estimator is not defined until way too long after.\n\n- The notion of optimal sample complexity is not well explained enough and I struggle to see exactly with respect to what it is optimal. How can it be optimal given the crude estimate for the sum of Christoffel functions ?\n\n- Section 3.1: Have you studied the impact of the choice of $\\rho$ on numerical performances ? What if $\\rho$ were a laplace measure ? How do you choose $f$ in the experiments ? Also, why not write $(y_i, f(y_i), \\nabla f (y_i))$ ? This avoids the supercharge of the subscript notation in line 752.\n\n- Proposition 4.3, 4.4 could be renamed corollaries or examples.\n\n\nTypos:\n\n- Line 61: vector-valued instead of vector space valued\n- In assumption 2.2, the mappings $L_c$ are from $D_c$ to $\\mathbb{Y}_c$. (also in definition 2.4, check the whole text)\n- In Eq. (2.2) and (2.3) it should be $\\forall u \\in \\mathbb{U}$.\n- \"Hence, the sampling operators and measures preserve the X-norm in expectation\" is very vague.\n- Appendix B1: line 759: no need for the complex conjugate. Why do you need to work in C after having defined your function as R-valued ? Line 763 rho is the same measure for all indexes k.", "limitations": "Most limitations are discussed in the paper. I would also like to mention that the cs4ml framework is not suited to all regression problems, but only to those where one controls the sampling strategy. Alas, in practice you seldom know $\\rho$, because the data distribution is often unknown. (Correct me if I'm wrong)", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed approach is novel and encompasses many valuable problems to the machine learning community.\n- Mathematical details are sound.\n- Experiments show clear improvements.\n- The appendix contains a lot of remarks, additional experiments, that further develop the framework.\n- I share the author's enthusiasm regarding the potential of the framework, which is far from explored.", "weaknesses": "- It sometimes feels that the paper is overly complicated for the sake of generality, without benefits (see questions).\n\n- While fairly general, the framework assumes that the user has access to the data generation strategy (not the targets, but the inputs) which is often not the case in practice.\n\n- Overall, the paper is very dense and notation heavy. It is impossible to read it without a constant back and forth to the (31 pages long) appendix, which makes the reviewer wonder why the 9 pages limit exists for this conference. In my opinion, it would be beneficial to have a longer (i.e. journal) version of the paper, as the supplementary contains many interesting remarks that help a lot to the understanding of the ideas.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for their excellent feedback.\n## Weaknesses\n### Bullet 1\nWe agree that the framework is complicated. This was raised by other referees and we have discussed in our global rebuttal. In brief, we believe it is justified given the range of applications we address. However, we also agree this justification needs to be more clearly made. **Please see our global rebuttal for the changes we will make in this regard.**\n### Bullet 2\nWe are not sure what the referee means here. Our main assumption is that, for each $c$, we can query $L_c(y)(f)$ for any $y \\in D_c$. This is essentially the same assumption as in standard active learning, where $L_c(y)(f) = f(y)$. Note this assumption holds for Examples 1-3.\n\nWe agree that this is worth clarifying. **We will add this as an Assumption in Section 2 and remark that it holds for our examples.** The addition of the classic regression problem to Section 2 will also help clarify this point.\n### Bullet 3\nThis issue was also raised by other referees. We agree, and we will address this. **Please see our global rebuttal.** Regarding a journal version, referee n7M7 suggested that we edit the arXiv preprint so that it was not so appendix heavy. **We will do this.**\n## Questions\n**We agree, and we will change this as follows.** We will rename the measurement locations as $\\theta_{ic}$. We prefer not to use $x_{ic}$, since $x$ is often used to denote a spatial locations, whereas our samples could be, e.g., frequencies. $\\Theta_{ic}$ will the corresponding random variable, instead of $Y_{ic}$. The measurements will be $y_{ic} = L(\\Theta_{ic})(f^*) + e_{ic}$. We will write $\\mathbb{F}$ for the hypothesis set, with elements $f \\in \\mathbb{F}$, object $f^*$ and estimator $\\hat{f}$. We will also change Definition 2.4 to use $\\mathbb{F}$. \n## Other questions/comments\n### Bullet 1\nThis was done to allow for the pointwise sampling operator $f \\mapsto f(y)$, which is unbounded over $L^2_{\\rho}(D)$. However, we agree it is problematic. After considering it, we have concluded it is best to assume that $f^*$ and $\\mathbb{F}$ lie in some normed vector subspace $\\mathbb{X}_0$ of $\\mathbb{X}$ and define $L_c : D_c \\rightarrow \\mathcal{B}(\\mathbb{X}_0,\\mathbb{Y}_c)$, so that $L_c(\\theta_c)$ is a bounded linear operator. In the case of pointwise sampling, one can, e.g., let $\\mathbb{X}_0$ be the space of continuous functions on $\\bar{D}$. **We will change this.** It does not alter the main results/proofs significantly.\n### Bullet 2\nGood question. For each $c$ the set $D_c$ generates the samples as $L_c(\\theta_c)(f^*)$ for $\\theta_c \\in D_c$. The approach pursued in this paper is to find an ‘optimal' probability measure $\\mu_c$ on $D_c$ (in the sense of sample complexity). To do this, we first assume there is a measure space $(D_c,\\mathcal{D_c},\\rho_c)$. Then in Assumption 2.1 we assume that the candidate $\\mu_c$'s are absolutely continuous wrt $\\rho_c$ with Radon-Nikodym derivatives $\\nu_c$ that are positive a.e. This is done so that the search for the optimal $\\mu_c$ is reduced to finding an optimal a.e. positive function $\\nu_c$ that satisfies $\\int_{D_c} \\nu_c(y) d \\rho_c(y) = 1$. We do this by showing (e.g. Theorem 4.2) how $\\nu_c$ affects the sample complexity, and then optimize this bound (Section 4.2).\n\nNote that $\\rho_c$ is often not something we can choose. For example, in standard regression, $\\mathbb{X} = L^2_{\\rho}(D)$ and $L(y)(f) = f(y)$. One can think of $\\mathbb{X}$ as ‘the space in which we measure the error’, in which case $\\rho$ is usually dictated to us. In particular, even though we draw samples according to $\\mu$, the error is still measured wrt $\\rho$. Typical examples here are the uniform measure on bounded domains or the Gaussian measure on $\\mathbb{R}^d$ (as we use in Example 1).\n\nIt is worth explaining this. As noted, **we will add the classic regression problem as an example in Section 2. We will also comment on $\\rho$ and $\\mu$ therein.**\n### Bullet 3\n**We will change this to say 'empirical nondegeneracy holds with constant $0 < \\delta < 1$ if (2.5) holds with $\\alpha' = (1-\\delta) \\alpha$ and $\\beta' = (1+\\delta) \\beta$'.** This is what we prove in Theorem 4.2.\n### Bullet 4\n**We will move the definition of $\\check{f}$ in Theorem 4.8 earlier in the paper.**\n### Bullet 5\nFor a single ($d = 1$) or for a small number ($d \\approx 1$) of subspaces the bound (2.8) is near-optimal, i.e. log-linear in $n$. However, it is highly suboptimal for $d \\gg 1$. We noted this in lines 331-335. However, we agree the reader may well miss this. **We will move this discussion to directly after Theorem 2.5 to clarify.**\n### Bullet 6\nGood question. We have not done this. For the applications that motivated this example, namely regression problems in UQ, it is typical to use the Gaussian measure. We have not seen the Laplace measure used in such applications before. An advantage of the Gaussian measure is that the orthogonal polynomials are tensor-products of the 1D Hermite polynomials, and we also have explicit expressions for their gradients. This allows us to solve the training problem numerically (see Sections B.2-B.4). Note that $\\rho$ also dictates the norm in which the error is measured, i.e., the $L^2_{\\rho}$-norm. Therefore, it is unclear how best to compare different choices of it. \n\nThe test function in Figure 1 was chosen as a simple example to demonstrate the main effects. We could show other test functions, with similar outcomes. **If the referee thinks this would be beneficial, we can add these to the Appendices.**\n\n**We agree about the notation and will change it.**\n### Bullet 7\n**We will change them to corollaries.**\n## Typos\n### Bullets 1-3\n**We will fix these.**\n### Bullet 4\n**We agree and will delete this.**\n### Bullet 5\n**We will correct these typos.**\n## Limitations\nWe agree, but unless we have misunderstood, we believe that this is true of active learning in general. **As noted above we will add this as an assumption in Section 2.**"}, {"review_id": "zNt6OL65LQ", "reviewer": "Reviewer_7Xvg", "summary": "This paper proposes a general framework for active learning. It claims that the proposed method can help achieve near-optimal sample complexity. In additional to the theoretical results, this paper also present 3 use cases, showing favorable results for the proposed method.", "questions": "1. line 19, p. 1: In ML literature, features are represented by $x_i$ instead of $y_i$ while the latter denotes the label, which is $f(y_i)$ in your case.\n2. line 38, p. 2: In your example of computational imaging, is one image an example or one pixel an example? Both cases can occur in real applications.\n3. line 60, p. 2: Do you mean the label function $f$ is in a Hilbert space? For any function with a set of real-valued parameters (e.g., a neural network), if it's represented by a vector of its real-valued parameters, is such a function in a Hilbert space?\n4. line 61, p. 2: What does \"data\" in \"data arises\" mean? Examples of features and label pair?\n5. line 179, p. 5: You claim \"there are many settings where one can acquire both function values and values of its gradient.\" Can you give some real examples of such settings?", "limitations": "n/a", "rating": 3, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "Important topic with claimed good results.", "weaknesses": "1. Poor presentation: Very heavy theoretical setup buried the connection to solving any real active learning problem. No high-level description of the algorithm and its advantages over the existing active learning algorithms. No insights are provided based on the theoretical derivation.\n2. Poor experiment comparison: The proposed method was only compared with random sampling. There's no comparison with any existing active learning method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for their informative feedback.\n\n## Weaknesses\n### 1. 'Very heavy theoretical...'\nThe heavy setup was also noted as a weakness by other reviewers. **As discussed in our global rebuttal, we will edit Section 2 to improve this presentation. In particular, we will add the running example of the standard regression problem.** This should greatly improve the presentation and help connect it to what the reader is familiar with.\n\n### 'No high-level...' \nWe agree that the paper lacks a high-level description of the algorithm. However, what we propose is more of a 'framework' than an 'algorithm'. We do think Theorem 2.5 neatly summarizes the main facets of the approach. **If the referee thinks this can be made clearer, we are happy to hear suggestions.** The reason we do not consider this an 'algorithm' is because there is no general prescription for how to sample from the optimal measure (2.6). This is the main computational hurdle to tackle in practice. As our examples show, how to do this (or, indeed, whether it is possible) is very problem dependent. Nonetheless, this is a important point. **We will add a sentence to the conclusion about this.**\n### 'and its advantages...' \nIn terms of the advantage over other active learning strategies, we are currently unaware of any work that addresses the broad class of problems that our framework does. **Please see our global rebuttal for more discussion on this.**  Our work essentially shows that one can extend well-known leverage score sampling to a very broad class of problems, with theoretical guarantees. **We will add a sentence to this effect in Section 1.2.**\n### 'No insights are...' \nWe already give several insights in the paper. Directly below Theorem 2.5 we explain how one obtains near-optimal log-linear sample complexity whenever $\\mathbb{U}$ is a subspace, or a union of a few (i.e., $d \\ll \\infty$) subspaces. This insight explains how our work extends classical leverage score sampling to a much more general setting. Further insights are also given in Remark 4.5. Finally, in Section 5 we return to the union-of-subspaces case with further discussion. Section A.4 (mentioned therein) also gives additional insight. \n\nWe agree, however, that these theoretical contributions are hard to parse and spread over too many sections. **Referees tt34 and n7M7 also had some suggestions to improve this presentation, which we will implement. We will (i) move the discussion on sample complexity in Section 5 (lines 331-335) and consolidate it into an expanded discussion directly below Theorem 2.5, and (ii) add a brief comparison of the sample complexity bound for CS versus MCS in Section 4.2, demonstrating how this corresponds to the difference between the mean value of the Christoffel function and its maximum.** \n### 2. \nThis is a good point. **Please see our global rebuttal for discussion of this comment and the actions we intend to take.**\n## Questions\n### 1. \nWe agree. This was also noted by reviewer tt34, along with other notational comments. We will change this to $y_{ic} = L(\\theta_{ic})(f^*) + e_{ic}$. We prefer to use $\\theta$'s to represent the measurement location: $x$'s often denote spatial locations, whereas in our work they could be, e.g., frequencies.\n### 2. \nGood point. The short answer is neither. In Fourier imaging, an 'example' is a frequency. Adopting the notational changes proposed in our rebuttal to reviewer tt34, in this problem we wish to reconstruct a (vectorized) target image $f^* \\in \\mathbb{C}^N$ from measurements $y = A f^* + e$. Here $A = P_{\\Omega} F$ is a subsampled Fourier matrix, where $\\Omega \\subseteq \\{1,\\ldots,N\\}$ is a set of $m$ frequencies. In the active learning problem, we wish to select $\\Omega$ (i.e., select frequencies) to recover $f^*$ as well as possible from $y$. This is detailed in Appendix C, but we agree it could be clearer both there and in Section 3.2 of the main paper. **We will add a few sentences for clarity, including the above explanation of what an example is in this context.** \n### 3. \nYes, the target object $f^*$ is an element of the (abstract) Hilbert space $\\mathbb{X}$. In classical regression (see lines 19-22), $\\mathbb{X} = L^2_{\\rho}(D)$ for some measure $\\rho$, i.e., the space of square-integrable functions over $D$ wrt $\\rho$. The reason for considering abstract Hilbert spaces is motivated by applications where the target object may not be a scalar-valued function. For example, in parametric PDE learning problems in UQ (lines 47-48), the target object is a function that takes values in a Hilbert space. In this case, $\\mathbb{X}$ is a Bochner space.  Similarly in operator learning, the target object is an operator, not a function. **As we mentioned above, we will add some sentences in Section 1.2 to better motivate this generalization. We will also add the classic regression problem as an example in Section 2.**\n\nWe are not sure what the referee means by their question. If the function $f_{\\theta} : D \\rightarrow \\mathbb{R}$ was square-integrable over its domain then it would belong to the Hilbert space $L^2(D)$. This doesn't seem restrictive, e.g., it holds for neural networks with (piecewise) continuous activation functions over compact domains. **We would welcome a clarification of this question.**\n### 4. \nGood point. As stated in line 19 (modulo the new notation), in the classical setting by 'data' we mean pairs $(\\theta_i , f^*(\\theta_i))$. In our general framework, the data is pairs $(\\theta_{ic},L_c(\\theta_{ic})(f^*))$. The main point is that rather than function samples, i.e., $f^*(\\theta_i)$, of the target object, we consider linear operators, i.e., $L_c(\\theta_{ic})(f^*)$. We agree this was not sufficiently clear. **We will edit lines 96-100 to clarify exactly what the training data is.**\n### 5. \nThese were mentioned in lines 46-50. However, we agree the reader may well have forgotten this by line 179. **We will add a reference back to Section 1.1 in line 179.**"}, {"review_id": "CfiL6RqLHX", "reviewer": "Reviewer_n7M7", "summary": "This paper studies an extremely general notion of active learning in the $\\ell_2$ norm. Suppose we are able to actively observe data in many different modalities. \"Active Learning\" means we can choose where we observe data in a domain, and \"different modalities\" means there are fundamentally different ways to observe the data. For example, an MRI machine can have many different coils in it, and for each coil we can measure data at a user-specified frequency. The fact that there are different coils with different physical properties corresponds to having \"different modalities\". The fact that we can choose which frequencies to measure data at corresponds to \"active learning\".\n\nThe paper studies an extremely general formalization of active learning in the $\\ell_2$ norm with different modalities in active learning. Specifically, it suggests computing a \"Generalized Christoffel Function\" (i.e. leverage score function) for each modality, and to sample from each modality at random places, chosen with probability proportional to the generalized Christoffel function.\n\nThe paper allows for an exceptionally general notion of \"sampling\", where a sample could entail something classical in numerical linear algebra, like observing a row from a matrix. It can also mean something broader, like observing the gradient of a function. Also, while the error in each modality is measured with respect to the $\\ell_2$ norm, it is the weighted $\\ell_2$ norm with respect to a given measure $\\rho$ for each modality. So, the user can choose to have (e.g.) a uniform error metric on a small interval, or to instead have a Gaussian-weighted error measure on the real line.\n\nLastly, the framework also has enough flexibility to give guarantees in some nonlinear spaces, with the main example being the union-of-subspaces.\n\nTheoretical guarantees on sample complexity are given, roughly matching the rates that would appear in the special case of leverage score sampling for matrices. Further, many experiments and concrete instantiations of the general framework are presented. Applications vary from approximating function with multivariate polynomials, to optimizing MRI reconstructions, to solving PDEs with physically informed neural nets.", "questions": "First, I have some moderately technical qualms with the paper:\n1. In Figure 1, if I understand Appendix B.6 correctly, is it correct that MCS (monte carlo sampling / non-christoffel sampling) is performing worse with more samples because of numerical instability / poor conditioning? Or, like [Line 194] says, is it because the sample complexity of MCS sampling is so bad that the error.... _gets worse_ as the sample complexity grows?\n1. The Appendix doesn't seem to have a fully accurate and consistent instantiation of leverage scores into the CS4ML framework. Specifically, $\\mathbb{U} = \\mathbb{C}$ on [Line 672] seems at odds with $\\mathbb{U} \\subseteq \\mathbb{X}$ when $\\mathbb{X} = L\\_\\rho^2(D)$. I'm pretty sure that $\\mathbb{U} = \\text{span}(A)$ in leverage score sampling? Also, it feels pretty inconsistent to describe $\\mathbb{V}$ as a subset of $\\mathbb{R}^N$ but to describe $\\mathbb{X}$ as a weighted $L_2$ function space on $[n]$. Understanding that much is already non-obvious from the notation, but would be much clearer if you just wrote $\\mathbb{X}=(\\mathbb{R}^N, \\|\\|\\cdot\\|\\|\\_{\\mathbb{X}})$ where $\\|\\|\\vec v\\|\\|\\_\\mathbb{X}^2 = \\frac1N \\|\\|\\vec v\\|\\|_2^2$. Also, there's no reason (afaik) for $\\mathbb{Y}$ to be complex instead of real. Further, the sampling function should more explicitly be about looking up an item from a vector, something like $L(y)(\\vec u) = \\sqrt{p(y)}u(y) = \\frac{1}{\\sqrt N} [u]\\_{y}$. Lastly, from my algebra, I found that $\\alpha=\\beta=\\frac1N$ in equation (2.4) for the leverage score setting. Did I make an error, or is there an adjustment to the instantiation that can instead make $\\alpha=\\beta=1$?\n\n---\n\nAfter that, I've got smaller qualms / typos / recommended edits:\n1. [Line 92] The choice to make $(D_c,\\mathcal{D}_c)$ makes for two symbols which look identical at a first (and second) glance. I'd change at least one of these symbols so it's clear that the first and second items in the pair are different.\n1. [Line 116] Add parenthesis around 2.1\n1. [Line 142] Remove $K=$\n1. [Line 156] Why isn't there rescaling by $\\sqrt{p(y)}$ here, like there was in the leverage score appendix's definition of $L$?\n1. [Figure 1] Explain the confidence intervals in the caption\n1. [Line 168] The placement of \"See Section 4.3\" is not great, since Section 4.3 is about translating an \"in-probability bound\" into an \"expectation bound\". I'd move \"See Section 4.3\" one sentence earlier.\n1. [Line 226] Redefine PINN here. I know it's defined in the abstract, but I'd do it again here.\n1. [Figure 3] Add titles to the plots\n1. [Lines 230-239] I completely failed to understand what this paragraph is trying to say.... I just don't understand the problem or how it's being solved.\n1. [Section 4] Swap $\\varepsilon$ and $\\delta$. I'd **very heavily** recommend this. The choice of $\\delta$ to mean failure probability and $\\varepsilon$ to mean accuracy is extremely standard. I would not mess with this; it's very confusing to read.\n1. [Line 269] Interpret this big messy norm $\\|\\|\\|\\cdot\\|\\|\\|$ somewhere. It looks scary, but I don't think it really should be that scary?\n1. [Line 269] Missing $c$ subscript on $\\nu$.\n1. [Equation 4.1] Explore this sampling complexity. What is it really saying, comparing our sampling distribution to the Christoffel function? Can we use it to get a sorta \"coherence assumption\" for uniform sampling / MCS? This should be somewhat intuitive, but it really stands to be formally explored a bit more in the writing.\n1. [Lines 271-272] Why is it \"particularly relevant\"? Why's it hard to understand the Christoffel function of the cover but easy to understand the Christoffel function of $\\mathbb{U}$. I sorta intuitively believe it's true, but you should justify it.\n1. [Line 311] Consider calling $\\mathcal{T}_\\theta$ a \"shrinking operator\" maybe? or a \"regularization operator\" or something? It's not very truncation-like imo, but it's really a small preference. This is a very mild/soft recommendation.\n1. [Lines 316-318] Please formalize this added-penalty approach. It's the generalization of ridge regression, which feels very worth exploring.", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper is also 40 pages of really intense serious research. The appendix is chalk full of interesting special case studies, demonstrating the flexibility of their theory and the practical algorithms it suggests. The paper is so big and full of ideas that the NeurIPS peer review system, where I don't have enough time to read it cover-to-cover, really does this paper a disservice. I'd love to have 2 months to focus on this paper and understand the ins-and-outs of every case study and theorem. However, I don't have that time, so I'll presume the correctness of everything in the appendix and strongly recommend publishing this paper.\n\nThe paper is exceptionally general, doing a great job of generalizing much of the recent research on leverage score sampling beyond matrices. Lots of existing work has slowly generalized one or two ideas from leverage score sampling to Hilbert spaces or non-linearity or whatever else fits that work's setting. This paper really goes the extra mile and writes out a ridiculously general setting that covers:\n- Fitting a polynomial to a function, where we can observe both the function and it's gradient\n- Fitting a polynomial to a function, where we can choose if we want to observe the function or it's gradient at each query (in case one is more expensive than the other, we can consider them separate modalities with separate sample complexities).\n- Iteratively refined approximations to solving a PDE\n- Reconstructing MRI data from observations at carefully chosen frequencies\n\nThe general framework is phrased in terms of normed spaces, Hilbert spaces, measurable functions, and other abstract math that really gives the user freedom to do what the want. The theorems also apply to this extremely general framework, so the user immediately has Christoffel sampling guarantees with a likely near-optimal sample complexity out-of-the-box.\n\nI think this paper is original in it's powerful results in extreme generality, and is general in it's applications. The paper's results are high quality sample complexity guarantees. The paper is broadly well written (but this is a bit of a weaker point). The paper should be significant in its expressive power owing to its applicability to many domains.\n\nI strongly recommend publishing it.", "weaknesses": "The paper does suffer a bit on the clarity front. I'm familiar with leverage score sampling (and even some infinite-dimensional generalizations thereof), so I'd think that a generalized Christoffel function framework would be easy enough to understand. This was not the case though, and the extremely general framework was daunting an unapproachable to read about.\n\nThere's even an appendix subsection devoted to relating the extremely general framework back to the leverage score form I'm comfortable with. However, this description isn't super clear and even has (as far as I can tell) several minor errors which really harm legibility.\n\nThe general framework (section 2.1) is just a list of math definitions stated without any running example of what each mathematical object is. It's very unintuitive what the difference between a \"measurement domain\" and a \"measurement space\" are [Lines 85-87]. I'd strongly recommend the authors decide on a running example to present alongside all of the math definitions, which would make such definitions more intuitively distinct and clear.\n\nThe experiment and case study examples (section 3) are also pretty hard to approach. Section 3 consistently summarizes ideas at an extremely high level, and pushes the rigorous instantiations of the general framework to the appendix. While this makes sense from a page-limit perspective, it does harm the clarity and reading experience. Unfortunately, under the constraints of the NeurIPS format, I'm not sure a better option is available. Perhaps the authors can avoid this extreme appendicizing in the arXiv version of their paper?\n\nEven when reading the appendices in good detail, there's bits and pieces that I don't follow (especially in the MRI example). Everything I understood was clearly correct, but sometimes the technical domain-specific language gets a bit overwhelming making the examples hard to follow.\n\nThis clarity point is not a game-breaking issue, but another pass at making the technical material more approachable would benefit the paper, especially when it's targeting such a broad audience of both theoretical and empirical data scientists.\n\n\n_As a side note, it's curious to note one particular limitation of the framework -- it cannot explicitly handle ridge regression and ridge leverage scores, which is essential for some prior work on infinite dimensional leverage score sampling, like paper [12] in the references. I don't see any reason why CS4ML couldn't handle ridge regression / ridge leverage scores though._", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for their excellent review.\n## Weaknesses\n### 'The paper...'\nWe agree. **Please see our global rebuttal for discussion and changes we will make.**\n### 'There's even an....'\n**We will edit and move parts of this to the main paper.** See below for details.\n### 'The general framework....'\nA running example is an excellent idea. We think the best example is the classic regression problem. **Please see our global rebuttal.** Regarding the terminology: the 'measurement domain' is how we enumerate the possible measurements. In classic regression, it is the domain of the function. In Fourier sampling (Example 2) it is the set of possible frequencies. The 'measurement space' is the space where the measurements lie. E.g. $\\mathbb{R}$ for classic regression. **We will clarify this.**\n### 'The experiment....'\nWe agree that this can pose challenges. Our goal in this work is to introduce a general framework, then present three diverse examples to show its broad applicability. Unfortunately, it is hard to describe each example in the page limit, hence we pushed the details to the appendices. **The idea to reorganize the arXiv preprint is an excellent one. We will do this.**\n### 'This clarity....'\n**We will edit the appendices for readability.**\n### 'As a side...'\nThanks for raising this interesting issue. We are inclined to agree, but would need to investigate further as the proofs in [12] are quite different to ours. This is an interesting aim for future work.\n## Questions\n### 1. \nExactly. The worse performance arises from instability due to poor conditioning. As shown in Fig. 4, cond$(A)$ blows up with $m\\approx n\\log(n)/(d+1)$. In Fig. 5 we compute how large $m$ should be, given $n$, to ensure a cond$(A)\\le tol$. As shown, $m$ needs to grow much more rapidly than $n\\log(n)/ (d+1)$ for this to occur.\n### 2.\nThanks. We think there are two issues here. First, relating (A.1) to Definition 2.4. This is described in lines 672-674, but there were several errors: i) $\\mathbb{U}=\\mathbb{C}$ in line 672 should have been deleted, ii) it was not stated that $D$ should be equipped with the reference measure $\\rho$ (e.g. the Lebesgue measure) that defines the density $p$ via the Radon-Nikodym derivative. There was an unfortunate notation clash, since we also used $\\rho$ for the probability measure with density $p$. We will change this probability measure to $\\pi$, so that $p=d\\pi/d\\rho$. iii), in l.674, it should be $\\tau(\\mathbb{V},p)(y)=K(\\mathbb{V})(y)$. **We will fix this discussion.**\n\nSecond, relating (A.2) to (A.1). We did this in lines 669-671. However, we agree it is easier to directly relate it to Definition 2.4 (a benefit of the general definition). This can be done in several ways, but perhaps the easiest is to set $\\mathbb{X}=(\\mathbb{R}^N,\\|\\|\\cdot\\|\\|_{2})$, $\\mathbb{Y}=(\\mathbb{R},|\\cdot|)$, $D=\\{1,\\ldots,N\\}$ with the uniform measure $\\rho$ and $L(y)(u)=[u]_y$. Then, with $\\mathbb{V}$ as in line 669,\n\n$$K(\\mathbb{V})(y)=\\max_{v\\in\\mathbb{V},v\\neq0}\\frac{\\|\\|L(y)(v)\\|\\|^2_{\\mathbb{Y}}}{\\|\\|v\\|\\|^2_{\\mathbb{X}}}=\\max_{x\\neq0}\\frac{[Ax]^2_y}{\\|\\|Ax\\|\\|^2_2},$$\nwhich is precisely (A.2). Note that in this case, nondegeneracy holds with $\\alpha=\\beta=1$, since $$\\int_D\\|\\|L(y)(x)\\|\\|^2_{\\mathbb{Y}}d \\rho(y)=\\sum^{N}_{i=1} (x_i)^2.$$\nWe get $\\alpha=\\beta=1$ since we do not impose that $\\rho$ is the uniform probability measure. **We will add this derivation.**\n## 'After that....'\n### 1-3.\n**We will fix these**.\n### 4.\nGood question. It will hopefully be clear in the revision when we add the classic regression problem. Suppose that $\\mathbb{X}=L^2_{\\pi}(D)$ for some probability measure $\\pi$ with density $p$. Then there are two ways to setup the problem:\n\na) Consider $D$ with the measure $\\rho$ that defines $p$ as $p=d\\pi/d\\rho$. Set $L(y)(u)=\\sqrt{p(y)}u(y)$. Then\n$$\nK_a(y):=K(\\mathbb{V})(y)=\\sup\\\\{p(y)|v(y)|^2/\\|\\|v\\|\\|^2_{\\mathbb{X}}:v\\in\\mathbb{V},v\\ne0\\\\} =\\tau(\\mathbb{V},p)(y).\n$$\n\nb) Consider $D$ with $\\rho=\\pi$ and set $L(y)(u)=u(y)$. Then \n$$\nK_b(y):=K(\\mathbb{V})(y)=\\sup\\\\{|v(y)|^2/\\|\\|v\\|\\|^2_{\\mathbb{X}}:v\\in\\mathbb{V},v\\ne0\\\\}.\n$$\nObserve that $K_a(y)=K_b(y)p(y)$, so the two terms differ by $p(y)$. However, they lead to exactly the same Christoffel sampling measure $\\mu^{\\star}$ in (2.6). So the difference boils down to convention, i.e. whether to include $p$ or not. **We will explain this in the revision.**\n### 5-8.\n**We will fix these**.\n### 9.\n**We will rewrite this for clarity.**\n### 10.\n**We will change this.**\n### 11.\n**We will add this (likely in the appendices)**\n### 12.\n**We will fix this.**\n### 13.\nGood point. We think the best way to do this is to compare with MCS. In MCS, (4.1) involves $\\mathrm{esssup}_{y\\sim\\rho_c}K_c(\\mathbb{V})(y)$, whereas with CS it involves  $\\kappa_c(\\mathbb{V})=\\int K_c(\\mathbb{V})(y)d\\rho_c(y)$. Thus, the difference relates to the maximal behaviour of $K_c(\\mathbb{V})$ versus its integral (i.e. mean). If it is very flat, these bounds are similar. If it has spikes/peaks, they may differ substantially. An instance of this can already been seen in Fig 2, where $K$ is sharply peaked near the zero frequency (in the middle) and decays as frequency increases. **We will add this intuition.**\n### 14.\nGood question. Our thought is that it may be possible to show that there is a cover, but hard to explicitly formulate it, and therefore difficult to sample from (4.2). Generative models are an example. The range of a ReLU generative model is contained in a union of subspaces (lines 1009-1015). But these subspaces are likely not easily quantified. And even if they were, since there are a lot of them, it would be computationally intractable to evaluate the Christoffel function over their union. However, this point was poorly explained. **We will rephrase this sentence.**\n### 15.\n**We will change this.**\n### 16.\nApologies. We now don't think it is possible to get the same error bound using a regularized estimator. **We will delete the sentence.**"}]

Author rebuttal:
We thank the referees heartily for their insightful comments and the time and effort they put into carefully reviewing our manuscript. Each referee has made insightful comments that will undoubtedly improve the final version of the paper. We have provided detailed responses to each review separately below. However, in this global rebuttal we want to also discuss some of the main comments raised by the referees.

Note that in this and other rebuttals, **all specific changes we intend to make in the final article are in bold. We do not anticipate that these changes will exceed the one additional page allowed in the camera-ready version of the paper.**

### Experimental comparison/clarification of contribution (referees 9pYz, 7Xvg): 

Several referees commented that we only compared the proposed method against inactive learning (Monte Carlo sampling) and not other active learning techniques. It is certainly the case that for each of our three main examples, there has been much previous research on problem-specific active learning strategies. We commented on these briefly in the conclusion (Section 5). However, the main aim of our article was not necessarily to achieve the absolute state-of-the-art performance in each example. Rather, it shows how a single active learning technique (Christoffel sampling), which also comes with theoretical guarantees, can improve against inactive learning across a broad spectrum of problems. In particular, we extend classical leverage score sampling to a much broader class of problems, while maintaining its theoretical guarantees. We are unaware of any other current active learning strategy that can simultaneously address such a broad class of problems. **We will add a sentence to this effect in Section 1.2 (Contributions).**

We very much agree, however, that it is important to compare different strategies. But we think such a comparison is well beyond the scope of the current article. It is likely that a comprehensive comparison in each separate application could make for a paper on its own. We are interested in doing this, especially to see how well CS performs against other techniques. A related, and interesting, question for future work is whether one could use CS as a starting point for even more advanced active learning methods, e.g., by using the linear-sample sparsification techniques of [32], as briefly mentioned in Section 5, or by using 'boosting' techniques (Haberstich, Nouy \& Perrin).

**To address this issue, we will expand the discussion in Section 5 (Conclusions, limitations and future work) on other active learning strategies for the main examples and re-emphasize the main contributions of CS4ML to this problem.**



### Dense presentation (referees tt34, 7Xvg, n7M7): 

Several referees found the presentation of the framework in Section 2 dense and difficult to follow.

We agree and will make a series of changes to address this. First, **referees tt34 and n7M7 also proposed notational changes to improve readability, which we will implement. Second, as recommended by referee n7M7, we will add the classical regression problem as a running example in Section 2 (The CS4ML framework and main results) to clarify how this sits within the general framework.** This will make the generalizations we introduce easier to understand and motivate. **As also suggested, we will also move parts of the discussion on leverage score sampling from Section A.2  to Section 2.** Many readers are likely familiar with this leverage scores, therefore doing this will greatly aid readability. Overall, we believe these changes will make Section 2 much clearer for the reader.


### Complicated framework (referees tt34,n7M7): 

Several referees commented that the framework we propose is complicated/daunting due to its generality without proper justification.

We agree that the framework we propose is very general and the notation can feel quite heavy. As noted above, **we will implement a number of notational changes for clarity.** In terms of the formulation of the framework, however, we think its generality is justified by the broad range of applications it can address. 

The main ways our framework generalizes standard active learning is that i) we allow the target object to an element of an arbitrary Hilbert space $\mathbb{X}$, ii) we allow arbitrary linear sampling operators, and measurements which are scalar or vector-valued, and iii) we allow for potentially multimodal data. i) is a useful extension, and not too difficult to achieve. Both ii) and iii) are motivated by the examples. ii) allows one to consider sampling with, e.g., the Fourier or Radon transform, both of which are very common in computational imaging (e.g., MRI reconstruction in Example 2 of the paper). It also allows vector-valued measurements, which arise in both Examples 1 and 2 of the paper. Finally, multimodal data is found in many real-world applications, and is encountered in Example 3, as well as practically-important extensions of Examples 1 and 2 (see Sections B.7 and C.7, respectively).

We discussed these motivations in Section 1.1 (Motivations) and later in Section 3 (Examples and numerical experiments) when we describe the three examples. However, they are worth elaborating for clarity. **We will add a short discussion in Section 1.2 (Contributions) to explain lines 60-63 and thereby justify the generalizations. Further, as discussed above, we will also add the classic regression problem as an example in Section 2.** This will allow us to better justify the generalizations there as well.

Meta-review: Almost all of the reviewers agreed that this paper was an interesting read, and studies a very general form of the active learning problem with a number of compelling applications. In particular, it considered many variants of data acquisition beyond simple point-wise function sampling. Its results generalize tools like leverage score sampling that have recently applied for the more standard notion of active learning, so should be very interesting to many in the NeurIPS community.
Decision: Accept (spotlight)