A unified framework for learning with nonlinear model classes from arbitrary linear samples

Learning an unknown object (e.g., a vector, matrix or function) from a finite set of training data is a fundamental problem in applied mathematics and computer science. Typically, in modern settings, one seeks to learn an approximate representation in a nonlinear model class (also known as an approximation space or hypothesis set). It is also common to generate the training data randomly according to some distribution. Of critical importance in this endeavour is the question of learning guarantees. In other words: how much training data suffices to ensure good generalization, and how is this influenced by, firstly, the choice of model class, and secondly, the random process generating the training data?

This question has often been addressed for specific types of training data. For instance, in the case of function regression, the training data consists of pointwise evaluations of some target function, or in the case of computational imaging, the training data may consist of samples of the Fourier or Radon transform of some target image. It is also commonly studied for specific model classes, e.g., (linear or nonlinear) polynomial spaces [5] or (nonlinear) spaces of sparse vectors [43, 63], spaces of low-rank matrices or tensors [31, 63], spaces defined by generative models [18], single- [44] or multi-layer neural networks [8, 2, 3], Fourier sparse functions [41], (sparse) random feature models [12, 47] and many more.

In this paper, we introduce a unified framework for learning with nonlinear model classes from arbitrary linear samples. The main features of this framework are:

1. (i)

   the target object is an element of a separable Hilbert space;

2. (ii)

   each measurement is taken randomly and independently according to a random linear operator (which may differ from measurement to measurement);

3. (iii)

   the measurements may be scalar- or vector-valued, or, in general, may take values in a Hilbert space;

4. (iv)

   the measurements can be completely multimodal, i.e., generated by different distributions of random linear operators, as long as a certain nondegeneracy condition holds;

5. (v)

   the model class can be linear or nonlinear, but should be contained in (or covered by) a union of finite-dimensional subspaces;

6. (vi)

   the resulting learning guarantees are given in terms of the variation of the model class with respect to the sampling distributions.

We present a series of examples to highlight the generality of this framework. In various cases, our resulting learning guarantees either include or improve known guarantees in the literature.

In this section, we present a series of different sampling problems that can be cast into this unified framework. We will return to these examples later having stated our main learning guarantees in the next section.

• Example 2.1 (Function regression from i.i.d. samples)

  Let $D\subseteq\mathbb{R}^{d}$ be a domain with a measure $\rho$ and consider the problem of learning an unknown function $f\in L^{2}_{\rho}(D)$ from $m$ pointwise samples $(x_{i},f(x_{i}))$, $i=1,\ldots,m$, drawn i.i.d. from some probability measure $\mu$ on $D$. To cast this problem in the framework of §1.1, we make the (mild) assumption that $\mu$ is absolutely continuous with respect to $\rho$ with Radon–Nikodym derivative $\,\mathrm{d}\mu/\,\mathrm{d}\rho=\nu$ that is positive almost everywhere. Let $\mathbb{X}=L^{2}_{\rho}(D)$, $\mathbb{X}_{0}=C(\overline{D})$, $\mathbb{Y}_{1}=\cdots=\mathbb{Y}_{m}=\mathbb{Y}=\mathbb{R}$ with the Euclidean inner product and $\mathcal{A}_{1}=\cdots\mathcal{A}_{m}=\mathcal{A}$ be defined by $A\sim\mathcal{A}$ if $A(f)=f(x)/\sqrt{\nu(x)}$ for $x\sim\mu$. Observe that nondegeneracy (1.1) holds with $\alpha=\beta=1$ in this case, since

  $$\frac{1}{m}\sum^{m}_{i=1}\mathbb{E}_{A_{i}\sim\mathcal{A}_{i}}{\|A_{i}(f)\|}^{2}_{\mathbb{Y}_{i}}=\mathbb{E}_{x\sim\mu}\frac{|f(x)|^{2}}{\nu(x)}=\int_{D}|f(x)|^{2}\,\mathrm{d}\rho(x)={\|f\|}^{2}_{\mathbb{X}},\quad\forall f\in\mathbb{X}_{0}.$$

  In this case, given an approximation space $\mathbb{U}\subseteq C(\overline{D})$, the least-squares problem (1.3) becomes the (nonlinear) weighted-least squares fit

  $$\hat{f}\in{\underset{u\in\mathbb{U}}{\operatorname{argmin}}}\frac{1}{m}\sum^{m}_{i=1}\frac{1}{\nu(x_{i})}|f(x_{i})+\sqrt{\nu(x_{i})}e_{i}-u(x_{i})|^{2}.$$

  (2.1)

  Note that it is common to consider the case $\mu=\rho$ in such problems, in which case $\nu=1$ and (2.1) is an unweighted least-squares fit. However, this more general setup allows one to consider the active learning setting, where the sampling measure $\mu$ is chosen judiciously in term of $\mathbb{U}$ to improve the learning performance of $\hat{f}$. We discuss this in §4.

