Abstract

In the context of multivariate nonparametric regression with missing covariates, we propose Pattern Embedded Neural Networks (PENNs), which can be applied in conjunction with any existing imputation technique. In addition to a neural network trained on the imputed data, PENNs pass the vectors of observation indicators through a second neural network to provide a compact representation. The outputs are then combined in a third neural network to produce final predictions. Our main theoretical result exploits an assumption that the observation patterns can be partitioned into cells on which the Bayes regression function behaves similarly, and belongs to a compositional Hölder class. It provides a finite-sample excess risk bound that holds for an arbitrary missingness mechanism, and in combination with a complementary minimax lower bound, demonstrates that our PENN estimator attains in typical cases the minimax rate of convergence as if the cells of the partition were known in advance, up to a poly-logarithmic factor in the sample size. Numerical experiments on simulated, semi-synthetic and real data confirm that the PENN estimator consistently improves, often dramatically, on standard neural networks without pattern embedding. Code to reproduce our experiments, as well as a tutorial on how to apply our method, is publicly available.

Keywords: Deep learning, Missing data, Nonparametric regression

1 Introduction↩︎

Over the last decade or so, deep neural networks have achieved stunning empirical successes in learning tasks across diverse application areas, including image classification [1], [2], protein folding [3], natural language processing [4], [5] and many others. While their complexity initially led to the temptation to regard them as a black box, recent theory does provide insights into the origins of their impressive practical performance [6]–[10].

The works described in the previous paragraph all concern settings where the (large) datasets involved are fully observed. Nevertheless, as argued by [11], missing data play an ever more significant role in high-dimensional learning problems, and new methods have now been introduced to tackle several different contemporary statistical challenges involving missing data, including sparse linear regression [12], [13], principal component analysis [11], [14], classification [15], [16] and changepoint estimation [17]. Most of these papers study the simplest, idealised case where the data and missingness indicators are independent, a setting known as Missing Completely At Random (MCAR). Indeed, it is now understood that for more general (dependent) missingness mechanisms, even consistent mean estimation may be impossible without further assumptions [18].

The goal of this paper is to study supervised deep learning problems with missing values among the covariates, where we do not rely on an MCAR assumption, or indeed any other restriction on the missingness mechanism. Motivated by many applications in which deep learning is applied, we focus on the problem of prediction (i.e. making a forecast of the response at a new covariate vector) as opposed to estimation (i.e. learning the underlying parameters of the model). Our primary methodological contribution is to introduce the idea of (observation) pattern embedding into the neural network framework. In other words, in addition to training a neural network on our original covariates (with missing values imputed via any existing technique), we pass the vectors of observation indicators, which we call revelation vectors, through another neural network to obtain a compact representation that summarises the information they contain. We can then train a third neural network that combines these two earlier ones to produce final predictions.

The benefits of our approach are illustrated in Figure 1, where our training data of size \(n = 1{,}000\) and \(d=1\) are generated from the model described in Example 1 in Section 2.1 below. Our original covariates \((\boldsymbol{X}_i)_{i=1}^n\) are observed with missingness, and we apply zero (mean) imputation based on the corresponding revelation vectors \((\boldsymbol{\Omega}_i)_{i=1}^n\) to obtain imputed covariates \((\boldsymbol{Z}_i)_{i=1}^n\). Thus, together with the responses \((Y_i)_{i=1}^n\), which satisfy \(Y_i|\boldsymbol{X}_i \sim N(3\boldsymbol{X}_i^2,0.1^2)\) independently for \(i=1,\ldots,n\), we have training data \((\boldsymbol{Z}_i, \boldsymbol{\Omega}_i, Y_i)_{i=1}^n\). Following the imputation, the standard approach would be to train a model on \((\boldsymbol{Z}_i, Y_i)_{i=1}^n\) (see Figure 1 (a)), yielding fitted values on an independent test set of size 500 displayed in panel (c). By contrast, our approach trains a neural network on the augmented data \((\boldsymbol{Z}_i, \boldsymbol{\Omega}_i, Y_i)_{i=1}^n\) in panel (b), leading to much more accurate predictions on the test set, as illustrated in panel (d). The main point to observe here is that the failure to include the revelation vectors \((\boldsymbol{\Omega}_i)_{i=1}^n\) in panel (c) corrupts the output in a neighbourhood of the origin, which is a point of discontinuity of the function \(\boldsymbol{z} \mapsto \mathbb{E}(Y_1 \, | \, \boldsymbol{Z}_1 = \boldsymbol{z})\), whereas this is corrected in panel (d) by the inclusion of the additional covariate.

Figure 1: An illustration of Example 1, and the outputs of neural networks trained without and with the revelation vectors.

On the other hand, as we illustrate in Figure 2 in Section 2.3, when \(d\) is larger, naive inclusion of the revelation vectors as additional covariates can harm performance, even compared with omitting \((\boldsymbol{\Omega}_i)_{i=1}^n\) entirely. Moreover, as we also discuss in Section 2.3, the predictive value of the revelation vectors may not be well-aligned with their Euclidean geometry. Thus, a key challenge is to construct a suitable compression of the information contained in the revelation vectors that retains their predictive content to the greatest extent possible.

After a more formal description of our problem set-up and some background on ReLU neural networks, we introduce our Pattern Embedded Neural Networks (PENNs) in Section 2. These can be fitted using standard empirical risk minimisation algorithms such as Adam or AdamW [19], [20], as implemented in PyTorch in Python, yielding an estimator \(\widehat{f}\) of the Bayes regression function \(f^\star\), given by \(f^\star(\boldsymbol{z},\boldsymbol{\omega}) \mathrel{\vcenter{:}}= \mathbb{E}(Y_1 \, | \, \boldsymbol{Z}_1 = \boldsymbol{z}, \boldsymbol{\Omega}_1 = \boldsymbol{\omega})\).

In Section 3 we turn our attention to the theoretical properties of our procedure. We begin with a general oracle inequality (Proposition 1), revealing that under a sub-Gaussian condition on the response, the excess risk of our estimator is controlled by the sum of optimisation error, approximation error and estimation error terms, with the latter two reflecting a bias–variance trade-off in the complexity of the neural network class. Our main result (Theorem 2 in Section 3.2) specialises the general setting studied previously to give a more explicit excess risk bound. In particular, since there \(2^d\) possible observation patterns, we introduce a new condition on the Bayes regression function \(f^\star\) to encapsulate the notion that the set of all possible observation patterns may be partitioned into sets on which \(f^\star\) behaves similarly as a function of the covariates. We further ask that on each cell of this partition, \(f^\star\) belongs to a compositional Hölder smoothness class. This allows us to show that the sum of the approximation error and estimation error terms can be controlled by a weighted average of estimation rates for each cell of the partition, together with an additional term reflecting the complexity of the partition that will typically be negligible, up to a poly-logarithmic factor in the sample size. This theorem is complemented by a minimax lower bound in Theorem 3, which confirms that the weighted average of the estimation rates over different cells in Theorem 2 is optimal. All proofs are deferred to the Appendix.

A numerical study of the performance of our PENN estimator is presented in Section 4. Our simulated data settings consider both MCAR and Missing Not At Random (MNAR) scenarios, as well as three commonly-used imputation techniques, namely (columnwise) mean imputation, MissForest imputation [21] and Multiple Imputation by Chained Equations (MICE) [22]. A consistent pattern emerges whereby the PENN estimator is able to improve, sometimes very significantly, on the corresponding neural network estimator that does not include pattern embedding. We also compare with other machine learning methods that handle missingness directly, namely XGBoost [23] and random forests [24], and see similar improvements in these settings. Beyond purely simulated data, we study two semi-synthetic datasets and one real dataset with the same imputation methods. In the former cases, the original real data, on handwritten digits (where we include Vision Transformers [25] as an additional competitor) and relative location of Computed Tomography (CT) slices respectively, are observed without missingness, which allows us to introduce either MCAR or MNAR missingness via known mechanisms. On the other hand, in the latter real dataset on credit scores, missingness is already present in the original data. By splitting the data into training, validation and test sets, we again see consistent improvements from our pattern embedding approach. Python code to reproduce all of the experiments in this section, together with an accompanying tutorial on how to apply our method, is available at https://github.com/tianyima2000/DNN_missing_data.

The desire to understand and explain the impressive empirical performance of deep learning represents a major current research theme in statistics and machine learning. One line of work provides explicit rates of convergence through the lens of approximation theory and empirical process theory, assuming that the empirical risk can be minimised sufficiently well. Minimax optimality (in terms of the sample size) of neural networks has been studied, for example, in the context of nonparametric regression [7], [8], [26]–[30], classification [31], [32], the partially linear Cox model [33] and density estimation [34]. In particular, it is now known that neural networks can exploit low-dimensional structure in nonparametric regression under a compositional Hölder assumption [7], [8]. While most of the bounds in the work mentioned above have pre-factors depending exponentially on the covariate dimension or the number of variables on which the regression function depends, [28] provide upper bounds that depend only polynomially on the dimension, using the approximation scheme of [35], while [27] allow discontinuities in the regression function. Other research directions focus on understanding the training dynamics of neural networks, for example through Neural Tangent Kernels [6], [36], [37], Tensor programs [38], [39], and mean-field limits [9], [40]–[42]. Recently, the in-context learning ability of Transformers has also been exploited to build foundation models for tabular data [43]; theoretical results on in-context nonparametric regression have been studied by, e.g., [44]–[46].

When fitting neural networks, the embedding of discrete or structured data into a latent space is an attractive approach. In particular, categorical embeddings map discrete objects, such as words or user identifiers, into continuous representations learned jointly with the prediction task [47], [48]. Relatedly, in unsupervised tasks, autoencoders learn compact latent representations via ‘bottleneck architectures’ (with narrow middle layers) that capture essential structure in high-dimensional data [49], [50]. Viewed in this light, our method learns a low-dimensional embedding of the observation pattern, a categorical variable with up to \(2^d\) levels, in which similarities between patterns are inferred from the data rather than specified a priori. Unlike classical autoencoders, in our supervised learning task this embedding is optimised solely for prediction and is not required to reconstruct the missingness pattern itself.

Missing data has been an active research topic in statistics for several decades, but is currently undergoing a renaissance for two main reasons. First, as already mentioned, missing values are ubiquitous in large datasets, and, unlike for other forms of data corruption, many statistical learning algorithms cannot be applied until the missingness is handled appropriately. Second, and somewhat related, the complexity of modern data demands new models for missingness and new inferential methods with appropriate guarantees on their performance [18], [51]. It has long been recognised that the MCAR assumption is unrealistic for many practical applications. On the other hand, modern data generating mechanisms can often only be adequately described by high- or infinite-dimensional parameter spaces. In such settings, missingness models such as Missing At Random (MAR) that are predicated on the correctness of low-dimensional parametric models fitted using maximum likelihood may be inappropriate.

For regression problems with missing covariates, one widely used general strategy is impute-then-regress, i.e. we first impute the missing data and then treat the imputed dataset as complete to train a regression algorithm. Many imputation algorithms have been proposed under MCAR or MAR assumptions, such as MissForest imputation [21], MICE [22], and methods based on deep learning and generative models [52]–[55]. If there exists a universally consistent estimator, then under some conditions that still allow MNAR, the impute-then-regress approach leads to asymptotically vanishing excess risk on new covariate vectors as the sample size diverges to infinity [56], [57]. However, the Bayes regression function, which in this case is the conditional expectation of the response given the imputed covariate vector, may be discontinuous and hard to learn [56].

[58] studies orthogonal series methods in univariate nonparametric regression with MAR missingness. Other strategies for regression with missing data include augmenting the covariate space with a distinguished point, reflecting a missing value, in relevant coordinates; this can be applied with regression trees or other (non-orthogonally equivariant) methods such as XGBoost and random forests. [59] propose regression trees with the observation patterns included as covariates, [60] replace neurons in the first hidden layer of a neural network by estimated expected values to handle missing data, while [56] train imputation and regression algorithms simultaneously using neural networks. For image data, MisGAN [52] imputes missing pixels, while Vision Transformers (ViTs) can naturally handle occlusions through their patch-based representation and attention mechanism [25], [61], [62]. Nevertheless, to the best of our knowledge, our work is the first to provide minimax optimality guarantees for multivariate nonparametric regression with missing data.

1.2 Notation↩︎

We conclude the introduction with some notation employed throughout the paper. For \(n\in\mathbb{N}\), we define \([n] \mathrel{\vcenter{:}}= \{1,\ldots,n\}\), and for \(a,b\in\mathbb{R}\), we let \(a\wedge b \mathrel{\vcenter{:}}= \min\{a,b\}\) and \(a\vee b \mathrel{\vcenter{:}}= \max\{a,b\}\). For \(\boldsymbol{a},\boldsymbol{b}\in\mathbb{R}^d\), we let \(\boldsymbol{a}\odot \boldsymbol{b} \in \mathbb{R}^d\) denote the Hadamard product (i.e. coordinate-wise product) of \(\boldsymbol{a}\) and \(\boldsymbol{b}\). For \(q \in [1,\infty)\) and \(\boldsymbol{v} = (v_1,\ldots,v_d)^\top \in \mathbb{R}^d\), we write \(\|\boldsymbol{v}\|_q \mathrel{\vcenter{:}}= \bigl(\sum_{j=1}^d |v_j|^q\bigr)^{1/q}\), as well as \(\|\boldsymbol{v}\|_0 \mathrel{\vcenter{:}}= \sum_{j=1}^d \mathbb{1}_{\{v_j \neq 0\}}\) and \(\|\boldsymbol{v}\|_{\infty} \mathrel{\vcenter{:}}= \max_{j \in [d]} |v_j|\). The all-ones vector is \(\boldsymbol{1}_d \mathrel{\vcenter{:}}= (1,\ldots,1)^\top \in \mathbb{R}^d\). If \((\mathcal{X},\mathcal{A},\mu)\) is a measure space and \(f:\mathcal{X} \rightarrow \mathbb{R}\) is measurable, then we define \(\|f\|_{L_q(\mu)} \mathrel{\vcenter{:}}= \bigl(\int_{\mathcal{X}} |f|^q \, d\mu\bigr)^{1/q}\), as well as \(\|f\|_\infty \mathrel{\vcenter{:}}= \sup_{\boldsymbol{x} \in \mathcal{X}} |f(\boldsymbol{x})|\). For function classes \(\mathcal{F}\) and \(\mathcal{G}\), we define \(\mathcal{F}\circ\mathcal{G} \mathrel{\vcenter{:}}= \{f \circ g:f \in \mathcal{F}, g \in \mathcal{G}\}\), and for \(B\geq 0\), we define the truncation operator \(T_B : \mathbb{R} \to [-B,B]\) by \(T_B(y) \mathrel{\vcenter{:}}= (-B) \vee y \wedge B\). We say that \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is a partition of a non-empty set \(\mathcal{S}\) if \(\mathcal{S}_1,\ldots,\mathcal{S}_K\) are pairwise disjoint, non-empty subsets of \(\mathcal{S}\) whose union is \(\mathcal{S}\). The sub-Gaussian norm of a real-valued random variable \(X\) is \(\|X\|_{\psi_2} \mathrel{\vcenter{:}}= \inf \{t>0 : \exp(X^2/t^2) \leq 2\}\); its sub-exponential norm is \(\|X\|_{\psi_1} \mathrel{\vcenter{:}}= \inf \{t>0 : \exp(|X|/t) \leq 2\}\). For positive sequences \((a_n)\), \((b_n)\), we write \(a_n \lesssim b_n\) if there exists a universal constant \(C > 0\) such that \(a_n \leq C b_n\) for all \(n \in \mathbb{N}\); if we also have \(b_n \lesssim a_n\), then we write \(a_n \asymp b_n\).

2 Problem set-up and methodology↩︎

2.1 Problem set-up↩︎

Suppose that \((\boldsymbol{X}_i,\boldsymbol{\Omega}_i,Y_i)_{i=0}^{n}\) are independent and identically distributed random vectors taking values in \(\mathbb{R}^d \times \{0,1\}^d \times \mathbb{R}\). The elements of these triples represent the fully observed covariate vectors, revelation vectors and responses, respectively, and we let \(\mathcal{S} \mathrel{\vcenter{:}}= \bigl\{\boldsymbol{\omega}: \mathbb{P}(\boldsymbol{\Omega}_0 = \boldsymbol{\omega}) > 0\bigr\}\) denote the set of possible observation patterns. In our missing data context, we are in general unable to observe \((\boldsymbol{X}_i)_{i=0}^n\); instead, we have access to partially observed covariate vectors \((\widetilde{\boldsymbol{X}}_i)_{i=0}^n\) taking values in the extended space¹ \(\mathbb{R}_{\star}^d \mathrel{\vcenter{:}}= \bigl(\mathbb{R} \cup \{\star\}\bigr)^d\), where \(\star\) denotes a missing value. Thus \(\widetilde{\boldsymbol{X}}_i\) agrees with \(\boldsymbol{X}_i\) except in components where \(\boldsymbol{\Omega}_i\) is zero, and those components of \(\widetilde{\boldsymbol{X}}_i\) are replaced with \(\star\). We emphasise that we do not assume independence between the covariate \(\boldsymbol{X}_i\) and revelation vector \(\boldsymbol{\Omega}_i\), and indeed we allow the entries of \(\widetilde{\boldsymbol{X}}_i\) to be MNAR. Let \(\mathsf{Imp} : \mathbb{R}_{\star}^d \to \mathbb{R}^d\) be a potentially randomised imputation algorithm, where any randomness in the construction of \(\mathsf{Imp}\) is independent of \((\boldsymbol{X}_i,\boldsymbol{\Omega}_i,Y_i)_{i=0}^{n}\), and let \(\boldsymbol{Z}_i \mathrel{\vcenter{:}}= \mathsf{Imp}(\widetilde{\boldsymbol{X}}_i)\) for \(i\in\{0,1,\ldots,n\}\). For example, \(\mathsf{Imp}\) can be zero (or mean) imputation, or other regression-based imputation algorithms trained on an independent dataset². We observe training data \((\boldsymbol{Z}_i,\boldsymbol{\Omega}_i,Y_i)_{i=1}^n\) and our goal is to predict \(Y_0\) given a test point \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\). Write \(\mathcal{G}\) for the set of all possible prediction functions, i.e. the set of Borel measurable functions from \(\mathbb{R}^d \times \mathcal{S}\) to \(\mathbb{R}\). We define the generalisation error of \(\widetilde{f} \in \mathcal{G}\) as \[\begin{align} R(\widetilde{f}) &\mathrel{\vcenter{:}}= \mathbb{E}_{(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0)} \bigl\{ \bigl(\widetilde{f}(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0) - Y_0\bigr)^2 \bigr\}\\ &= \int_{\mathbb{R}^d \times \mathcal{S} \times \mathbb{R}} \bigl(\widetilde{f}(\boldsymbol{z},\boldsymbol{\omega}) - y\bigr)^2 \;\mathrm{d} \mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0}(\boldsymbol{z},\boldsymbol{\omega},y), \end{align}\] where \(\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0}\) denotes the distribution of \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0)\). Note that if \(\widetilde{f}\) is an estimator depending on \((\boldsymbol{Z}_i,\boldsymbol{\Omega}_i,Y_i)_{i=1}^n\), then \(R(\widetilde{f})\) is random, since the expectation is taken only over the distribution of \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0)\). The Bayes regression function \(f^{\star} : \mathbb{R}^d \times \mathcal{S} \to \mathbb{R}\) is defined by \[f^{\star}(\boldsymbol{z}, \boldsymbol{\omega}) \mathrel{\vcenter{:}}= \mathbb{E}(Y_0 \,|\, \boldsymbol{Z}_0=\boldsymbol{z}, \boldsymbol{\Omega}_0 = \boldsymbol{\omega}).\] This function, which satisfies \(R(f^{\star}) = \inf_{f \in \mathcal{G}} R(f)\), may therefore depend on the imputation algorithm employed, though \(R(f^{\star})\) does not. For an estimator \(\widetilde{f}\), we measure its performance by its excess risk \(\mathbb{E}\bigl\{ R(\widetilde{f})\bigr\} - R(f^{\star})\). Finally, we define the empirical risk of \(\widetilde{f}\) as \[\widehat{R}_n(\widetilde{f}) \mathrel{\vcenter{:}}= \frac{1}{n} \sum_{i=1}^n \bigl(\widetilde{f}(\boldsymbol{Z}_i,\boldsymbol{\Omega}_i)-Y_i\bigr)^2.\]

Example 1. Let \(\boldsymbol{X}_0=(X_{0,1},\ldots,X_{0,d})^\top \sim \mathrm{Unif}[-1,1]^d\), and let \(Y_0 = 3X_{0,1}^2 + \varepsilon_0\) where \(\varepsilon_0 \sim N(0,0.01)\) and \(\varepsilon_0 \perp\!\!\!\perp\boldsymbol{X}_0\). Suppose that \(\boldsymbol{\Omega}_0 = (\Omega_{0,1},\ldots,\Omega_{0,d})^\top \perp\!\!\!\perp(\boldsymbol{X}_0,\varepsilon_0)\) satisfies \(\Omega_{0,1},\ldots,\Omega_{0,d} \overset{\mathrm{iid}}{\sim} \mathrm{Ber}(0.7)\), i.e. we have MCAR missingness where each coordinate is missing independently with probability \(0.3\). Let \(\widetilde{\boldsymbol{X}}_0\) denote the partially observed covariate vector corresponding to \(\boldsymbol{X}_0\), and let \(\mathsf{Imp}:\mathbb{R}_{\star}^d \to \mathbb{R}^d\) be the zero imputation algorithm (which is the same as mean imputation in this example) that replaces \(\star\) by zero, so \(\boldsymbol{Z}_0 \mathrel{\vcenter{:}}= \mathsf{Imp}(\widetilde{\boldsymbol{X}}_0) = \boldsymbol{X}_0 \odot \boldsymbol{\Omega}_0\). For \(\boldsymbol{z} = (z_1,\ldots,z_d)^\top \in [-1,1]^d\) and \(\boldsymbol{\omega} = (\omega_1,\ldots,\omega_d)^\top \in \{0,1\}^d\), the Bayes regression function can be written as \[\begin{align} f^{\star}(\boldsymbol{z}, \boldsymbol{\omega}) = \begin{cases} 3z_1^2 \quad&\text{if } \omega_1 = 1\\ 1 &\text{if } \omega_1 = 0. \end{cases} \end{align}\]

2.2 ReLU neural networks↩︎

In this section, we formally define classes of neural networks with ReLU activation function \(\sigma\) given by \(\sigma(a) \mathrel{\vcenter{:}}= a\vee 0\) for \(a\in\mathbb{R}\). For a vector \(\boldsymbol{x}=(x_1,\ldots,x_d)^\top\in\mathbb{R}^d\), we define \[\begin{align} \boldsymbol{\sigma}(\boldsymbol{x}) \mathrel{\vcenter{:}}= \bigl(\sigma(x_1),\ldots,\sigma(x_d)\bigr)^\top \in [0,\infty)^d, \end{align}\] though we allow \(d\) to vary in different instances of this function without comment. Given \(L\in\mathbb{N}\) and \(\boldsymbol{p} = (p_0,p_1,\ldots,p_{L+1}) \in \mathbb{N}^{L+2}\), the set of neural networks with architecture \((L,\boldsymbol{p})\) is defined as \[\begin{align} \mathcal{F}(L,\boldsymbol{p}) \mathrel{\vcenter{:}}= &\Bigl\{ \boldsymbol{f}:\mathbb{R}^{p_0} \to \mathbb{R}^{p_{L+1}} :\; \boldsymbol{f}(\cdot) = \boldsymbol{A}_{L+1} \circ \boldsymbol{\sigma} \circ \boldsymbol{A}_L \circ \boldsymbol{\sigma} \circ \cdots \circ \boldsymbol{A}_2 \circ \boldsymbol{\sigma} \circ \boldsymbol{A}_1(\cdot),\text{ where}\nonumber\\ & \qquad\qquad \boldsymbol{A}_\ell(\boldsymbol{v}) = \boldsymbol{W}_\ell \boldsymbol{v} + \boldsymbol{b}_\ell,\, \boldsymbol{W}_\ell \in \mathbb{R}^{p_{\ell} \times p_{\ell-1}} \text{ and } \boldsymbol{b}_{\ell} \in\mathbb{R}^{p_{\ell}} \;\forall \ell\in[L+1] \Bigr\}. \label{Eq:Flp} \end{align}\tag{1}\] Here, \(L\) is the number of hidden layers (or depth of the network), \(p_1,\ldots,p_L\) are the widths of the hidden layers, \(p_0\) is the input dimension, \(p_{L+1}\) is the output dimension, \(\boldsymbol{W}_1,\ldots,\boldsymbol{W}_{L+1}\) are the weight matrices and \(\boldsymbol{b}_1,\ldots,\boldsymbol{b}_{L+1}\) are the bias vectors. For \(\boldsymbol{f}\in\mathcal{F}(L,\boldsymbol{p})\) with weight matrices \((\boldsymbol{W}_{\ell})_{\ell=1}^{L+1}\) and bias vectors \((\boldsymbol{b}_{\ell})_{\ell=1}^{L+1}\), we define \(\boldsymbol{\Theta}(\boldsymbol{f})\) to be the vector consisting of all the parameters of the neural network \(\boldsymbol{f}\), i.e.\(\boldsymbol{\Theta}(\boldsymbol{f}) \mathrel{\vcenter{:}}= \bigl(\mathrm{vec}(\boldsymbol{W}_1)^\top, \boldsymbol{b}_1^\top, \ldots,\mathrm{vec}(\boldsymbol{W}_{L+1})^\top, \boldsymbol{b}_{L+1}^\top\bigr)^\top \in \mathbb{R}^{V}\), where \(V \mathrel{\vcenter{:}}= \sum_{\ell=1}^{L+1} p_\ell(p_{\ell-1}+1)\) is the total number of parameters. Given \(s\in\mathbb{N}\), define \[\begin{align} \mathcal{F}(L,\boldsymbol{p},s) \mathrel{\vcenter{:}}= \bigl\{ \boldsymbol{f}\in\mathcal{F}(L,\boldsymbol{p}) : \|\boldsymbol{\Theta}(\boldsymbol{f})\|_0 \leq s \bigr\} \end{align}\] to be the set of neural networks with architecture \((L,\boldsymbol{p})\) and sparsity \(s\). Note that \(\mathcal{F}(L,\boldsymbol{p}, s) = \mathcal{F}(L,\boldsymbol{p})\) for all \(s\geq V\).

2.3 Pattern Embedded Neural Network estimators↩︎

Figure 2: Excess risk for Example 1 with d\in\{10,20,\ldots,50\} and n=1000. NN (blue) is a neural network that regresses Y_i onto \boldsymbol{Z}_i; NN\_concat (green) is a neural network that directly regresses Y_i onto (\boldsymbol{Z}_i, \boldsymbol{\Omega}_i); and PENN (red) is our pattern embedded neural network (with m=3). The shaded regions represent 90\% confidence intervals for the true excess risk, based on 100 repetitions of the experiment. — Figure 2: Excess risk for Example 1 with \(d\in\{10,20,\ldots,50\}\) and \(n=1000\). NN (blue) is a neural network that regresses \(Y_i\) onto \(\boldsymbol{Z}_i\); NN\(\_\)concat (green) is a neural network that directly regresses \(Y_i\) onto \((\boldsymbol{Z}_i, \boldsymbol{\Omega}_i)\); and PENN (red) is our pattern embedded neural network (with \(m=3\)). The shaded regions represent \(90\%\) confidence intervals for the true excess risk, based on 100 repetitions of the experiment.

Our aim is to estimate \(f^{\star}\) by regressing \((Y_i)_{i=1}^n\) onto \((\boldsymbol{Z}_i,\boldsymbol{\Omega}_i)_{i=1}^n\) using neural networks, while borrowing strength across similar observation patterns. Naive training of a neural network using the concatenated vectors \((\boldsymbol{Z}_i,\boldsymbol{\Omega}_i)_{i=1}^n\) as covariates leads to significant overfitting when the dimension \(d\) is large (see Figure 2), and, indeed the excess risk may be worse than that obtained by regressing \((Y_i)_{i=1}^n\) on \((\boldsymbol{Z}_i)_{i=1}^n\), ignoring the revelation vectors. The main problem is that the number of observation patterns \(|\mathcal{S}|\) may grow exponentially in \(d\), so each data point may even have a unique observation pattern, and naive training is unable to borrow strength across similar observation patterns. Moreover, while the revelation vectors \(\boldsymbol{\Omega}_i\in\{0,1\}^d\) may carry highly useful information for prediction, the raw Euclidean geometry of the hypercube \(\{0,1\}^d\) may align poorly with the predictive structure of the problem. For instance, in Example 1, two revelation vectors that differ in all but the first coordinate yield identical regression functions, despite the fact that their Euclidean distance of \(\sqrt{d-1}\) is almost maximal. As a result, direct incorporation of the revelation vectors as covariates forces the model to fit into an extraneous geometric structure that almost amounts to noise.

To remedy the issue raised in the previous paragraph, we seek to construct a learned embedding of the revelation vectors into a lower-dimensional Euclidean space where geometric proximity corresponds to similarity in predictive behaviour (see Figure 3). Such an embedding allows the model to borrow statistical strength across related missingness patterns, so as to provide better generalisation for rare patterns. Figure 3 illustrates the predictive value of our learned embeddings of the revelation vectors in Example 1, and in particular the fact that better separation in our embeddings is associated with lower excess risks. Naturally, clusters tend to have greater overlap in higher dimensions, reflecting the increased difficulty of the problem; nonetheless, even when \(d=100\), our learned three-dimensional embedding still provides considerable predictive information. The embedding illustrated takes the form of a neural network that maps the \(d\)-dimensional revelation vectors to vectors in \(\mathbb{R}^m\) for some embedding dimension \(m \leq d\) (so \(m=3\) in the figure). As a secondary consideration, the imputed covariates \(\boldsymbol{Z}_1,\ldots,\boldsymbol{Z}_n\) can also benefit from a nonlinear feature map, before both sets of transformed variables are combined in a further flexible regression model that is able to capture appropriate interactions. We again take these nonlinear functions to be neural networks, which are convenient for both modelling and fitting.

Figure 4: An illustration of the class \mathcal{F}_{\mathrm{PENN}}\bigl((L_r,\boldsymbol{p}_r)_{r=1}^3,s\bigr). — Figure 4: An illustration of the class \(\mathcal{F}_{\mathrm{PENN}}\bigl((L_r,\boldsymbol{p}_r)_{r=1}^3,s\bigr)\).

Our pattern embedded neural networks (PENNs) therefore take the form \((\boldsymbol{z},\boldsymbol{\omega}) \mapsto \boldsymbol{f}_3\bigl(\boldsymbol{f}_1(\boldsymbol{z}), \boldsymbol{f}_2(\boldsymbol{\omega})\bigr)\), where \(\boldsymbol{f}_r\) is a neural network for \(r \in \{1,2,3\}\). Here, \(\boldsymbol{f}_1\) denotes the feature map for the imputed covariates, \(\boldsymbol{f}_2\) denotes the pattern embedding for the revelation vectors and \(\boldsymbol{f}_3\) combines the learned covariate features and pattern embeddings. More precisely, for \(r \in \{1,2,3\}\), let \(L_r \in \mathbb{N}\), suppose that \(\boldsymbol{p}_r = (p_{r,0},\ldots,p_{r,L_r+1}) \in \mathbb{N}^{L_r+2}\) satisfies \(p_{3,0} = p_{1,L_1+1} + p_{2,L_2+1}\), and let \(s\in\mathbb{N}\); writing \(p_{\mathrm{in}} \mathrel{\vcenter{:}}= p_{1,0} + p_{2,0}\) and \(p_{\mathrm{out}} \mathrel{\vcenter{:}}= p_{3,L_3+1}\), the class of pattern embedded neural networks (PENNs) is given by \[\begin{align} \mathcal{F}_{\mathrm{PENN}}\bigl((L_r,\boldsymbol{p}_r)_{r=1}^3 &,s\bigr) \mathrel{\vcenter{:}}= \biggl\{ \boldsymbol{f} : \mathbb{R}^{p_{\mathrm{in}}} \to \mathbb{R}^{p_{\mathrm{out}}} : \boldsymbol{f}(\cdot,\cdot\cdot) = \boldsymbol{f}_3\bigl(\boldsymbol{f}_1(\cdot), \boldsymbol{f}_2(\cdot\cdot)\bigr), \nonumber \\ & \text{where } \boldsymbol{f}_r \in \mathcal{F}(L_r,\boldsymbol{p}_r) \text{ for } r\in\{1,2,3\} \text{ and } \sum_{r=1}^3 \|\boldsymbol{\Theta}(\boldsymbol{f}_r)\|_0 \leq s \biggr\}. \label{eq:PENN-def} \end{align}\tag{2}\] See Figure 4 for an illustration of a PENN. In the setting of Section 2.1, we seek an estimator \(\widehat{f}\) that minimises the empirical risk \(\widehat{R}_n(f)\) over an appropriate PENN class as defined in 2 . To this end, our PENN is implemented as a single neural network (using standard software such as PyTorch [63]) and trained by gradient methods, though we remark that the optimisation problem involved is non-convex, and our theory in Section 3 therefore allows for a residual optimisation error. In our applications, we will set \(p_{1,0} = p_{2,0} = d\), \(p_{2,L_2+1} = m\) and \(p_{3,L_3+1} = 1\).