• Example 2.2 (Matrix sketching for large least-squares problems)

Let $X\in\mathbb{C}^{N\times n}$, $N\geq n$, be a given matrix and $y\in\mathbb{C}^{N}$ a target vector. In many applications, it may be infeasible (due to computational constraints) to find a solution to the ‘full’ least-squares problem

Therefore, one aims to instead find a sketching matrix $S\in\mathbb{C}^{m\times N}$ (a matrix with one nonzero per row) such that a minimizer

satisfies ${\|X\hat{w}-y\|}^{2}_{\ell^{2}}\leq(1+\epsilon){\|Xw-x\|}^{2}_{\ell^{2}}$ for some small $\epsilon>0$. A particularly effective way to do this involves constructing a random sketch. Formally, let $\pi=\{\pi_{1},\ldots,\pi_{N}\}$ be a discrete probability distribution on $\{1,\ldots,N\}$, i.e., $0\leq\pi_{i}\leq 1$ and $\sum^{N}_{i=1}\pi_{i}=1$. We also assume that $\pi_{i}>0$ for all $i$. Then we draw $m$ integers $j_{1},\ldots,j_{m}\sim_{\mathrm{i.i.d.}}\pi$ and set

Therefore, $SX\in\mathbb{C}^{m\times n}$ consists of $m$ rows of $X$ scaled by the probabilities $1/\sqrt{\pi_{i}}$. See [51, 64] for further discussions on matrix sketching.

To cast into the above framework we let $\mathbb{X}=\mathbb{X}_{0}=\mathbb{C}^{N}$ and $\mathbb{Y}=\mathbb{C}$ both equipped with the Euclidean norm. Note that bounded linear operators $\mathbb{X}_{0}\rightarrow\mathbb{Y}$ are equivalent to column vectors $a\in\mathbb{C}^{N}$ (via the relation $x\mapsto a^{*}x$). Hence we define $\mathcal{A}_{1}=\cdots=\mathcal{A}_{m}=\mathcal{A}$ to be a distribution of vectors in $\mathbb{C}^{N}$ with $a\sim\mathcal{A}$ if

Observe that nondegeneracy (1.1) holds with $\alpha=\beta=1$. Finally, we consider the model class

Then we readily see that (1.3) (with $b_{i}=(Sx)_{i}$) is equivalent to (2.2) in the sense that $\hat{x}=X\hat{w}$ is a solution of (1.3) if and only if $\hat{w}$ is a solution of (2.2). In particular, ${\|X\hat{w}-x\|}^{2}_{\ell^{2}}={\|\hat{x}-x\|}^{2}_{\ell^{2}}$ is precisely the $\mathbb{X}$-norm error of the estimator $\hat{x}$.