3 Theoretical results↩︎

The main goal of our theory in this section is to derive a theoretical guarantee on the performance of the PENN methodology introduced in Section 2.3. Our overall strategy is first to decompose the excess risk of our estimator into a sum of three terms, representing the optimisation error, approximation error and estimation error respectively; see Proposition 1 below. This decomposition is quite general, in the sense that in addition to requiring no conditions on the dependence structure of the data generating and missingness mechanisms, we also make no assumptions on the form of the Bayes regression function \(f^\star\) and consider an arbitrary neural network estimator. A consequence of this generality, however, is that the approximation error term is not very explicit, in that it simply reflects the extent to which \(f^\star\) can be approximated by an element of our neural network class. For this reason, we then introduce natural assumptions that allow us to borrow strength across different observation patterns, as well as smoothness conditions, that provide an explicit form for the approximation error. Thus, in our main result (Theorem 2), we are able to choose the architecture of our PENN estimator so as to balance the approximation and estimation error terms to give a finite-sample excess risk bound that holds under no assumptions on the form of the missingness mechanism. This upper bound is complemented by a minimax lower bound (Theorem 3) that reveals the optimality of the PENN estimator up to poly-logarithmic factors in the sample size.

3.1 Oracle inequality↩︎

Following the strategy described above, let \(L\in\mathbb{N}\) and \(\boldsymbol{p}=(p_0,\ldots,p_{L+1})^\top \in \mathbb{N}^{L+2}\) with \(p_0=2d\) and \(p_{L+1}=1\). By a neural network estimator in \(\mathcal{F} \subseteq \mathcal{F}(L,\boldsymbol{p},s)\), we mean a jointly measurable function \(\widetilde{f}:\mathbb{R}^d \times \mathcal{S} \times (\mathbb{R}^d \times \mathcal{S} \times \mathbb{R})^n \rightarrow \mathbb{R}\) such that for each \(\mathcal{D} \mathrel{\vcenter{:}}= (\boldsymbol{z}_i,\boldsymbol{\omega}_i,y_i)_{i=1}^n \in (\mathbb{R}^d \times \mathcal{S} \times \mathbb{R})^n\), the function \(\widetilde{f}(\cdot,\cdot;\mathcal{D}) \in \mathcal{F}\). Where the data are clear from context, we often omit the final argument of \(\widetilde{f}\).

Proposition 1. In the setting of Section 2.1, assume that \(\|Y_0\|_{\psi_2} \leq \xi\) for some \(\xi\geq 1\). Let \(\widetilde{f}\) be a neural network estimator in \(\mathcal{F}\subseteq \mathcal{F}(L,\boldsymbol{p}, s)\) based on data \(\mathcal{D} \mathrel{\vcenter{:}}= (\boldsymbol{Z}_i,\boldsymbol{\Omega}_i,Y_i)_{i=1}^n\) and let \(B_n \mathrel{\vcenter{:}}= \xi\sqrt{2\log n}\). Then there exists a universal constant \(C>0\) such that for \(n \geq 2\), \[\begin{align} \mathbb{E}\bigl\{ R(T_{B_n}\widetilde{f})\bigr\} - R(f^{\star}) &\leq 2\mathbb{E}\Bigl\{ \widehat{R}_n(\widetilde{f}) - \inf_{f\in\mathcal{F}}\widehat{R}_n(f) \Bigl\} + 2\inf_{f\in\mathcal{F}} \mathbb{E}\Bigl\{ \bigl(f(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0) - f^{\star}(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\bigr)^2 \Bigr\}\nonumber\\ & + \frac{C\xi^4\log(e\xi) \log^3 n \cdot \bigl(sL\log(es) + s\log(ed)\bigr)}{n}. \end{align}\]

As a simple illustration of the bound on \(\|Y_0\|_{\psi_2}\) in Proposition 1, if \(Y_0 = f^0(\boldsymbol{X}_0) + \varepsilon_0\) where \(\|f^0\|_{\infty} \leq \xi_1\) and \(\|\varepsilon_0\|_{\psi_2} \leq \xi_2\), then \(\|Y_0\|_{\psi_2} \leq \xi_1/\sqrt{\log 2} + \xi_2\). The upper bound on the excess risk in Proposition 1 is a sum of three terms, where the first term corresponds to the optimisation error, the second term represents the approximation error, and the last term corresponds to estimation error and reflects the complexity of the function class \(\mathcal{F}\). If \(\widetilde{f}\) is an empirical risk minimiser, then the optimisation error term vanishes. Importantly, we do not insist that \(f^\star \in \mathcal{F}\), though if it does, then we may take the approximation error term to be zero. The estimation error term is of order \(sL/n\) up to poly-logarithmic factors. In general, there is a trade-off between the approximation and estimation error terms that is akin to a bias–variance trade-off: more complex classes \(\mathcal{F}\) will have smaller approximation error, but the price to be paid is through larger values of \(s\) and \(L\) in the estimation error term. Related results to Proposition 1 in the context of fully observed data include those of [7], who has an additional boundedness assumption on the parameter and input spaces, and [8], who work with fully dense neural networks. The key to our proof is a new bound on the Vapnik–Chervonenkis dimension and covering numbers of the \(\mathcal{F}(L,\boldsymbol{p},s)\) class given in Proposition 4, which allows us to remove constraints in prior work on the boundedness of covariates and the parameters in our neural networks.

3.2 Minimax rate under a piecewise smoothness assumption↩︎

In principle, the functions \(\boldsymbol{z} \mapsto f^\star(\boldsymbol{z}, \boldsymbol{\omega})\) may be arbitrarily different as \(\boldsymbol{\omega}\) varies through \(\mathcal{S}\), and indeed Proposition 1 does not restrict the differences between these functions as \(\boldsymbol{\omega}\) varies. In the worst case, then, we may have \(|\mathcal{S}| = 2^d\) different regression functions to learn! Fortunately, in many circumstances, it is reasonable to postulate that the Bayes regression function at certain different observation patterns may be similar, and this will provide great advantages for our theory.

Assumption 1. Assume that each coordinate of \(\boldsymbol{Z}_0\) is sub-exponential and that \(Y_0\) is sub-Gaussian, i.e. there exist \(\xi_1,\xi_2>0\) such that \(\|Z_{0,j}\|_{\psi_1} \leq \xi_1\) for all \(j\in[d]\) and \(\|Y_0\|_{\psi_2} \leq \xi_2\). Further assume that there exist \(K\leq |\mathcal{S}|\), a partition \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) of \(\mathcal{S}\), and functions \(f^{\mathcal{S}_1},\ldots,f^{\mathcal{S}_K} : \mathbb{R}^d \to \mathbb{R}\) such that³ \[\begin{align} f^{\star}(\boldsymbol{z}, \boldsymbol{\omega}) = \sum_{k=1}^K f^{\mathcal{S}_k}(\boldsymbol{z}) \mathbb{1}_{\{\boldsymbol{\omega} \in \mathcal{S}_k\}} \label{eq:piecewise-f-star} \end{align}\qquad{(1)}\] for all \(\boldsymbol{z} \in \mathbb{R}^d\) and \(\boldsymbol{\omega} \in \mathcal{S}\). For \(k \in [K]\), we write \(\pi_k \mathrel{\vcenter{:}}= \mathbb{P}(\boldsymbol{\Omega}_0 \in \mathcal{S}_k)\) and write \(n_k \mathrel{\vcenter{:}}= n\pi_k\) for the effective sample size* in the \(k\)th cell.*

The tail condition on \(\boldsymbol{Z}_0\) allows our covariates to be unbounded, in contrast to much of the literature on nonparametric regression. Of course, any Bayes regression function \(f^{\star}\) always satisfies ?? with \(K = |\mathcal{S}|\). However, \(K\) may be much smaller than \(|\mathcal{S}|\); e.g. in Example 1 we have \(|\mathcal{S}| = 2^d\) and \(K=2\), since we may take \(\mathcal{S}_1 = \bigl\{\boldsymbol{\omega} \in \{0,1\}^d:\omega_1 = 1\bigr\}\) and \(\mathcal{S}_2 = \bigl\{\boldsymbol{\omega} \in \{0,1\}^d:\omega_1 = 0\bigr\}\). In such circumstances, we can borrow strength across data whose revelation vectors lie in the same cell of the partition. It turns out that Assumption 1 may be weakened to requiring only that ?? holds approximately; see the discussion following Theorem 2 below.

Given an arbitrary partition \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) of \(\mathcal{S}\), there exists a Bayes regression function \(f^{\star}\) that satisfies Assumption 1 with that partition; see Lemma 10. Beyond the cardinality \(K\) of this partition, its complexity can be measured through the complexity of classes of functions (e.g. neural networks) that can cluster observation patterns in the same cell of the partition. To this end, we introduce a notion of separability of a partition of \(\mathcal{S}\).

Definition 1. Given a class \(\mathcal{F}\) of functions from \(\mathbb{R}^d\) to \(\mathbb{R}^m\), we say a partition \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) of \(\mathcal{S} \subseteq \{0,1\}^d\) is \(\mathcal{F}\)-separable* if there exist \(\boldsymbol{f} \in \mathcal{F}\), \(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_K \in \mathbb{R}^m\) and \(\epsilon>0\) such that*

\(\|\boldsymbol{f}(\boldsymbol{\omega}) - \boldsymbol{v}_k\|_{\infty} \leq \epsilon/2\) for all \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\);
\(\|\boldsymbol{v}_k - \boldsymbol{v}_{k'}\|_{\infty} \geq 2\epsilon\) for all \(k \neq k'\).

In this case, we say that \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is separated by \(\boldsymbol{f}\).

Thus \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is separated by \(\boldsymbol{f}\) if the scale over which \(\boldsymbol{f}\) varies on each \(\mathcal{S}_k\) is small by comparison with its variability across different cells of the partition. Proposition 5 guarantees that an arbitrary partition \(\{\mathcal{S}_1, \ldots, \mathcal{S}_K\}\) of \(\mathcal{S}\) is \(\mathcal{F}(2,\boldsymbol{p})\)-separable for a suitable choice of \(\boldsymbol{p}\). Moreover, if the partition is defined by a small number of coordinates (as in part (a) of that result) or a small number of halfspaces (as in part (b)), then the partition may be separated by a class of neural networks with fewer parameters.

We now introduce smoothness assumptions that will be imposed on each \(f^{\mathcal{S}_k}\) in ?? . It is convenient to invoke multi-index notation for partial derivatives, whereby for \(\boldsymbol{\alpha}=(\alpha_1,\ldots,\alpha_d)^\top \in \mathbb{N}_0^d\) and an \(\|\boldsymbol{\alpha}\|_1\)-times differentiable real-valued function \(f\) defined on a subset of \(\mathbb{R}^d\), we set \(\partial^{\boldsymbol{\alpha}}f \mathrel{\vcenter{:}}= \partial^{\alpha_1}\cdots\partial^{\alpha_d}f\). We also write \(\boldsymbol{x}^{\boldsymbol{\alpha}} := \prod_{j=1}^d x_j^{\alpha_j}\) for \(\boldsymbol{x} = (x_1,\ldots,x_d)^\top \in \mathbb{R}^d\).

Definition 2. For \(\beta,\gamma>0\), \(d\in\mathbb{N}\), \(t\in[d] \cup \{0\}\) and \(D\subseteq \mathbb{R}^d\), we write \(\beta_0 \mathrel{\vcenter{:}}= \lceil \beta \rceil -1\) and define the class of \((\beta,\gamma)\)-Hölder functions that depend only on \(t\) variables⁴ as \[\begin{align} \mathcal{H}_t^{\beta}(D,\gamma) &\mathrel{\vcenter{:}}= \biggl\{ f:D\to\mathbb{R} : \text{f depends only on t variables, f is \beta_0-times differentiable,}\\ &\max_{\boldsymbol{\alpha}\in\mathbb{N}_0^d \,:\, \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \|\partial^{\boldsymbol{\alpha}} f\|_{\infty} \leq \gamma,\, \max_{\boldsymbol{\alpha}\in\mathbb{N}_0^d \,:\, \|\boldsymbol{\alpha}\|_1 = \beta_0}\; \sup_{\boldsymbol{x}\neq \boldsymbol{y} \in D} \frac{|\partial^{\boldsymbol{\alpha}} f(\boldsymbol{x}) - \partial^{\boldsymbol{\alpha}} f(\boldsymbol{y})|}{\|\boldsymbol{x}-\boldsymbol{y}\|_{2}^{\beta-\beta_0}} \leq \gamma \biggr\}. \end{align}\] We also write \(\mathcal{H}_t^\beta(D,\mathbb{R}^{d'},\gamma)\) to denote the set of vector-valued functions \(\boldsymbol{g}:D \rightarrow \mathbb{R}^{d'}\) all of whose component functions belong to \(\mathcal{H}_t^\beta(D,\gamma)\).

Our functions \(f^{\mathcal{S}_k}\) will be assumed to be compositions of vector-valued functions whose corresponding component functions belong to these Hölder classes. Definition 3 below generalises the standard notion of Hölder smoothness to compositional classes of functions; such definitions have been widely employed in the theoretical analysis of deep learning [7], [8], [30].

Definition 3. Let \(q\in\mathbb{N}\), \(\boldsymbol{d} = (d_r)_{r=1}^{q+1} \in \mathbb{N}^{q+1}\) with \(d_1=d\) and \(d_{q+1} = 1\), \(\boldsymbol{t} = (t_r)_{r=1}^q \in \mathbb{N}_0^q\) with \(t_r \in [d_r] \cup \{0\} \;\forall r\in[q]\), \(\boldsymbol{\beta} = (\beta_r)_{r=1}^q \in (0,\infty)^q\) and \(\boldsymbol{\gamma} = (\gamma_r)_{r=1}^q \in (0,\infty)^q\). We define \(\mathcal{H}_{\mathrm{comp}}(q,\boldsymbol{d}, \boldsymbol{t}, \boldsymbol{\beta}, \boldsymbol{\gamma})\) to be the class of functions \(f:\mathbb{R}^d \to \mathbb{R}\) of the form \[\begin{align} f = \boldsymbol{g}_q \circ \cdots \circ \boldsymbol{g}_1 \end{align}\] where⁵ \(\boldsymbol{g}_{r} \in \mathcal{H}_{t_r}^{\beta_r}(\mathbb{R}^{d_r}, \mathbb{R}^{d_{r+1}}, \gamma_r)\) for all \(r \in [q]\).

As an example, if \(f\) has a single index structure, i.e. \(f(x) = g_2(a^\top x)\), for some \(a \in \mathbb{R}^d\) and \(g_2\in\mathcal{H}_1^{\beta}(\mathbb{R},\gamma)\), then \(f\) belongs to the compositional Hölder class with \(g_1:x\mapsto a^\top x\) being a linear function (which is infinitely smooth) depending on all \(d\) variables, and \(g_2\) being a \(\beta\)-Hölder function on \(\mathbb{R}\).

Given \(f = \boldsymbol{g}_q \circ \cdots \circ \boldsymbol{g}_1 \in \mathcal{H}_{\mathrm{comp}}(q,\boldsymbol{d}, \boldsymbol{t}, \boldsymbol{\beta}, \boldsymbol{\gamma})\) and \(r \in [q]\), the Hölder smoothness of \(\boldsymbol{g}_q \circ \cdots \circ \boldsymbol{g}_r\) is \[\bar{\beta}_r \mathrel{\vcenter{:}}= \beta_r \prod_{\ell=r+1}^{q} (\beta_{\ell} \wedge 1).\] This then leads to the following definition.

Definition 4. The critical composition index* of \(f = \boldsymbol{g}_q \circ \cdots \circ \boldsymbol{g}_1 \in \mathcal{H}_{\mathrm{comp}}(q,\boldsymbol{d}, \boldsymbol{t}, \boldsymbol{\beta}, \boldsymbol{\gamma})\) is⁶ \[r_* \mathrel{\vcenter{:}}= \mathop{\mathrm{sargmax}}_{r\in [q]} \frac{t_r}{\bar{\beta}_r}.\] The effective smoothness and effective dimension of \(f\) are then given by \(\bar{\beta}_* \mathrel{\vcenter{:}}= \bar{\beta}_{r_*}\) and \(t_* := t_{r_*}\) respectively.*

It is important to note that the effective smoothness and effective dimension arise from a worst-case ratio, as opposed to, for instance, the individual worst cases. For instance, returning to our single index example below Definition 3, we have \(\bar{\beta}_* = \beta\) and \(t_* = 1\), even though \(f\) depends on all \(d\) covariates. We will see in Theorem 2 below that the small effective dimension induced through its compositional structure allows us to obtain a rate of convergence that avoids the curse of dimensionality.

Assumption 2. We assume that \(f^{\mathcal{S}_k} \in \mathcal{H}_{\mathrm{comp}}(q_k,\boldsymbol{d}^{(k)}, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)})\) for each \(k\in[K]\).

We write \(r_*^{(k)}\), \(\bar{\beta}_*^{(k)}\) and \(t_*^{(k)}\) for the critical composition index, effective smoothness and effective dimension of \(f^{\mathcal{S}_k}\) respectively. Finally, then, we can state our main result:

Theorem 2. Suppose that Assumptions 1 and 2 hold. Suppose further that \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is \(\mathcal{F}(L_2,\boldsymbol{p}_2,s_2)\)-separable for some \(L_2\in\mathbb{N}\), \(\boldsymbol{p}_2 \in \mathbb{N}^{L_2+2}\) and \(s_2\in\mathbb{N}\), and let \(B_n \mathrel{\vcenter{:}}= \xi_2\sqrt{2\log n}\). Then there exist \(L_1,L_3 \in \mathbb{N}\), \(\boldsymbol{p}_1 \in \mathbb{N}^{L_1+2}\), \(\boldsymbol{p}_3 \in \mathbb{N}^{L_3+2}\) and \(s \in \mathbb{N}\) such that, writing \[\begin{align} \mathcal{F} \mathrel{\vcenter{:}}= \mathcal{F}_{\mathrm{PENN}}\bigl((L_r,\boldsymbol{p}_r)_{r=1}^3,s\bigr), \end{align}\] and letting \(\widehat{f}\) denote any neural network estimator in \(\mathcal{F}\) based on data \(\mathcal{D} \mathrel{\vcenter{:}}= (\boldsymbol{Z}_i,\boldsymbol{\Omega}_i,Y_i)_{i=1}^n\), we have for \(n \geq 2\) that \[\begin{align} \mathbb{E}\bigl\{ R(T_{B_n}\widehat{f})\bigr\} - R(f^{\star}) &\leq C \biggl\{\sum_{k=1}^K \pi_k n_k^{-2\bar\beta^{(k)}_*/(2\bar\beta^{(k)}_* + t^{(k)}_*)} + \frac{s_2\log s_2}{n}\biggr\} \cdot (\log n)^{2\max_{k\in[K]} \bar{\beta}^{(k)}_1 \vee 6}\\ & + 2\mathbb{E}\Bigl\{\widehat{R}_n(\widehat{f}) - \inf_{f\in\mathcal{F}} \widehat{R}_n(f) \Bigr\}, \end{align}\] where \(C>0\) does not depend on \(n\), \((\pi_k)_{k=1}^K\) or \(s_2\).

In order to understand the main messages of Theorem 2, first suppose that we are able to compute the empirical risk minimiser exactly, so that the optimisation error \(\mathbb{E}\bigl\{\widehat{R}_n(\widehat{f}) - \inf_{f\in\mathcal{F}} \widehat{R}_n(f) \bigr\}\) is zero. Then the excess risk of a truncated PENN estimator is controlled by the sum of two interpretable terms. The first of these would be the minimax rate for estimating the Bayes regression function if the partition \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) of Assumption 1 were known, up to a poly-logarithmic factor in the sample size. It comprises a weighted average over \(k \in [K]\) of the minimax rates of estimating the Bayes regression function \(f^{\mathcal{S}_k}\) on the \(k\)th cell of the partition, with effective sample size \(n_k\), effective smoothness \(\bar{\beta}_*^{(k)}\) and effective dimension \(t_*^{(k)}\); see Theorem 3 below. As an attraction of this weighted average form, we see that the \(k\)th summand \[\pi_k n_k^{-2\bar{\beta}_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})} = \pi_k^{t_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})} n^{-2\bar{\beta}_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})} \to 0 \quad\text{as \pi_k \rightarrow 0,}\] for fixed \(n\); thus, rarely observed missingness patterns have negligible effect on the excess risk. The second term in the bound in Theorem 2 is the additional error incurred due to the fact that the \(\mathcal{F}(L_2,\boldsymbol{p}_2,s_2)\)-separable partition \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is unknown. For example, in cases where the partition is defined by a small number of coordinates or a small number of halfspaces, we can expect this second term to be dominated by the first. In particular, this occurs in the setting of Proposition 5(a) with \(|\mathcal{S}_{\mathcal{J}}| \lesssim \sum_{k=1}^K n_k^{t^{(k)}_*/(2\bar\beta^{(k)}_* + t^{(k)}_*)}\) and in the setting of Proposition 5(b) with \(K\sum_{k=1}^K P_k \lesssim \sum_{k=1}^K n_k^{t^{(k)}_*/(2\bar\beta^{(k)}_* + t^{(k)}_*)}\). Theorem 2 also accounts for cases where the empirical risk minimiser is not computed exactly, in which case we incur an additional optimisation error.

We next characterise the order in \(n_1,\ldots,n_K\) of the parameters \(L_1,L_3,\boldsymbol{p}_1, \boldsymbol{p}_3\) and \(s\) needed for Theorem 2 to hold. Writing \(\boldsymbol{p}_1 = (d, p_{1,*}, \ldots, p_{1,*}, p_{1,L_1+1})^\top \in \mathbb{N}^{L_1+2}\) and \(\boldsymbol{p}_3 = (d, p_{3,*}, \ldots, p_{3,*}, 1)^\top \in \mathbb{N}^{L_3+2}\), we can see from the proof of Theorem 2 that it suffices to choose \(L_1\) and \(L_3\) of constant order in the sample size, together with \[\begin{gather} p_{1,*} \asymp \sum_{k=1}^K n_k^{t^{(k)}_* / (4\bar{\beta}^{(k)}_* + 2t^{(k)}_*)}\log n, \quad p_{3,*} \asymp \sum_{k=1}^K n_k^{t^{(k)}_* / \{(L_3-3)(2\bar{\beta}^{(k)}_* + t^{(k)}_*)\}}, \\ s \asymp s_2 + \sum_{k=1}^K n_k^{t^{(k)}_* / (2\bar{\beta}^{(k)}_* + t^{(k)}_*)}\log^2 n. \end{gather}\] Moreover, by [NN-enlarging] in Appendix 6 and the fact that the bound in Proposition 1 does not depend on the widths of the hidden layers, we may increase \(p_{1,*}\) and \(p_{3,*}\) without affecting the bound in Theorem 2. This means that Theorem 2 applies to over-parametrised neural networks of appropriate sparsity.

From the proof, we can see that the quantity \(C > 0\) in Theorem 2 may be chosen as the maximum over \(k\in[K]\) of polynomial functions of \(d, \boldsymbol{d}^{(k)}, \boldsymbol{t}^{(k)}\), whose degrees depend only on \(\boldsymbol{\beta}^{(k)}\) and whose coefficients depend only on \(p_{2,L_2+1}, L_1, L_2, L_3, \xi_1, \xi_2, d, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}\). In particular, if \(\pi_k = 1/K\), \(\beta^{(k)}_r = \beta \geq 1\) and \(t^{(k)}_r = t\) for all \(k\in[K]\) and \(r\in[q_k]\), then the first term in the upper bound simplifies to \((K/n)^{2\beta/(2\beta+t)}\), up to a poly-logarithmic factor in \(n\) that does not depend on \(K\). A final observation from the proof is that Assumption 1 can be weakened so that the Bayes regression function is not required to be identical on different elements within the same \(\mathcal{S}_k\); in fact, it suffices to assume that \(|f^{\star}(\boldsymbol{z},\boldsymbol{\omega}) - f^{\mathcal{S}_k}(\boldsymbol{z})| \lesssim n_k^{-\bar{\beta}_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})}\) for \(\boldsymbol{z}\in\mathbb{R}^d\), \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\).

It is worth highlighting the novel aspects of Theorem 2 relative to prior work with fully observed data [7], [8]. One key challenge for us is to formulate an appropriate model to allow us to borrow strength across different missingness patterns. This is essential in view of the fact that there can be up to \(2^d\) different missingness patterns in total, and is achieved through our Assumption 1. Likewise, the \(\mathcal{F}\)-separability condition in Definition 1 that captures the complexity of the cell partition of the Bayes regression function is new. The main challenge in the proof of Theorem 2 is to achieve the delicate balance of the estimation and approximation errors needed to obtain the \(\sum_{k=1}^K \pi_k n_k^{-2\bar{\beta}_*^{(k)}/(2\bar{\beta}_*^{(k)} + t_*^{(k)})}\) term in the bound; this term does not arise when no missingness is present.

We complement the upper bound of Theorem 2 with a corresponding minimax lower bound, that uses the notation of Assumptions 1 and 2, as well as Definition 4. Further, for \(k\in[K]\), define \(\mathcal{J}^{(k)} \mathrel{\vcenter{:}}= \{j\in[d] : \omega_j = 1 \text{ for all } \boldsymbol{\omega} \in \mathcal{S}_k\}\), as well as \(d_*^{(k)} \mathrel{\vcenter{:}}= d_{r_*^{(k)}}^{(k)}\) and \(\gamma_*^{(k)} \mathrel{\vcenter{:}}= \gamma^{(k)}_{r_*^{(k)}}\).

Theorem 3. Let \(\mathcal{P}\) be the set of all distributions of \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0)\) where \(\boldsymbol{Z}_0 = \mathsf{Imp}(\widetilde{\boldsymbol{X}}_0)\), where \(\widetilde{\boldsymbol{X}}_0\) denotes the partially observed covariate vector and where \((\boldsymbol{X}_0, \boldsymbol{\Omega}_0, Y_0)\) satisfies Assumptions 1 and 2 with \(\xi_1,\xi_2\geq 1\). Suppose further that for some \(j_*\in[d]\), we have \[t_*^{(k)} \leq \min\bigl\{d_1^{(k)},\ldots,d_*^{(k)}\bigr\} \wedge \bigl|\mathcal{J}^{(k)} \setminus \{j_*\}\bigr| \wedge \gamma_*^{(k)}\] for all \(k \in [K]\). For \(P\in\mathcal{P}\), let \(f^{\star} \equiv f^{\star}_P \mathrel{\vcenter{:}}= \mathbb{E}_P(Y_0 \,|\, \boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\), and let \(\widehat{\mathcal{F}}\) be the set of all estimators of \(f^\star\) based on a sample of size \(n\), i.e. the set of Borel measurable functions from \(\mathbb{R}^d \times \mathcal{S} \times (\mathbb{R}^d \times \mathcal{S} \times \mathbb{R})^n\) to \(\mathbb{R}\). Then there exists \(c>0\), depending only on \(\xi_2\) and \((\bar{\beta}_*^{(k)}, t_*^{(k)})_{k=1}^K\), such that \[\begin{align} \inf_{\widehat{f} \in \widehat{\mathcal{F}}} \sup_{P\in \mathcal{P}} \mathbb{E}_{P^{\otimes n}} \bigl\{R(\widehat{f}) - R(f^{\star})\bigr\} \geq c \sum_{k=1}^K \pi_k n_k^{-2\bar{\beta}_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})} \end{align}\] for all \(n \in \mathbb{N}\).

Theorem 3 reveals that the main term in the upper bound in Theorem 2, namely the first estimation error term, is minimax optimal in \(n\) and \(\pi_1,\ldots,\pi_K\), up to a poly-logarithmic factor in \(n\).

4 Simulations↩︎

In this section, we study the empirical performance of Pattern Embedded Neural Network (PENN) estimators on simulated, semi-synthetic and real data. Since PENN estimators can be used in conjunction with any imputation technique, we consider (columnwise) mean imputation (MI), MissForest imputation (MF) [21] and a python implementation of Multiple Imputation by Chained Equations (MICE) [22] called IterativeImputer (II) from scikit-learn [64]. In each case, we compare PENN with standard neural networks that do not incorporate the revelation vectors as covariates. We also compare with XGBoost [23] and random forests [24], which are two popular tree-based algorithms that handle missing values directly by learning default split directions for observations with missingness. For all of our numerical experiments, we divide the data into training, validation and test sets. We fit the neural networks on the training data by first running the stochastic optimisation method AdamW [20] for 10 epochs, and then keeping a proportion \(\lambda \in \{0.1,0.2,0.4,0.8\}\) of weights of largest magnitude (in addition to all of the bias vectors) to obtain a sparse network. Following the recommendation of [65], we then randomly reinitialise the non-zero parameters after this pruning step using the PyTorch function torch.nn.init.kaiming_uniform_ and retrain the sparse model via AdamW. Early stopping [66] is incorporated, so that the training process for each value of \(\lambda\) is terminated once the validation loss fails to decrease by at least \(0{.}001\) in 10 epochs. The tuning parameter \(\lambda\) is then chosen to minimise the average loss on the validation set, and finally the performance of this selected estimator on the test set is reported. For XGBoost, we choose the max_depth parameter from \(\{3,6,9,12\}\) based on its performance on the validation set, while for random forests, we tune its max_features parameter from \(\{\lceil0.1d\rceil, \lceil0.2d\rceil, \lceil0.4d\rceil, \lceil0.8d\rceil\}\); other tuning parameters for these methods were chosen using default settings. We remark that although our theory requires the data used for imputation to be independent of the training data, in our simulations we train the imputation algorithms on the whole dataset (training, validation and test sets) and then impute the missing entries.

In our simulations, for a dataset with (training) sample size \(n\) and covariate dimension \(d\), we define \(w_1 \mathrel{\vcenter{:}}= \lceil \sqrt{n} \rceil\), \(w_2 \mathrel{\vcenter{:}}= \lceil w_1/5 \rceil\) and embedding dimension \(m\mathrel{\vcenter{:}}= \lceil \sqrt{d} \rceil \wedge \lceil w_1/20 \rceil\). Then

PENN uses \(\mathcal{F}_{\mathrm{PENN}}\bigl((L_r,\boldsymbol{p}_r)_{r=1}^3, s\bigr)\), where \(L_1 = 3\), \(\boldsymbol{p}_1 = (d, w_1, w_1, w_1, w_1)\), \(L_2 = 2\), \(\boldsymbol{p}_2 = (d,w_2,w_2,m)\) and \(L_3=3\), \(\boldsymbol{p}_3=(w_1+m,w_1,w_1,w_1,1)\);
NN uses \(\mathcal{F}\bigl(6, (d,w_1,w_1,w_1,w_1,w_1,w_1,1),s\bigr)\).

By [NN-composition], the PENN class above has six hidden layers in total, not including the embedding function \(\boldsymbol{f}_2\); see 2 and Figure 4. We therefore compare it with a standard neural network with six hidden layers of the same width. The sparsity \(s\) is chosen as described above.

4.1 Simulated data↩︎

For each of our experiments on simulated data, we take \(d=20\), with a training set of size \(n=10{,}000\), meaning that \(m = 4\), as well as validation and test sets each of size \(5{,}000\). Our data generating mechanisms were chosen as follows:

4.1.0.1 Model 1:

\(\boldsymbol{X}_0 \sim \mathrm{Unif}[-1,1]^d\), \(Y_0 = \exp(X_{0,1} + X_{0,2}) + 4X_{0,3}^2 + \varepsilon_0\), \(\varepsilon_0\sim N(0,0.25)\), \(\varepsilon_0 \perp\!\!\!\perp\boldsymbol{X}_0\), \(\boldsymbol{\Omega}_0 \perp\!\!\!\perp(\boldsymbol{X}_0, \varepsilon_0)\) and \(\Omega_{0,j} \overset{\mathrm{iid}}{\sim} \mathrm{Ber}(0.7)\) for \(j \in [d]\).

4.1.0.2 Model 2:

\(\boldsymbol{X}_0 \sim \mathrm{Unif}[-1,1]^d\), \(Y_0 = 2\sin(2X_{0,1} + 2X_{0,2} + 2X_{0,3}) + 2X_{0,3} + \varepsilon_0\), \(\varepsilon_0\sim N(0,0.25)\), \(\varepsilon_0 \perp\!\!\!\perp\boldsymbol{X}_0\), \(\Omega_{0,j} \overset{\mathrm{iid}}{\sim} \mathrm{Ber}(0.7)\) independent of \(\boldsymbol{X}_0\) for \(j\notin\{2,3\}\), and \(\Omega_{0,j} = \mathbb{1}_{\{X_{0,j} \leq 0.4\}}\) for \(j\in\{2,3\}\).

4.1.0.3 Model 3:

As for Model 1 except that we set \(X_{0,1} = \sqrt{X_{0,4}+1} - 0.7 + \mathrm{Unif}[-0.3,0.3]\) and \(X_{0,3} = 0.7X_{0,5} + \mathrm{Unif}[-0.3,0.3]\).

4.1.0.4 Model 4:

As for Model 2 except that we set \(X_{0,1} = \sqrt{X_{0,4}+1} - 0.7 + \mathrm{Unif}[-0.3,0.3]\) and \(X_{0,3} = 0.7X_{0,5} + \mathrm{Unif}[-0.3,0.3]\).

Thus, Models 1 and 3 are MCAR, while Models 2 and 4 are MNAR. In Models 1 and 2, the different coordinates of the covariates are independent, while in Models 3 and 4 we introduce positive correlation between \(X_{0,1}\) and \(X_{0,4}\), and between \(X_{0,3}\) and \(X_{0,5}\). In each case, the true regression function depends only on the first three components of \(\boldsymbol{X}_0\); this facilitates computation of the Bayes risk via Monte Carlo integration.

The results of our simulations over 100 repetitions are presented in Figure 5. We observe that for all four models, PENN improves the performance of vanilla NNs for each imputation technique, often dramatically. In particular, it is able to substantially remedy the strikingly poor performance of NN_MF for Models 2 and 4. It seems that, to some extent, more successful imputation techniques for the vanilla neural network estimator tend to yield more successful PENN estimators. The XGBoost and random forest methods are competitive for Model 1, but less so for the other three models. In Appendix 14, we also provide visualisations of the learned pattern embeddings.

4.2 Semi-synthetic data↩︎

The aim of this subsection is to consider two semi-synthetic datasets. By this we mean that we take two real datasets without missingness, and artificially introduce missingness according to two different prescribed mechanisms that we articulate below. An attraction of this approach is that it allows us to study the effects of different types of missingness on real data.

4.2.0.1 Relative location of CT dataset:

The relative location of Computed Tomography (CT) dataset from https://www.openml.org/search?type=data&status=active&id=46300 is a complete dataset with \(d=384\) and total sample size \(n=53{,}500\). The response variable is the relative location of the CT slice on the axial axis of the human body, while the covariates describe the location of bone structures and the location of air inclusions. Here we again consider MCAR missingness with homogeneous observation probability 0.7 in each coordinate. For MNAR missingness, the probability of observing \(X_{ij}\) is given by \(\mathrm{sigmoid}(-2X_{ij} + 4\bar{X}_i + 1)\), where \(\mathrm{sigmoid}(x) \mathrel{\vcenter{:}}= 1/(1+e^{-x})\) and \(\bar{X}_i \mathrel{\vcenter{:}}= \frac{1}{d} \sum_{k=1}^d X_{ik}\).

4.2.0.2 MNIST dataset:

The MNIST dataset [67] in PyTorch consists of \(70{,}000\) greyscale images of handwritten digits from 0 to 9, with each image represented as a \(28 \times 28\) pixel grid. We normalise the greyscale so that it takes values in \([0,1]\), and the goal is to predict the labels based on the images. To reflect the fact that missingness is likely to be correlated among nearby pixels, we partition each image uniformly into 49 blocks, each of \(4\times 4\) pixels. In our MCAR setting, each block is observed independently with probability \(0.5\); in our MNAR setting, for each \(\ell\in\{0,\ldots,9\}\), we draw a random vector \(\boldsymbol{p}_\ell = (p_{\ell,1},\ldots,p_{\ell,49})^\top\) uniformly from \([0.2,0.8]^{49}\), and generate \(\Omega_{i,j} \sim \mathrm{Ber}(p_{\ell_i,j})\) independently for \(j \in [49]\), where \(\ell_i\) is the label for the \(i\)th observation. In other words, in our MNAR setting, the missingness probability varies across different labels, while the overall expected missingness probability is 0.5 for all observations. For the MNIST dataset, we adopt only mean imputation, since MissForest and MICE are not well-suited for image data. Figure 6 presents the first 16 images from the MNIST dataset with MCAR and MNAR missingness.

In image classification tasks, convolutional neural networks [1], [68], [69] have achieved great successes; see also [70] for an introduction. Thus, for the MNIST dataset, we replace each of the first two hidden layers in \(\boldsymbol{f}_1\) in the definition of PENN 2 , and each of the first two hidden layers in NN, by a composition of a 2D convolutional layer, ReLU activation layer and max pooling layer. Details of the architectures of PENN and NN with convolutional layers used in our simulations can be found at https://github.com/tianyima2000/DNN_missing_data. Again, we compare a PENN with a neural network of the same architecture except that the embedding function has been removed, as well as with XGBoost and random forests. In addition, we include a Vision Transformer (ViT) [25] as a benchmark⁷ for the MNIST dataset, since ViT architectures can be applied directly to images with missing or occluded patches by downweighting attention weights on patches exhibiting missingness or occlusion. Our training employs the cross-entropy loss, which is the negative log-likelihood of the relevant multinomial distribution, for the MNIST classification task.

For both datasets, and for each of 100 repetitions, we randomly split the dataset into training, validation and test sets with sizes in the ratio 8:1:1 after introducing the missingness. For the regression task, we measure the performance of the algorithms via the proportion of unexplained variance (PUV), which is the ratio of the mean squared prediction error on the test set to the sample variance of the response on the same test set. On the other hand, for the classification task, we measure the performance of the algorithms by the misclassification error (MCE) on the test set. The results for the two different datasets are presented in Figures 7 and 8. For MCAR missingness, the PENN estimator is at least comparable with the vanilla NN estimator in terms of overall performance, while for MNAR missingness, it provides a significant improvement. PENN also improves substantially on XGBoost, random forests and ViT.

4.3 Real data↩︎

Finally, we now turn to a further real dataset that already has some missing values.

4.3.0.1 Credit score prediction dataset:

The credit score prediction dataset from https://www.kaggle.com/datasets/prasy46/credit-score-prediction has \(d=304\) and total sample size of \(100{,}000\). The response variable of interest is the credit rating, quantified as a positive integer ranging from 300 to 839 in the available data. There are 41 columns with missingness, and the observation probabilities for the columns with missingness are given in the left panel of Figure 9.

Again, for each of 30 repetitions, we randomly split the dataset into training, validation and test sets with sizes in the ratio 8:1:1. The PUVs are presented in the right panel of Figure 9 for the credit score data. The improvements of PENN over both the vanilla NN estimator, as well as XGBoost and random forests, are again very notable.

Figure 9: Left: Histogram of the observation probabilities for the columns with missingness. Right: PUVs for the credit score prediction dataset..

5 Discussion↩︎

In this paper, we have introduced Pattern Embedded Neural Networks (PENNs) as a novel deep learning architecture for nonparametric regression with missing covariates. Example 1, which is illustrated in Figure 1, shows that the function \(\boldsymbol{z} \mapsto \mathbb{E}(\boldsymbol{Y} \, | \, \boldsymbol{Z} = \boldsymbol{z})\) may have discontinuities caused by the different observation patterns, so one of the main messages of this example is that the revelation vectors should be incorporated into the modelling process.

On the other hand, Figure 2 provides the insight that simply including the revelation vectors as additional covariates (thereby increasing the dimension of the input space by a factor of 2) may even harm predictive performance. The primary methodological contribution of PENNs, then, is to provide an effective compression of the information in the revelation vectors by embedding them into a relatively low-dimensional space. An attractive feature of the methodology is that it can be used in conjunction with any existing imputation technique.

We provide theoretical support for the use of PENNs in the form of a finite-sample upper bound on their excess risk that holds without any assumption on the relationship between the data generating and missingness mechanisms. Our Assumption 1, which partitions the Bayes regression function into different cells, allows us to borrow strength across different observation patterns, and the main conclusion of Theorems 2 and 3 is that PENNs typically achieve the minimax rate of convergence as if the cells in this partition were known in advance, up to a poly-logarithmic factor in the sample size.

Our theoretical results are complemented by numerical experiments on synthetic, semi-synthetic and real data, which confirm the practical improvements offered by PENNs.

Acknowledgement↩︎

The research of TM and RJS was supported by RJS’s European Research Council Advanced Grant 101019498.

6 Some properties of neural networks↩︎

We summarise some basic operations associated with neural networks:

Neural network enlarging: Let \(L\in\mathbb{N}\), let \(\boldsymbol{p}_1, \boldsymbol{p}_2 \in \mathbb{N}^{L+2}\) be such that \(\boldsymbol{p}_1 \leq \boldsymbol{p}_2\) coordinate-wise and let \(s\in\mathbb{N}\). Then, from the definition, \(\mathcal{F}(L,\boldsymbol{p}_1, s) \subseteq \mathcal{F}(L,\boldsymbol{p}_2, s)\).
Neural network composition: \(\boldsymbol{p}_1 = (p_{1,0},\ldots,p_{1,L_1+1})^\top \in \mathbb{N}^{L_1+2}\) and \(\boldsymbol{p}_2 = (p_{2,0},\ldots,p_{2,L_2+1})^\top \in \mathbb{N}^{L_2+2}\) satisfy \(p_{1,L_1+1} = p_{2,0}\); let \(\boldsymbol{f}_1 \in\mathcal{F}(L_1,\boldsymbol{p}_1)\) and \(\boldsymbol{f}_2 \in\mathcal{F}(L_2,\boldsymbol{p}_2)\) (if either \(\boldsymbol{f}_1\) or \(\boldsymbol{f}_2\) is an affine function, then we set the corresponding \(L_1\) or \(L_2\) to be zero). Then \[\begin{gather} \boldsymbol{f}_2 \circ \boldsymbol{f}_1 \in \mathcal{F}(L_1+L_2,\, \boldsymbol{p}_3),\text{ where}\\ \boldsymbol{p}_3 \mathrel{\vcenter{:}}= (p_{1,0},\, \ldots,\, p_{1,L_1},\, p_{2,1},\, \ldots,\, p_{2,L_2+1}) \in \mathbb{N}^{L_1+L_2+2}. \end{gather}\] To see this, suppose that \(\boldsymbol{f}_1(\cdot) = \boldsymbol{A}_{L_1+1}^{(1)} \circ \boldsymbol{\sigma} \circ \boldsymbol{A}_{L_1}^{(1)} \circ \boldsymbol{\sigma} \circ \cdots \circ \boldsymbol{A}_2^{(1)} \circ \boldsymbol{\sigma} \circ \boldsymbol{A}_1^{(1)}(\cdot)\) and \(\boldsymbol{f}_2(\cdot) = \boldsymbol{A}_{L_2+1}^{(2)} \circ \boldsymbol{\sigma} \circ \boldsymbol{A}_{L_2}^{(2)} \circ \boldsymbol{\sigma} \circ \cdots \circ \boldsymbol{A}_2^{(2)} \circ \boldsymbol{\sigma} \circ \boldsymbol{A}_1^{(2)}(\cdot)\). Then \[\begin{align} \boldsymbol{f}_2 \circ \boldsymbol{f}_1 (\cdot) = \boldsymbol{A}_{L_2+1}^{(2)} \circ \boldsymbol{\sigma} \circ \cdots \circ \boldsymbol{A}_2^{(2)} \circ \boldsymbol{\sigma} \circ \bigl(\boldsymbol{A}_1^{(2)} \circ \boldsymbol{A}_{L_1+1}^{(1)}\bigr) \circ \boldsymbol{\sigma} \circ \cdots \circ \boldsymbol{A}_2^{(1)} \circ \boldsymbol{\sigma} \circ \boldsymbol{A}_1^{(1)}(\cdot) \end{align}\] where we note that \(\boldsymbol{A}_1^{(2)} \circ \boldsymbol{A}_{L_1+1}^{(1)}: \mathbb{R}^{p_{1,L_1}} \to \mathbb{R}^{p_{2,1}}\) is an affine function.
Neural network padding: Let \(L_1,L_2 \in \mathbb{N}\) be such that \(L_1 < L_2\), let \(\boldsymbol{p}_1 = (p_{1,0},\ldots,p_{1,L_1+1})^\top \in \mathbb{N}^{L_1+2}\), \(\boldsymbol{p}_2 = (\boldsymbol{p}_1, 2p_{1,L_1+1},\ldots, 2p_{1,L_1+1})^\top \in \mathbb{N}^{L_2+2}\) and \(s\in\mathbb{N}\). Then \(\mathcal{F}(L_1, \boldsymbol{p}_1, s) \subseteq \mathcal{F}\bigl(L_2, \boldsymbol{p}_2, 2s+2p_{1,L_1+1}(L_2-L_1)\bigr)\). To see this, let \(\boldsymbol{\phi} \in \mathcal{F}\bigl(1, (p_{1,L_1+1}, 2p_{1,L_1+1}, p_{1,L_1+1})\bigr)\) be defined by \(\boldsymbol{\phi} (\boldsymbol{y}) \mathrel{\vcenter{:}}= \boldsymbol{\sigma}(\boldsymbol{y}) - \boldsymbol{\sigma}(-\boldsymbol{y})\) for \(\boldsymbol{y} \in \mathbb{R}^{p_{1,L_1+1}}\), so that \(\boldsymbol{\phi}(\boldsymbol{y}) = \boldsymbol{y}\). Let \(\boldsymbol{f}_1 \in \mathcal{F}(L_1, \boldsymbol{p}_1, s)\), and define \(\boldsymbol{f}_2 \mathrel{\vcenter{:}}= \boldsymbol{\phi} \circ \cdots\circ \boldsymbol{\phi} \circ \boldsymbol{f}_1\), where \(\boldsymbol{\phi}\) is applied \((L_2-L_1)\)-times. Then \(\boldsymbol{f}_1(\boldsymbol{x}) = \boldsymbol{f}_2(\boldsymbol{x})\) for all \(\boldsymbol{x} \in \mathbb{R}^{p_{1,0}}\), and \(\boldsymbol{f}_2 \in \mathcal{F}\bigl(L_2, \boldsymbol{p}_2, 2s + 2p_{1,L_1+1}(L_2-L_1)\bigr)\) by [NN-composition] and counting parameters.
Neural network parallelisation: Let \(N, L \in\mathbb{N}\) and for \(i\in[N]\), let \(\boldsymbol{f}_i \in \mathcal{F}(L,\boldsymbol{p}_i,s_i)\) where \(\boldsymbol{p}_i = (d,p_{i,1},\ldots,p_{i,L+1})^\top \in \mathbb{N}^{L+2}\) and \(s_i \in \mathbb{N}\). Then, writing \(\boldsymbol{f}(\cdot) = \bigl(\boldsymbol{f}_1(\cdot)^\top, \ldots, \boldsymbol{f}_N(\cdot)^\top \bigr)^\top\), we have from the definition that \[\begin{align} \boldsymbol{f} \in \mathcal{F}\biggl(L,\, \Bigl(d,\sum_{i=1}^N p_{i,1}, \ldots, \sum_{i=1}^N p_{i,L+1}\Bigr),\, \sum_{i=1}^N s_i\biggr). \end{align}\]

7 Covering number bounds for sparse neural networks↩︎

Our oracle inequality for the excess risk of sparse neural network estimators in Proposition 1 relies on bounds on the covering number of the relevant class that we develop in this subsection. In fact, our proof proceeds via a bound on the pseudo-dimension of this class, which is related to its Vapnik–Chervonenkis (VC) dimension, so we begin by defining the notions we require.

Definition 5. Let \(\mathcal{H}\) be a set of functions from \(\mathcal{X}\subseteq\mathbb{R}^d\) to \(\{0,1\}\). For \(m\in\mathbb{N}\), the shattering coefficient* is defined as \[\begin{align} \mathrm{shat}(\mathcal{H},m) \mathrel{\vcenter{:}}= \max_{\boldsymbol{x}_1,\ldots,\boldsymbol{x}_m \in \mathcal{X}} \bigl| \bigl\{\bigl(h(\boldsymbol{x}_1), \ldots, h(\boldsymbol{x}_m)\bigr) : h\in\mathcal{H}\bigr\} \bigr|. \end{align}\] The VC-dimension of \(\mathcal{H}\) is defined as \[\begin{align} \mathrm{VCdim}(\mathcal{H}) \mathrel{\vcenter{:}}= \sup \{m\in\mathbb{N} : \mathrm{shat}(\mathcal{H},m) = 2^m\}. \end{align}\]*

We define the sign function \(\mathrm{sgn} : \mathbb{R} \to \{0,1\}\) as⁸ \(\mathrm{sgn}(x) \mathrel{\vcenter{:}}= \mathbb{1}_{\{x>0\}}\). If \(\mathcal{F}\) is a class of real-valued functions, then we define \(\mathrm{sgn}\circ\mathcal{F} \mathrel{\vcenter{:}}= \{\mathrm{sgn}\circ f : f\in\mathcal{F}\}\).

Definition 6. Let \(\mathcal{F}\) be a set of functions from \(\mathcal{X}\subseteq\mathbb{R}^d\) to \(\mathbb{R}\). The pseudo-dimension* of \(\mathcal{F}\) is defined as \[\begin{align} \mathrm{Pdim}(\mathcal{F}) \mathrel{\vcenter{:}}= \mathrm{VCdim}\bigl( \bigl\{(\boldsymbol{x},y) \mapsto \mathrm{sgn}\bigl(f(\boldsymbol{x})-y\bigr) : f\in\mathcal{F}\bigr\} \bigr). \end{align}\] For \(\epsilon>0\), we say that a collection of functions \(g_1,\ldots,g_N:\mathcal{X}\to\mathbb{R}\) is an \(\epsilon\)-cover of \(\mathcal{F}\) with respect to \(\|\cdot\|_{L_q(\mu)}\) if for every \(f\in\mathcal{F}\), there exists \(j=j(f) \in [N]\) such that \(\|f-g_j\|_{L_q(\mu)} \leq \epsilon\). The \(\epsilon\)-covering number of \(\mathcal{F}\) with respect to \(\|\cdot\|_{L_q(\mu)}\), written as \(\mathcal{N}(\epsilon,\mathcal{F},\|\cdot\|_{L_q(\mu)})\), is the cardinality of the smallest \(\epsilon\)-cover of \(\mathcal{F}\) with respect to \(\|\cdot\|_{L_q(\mu)}\) (if no finite \(\epsilon\)-cover exists, then the \(\epsilon\)-covering number is \(\infty\)).*

The following proposition provides upper bounds on the VC-dimension and covering number of the class \(\mathcal{F}(L,\boldsymbol{p},s)\). The proof is based on [71], which gives an upper bound on the VC-dimension of the class \(\mathcal{F}(L,\boldsymbol{p})\). We also remark that upper bounds on the covering number of the class \(\{f\in\mathcal{F}(L,\boldsymbol{p},s) : \|\boldsymbol{\Theta}(\boldsymbol{f})\|_{\infty} \leq 1\}\) have been obtained by, e.g. [7]; however, these do not imply an upper bound on its VC-dimension, and they do not generalise to the class \(\mathcal{F}(L,\boldsymbol{p},s)\).

Proposition 4. Let \(L\in\mathbb{N}\), \(\boldsymbol{p} = (p_0,\ldots,p_{L+1})^\top \in \mathbb{N}^{L+2}\) with \(p_{L+1}=1\), let \(V \mathrel{\vcenter{:}}= \sum_{\ell=1}^{L+1} p_\ell(p_{\ell-1}+1)\) and let \(s\in[V]\).

We have \[\begin{align} \mathrm{VCdim}\bigl(\mathrm{sgn}\circ\mathcal{F}(L,\boldsymbol{p},s)\bigr) &\leq \mathrm{Pdim}\bigl(\mathcal{F}(L,\boldsymbol{p},s)\bigr)\\ &\leq 6s(L+1)\log_2(3s) + 2s\log_2(2p_0) \\ &\lesssim sL\log (es) + s\log(ep_0). \end{align}\]
For \(q \in [1,\infty)\), \(B>0\), \(\epsilon\in(0, B/2)\) and any probability measure \(\mu\) on \(\mathbb{R}^d\), we have \[\begin{align} \log \mathcal{N}\bigl(\epsilon,\, T_B \circ \mathcal{F}(L,\boldsymbol{p},s),\, \|\cdot\|_{L_q(\mu)} \bigr) &\leq 2q\cdot\mathrm{Pdim}\bigl(\mathcal{F}(L,\boldsymbol{p},s)\bigr)\log(10B/\epsilon) \\ &\lesssim q\bigl\{sL\log (es) + s\log(ep_0)\bigr\}\log(B/\epsilon). \end{align}\]