• Example 2.3 (Function regression with vector-valued measurements)

  Regression problems in various applications call for learning vector- as opposed to scalar-valued functions. These are readily incorporated into this framework by modifying Example 2.

  Hilbert-valued functions. Let $\mathbb{V}$ be a Hilbert space and consider the Hilbert-valued function $f:D\rightarrow\mathbb{V}$. The problem of learning Hilbert-valued functions arises in several applications, including parametric Differential Equations (DEs) in computational Uncertainty Quantification (UQ). Here, $f$ represents the parameters-to-solution map of a DE involving parameters $x\in D$, which, for each $x\in D$, yields the Hilbert-valued output $f(x)\in D$ being the solution of the DE at those parameter values (see [5, 27, 33] and references therein for discussion).

  To cast this problem into the general framework, we modify Example 2 by letting $\mathbb{X}=L^{2}_{\rho}(D;\mathbb{V})$ be the Bochner space of strongly $\rho$-measurable functions $D\rightarrow\mathbb{V}$, $\mathbb{X}_{0}=C(\overline{D};\mathbb{V})$ be the space of continuous, $\mathbb{V}$-valued functions, $\mathbb{Y}_{1}=\cdots=\mathbb{Y}_{m}=\mathbb{V}$ and $\mathcal{A}$ be the distribution of bounded linear operators $\mathbb{X}_{0}\rightarrow\mathbb{V}$ with $A\sim\mathcal{A}$ if $A(f)=f(x)/\sqrt{\nu(x)}\in\mathbb{V}$ for $f\in\mathbb{X}_{0}$ and $x\sim\mu$. Nondegeneracy holds (1.1) as before with $\alpha=\beta=1$.

  Continuous-in-time sampling. Consider a function $f:D\times[0,T]\rightarrow\mathbb{R}$ depending on a spatial variable $x\in D$ and a time variable $t\in[0,T]$. In some examples, for example seismology, one assumes continuous (or dense) sampling in time with discrete (i.e., sparse) sampling in space. Thus, each measurement takes the form $\{f(x,t):0\leq t\leq T\}$ for fixed $x\in D$.

  It transpires that we can cast this problem into a Hilbert-valued function approximation problem by letting $\mathbb{V}=L^{2}_{\sigma}(0,T)$ so that $\mathbb{X}=L^{2}_{\rho}(D;\mathbb{V})\cong L^{2}_{\rho\times\sigma}(D\times[0,T])$. Hence, continuous-in-time sampling is also covered by the general framework.

  Gradient-augmented measurements. Another extension of Example 2 involves gradient-augmented measurements. This can be considered both in the scalar- or Hilbert-valued setting. In this problem, each measurement takes the form $(x,f(x),\nabla_{x}f(x))$, i.e., we sample both the function and its gradient with respect to the variable $x$ at each sample point. This problem arises in a number of applications, including parametric DEs and UQ [11, 45, 55, 54, 53], seismology and Physics-Informed Neural Networks (PINNs) for PDEs [42, 65] and deep learning [29]. Assuming the Hilbert-valued setup of Example 2, we can cast this into the general framework by letting $\mathbb{X}$ be the Sobolev space $H^{1}_{\rho}(D)$, $\mathbb{X}_{0}=C^{1}(\overline{D})$, $\mathbb{Y}_{1}=\cdots=\mathbb{Y}_{m}=\mathbb{Y}=\mathbb{V}^{d+1}$ with the Euclidean inner product and defining $A\sim\mathcal{A}$ if $A(f)=(f(x),\nabla f(x))/\sqrt{\nu(x)}\in\mathbb{R}^{d+1}$ for $f\in\mathbb{X}_{0}$ and $x\sim\mu$. It is readily checked that nondegeneracy (1.1) holds with $\alpha=\beta=1$, as before.

In the next four examples, we show how this framework includes as special cases various general sampling models from the compressed sensing literature.