By [71], there exists a universal constant \(C_3 > 0\) such that if \(s \geq C_3 L \geq C_3^2\), then there exists \(\boldsymbol{p}' = (p'_0,\ldots,p'_{L+1})^\top \in \mathbb{N}^{L+2}\) with \(V' \mathrel{\vcenter{:}}= \sum_{\ell=1}^{L+1} p_\ell'(p_{\ell-1}'+1) \leq s\), such that \(\mathrm{VCdim}\bigl(\mathrm{sgn} \circ \mathcal{F}(L,\boldsymbol{p}')\bigr) \geq c_4\cdot sL\log(s/L)\) for some universal constant \(c_4>0\). By [NN-enlarging], \(\mathcal{F}(L,\boldsymbol{p}') \subseteq \mathcal{F}(L,\boldsymbol{p},s)\) for all \(\boldsymbol{p}\in\mathbb{N}^{L+2}\) such that \(\boldsymbol{p} \geq \boldsymbol{p}'\) coordinate-wise, so the same lower bound then applies to \(\mathrm{VCdim}\bigl(\mathrm{sgn} \circ \mathcal{F}(L,\boldsymbol{p},s)\bigr)\). Thus, under the above condition on \(s\) and \(L\), our upper bound in Proposition 4(a) is tight up to a logarithmic factor in \(n\) when \(\boldsymbol{p}\) is sufficiently large.

Proof. (a) We first observe that \[\begin{align} \mathrm{Pdim}\bigl(\mathcal{F}(L,\boldsymbol{p},s)\bigr) &= \mathrm{VCdim}\bigl( \bigl\{(\boldsymbol{x},y) \mapsto \mathrm{sgn}\bigl(f(\boldsymbol{x})-y\bigr) : f\in\mathcal{F}(L,\boldsymbol{p},s)\bigr\} \bigr) \\ &\geq \mathrm{VCdim}\bigl( \bigl\{\boldsymbol{x} \mapsto \mathrm{sgn}\bigl(f(\boldsymbol{x})\bigr) : f\in\mathcal{F}(L,\boldsymbol{p},s)\bigr\} \bigr) \\ &= \mathrm{VCdim}\bigl(\mathrm{sgn}\circ\mathcal{F}(L,\boldsymbol{p},s)\bigr). \end{align}\] Writing \(\widetilde{\boldsymbol{p}} \mathrel{\vcenter{:}}= (p_0,p_1\wedge s,\ldots,p_L\wedge s, p_{L+1})^\top\), we have by [7] that \(\mathcal{F}(L,\boldsymbol{p},s) = \mathcal{F}(L,\widetilde{\boldsymbol{p}},s)\). Define a class of functions \(\mathcal{H} \mathrel{\vcenter{:}}= \bigl\{(\boldsymbol{x},y) \mapsto \mathrm{sgn}\bigl(f(\boldsymbol{x}) - y\bigr) : f\in\mathcal{F}(L,\widetilde{\boldsymbol{p}},s),\, \gamma\in\mathbb{R}\bigr\}\) from \(\mathbb{R}^{p_0} \times\mathbb{R}\) to \(\mathbb{R}\). Then \(\mathrm{Pdim}\bigl(\mathcal{F}(L,\boldsymbol{p},s)\bigr) = \mathrm{VCdim}(\mathcal{H})\), so it suffices to upper bound \(m\mathrel{\vcenter{:}}= \mathrm{VCdim}(\mathcal{H})\). If \(m < s\), then part (a) of the proposition follows since the right-hand side is at least \(s\). Therefore, we may assume without loss of generality that \(m \geq s\). Suppose that \((\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_m,y_m)\in\mathbb{R}^{p_0}\times \mathbb{R}\) are shattered by \(\mathcal{H}\). Let \(\widetilde{V}\mathrel{\vcenter{:}}= \sum_{\ell=1}^{L+1} \widetilde{p}_\ell (\widetilde{p}_{\ell-1}+1)\) denote the total number of parameters of a neural network in \(\mathcal{F}(L,\widetilde{\boldsymbol{p}},s)\). For \(\boldsymbol{x}\in\mathbb{R}^{p_0}\) and \(\boldsymbol{\theta} \in \{\boldsymbol{\theta}'\in\mathbb{R}^{\widetilde{V}} : \|\boldsymbol{\theta}'\|_0 \leq s\} \eqqcolon \mathbb{B}_0^{\widetilde{V}}(s)\), let \(g(\boldsymbol{x},\boldsymbol{\theta}) \mathrel{\vcenter{:}}= f(\boldsymbol{x})\) when \(f\in\mathcal{F}(L,\widetilde{\boldsymbol{p}},s)\) satisfies \(\boldsymbol{\Theta}(\boldsymbol{f}) = \boldsymbol{\theta}\). In other words, \(g(\cdot,\boldsymbol{\theta})\) is the neural network in \(\mathcal{F}(L,\widetilde{\boldsymbol{p}},s)\) with parameter vector \(\boldsymbol{\theta}\), so \(\mathcal{F}(L,\widetilde{\boldsymbol{p}},s) = \bigl\{g(\cdot,\boldsymbol{\theta}) : \boldsymbol{\theta} \in \mathbb{B}_0^{\widetilde{V}}(s)\bigr\}\). We partition \(\mathbb{B}_0^{\widetilde{V}}(s)\) into sets \(B_1,\ldots,B_{\binom{\widetilde{V}}{s}}\), where the elements in each set \(B_i\) are all supported on the same set of cardinality \(s\). Then, by definition of \(m\), \[\begin{align} 2^m &= \Bigl| \Bigl\{ \Bigl(\mathrm{sgn}\bigl(g(\boldsymbol{x}_1,\boldsymbol{\theta})- y_1\bigr), \ldots, \mathrm{sgn}\bigl(g(\boldsymbol{x}_m,\boldsymbol{\theta})- y_m\bigr)\Bigr)^\top : \boldsymbol{\theta}\in \mathbb{B}_0^{\widetilde{V}}(s)\Bigr\} \Bigr|\nonumber\\ &\leq \sum_{i=1}^{\binom{\widetilde{V}}{s}} \Bigl| \Bigl\{ \Bigl(\mathrm{sgn}\bigl(g(\boldsymbol{x}_1,\boldsymbol{\theta})- y_1\bigr), \ldots, \mathrm{sgn}\bigl(g(\boldsymbol{x}_m,\boldsymbol{\theta})- y_m\bigr)\Bigr)^\top : \boldsymbol{\theta}\in B_i\Bigr\} \Bigr| \eqqcolon \sum_{i=1}^{\binom{\widetilde{V}}{s}} K_i. \label{eq:VC-bound-K-decomposition} \end{align}\tag{3}\] We will prove upper bounds for \(K_1,\ldots,K_{\binom{\widetilde{V}}{s}}\), which then imply an upper bound on \(m\). To this end, without loss of generality, we upper bound \(K_1\). For \(\ell\in[L+1]\), \(\boldsymbol{x} \in \mathbb{R}^{p_0}\) and \(\boldsymbol{\theta} \in B_1\), define \(\boldsymbol{g}^{(\ell)}(\boldsymbol{x}, \boldsymbol{\theta}) \mathrel{\vcenter{:}}= \boldsymbol{A}_{\ell}\circ \boldsymbol{\sigma} \circ\cdots\circ \boldsymbol{\sigma}\circ \boldsymbol{A}_1(\boldsymbol{x})\), where \(\boldsymbol{A}_1,\ldots,\boldsymbol{A}_{L+1}\) are defined analogously to 1 (but with each \(p_\ell\) there replaced with \(\widetilde{p}_\ell\)) with weight matrices and bias vectors given by relevant components of \(\boldsymbol{\theta}\). For \(\ell \in [L+1]\) and \(u\in[\widetilde{p}_{\ell}]\), let \(g^{(\ell)}_u\) be the \(u\)th coordinate function of \(\boldsymbol{g}^{(\ell)}\), let \(\mathcal{U}_\ell\mathrel{\vcenter{:}}= \{u\in[\widetilde{p}_\ell] : g^{(\ell)}_u(\cdot,\boldsymbol{\theta}) \neq 0 \text{ for some } \boldsymbol{\theta} \in B_1\}\) be the coordinates of active neurons in the \(\ell\)th layer, and let \(k_\ell \mathrel{\vcenter{:}}= |\mathcal{U}_\ell|\). If \(k_\ell = 0\) for some \(\ell\in[L+1]\), then \(g(\cdot,\boldsymbol{\theta}) = 0\) for all \(\boldsymbol{\theta} \in B_1\), so \(K_1=1\). Now assume that \(k_\ell \geq 1\) for all \(\ell\in[L+1]\). We will construct a finite sequence of partitions \(\mathcal{P}_1,\ldots,\mathcal{P}_{L+1}\) of \(B_1\), each refining the previous one, satisfying the following properties:

\(N_\ell \mathrel{\vcenter{:}}= |\mathcal{P}_\ell|\) satisfies \(N_1 = 1\) and for \(\ell\in [L]\), we have \[\begin{align} \frac{N_{\ell+1}}{N_{\ell}} \leq 2\biggl( \frac{2em \ell k_{\ell}}{s} \biggr)^s \eqqcolon \phi_{\ell}. \end{align}\]
\(\boldsymbol{\theta} \mapsto \boldsymbol{g}^{(\ell)}(\boldsymbol{x}_j, \boldsymbol{\theta})\) is a polynomial of degree at most \(\ell\) on \(P_{\ell}\), for each \(j\in[m]\), \(\ell\in[L+1]\) and \(P_\ell \in \mathcal{P}_\ell\).

We start by defining \(\mathcal{P}_1 \mathrel{\vcenter{:}}= \{B_1\}\). By the definition of \(\boldsymbol{A}_1\) in 1 , we have that \(\boldsymbol{\theta} \mapsto \boldsymbol{g}^{(1)}(\boldsymbol{x}_j, \boldsymbol{\theta}) = \boldsymbol{A}_1(\boldsymbol{x}_j)\) is linear on \(B_1\). Now suppose that we have constructed \(\mathcal{P}_1,\ldots,\mathcal{P}_{\ell}\) for some \(\ell \in [L]\) satisfying both Properties [property1] and [property2]. By the induction hypothesis, \(\mathcal{P}_{\ell} = \{P_{\ell,1},\ldots,P_{\ell,N_{\ell}}\}\) is such that, for each \(r\in[N_\ell]\), \(j\in[m]\) and \(u\in\mathcal{U}_{\ell}\), the map \(\boldsymbol{\theta} \mapsto g^{(\ell)}_u(\boldsymbol{x}_j,\boldsymbol{\theta})\) is a polynomial of degree at most \(\ell\) on \(P_{\ell,r}\), depending on at most \(s\) coordinates of \(\boldsymbol{\theta}\). Then, for a fixed \(r\in[N_\ell]\), by [71], since \(m \geq s\), we have \[\begin{align} \Bigl|\Bigl\{\Bigl( \mathrm{sgn}\bigl(g^{(\ell)}_u&(\boldsymbol{x}_j,\boldsymbol{\theta})\bigr) : u\in[\widetilde{p}_{\ell}],\, j\in[m] \Bigr) : \boldsymbol{\theta}\in P_{\ell,r}\Bigr\} \Bigr|\\ & = \Bigl|\Bigl\{\Bigl( \mathrm{sgn}\bigl(g^{(\ell)}_u(\boldsymbol{x}_j,\boldsymbol{\theta})\bigr) : u\in \mathcal{U}_{\ell},\, j\in[m] \Bigr) : \boldsymbol{\theta}\in P_{\ell,r}\Bigr\} \Bigr| \leq \phi_{\ell}. \end{align}\] Therefore, for each \(r\in[N_\ell]\), we can partition \(P_{\ell,r}\) into regions \(R_{r,1},\ldots,R_{r,\phi_{\ell}}\) such that for each \(t \in [\phi_{\ell}]\), the map \(\boldsymbol{\theta} \mapsto \Bigl( \mathrm{sgn}\bigl(g_u^{(\ell)}(\boldsymbol{x}_j,\boldsymbol{\theta})\bigr) : u\in[\widetilde{p}_{\ell}],\, j\in[m] \Bigr)\) is constant on \(R_{r,t}\). We then define \(\mathcal{P}_{\ell+1} \mathrel{\vcenter{:}}= \bigl\{ R_{r,t} : r\in[N_\ell],\, t\in[\phi_{\ell}] \bigr\}\). By construction, \(\mathcal{P}_{\ell+1}\) satisfies Property [property1]. Moreover, writing \(\boldsymbol{\xi}_{\boldsymbol{x}_j,\boldsymbol{\theta}} \mathrel{\vcenter{:}}= \Bigl(\mathrm{sgn}\bigl(g_u^{(\ell)}(\boldsymbol{x}_j,\boldsymbol{\theta})\bigr):u\in [\widetilde{p}_{\ell}]\Bigr)^\top \in\{0,1\}^{\widetilde{p}_{\ell}}\), we have \[\boldsymbol{g}^{(\ell+1)}(\boldsymbol{x}_j,\boldsymbol{\theta}) = \boldsymbol{A}_{\ell+1}\circ\boldsymbol{\sigma}\circ \boldsymbol{g}^{(\ell)}(\boldsymbol{x}_j,\boldsymbol{\theta}) = \boldsymbol{A}_{\ell+1}\bigl(\mathrm{diag}(\boldsymbol{\xi}_{\boldsymbol{x}_j,\boldsymbol{\theta}}) \boldsymbol{g}^{(\ell)}(\boldsymbol{x}_j,\boldsymbol{\theta}) \bigr).\] Since for each \(j\in[m]\), \(r\in[N_\ell]\) and \(t\in[\phi_{\ell}]\), the sign vector \(\boldsymbol{\xi}_{\boldsymbol{x}_j,\boldsymbol{\theta}}\) is constant for all \(\boldsymbol{\theta}\in R_{r,t}\), the map \(\boldsymbol{\theta}\mapsto \boldsymbol{g}^{(\ell+1)}(\boldsymbol{x}_j,\boldsymbol{\theta})\) is a polynomial of degree at most \(\ell+1\) on \(R_{r,t}\), which verifies Property [property2] for \(\ell+1\) and hence completes the induction.

Next, by Property [property2], for each \(j\in[m]\) and \(P_{L} \in \mathcal{P}_L\), we have that \(\boldsymbol{\theta} \mapsto g(\boldsymbol{x}_j,\boldsymbol{\theta}) - y_j = \boldsymbol{g}^{(L+1)}(\boldsymbol{x}_j,\boldsymbol{\theta}) - y_j\) is a polynomial of degree at most \(L\) on \(P_L\), depending on at most \(s\) coordinates of \(\boldsymbol{\theta}\). Thus, by [71] again, \[\begin{align} \Bigl| \Bigl\{ \Bigl(\mathrm{sgn}\bigl(g(\boldsymbol{x}_1,\boldsymbol{\theta}) - y_1\bigr), \ldots, \mathrm{sgn}\bigl(g(\boldsymbol{x}_m,\boldsymbol{\theta}) - y_m\bigr)\Bigr)^\top : \boldsymbol{\theta}\in P_L \Bigr\} \Bigr| \leq 2\biggl( \frac{2emL}{s} \biggr)^{s}. \label{eq:VC-bound-ineq-1} \end{align}\tag{4}\] By Property [property1], we also have \[\begin{align} |\mathcal{P}_L| \leq 2^L\prod_{\ell=1}^L \biggl( \frac{2em\ell k_{\ell}}{s} \biggr)^s. \label{eq:VC-bound-ineq-2} \end{align}\tag{5}\] Combining 4 and 5 yields that \[\begin{align} K_1 &\leq 2^{L+1}\biggl( \frac{2emL}{s} \biggr)^{s} \prod_{\ell=1}^{L} \biggl( \frac{2em \ell k_{\ell}}{s} \biggr)^s = 2^{L+1} \biggl( \frac{2em}{s} \biggr)^{s(L+1)} \biggl(\prod_{\ell=1}^L \ell k_\ell\biggr)^s\\ &\leq 2^{L+1} \biggl( \frac{2em}{s} \biggr)^{s(L+1)} \biggl(\frac{1}{L}\sum_{\ell=1}^L \ell k_\ell\biggr)^{sL}\leq 2^{L+1} (2em)^{s(L+1)}, \end{align}\] where the second inequality is an application of the AM–GM inequality, and the final bound uses the fact that \(\sum_{\ell=1}^L k_\ell \leq s\). Therefore, by 3 , we deduce that \[\begin{align} 2^m \leq \binom{\widetilde{V}}{s} \cdot 2^{L+1} (2em)^{s(L+1)} &\leq \bigl( 4em \widetilde{V}^{1/(L+1)}\bigr)^{s(L+1)}. \end{align}\] By Lemma 7, since \(4e\widetilde{V}^{1/(L+1)} \geq 4\), we have \[\begin{align} m &\leq 2s(L+1)\log_2\bigl(4es(L+1)\widetilde{V}^{1/(L+1)}\bigr) \\ &\leq 2s(L+1)\log_2\bigl(8es^3(2p_0)^{1/(L+1)}\bigr) \leq 6s(L+1)\log_2(3s) + 2s\log_2(2p_0), \end{align}\] where the second inequality follows since \(L+1 \leq s\) by our assumption that \(k_\ell \geq 1\) for all \(\ell\in[L+1]\) and \[\begin{align} \widetilde{V} \leq (L-1)s(s+1) + (p_0+1)s + s + 1 \leq 2(L+1)s^2 + p_0s \leq 2p_0(2s)^{L+1}. \end{align}\]

(b) If \((\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_m,y_m) \in \mathbb{R}^{p_0} \times \mathbb{R}\) are shattered by \(\bigl\{(\boldsymbol{x},y) \mapsto \mathrm{sgn}\bigl(T_B f(\boldsymbol{x})-y\bigr) : f\in\mathcal{F}(L,\boldsymbol{p},s)\bigr\}\), then we must have \(y_j\in[-B,B)\) for all \(j\in[m]\). Therefore, \((\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_m,y_m)\) are also shattered by \(\bigl\{(\boldsymbol{x},y) \mapsto \mathrm{sgn}\bigl(f(\boldsymbol{x})-y\bigr) : f\in\mathcal{F}(L,\boldsymbol{p},s)\bigr\}\), so \(\mathrm{Pdim}\bigl(T_B \circ \mathcal{F}(L,\boldsymbol{p},s)\bigr) \leq \mathrm{Pdim}\bigl(\mathcal{F}(L,\boldsymbol{p},s)\bigr)\). Then, by [72], since \(\mathrm{Pdim}\bigl(T_B \circ \mathcal{F}(L,\boldsymbol{p},s)\bigr) \geq 2\), we have \[\begin{align} \mathcal{N}\bigl( \epsilon, T_B \circ \mathcal{F}(L,\boldsymbol{p},s), \|\cdot\|_{L_q(\mu)} \bigr) &\leq 3\biggl\{ \frac{2e(2B)^q}{\epsilon^q} \log \biggl(\frac{3e(2B)^q}{\epsilon^q}\biggr) \biggr\}^{\mathrm{Pdim}(T_B \circ \mathcal{F}(L,\boldsymbol{p},s))}\\ &\leq \biggl(\frac{10B}{\epsilon}\biggr)^{2q\cdot\mathrm{Pdim}(\mathcal{F}(L,\boldsymbol{p},s))}. \end{align}\] Taking logarithms and applying part (a) yields the desired result. ◻

8 Proof of Proposition 1 ↩︎

Proof of Proposition 1. For \(i=0,1,\ldots,n\), let \(\widetilde{\boldsymbol{Z}}_i \mathrel{\vcenter{:}}= (\boldsymbol{Z}_i,\boldsymbol{\Omega}_i)\) and let \(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_i) \mathrel{\vcenter{:}}= \mathbb{E}(T_{B_n}Y_i \,|\, \widetilde{\boldsymbol{Z}}_i)\). Then \[\begin{align} \mathbb{E}\bigl\{ R(T_{B_n}\widetilde{f}) - R(f^{\star}) \bigr\} &= \mathbb{E}\bigl\{ \bigl(T_{B_n}\widetilde{f}(\widetilde{\boldsymbol{Z}}_0) - Y_0\bigr)^2 - \bigl(T_{B_n}\widetilde{f}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 \bigr\}\\ &\qquad + \mathbb{E}\bigl\{ \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 - \bigl(f^{\star}(\widetilde{\boldsymbol{Z}}_0) - Y_0\bigr)^2 \bigr\}\\ &\qquad + \mathbb{E}\biggl[ \bigl(T_{B_n}\widetilde{f}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2\\ &\qquad\quad -\frac{2}{n} \sum_{i=1}^n \Bigl\{ \bigl(T_{B_n}\widetilde{f}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 \Bigr\}\biggr] \\ &\qquad + \mathbb{E}\biggl[ \frac{2}{n} \sum_{i=1}^n \Bigl\{ \bigl(T_{B_n}\widetilde{f}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 - \bigl(f^{\star}(\widetilde{\boldsymbol{Z}}_i) - Y_i\bigr)^2 \Bigr\} \biggr] \\ &\qquad + \mathbb{E}\biggl[ \frac{2}{n} \sum_{i=1}^n \Bigl\{\bigl(f^{\star}(\widetilde{\boldsymbol{Z}}_i) - Y_i\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2\Bigr\} \biggr]\\ &\eqqcolon E_1 + E_2 + E_3 + E_4 + E_5. \end{align}\]

8.0.0.1 Bounding \(E_1\):

By Lemma 8, \[\begin{align} E_1 \leq \mathbb{E}\bigl\{ Y_0^2 - (T_{B_n}Y_0)^2 \bigr\} + 2B_n\mathbb{E}\bigl\{ |Y_0 - T_{B_n}Y_0| \bigr\} \leq \frac{5\xi^2}{n}. \label{eq:oracle-inequality-E1} \end{align}\tag{6}\]

8.0.0.2 Bounding \(E_2 + E_5\):

Note that \(E_5 = -2E_2\), so by Lemma 8, \[\begin{align} E_2 + E_5 &= \mathbb{E}\bigl\{ \bigl(f^{\star}(\widetilde{\boldsymbol{Z}}_0) - Y_0\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 \bigr\}\nonumber\\ &= \mathbb{E}\bigl\{ \bigl(f^{\star}(\widetilde{\boldsymbol{Z}}_0)\bigr)^2 - \bigl( f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) \bigr)^2 \bigr\} + \mathbb{E}\bigl\{ Y_0^2 - (T_{B_n} Y_0)^2 \bigr\}\nonumber\\ & - 2\mathbb{E}\bigl\{f^{\star}(\widetilde{\boldsymbol{Z}}_0)\cdot Y_0 - f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) \cdot T_{B_n}Y_0\bigr\} \leq \frac{13\xi^2}{n}. \label{eq:oracle-inequality-E243E5} \end{align}\tag{7}\]

8.0.0.3 Bounding \(E_3\):

For \((\boldsymbol{u}_1,\boldsymbol{v}_1),\ldots,(\boldsymbol{u}_n,\boldsymbol{v}_n) \in \mathbb{R}^d\times\mathbb{R}^d\), let \(\mathbb{P}_n\) be their empirical measure and let \[\begin{align} \mathcal{N}_{1,n} \mathrel{\vcenter{:}}= \sup_{(\boldsymbol{u}_i,\boldsymbol{v}_i)_{i=1}^n \in (\mathbb{R}^d\times\mathbb{R}^d)^n} \mathcal{N}\bigl((80B_n n)^{-1},\, T_{B_n}\circ\mathcal{F},\, \|\cdot\|_{L_1(\mathbb{P}_n)}\bigr). \end{align}\] For \(\delta \mathrel{\vcenter{:}}= \frac{24\cdot214 B_n^4 \log(14\mathcal{N}_{1,n})}{n} \geq 1/n\), we have \[\begin{align} E_3 &= \mathbb{E}\biggl[ \mathbb{E}\Bigl\{ \bigl(T_{B_n}\widetilde{f}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 \,\Bigm|\, \mathcal{D} \Bigr\}\nonumber\\ & -\frac{2}{n} \sum_{i=1}^n \Bigl\{ \bigl(T_{B_n}\widetilde{f}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 \Bigr\}\biggr]\nonumber\\ &\leq \mathbb{E}\biggl( \sup_{g\in T_{B_n} \circ \mathcal{F}(L,\boldsymbol{p},s)} \biggl[ \mathbb{E}\Bigl\{ \bigl(g(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 \Bigr\}\nonumber\\ & -\frac{2}{n} \sum_{i=1}^n \Bigl\{ \bigl(g(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 \Bigr\} \biggr] \biggr) \nonumber\\ &\leq \delta + \int_{\delta}^{\infty} \mathbb{P}\biggl( \sup_{g\in T_{B_n} \circ \mathcal{F}(L,\boldsymbol{p},s)} \Bigl[ \mathbb{E}\bigl\{\bigl(g(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_0) - T_{B_n}Y_0\bigr)^2\bigr\} \nonumber\\ & -\frac{2}{n} \sum_{i=1}^n \bigl\{ \bigl(g(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 - \bigl(f^{\star}_{B_n}(\widetilde{\boldsymbol{Z}}_i) - T_{B_n}Y_i\bigr)^2 \bigr\} \Bigr] > t \biggr) \,\mathrm{d}t\nonumber\\ \overset{(i)}&{\leq} \delta + 14\mathcal{N}_{1,n} \int_{\delta}^{\infty} \exp\Bigl( -\frac{nt}{24\cdot 214 B_n^4} \Bigr) \,\mathrm{d}t\nonumber\\ &= \delta + 14\mathcal{N}_{1,n} \cdot \frac{24\cdot 214 B_n^4}{n}\exp\Bigl( -\frac{n\delta}{24\cdot 214 B_n^4} \Bigr)\nonumber\\ &\leq \frac{24\cdot214 B_n^4 \log(14\mathcal{N}_{1,n})}{n} + \frac{24\cdot214B_n^4}{n}\nonumber\\ \overset{(ii)}&{\lesssim} \frac{\xi^4 \log(e\xi) \log^3 n \cdot \bigl(sL\log(es) + s\log(ed)\bigr)}{n}, \label{eq:oracle-inequality-E3} \end{align}\tag{8}\] were \((i)\) uses [72] with \(\epsilon=1/2\) and \(\alpha=\beta=t/2\) therein, and \((ii)\) uses Proposition 4(b).

8.0.0.4 Bounding \(E_4\):

The functions in \(\mathcal{F}\) are parametrised by a subset \(A\) of a Euclidean space, meaning that we can write \(\mathcal{F} = \{f_{\boldsymbol{\theta}}: \boldsymbol{\theta} \in A\}\). Since \(A\) has a countable, dense subset \(\widetilde{A}\) [73] and the map \(\boldsymbol{\theta} \mapsto \widehat{R}_n(f_{\boldsymbol{\theta}})\) is continuous, it follows that \(\inf_{\boldsymbol{\theta} \in A} \widehat{R}_n(f_{\boldsymbol{\theta}}) = \inf_{\boldsymbol{\theta} \in \widetilde{A}} \widehat{R}_n(f_{\boldsymbol{\theta}})\). Thus \(\inf_{f \in \mathcal{F}} \widehat{R}_n(f)\) is measurable, and \[\begin{align} E_4 &\leq \mathbb{E}\biggl[ \frac{2}{n} \sum_{i=1}^n \Bigl\{ \bigl(\widetilde{f}(\widetilde{\boldsymbol{Z}}_i) - Y_i\bigr)^2 - \bigl(f^{\star}(\widetilde{\boldsymbol{Z}}_i) - Y_i\bigr)^2 \Bigr\} \biggr] \nonumber\\ &= 2\mathbb{E}\Bigl\{\widehat R_n(\widetilde{f}) - \inf_{f\in\mathcal{F}}\widehat{R}_n(f) \Bigr\} + 2\mathbb{E} \Bigl\{\inf_{f\in\mathcal{F}}\widehat{R}_n(f) - \widehat{R}_n(f^{\star}) \Bigr\}\nonumber\\ &\leq 2\mathbb{E}\Bigl\{\widehat R_n(\widetilde{f}) - \inf_{f\in\mathcal{F}}\widehat{R}_n(f) \Bigr\} + 2\inf_{f\in\mathcal{F}} \mathbb{E} \bigl\{\widehat{R}_n(f) - \widehat{R}_n(f^{\star}) \bigr\}\nonumber\\ &= 2\mathbb{E}\Bigl\{\widehat R_n(\widetilde{f}) - \inf_{f\in\mathcal{F}}\widehat{R}_n(f) \Bigr\} + 2\inf_{f\in\mathcal{F}} \mathbb{E} \bigl\{\bigl(f(\widetilde{\boldsymbol{Z}_0}) - Y_0\bigr)^2 - \bigl(f^{\star}(\widetilde{\boldsymbol{Z}_0}) - Y_0\bigr)^2 \bigr\}\nonumber\\ &= 2\mathbb{E}\Bigl\{\widehat R_n(\widetilde{f}) - \inf_{f\in\mathcal{F}}\widehat{R}_n(f) \Bigr\} + 2\inf_{f\in\mathcal{F}} \mathbb{E} \bigl\{\bigl(f(\widetilde{\boldsymbol{Z}_0}) - f^{\star}(\widetilde{\boldsymbol{Z}_0})\bigr)^2 \bigr\}. \label{eq:oracle-inequality-E4} \end{align}\tag{9}\] Combining 6 , 7 , 8 and 9 yields the final result. ◻

9 \(\mathcal{F}\)-separability of partitions of \(\mathcal{S}\)↩︎

Proposition 5. Let \(\mathcal{S} \subseteq \{0,1\}^d\) be such that \(|\mathcal{S}| \geq 2\), let \(K\in\{2,\ldots,|\mathcal{S}|\}\) and let \(\{\mathcal{S}_1, \ldots, \mathcal{S}_K\}\) be a partition of \(\mathcal{S}\).

Suppose that there exists \(\mathcal{J} \subseteq [d]\) such that \(\boldsymbol{\omega}, \boldsymbol{\omega}' \in \mathcal{S}\) belong to the same cell of the partition whenever \(\boldsymbol{\omega}_{\mathcal{J}} = \boldsymbol{\omega}'_{\mathcal{J}}\). Let \(\mathcal{S}_{\mathcal{J}} \mathrel{\vcenter{:}}= \{\boldsymbol{\omega}_{\mathcal{J}} : \boldsymbol{\omega} \in \mathcal{S}\} \subseteq \{0,1\}^{|\mathcal{J}|}\). Define \[\begin{gather} p_* \mathrel{\vcenter{:}}= 2\bigl\lceil |\mathcal{S}_{\mathcal{J}}|^{1/2} \bigr\rceil \quad\text{and}\quad \boldsymbol{p} \mathrel{\vcenter{:}}= (d,p_*,p_*,1)^\top \in \mathbb{N}^{4}. \end{gather}\] Then \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is \(\mathcal{F}(2,\boldsymbol{p})\)-separable. In particular, if \(\mathcal{S}_1,\ldots,\mathcal{S}_K\) is an arbitrary partition of \(\mathcal{S}\), then we may take \(\mathcal{J} = [d]\).
Suppose that for each \(k\in[K]\), there exist \(P_k \in \mathbb{N}\) and \((\boldsymbol{v}^{(k)}_{\ell}, b^{(k)}_{\ell})_{\ell \in [P_k]} \in (\mathbb{R}^d \times \mathbb{R})^{P_k}\) such that \(\mathcal{S}_k = \bigl\{\boldsymbol{\omega}\in\mathcal{S}:\boldsymbol{\omega}^\top \boldsymbol{v}^{(k)}_{\ell} \leq b^{(k)}_{\ell} \text{ for all } \ell\in[P_k]\bigr\}\). Define \[\begin{gather} \boldsymbol{p} \mathrel{\vcenter{:}}= \biggl(d,\, 2\sum_{k=1}^K P_k,\, K, 1\biggr)^\top \in \mathbb{N}^4. \end{gather}\] Then \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is \(\mathcal{F}(2,\boldsymbol{p})\)-separable.

Proof. (a) Let \(J \mathrel{\vcenter{:}}= |\mathcal{J}|\). Without loss of generality, suppose that \(\mathcal{J} = [J]\), and let \(\mathcal{S}_{\mathcal{J}} = \{\boldsymbol{u}_1,\ldots,\boldsymbol{u}_{|\mathcal{S}_{\mathcal{J}}|}\}\subseteq \{0,1\}^{J}\). For \(i\in[|\mathcal{S}_{\mathcal{J}}|]\), define \(x_i \mathrel{\vcenter{:}}= \sum_{j=1}^{J} 2^{j-1} u_{ij} \in \mathbb{N}_0\), where \(u_{ij}\) is the \(j\)th coordinate of \(\boldsymbol{u}_i\). Further define \(y_i \mathrel{\vcenter{:}}= k/K\) where \(k\in[K]\) is such that there exists \(\boldsymbol{\omega} \in \mathcal{S}_{k}\) such that \(\boldsymbol{\omega}_{\mathcal{J}} = \boldsymbol{u}_i\); note that \(k\) is uniquely defined by our assumption. By [74] and [NN-enlarging], there exists \(f_1 \in \mathcal{F}\bigl(2,(1,p_*,p_*,1)\bigr)\) such that \(f_1(x_i) = y_i\) for all \(i\in[|\mathcal{S}_{\mathcal{J}}|]\). Thus, by [NN-composition], there exists \(f \in\mathcal{F}(2,\boldsymbol{p})\) such that \[\begin{align} f(\boldsymbol{v}) = f_1\biggl(\sum_{j=1}^J 2^{j-1} v_j\biggr) \end{align}\] for \(\boldsymbol{v} = (v_1,\ldots,v_d)^\top \in \mathbb{R}^d\). For any \(k\in[K]\) and \(\boldsymbol{\omega} = (\omega_1,\ldots,\omega_d)^\top \in \mathcal{S}_k\), there exists \(i \in |\mathcal{S}_{\mathcal{J}}|\) such that \(\boldsymbol{\omega}_{\mathcal{J}} = \boldsymbol{u}_i\). Therefore, \[\begin{align} f(\boldsymbol{\omega}) = f_1\biggl(\sum_{j=1}^J 2^{j-1} \omega_j\biggr) = f_1\biggl(\sum_{j=1}^J 2^{j-1} u_{ij}\biggr) = f_1(x_i) = \frac{k}{K}. \end{align}\] Hence, \(\mathcal{S}_1,\ldots,\mathcal{S}_K\) are \(\mathcal{F}(2,\boldsymbol{p})\)-separable with \(\epsilon = 1/(2K)\).

(b) First define \[\begin{align} \epsilon \mathrel{\vcenter{:}}= \min_{k\in[K]} \min_{\boldsymbol{\omega} \in \mathcal{S} \setminus \mathcal{S}_k} \max_{\ell\in[P_k]} \;\bigl(\boldsymbol{\omega}^\top \boldsymbol{v}^{(k)}_{\ell} - b^{(k)}_{\ell}\bigr). \end{align}\] For each \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S} \setminus \mathcal{S}_k\), we have \(\max_{\ell\in[P_k]} \;\bigl(\boldsymbol{\omega}^\top \boldsymbol{v}^{(k)}_{\ell} - b^{(k)}_{\ell}\bigr) > 0\) by assumption, so \(\epsilon > 0\). For \(k\in[K]\) and \(\ell\in[P_k]\), define \(\phi_{(k,\ell)} \in \mathcal{F}\bigl(1,(d,2,1)\bigr)\) by \[\begin{align} \phi_{(k,\ell)}(\boldsymbol{x}) \mathrel{\vcenter{:}}= \sigma\biggl(-\frac{\boldsymbol{x}^\top \boldsymbol{v}^{(k)}_{\ell} - b^{(k)}_{\ell}}{\epsilon} + 1\biggr) - \sigma\biggl(-\frac{\boldsymbol{x}^\top \boldsymbol{v}^{(k)}_{\ell} - b^{(k)}_{\ell}}{\epsilon}\biggr) \end{align}\] for \(\boldsymbol{x}\in\mathbb{R}^d\). If \(\boldsymbol{x}^\top \boldsymbol{v}^{(k)}_{\ell} - b^{(k)}_{\ell} \leq 0\), then \(\phi_{(k,\ell)}(\boldsymbol{x}) = 1\); if \(\boldsymbol{x}^\top \boldsymbol{v}^{(k)}_{\ell} - b^{(k)}_{\ell} \geq \epsilon\), then \(\phi_{(k,\ell)}(\boldsymbol{x}) = 0\). By [NN-parallelisation], the function \(\boldsymbol{\phi}: \mathbb{R}^d \to \mathbb{R}^{\sum_{k=1}^K P_k}\) defined by \(\boldsymbol{\phi}(\boldsymbol{x}) \mathrel{\vcenter{:}}= \bigl(\phi_{(k,\ell)}(\boldsymbol{x})\bigr)_{k\in[K],\ell\in[P_k]}\) belongs to \(\mathcal{F}\bigl(1,(d,\, 2\sum_{k=1}^K P_k,\, \sum_{k=1}^K P_k)\bigr)\). For \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\), we have \(\sum_{\ell=1}^{P_k} \phi_{(k,\ell)}(\boldsymbol{\omega}) = P_k\), and for all \(k'\neq k\), we have \(\sum_{\ell'=1}^{P_{k'}} \phi_{(k',\ell')}(\boldsymbol{\omega}) \leq P_{k'}-1\) since there exists \(\ell^* \in [P_{k'}]\) such that \(\boldsymbol{\omega}^\top \boldsymbol{v}^{(k')}_{\ell^*} - b^{(k')}_{\ell^*} \geq \epsilon\). Next define \(\psi \in \mathcal{F}\bigl(1,(\sum_{k=1}^K P_k,\, K,\, 1)\bigr)\) by \[\begin{align} \psi(\boldsymbol{u}) \mathrel{\vcenter{:}}= \sum_{k=1}^K k \cdot\sigma\biggl(\sum_{\ell=1}^{P_k} u_{k,\ell} - P_k + 1\biggr) \end{align}\] for \(\boldsymbol{u} = (u_{k,\ell})_{k\in[K], \ell\in[P_k]} \in \mathbb{R}^{\sum_{k=1}^K P_k}\). Then, for \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\), we have \(\psi\bigl(\boldsymbol{\phi}(\boldsymbol{\omega})\bigr) = k\). Finally, \(\psi\circ\boldsymbol{\phi} \in \mathcal{F}(2,\boldsymbol{p})\) by [NN-composition], so \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is \(\mathcal{F}(2,\boldsymbol{p})\)-separable. ◻

10 Approximation theory for neural networks↩︎

The following lemma follows the arguments of [35] and [28], with very minor changes.

::: {#lemma:approximate-holder-functions-[0,1]^d .lemma} Lemma 1. Let \(\beta,\gamma>0\), \(\beta_0 \mathrel{\vcenter{:}}= \lceil\beta\rceil - 1\), \(d\in\mathbb{N}\) and \(g \in \mathcal{H}_d^{\beta}\bigl([0,1]^d,\gamma\bigr)\). For any \(M,N \in \mathbb{N}\), let \[\begin{gather} R \mathrel{\vcenter{:}}= \lfloor N^{1/d} \rfloor^2 \lfloor M^{2/d}\rfloor,\quad L\mathrel{\vcenter{:}}= 12(\beta_0+1)^2(M+2)\lceil \log_2(4M) \rceil,\\ p_* \mathrel{\vcenter{:}}= 30(\beta_0+1)^2 d^{\beta_0+1} (N+1) \lceil\log_2(8N)\rceil \quad\text{and}\quad \boldsymbol{p} \mathrel{\vcenter{:}}= (d,p_*,\ldots,p_*,1)^\top \in \mathbb{N}^{L+2}. \end{gather}\] For \(\delta > 0\), let \[\begin{align} \Gamma\bigl( [0,1]^d, R, \delta \bigr) \mathrel{\vcenter{:}}= \bigcup_{j=1}^d \biggl\{ \boldsymbol{x} = (x_1,\ldots,x_d)^\top &\in [0,1]^d : x_j \in \bigcup_{r=1}^{R-1} \biggl( \frac{r}{R} - \delta,\; \frac{r}{R} \biggr) \biggr\}. \end{align}\] Then, for any \(\delta \in \bigl(0, \frac{1}{3R}\bigr]\), there exists \(f\in\mathcal{F}(L,\boldsymbol{p})\) such that \(|f(\boldsymbol{x})| \leq \gamma\) for all \(\boldsymbol{x} \in \mathbb{R}^d\), and \[\begin{align} |f(\boldsymbol{x}) - g(\boldsymbol{x})| \leq 9\gamma (\beta_0+3)^2 8^{\beta} d^{\beta_0+\beta/2} (NM)^{-2\beta/d}, \end{align}\] for all \(\boldsymbol{x} \in [0,1]^d \setminus \Gamma\bigl( [0,1]^d, R, \delta \bigr)\). :::

Proof. Step 1 (discretisation): By [35], there exists \(\phi_1 \in \mathcal{F}\bigl(4M+5, (1, p_{*1}, \ldots, p_{*1}, 1) \bigr)\), where \(p_{*1} \mathrel{\vcenter{:}}= 4\lfloor N^{1/d} \rfloor +3\) such that \[\begin{align} \phi_1(x) = \frac{r}{R} \quad\text{if } x\in \biggl[ \frac{r}{R},\; \frac{r+1}{R} - \delta \cdot \mathbb{1}_{\{r \leq R-2\}} \biggr] \text{ for } r\in \{0,1,\ldots,R-1\}. \end{align}\] For \(\boldsymbol{v} = (v_1,\ldots,v_d)^\top \in \{0,1,\ldots,R-1\}^d\), define \[\begin{align} Q_{\boldsymbol{v}} \mathrel{\vcenter{:}}= \biggl\{\boldsymbol{x} = (x_1,\ldots,x_d)^\top \in [0,1]^d : x_j \in \biggl[ \frac{v_j}{R},\; \frac{v_j+1}{R} - \delta\cdot \mathbb{1}_{\{v_j \leq R-2\}} \biggr] \text{ for all } j\in[d]\biggr\}, \end{align}\] so that \([0,1]^d \setminus \Gamma\bigl( [0,1]^d, R, \delta \bigr) = \bigcup_{\boldsymbol{v} \in \{0,\ldots,R-1\}^d} Q_{\boldsymbol{v}}\). By Property [NN-parallelisation], the function \(\boldsymbol{\phi}_{\mathrm{dsc}}:\mathbb{R}^d \rightarrow \mathbb{R}^d\) given by \(\boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) \mathrel{\vcenter{:}}= \bigl(\phi_1(x_1), \ldots, \phi_1(x_d)\bigr)^\top\) for \(\boldsymbol{x} = (x_1,\ldots,x_d)^\top\) belongs to \(\mathcal{F}\bigl(4M+5, (d, dp_{*1}, \ldots, dp_{*1}, d) \bigr)\). Thus, \[\begin{align} \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) = \biggl( \frac{v_1}{R}, \ldots, \frac{v_d}{R} \biggr)^\top \quad\text{for all } \boldsymbol{x} \in Q_{\boldsymbol{v}},\, \boldsymbol{v} \in \{0,1,\ldots,R-1\}^d. \end{align}\]

Step 2 (approximation of Taylor coefficients): The function \(\phi_2:\mathbb{R}^d \rightarrow \mathbb{R}\) given by \(\phi_2(\boldsymbol{x}) \mathrel{\vcenter{:}}= \sum_{j=1}^d R^j \phi_1(x_j)\) is a composition of \(\boldsymbol{\phi}_{\mathrm{dsc}}\) with a projection along the vector \((R,R^2,\ldots,R^d)^\top\) and hence by [NN-composition], \(\phi_2 \in \mathcal{F}\bigl(4M+5, (d, dp_{*1}, \ldots, dp_{*1}, 1) \bigr)\). Moreover, for all \(\boldsymbol{v} \in \{0,1,\ldots,R-1\}^d\) and \(\boldsymbol{x} \in Q_{\boldsymbol{v}}\), we have \[\begin{align} \phi_2(\boldsymbol{x}) = \sum_{j=1}^d R^{j-1}v_j \eqqcolon I_{\boldsymbol{v}} \in \{0,1,\ldots,R^d-1\}. \label{eq:phi953-property} \end{align}\tag{10}\] For each \(\boldsymbol{\alpha} \in \mathbb{N}_0^d\) with \(\|\boldsymbol{\alpha}\|_1 \leq \beta_0\) we have \(\frac{\partial^{\boldsymbol{\alpha}} g(\boldsymbol{x}) + \gamma}{2\gamma} \in [0,1]\) for \(\boldsymbol{x} \in [0,1]^d\). Hence, since \(R^d \leq N^2M^2\) and since \(\boldsymbol{v} \mapsto I_{\boldsymbol{v}}\) is a bijection, by [35] there exists \(\psi_{\boldsymbol{\alpha}}^\circ \in \mathcal{F}\bigl(5(M+2)\lceil\log_2(4M)\rceil, (1,p_{*2},\ldots,p_{*2},1)\bigr)\), where \(p_{*2} \mathrel{\vcenter{:}}= 16(\beta_0+1)(N+1) \lceil\log_2(8N)\rceil\), such that \[\begin{align} \biggl| \psi_{\boldsymbol{\alpha}}^\circ(I_{\boldsymbol{v}}) - \frac{\partial^{\boldsymbol{\alpha}} g(\boldsymbol{v}/R) + \gamma}{2\gamma} \biggr| \leq (NM)^{-2(\beta_0+1)} \quad\text{for all } \boldsymbol{v} \in \{0,1,\ldots,R-1\}^d. \label{eq:psi94circ95alpha-property} \end{align}\tag{11}\] Now \[dp_{*1} \vee p_{*2} \leq 16d(\beta_0+1)(N+1)\lceil\log_2(8N)\rceil \eqqcolon p_{*3}\] and \[4M+5+5(M+2)\lceil\log_2(4M)\rceil \leq 7(M+2)\lceil\log_2(4M)\rceil \eqqcolon L_0\] Hence, by Properties [NN-enlarging], [NN-composition] and [NN-padding], there exists \(\psi_{\boldsymbol{\alpha}} \in \mathcal{F}\bigl(L_0,\, (d,p_{*3},\ldots,p_{*3},1)\bigr)\) such that \(\psi_{\boldsymbol{\alpha}}(\boldsymbol{x}) = 2\psi_{\boldsymbol{\alpha}}^\circ\bigl(\phi_2(\boldsymbol{x})\bigr) - 1 \in [-1,1]\) for all \(\boldsymbol{x} \in [0,1]^d\). By 10 and 11 , we deduce that for all \(\boldsymbol{v} \in \{0,1,\ldots,R-1\}^d\) and \(\boldsymbol{x} \in Q_{\boldsymbol{v}}\), we have \[\begin{align} \biggl| \psi_{\boldsymbol{\alpha}}(\boldsymbol{x}) - \frac{1}{\gamma} \cdot \partial^{\boldsymbol{\alpha}} g\bigl(\boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr) \biggr| \leq 2(NM)^{-2(\beta_0+1)}. \label{eq:psi95alpha-property} \end{align}\tag{12}\]

Step 3 (local Taylor expansion): By [35], there exists \(\phi_{\times} \in \mathcal{F}\bigl(2(\beta_0+1)(M+1),\, (1,9(N+1)+1,\ldots,9(N+1)+1,1)\bigr)\) such that for all \(x,y\in[-1,1.1]\), we have \[\begin{align} |\phi_{\times}(x,y) - xy| \leq 27(N+1)^{-2(\beta_0+1)(M+1)}. \label{eq:phi95times-property} \end{align}\tag{13}\] Moreover, by [35], for \(\boldsymbol{\alpha}\in\mathbb{N}_0^d\) with \(\|\boldsymbol{\alpha}\|_1 \leq \beta_0\), there exists \(\mathrm{Poly}_{\boldsymbol{\alpha}} \in \mathcal{F}\bigl(7(\beta_0+1)^2M,\, (d,9(N+1)+\beta_0,\ldots,9(N+1)+\beta_0,1)\bigr)\) such that \[\begin{align} |\mathrm{Poly}_{\boldsymbol{\alpha}}(\boldsymbol{x}) - \boldsymbol{x}^{\boldsymbol{\alpha}}| \leq 9(\beta_0+1)(N+1)^{-7(\beta_0+1)M}, \label{eq:poly95alpha-property} \end{align}\tag{14}\] for all \(\boldsymbol{x} \in [0,1]^d\). Moreover, since \(9(\beta_0+1)(N+1)^{-7(\beta_0+1)M} \leq 9(\beta_0+1)2^{-7(\beta_0+1)} < 0.1\), we have \(\mathrm{Poly}_{\boldsymbol{\alpha}}(\boldsymbol{x}) \in [-1,1.1]\) for all \(\boldsymbol{x}\in[0,1]^d\). Now define \(f^\circ:[0,1]^d \rightarrow \mathbb{R}\) by \[\begin{align} f^\circ(\boldsymbol{x}) \mathrel{\vcenter{:}}= \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\gamma}{\boldsymbol{\alpha}!} \cdot \phi_{\times} \Bigl(\psi_{\boldsymbol{\alpha}}(\boldsymbol{x}),\, \mathrm{Poly}_{\boldsymbol{\alpha}}\bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) \bigr)\Bigr). \end{align}\] Since \(\bigl|\{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0\}\bigr| = \binom{d+\beta_0}{\beta_0} \leq (\beta_0+1)d^{\beta_0}\), we have by Properties [NN-enlarging]–[NN-parallelisation] that \(f^\circ \in \mathcal{F}(L-1,\boldsymbol{p}^\circ)\) where \(\boldsymbol{p}^\circ \mathrel{\vcenter{:}}= (d,p_*,\ldots,p_*,1)^\top \in \mathbb{N}^{L+1}\). Moreover, for \(\boldsymbol{v} \in \{0,\ldots,R-1\}^d\) and \(\boldsymbol{x} \in Q_{\boldsymbol{v}}\), we have \[\begin{align} &\biggl|f^\circ(\boldsymbol{x}) - \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\partial^{\boldsymbol{\alpha}}g\bigl(\boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr)}{\boldsymbol{\alpha}!} \bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr)^{\boldsymbol{\alpha}} \biggr| \nonumber\\ &\leq \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\gamma}{\boldsymbol{\alpha}!} \cdot \biggl| \phi_{\times} \Bigl(\psi_{\boldsymbol{\alpha}}(\boldsymbol{x}),\, \mathrm{Poly}_{\boldsymbol{\alpha}}\bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) \bigr)\Bigr) - \psi_{\boldsymbol{\alpha}}(\boldsymbol{x}) \cdot \mathrm{Poly}_{\boldsymbol{\alpha}}\bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) \bigr) \biggr| \nonumber\\ &\qquad + \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\gamma}{\boldsymbol{\alpha}!} \cdot \biggl| \psi_{\boldsymbol{\alpha}}(\boldsymbol{x}) - \frac{1}{\gamma}\cdot \partial^{\boldsymbol{\alpha}}g\bigl(\boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr) \biggr| \cdot \mathrm{Poly}_{\boldsymbol{\alpha}}\bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) \bigr) \nonumber\\ &\qquad + \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\partial^{\boldsymbol{\alpha}}g\bigl(\boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr)}{\boldsymbol{\alpha}!} \Bigl| \mathrm{Poly}_{\boldsymbol{\alpha}}\bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) \bigr) - \bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x}) \bigr)^{\boldsymbol{\alpha}} \Bigr| \nonumber\\ &\leq \gamma(\beta_0+1)d^{\beta_0}\bigl\{ 27 (N+1)^{-2(\beta_0+1)(M+1)} + 3(NM)^{-2(\beta_0+1)} + 9(\beta_0+1)(N+1)^{-7(\beta_0+1)M} \bigr\} \nonumber\\ &\leq \gamma(\beta_0+1)(9\beta_0+39)d^{\beta_0}(NM)^{-2(\beta_0+1)}, \label{eq:f-property} \end{align}\tag{15}\] where the second inequality follows from 13 , 12 and 14 . Therefore, we deduce that, for \(\boldsymbol{v} \in \{0,\ldots,R-1\}^d\) and \(\boldsymbol{x} \in Q_{\boldsymbol{v}}\), \[\begin{align} |f^\circ(\boldsymbol{x}) - g(\boldsymbol{x})| &\leq \biggl|f^\circ(\boldsymbol{x}) - \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\partial^{\boldsymbol{\alpha}}g\bigl(\boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr)}{\boldsymbol{\alpha}!} \bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr)^{\boldsymbol{\alpha}} \biggr| \nonumber\\ &\qquad + \biggl|g(\boldsymbol{x}) - \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\partial^{\boldsymbol{\alpha}}g\bigl(\boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr)}{\boldsymbol{\alpha}!} \bigl(\boldsymbol{x} - \boldsymbol{\phi}_{\mathrm{dsc}}(\boldsymbol{x})\bigr)^{\boldsymbol{\alpha}} \biggr| \nonumber\\ &\leq \gamma(\beta_0+1)(9\beta_0+39)d^{\beta_0}(NM)^{-2(\beta_0+1)} + \gamma d^{\beta_0}(\sqrt{d}/R)^{\beta} \nonumber\\ &\leq \gamma(\beta_0+1)(9\beta_0+39)d^{\beta_0}(NM)^{-2(\beta_0+1)} + \gamma d^{\beta_0+\beta/2} 8^{\beta}(NM)^{-2\beta/d} \nonumber\\ &\leq 9\gamma (\beta_0+3)^2 8^{\beta} d^{\beta_0+\beta/2} (NM)^{-2\beta/d}, \end{align}\] where the second inequality follows from 15 and Lemma 9, and the third inequality follows since \(R \geq \frac{1}{8}(NM)^{2/d}\). Finally, we define \(f:\mathbb{R}^d \rightarrow [-\gamma,\gamma]\) by \[\begin{align} f(\boldsymbol{x}) \mathrel{\vcenter{:}}= \sigma\bigl(f^\circ(\boldsymbol{x}) + \gamma\bigr) - \sigma\bigl(f^\circ(\boldsymbol{x}) - \gamma\bigr) - \gamma = T_{\gamma}f^\circ(\boldsymbol{x}). \end{align}\] By [NN-enlarging] and [NN-composition], we have \(f\in\mathcal{F}(L,\boldsymbol{p})\). Moreover, since \(g(\boldsymbol{x}) \in [-\gamma,\gamma]\) for all \(\boldsymbol{x} \in [0,1]^d\), we have \(|f(\boldsymbol{x}) - g(\boldsymbol{x})| \leq |f^\circ(\boldsymbol{x}) - g(\boldsymbol{x})| \leq 9\gamma (\beta_0+3)^2 8^{\beta} d^{\beta_0+\beta/2} (NM)^{-2\beta/d}\) for \(\boldsymbol{v} \in \{0,\ldots,R-1\}^d\) and \(\boldsymbol{x} \in Q_{\boldsymbol{v}}\). ◻