• Example 2.4 (Compressed sensing with isotropic vectors)

  Classical compressed sensing concerns learning a sparse approximation to an unknown vector $f\in\mathbb{C}^{N}$ from $m$ linear measurements. A well-known model involves sampling with isotropic vectors [22] (see also [9, Chpt. 11]). We can cast this in the above framework as follows. Let $\mathbb{X}=\mathbb{X}_{0}=\mathbb{C}^{N}$ equipped with Euclidean inner product and $\mathbb{Y}_{1}=\cdots=\mathbb{Y}_{m}=\mathbb{Y}=\mathbb{C}$. As in Example 2, we consider $\mathcal{A}_{1}=\cdots=\mathcal{A}_{m}=\mathcal{A}$ to be a distribution of vectors in $\mathbb{C}^{N}$ that are isotropic, i.e.,

  $$\mathbb{E}_{a\sim\mathcal{A}}aa^{*}=I,$$

  (2.4)

  where $I$ is the $N\times N$ identity matrix. Note that (1.1) holds with $\alpha=\beta=1$ in this case. Moreover, the measurements (1.2) have the form

  $$b_{i}=a^{*}_{i}x+e_{i}\in\mathbb{C},\quad i=1,\ldots,m,$$

  where $a_{1},\ldots,a_{m}\sim_{\mathrm{i.i.d.}}\mathcal{A}$. In matrix-vector notation, we can rewrite this as

  $$b=Ax+e,\quad\text{where }A=\frac{1}{\sqrt{m}}\begin{bmatrix}a^{*}_{1}\\ \vdots\\ a^{*}_{m}\end{bmatrix}\in\mathbb{C}^{m\times N},$$

  (2.5)

  $b=\frac{1}{\sqrt{m}}(b_{i})^{m}_{i=1}\in\mathbb{C}^{m}$ and $e=\frac{1}{\sqrt{m}}(e_{i})^{m}_{i=1}$ (the division by $1/\sqrt{m}$ is a convention: due to (2.4), it ensures that $\mathbb{E}(A^{*}A)=I$).

  As discussed in [22], this model includes not only the well-known case of subgaussian random matrices, in which case $\mathcal{A}$ is a distribution of subgaussian random vectors, but also many other common sampling models used in signal and image processing applications. It is also a generalization of the concept of random sampling with bounded orthonormal systems (see, e.g., [43, Chpt. 12]). Moreover, if we slightly relax (2.4) to

  $$\alpha I\preceq\mathbb{E}_{a\sim\mathcal{A}}aa^{*}\preceq\beta I,$$

  so that (1.1) holds with the same values of $\alpha$ and $\beta$, then it also generalizes the bounded Riesz systems studied in [21].

• Example 2.5 (Compressed sensing with subsampled unitary matrices)

  A particular case of interest within the previous example is the class of randomly subsampled unitary matrices (see also [9, Defn. 5.6 and Examp. 11.5]). Let $U\in\mathbb{C}^{N\times N}$ be unitary, i.e., $U^{*}U=I$. For example, $U$ may be the matrix of the Discrete Fourier Transform (DFT) in a Fourier sensing problem. Let $u_{i}=U^{*}e_{i}$, where $e_{i}$ is the $i$th canonical basis vector, and define the (discrete) distribution of vectors $\mathcal{A}$ by $a\sim\mathcal{A}$ if

  $$\mathbb{P}(a=\sqrt{N}u_{i})=\frac{1}{N},\quad i=1,\ldots,N.$$

  One readily checks that (2.4) holds in this case. Hence this family is isotropic. Note that the corresponding measurement matrix (2.5) consists of rows of $U$ – hence the term ‘subsampled unitary matrix’.

  This setup can be straightforwardly extended to the case where the rows of $U$ are sampled with different probabilities, termed a nonuniformly subsampled unitary matrix. Let $\pi=(\pi_{1},\ldots,\pi_{N})$ be a discrete probability distribution on $\{1,\ldots,N\}$, i.e., $0\leq\pi_{i}\leq 1$ and $\sum^{N}_{i=1}\pi_{i}=1$. We also assume that $\pi_{i}>0$ for all $i$. Then we now modify the distribution $\mathcal{A}$ so that $a\sim\mathcal{A}$ if

  $$\mathbb{P}(a=u_{i}/\sqrt{\pi_{i}})=\pi_{i},\quad i=1,\ldots,N.$$

  It is readily checked that (2.4) also holds in this case, making this family once more isotropic. Note that uniform subsampling is restored simply by setting $\pi_{i}=1/N$, $\forall i$.

  Nonuniform subsampling is important in various applications. For instance, in applications that involve Fourier measurements (e.g., MRI, NMR, Helium Atom Scattering and radio interferometry) it usually desirable to sample rows corresponding to low frequencies more densely than rows corresponding to high frequencies. See, e.g., [9] and references therein.

• Example 2.6 (Sampling without replacement)

  The previous example considers random sampling of the rows of $U$ with replacement. In particular, repeats are possible. In practice, it is usually desirable to avoid repeats. One way to do this is to use Bernoulli selectors (see [9, §11.4.3] or [15]). Here, the decision of whether to include a row of $U$ or not is based on the outcome of a (biased) coin toss, i.e., a realization of a Bernoulli random variable.

  Specifically, let $\pi=(\pi_{1},\ldots,\pi_{N})$ satisfy $0<\pi_{i}\leq 1/m$ and $\sum^{N}_{i=1}\pi_{i}=1$. Then, for each $i=1,\ldots,N$, define the distribution $\mathcal{A}_{i}$ by $a_{i}\sim\mathcal{A}_{i}$ if

  $$\mathbb{P}\left(a_{i}=\sqrt{\frac{N}{m\pi_{i}}}u_{i}\right)=m\pi_{i},\quad\mathbb{P}(a_{i}=0)=1-m\pi_{i}.$$

  Notice that the collection $\{\mathcal{A}_{i}\}^{N}_{i=1}$ is nondegenerate. Indeed,

  $$\frac{1}{N}\sum^{N}_{i=1}\mathbb{E}_{a_{i}\sim\mathcal{A}_{i}}a_{i}a^{*}_{i}=\frac{1}{N}\sum^{N}_{i=1}m\pi_{i}\frac{N}{m\pi_{i}}u_{i}u^{*}_{i}=U^{*}U=I.$$

  Hence, this model falls within the general setup. Later, in §5.2 and Corollary 5.4, we will see that this model admits essentially the same learning guarantees as the model considered in Example 2. Observe that the measurement matrix (2.5) in this case is $N\times N$, where the $i$th row is proportional to the $i$th row of $U$ if the $i$th coin toss returns a heads, and zero otherwise. In particular, it is equivalent to a $q\times N$ matrix, where $q$ is the number of heads. Notice that, unlike in the previous model, the number of measurements $q$ is a random variable with $\mathbb{E}(q)=m$.

The reader will notice that in the previous examples, the distributions $\mathcal{A}_{1},\ldots,\mathcal{A}_{m}$ we all equal. We now present several examples that justify considering different distributions.