Our next lemma quantifies the extent to which a Hölder function on a bounded hypercube that depends only on a subset of the variables can be approximated by a neural network once we excise a finite set of strips in each coordinate.

::: {#lemma:approximate-Holder-functions-[a,c]^d .lemma} Lemma 2. Let \(-\infty < a < c < \infty\), \(\beta,\gamma>0\), \(\beta_0 \mathrel{\vcenter{:}}= \lceil \beta \rceil - 1\), \(d\in\mathbb{N}\), \(t\in[d]\cup\{0\}\) and \(g\in\mathcal{H}_t^{\beta}\bigl([a,c]^d,\gamma\bigr)\). For any \(M,N\in\mathbb{N}\), let \[\begin{gather} R\mathrel{\vcenter{:}}= \lfloor N^{1/t} \rfloor^2 \lfloor M^{2/t} \rfloor,\quad L\mathrel{\vcenter{:}}= 12(\beta_0+1)^2(M+2)\lceil \log_2(4M) \rceil,\\ p_* \mathrel{\vcenter{:}}= 30(\beta_0+1)^2 t^{\beta_0+1} (N+1) \lceil\log_2(8N)\rceil \vee 1 \quad\text{and}\quad \boldsymbol{p} \mathrel{\vcenter{:}}= (d,p_*,\ldots,p_*,1)^\top \in \mathbb{N}^{L+2}. \end{gather}\] Then, for any \(\delta \in \bigl(0, \frac{1}{3R}\bigr]\), there exists \(f\in\mathcal{F}(L,\boldsymbol{p})\) such that \(|f(\boldsymbol{x})| \leq \gamma \vee (c-a)^{\beta_0}\gamma\) for all \(\boldsymbol{x} \in \mathbb{R}^d\), and \[\begin{align} |f(\boldsymbol{x}) - g(\boldsymbol{x})| \leq 9\bigl(1 \vee (c-a)^{\beta_0}\bigr)\gamma (\beta_0+3)^2 8^{\beta} t^{\beta_0+\beta/2} (NM)^{-2\beta/t}, \end{align}\] for all \(\boldsymbol{x} \in [a,c]^d \setminus \Gamma\bigl( [a,c]^d, R, \delta \bigr)\), where \[\begin{align} \Gamma\bigl( [a,c]^d, R, \delta \bigr) \mathrel{\vcenter{:}}= \bigcup_{j=1}^d \biggl\{ \boldsymbol{x} = (x_1,\ldots,x_d)^\top &\in [a,c]^d : \frac{x_j-a}{c-a} \in \bigcup_{r=1}^{R-1} \biggl( \frac{r}{R} - \delta,\; \frac{r}{R} \biggr) \biggr\} \end{align}\] if \(t \in [d]\), and \(\Gamma\bigl( [a,c]^d, R, \delta \bigr) \mathrel{\vcenter{:}}= \emptyset\) if \(t=0\). :::

Proof. In the case where \(t=0\), the function \(g\) is constant, so belongs to \(\mathcal{F}(L,\boldsymbol{p})\) and we have zero approximation error. We next consider the case where \(t=d\). Define \(h:[0,1]^d \to \mathbb{R}\) by \[\begin{align} h(\boldsymbol{x}) \mathrel{\vcenter{:}}= g\bigl(a\boldsymbol{1}_d + (c-a)\boldsymbol{x} \bigr), \end{align}\] so that \(h\in\mathcal{H}_d^{\beta}\bigl([0,1]^d, \gamma \vee (c-a)^{\beta_0}\gamma\bigr)\). By Lemma 1, there exists \(f^\circ \in\mathcal{F}(L,\boldsymbol{p})\) such that \(|f^\circ(\boldsymbol{x})| \leq \gamma \vee (c-a)^{\beta_0}\gamma\) for all \(\boldsymbol{x} \in \mathbb{R}^d\), and \[\begin{align} |f^\circ(\boldsymbol{x}) - h(\boldsymbol{x})| \leq 9 \bigl(\gamma \vee (c-a)^{\beta_0}\gamma\bigr) (\beta_0+3)^2 8^{\beta} t^{\beta_0+\beta/2} (NM)^{-2\beta/t} \label{eq:f94circ-property} \end{align}\tag{16}\] for all \(\boldsymbol{x} \in [0,1]^d \setminus \Gamma \bigl([0,1]^d,R,\delta\bigr)\). By [NN-composition], there exists \(f \in \mathcal{F}(L,\boldsymbol{p})\) such that \[\begin{align} f(\boldsymbol{x}) = f^\circ\biggl(\frac{\boldsymbol{x} - a\boldsymbol{1}_d}{c-a}\biggr), \end{align}\] and \(|f(\boldsymbol{x})| \leq \gamma \vee (c-a)^{\beta_0}\gamma\) for all \(\boldsymbol{x} \in \mathbb{R}^d\). Thus, by 16 , \[\begin{align} |f(\boldsymbol{x}) - g(\boldsymbol{x})| \leq 9 \bigl(\gamma \vee (c-a)^{\beta_0}\gamma\bigr) (\beta_0+3)^2 8^{\beta} t^{\beta_0+\beta/2} (NM)^{-2\beta/t} \end{align}\] for all \(\boldsymbol{x} \in [a,c]^d \setminus \Gamma\bigl([a,c]^d, R, \delta\bigr)\). This proves the claim when \(t=d\).

Now assume that \(t\in[d-1]\). Without loss of generality, assume that \(g\) depends only on the coordinates in \([t]\). Define \(g^{[t]} : [a,c]^t \to \mathbb{R}\) by \(g^{[t]}(\boldsymbol{y}) \mathrel{\vcenter{:}}= g(\boldsymbol{y}, \boldsymbol{0}_{d-t})\), so that \(g^{[t]} \in \mathcal{H}_t^{\beta}\bigl([a,c]^t, \gamma\bigr)\). Then, by the case where \(t=d\), there exists \(f^{[t]} \in \mathcal{F}(L, \boldsymbol{p}^{[t]})\) where \(\boldsymbol{p}^{[t]} \mathrel{\vcenter{:}}= (t,p_*,\ldots,p_*,1)^\top \in \mathbb{N}^{L+2}\) such that \(|f^{[t]}(\boldsymbol{y})| \leq \gamma \vee (c-a)^{\beta_0}\gamma\) for all \(\boldsymbol{y}\in \mathbb{R}^t\), and \[\begin{align} \bigl|f^{[t]}(\boldsymbol{y}) - g^{[t]}(\boldsymbol{y})\bigr| \leq 9 \bigl(\gamma \vee (c-a)^{\beta_0}\gamma\bigr) (\beta_0+3)^2 8^{\beta} t^{\beta_0+\beta/2} (NM)^{-2\beta/t} \end{align}\] for all \(\boldsymbol{y} \in [a,c]^t \setminus \Gamma\bigl([a,c]^t, R, \delta\bigr)\). By [NN-composition], we can define \(f\in\mathcal{F}(L,\boldsymbol{p})\) by \(f(\boldsymbol{x}) \mathrel{\vcenter{:}}= f^{[t]}(\boldsymbol{M} \boldsymbol{x})\), where \(\boldsymbol{M} \mathrel{\vcenter{:}}= \begin{pmatrix} \boldsymbol{I}_t & \boldsymbol{0} \end{pmatrix} \in \mathbb{R}^{t \times d}\), and \(f\) satisfies the requirements in the statement. ◻

By Assumption 2, for each \(k\in[K]\), there exist \(\boldsymbol{g}^{(k)}_{1}, \ldots, \boldsymbol{g}^{(k)}_{q_k}\) such that \[\begin{gather} \boldsymbol{g}^{(k)}_{r}=\bigl(g^{(k)}_{r,1}, \ldots, g^{(k)}_{r,d_{r+1}^{(k)}}\bigr)^\top : \mathbb{R}^{d_{r}^{(k)}} \to \mathbb{R}^{d_{r+1}^{(k)}}, \nonumber\\ g_{r,j}^{(k)} \in \mathcal{H}_{t_{r}^{(k)}}^{\beta_{r}^{(k)}}\bigl(\mathbb{R}^{d^{(k)}_r}, \gamma^{(k)}_r\bigr) \text{ for all } r\in[q_k], j\in[d_{r+1}^{(k)}], \end{gather}\] and \[\begin{align} f^{\mathcal{S}_k}(\boldsymbol{z}) = \boldsymbol{g}^{(k)}_{q_k} \circ \boldsymbol{g}^{(k)}_{q_k-1} \circ \cdots \circ \boldsymbol{g}^{(k)}_{1}(\boldsymbol{z}) \end{align}\] for all \(\boldsymbol{z}\in \mathbb{R}^d\). Now, for \(k \in [K]\), define \[\begin{gather} a_1^{(k)} \mathrel{\vcenter{:}}= -\xi_1\log(2dn),\quad c_1^{(k)} \mathrel{\vcenter{:}}= \xi_1\log(2dn)\nonumber\\ \text{and } a_r^{(k)} \mathrel{\vcenter{:}}= -\gamma_{r-1}^{(k)},\quad c_r^{(k)} \mathrel{\vcenter{:}}= \gamma_{r-1}^{(k)} \quad\text{for } r\in\{2,\ldots,q_k+1\}. \label{eq:defn-a95r9440k41-c95r9440k41} \end{gather}\tag{17}\] For \(r\in\{2,\ldots,q_k+1\}\), we have \(\boldsymbol{g}_{r-1}^{(k)}(\boldsymbol{z}) \in [a_r^{(k)},\, c_r^{(k)}]^{d_r^{(k)}}\) for all \(\boldsymbol{z} \in \mathbb{R}^{d^{(k)}_{r-1}}\) by the Hölder property of these functions. Thus, it is sufficient to restrict the domain of \(\boldsymbol{g}_r^{(k)}\) to \([a_r^{(k)},\, c_r^{(k)}]^{d_r^{(k)}}\), for \(r\in\{2,\ldots,q_k\}\). Then, Assumption 2 yields that \[\begin{align} f^{\mathcal{S}_k}(\boldsymbol{z}) = \boldsymbol{g}^{(k)}_{q_k} \circ \boldsymbol{g}^{(k)}_{q_k-1} \cdots \circ \boldsymbol{g}^{(k)}_{1}(\boldsymbol{z}) \end{align}\] for all \(\boldsymbol{z}\in [a_1^{(k)},c_1^{(k)}]^d = \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d\), where \[\begin{gather} \boldsymbol{g}^{(k)}_{r}=\bigl(g^{(k)}_{r,1}, \ldots, g^{(k)}_{r,d_{i+1}^{(k)}}\bigr)^\top : [a_{r}^{(k)}, c_{r}^{(k)}]^{d_{r}^{(k)}} \to [a_{r+1}^{(k)}, c_{r+1}^{(k)}]^{d_{r+1}^{(k)}}, \text{ and} \nonumber\\ g_{r,j}^{(k)} \in \mathcal{H}_{t_{r}^{(k)}}^{\beta_{r}^{(k)}}\bigl([a^{(k)}_r,c^{(k)}_r]^{d^{(k)}_r}, \gamma^{(k)}_r\bigr) \text{ for all } r\in[q_k], j\in[d_{r+1}^{(k)}]. \label{eq:defn-g95r94k} \end{gather}\tag{18}\] The reason that we are restricting the domain of \(f^{\mathcal{S}_k}\) to \(\bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d\) is that by Assumption 1, each coordinate of \(\boldsymbol{Z}_0\) is sub-exponential, so \(\mathbb{P}\bigl(|Z_{0,j}| \geq \xi_1\log(2dn)\bigr) \leq 1/(dn)\) for all \(j\in[d]\). Thus, by a union bound, \[\begin{align} \mathbb{P}\Bigl\{ \boldsymbol{Z}_0 \notin \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d \Bigr\} \leq \frac{1}{n}, \label{eq:truncate-Z} \end{align}\tag{19}\] so it will suffice to approximate \(f^{\mathcal{S}_k}\) on \(\bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d\). To this end, we begin by approximating each function in the composition that defines \(f^{\mathcal{S}_k}\). Finally, recall that for \(k\in[K]\) and \(r\in[q_k]\), we define \[\begin{align} \bar{\beta}^{(k)}_r \mathrel{\vcenter{:}}= \beta^{(k)}_{r} \prod_{\ell=r+1}^{q_k} (\beta^{(k)}_{\ell} \wedge 1). \end{align}\] We also define \(r_*^{(k)} \mathrel{\vcenter{:}}= \mathrm{sargmax}_{r\in[q_k]} t^{(k)}_r / \bar{\beta}^{(k)}_r\) and let \(\bar\beta^{(k)}_* \mathrel{\vcenter{:}}= \bar\beta^{(k)}_{r_*^{(k)}}\), \(\beta^{(k)}_* \mathrel{\vcenter{:}}= \beta^{(k)}_{r_*^{(k)}}\), \(t^{(k)}_* \mathrel{\vcenter{:}}= t^{(k)}_{r_*^{(k)}}\) and \(\gamma_*^{(k)} \mathrel{\vcenter{:}}= \gamma^{(k)}_{r_*^{(k)}}\).

Lemma 3. Suppose that Assumptions 1 and 2 hold. With the notation in 17 and 18 , for \(M,N\in\mathbb{N}\) and \(k\in[K]\), let \[\begin{gather} L^{(k)} \mathrel{\vcenter{:}}= \max_{r\in[q_k]} 12\lceil \beta^{(k)}_r \rceil^2(M+2)\lceil\log_2(4M)\rceil,\\ p^{(k)}_* \mathrel{\vcenter{:}}= \max_{r\in[q_k]} \Bigl\{30 d_{r+1}^{(k)} \lceil\beta^{(k)}_r\rceil^2 (t^{(k)}_r)^{\lceil\beta^{(k)}_r\rceil} (N+1)\lceil\log_2(8N)\rceil \vee 2 d_{r+1}^{(k)}\Bigr\} \text{ and}\\ \boldsymbol{p}^{(k)}_r \mathrel{\vcenter{:}}= (d^{(k)}_r, p^{(k)}_*,\ldots, p^{(k)}_*, d^{(k)}_{r+1})^\top \in \mathbb{N}^{L^{(k)}+2} \text{ for } r\in[q_k]. \end{gather}\] For each \(k\in[K]\), \(r \in [q_k]\) and \(n\in\mathbb{N}\), there exist \(\boldsymbol{f}^{(k)}_r \in \mathcal{F}(L^{(k)},\boldsymbol{p}^{(k)}_r)\) and \(E_r^{(k)} \subseteq [a^{(k)}_r,c^{(k)}_r]^{d^{(k)}_r}\) satisfying:

\(\|\boldsymbol{f}_r^{(k)}(\boldsymbol{x})\|_{\infty} \leq \gamma_r^{(k)} \vee (c_r^{(k)} - a_r^{(k)})^{\lceil \beta_r^{(k)} \rceil-1} \gamma_r^{(k)}\) for all \(\boldsymbol{x} \in \mathbb{R}^{d_r^{(k)}}\) and \[\begin{align} &\bigl\|\boldsymbol{f}^{(k)}_r(\boldsymbol{x}) - \boldsymbol{g}^{(k)}_r(\boldsymbol{x})\bigr\|_{\infty}\\ & \leq 9 \bigl( 1 \vee (c_r^{(k)} - a_r^{(k)})^{\lceil \beta_r^{(k)} \rceil - 1} \bigr) \gamma^{(k)}_r (\lceil \beta^{(k)}_r \rceil +2)^2 8^{\beta_r^{(k)}} (t^{(k)}_r)^{\lceil \beta_r^{(k)} \rceil - 1 + \beta^{(k)}_r/2} (NM)^{-2\beta^{(k)}_r / t^{(k)}_r}, \end{align}\] for all \(\boldsymbol{x} \in [a^{(k)}_r,c^{(k)}_r]^{d^{(k)}_r} \setminus E^{(k)}_r\).
\(\mu_{\boldsymbol{Z}_0}(E^{(k)}_1) \leq \frac{1}{Kn q_k}\) and \(\mu_{\boldsymbol{Z}_0}\bigl((\boldsymbol{F}^{(k)}_{r-1})^{-1}(E^{(k)}_r)\bigr) \leq \frac{1}{Kn q_k}\) for all \(r\in\{2,\ldots,q_k\}\), where \(\boldsymbol{F}^{(k)}_r \mathrel{\vcenter{:}}= \boldsymbol{f}^{(k)}_r \circ \cdots\circ \boldsymbol{f}^{(k)}_1\).

Proof. Fixing \(k\in[K]\), we construct \((f^{(k)}_r,E^{(k)}_r)_{r=1}^{q_k}\) inductively. For \(r \in [q_k]\), let \(R^{(k)}_r \mathrel{\vcenter{:}}= \lfloor N^{1/t^{(k)}_r} \rfloor^2 \lfloor M^{2/t^{(k)}_r} \rfloor\) for \(r \in [q_k]\). Let \(\delta_{\max} \mathrel{\vcenter{:}}= \frac{1}{3\max_{r\in[q_k]}R_r^{(k)}}\). By Lemma 2, [NN-enlarging], [NN-padding] and [NN-parallelisation], for any \(\delta\in(0,\delta_{\max}]\), there exists \(\boldsymbol{f}^{(k)}_{1,\delta} \in \mathcal{F}(L^{(k)}, \boldsymbol{p}^{(k)}_1)\) such that \(\|\boldsymbol{f}_{1,\delta}^{(k)}(\boldsymbol{x})\|_{\infty} \leq \bigl( 1 \vee (c_1^{(k)} - a_1^{(k)})^{\lceil \beta_1^{(k)} \rceil - 1} \bigr) \gamma_1^{(k)}\) for all \(\boldsymbol{x} \in \mathbb{R}^{d_1^{(k)}}\) and \[\begin{align} &\bigl\|\boldsymbol{f}^{(k)}_{1,\delta}(\boldsymbol{x}) - \boldsymbol{g}^{(k)}_1(\boldsymbol{x})\bigr\|_{\infty}\\ &\quad \leq 9 \bigl( 1 \vee (c_1^{(k)} - a_1^{(k)})^{\lceil \beta_1^{(k)} \rceil - 1} \bigr) \gamma^{(k)}_1 (\lceil \beta^{(k)}_1 \rceil +2)^2 8^{\beta_1^{(k)}} (t^{(k)}_1)^{\lceil \beta_1^{(k)} \rceil - 1 + \beta^{(k)}_1/2} (NM)^{-2\beta^{(k)}_1 / t^{(k)}_1}, \end{align}\] for all \(\boldsymbol{x} \in [a^{(k)}_1, c^{(k)}_1]^{d^{(k)}_1} \setminus E^{(k)}_{1,\delta}\), where \(E^{(k)}_{1,\delta} \mathrel{\vcenter{:}}= \Gamma\bigl([a^{(k)}_1, c^{(k)}_1]^{d^{(k)}_1},\, R^{(k)}_1,\, \delta\bigr)\) as defined in Lemma 2. Further note that \((E^{(k)}_{1,\delta})_{\delta\in(0,\delta_{\max}]}\) are nested and have empty intersection. Thus, there exists \(\delta^* \in (0,\delta_{\max}]\) such that \(\mu_{\boldsymbol{Z}_0}(E^{(k)}_{1,\delta^*}) \leq \frac{1}{Kn q_k}\). We set \(\boldsymbol{f}^{(k)}_1 \mathrel{\vcenter{:}}= \boldsymbol{f}^{(k)}_{1,\delta^*}\) and \(E^{(k)}_1 \mathrel{\vcenter{:}}= E^{(k)}_{1,\delta^*}\), so that \(\boldsymbol{f}^{(k)}_1\) and \(E^{(k)}_1\) satisfy conditions (i) and (ii).

Now suppose that \(\boldsymbol{f}^{(k)}_1,\ldots,\boldsymbol{f}^{(k)}_{r-1}\) and \(E^{(k)}_1,\ldots,E^{(k)}_{r-1}\) satisfying conditions (i) and (ii) have been constructed for some \(r\in\{2,\ldots,q_k\}\). We apply the same argument as above to construct \(\boldsymbol{f}^{(k)}_r\) and \(E^{(k)}_r\). By Lemma 2, [NN-enlarging], [NN-padding] and [NN-parallelisation], for any \(\delta\in(0,\delta_{\max}]\), there exists \(\boldsymbol{f}^{(k)}_{r,\delta} \in \mathcal{F}(L^{(k)}, \boldsymbol{p}^{(k)}_r)\) such that \(\|\boldsymbol{f}_{r,\delta}^{(k)}(\boldsymbol{x})\|_{\infty} \leq \bigl( 1 \vee (c_r^{(k)} - a_r^{(k)})^{\lceil \beta_r^{(k)} \rceil - 1} \bigr) \gamma_r^{(k)}\) for all \(\boldsymbol{x} \in \mathbb{R}^{d_r^{(k)}}\) and \[\begin{align} &\bigl\|\boldsymbol{f}^{(k)}_{r,\delta}(\boldsymbol{x}) - \boldsymbol{g}^{(k)}_r(\boldsymbol{x})\bigr\|_{\infty}\\ & \leq 9 \bigl( 1 \vee (c_r^{(k)} - a_r^{(k)})^{\lceil \beta_r^{(k)} \rceil - 1} \bigr) \gamma^{(k)}_r (\lceil \beta^{(k)}_r \rceil +2)^2 8^{\beta_r^{(k)}} (t^{(k)}_r)^{\lceil \beta_r^{(k)} \rceil - 1 + \beta^{(k)}_r/2} (NM)^{-2\beta^{(k)}_r / t^{(k)}_r}, \end{align}\] for all \(\boldsymbol{x} \in [a^{(k)}_r, c^{(k)}_r]^{d^{(k)}_r} \setminus E^{(k)}_{r,\delta}\), where \(E^{(k)}_{r,\delta} \mathrel{\vcenter{:}}= \Gamma\bigl([a^{(k)}_r, c^{(k)}_r]^{d^{(k)}_r},\, R^{(k)}_r,\, \delta\bigr)\). Again, since \(\bigl((\boldsymbol{F}_{r-1}^{(k)})^{-1}(E_{r,\delta}^{(k)})\bigr)_{\delta \in (0,\delta_{\max}]}\) are nested and have empty intersection, there exists \(\delta^* \in (0,\delta_{\max}]\) such that \(\mu_{\boldsymbol{Z}_0}\bigl((\boldsymbol{F}_{r-1}^{(k)})^{-1}(E^{(k)}_{r,\delta^*})\bigr) \leq \frac{1}{Kn q_k}\). We set \(\boldsymbol{f}^{(k)}_r \mathrel{\vcenter{:}}= \boldsymbol{f}^{(k)}_{r,\delta^*}\) and \(E^{(k)}_r \mathrel{\vcenter{:}}= E^{(k)}_{r,\delta^*}\), so that \(\boldsymbol{f}^{(k)}_r\) and \(E^{(k)}_r\) satisfy conditions (i) and (ii). ◻

We are now in a position to approximate each piece of the Bayes regression function by a neural network on a hypercube, once we have excised certain strips.

Lemma 4. Suppose that Assumptions 1 and 2 hold and let \(n\geq 2\). For \(M,N\in\mathbb{N}\) and \(k\in[K]\), let \[\begin{gather} L^{(k)} \mathrel{\vcenter{:}}= \max_{r\in[q_k]} 12\lceil \beta^{(k)}_r \rceil^2(M+2)\lceil\log_2(4M)\rceil \text{ and}\\ p^{(k)}_* \mathrel{\vcenter{:}}= \max_{r\in[q_k]} \Bigl\{ 30 d_{r+1}^{(k)} \lceil\beta^{(k)}_r\rceil^2 (t^{(k)}_r)^{\lceil\beta^{(k)}_r\rceil} (N+1)\lceil\log_2(8N)\rceil \vee 2d_{r+1}^{(k)} \Bigr\}. \end{gather}\] For each \(k\in[K]\), there exist \(E^{(k)} \subseteq \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d\) and \(f^{(k)} \in \mathcal{F}(q_kL^{(k)}, \boldsymbol{p}^{(k)})\) where \(\boldsymbol{p}^{(k)} \mathrel{\vcenter{:}}= (d, p^{(k)}_*,\ldots,p^{(k)}_*,1) \in \mathbb{N}^{q_kL^{(k)}+2}\) such that \(\mu_{\boldsymbol{Z}_0}(E^{(k)}) \leq \frac{1}{Kn}\), \(|f^{(k)}(\boldsymbol{z})| \leq \gamma_{q_k}^{(k)} \vee (2\gamma_{q_k-1}^{(k)})^{\lceil\beta_{q_k}^{(k)}\rceil-1} \gamma_{q_k}^{(k)}\) for all \(\boldsymbol{z} \in \mathbb{R}^d\), and \[\begin{align} \bigl|f^{(k)}(\boldsymbol{z}) - f^{\mathcal{S}_k}(\boldsymbol{z})\bigr| \leq C_1(\xi_1, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}) \cdot \log^{\bar{\beta}_1^{(k)}} (2dn) \sum_{r=1}^{q_k} \frac{1}{(NM)^{2\bar{\beta}^{(k)}_r / t^{(k)}_r}} \end{align}\] for all \(\boldsymbol{z}\in \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d \setminus E^{(k)}\), where \(C_1(\xi_1, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}) > 0\) depends only on \((\xi_1, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)})\), and \(C_1(\xi_1, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}) \leq A(\xi_1,\boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)})\|\boldsymbol{t}^{(k)}\|_\infty^{B(\boldsymbol{\beta}^{(k)})}\) for some \(A(\xi_1,\boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}),B(\boldsymbol{\beta}^{(k)}) > 0\).