• Example 2.7 (Half-half and multilevel sampling)

  Recall that Example 2 arises in various applications involving Fourier measurements. In these applications, it is often desirable to fully sample the low-frequency regime [49] (see also [9]). The low frequencies of a signal or image contain much of its energy. Therefore, any purely random sampling scheme can miss important information with nonzero probability.

  A simple way to avoid this problem is a half-half sampling scheme [10, 58]. Here the first $m_{1}$ measurements are set equal to the lowest $m_{1}$ frequencies (i.e., the first $m_{1}$ samples are deterministic) and the remaining $m_{2}:=m-m_{1}$ samples are obtained by randomly sampling the remaining $N-m_{1}$ frequencies according to some distribution. This can be formulated within our framework as follows. Let $U\in\mathbb{C}^{N\times N}$ be unitary (typically, $U$ is the DFT matrix, but this is not needed for the current discussion) and $u_{i}=U^{*}e_{i}$, as before. Then, for $i=1,\ldots,m_{1}$, we define the distribution $\mathcal{A}_{i}$ by $a\sim\mathcal{A}_{i}$ if

  $$\mathbb{P}(a=\sqrt{m}u_{i})=1,\quad i=1,\ldots,m_{1}.$$

  In other words, $a\sim\mathcal{A}_{i}$ takes value $\sqrt{m}u_{i}$ with probability one. Now let $\pi=(\pi_{m_{1}+1},\ldots,\pi_{N})$ be a discrete probability distribution on $\{m_{1}+1,\ldots,N\}$ with $0<\pi_{i}\leq 1$ for all $i$. Then we define $\mathcal{A}_{m_{1}+1}=\cdots=\mathcal{A}_{m}=\mathcal{A}$ with $a\sim\mathcal{A}$ if

  $$\mathbb{P}(a=\sqrt{m/(m_{2}\pi_{i})}u_{i})=\pi_{i},\quad i=m_{1}+1,\ldots,N.$$

  We readily see that the family $\{\mathcal{A}_{i}\}^{m}_{i=1}$ is nondegenerate with $\alpha=\beta=1$. Notice that the first $m_{1}$ rows of measurement matrix obtained from this procedure are proportional to the first $m_{1}$ rows of $U$ and its remaining $m_{2}=m-m_{1}$ rows are randomly sampled according to $\pi$ from the last $N-m_{1}$ rows of $U$.

  Half-half sampling schemes have been used in various imaging applications [10, 49, 23, 57, 58]. Note that such a scheme subdivides the indices $\{1,\ldots,N\}$ into two levels: fully sampled and randomly subsampled. In practice, it is often desirable to have further control over the sampling, by subdividing into more than two levels. This is known as multilevel random subsampling [10] (see also [9, Chpts. 4 & 11]). It can be formulated within this framework in a similar way.

• Example 2.8 (Multimodal data)

  Another benefit of allowing for different distributions is that it can model multimodal data. Consider the general setup of §1.1. We now assume that there are $C>1$ different types of data, with the $c$th type generating $m_{c}$ samples via a distribution $\mathcal{A}^{(c)}$, $c=1,\ldots,C$, of bounded linear operators in $\mathcal{B}(\mathbb{X}_{0},\mathbb{Y}^{(c)})$. Let $m=m_{1}+\cdots+m_{C}$ and define $\{\mathcal{A}_{i}\}^{m}_{i=1}$ by

  $$\mathcal{A}_{i}=\mathcal{A}^{(c)}\quad\text{if }m_{1}+\cdots+m_{c-1}<i\leq m_{1}+\cdots+m_{c}.$$

  Thus, the first $m_{1}$ samples are generated by $\mathcal{A}^{(1)}$, the next $m_{2}$ samples by $\mathcal{A}^{(2)}$, and so forth. Notice that nondegeneracy (1.1) is now equivalent to the condition

  $$\alpha{\|x\|}^{2}_{\mathbb{X}}\leq\sum^{C}_{c=1}\frac{m_{c}}{m}\mathbb{E}_{A\sim\mathcal{A}^{(c)}}{\|A(x)\|}^{2}_{\mathbb{Y}^{(c)}}\leq\beta{\|x\|}^{2}_{\mathbb{X}}.$$

  Multimodal data was previously considered in [6], which, as noted in §1 is a special case of this work. As observed in [6], multimodal data arises in various applications, such as multi-sensor imaging systems [26] and PINNs for PDEs [46, 56]. This includes the important case of parallel MRI [52], which is used widely in medical practice. Another application involves an extension of the gradient-augmented learning problem in Example 2 where, due to cost or other constraints, one can only afford to measure gradients in addition to function values at some fraction of the total samples. See [6, §B.7].

In this section, we present our main results.