Proof. We use the notation in 17 and 18 . Fix \(k \in [K]\), and let \((\boldsymbol{f}^{(k)}_r)_{r=1}^{q_k}\) and \((E^{(k)}_r)_{r=1}^{q_k}\) be defined as in Lemma 3. By [NN-composition], the function \(f^{(k)} \mathrel{\vcenter{:}}= \boldsymbol{f}^{(k)}_{q_k} \circ\cdots\circ \boldsymbol{f}^{(k)}_1\) belongs to \(\mathcal{F}(q_kL^{(k)}, \boldsymbol{p}^{(k)})\). For \(r\in[q_k]\), recall the definition of \(\boldsymbol{F}^{(k)}_r\) from Lemma 3 and let \(\boldsymbol{G}^{(k)}_r \mathrel{\vcenter{:}}= \boldsymbol{g}^{(k)}_{r} \circ\cdots\circ \boldsymbol{g}^{(k)}_1\). Define \(E^{(k)} \mathrel{\vcenter{:}}= \bigcup_{r\in[q_k]} (\boldsymbol{F}^{(k)}_{r-1})^{-1}(E^{(k)}_r)\) with \(\boldsymbol{F}^{(k)}_0\) being the identity function. By Lemma 3 and a union bound, \(\mu_{\boldsymbol{Z}_0}(E^{(k)}) \leq \frac{1}{Kn}\). For \(\boldsymbol{f}:\mathbb{R}^d \to \mathbb{R}^m\) and \(D\subseteq\mathbb{R}^d\), we define \(\|\boldsymbol{f}\|_{L^{\infty}(D)} \mathrel{\vcenter{:}}= \sup_{\boldsymbol{x}\in D} \|\boldsymbol{f}(\boldsymbol{x})\|_{\infty}\). For \(r\in[q_k]\), let \(D^{(k)}_r \mathrel{\vcenter{:}}= [a^{(k)}_r, c^{(k)}_r]^{d^{(k)}_r} \setminus E^{(k)}_r\) and let \(D^{(k)} \mathrel{\vcenter{:}}= \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d \setminus E^{(k)}\). Then, for \(r\in\{2,\ldots,q_k\}\), \[\begin{align} \bigl\|\boldsymbol{F}^{(k)}_r - \boldsymbol{G}^{(k)}_r&\bigr\|_{L^{\infty}(D^{(k)})} \leq \bigl\|\boldsymbol{f}^{(k)}_r \circ \boldsymbol{f}^{(k)}_{r-1} \circ\cdots\circ \boldsymbol{f}^{(k)}_1 - \boldsymbol{g}^{(k)}_r \circ \boldsymbol{f}^{(k)}_{r-1} \circ\cdots\circ \boldsymbol{f}^{(k)}_1\bigr\|_{L^{\infty}(D^{(k)})} \nonumber\\ & + \bigl\|\boldsymbol{g}^{(k)}_r \circ \boldsymbol{f}^{(k)}_{r-1} \circ\cdots\circ \boldsymbol{f}^{(k)}_1 - \boldsymbol{g}^{(k)}_r \circ \boldsymbol{g}^{(k)}_{r-1} \circ\cdots\circ \boldsymbol{g}^{(k)}_1\bigr\|_{L^{\infty}(D^{(k)})} \nonumber\\ &\leq \bigl\|\boldsymbol{f}^{(k)}_r - \boldsymbol{g}^{(k)}_r\bigr\|_{L^{\infty} (\boldsymbol{F}^{(k)}_{r-1}(D^{(k)}))} + \gamma^{(k)}_r \Bigl\{ \bigl(t^{(k)}_r\bigr)^{1/2}\bigl\|\boldsymbol{F}^{(k)}_{r-1} - \boldsymbol{G}^{(k)}_{r-1}\bigr\|_{L^{\infty}(D^{(k)})} \Bigr\}^{\beta^{(k)}_r \wedge 1} \nonumber\\ &\leq \bigl\|\boldsymbol{f}^{(k)}_r - \boldsymbol{g}^{(k)}_r\bigr\|_{L^{\infty} (D^{(k)}_r)} + \gamma^{(k)}_r \bigl(t^{(k)}_r\bigr)^{(\beta^{(k)}_r \wedge 1)/2} \bigl\|\boldsymbol{F}^{(k)}_{r-1} - \boldsymbol{G}^{(k)}_{r-1}\bigr\|_{L^{\infty}(D^{(k)})}^{\beta^{(k)}_r \wedge 1}, \label{eq:composition-error} \end{align}\tag{20}\] where the second inequality follows since each coordinate of \(\boldsymbol{g}_r^{(k)}\) belongs to the class \(\mathcal{H}_{t_r^{(k)}}^{\beta_r^{(k)}}\bigl([a_r^{(k)},c_r^{(k)}]^{d_r^{(k)}}, \gamma_r^{(k)}\bigr)\). Thus, \[\begin{align} \bigl\|&f^{(k)} - f^{\mathcal{S}_k}\bigr\|_{L^{\infty}(D^{(k)})} = \bigl\|\boldsymbol{F}^{(k)}_{q_k} - \boldsymbol{G}^{(k)}_{q_k}\bigr\|_{L^{\infty}(D^{(k)})}\\ &\leq \sum_{r=1}^{q_k} \biggl\{ \prod_{j=r+1}^{q_k} (\gamma^{(k)}_j)^{\bar{\beta}_j^{(k)} / \beta_j^{(k)}}\bigl(t^{(k)}_j\bigr)^{\bar{\beta}_{j-1}^{(k)} / (2\beta_{j-1}^{(k)})} \biggr\} \bigl\|\boldsymbol{f}^{(k)}_r - \boldsymbol{g}^{(k)}_r\bigr\|_{L^{\infty} (D^{(k)}_r)}^{\bar{\beta}^{(k)}_r / \beta^{(k)}_r}\\ &\leq \sum_{r=1}^{q_k} \biggl\{ \prod_{j=r+1}^{q_k} (\gamma^{(k)}_j)^{\bar{\beta}_j^{(k)} / \beta_j^{(k)}}\bigl(t^{(k)}_j\bigr)^{\bar{\beta}_{j-1}^{(k)} / (2\beta_{j-1}^{(k)})} \biggr\} \Bigl\{9 \bigl( 1 \vee (c_r^{(k)} - a_r^{(k)})^{\lceil \beta_r^{(k)} \rceil - 1} \bigr) \gamma^{(k)}_r \\ & \times (\lceil \beta^{(k)}_r \rceil +2)^2 8^{\beta_r^{(k)}} (t^{(k)}_r)^{\lceil \beta_r^{(k)} \rceil - 1 + \beta^{(k)}_r/2} \Bigr\}^{\bar{\beta}^{(k)}_r / \beta^{(k)}_r} (NM)^{-2\bar{\beta}^{(k)}_r / t^{(k)}_r}\\ &\leq C_1(\xi_1, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}) \cdot \log^{\bar{\beta}_1^{(k)}} (2dn) \sum_{r=1}^{q_k} \frac{1}{(NM)^{2\bar{\beta}^{(k)}_r / t^{(k)}_r}}, \end{align}\] where \(C_1(\xi_1, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)})\) has the properties claimed in the statement of the result. Here, the first inequality follows by applying 20 iteratively and using the fact that \((a+b)^t \leq a^t + b^t\) for \(a,b \geq 0\) and \(t\in[0,1]\), the second inequality follows from Lemma 3, and the third inequality follows by substituting the definitions of \((a^{(k)}_r, c^{(k)}_r)_{r=1}^{q_k}\) in 17 . Moreover, \(\|f^{(k)}\|_{L^{\infty}(\mathbb{R}^d)} \leq \|\boldsymbol{f}^{(k)}_{q_k}\|_{L^{\infty}(\mathbb{R}^d)} \leq \gamma_{q_k}^{(k)} \vee (2\gamma_{q_k-1}^{(k)})^{\lceil\beta_{q_k}^{(k)}\rceil-1} \gamma_{q_k}^{(k)}\) by Lemma 3. ◻

The following lemma is used in the proof of Lemma 6 below, which quantifies the extent to which we can extract coordinates, based on a function \(\boldsymbol{f}_2\) that separates \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\), using a neural network.

Lemma 5. For any \(B>0\) and \(N,L\in\mathbb{N}\), there exists \(\phi \in \mathcal{F}\bigl(L,(2,9N+1,\ldots,9N+1,1)\bigr)\) such that for all \(x\in[-B,B]\), we have \[\begin{align} \phi(x,0) = 0 \quad\text{and}\quad |\phi(x,1)-x| \leq \frac{12B}{N^L}. \end{align}\]

Proof. By [35], there exists \(\phi_1 \in \mathcal{F}\bigl(L,(2,9N,\ldots,9N,1)\bigr)\) such that \(|\phi_1(a,b)-ab| \leq 6N^{-L}\) for all \(a,b\in[0,1]\). Moreover, by [35], the function \(\phi_1\) is defined by \(\phi_1(a,b) = 2\bigl(\psi(\frac{a+b}{2}) - \psi(\frac{a}{2}) - \psi(\frac{b}{2})\bigr)\), where \(\psi\) is the neural network constructed in [35], which satisfies \(\psi(0) = 0\). Therefore, \(\phi_1(a,0) = 0\) for all \(a\in[0,1]\). By [NN-composition] and [NN-parallelisation], there exists \(\phi\in\mathcal{F}\bigl(L,(2,9N+1,\ldots,9N+1,1)\bigr)\) such that \(\phi(x,y) = 2B\phi_1(\frac{x+B}{2B}, y) - By\) for all \((x,y)\in\mathbb{R}\times[0,\infty)\). Moreover, for all \(x\in[-B,B]\), we have \(\phi(x,0) = 2B\phi_1(\frac{x+B}{2B}, 0) = 0\) and \[\begin{align} |\phi(x,1) - x| = 2B\biggl|\phi_1\biggl(\frac{x+B}{2B}, 1\biggr) - \frac{x+B}{2B}\biggr| \leq \frac{12B}{N^L}, \end{align}\] as required. ◻

Lemma 6. Suppose that \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is separated by \(\boldsymbol{f}_2 \in \mathcal{F}(L_2,\boldsymbol{p}_2)\). Let \(m \mathrel{\vcenter{:}}= p_{2,L_2+1}\) and \(B > 0\). For any \(M,N_1,\ldots,N_K \in \mathbb{N}\), let \[\begin{gather} s \mathrel{\vcenter{:}}= (13m+7)K + (2M+2)\sum_{k=1}^K(9N_k+1)^2 + 7,\\ p_* \mathrel{\vcenter{:}}= (4m+1)K \vee \sum_{k=1}^K (9N_k+1) \quad \text{and} \quad \boldsymbol{p} \mathrel{\vcenter{:}}= (K+m, p_*, \ldots, p_*, 1) \in \mathbb{N}^{M+5}. \end{gather}\] Then there exists \(f_3\in\mathcal{F}(M+3, \boldsymbol{p}, s)\) such that \(|f_3(\boldsymbol{u}, \boldsymbol{v})| \leq B\) for all \((\boldsymbol{u}, \boldsymbol{v}) \in \mathbb{R}^K \times \mathbb{R}^m\), and for all \(\boldsymbol{u}=(u_1,\ldots,u_K)^\top \in [-B,B]^K\), \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\), we have \[\begin{align} \bigl|f_3 \bigl(\boldsymbol{u}, \boldsymbol{f}_2(\boldsymbol{\omega})\bigr) - u_k \bigr| \leq\frac{12B}{N_k^M}. \end{align}\]

Proof. Suppose that \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) and \(\boldsymbol{f}_2 \in \mathcal{F}(L_2,\boldsymbol{p}_2)\) satisfy Definition 1 for some \(\epsilon>0\) and \(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_K \in \mathbb{R}^m\). For \(a\in\mathbb{R}\), define \(h_a:\mathbb{R} \to [0,1]\) by \[\begin{align} h_a(x) \mathrel{\vcenter{:}}= \sigma\biggl(\frac{2x-2a+2\epsilon}{\epsilon}\biggr) - \sigma\biggl(\frac{2x-2a+\epsilon}{\epsilon}\biggr) - \sigma\biggl(\frac{2x-2a-\epsilon}{\epsilon}\biggr) +\sigma\biggl(\frac{2x-2a-2\epsilon}{\epsilon}\biggr). \end{align}\] Then \(h_a \in \mathcal{F}\bigl(1,(1,4,1),12\bigr)\), with \(h_a(x) = 1\) for all \(x\in\bigl[a-\frac{\epsilon}{2}, a+\frac{\epsilon}{2}\bigr]\) and \(h_a(x) = 0\) for all \(x\in(-\infty,a-\epsilon] \cup [a+\epsilon,\infty)\). Further, for \(k\in[K]\), write \(\boldsymbol{v}_k = (v_{k,1},\ldots,v_{k,m})^\top \in \mathbb{R}^m\) and define \(g_k \in \mathcal{F}\bigl(2,(m,4m,1,1),13m+2\bigr)\) by \[\begin{align} g_k(\boldsymbol{x}) \mathrel{\vcenter{:}}= \sigma\biggl(\sum_{j=1}^m h_{v_{k,j}}(x_j) - m + 1 \biggr). \end{align}\] Then, for \(\boldsymbol{\omega} \in \mathcal{S}_k\), we have \(g_k\bigl(\boldsymbol{f}_2(\boldsymbol{\omega})\bigr) = \sigma(m-m+1) = 1\); for \(\boldsymbol{\omega} \notin \mathcal{S}_k\), we have \(\sum_{j=1}^m h_{v_{k,j}}\bigl(f_{2,j}(\boldsymbol{\omega})\bigr) \leq m-1\), so \(g_k\bigl(\boldsymbol{f}_2(\boldsymbol{\omega})\bigr) = 0\). By Lemma 5, for \(k\in[K]\), there exists \(\phi_k \in \mathcal{F}\bigl(M,(2,9N_k+1,\ldots,9N_k+1,1)\bigr)\) such that \(\phi_k(x,0) = 0\) and \(|\phi_k(x,1) - x| \leq 12BN_k^{-M}\) for all \(x\in[-B,B]\). Further, by [NN-enlarging], [NN-composition] and [NN-parallelisation], there exists \(f_3^\circ\in\mathcal{F}\bigl(M+2,\, (K+m,p_*,\ldots,p_*,1),\, s-7\bigr)\) such that \(f_3^\circ(\boldsymbol{u}, \boldsymbol{v}) = \sum_{k=1}^K \phi_k\bigl(u_k, g_k(\boldsymbol{v})\bigr)\) for all \(\boldsymbol{u} \in[-B,B]^K\) and \(v\in\mathbb{R}^m\). Moreover, for \(\boldsymbol{\omega} \in \mathcal{S}_k\) and \(\boldsymbol{u} = (u_1,\ldots,u_K)^\top \in [-B,B]^K\), we have \[\begin{align} \bigl|f_3^\circ\bigl(\boldsymbol{u}, \boldsymbol{f}_2(\boldsymbol{\omega})\bigr) - u_k \bigr| &= \biggl|\sum_{\ell=1}^K \Bigl\{\phi_k\Bigl(u_{\ell},g_{\ell}\bigl(\boldsymbol{f}_2(\boldsymbol{\omega})\bigr)\Bigr) - u_{\ell}g_{\ell}\bigl(\boldsymbol{f}_2(\boldsymbol{\omega})\bigr) \Bigr\}\biggr|\\ &\leq \sum_{\ell=1}^K \Bigl| \phi_k \Bigl(u_{\ell},g_{\ell}\bigl(\boldsymbol{f}_2(\boldsymbol{\omega})\bigr)\Bigr) - u_{\ell}g_{\ell}\bigl(\boldsymbol{f}_2(\boldsymbol{\omega})\bigr) \Bigr|\\ &=|\phi_k(u_k,1) - u_k| + \sum_{\ell\neq k} |\phi_\ell(u_\ell, 0) - 0|\leq \frac{12B}{N_k^M}. \end{align}\] Finally, define \(f_3: \mathbb{R}^{K+m} \to [-B,B]\) by \[\begin{align} f_3 \mathrel{\vcenter{:}}= \sigma(f_3^\circ + B) - \sigma(f_3^\circ - B) - B = T_B f_3^\circ. \end{align}\] By [NN-enlarging] and [NN-composition], we have \(f_3 \in \mathcal{F}(M+3,\boldsymbol{p},s)\) and since \(u_k \in [-B,B]\), we deduce that \(\bigl|f_3\bigl(\boldsymbol{u}, \boldsymbol{f}_2(\boldsymbol{\omega})\bigr) - u_k \bigr| \leq \bigl|f_3^\circ\bigl(\boldsymbol{u}, \boldsymbol{f}_2(\boldsymbol{\omega})\bigr) - u_k \bigr|\) for all \(\boldsymbol{u}=(u_1,\ldots,u_K)^\top \in [-B,B]^K\), \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\). ◻

11 Proof of Theorem 2 ↩︎

Proof of Theorem 2. For any \(M_1 \in \mathbb{N}\), let \[L_1 \mathrel{\vcenter{:}}= \max_{k\in[K],\, r\in[q_k]} 12q_k\lceil \beta^{(k)}_r \rceil^2 (M_1+2) \lceil\log_2(4M_1)\rceil \in \mathbb{N}\] and for \(k \in [K]\), let \[\begin{gather} N^{(k)}_1 \mathrel{\vcenter{:}}= \bigl\lceil M_1^{-1} n_k^{t^{(k)}_* / (4\bar\beta^{(k)}_* + 2t^{(k)}_*)} \bigr\rceil,\\ p^{(k)}_{1,*} \mathrel{\vcenter{:}}= \max_{r\in[q_k]} \Bigl\{ 30 d_{r+1}^{(k)} \lceil\beta^{(k)}_r\rceil^2 (t^{(k)}_r)^{\lceil\beta^{(k)}_r\rceil} (N^{(k)}_1+1) \lceil\log_2(8N^{(k)}_1)\rceil \vee 2d_{r+1}^{(k)} \Bigr\},\\ \boldsymbol{p}^{(k)}_1 \mathrel{\vcenter{:}}= (d,p^{(k)}_{1,*},\ldots,p^{(k)}_{1,*},1) \in \mathbb{N}^{L_1+2}. \end{gather}\] By Lemma 4 and [NN-padding], for \(k \in [K]\) we can find \(E^{(k)} \subseteq \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d\) and \(f^{(k)}_1 \in \mathcal{F}(L_1,\boldsymbol{p}^{(k)}_1)\) such that \(\mu_{\boldsymbol{Z}_0}(E^{(k)}) \leq \frac{1}{Kn}\), \[|f^{(k)}_1(\boldsymbol{z})| \leq \max_{k\in[K]} \bigl\{\gamma_{q_k}^{(k)} \vee (2\gamma_{q_k-1}^{(k)})^{\lceil\beta_{q_k}^{(k)}\rceil-1} \gamma_{q_k}^{(k)}\bigr\} \eqqcolon B\] for all \(\boldsymbol{z} \in \mathbb{R}^d\) and \[\begin{align} \bigl|f^{(k)}_1(\boldsymbol{z}) - f^{\mathcal{S}_k}(\boldsymbol{z})\bigr| & \leq C_1(\xi_1, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}) \cdot \log^{\bar{\beta}_1^{(k)}} (2dn) \cdot q_k \cdot n_k^{-\bar\beta^{(k)}_* / (2\bar\beta^{(k)}_* + t^{(k)}_*)}\nonumber\\ & \leq C_2(\xi_1, d, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}) \cdot \log^{\bar{\beta}_1^{(k)}}(n) \cdot n_k^{-\bar\beta^{(k)}_* / (2\bar\beta^{(k)}_* + t^{(k)}_*)} \label{eq:approx-error-for-f94123S95k125} \end{align}\tag{21}\] for all \(\boldsymbol{z}\in \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d \setminus E^{(k)}\). Furthermore, each \(f^{(k)}_1\) has \(V^{(k)}_1 \mathrel{\vcenter{:}}= (d+L_1+1)p^{(k)}_{1,*} + (L_1-1)(p_{1,*}^{(k)})^2 + 1\) parameters. Thus, by [NN-parallelisation], the function \(\boldsymbol{f}_1 \mathrel{\vcenter{:}}= (f^{(1)}_1, \ldots, f^{(K)}_1)^\top : \mathbb{R}^d \to [-B,B]^K\) belongs to \(\mathcal{F}\bigl(L_1, \boldsymbol{p}_1, s_1 \bigr)\), where \(\boldsymbol{p}_1 \mathrel{\vcenter{:}}= \bigl(d, \sum_{k=1}^K p^{(k)}_{1,*}, \ldots, \sum_{k=1}^K p^{(k)}_{1,*}, K\bigr) \in \mathbb{N}^{L_1+2}\) and \(s_1 \mathrel{\vcenter{:}}= \sum_{k=1}^K V^{(k)}_1\).

By assumption, there exists \(\boldsymbol{f}_2 \in \mathcal{F}(L_2,\boldsymbol{p}_2,s_2)\) such that \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) is separated by \(\boldsymbol{f}_2\). For any \(M_3 \in \mathbb{N}\), let \(m\mathrel{\vcenter{:}}= p_{2,L_2+1}\), and let \[\begin{gather} L_3 \mathrel{\vcenter{:}}= \biggl\lceil 2M_3 \max_{k\in[K]} \frac{\bar{\beta}^{(k)}_*}{t^{(k)}_*} \biggr\rceil +3,\quad N_{3,k} \mathrel{\vcenter{:}}= \Bigl\lceil n_k^{\bar\beta^{(k)}_* / \{(L_3-3)(2\bar\beta^{(k)}_* + t^{(k)}_*)\}} \Bigr\rceil \text{ for }k\in[K],\\ p_{3,*} \mathrel{\vcenter{:}}= (4m+1)K \vee \sum_{k=1}^K (9N_{3,k}+1),\quad \boldsymbol{p}_3 \mathrel{\vcenter{:}}= \bigl(K+m,\, p_{3,*},\,\ldots,\,p_{3,*}, \,1\bigr) \in \mathbb{N}^{L_3+2} \text{ and}\\ s_3 \mathrel{\vcenter{:}}= (13m+7)K + (2M_3+2)\sum_{k=1}^K (9N_{3,k}+1)^2 + 7. \end{gather}\] By Lemma 6, there exists \(f_3 \in \mathcal{F}(L_3,\boldsymbol{p}_3, s)\) such that \(|f_3(\boldsymbol{u}, \boldsymbol{v})| \leq B\) for all \((\boldsymbol{u},\boldsymbol{v}) \in \mathbb{R}^K \times \mathbb{R}^m\), and that for all \(\boldsymbol{z} \in \mathbb{R}^d\), \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\), we have \[\begin{align} \bigl| f_3\bigl(\boldsymbol{f}_1(\boldsymbol{z}), \boldsymbol{f}_2(\boldsymbol{\omega})\bigr) - f_1^{(k)}(\boldsymbol{z}) \bigr| \leq 12B \cdot n_k^{-\bar\beta^{(k)}_* / (2\bar\beta^{(k)}_* + t^{(k)}_*)}. \label{eq:extract-coordinate-error} \end{align}\tag{22}\] Further note that for \(k\in[K]\), \[\begin{align} N_{3,k} \leq 2n_k^{t_*^{(k)} / (4\bar{\beta}_*^{((k)} + 2t_*^{(k)})}. \end{align}\] Thus, \[\begin{align} s_3 \leq C_3(m,M_3) \sum_{k=1}^K n_k^{t_*^{(k)} / (2\bar{\beta}_*^{((k)} + t_*^{(k)})}. \end{align}\] Now, define \(\bar{f} \in \mathcal{F}\) by \[\begin{align} \bar{f}(\boldsymbol{z},\boldsymbol{\omega}) \mathrel{\vcenter{:}}= f_3 \bigl( \boldsymbol{f}_1(\boldsymbol{z}),\, \boldsymbol{f}_2(\boldsymbol{\omega}) \bigr), \end{align}\] so that \(|\bar{f}(\boldsymbol{z},\boldsymbol{\omega})| \leq B\) for all \(\boldsymbol{z} \in \mathbb{R}^d\) and \(\boldsymbol{\omega} \in \mathcal{S}\). Let \(D\mathrel{\vcenter{:}}= \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d \setminus \bigl(\bigcup_{k\in[K]}E^{(k)}\bigr)\), so that by Lemma 4 and 19 , we have \[\begin{align} \mathbb{P}(\boldsymbol{Z}_0 \notin D) \leq \mathbb{P}\bigl(\boldsymbol{Z}_0 \notin \bigl[-\xi_1\log(2dn),\,\xi_1\log(2dn)\bigr]^d \bigr) + \sum_{k=1}^K \mathbb{P}(\boldsymbol{Z}_0 \in E^{(k)}) \leq \frac{2}{n}. \label{eq:D-complement-prob} \end{align}\tag{23}\] By 21 and 22 , for all \(\boldsymbol{z} \in D\), \(k\in[K]\) and \(\boldsymbol{\omega} \in \mathcal{S}_k\), we have \[\begin{align} \bigl|\bar{f}(\boldsymbol{z},\boldsymbol{\omega}) &- f^{\star}(\boldsymbol{z},\boldsymbol{\omega})\bigr| \leq \bigl|f_3 \bigl( \boldsymbol{f}_1(\boldsymbol{z}),\, \boldsymbol{f}_2(\boldsymbol{\omega}) \bigr) - f_1^{(k)}(\boldsymbol{z}) \bigr| + \bigl| f_1^{(k)}(\boldsymbol{z}) - f^{\mathcal{S}_k}(\boldsymbol{z})\bigr|\nonumber\\ &\leq \bigl\{C_2(\xi_1, d, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}) + 12B \bigr\} \cdot \log^{\bar{\beta}_1^{(k)}}(n) \cdot n_k^{-\bar\beta^{(k)}_* / (2\bar\beta^{(k)}_* + t^{(k)}_*)}. \label{eq:f-bar-property-1} \end{align}\tag{24}\] Hence there exists \(C_4>0\), depending only on \(\xi_1,d,m\) and \((\boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)})_{k=1}^K\) such that \[\begin{align} \inf_{f\in\mathcal{F}} \mathbb{E}\Bigl\{ \bigl(f(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0) &- f^{\star}(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\bigr)^2 \Bigr\}\nonumber\\ &\leq \mathbb{E}\Bigl\{ \bigl(\bar{f}(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0) - f^{\star}(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\bigr)^2 \mathbb{1}_{\{\boldsymbol{Z}_0 \in D\}} \Bigr\} + \frac{8B^2}{n}\nonumber\\ &= \sum_{k=1}^K \pi_k \mathbb{E}\Bigl\{ \bigl(\bar{f}(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0) - f^{\star}(\boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\bigr)^2 \mathbb{1}_{\{\boldsymbol{Z}_0 \in D\}} \,\bigm|\, \boldsymbol{\Omega}_0 \in \mathcal{S}_k \Bigr\} + \frac{8B^2}{n}\nonumber\\ &\leq \sum_{k=1}^K \pi_k \sup_{\boldsymbol{z}\in D, \boldsymbol{\omega}\in\mathcal{S}_k} \bigl\{\bar{f}(\boldsymbol{z},\boldsymbol{\omega}) - f^{\star}(\boldsymbol{z},\boldsymbol{\omega})\bigr\}^2 + \frac{8B^2}{n}\nonumber\\ &\leq C_4 (\log n)^{2\max_{k\in[K]}\bar{\beta}_1^{(k)}} \cdot \sum_{k=1}^K \pi_k n_k^{-2\bar\beta^{(k)}_* / (2\bar\beta^{(k)}_* + t^{(k)}_*)}, \label{eq:approx-error} \end{align}\tag{25}\] where the first inequality follows from 23 and \(|\bar{f}(\boldsymbol{z},\boldsymbol{\omega}) - f^{\star}(\boldsymbol{z},\boldsymbol{\omega})| \leq 2B\) for all \(\boldsymbol{z} \in \mathbb{R}^d\) and \(\boldsymbol{\omega}\in\mathcal{S}\), and the final inequality follows from 24 . Let \(L_0 \mathrel{\vcenter{:}}= L_3+(L_1 \vee L_2)\), \(p_0 \mathrel{\vcenter{:}}= \bigl(2d, 2\|\boldsymbol{p}_1\|_{\infty} + 2\|\boldsymbol{p}_2\|_{\infty}, \ldots, 2\|\boldsymbol{p}_1\|_{\infty} + 2\|\boldsymbol{p}_2\|_{\infty}, \boldsymbol{p}_3\bigr) \in \mathbb{N}^{L_0+2}\) and \(s_0 \mathrel{\vcenter{:}}= 2(s_1+s_2+s_3) + 2(K \vee m)|L_1 - L_2|\). By [NN-enlarging]–[NN-parallelisation], we have \(\mathcal{F}\subseteq \mathcal{F}(L_0, \boldsymbol{p}_0, s_0)\). Moreover, \[\begin{align} \frac{s_0L_0\log(es_0) + s_0\log(ed)}{n} & \leq C_5 \log^3 n \cdot \frac{\sum_{k=1}^K n_k^{t_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})} + s_2\log s_2}{n}\nonumber\\ &= C_5\log^3 n \cdot \biggl\{\sum_{k=1}^K \pi_k n_k^{-2\bar\beta^{(k)}_*/(2\bar\beta^{(k)}_* + t^{(k)}_*)} + \frac{s_2 \log s_2}{n}\biggr\}, \label{eq:entropy-bound} \end{align}\tag{26}\] where \(C_5>0\) depends only on \(m,L_2,M_1,M_3,d\) and \((\boldsymbol{d}^{(k)}, \boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)})_{k=1}^K\). The final result then follows by applying Proposition 1 in conjunction with 25 and 26 . ◻

12 Proof of Theorem 3 ↩︎

Proof of Theorem 3. Without loss of generality, we may assume that \(j_* = d\). We also define \(\beta_*^{(k)} \mathrel{\vcenter{:}}= \beta^{(k)}_{r_*^{(k)}}\). Let \(\boldsymbol{X}_0\) be uniformly distributed on \([0,1]^d\), so that \(\|X_{0,j}\|_{\psi_1} \leq 0.8 \leq \xi_1\) for \(j\in[d]\). For \(k\in[K-1]\), let \(A_k \mathrel{\vcenter{:}}= \bigl[\sum_{\ell=1}^{k-1} \pi_\ell, \sum_{\ell=1}^{k} \pi_\ell\bigr)\) and let \(A_K \mathrel{\vcenter{:}}= \bigl[\sum_{\ell=1}^{K-1} \pi_\ell, 1\bigr]\). Given \(f^{(1)}, \ldots, f^{(K)} : [0,1]^d \to [0,1/2]\), we define \(g_{(f^{(1)},\ldots,f^{(K)})} : [0,1]^d \to [0,1/2]\) by \(g_{(f^{(1)},\ldots,f^{(K)})}(\boldsymbol{x}) \mathrel{\vcenter{:}}= \sum_{k=1}^K \mathbb{1}_{\{x_d \in A_k\}} \cdot f^{(k)}(\boldsymbol{x})\) where \(\boldsymbol{x} = (x_1,\ldots,x_d)^\top \in [0,1]^d\). Further, let \(P_{(f^{(1)}, \ldots, f^{(K)})}\) be the distribution of \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0)\), where \(\boldsymbol{\Omega}_0 \,|\, \boldsymbol{X}_0 \sim \mathrm{Unif}(\mathcal{S}_k)\) if \(X_{0,d} \in A_k\), \(\boldsymbol{Z}_0 = \mathsf{Imp}(\widetilde{\boldsymbol{X}}_0)\) (where \(\widetilde{\boldsymbol{X}}_0\) is the partially observed version of \(\boldsymbol{X}_0\)) and \(Y_0 = g_{(f^{(1)},\ldots,f^{(K)})}(\boldsymbol{X}_0) + \varepsilon_0\), where \(\varepsilon_0 \sim N(0,\xi_2^2/25)\) is independent of \((\boldsymbol{X}_0, \boldsymbol{\Omega}_0)\). Thus \[\|Y_0\|_{\psi_2} \leq \|g_{(f^{(1)},\ldots,f^{(K)})}(\boldsymbol{X}_0)\|_{\psi_2} + \|\varepsilon_0\|_{\psi_2} \leq \frac{1}{2\sqrt{\log 2}} + \sqrt{\frac{8}{75}}\xi_2 \leq \xi_2.\] Moreover, observe that when \(\boldsymbol{\omega} \in \mathcal{S}_k\), we must have \(X_{0,d} \in A_k\) and hence \(g_{(f^{(1)},\ldots,f^{(K)})}(\boldsymbol{X}_0) = f^{(k)}(\boldsymbol{X}_0)\). Hence, if for each \(k\in[K]\), the function \(f^{(k)}\) depends only on the coordinates in \(\widetilde{\mathcal{J}}^{(k)} \mathrel{\vcenter{:}}=\mathcal{J}^{(k)}\setminus\{d\}\), then when \(\boldsymbol{\omega} \in \mathcal{S}_k\), \[\begin{align} f^{\star}(\boldsymbol{z}, \boldsymbol{\omega}) = \mathbb{E}(\boldsymbol{Y}_0 \, | \, \boldsymbol{Z}_0 = \boldsymbol{z},\boldsymbol{\Omega}_0 = \boldsymbol{\omega}) &= \mathbb{E}\bigl(g_{(f^{(1)},\ldots,f^{(K)})}(\boldsymbol{X}_0) \, | \, \boldsymbol{Z}_0 = \boldsymbol{z},\boldsymbol{\Omega}_0 = \boldsymbol{\omega}\bigr) \\ &= \mathbb{E}\bigl(f^{(k)}(\boldsymbol{X}_0) \, | \, \boldsymbol{Z}_0 = \boldsymbol{z},\boldsymbol{\Omega}_0 = \boldsymbol{\omega}\bigr) = f^{(k)}(\boldsymbol{z}). \end{align}\] In general then, \(f^{\star}(\boldsymbol{z}, \boldsymbol{\omega}) = \sum_{k=1}^K f^{(k)}(\boldsymbol{z})\mathbb{1}_{\{\boldsymbol{\omega} \in \mathcal{S}_k\}}\). For \(k \in [K]\), let \[\begin{align} \mathcal{F}^{(k)} \mathrel{\vcenter{:}}= \Bigl\{ f \in \mathcal{H}_{\mathrm{comp}}(q_k,\boldsymbol{d}^{(k)}, &\boldsymbol{t}^{(k)}, \boldsymbol{\beta}^{(k)}, \boldsymbol{\gamma}^{(k)}): f \text{ takes values in } [0,1/2] \text{ and}\\ &\text{depends only on the coordinates in \widetilde{\mathcal{J}}^{(k)}} \Bigr\}. \end{align}\] We have established that if \(f^{(k)} \in \mathcal{F}^{(k)}\) for all \(k\in[K]\), then \(P_{(f^{(1)}, \ldots, f^{(K)})} \in \mathcal{P}\). Let \(\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}\) be the joint distribution of \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\) when \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0,Y_0) \sim P_{(f^{(1)}, \ldots, f^{(K)})} \in \mathcal{P}\), and for \(k\in[K]\) and \(f^{(k)} \in \mathcal{F}^{(k)}\), let \(P_{f^{(k)}} \mathrel{\vcenter{:}}= P_{(0,\ldots,0,f^{(k)},0,\ldots,0)}\). Then \[\begin{align} &\inf_{\widehat{f}\in \widehat{\mathcal{F}}} \sup_{P \in \mathcal{P}} \;\mathbb{E}_{P^{\otimes n}}\bigl\{R(\widehat{f}) - R(f^{\star})\bigr\} \geq \inf_{\widehat{f}\in \widehat{\mathcal{F}}} \sup_{\substack{f^{(1)},\ldots,f^{(K)} : \\ f^{(\ell)} \in \mathcal{F}^{(\ell)} \,\forall \ell\in[K]}} \mathbb{E}_{P_{(f^{(1)}, \ldots, f^{(K)})}^{\otimes n}}\bigl\{\|\widehat{f} - f^{\star}\|_{L_2(\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0})}^2\bigr\} \nonumber\\ &= \inf_{\widehat{f} \in \widehat{\mathcal{F}}} \sup_{\substack{f^{(1)},\ldots,f^{(K)} : \\ f^{(\ell)} \in \mathcal{F}^{(\ell)} \,\forall \ell\in[K]}} \sum_{k=1}^K \mathbb{E}_{P_{(f^{(1)}, \ldots, f^{(K)})}^{\otimes n}} \int_{[0,1]^d \times \mathcal{S}} \bigl\{\widehat{f}(\boldsymbol{z},\boldsymbol{\omega}) - f^{(k)}(\boldsymbol{z})\bigr\}^2 \mathbb{1}_{\{\boldsymbol{\omega}\in\mathcal{S}_k\}} \, \mathrm{d}\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}(\boldsymbol{z}, \boldsymbol{\omega}) \nonumber\\ &\geq \sum_{k=1}^K \inf_{\widehat{f} \in \widehat{\mathcal{F}}} \sup_{\substack{f^{(1)},\ldots,f^{(K)} : \\ f^{(\ell)} \in \mathcal{F}^{(\ell)} \,\forall \ell\in[K]}} \mathbb{E}_{P_{(f^{(1)}, \ldots, f^{(K)})}^{\otimes n}} \int_{[0,1]^d \times \mathcal{S}} \bigl\{\widehat{f}(\boldsymbol{z},\boldsymbol{\omega}) - f^{(k)}(\boldsymbol{z})\bigr\}^2 \mathbb{1}_{\{\boldsymbol{\omega}\in\mathcal{S}_k\}} \, \mathrm{d}\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}(\boldsymbol{z}, \boldsymbol{\omega})\nonumber\\ &\geq \sum_{k=1}^K \inf_{\widehat{f} \in \widehat{\mathcal{F}}} \sup_{f^{(k)} \in \mathcal{F}^{(k)}} \mathbb{E}_{P_{f^{(k)}}^{\otimes n}} \int_{[0,1]^d \times \mathcal{S}} \bigl\{\widehat{f}(\boldsymbol{z},\boldsymbol{\omega}) - f^{(k)}(\boldsymbol{z})\bigr\}^2 \mathbb{1}_{\{\boldsymbol{\omega}\in\mathcal{S}_k\}} \, \mathrm{d}\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}(\boldsymbol{z}, \boldsymbol{\omega}). \label{eq:minimax-lower-bound-k-simplified} \end{align}\tag{27}\]

Now fix \(k\in[K]\) and take \(f^{(\ell)} = 0\) for all \(\ell \neq k\). Since any \(f^{(k)} \in \mathcal{F}^{(k)}\) depends only on the coordinates in \(\widetilde{\mathcal{J}}^{(k)}\), there exists \(\widetilde{f}^{(k)}: [0,1]^{|\widetilde{\mathcal{J}}^{(k)}|} \to [0, 1/2]\) such that \(f^{(k)}(\boldsymbol{x}) = \widetilde{f}^{(k)}(\boldsymbol{x}_{\widetilde{\mathcal{J}}^{(k)}})\) for all \(\boldsymbol{x} = (x_1,\ldots,x_d)^\top \in[0,1]^d\), where \(\boldsymbol{x}_{\widetilde{\mathcal{J}}^{(k)}} \mathrel{\vcenter{:}}= (x_j)_{j \in \widetilde{\mathcal{J}}^{(k)}} \in [0,1]^{|\widetilde{\mathcal{J}}^{(k)}|}\). Thus, writing \(\|f\|_{L_2} \mathrel{\vcenter{:}}= \bigl(\int_{\boldsymbol{x} \in [0,1]^m} f(\boldsymbol{x})^2 \,\mathrm{d}\boldsymbol{x}\bigr)^{1/2}\) for square-integrable \(f:[0,1]^m \to \mathbb{R}\) and \(m\in\mathbb{N}\), we deduce that for \(f_1^{(k)}, f_2^{(k)} \in \mathcal{F}^{(k)}\), \[\begin{align} \int_{[0,1]^d \times \mathcal{S}} \bigl\{f^{(k)}_1(\boldsymbol{z}) &- f^{(k)}_2(\boldsymbol{z}) \bigr\}^2\mathbb{1}_{\{\boldsymbol{\omega}\in\mathcal{S}_k\}} \, \mathrm{d}\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}(\boldsymbol{z}, \boldsymbol{\omega}) = \mathbb{E} \Bigl[ \bigl\{f^{(k)}_1(\boldsymbol{Z}_0) - f^{(k)}_2(\boldsymbol{Z}_0)\bigr\}^2 \mathbb{1}_{\{\boldsymbol{\Omega}_0 \in \mathcal{S}_k\}} \Bigr]\nonumber\\ &= \mathbb{E} \Bigl[ \bigl\{\widetilde{f}^{(k)}_1(\boldsymbol{X}_{0,\widetilde{\mathcal{J}}^{(k)}}) - \widetilde{f}^{(k)}_2(\boldsymbol{X}_{0,\widetilde{\mathcal{J}}^{(k)}})\bigr\}^2 \mathbb{1}_{\{X_{0,d} \in A_k\}} \Bigr]\nonumber\\ &= \pi_k \mathbb{E} \Bigl[ \bigl\{\widetilde{f}^{(k)}_1(\boldsymbol{X}_{0,\widetilde{\mathcal{J}}^{(k)}}) - \widetilde{f}^{(k)}_2(\boldsymbol{X}_{0,\widetilde{\mathcal{J}}^{(k)}})\bigr\}^2 \,\Big|\, X_{0,d} \in A_k \Bigr] \nonumber\\ &= \pi_k \bigl\| f^{(k)}_1 - f^{(k)}_2 \bigr\|_{L_2}^2. \label{eq:mu-Z-Omega-norm-bound} \end{align}\tag{28}\] Next, we use a construction similar to [7] to prove the lower bound. Define \(R \mathrel{\vcenter{:}}= \lfloor \lambda n_k^{1/(2\bar\beta_*^{(k)} + t_*^{(k)})} \rfloor \in \mathbb{N}\) where \(\lambda \geq 16\) will be chosen later, let \(\rho\mathrel{\vcenter{:}}= 1/R\) and let \(\mathcal{U} \mathrel{\vcenter{:}}= \{0,\rho,2\rho,\ldots,(R-1)\rho\}^{t_*^{(k)}}\). Define \(h: \mathbb{R} \rightarrow [0,1]\) by \(h(x) \mathrel{\vcenter{:}}= c_1e^{-1/\{x(1-x)\}}\mathbb{1}_{\{x\in(0,1)\}}\), where \(c_1 > 0\) depends only on \(\beta^{(k)}_*\) and is chosen such that \(h \in \mathcal{H}_1^{\beta^{(k)}_*}(\mathbb{R},1)\). Further, without loss of generality, suppose that \(\widetilde{\mathcal{J}}^{(k)} = \{1,\ldots,|\widetilde{\mathcal{J}}^{(k)}|\}\). For \(\boldsymbol{u} = (u_1,\ldots,u_{t_*^{(k)}})^\top \in \mathcal{U}\), define \(\psi_{\boldsymbol{u}} : [0,1]^{t_*^{(k)}} \to [0,1]\) by \[\begin{align} \psi_{\boldsymbol{u}}(x_1,\ldots,x_{t_*^{(k)}}) \mathrel{\vcenter{:}}= \rho^{\beta_*^{(k)}}\prod_{j=1}^{t_*^{(k)}} h\biggl(\frac{x_j-u_j}{\rho}\biggr). \end{align}\] For \(\boldsymbol{\alpha} \in \mathbb{N}_0^d\) with \(\|\boldsymbol{\alpha}\|_1 \leq \lceil \beta_*^{(k)} \rceil - 1\), we have \(\|\partial^{\boldsymbol{\alpha}} \psi_{\boldsymbol{u}}\|_{\infty} \leq 1\) since \(h \in \mathcal{H}_1^{\beta^{(k)}_*}(\mathbb{R},1)\). Moreover, for \(\boldsymbol{\alpha} \in \mathbb{N}_0^d\) with \(\|\boldsymbol{\alpha}\|_1 = \lceil \beta_*^{(k)} \rceil - 1\) and for all \(\boldsymbol{x},\boldsymbol{y} \in [0,1]^{t_*^{(k)}}\), we have \[\begin{align} &\frac{|\partial^{\boldsymbol{\alpha}} \psi_{\boldsymbol{u}}(\boldsymbol{x}) - \partial^{\boldsymbol{\alpha}} \psi_{\boldsymbol{u}}(\boldsymbol{y})|}{\|\boldsymbol{x} - \boldsymbol{y}\|_2^{\beta_*^{(k)}+1-\lceil\beta_*^{(k)}\rceil}} = \rho^{\beta_*^{(k)}+1-\lceil\beta_*^{(k)}\rceil} \frac{\Bigl| \prod_{j=1}^{t_*^{(k)}} h^{(\alpha_j)}\bigl(\frac{x_j-u_j}{\rho}\bigr) - \prod_{j=1}^{t_*^{(k)}} h^{(\alpha_j)}\bigl(\frac{y_j-u_j}{\rho}\bigr) \Bigr|}{\|\boldsymbol{x} - \boldsymbol{y}\|_2^{\beta_*^{(k)}+1-\lceil\beta_*^{(k)}\rceil}}\\ & \leq \frac{\rho^{\beta_*^{(k)}+1-\lceil\beta_*^{(k)}\rceil}}{\|\boldsymbol{x} - \boldsymbol{y}\|_2^{\beta_*^{(k)}+1-\lceil\beta_*^{(k)}\rceil}} \sum_{\ell=1}^{t_*^{(k)}}\Biggl| \prod_{j=\ell}^{t_*^{(k)}} h^{(\alpha_j)}\Bigl(\frac{x_j-u_j}{\rho}\Bigr)\prod_{j=1}^{\ell-1} h^{(\alpha_j)}\Bigl(\frac{y_j-u_j}{\rho}\Bigr)\\ & - \prod_{j=\ell+1}^{t_*^{(k)}} h^{(\alpha_j)}\Bigl(\frac{x_j-u_j}{\rho}\Bigr)\prod_{j=1}^{\ell} h^{(\alpha_j)}\Bigl(\frac{y_j-u_j}{\rho}\Bigr) \Biggr|\\ & \leq \sum_{\ell=1}^{t_*^{(k)}} \frac{\bigl| h^{(\alpha_\ell)}\bigl(\frac{x_\ell-u_\ell}{\rho}\bigr) - h^{(\alpha_\ell)}\bigl(\frac{y_\ell-u_\ell}{\rho}\bigr) \bigr|}{|(x_\ell - y_\ell)/\rho|^{\beta_*^{(k)}+1-\lceil\beta_*^{(k)}\rceil}} \leq t_*^{(k)}, \end{align}\] where the first inequality follows from the triangle inequality, and the second and third inequalities follow since \(h \in \mathcal{H}_1^{\beta^{(k)}_*}(\mathbb{R},1)\). Thus, we have shown that \(\psi_{\boldsymbol{u}} \in \mathcal{H}_{t_*^{(k)}}^{\beta_*^{(k)}}\bigl([0,1]^{t_*^{(k)}}, t_*^{(k)}\bigr)\). For \(\boldsymbol{v} = (v_{\boldsymbol{u}})_{\boldsymbol{u} \in \mathcal{U}} \in \{0,1\}^{|\mathcal{U}|}\), define \(\phi_{\boldsymbol{v}} : [0,1]^{t_*^{(k)}} \to [0,1]\) by \[\begin{align} \phi_{\boldsymbol{v}} \mathrel{\vcenter{:}}= \sum_{\boldsymbol{u} \in \mathcal{U}} v_{\boldsymbol{u}} \psi_{\boldsymbol{u}}. \end{align}\] Since \(\psi_{\boldsymbol{u}}\) and \(\psi_{\boldsymbol{u}'}\) have disjoint support for \(\boldsymbol{u} \neq \boldsymbol{u}'\), we have \(\phi_{\boldsymbol{v}} \in \mathcal{H}_{t_*^{(k)}}^{\beta_*^{(k)}}\bigl([0,1]^{t_*^{(k)}}, t_*^{(k)}\bigr)\). For \(r< r_*^{(k)}\), if \(d_{r+1}^{(k)} \leq d_{r}^{(k)}\), then we define \(\boldsymbol{g}_r^{(k)} : [0,1]^{d_{r}^{(k)}} \to [0,1]^{d_{r+1}^{(k)}}\) by \(\boldsymbol{g}_r^{(k)}(\boldsymbol{x}) \mathrel{\vcenter{:}}= (x_1,\ldots,x_{d_{r+1}^{(k)}})^\top\); otherwise, we define \(\boldsymbol{g}_r^{(k)} : [0,1]^{d_{r}^{(k)}} \to [0,1]^{d_{r+1}^{(k)}}\) by \(\boldsymbol{g}_r^{(k)}(\boldsymbol{x}) \mathrel{\vcenter{:}}= (\boldsymbol{x}, 0,\ldots,0)^\top\). For \(r > r_*^{(k)}\), define \(\boldsymbol{g}_r^{(k)} : [0,1]^{d_{r}^{(k)}} \to [0,1]^{d_{r+1}^{(k)}}\) by \(\boldsymbol{g}_r^{(k)}(\boldsymbol{x}) \mathrel{\vcenter{:}}= (x_1^{\beta_r^{(k)} \wedge 1}, 0,\ldots,0)^\top\). For \(\boldsymbol{v} \in \{0,1\}^{|\mathcal{U}|}\), define \(\boldsymbol{g}_{r_*^{(k)},\boldsymbol{v}}^{(k)}: [0,1]^{d_{r_*^{(k)}}^{(k)}} \to [0,1]^{d_{r_*^{(k)}+1}^{(k)}}\) by \(\boldsymbol{g}_{r_*^{(k)},\boldsymbol{v}}^{(k)}(\boldsymbol{x}) \mathrel{\vcenter{:}}= \bigl(\phi_{\boldsymbol{v}}(x_1,\ldots,x_{t_*^{(k)}}), 0, \ldots, 0\bigr)^\top\). Then each component of \(\boldsymbol{g}_r^{(k)}\) belongs to \(\mathcal{H}_{t^{(k)}_r}^{\beta^{(k)}_r} ([0,1]^{d_{r}^{(k)}}, \gamma^{(k)}_r)\) for \(r\in[q_k] \setminus \{r_*^{(k)}\}\), and each component of \(\boldsymbol{g}_{r_*^{(k)},\boldsymbol{v}}^{(k)}\) belongs to \(\mathcal{H}_{t^{(k)}_{*}}^{\beta^{(k)}_*} ([0,1]^{d_{r_*^{(k)}}^{(k)}}, \gamma^{(k)}_*)\) for \(\boldsymbol{v} \in \{0,1\}^{|\mathcal{U}|}\). Let \(B \mathrel{\vcenter{:}}= \prod_{r=r_*^{(k)}+1}^{q_k} (\beta_r^{(k)} \wedge 1) = \bar{\beta}_*^{(k)} / \beta_*^{(k)}\). For \(\boldsymbol{v} = (v_{\boldsymbol{u}})_{\boldsymbol{u} \in \mathcal{U}} \in \{0,1\}^{|\mathcal{U}|}\), define \(f^{(k)}_{\boldsymbol{v}} : [0,1]^d \to [0,1/2]\) by \[\begin{align} f^{(k)}_{\boldsymbol{v}}(\boldsymbol{x}) &\mathrel{\vcenter{:}}= \frac{1}{2}\boldsymbol{g}_{q_k}^{(k)} \circ \cdots \circ \boldsymbol{g}_{r_*^{(k)}+1}^{(k)} \circ \boldsymbol{g}_{r_*^{(k)},\boldsymbol{v}}^{(k)} \circ \boldsymbol{g}_{r_*^{(k)}-1}^{(k)} \circ \cdots \circ \boldsymbol{g}_{1}^{(k)}(\boldsymbol{x})\\ &\phantom{:}= \frac{1}{2}\phi_{\boldsymbol{v}}(\boldsymbol{x})^B = \frac{1}{2}\sum_{\boldsymbol{u} \in \mathcal{U}} v_{\boldsymbol{u}} \psi_{\boldsymbol{u}}(x_1,\ldots,x_{t_*^{(k)}})^B, \end{align}\] which satisfies \(f^{(k)}_{\boldsymbol{v}} \in \mathcal{F}^{(k)}\) by construction. For \(\boldsymbol{u} \in \mathcal{U}\), we have \(\|\psi_{\boldsymbol{u}}^B\|_{L_2}^2 = \rho^{2\bar{\beta}_*^{(k)} + t_*^{(k)}} \|h^B\|_{L_2}^{2t_*^{(k)}}\). Therefore, for \(\boldsymbol{v}, \boldsymbol{v}' \in \{0,1\}^{|\mathcal{U}|}\), \[\begin{align} \|f^{(k)}_{\boldsymbol{v}} - f^{(k)}_{\boldsymbol{v}'}\|_{L_2}^2 = \frac{1}{4}\|\boldsymbol{v} - \boldsymbol{v}'\|_1 \cdot \rho^{2\bar{\beta}_*^{(k)} + t_*^{(k)}} \|h^B\|_{L_2}^{2t_*^{(k)}}. \label{eq:f95w-difference-upper-bound} \end{align}\tag{29}\] By the Gilbert–Varshamov lemma [75], there exists \(\mathcal{V} \subseteq \{0,1\}^{|\mathcal{U}|}\) such that \(|\mathcal{V}| \geq e^{|\mathcal{U}|/8}\) and \(\|\boldsymbol{v} - \boldsymbol{v}'\|_1 > |\mathcal{U}|/4\) for all \(\boldsymbol{v}, \boldsymbol{v}' \in \mathcal{V}\) with \(\boldsymbol{v} \neq \boldsymbol{v}'\). Thus, for \(\boldsymbol{v}, \boldsymbol{v}' \in \mathcal{V}\) with \(\boldsymbol{v} \neq \boldsymbol{v}'\), we have by 28 and 29 that \[\begin{align} \int_{[0,1]^d \times \mathcal{S}}\bigl\{f^{(k)}_{\boldsymbol{v}}(\boldsymbol{z}) &- f^{(k)}_{\boldsymbol{v}'}(\boldsymbol{z}) \bigr\}^2 \mathbb{1}_{\{\boldsymbol{\omega}\in\mathcal{S}_k\}} \, \mathrm{d}\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}(\boldsymbol{z}, \boldsymbol{\omega}) = \pi_k \|f^{(k)}_{\boldsymbol{v}} - f^{(k)}_{\boldsymbol{v}'}\|_{L_2}^2\nonumber\\ &> \frac{\pi_k}{4} \cdot \frac{\rho^{-t_*^{(k)}}}{4} \cdot \rho^{2\bar{\beta}_*^{(k)} + t_*^{(k)}} \|h^B\|_{L_2}^{2t_*^{(k)}} \geq \frac{\|h^B\|_{L_2}^{2t_*^{(k)}}}{16 \lambda^{2\bar{\beta}_*^{(k)}}} \cdot \pi_k n_k^{-2\bar{\beta}_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})}. \label{eq:separation-lower-bound} \end{align}\tag{30}\] Moreover, with \(\lambda \mathrel{\vcenter{:}}= 2\Bigl(\frac{100\|h^B\|_{L_2}^{2t_*^{(k)}}}{\xi_2^2}\Bigr)^{1/(2\bar{\beta}_*^{(k)} + t_*^{(k)})} \vee 16\), \[\begin{align} \mathrm{KL}\Bigl(P^{\otimes n}_{f^{(k)}_{\boldsymbol{v}}}, P^{\otimes n}_{f^{(k)}_{\boldsymbol{v}'}}\Bigr) &= n\mathrm{KL}\Bigl(P_{f^{(k)}_{\boldsymbol{v}}}, P_{f^{(k)}_{\boldsymbol{v}'}}\Bigr) \nonumber \\ &= \frac{25n}{2\xi_2^2} \cdot \int_{[0,1]^d \times \mathcal{S}}\bigl\{f^{(k)}_{\boldsymbol{v}}(\boldsymbol{z}) - f^{(k)}_{\boldsymbol{v}'}(\boldsymbol{z}) \bigr\}^2 \mathbb{1}_{\{\boldsymbol{\omega}\in\mathcal{S}_k\}} \, \mathrm{d}\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}(\boldsymbol{z}, \boldsymbol{\omega}) \nonumber\\ &= \frac{25n\pi_k}{2\xi_2^2} \|f^{(k)}_{\boldsymbol{v}} - f^{(k)}_{\boldsymbol{v}'}\|_{L_2}^2 \leq \frac{25\|h^B\|_{L_2}^{2t_*^{(k)}}}{8\xi_2^2} \cdot n_k \rho^{2\bar{\beta}_*^{(k)}} \nonumber\\ &\leq \frac{1}{32\rho^{t_*^{(k)}}} \leq \frac{\log(|\mathcal{V}|)}{4}. \label{eq:kl-upper-bound} \end{align}\tag{31}\] By applying Fano’s lemma [75] in conjunction with 30 and 31 , we conclude that there exists \(c^{(k)} > 0\), depending only on \((\xi_2, \bar{\beta}_*^{(k)}, t_*^{(k)})\), such that \[\begin{align} &\inf_{\widehat{f} \in \widehat{\mathcal{F}}} \sup_{f^{(k)} \in \mathcal{F}^{(k)}} \mathbb{E}_{P_{f^{(k)}}^{\otimes n}}\int_{[0,1]^d \times \mathcal{S}} \bigl\{\widehat{f}(\boldsymbol{z},\boldsymbol{\omega}) - f^{(k)}(\boldsymbol{z})\bigr\}^2 \mathbb{1}_{\{\boldsymbol{\omega}\in\mathcal{S}_k\}} \, \mathrm{d}\mu_{\boldsymbol{Z}_0,\boldsymbol{\Omega}_0}(\boldsymbol{z}, \boldsymbol{\omega}) \nonumber\\ &\geq c^{(k)} \pi_k n_k^{-2\bar{\beta}_*^{(k)} / (2\bar{\beta}_*^{(k)} + t_*^{(k)})}. \label{eq:minimax-lb-kth-term} \end{align}\tag{32}\] The final result follows from 27 and 32 . ◻

13 Auxiliary lemmas↩︎

Lemma 7. For \(c\geq 4\) and \(d\geq 1\), if \(m \geq 0\) satisfies \(2^m \leq (cm)^d\), then \(m\leq 2d\log_2(cd)\).

Proof. First, in the case \(d=1\), we have that \(x \geq 0\) satisfies \(2^x\leq cx\) if and only if \(f(x)\mathrel{\vcenter{:}}= x-\log_2 x - \log_2 c \leq 0\). Since \(f'(x) \geq 0\) for \(x \geq \log_2 e\), any \(m_0\geq \log_2 e\) satisfying \(f(m_0) > 0\) is an upper bound of \(m\). But for \(m_0 = 2\log_2 c\), \[f(m_0) = \log_2 c - \log_2\log_2 c - 1 \geq 0\] for all \(c \geq 4\). Hence \(m\leq m_0\) as desired. For general \(d\geq 1\), defining \(y \mathrel{\vcenter{:}}= m/d\), we have \(2^y\leq cd y\), so the result follows from the case \(d=1\). ◻

Lemma 8. Let \(Y\) be a random variable such that \(\|Y\|_{\psi_2} \leq \xi\) for some \(\xi > 0\). Let \(Z\) be a random variable taking values in a measurable space \(\mathcal{Z}\). Writing \(B_n\mathrel{\vcenter{:}}= \xi\sqrt{2\log n}\), we have \[\begin{align} \mathbb{E}\{|Y - T_{B_n}Y|\} \leq \frac{\sqrt{\pi}\xi}{n^2}, \quad \mathbb{E}\bigl\{Y^2 - (T_{B_n}Y)^2\bigr\} \leq \frac{2\xi^2}{n^2} \end{align}\] and \[\begin{align} \mathbb{E}\Bigl\{\bigl(\mathbb{E}(Y\,|\,Z)\bigr)^2 - \bigl(\mathbb{E}(T_{B_n}Y\,|\,Z)\bigr)^2 \Bigr\} \leq \frac{4\xi^2}{n}, \, \Bigl|\mathbb{E}\Bigl\{\mathbb{E}(Y\,|\,Z)Y - \mathbb{E}(T_{B_n}Y\,|\,Z) \cdot T_{B_n}Y\Bigr\}\Bigr| \leq \frac{4\xi^2}{n}. \end{align}\]

Proof. By Markov’s inequality, \[\begin{align} \mathbb{P}(|Y|\geq t) \leq \mathbb{E}(e^{|Y|^2/\xi^2}) \cdot e^{-t^2/\xi^2} \leq 2e^{-t^2/\xi^2}, \end{align}\] for all \(t\geq 0\). For the first inequality, \[\begin{align} \mathbb{E}\{|Y - T_{B_n}Y|\} &= \int_0^{\infty} \mathbb{P}(|Y - T_{B_n}Y| \geq t) \,\mathrm{d}t\\ &\leq \int_0^{\infty} \mathbb{P}(|Y| \geq B_n + t) \,\mathrm{d}t\\ &\leq 2\int_0^{\infty} e^{-(B_n^2 + t^2)/\xi^2}\,\mathrm{d}t = \frac{2}{n^2} \int_0^{\infty} e^{-t^2/\xi^2}\,\mathrm{d}t = \frac{\sqrt{\pi} \xi}{n^2}. \end{align}\] For the second inequality, \[\begin{align} \mathbb{E}\bigl\{Y^2 - (T_{B_n}Y)^2\bigr\} &= \int_0^{\infty} \mathbb{P}\bigl(Y^2 - (T_{B_n}Y)^2 \geq t\bigr)\,\mathrm{d}t\\ &\leq \int_0^{\infty} \mathbb{P}\bigl(Y^2 \geq B_n^2 + t\bigr) \,\mathrm{d}t \leq 2 \int_0^{\infty} e^{-(B_n^2 + t)/\xi^2} \,\mathrm{d}t = \frac{2\xi^2}{n^2}. \end{align}\] For the third inequality, by the Cauchy–Schwarz inequality, \[\begin{align} \mathbb{E}\Bigl\{\bigl(\mathbb{E}&(Y\,|\,Z)\bigr)^2 - \bigl(\mathbb{E}(T_{B_n}Y\,|\,Z)\bigr)^2 \Bigr\}\nonumber\\ &= \mathbb{E}\Bigl\{\bigl(\mathbb{E}(Y\,|\,Z) -\mathbb{E}(T_{B_n}Y\,|\,Z)\bigr) \cdot \bigl(\mathbb{E}(Y\,|\,Z) +\mathbb{E}(T_{B_n}Y\,|\,Z)\bigr) \Bigr\} \nonumber\\ &\leq \sqrt{\mathbb{E}\Bigl\{\bigl(\mathbb{E}(Y-T_{B_n}Y\,|\,Z)\bigr)^2\Bigr\} \cdot \mathbb{E}\Bigl\{2\bigl(\mathbb{E}(Y\,|\,Z)\bigr)^2 + 2\bigl(\mathbb{E}(T_{B_n}Y\,|\,Z)\bigr)^2 \Bigr\}}. \label{eq:truncation-ineq-5} \end{align}\tag{33}\] Moreover, by the conditional version of Jensen’s inequality, \[\begin{align} \mathbb{E}\Bigl\{\bigl(\mathbb{E}(Y-T_{B_n}Y\,|\,Z)\bigr)^2\Bigr\} \leq \mathbb{E}\Bigl\{\mathbb{E}\bigl((Y-T_{B_n}Y)^2\,|\,Z\bigr)\Bigr\} \leq \mathbb{E}\bigl\{Y^2 - (T_{B_n}Y)^2\bigr\} \leq \frac{2\xi^2}{n^2}, \label{eq:truncation-ineq-6} \end{align}\tag{34}\] and \[\begin{align} \mathbb{E}\Bigl\{2\bigl(\mathbb{E}(Y\,|\,Z)\bigr)^2 + 2\bigl(\mathbb{E}(&T_{B_n}Y\,|\,Z)\bigr)^2 \Bigr\} \leq \mathbb{E}\Bigl\{2\mathbb{E}(Y^2\,|\,Z) + 2\mathbb{E}\bigl((T_{B_n}Y)^2\,|\,Z\bigr) \Bigr\}\nonumber\\ &\leq 4\mathbb{E}(Y^2) = 4 \int_0^{\infty} \mathbb{P}(Y^2\geq t)\,\mathrm{d}t \leq 8 \int_0^{\infty} e^{-t/\xi^2}\,\mathrm{d}t = 8\xi^2. \label{eq:truncation-ineq-7} \end{align}\tag{35}\] The third inequality then follows by combining 33 , 34 and 35 .

Finally, for the fourth inequality, by Cauchy–Schwarz again, \[\begin{align} \Bigl|\mathbb{E}\Bigl\{\mathbb{E}&(Y\,|\,Z)Y - \mathbb{E}(T_{B_n}Y\,|\,Z) \cdot T_{B_n}Y\Bigr\}\Bigr|\nonumber\\ &\leq \Bigl|\mathbb{E}\Bigl\{\mathbb{E}(Y\,|\,Z)(Y-T_{B_n}Y)\Bigr\}\Bigr| + \Bigl|\mathbb{E}\Bigl\{\bigl( \mathbb{E}(Y\,|\,Z)-\mathbb{E}(T_{B_n}Y\,|\,Z) \bigr) \cdot T_{B_n}Y\Bigr\}\Bigr| \nonumber\\ &\leq \sqrt{\mathbb{E}\bigl\{\bigl(\mathbb{E}(Y\,|\,Z)\bigr)^2\bigr\}\cdot \mathbb{E}\bigl\{(Y-T_{B_n}Y)^2\bigr\}} + B_n \mathbb{E}\bigl\{ \bigl| \mathbb{E}(Y - T_{B_n}Y\,|\,Z) \bigr| \bigr\}. \label{eq:truncation-ineq-1} \end{align}\tag{36}\] Now, by 35 , \[\begin{align} \mathbb{E}\bigl\{\bigl(\mathbb{E}(Y\,|\,Z)\bigr)^2\bigr\} \leq \mathbb{E}(Y^2) \leq 2\xi^2, \label{eq:truncation-ineq-2} \end{align}\tag{37}\] and \[\begin{align} \mathbb{E}\bigl\{(Y-T_{B_n}Y)^2\bigr\} \leq \mathbb{E}\bigl\{Y^2-(T_{B_n}Y)^2\bigr\} \leq \frac{2\xi^2}{n^2}. \label{eq:truncation-ineq-3} \end{align}\tag{38}\] Lastly, \[\begin{align} \mathbb{E}\bigl\{ \bigl| \mathbb{E}(Y - T_{B_n}Y\,|\,Z) \bigr| \bigr\} \leq \mathbb{E}\bigl(|Y - T_{B_n}Y|\bigr) \leq \frac{\sqrt{\pi}\xi}{n^2}. \label{eq:truncation-ineq-4} \end{align}\tag{39}\] Combining 36 , 37 , 38 and 39 yields that \[\begin{align} \Bigl|\mathbb{E}\Bigl\{\mathbb{E}(Y\,|\,Z)Y - \mathbb{E}(T_{B_n}Y\,|\,Z) \cdot T_{B_n}Y\Bigr\}\Bigr| \leq \frac{4\xi^2}{n}, \end{align}\] as desired. ◻

Lemma 9. Let \(\beta,\gamma>0\), \(\beta_0 \mathrel{\vcenter{:}}= \lceil\beta\rceil - 1\), \(d\in\mathbb{N}\) and \(g\in \mathcal{H}_d^{\beta}\bigl([0,1]^d,\gamma\bigr)\). Then \[\begin{align} \biggl| g(\boldsymbol{y}) - \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\partial^{\boldsymbol{\alpha}}g(\boldsymbol{x})}{\boldsymbol{\alpha}!}(\boldsymbol{y} - \boldsymbol{x})^{\boldsymbol{\alpha}} \biggr| \leq \gamma d^{\beta_0} \|\boldsymbol{y} - \boldsymbol{x}\|_2^{\beta} \end{align}\] for all \(\boldsymbol{x},\boldsymbol{y} \in [0,1]^d\).

Proof. Let \(\boldsymbol{u} \mathrel{\vcenter{:}}= \boldsymbol{y} - \boldsymbol{x}\). By Taylor’s theorem, there exists \(\theta\in(0,1)\) such that \[\begin{align} g(\boldsymbol{y}) = \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0-1} \frac{\partial^{\boldsymbol{\alpha}}g(\boldsymbol{x})}{\boldsymbol{\alpha}!}\boldsymbol{u}^{\boldsymbol{\alpha}} + \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 = \beta_0} \frac{\partial^{\boldsymbol{\alpha}}g(\boldsymbol{x} + \theta\boldsymbol{u})}{\boldsymbol{\alpha}!}\boldsymbol{u}^{\boldsymbol{\alpha}}. \end{align}\] Thus, \[\begin{align} \biggl| g(\boldsymbol{y}) - \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 \leq \beta_0} \frac{\partial^{\boldsymbol{\alpha}}g(\boldsymbol{x})}{\boldsymbol{\alpha}!} \boldsymbol{u}^{\boldsymbol{\alpha}} \biggr| &\leq \sum_{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 = \beta_0} \bigl|\partial^{\boldsymbol{\alpha}}g(\boldsymbol{x} + \theta\boldsymbol{u}) - \partial^{\boldsymbol{\alpha}}g(\boldsymbol{x})\bigr| \boldsymbol{u}^{\boldsymbol{\alpha}}\\ &\leq d^{\beta_0} \gamma \|\boldsymbol{u}\|_2^{\beta-\beta_0}\cdot \|\boldsymbol{u}\|_2^{\beta_0} \end{align}\] where the final inequality uses the facts that \(\bigl|\{\boldsymbol{\alpha} \in \mathbb{N}_0^d : \|\boldsymbol{\alpha}\|_1 = \beta_0\}\bigr|= \binom{d+\beta_0-1}{\beta_0}\leq d^{\beta_0}\), that \(g \in \mathcal{H}_d^{\beta}\bigl([0,1]^d,\gamma\bigr)\) and that \(\boldsymbol{u}^{\boldsymbol{\alpha}} = \prod_{j=1}^d u_j^{\alpha_j} \leq \|\boldsymbol{u}\|_{\infty}^{\beta_0} \leq \|\boldsymbol{u}\|_2^{\beta_0}\). ◻

Lemma 10. Given an arbitrary partition \(\{\mathcal{S}_1,\ldots,\mathcal{S}_K\}\) of \(\mathcal{S}\), there exists a Bayes regression function \(f^{\star}\) that satisfies Assumption 1.

Proof. Indeed, let \(\boldsymbol{X} = (X_1,\ldots,X_d)^\top \sim \mathrm{Unif}[0,1]^d\) and let \(Y = \sum_{k=1}^K \mathbb{1}_{\{X_{1}\geq (k-1)/K\}} + \varepsilon\) where \(\varepsilon \sim N(0,1)\) is independent of \(\boldsymbol{X}\). Further define \(\boldsymbol{\Omega}\) by \(\boldsymbol{\Omega} \,|\, \boldsymbol{X} \sim \mathrm{Unif}( \mathcal{S}_k)\) when \(X_1 \in \bigl[(k-1)/K,k/K\bigr)\). Then \(f^{\star}(\boldsymbol{z},\boldsymbol{\omega}) = k\) for all \(\boldsymbol{z} \in [0,1]^d\) whenever \(\boldsymbol{\omega}\in\mathcal{S}_k\). ◻

14 Visualisation of the learned pattern embeddings for synthetic data↩︎

In Figures 10–13, we plot visualisations of the learned embeddings for our synthetic data examples from Models 1–4 in Section 4.1. Since the original embeddings were in four dimensions, we plot the first two principal components for the visualisations. The clustering structure of the different colours in these figures reinforces the message that the embeddings of the revelation vectors contain relevant information for predictive performance. In some cases, such as Figure 11, the clusters may be almost disjoint, while in others, such as Figure 10, there may be non-trivial overlap between the clusters, at least following the projection onto the first two principal components.

References↩︎

[1]

Krizhevsky, A., Sutskever, I. and Hinton, G. E. (2012) Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems, 25.

[2]

He, K., Zhang, X., Ren, S. and Sun, J. (2016) Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 770–778.

[3]

Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žı́dek, A., Potapenko, A., Bridgland, A., Meyer, C., Kohl, S. A. A., Ballard, A. J., Cowie, A., Romera-Paredes, B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen, S., Reiman, D., Clancy, E., Zielinski, M., Steinegger, M., Pacholska, M., Berghammer, T., Bodenstein, S., Silver, D., Vinyals, O., Senior, A. W., Kavukcuoglu, K., Kohli, P. and Hassabis, D. (2021) Highly accurate protein structure prediction with AlphaFold. Nature, 596, 583–589.

[4]

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł. and Polosukhin, I. (2017) Attention is all you need. Advances in Neural Information Processing Systems, 30.

[5]

Devlin, J., Chang, M.-W., Lee, K. and Toutanova, K. (2019) Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (long and short papers), 4171–4186.

[6]

Jacot, A., Gabriel, F. and Hongler, C. (2018) Neural tangent kernel: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems, 31.

[7]

Schmidt-Hieber, J. (2020) Nonparametric regression using deep neural networks with ReLU activation function. Annals of Statistics, 48, 1875–1897.

[8]

Kohler, M. and Langer, S. (2021) On the rate of convergence of fully connected deep neural network regression estimates. Annals of Statistics, 49, 2231–2249.

[9]

Mei, S. and Montanari, A. (2022) The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75, 667–766.

[10]

Suh, N. and Cheng, G. (2024) A survey on statistical theory of deep learning: Approximation, training dynamics, and generative models. Annual Review of Statistics and Its Application, 12, 177–207.

[11]

Zhu, Z., Wang, T. and Samworth, R. J. (2022) High-dimensional principal component analysis with heterogeneous missingness. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84, 2000–2031.

[12]

Loh, P.-L. and Wainwright, M. J. (2012) High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity. Annals of Statistics, 40, 1637–1664.

[13]

Chandrasekher, K. A., Alaoui, A. E. and Montanari, A. (2020) Imputation for high-dimensional linear regression. arXiv preprint arXiv:2001.09180.

[14]

Elsener, A. and van de Geer, S. (2019) Sparse spectral estimation with missing and corrupted measurements. Stat, 8, e229.

[15]

Cai, T. T. and Zhang, L. (2019) High dimensional linear discriminant analysis: optimality, adaptive algorithm and missing data. Journal of the Royal Statistical Society, Series B: Statistical Methodology, 81, 675–705.

[16]

Sell, T., Berrett, T. B. and Cannings, T. I. (2024) Nonparametric classification with missing data. Annals of Statistics, 52, 1178–1200.

[17]

Follain, B., Wang, T. and Samworth, R. J. (2022) High-dimensional changepoint estimation with heterogeneous missingness. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84, 1023–1055.

[18]

Ma, T., Verchand, K. A., Berrett, T. B., Wang, T. and Samworth, R. J. (2026+) Estimation beyond Missing (Completely) at Random. Annals of Statistics (to appear).

[19]

Kingma, D. P. and Ba, J. (2015) Adam: A method for stochastic optimization. In International Conference on Learning Representations.

[20]

Loshchilov, I. and Hutter, F. (2019) Decoupled weight decay regularization. In International Conference on Learning Representations.

[21]

Stekhoven, D. J. and Bühlmann, P. (2012) MissForest—non-parametric missing value imputation for mixed-type data. Bioinformatics, 28, 112–118.

[22]

van Buuren, S. and Groothuis-Oudshoorn, K. (2011) mice: Multivariate imputation by chained equations in R. Journal of Statistical Software, 45, 1–67.

[23]

Chen, T. and Guestrin, C. (2016) XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 785–794.

[24]

Breiman, L. (2001) Random forests. Machine Learning, 45, 5–32.

[25]

Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J. and Houlsby, N. (2021) An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations.

[26]

Bauer, B. and Kohler, M. (2019) On deep learning as a remedy for the curse of dimensionality in nonparametric regression. Annals of Statistics, 47, 2261–2285.

[27]

Imaizumi, M. and Fukumizu, K. (2019) Deep neural networks learn non-smooth functions effectively. In The 22nd International Conference on Artificial Intelligence and Statistics, 869–878, PMLR.

[28]

Jiao, Y., Shen, G., Lin, Y. and Huang, J. (2023) Deep nonparametric regression on approximate manifolds: Nonasymptotic error bounds with polynomial prefactors. Annals of Statistics, 51, 691–716.

[29]

Bhattacharya, S., Fan, J. and Mukherjee, D. (2024) Deep neural networks for nonparametric interaction models with diverging dimension. Annals of Statistics, 52, 2738–2766.

[30]

Fan, J. and Gu, Y. (2024) Factor augmented sparse throughput deep ReLU neural networks for high dimensional regression. Journal of the American Statistical Association, 119, 2680–2694.

[31]

Bos, T. and Schmidt-Hieber, J. (2022) Convergence rates of deep ReLU networks for multiclass classification. Electronic Journal of Statistics, 16, 2724–2773.

[32]

Zhang, Z., Shi, L. and Zhou, D.-X. (2024) Classification with deep neural networks and logistic loss. Journal of Machine Learning Research, 25, 1–117.

[33]

Zhong, Q., Mueller, J. and Wang, J.-L. (2022) Deep learning for the partially linear Cox model. Annals of Statistics, 50, 1348–1375.

[34]

Bos, T. and Schmidt-Hieber, J. (2024) A supervised deep learning method for nonparametric density estimation. Electronic Journal of Statistics, 18, 5601–5658.

[35]

Lu, J., Shen, Z., Yang, H. and Zhang, S. (2021) Deep network approximation for smooth functions. SIAM Journal on Mathematical Analysis, 53, 5465–5506.

[36]

Du, S. S., Zhai, X., Poczos, B. and Singh, A. (2019) Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations.

[37]

Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R. and Wang, R. (2019) On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32.

[38]

Yang, G. and Hu, E. J. (2021) Tensor Programs IV: Feature Learning in Infinite-Width Neural Networks. In International Conference on Machine Learning, PMLR.

[39]

Littwin, E. and Yang, G. (2023) Adaptive optimization in the \(\infty\)-width limit. In The Eleventh International Conference on Learning Representations.

[40]

Chizat, L. and Bach, F. (2018) On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in Neural Information Processing Systems, 31.

[41]

Mei, S., Montanari, A. and Nguyen, P.-M. (2018) A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115, E7665–E7671.

[42]

Suzuki, T., Wu, D. and Nitanda, A. (2023) Convergence of mean-field langevin dynamics: time-space discretization, stochastic gradient, and variance reduction. Advances in Neural Information Processing Systems, 36, 15545–15577.

[43]

Hollmann, N., Müller, S., Purucker, L., Krishnakumar, A., Körfer, M., Hoo, S. B., Schirrmeister, R. T. and Hutter, F. (2025) Accurate predictions on small data with a tabular foundation model. Nature, 637, 319–326.

[44]

Kim, J., Nakamaki, T. and Suzuki, T. (2024) Transformers are minimax optimal nonparametric in-context learners. Advances in Neural Information Processing Systems, 37, 106667–106713.

[45]

Ma, T., Wang, T. and Samworth, R. J. (2025) Optimal in-context adaptivity and distributional robustness of Transformers. arXiv preprint arXiv:2510.23254.

[46]

Ching, M., Popescu, I., Smith, N., Ma, T., Underwood, W. G. and Samworth, R. J. (2026) Efficient and minimax-optimal in-context nonparametric regression with transformers. International Conference on Machine Learning, to appear.

[47]

Mikolov, T., Chen, K., Corrado, G. and Dean, J. (2013) Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781.

[48]

Guo, C. and Berkhahn, F. (2016) Entity embeddings of categorical variables. arXiv preprint arXiv:1604.06737.

[49]

Hinton, G. E. and Salakhutdinov, R. R. (2006) Reducing the dimensionality of data with neural networks. Science, 313, 504–507.

[50]

Vincent, P., Larochelle, H., Bengio, Y. and Manzagol, P.-A. (2008) Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th International Conference on Machine Learning, 1096–1103.

[51]

Berrett, T. B. and Samworth, R. J. (2023) Optimal nonparametric testing of Missing Completely At Random, and its connections to compatibility. Annals of Statistics, 51, 2170–2193.

[52]

Li, S. C.-X., Jiang, B. and Marlin, B. (2019) MisGAN: Learning from incomplete data with generative adversarial networks. In International Conference on Learning Representations.

[53]

Mattei, P.-A. and Frellsen, J. (2019) MIWAE: Deep generative modelling and imputation of incomplete data sets. In International Conference on Machine Learning, 4413–4423, PMLR.

[54]

Nazabal, A., Olmos, P. M., Ghahramani, Z. and Valera, I. (2020) Handling incomplete heterogeneous data using VAEs. Pattern Recognition, 107, 107501.

[55]

Zhang, H., Fang, L., Wu, Q. and Yu, P. S. (2025) DiffPuter: An EM-driven diffusion model for missing data imputation. In The Thirteenth International Conference on Learning Representations.

[56]

Le Morvan, M., Josse, J., Scornet, E. and Varoquaux, G. (2021) What’s a good imputation to predict with missing values? Advances in Neural Information Processing Systems, 34, 11530–11540.

[57]

Josse, J., Chen, J. M., Prost, N., Varoquaux, G. and Scornet, E. (2024) On the consistency of supervised learning with missing values. Statistical Papers, 65, 5447–5479.

[58]

Efromovich, S. (2011) Nonparametric regression with predictors missing at random. Journal of the American Statistical Association, 106, 306–319.

[59]

Twala, B. E., Jones, M. and Hand, D. J. (2008) Good methods for coping with missing data in decision trees. Pattern Recognition Letters, 29, 950–956.

[60]

Śmieja, M., Struski, Ł., Tabor, J., Zieliński, B. and Spurek, P. (2018) Processing of missing data by neural networks. Advances in Neural Information Processing Systems, 31.

[61]

Bao, H., Dong, L., Piao, S. and Wei, F. (2022) BEiT: BERT Pre-Training of Image Transformers. In International Conference on Learning Representations.

[62]

He, K., Chen, X., Xie, S., Li, Y., Dollár, P. and Girshick, R. (2022) Masked autoencoders are scalable vision learners. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 16000–16009.

[63]

Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Köpf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J. and Chintala, S. (2019) Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32.

[64]

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M. and Duchesnay, E. (2011) Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12, 2825–2830.

[65]

Liu, Z., Sun, M., Zhou, T., Huang, G. and Darrell, T. (2019) Rethinking the value of network pruning. In International Conference on Learning Representations.

[66]

Prechelt, L. (2002) Early stopping – but when? In Neural Networks: Tricks of the Trade(Orr, G. B. and Müller, K.-R., eds.), 55–69, Springer.

[67]

LeCun, Y., Cortes, C. and Burges, C. J. C. (1998) The MNIST database of handwritten digits. https://yann.lecun.com/exdb/mnist/.

[68]

Zhang, W., Tanida, J., Itoh, K. and Ichioka, Y. (1988) Shift-invariant pattern recognition neural network and its optical architecture. In Proceedings of annual conference of the Japan Society of Applied Physics, vol. 564, Montreal, CA.

[69]

LeCun, Y., Bottou, L., Bengio, Y. and Haffner, P. (1998) Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86, 2278–2324.

[70]

Fan, J., Ma, C. and Zhong, Y. (2020) A selective overview of deep learning. Statistical Science, 36, 264–290.

[71]

Bartlett, P. L., Harvey, N., Liaw, C. and Mehrabian, A. (2019) Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20, 1–17.

[72]

Györfi, L., Kohler, M., Krzyzak, A. and Walk, H. (2006) A Distribution-free Theory of Nonparametric Regression. Springer Science & Business Media.

[73]

Royden, H. L. and Fitzpatrick, P. (2010) Real Analysis. Printice-Hall Inc, Boston.

[74]

Shen, Z., Yang, H. and Zhang, S. (2019) Nonlinear approximation via compositions. Neural Networks, 119, 74–84.

[75]

Samworth, R. J. and Shah, R. D. (2026+) Modern Statistical Methods and Theory. Cambridge University Press, Cambridge.

Formally, this set is equipped with the natural topology and \(\sigma\)-algebra described in [18].↩︎
This is assumed for theoretical convenience. In practice (and indeed in our simulations in Section 4), the neural network and imputation algorithms would be trained on the same dataset.↩︎
More formally, since \(f^\star\) is only defined up to sets having zero measure under the distribution of \((\boldsymbol{Z}_0,\boldsymbol{\Omega}_0)\), we ask that there exists a version of \(f^\star\) for which the statement in Assumption 1 holds.↩︎
For \(D \subseteq \mathbb{R}^d\) and \(f:D \to \mathbb{R}\), we say that \(f\) depends only on \(t\) variables* if there exists \(\mathcal{J} \subseteq [d]\) with \(|\mathcal{J}| = t\) such that for all \(\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^d\) with \(\boldsymbol{x}_{\mathcal{J}} = \boldsymbol{y}_{\mathcal{J}}\), we have \(f(\boldsymbol{x}) = f(\boldsymbol{y})\), where \(\boldsymbol{x}_{\mathcal{J}}, \boldsymbol{y}_{\mathcal{J}} \in \mathbb{R}^t\) denote the subvectors of \(\boldsymbol{x}\) and \(\boldsymbol{y}\) respectively with indices in \(\mathcal{J}\); when \(\mathcal{J} = \emptyset\), this means that \(f\) is constant.*↩︎
Although \(\boldsymbol{g}_{q}\) is a real-valued function, we write it with a bold letter for convenience.↩︎
Here, \(\mathrm{sargmax}\) denotes the smallest element of the \(\mathop{\mathrm{argmax}}\) set.↩︎
We used the implementation from the GitHub repository https://github.com/gejinchen/PyTorch-Vision-Transformer-ViT-MNIST-CIFAR10.↩︎
Although this is not the standard definition of the sign function, it is used elsewhere in the neural network literature [71], and it is convenient for our purposes here.↩︎

Deep learning with missing data

Abstract

1 Introduction↩︎

1.2 Notation↩︎

2 Problem set-up and methodology↩︎

2.1 Problem set-up↩︎

2.2 ReLU neural networks↩︎

2.3 Pattern Embedded Neural Network estimators↩︎

3 Theoretical results↩︎

3.1 Oracle inequality↩︎

3.2 Minimax rate under a piecewise smoothness assumption↩︎

4 Simulations↩︎

4.1 Simulated data↩︎

4.1.0.1 Model 1:

4.1.0.2 Model 2:

4.1.0.3 Model 3:

4.1.0.4 Model 4:

4.2 Semi-synthetic data↩︎

4.2.0.1 Relative location of CT dataset:

4.2.0.2 MNIST dataset:

4.3 Real data↩︎

4.3.0.1 Credit score prediction dataset:

5 Discussion↩︎

Acknowledgement↩︎

6 Some properties of neural networks↩︎

7 Covering number bounds for sparse neural networks↩︎

8 Proof of Proposition 1 ↩︎

8.0.0.1 Bounding \(E_1\):

8.0.0.2 Bounding \(E_2 + E_5\):

8.0.0.3 Bounding \(E_3\):

8.0.0.4 Bounding \(E_4\):

9 \(\mathcal{F}\)-separability of partitions of \(\mathcal{S}\)↩︎

10 Approximation theory for neural networks↩︎

11 Proof of Theorem 2 ↩︎

12 Proof of Theorem 3 ↩︎

13 Auxiliary lemmas↩︎

14 Visualisation of the learned pattern embeddings for synthetic data↩︎

References↩︎

Subjects

Updated on Academus

Deep learning with missing data

Abstract

1 Introduction↩︎

1.1 Related literature↩︎

1.2 Notation↩︎

2 Problem set-up and methodology↩︎

2.1 Problem set-up↩︎

2.2 ReLU neural networks↩︎

2.3 Pattern Embedded Neural Network estimators↩︎

3 Theoretical results↩︎

3.1 Oracle inequality↩︎

3.2 Minimax rate under a piecewise smoothness assumption↩︎

4 Simulations↩︎

4.1 Simulated data↩︎

4.1.0.1 Model 1:

4.1.0.2 Model 2:

4.1.0.3 Model 3:

4.1.0.4 Model 4:

4.2 Semi-synthetic data↩︎

4.2.0.1 Relative location of CT dataset:

4.2.0.2 MNIST dataset:

4.3 Real data↩︎

4.3.0.1 Credit score prediction dataset:

5 Discussion↩︎

Acknowledgement↩︎

6 Some properties of neural networks↩︎

7 Covering number bounds for sparse neural networks↩︎

8 Proof of Proposition 1↩︎

8.0.0.1 Bounding \(E_1\):

8.0.0.2 Bounding \(E_2 + E_5\):

8.0.0.3 Bounding \(E_3\):

8.0.0.4 Bounding \(E_4\):

9 \(\mathcal{F}\)-separability of partitions of \(\mathcal{S}\)↩︎

10 Approximation theory for neural networks↩︎

11 Proof of Theorem 2↩︎

12 Proof of Theorem 3↩︎

13 Auxiliary lemmas↩︎

14 Visualisation of the learned pattern embeddings for synthetic data↩︎

References↩︎

Subjects

Updated on Academus

8 Proof of Proposition 1 ↩︎

11 Proof of Theorem 2 ↩︎

12 Proof of Theorem 3 ↩︎