# Optimal minimax random designs for weighted least squares estimators

David Azriel, Technion – Israel Institute of Technology

###### Abstract

This work studies an experimental design problem where the values of a
predictor variable, denoted by $x$, are to be determined with the goal of
estimating a function $m(x)$, which is observed with noise. A linear model is
fitted to $m(x)$ but it is not assumed that the model is correctly specified.
It follows that the quantity of interest is the best linear approximation of
$m(x)$, which is denoted by $\ell(x)$. It is shown that in this framework the
ordinary least squares estimator typically leads to an inconsistent estimation
of $\ell(x)$, and rather weighted least squares should be considered. An
asymptotic minimax criterion is formulated for this estimator, and a design
that minimizes the criterion is constructed. An important feature of this
problem is that the $x$’s should be random, rather than fixed. Otherwise, the
minimax risk is infinite. It is shown that the optimal random minimax design
is different from its deterministic counterpart, which was studied previously,
and a simulation study indicates that it generally performs better when $m(x)$
is a quadratic or a cubic function. Another finding is that when the variance
of the noise goes to infinity, the random and deterministic minimax designs
coincide. The results are illustrated for polynomial regression models and the
general case is also discussed.

Key words: Experimental design, I-optimality, Robust regression.

##  1 Introduction

A fundamental problem in experimental design is to determine the values of a
predictor variable $x$ in order to estimate a function $m(x)$, which is
observed with noise. Specifically, consider a pair $(X,Y)$ of univariate
random variables and suppose that the quantity of interest is $m(x)=E(Y|X=x)$.
Assume also that $X$ can assume values in the interval $[-1,1]$. The
experimenter selects $X_{1},\ldots,X_{n}$, which results in the corresponding
observations $Y_{1},\ldots,Y_{n}$. Then, based on
$(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$ an estimator $\hat{m}(x)$ is considered,
and the question of interest is how to select $X_{1},\ldots,X_{n}$ in order to
minimize $\int_{-1}^{1}E\\{\hat{m}(x)-m(x)\\}^{2}dx$. This problem is referred
to as Q-optimality in Fedorov (2013); other authors (e.g., Wiens, 2015) use
the term I-optimality.

When a polynomial of degree $K$ is used to model $m$, i.e.,
$m(x)=\sum_{k=0}^{K}b_{k}x^{k}$ for some unknown coefficients
$b_{0},\ldots,b_{k}$, which are estimated using least squares, a classical
result shows that the support of the optimal sampling measure contains $K+1$
points. These points can be computed as well as the optimal weights (Kiefer
and Wolfowitz, 1959). For the special case where $m$ is a linear function,
i.e., $m(x)=b_{0}+b_{1}x$, the optimal design is to sample $X=\pm 1$ with
equal weights.

The above designs do not allow one to check the model assumptions and
therefore are not robust to model misspecification. In order to address this
problem, Box and Draper (1959) considered the situation where a polynomial
model of degree $K$ is assumed, but the true function $m$ is a polynomial of
higher degree. This seminal paper started a line of work where model
misspecification is accounted for in order to compute optimal designs. A
review of this literature can be found in Wiens (2015); see also the recent
work of Waite and Woods (2021). A major theme in this literature is that the
bias term is more important than the variance, and therefore one can focus on
designs that minimize the bias. This idea can be summarized in the following
quote from Box and Draper:

> “We are led therefore to a somewhat remarkable conclusion. This is that the
> optimal design in a “typical” situation in which the influence of bias and
> variance are equal is very nearly the same as that obtained when variance is
> ignored completely and the experiment is designed to minimize bias alone.”
> (page 630)

However, as I argue below, this is a result of using the ordinary least
squares estimator, which is inconsistent in this setting to the parameter of
interest – the best linear approximation. When using a consistent estimator,
namely the weighted least squares estimator, the bias term is negligible
compared to the variance.

Another important consideration is the randomness of the design - an idea that
goes back at least to Fisher (1926) and has a long and rich history in
experimental design. It still plays a dominant role in current online A/B
testing (Kohavi and Longbotham, 2017) as well as in recent clinical trials
(Knoll and Wonodi, 2021). Cox (2009) reviews this large body of literature and
mentions three objectives of randomization: the avoidance of bias, error
estimation, and the provision of exact tests. In the context of the current
work, the first of these objectives is essential. Indeed, Wiens (1992) shows
that deterministic designs have infinite minimax risk as the resulting bias
can be arbitrarily large. Waite and Woods (2021) study a random experimental
design strategy in the above setting and construct a specific random design
that has a smaller minimax error than its deterministic counterpart. In the
current work, the random experimental design approach is adopted as detailed
below.

To fix ideas, a simple linear approximation is now considered. The best linear
approximation of $m(x)$ with respect to $X\in U[-1,1]$ is denoted by
$\ell(x)=\beta_{0}+\beta_{1}x$, where

$\left(\begin{array}[]{c}{\beta_{0}}\\\
{\beta_{1}}\end{array}\right)={Q}^{-1}\left(\begin{array}[]{c}\int_{-1}^{1}\frac{1}{2}m(x)dx\\\
{\int_{-1}^{1}\frac{x}{2}m(x)dx}\end{array}\right)\text{ and
}{Q}=\left(\begin{array}[]{cc}1&\int_{-1}^{1}\frac{x}{2}dx\\\
\int_{-1}^{1}\frac{x}{2}dx&\int_{-1}^{1}\frac{x^{2}}{2}dx\end{array}\right)=\left(\begin{array}[]{cc}1&0\\\
0&1/3\end{array}\right);$ (1)

see Section 2.25 of Hansen (2021). For a given estimator of $\ell(x)$, which
is denoted by $\bar{\ell}(x)$ and assumed to be a linear function of $x$, the
experimenter seeks to minimize $\int_{-1}^{1}E\\{\bar{\ell}(x)-m(x)\\}^{2}dx$.
The definition of $\ell(x)$ in (1) implies the orthogonality property of
$\ell(x)$, i.e.,
$\displaystyle{\int_{-1}^{1}\binom{1}{x}}\\{\ell(x)-m(x)\\}dx=\displaystyle{\binom{0}{0}}$;
see also Section 2.18 of Hansen (2021). It follows that

$\int_{-1}^{1}E\\{\bar{\ell}(x)-m(x)\\}^{2}dx=\int_{-1}^{1}E\\{\bar{\ell}(x)-\ell(x)\\}^{2}dx+\int_{-1}^{1}\\{{\ell}(x)-m(x)\\}^{2}dx.$

The second term does not depend on the design and therefore can be ignored.
Continuing with the first term,

$\int_{-1}^{1}E\\{\bar{\ell}(x)-\ell(x)\\}^{2}dx=\int_{-1}^{1}{\rm
var}\\{\bar{\ell}(x)\\}dx+\int_{-1}^{1}[E\\{\bar{\ell}(x)\\}-\ell(x)]^{2}dx.$
(2)

The first term is referred to as the variance and the second as bias in Box
and Draper (1959). As mentioned previously, Box and Draper found that the bias
term dominates the variance. However, this depends on the estimator used, as
explained below.

It is assumed from now on that the experimenter uses a random design strategy,
that is $X_{1},\ldots,X_{n}$ are sampled from a distribution on $[-1,1]$ with
density $\pi(x)$ with respect to the Lebesgue measure. Thus, the design,
$X_{1},\ldots,X_{n}$, is random and the experimenter wishes to find the
optimal $\pi$ according to a minimax criterion, which is defined below. It is
assumed that $\pi(x)>0$ for all $x\in[-1,1]$; otherwise, the risk in (2) could
be infinite for various settings; see Wiens (1992) and Heo et al. (2001). The
corresponding observations are $Y_{1},\ldots,Y_{n}$. The ordinary least
squares estimators, which are denoted by $\hat{\beta}_{0},\hat{\beta}_{1}$,
are a function of $(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$ and the estimate of the
best linear approximation is $\hat{\ell}(x)=\hat{\beta}_{0}+\hat{\beta}_{1}x$.

The important thing to notice here is that $\hat{\ell}(x)$ converges to the
best linear approximation of $m(x)$ with respect to $\pi$, rather than
$\ell(x)$, which is the best linear approximation when $X\in[-1,1]$.
Specifically, the limit of $\hat{\ell}(x)$ is
$\ell_{\pi}(x)=\beta_{0,\pi}+\beta_{1,\pi}x$, where

$\left(\begin{array}[]{c}{\beta_{0,\pi}}\\\
{\beta_{1,\pi}}\end{array}\right)={Q}_{\pi}^{-1}\left(\begin{array}[]{c}\int_{-1}^{1}\pi(x)m(x)dx\\\
{\int_{-1}^{1}x\pi(x)m(x)dx}\end{array}\right)\text{ and
}{Q}_{\pi}=\left(\begin{array}[]{cc}1&\int_{-1}^{1}x\pi(x)dx\\\
\int_{-1}^{1}x\pi(x)dx&\int_{-1}^{1}x^{2}\pi(x)dx\end{array}\right).$

A subscript $\pi$ is used to denote quantities that depend on $\pi$. To
illustrate this point, consider a specific setting where
$m(x)=1/4+x/2+x^{2}/4$ and $\pi$ is the density of truncated $N(1/2,1/4)$ on
the interval $[-1,1]$. This setting is illustrated in Figure 1. For the
truncated normal, more weight is given for large $x$ and therefore the
intercept of $\ell_{\pi}(x)$ is smaller and the slope is larger.

(a) $m(x)$, $\ell(x)$ and $\ell_{\pi}(x)$

(b) Marginal distribtion of $x$

Figure 1: Figure (a): the conditional expectation $m(x)$ (black) and the best
linear approximation for two possible marginal distributions of $X$: uniform
(red) and $\pi=$ truncated $N(1/2,1/4)$ (blue). Figure (b): The densities of
these two distributions.

The above discussion implies that $\hat{\ell}(x)$ is an inconsistent estimator
of $\ell(x)$ unless $\pi$ is the uniform density. This has two consequences:
first, the bias term dominates the variance in (2), and second,
asymptotically, the optimal design is the uniform design. These two findings
were described in Box and Draper (1959) and in other papers; see Section 20.3
of Wiens (2015) for a literature review. However, they are a result of using
an inconsistent estimator, rather than of robustness considerations. Below, a
consistent estimator to $\ell(x)$ is formulated, and it is found, in contrast,
that the bias term vanishes asymptotically and the uniform design is no longer
optimal.

In this framework, there is another reason to consider $X$ as random rather
than fixed, besides the one that was mentioned above. Buja et al. (2019) show
that $X_{1},\ldots,X_{n}$ is ancillary to $\beta_{0},\beta_{1}$, if and only
if $m(x)=\ell(x)$. This means that when the linear model $m(x)=\ell(x)$ is not
assumed, the marginal distribution of $X$ matters, and the conditionality
principle (Cox and Hinkley, 1974, page 38) does not apply, i.e., the $X$’s
should not be conditioned upon.

The goal of this work is to find an optimal density $\pi$ that is optimal in a
minimax sense. Nie et al. (2018) study the analogous problem in the active
learning setting where the purpose is to select predictors from a given
unlabeled dataset according to the minimax criterion. In particular, the
problem addressed in Section 3.1 of Nie et al. (2018) is similar to the one
that is considered in the current work and the theoretical results are similar
in both papers. The current work is also close to Wiens (1998) and Wiens
(2000). A detailed comparison to these works is given below in Section 3.

##  2 Problem formulation

A linear approximation to $m(x)=E(Y|X=x)$ is considered, using the vector of
monomials of $x$, $\vec{x}=(1,x,\dots,x^{K})$; general functions of $x$ are
considered in Section 6 of the supplementary material. The coefficient of the
best linear predictor is
${\beta}={Q}^{-1}\int_{-1}^{1}\frac{1}{2}\vec{x}^{T}m(x)dx$, where
${Q}=\int_{-1}^{1}\frac{1}{2}\vec{x}^{T}\vec{x}dx$. In this notation,
${\beta}$ and $\vec{x}$ are column and row vectors, respectively. The best
linear approximation is the function $\ell(x)=\vec{x}{\beta}$.

The experimenter chooses a density $\pi$ from which $X_{1},\ldots,X_{n}$ are
sampled. Then $Y_{1},\ldots,Y_{n}$ are observed, where

$Y_{i}=m(X_{i})+\varepsilon_{i},$ (3)

and the residuals $\varepsilon_{1},\ldots,\varepsilon_{n}$ are independent and
identically distributed satisfying $E(\varepsilon_{i}^{2}|X_{i})=\sigma^{2}$,
i.e., homoscedasticity is assumed; this assumption is relaxed in Section 4
below. Let $\vec{{X}}_{i}=(1,X_{i},\ldots,X_{i}^{K})$ and define the
regression residuals $e_{i}=Y_{i}-\vec{{X}}_{i}{\beta}$, $i=1,\ldots,n$. The
vector ${\beta}$ is the best linear predictor with respect to $X\sim U[-1,1]$
and not to $X\sim\pi$. Hence, $E_{\pi}(\vec{{X}}_{1}e_{1})$ is not necessarily
zero. However, when $\vec{{X}}_{1}$ is weighted by $1/\pi(X_{i})$, then the
expectation is zero, i.e., $E_{\pi}(\vec{{X}}_{1}e_{1}/\pi(X_{1}))={0}$.

Let ${\mathbb{X}}\in\mathbb{R}^{n\times(K+1)}$ be the matrix with
$\vec{{X}}_{i}$’s in the rows, ${\mathbb{Y}}=(Y_{1},\ldots,Y_{n})^{T}$ and let
${W}_{\pi}\in\mathbb{R}^{n\times n}$ be the diagonal matrix whose $i$-th
diagonal element is $\frac{1/2}{\pi(X_{i})}$. Define

$\tilde{Q}_{\pi}=I({\cal E}_{\pi})n{Q}+I({\cal
E}_{\pi}^{C}){\mathbb{X}}^{T}{W}_{\pi}{\mathbb{X}},$ (4)

where $I$ denotes the indicator function and

${\cal
E}_{\pi}=\\{\lambda_{min}({\mathbb{X}}^{T}{W}_{\pi}{\mathbb{X}}/n)<\lambda_{min}({Q})/2\\},$
(5)

and where $\lambda_{min}$ denotes the smallest eigenvalue. A discussion about
the estimator $\tilde{Q}_{\pi}$ is given below. Define also
$\tilde{V}_{\pi}={\mathbb{X}}^{T}{W}_{\pi}{\mathbb{Y}}$. The weighted least
squares estimate is $\tilde{\beta}_{\pi}=\tilde{Q}_{\pi}^{-1}\tilde{V}_{\pi}$
and the estimate of the best linear approximation is
$\tilde{\ell}_{\pi}(x)=\vec{x}\tilde{\beta}_{\pi}$.

The specific choice of $\tilde{Q}_{\pi}$ in (4) is now discussed. Under the
setting considered here ${Q}$ is known, and hence one can use the estimator
${Q}^{-1}\tilde{V}_{\pi}/n$. However, in this context this estimator is
typically less efficient; see Tarpey et al. (2014) and Cook et al. (2015).
Another option is the estimator
$\tilde{\beta}_{\pi,0}=\left({\mathbb{X}}^{T}{W}_{\pi}{\mathbb{X}}\right)^{-1}{\mathbb{X}}^{T}{W}_{\pi}{\mathbb{Y}}$.
This is an efficient estimator for ${\beta}$, but for finite $n$,
$\lambda_{min}\left({\mathbb{X}}^{T}{W}_{\pi}{\mathbb{X}}/n\right)$ can be
very small with positive probability and therefore the expectation of
$\tilde{\beta}_{\pi,0}$ may not exist; see Section 4.7 of Hansen (2021). On
the other hand, the event ${\cal E}_{\pi}$ occurs with exponentially small
probability (Tropp, 2012, Theorem 5.1) and therefore, in practice the
difference between $\tilde{\beta}_{\pi}$ and $\tilde{\beta}_{\pi,0}$ is small.
In particular, they have the same asymptotic distribution. The estimator
$\tilde{\beta}_{\pi}$ is advantageous because $(\tilde{Q}/n)^{-1}$ is bounded
and therefore moments of $\tilde{\beta}_{\pi}$ and related quantities exist.

The purpose of the experimenter is to minimize the error
$E_{\pi}\int_{-1}^{1}\frac{1}{2}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}{dx}$.
However, this quantity is difficult to handle because the dependence on $\pi$
can be complicated. Therefore, Theorem 1 below states an asymptotic
approximation where the dependence on $\pi$ is explicit, and leads to the
asymptotic minimax design stated in Theorem 2. To this end, define

${\Omega}_{\pi}={\rm
var}_{\pi}\left\\{\vec{{X}}_{1}^{T}e_{1}\frac{1/2}{\pi(X_{1})}\right\\}.$

The matrix ${\Omega}_{\pi}$ can be written explicitly using the law of total
variance

$\displaystyle{\rm
var}_{\pi}\left\\{\vec{{X}}_{1}^{T}e_{1}\frac{1/2}{\pi(X_{1})}\right\\}$
$\displaystyle=E_{\pi}\left\\{\vec{{X}}_{1}^{T}\vec{{X}}_{1}\frac{1/4}{\pi^{2}(X_{1})}{\rm
var}\left(e_{1}\Big{|}X_{1}\right)\right\\}+{\rm
var}_{\pi}\left\\{\vec{{X}}_{1}^{T}\frac{1/2}{\pi(X_{1})}E(e_{1}|X_{1})\right\\}$
$\displaystyle=\frac{\sigma^{2}}{4}\int_{-1}^{1}\vec{x}^{T}\vec{x}\frac{1}{\pi(x)}dx+\frac{1}{4}\int_{-1}^{1}\vec{x}^{T}\vec{x}\frac{\\{m(x)-\ell(x)\\}^{2}}{\pi(x)}dx$
$\displaystyle=\frac{1}{4}\int_{-1}^{1}\vec{x}^{T}\vec{x}\frac{1}{\pi(x)}[\sigma^{2}+\\{m(x)-\ell(x)\\}^{2}]dx.$
(6)

The following theorem quantifies the approximation,
$E_{\pi}\int_{-1}^{1}\frac{1}{2}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}{dx}\approx\frac{1}{n}tr({Q}^{-1}{\Omega}_{\pi})$.

######  Theorem 1.

Consider model (3), and suppose that $E_{\pi}(e_{1}^{4})$ is finite and
$\pi(x)>\varepsilon_{0}$ for all $x\in[-1,1]$. Then for all $n$,

$n^{3/2}\left|\int_{-1}^{1}\frac{1}{2}E_{\pi}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}dx-\frac{1}{n}tr({Q}^{-1}{\Omega}_{\pi})\right|<C,$
(7)

where $C$ is a constant that depends on $\pi$ only through $\varepsilon_{0}$.

Theorem 1 implies that

$\int_{-1}^{1}\frac{1}{2}E_{\pi}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}dx=\frac{1}{n}tr({Q}^{-1}{\Omega}_{\pi})+O(1/n^{3/2}),$
(8)

and the error term is uniform for all designs $\pi$, with
$\pi(x)>\varepsilon_{0}$. It follows that the approximation in (8) is
uniformly valid for all the densities $\pi$ that are bounded away from zero.
Since when $\pi(x)$ is close to zero for some $x$, the minimax risk can be
large, it is enough to consider only densities that are bounded away from
zero.

The focus from now on will be on the asymptotic variance term
$tr({Q}^{-1}{\Omega}_{\pi})$. Define the set

${\cal M}=\left\\{m(x)~{}\text{such
that}~{}\int_{-1}^{1}\frac{1}{2}\\{m(x)-\ell(x)\\}^{2}dx\leq 1\right\\},$

which bounds the possible deviation from linearity. The bound 1 is arbitrary,
and in general the minimax design depends on the ratio between $\sigma^{2}$
and the linearity bound; see (9) below and also the discussion in Section 4.
Let $h(x)=\vec{x}^{T}{Q}^{-1}\vec{x}$. Theorem 3.3 of Wiens (2000) connects
$h(x)$ to Legendre polynomials. Let

${\cal
R}_{\pi}=\frac{\sigma^{2}}{2}\int_{-1}^{1}\frac{h(x)}{\pi(x)}dx+\sup_{x\in[-1,1]}\frac{h(x)}{\pi(x)}.$
(9)

Lemma 1 of Nie et al. (2018) implies the following proposition.

######  Proposition 1.

Under the above setting, $\sup_{m\in{\cal M}}tr({Q}^{-1}{\Omega}_{\pi})={\cal
R}_{\pi}/2$.

Thus, the minimax problem is to find a density $\pi(x)$ that minimizes ${\cal
R}_{\pi}$.

##  3 Main result

Consider the problem of minimizing ${\cal R}_{\pi}$, which is given in (9).
The first part is minimized by $\pi(x)\propto h^{1/2}(x)$ and the second part
is optimized when $\pi(x)\propto h(x)$; see Remark 3.2 of Nie et al. (2018).
Theorem 2 below shows that the minimizer of ${\cal R}_{\pi}$ is composed from
both solutions.

To state the result about the minimax design, some definitions are needed.
Define the space of designs, which are densities supported in $[-1,1]$,

$\Pi=\left\\{\pi:[-1,1]\mapsto\mathbb{R}^{+}\text{ such that
}\int_{-1}^{1}\pi(x)dx=1\right\\}.$

The purpose is to find ${\pi}^{*}\in\Pi$ that minimizes ${\cal R}_{\pi}$ for
$\pi\in{\Pi}$. Consider $h_{0}\in[h_{min},h_{max}]$, where
$h_{min}=\min_{x\in[-1,1]}h(x)$ and $h_{max}=\max_{x\in[-1,1]}h(x)$. Define,

$A_{h_{0}}=\\{x\in[-1,1]\text{ such that }h(x)\leq h_{0}\\}\text{ and
}B_{h_{0}}=\\{x\in[-1,1]\text{ such that }h(x)>h_{0}\\}.$ (10)

The sets $A_{h_{0}}$ and $B_{h_{0}}$ have an explicit expression. Let
$x_{0,1},\ldots,x_{0,J}$ be all the solutions of $h(x)=h_{0}$ for $x\in[-1,1]$
ordered from smallest to largest. If none of $x_{0,1},\ldots,x_{0,J}$ is an
extremal point of $h$, then
$A_{h_{0}}=[x_{0,1},x_{0,2}]\cup[x_{0,3},x_{0,4}]\ldots\cup[x_{0,J-1},x_{0,J}]$
and $B_{h_{0}}=[-1,x_{0,1}]\cup[x_{0,2},x_{0,3}]\ldots\cup[x_{0,J},1]$. Define
the function

$f(h_{0})=\frac{\int_{B_{h_{0}}}\\{h_{0}-h(x)\\}dx}{h_{0}}.$ (11)

Since $h(x)\geq h_{0}$ for $x\in B_{h_{0}}$, we have that $f(h_{0})\leq 0$;
also, $f(h_{max})=0$. A calculation shows that
$f^{\prime}(h_{0})=\frac{\int_{B_{h_{0}}}h(x)dx}{h_{0}^{2}}>0$, i.e.,
$f(h_{0})$ is monotone increasing. Let
$\sigma^{2}_{min}=-\frac{2}{f(h_{min})}$. The main result is given now.

######  Theorem 2.

Under the above setting,

  1. (i)

If $\sigma^{2}\leq\sigma^{2}_{min}$, the design
${\pi}^{*}(x)=\frac{h(x)}{\int_{-1}^{1}h(x)dx}$ satisfies ${\cal
R}_{{\pi}^{*}}\leq{\cal R}_{\pi}$ for all $\pi\in{\Pi}$.

  2. (ii)

If $\sigma^{2}>\sigma^{2}_{min}$, define $h_{0}^{*}$ to be such that
$f(h_{0}^{*})=-\frac{2}{\sigma^{2}}$. The design

${\pi}^{*}(x)=\left\\{\begin{array}[]{cc}c\\{h^{*}_{0}h(x)\\}^{1/2}&x\in
A_{h_{0}^{*}}\\\ ch(x)&x\in B_{h_{0}^{*}}\end{array}\right.,$ (12)

where $c$ is a normalizing constant, satisfies ${\cal R}_{\pi^{*}}\leq{\cal
R}_{\pi}$ for all $\pi\in{\Pi}$.

By the properties of the function $f$ that were mentioned above, when
$\sigma^{2}>\sigma^{2}_{min}$ the solution
$f(h_{0}^{*})=-\frac{2}{\sigma^{2}}$ exists and is unique. Since
$h(x_{0,j})=h_{0}$, the density ${\pi}^{*}(x)$ is well-defined for
$x=x_{0,j}$, $j=1,\ldots,J$, and ${\pi}^{*}(x)$ is continuous.

The critical value $\sigma^{2}_{min}$ is equal to
$\frac{2}{\int_{-1}^{1}h(x)dx/h_{min}-2}$. For $K=1$, $\sigma^{2}_{min}=1$ and
for $K=2$, $\sigma^{2}_{min}=3/2$. When $K$ is large,
$h(x)\approx\frac{2K}{(1-x^{2})^{1/2}\beta^{2}(3/4,3/4)}$ (Wiens, 2000,
Theorem 3.3) and $\sigma^{2}_{min}\approx\frac{2}{\pi-2}\approx 1.752$.

Minimization of ${\cal R}_{\pi}$ is similar to the problem that is studied in
Wiens (1998) and Wiens (2000). The same minimax criterion is considered for
the weighted least squares estimators. However, these two papers study the
estimation error when $X_{1},\ldots,X_{n}$ are conditioned upon. Specifically,
they consider minimization of the first part of ${\cal R}_{\pi}$ as defined in
(9), which is an asymptotic approximation of $\sup_{m\in{\cal
M}}\left[E_{\pi}\left\\{\int_{-1}^{1}{\rm
var}(\tilde{\ell}_{\pi}(x)|X_{1},\ldots X_{n})dx\right\\}\right]$. This part
pertains to the variance of $\tilde{\ell}_{\pi}(x)$ conditioned on the design,
i.e., when the design is considered fixed; see (6). Wiens (2000) shows that it
is minimized when $\pi(x)\propto\sqrt{h(x)}$. On the other hand, the second
part of ${\cal R}_{\pi}$ comes from the variability of
$E(\tilde{\ell}_{\pi}(x)|X_{1},\ldots X_{n})$ and is not considered in Wiens
(1998) and Wiens (2000).

As mentioned in the introduction, Nie et al. (2018) study the same problem of
minimizing ${\cal R}_{\pi}$ in the active learning setup. In particular,
Theorem 1 of Nie et al. (2018) shows that in the current setting the optimal
design has the form
$\pi^{*}(x)=\left\\{\begin{array}[]{cc}c\\{h_{0}^{*}h(x)\\}^{1/2}&x\in
A_{h^{*}_{0}}\\\ ch(x)&x\in B_{h^{*}_{0}}\end{array}\right.$ for some optimal
$h^{*}_{0}$. This optimal form applies to both the discrete and continuous
settings. Theorem 2 of the current work shows that in the continuous case the
optimal $h^{*}_{0}$ must satisfy $f(h^{*}_{0})=-2/\sigma^{2}$ when such a
solution exists and otherwise it equals to $h_{min}$. It is also shown that
$f$ is monotone, and therefore the solution if exists is unique and can be
easily found using numerical algorithms. This result implies the phase-
transition phenomenon of Theorem 2, namely, that when
$\sigma^{2}\leq\sigma^{2}_{min}$ the optimal design is
${\pi}^{*}(x)=\frac{h(x)}{\int_{-1}^{1}h(x)dx}$ and for
$\sigma^{2}>\sigma^{2}_{min}$ the optimal design is given in (12).

##  4 Unknown variance and Heteroscedasticity

The results so far assumed that the conditional variance $\sigma^{2}$ is
known. When this is not the case, one can consider a parameter space where
$\sigma^{2}$ is upper bounded by $\bar{\sigma}^{2}$, say. In this case the
equivalent result for Proposition 1, with essentially the same proof, is
$\sup_{m\in{\cal
M},\sigma^{2}\leq\bar{\sigma}^{2}}tr({Q}^{-1}{\Omega}_{\pi})={\cal
R}_{\pi}/2$, where, ${\cal
R}_{\pi}=\frac{\bar{\sigma}^{2}}{2}\int_{-1}^{1}\frac{h(x)}{\pi(x)}dx+\sup_{x\in[-1,1]}\frac{h(x)}{\pi(x)}$.
Then Theorem 2 applies with $\sigma^{2}=\bar{\sigma}^{2}$. Thus, the minimax
design depends on the ratio between the upper bound on the variance,
$\bar{\sigma}^{2}$, and the bound on the departure from the linear model
quantified by $\int_{-1}^{1}\frac{1}{2}\left\\{m(x)-\ell(x)\right\\}^{2}dx$,
which was arbitrarily set to one. Practically, the experimenter can choose
this ratio based on the specific problem at hand and compute the minimax
design with respect to the selected ratio. When this ratio is smaller or equal
to $\sigma^{2}_{min}$, the minimax design is the same. In particular, for
$K=1$ and $K=2$ if this ratio is one, i.e., the bound of the variance is equal
to the bound of the departure from linearity, the minimax design is the same
as when the bound of the variance is zero.

Model (3) assumes that ${\rm var}(Y_{i}|X_{i})$ is a constant number,
$\sigma^{2}$, which does not depend on $X_{i}$. This is a strong assumption,
and the results for the heteroscedastic case are now discussed. Suppose that
${\rm var}(Y_{i}|X_{i})=\sigma^{2}(X_{i})$; here $\sigma^{2}$ is a function of
$X$, rather than a constant. The estimator $\tilde{\ell}_{\pi}(x)$, which is
defined after (5), is still a consistent estimator of $\ell(x)$, but now the
equivalent expression for ${\Omega}_{\pi}$ instead of (6) is
${\Omega}_{\pi}=\int_{-1}^{1}\vec{x}^{T}\vec{x}\frac{1/4}{\pi(x)}[\sigma^{2}(x)+\\{m(x)-\ell(x)\\}^{2}]dx$.
Therefore, ${\cal R}_{\pi}$ changes to ${\cal
R}_{\pi}=\frac{1}{2}\int_{-1}^{1}\frac{\sigma^{2}(x)h(x)}{\pi(x)}dx+\sup_{x\in[-1,1]}\frac{h(x)}{\pi(x)}$,
i.e., $\sigma^{2}(x)$ replaces $\sigma^{2}$. The minimax design
${\pi}^{*}(x)$, thus, depends on $\sigma^{2}(x)$, and is not given here.
However, the function $\sigma^{2}(x)$ is rarely known in advance and instead
it is natural to consider a setting where $\sigma^{2}(x)\leq\bar{\sigma}^{2}$
and then Theorem 2 with $\sigma^{2}=\bar{\sigma}^{2}$ applies as above. The
situation where $\sigma^{2}(x)$ is bounded by a function $\bar{\sigma}^{2}(x)$
is deferred to future work.

##  5 Numerical illustrations

In this section the optimal minimax design, ${\pi}^{*}$, which is given in
Theorem 2, is illustrated in a few examples and a comparison to other designs
is presented.

Figure 2 plots the optimal design ${\pi}^{*}$ for
$\sigma^{2}\leq\sigma^{2}_{min}$, $\sigma^{2}=2,3,\infty$ and $K=1,2$. When
$\sigma^{2}\leq\sigma^{2}_{min}$, the optimal design is proportional to
$h(x)$. When $\sigma^{2}=2,3$, for some $x$’s, ${\pi}^{*}(x)$ is proportional
to $h^{1/2}(x)$ and for others, it is proportional to $h(x)$. The intervals
where the former case holds are given in Table 1. For $\sigma^{2}=\infty$,
${\pi}^{*}(x)$ is proportional to $h^{1/2}(x)$ for all $x$.

| $K=1$ | $K=2$
---|---|---
$\sigma^{2}\leq\sigma^{2}_{min}$ | $\emptyset$ | $\emptyset$
$\sigma^{2}=2$ | $[-0.364,0.364]$ | $[-0.587,-0.235]\cup[0.235,0.587]$
$\sigma^{2}=3$ | $[-0.550,0.550]$ | $[-0.725,0.725]$
$\sigma^{2}=\infty$ | $[-1,1]$ | $[-1,1]$
Table 1: The intervals $A_{h_{0}^{*}}$

(a) $K=1$

(b) $K=2$

Figure 2: The optimal design ${\pi}^{*}$ for $\sigma^{2}\leq\sigma^{2}_{min}$
, $\sigma^{2}=2,3,\infty$ and $K=1,2$.

As Huber writes (Huber, 2004, page 244) “with any minimax procedure, there is
the question of whether it is too pessimistic and perhaps safeguards only
against some very unlikely contingency”. In order to examine this question,
the minimax design is compared against the sqrt design of Wiens (2000), which
corresponds to $\sigma^{2}=\infty$ in the above setting, and the uniform
design, in scenarios where $m(x)$ is a quadratic function of $x$ for $K=1$ or
a cubic function for $K=2$. In the former case, $m(x)=x+3.354x^{2}$ and in the
latter case $m(x)=x+x^{2}/2+6.614x^{3}$ were examined. The leading coefficient
of $m(x)$ in both cases were set to satisfy the condition
$\int_{-1}^{1}\frac{1}{2}\\{m(x)-\ell(x)\\}^{2}dx=1$. It is also of interest
to investigate the small sample performance of the minimax design.

Table 2 presents empirical evaluations of
$n\times\int_{-1}^{1}\frac{1}{2}E_{\pi}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}dx$
for $n=50$, which are based on $10^{5}$ simulations. Model (3) was used with
normal $\varepsilon$’s to generate the simulated dataset. Also presented is
the asymptotic approximation of the above expression, which is

$tr({Q}^{-1}{\Omega}_{\pi})=\frac{\sigma^{2}}{4}\int_{-1}^{1}\frac{h(x)}{\pi(x)}dx+\frac{1}{4}\int_{-1}^{1}\frac{h(x)}{\pi(x)}\\{m(x)-\ell(x)\\}^{2}dx.$

In order to better compare the designs, for each simulated dataset,
$U_{1},\ldots,U_{50}\sim U(0,1)$ were sampled and $X_{i}$ was defined to be
$2U_{i}-1,F_{sqrt}^{-1}(U_{i}),F_{minimax}^{-1}(U_{i})$ for the uniform, sqrt,
minimax designs respectively, where $F_{sqrt}$ and $F_{minimax}$ are the
cumulative distribution functions of the sqrt and minimax densities,
$i=1,\ldots,50$. Furthermore, the same $\varepsilon$’s were used for all three
designs. It follows that the standard error of the differences of the
empirical means are smaller than the standard errors of each mean. The former
is given in the second last column of Table 2 for the differences of the means
of the minimax and sqrt designs, and the latter is given after each mean in
parentheses. The best design for each setting is marked in italic font, and
when the difference is not statistically significant, i.e., less than two
standard errors, also the second best is marked. The last column of Table 2
shows the percentage of improvement between the best and the second best
designs.

In all scenarios, the uniform design has the largest estimation error and the
ensuing discussion focuses on the comparison between the sqrt and minimax
designs. When $\sigma^{2}=1,1/2$ the best design is the minimax and the
improvement with respect to the sqrt design is higher when $n=50$ compared to
the asymptotic scenario, when $K=2$ compared to $K=1$ and when
$\sigma^{2}=1/2$ compared to $\sigma^{2}=1$. For $\sigma^{2}=2,3$ the sqrt
design is generally better than minimax, but the percentage of improvement is
smaller compared to $\sigma^{2}=1,1/2$ and in most cases the estimation error
is almost the same. The conclusion is that it seems safe to use the minimax
designs under reasonable models for $m(x)$ and for relatively small sample
sizes.

|  |  | uniform | sqrt | minimax | SE | % improvement
---|---|---|---|---|---|---|---
$K=1$ | $\sigma^{2}=1/2$ | $n=50$ | $3.42(0.04)$ | $2.85(0.03)$ | ${\it 2.69(0.03)}$ | $0.01$ | $5.6\%$
asymptotic | $3.07$ | $2.62$ | ${\it 2.50}$ |  | $4.6\%$
$\sigma^{2}=1$ | $n=50$ | $4.93(0.05)$ | $4.31(0.04)$ | ${\it 4.22(0.04)}$ | $0.02$ | $2.1\%$
asymptotic | $4.57$ | $4.04$ | ${\it 4.00}$ |  | $0.99\%$
$\sigma^{2}=2$ | $n=50$ | $11.21(0.12)$ | ${\it 10.29(0.11)}$ | ${\it 10.31(0.11)}$ | $0.03$ | $0.2\%$
asymptotic | $10.57$ | ${\it 9.76}$ | $9.84$ |  | $0.8\%$
$\sigma^{2}=3$ | $n=50$ | $20.95(0.21)$ | ${\it 19.55(0.20)}$ | ${\it 19.62(0.20)}$ | $0.04$ | $0.36\%$
asymptotic | $20.57$ | ${\it 19.29}$ | $19.38$ |  | $0.46\%$
$K=2$ | $\sigma^{2}=1/2$ | $n=50$ | $6.21(0.08)$ | $4.49(0.05)$ | ${\it 4.06(0.04)}$ | $0.03$ | $9.58\%$
asymptotic | $5.13$ | $4.03$ | ${\it 3.72}$ |  | $7.7\%$
$\sigma^{2}=1$ | $n=50$ | $8.77(0.10)$ | $6.76(0.06)$ | ${\it 6.42(0.06)}$ | $0.04$ | $5.03\%$
asymptotic | $7.38$ | $6.13$ | ${\it 5.98}$ |  | $2.45\%$
$\sigma^{2}=2$ | $n=50$ | $18.46(0.18)$ | ${\it 15.61(0.14)}$ | ${\it 15.67(0.14)}$ | $0.07$ | $0.38\%$
asymptotic | $16.38$ | ${\it 14.57}$ | $14.92$ |  | $3.02\%$
$\sigma^{2}=3$ | $n=50$ | $34.37(0.32)$ | ${\it 30.34(0.27)}$ | ${\it 30.48(0.27)}$ | $0.08$ | $0.46\%$
asymptotic | $29.84$ | ${\it 28.62}$ | $29.02$ |  | $1.38\%$
Table 2: Simulation means (standard errors) of
$n\times\int_{-1}^{1}\frac{1}{2}E_{\pi}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}dx$
when $n=50$ and the asymptotic approximation $tr({Q}^{-1}{\Omega}_{\pi})$ for
the uniform, sqrt and minimax designs, $\sigma^{2}=1/2,1,2,3$ and $K=1,2$ are
presented. For each setting, the best design, and the second best if the
difference is not statistically significant, is marked in italic font. The
second last column shows the simulation standard error of the difference
between the means of the minimax and sqrt designs, and the last column shows
the percentage of improvement between the best and the second best designs.

##  6 General covariates

So far the discussion was limited to the case where the support of $X_{i}$ is
$[-1,1]$, where the estimation error of $\tilde{\ell}_{\pi}(x)$ was equally
weighted in $x$ and where the covariates were monomials of $x$. The general
setting is presented now.

Suppose that the support of $X_{i}$ is a compact set
${S}\subset{\mathbb{R}}^{p}$ and the estimation error is weighted by
$\lambda(x)$, which is a density on ${S}$ with respect to the Lebesgue
measure. It is assumed that $\lambda(x)$ is a continuous function of $x$ and
$\lambda(x)>0$ for all $x\in{S}$. The conditional expectation
$m(x)=E(Y_{i}|X_{i}=x)$ is approximated by a vector of covariates
$\vec{x}=(c_{1}(x),c_{2}(x),\ldots,c_{k}(x))$ for some predetermined
continuous functions $c_{1},\ldots,c_{K}$, and the best linear approximation
is $\ell(x)=\vec{x}{\beta}$, where
${\beta}={Q}^{-1}\int_{S}\vec{x}^{T}m(x)\lambda(x)dx$ and
${Q}=\int_{S}\vec{x}^{T}\vec{x}\lambda(x)dx$. The experimenter selects a
density $\pi$ on ${S}$ and then samples $(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$,
where $X_{i}\sim\pi$. The goal is to find $\pi\in\Pi$, where

$\Pi=\left\\{\pi:{S}\mapsto\mathbb{R}^{+}\text{ such that
}\int_{S}\pi(x)dx=1\right\\},$

that is optimal in a minimax sense.

In order to estimate ${\beta}$, the same weighted least squares estimator is
used as in Section 2, but now the weights are
$\frac{\lambda(X_{i})}{\pi(X_{i})}$. This leads to the estimator
$\tilde{\ell}_{\pi}(x)$ as in Section 2. By the same arguments of Theorem 1,
we have

$\int_{S}E_{\pi}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}\lambda(x)dx=\frac{1}{n}tr({Q}^{-1}{\Omega}_{\pi})+O(1/n^{3/2}),$

where,

${\Omega}_{\pi}=\int_{S}\vec{x}^{T}\vec{x}\frac{\lambda^{2}(x)}{\pi(x)}[\sigma^{2}+\\{m(x)-\ell(x)\\}^{2}]dx.$

Consider the set

${\cal M}=\left\\{m(x)~{}\text{such
that}~{}\int_{S}\\{m(x)-\ell(x)\\}^{2}dx\leq 2\right\\};$

for technical reasons it is convenient to weigh $\\{m(x)-\ell(x)\\}^{2}$
equally, rather than by $\lambda(x)$ and to set the bound to two. Then,
similar to Proposition 1, we have $\sup_{m\in{\cal
M}}tr({Q}^{-1}{\Omega}_{\pi})={\cal R}_{\pi}/2$, where,

${\cal
R}_{\pi}=\frac{\sigma^{2}}{2}\int_{S}\frac{h(x)}{\pi(x)}dx+\sup_{x\in[-1,1]}\frac{h(x)}{\pi(x)},$

and $h(x)=4\vec{x}^{T}{Q}^{-1}\vec{x}\lambda^{2}(x)$.

As in Section 3, let $h_{min}=\min_{x\in{S}}h(x)$ and
$h_{max}=\max_{x\in{S}}h(x)$. Consider $h_{0}\in[h_{min},h_{max}]$ and define
the sets $A_{h_{0}}=\\{x\in{S}~{}:~{}h(x)\leq{h_{0}}\\}$,
$B_{h_{0}}=\\{x\in{S}~{}:~{}h(x)>{h_{0}}\\}$ and the function
$f(h_{0})=\frac{\int_{B_{h_{0}}}\\{h_{0}-h(x)\\}dx}{h_{0}}$. Let also
$\sigma^{2}_{min}=-\frac{2}{f(h_{min})}$. Then Theorem 2 applies with this
notation using similar arguments, i.e., if $\sigma^{2}\leq\sigma^{2}_{min}$,
the design ${\pi}^{*}(x)=\frac{h(x)}{\int_{{S}}h(x)dx}$ satisfies ${\cal
R}_{{\pi}^{*}}\leq{\cal R}_{\pi}$ for all $\pi\in{\Pi}$, and if
$\sigma^{2}>\sigma^{2}_{min}$ the minimax design ${\pi}^{*}$ is given in (12).

##  7 Proofs

### Proof of Theorem 1

Write

$E_{\pi}\left[\int_{-1}^{1}\frac{1}{2}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}dx\right]=tr\left[E_{\pi}\left\\{(\tilde{\beta}_{\pi}-{\beta})(\tilde{\beta}_{\pi}-{\beta})^{T}\right\\}\int_{-1}^{1}\frac{1}{2}\vec{x}^{T}\vec{x}dx\right]\\\
=tr\left[E_{\pi}\left\\{(\tilde{\beta}_{\pi}-{\beta})(\tilde{\beta}_{\pi}-{\beta})^{T}\right\\}{Q}\right].$

By Theorem 5.1 of Tropp (2012), ${\rm pr}({\cal E}_{\pi})\leq a^{n}$ where
$a<1$, because $E_{\pi}[\tilde{Q}_{\pi}]=n{Q}$, and since when ${\cal
E}_{\pi}$ occurs $\tilde{\beta}_{\pi}$ is bounded, we have that

$tr\left[E_{\pi}\left\\{(\tilde{\beta}_{\pi}-{\beta})(\tilde{\beta}_{\pi}-{\beta})^{T}\right\\}{Q}\right]=tr\left[E_{\pi}\left\\{(\tilde{\beta}_{\pi}-{\beta})(\tilde{\beta}_{\pi}-{\beta})^{T}I({\cal
E}_{\pi}^{C})\right\\}{Q}\right]+b_{n},$ (13)

where $b_{n}$ satisfies $|b_{n}|\leq b^{n}$ for $b<1$. When ${\cal
E}_{\pi}^{C}$ occurs, then

$\tilde{\beta}_{\pi}-{\beta}=\left({\mathbb{X}}^{T}{W}_{\pi}{\mathbb{X}}\right)^{-1}{\mathbb{X}}^{T}{W}_{\pi}{\mathbb{Y}}-{\beta}=\left({\mathbb{X}}^{T}{W}_{\pi}{\mathbb{X}}\right)^{-1}{\mathbb{X}}^{T}{W}_{\pi}({\mathbb{X}}{\beta}+{\mathbb{E}})-{\beta}\\\
=\left({\mathbb{X}}^{T}{W}_{\pi}{\mathbb{X}}\right)^{-1}{\mathbb{X}}^{T}{W}_{\pi}{\mathbb{E}}=\frac{1}{\sqrt{n}}\left(\frac{1}{n}\tilde{Q}_{\pi}\right)^{-1}\frac{1}{\sqrt{n}}{\mathbb{X}}^{T}{W}_{\pi}{\mathbb{E}}=\frac{1}{\sqrt{n}}\bar{Q}_{\pi}^{-1}\bar{U}_{\pi},$

where ${\mathbb{E}}=(e_{1},\ldots,e_{n})^{T}$,
$\bar{Q}_{\pi}=\tilde{Q}_{\pi}/n$,
$\bar{U}_{\pi}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}{U}_{i,\pi}$ and
${U}_{i,\pi}=\vec{{X}}_{i}^{T}\frac{1/2}{\pi(X_{i})}e_{i}$. We have that
$E_{\pi}({U}_{i,\pi})={0}$, $i=1,\ldots,n$, because

$E_{\pi}\left({U}_{1,\pi}\right)=E_{\pi}\left\\{\vec{{X}}_{1}^{T}\frac{1/2}{\pi(X_{1})}e_{1}\right\\}=\int_{-1}^{1}\frac{1/2}{\pi(x)}\vec{x}^{T}E(e_{1}|X_{1}=x)\pi(x)dx\\\
=\int_{-1}^{1}\frac{1}{2}\vec{x}^{T}E(e_{1}|X_{1}=x)dx=\int_{-1}^{1}\frac{1}{2}\vec{x}^{T}\\{m(x)-\ell(x)\\}dx={0},$

where the last equality follows from the orthogonality property of $\ell(x)$.
Also, it is easy to verify that
$E_{\pi}({U}_{1,\pi}{U}_{1,\pi}^{T})={\Omega}_{\pi}$.

Going back to (13),

$tr\left[E_{\pi}\left\\{(\tilde{\beta}_{\pi}-{\beta})(\tilde{\beta}_{\pi}-{\beta})^{T}I({\cal
E}_{\pi}^{C})\right\\}{Q}\right]=\frac{1}{n}tr\left[E_{\pi}\left\\{\bar{Q}_{\pi}^{-1}\bar{U}_{\pi}\bar{U}_{\pi}^{T}\bar{Q}_{\pi}^{-1}I({\cal
E}_{\pi}^{C})\right\\}{Q}\right].$

Therefore,

$n\left\\{E_{\pi}\left[\int_{-1}^{1}\frac{1}{2}\\{\tilde{\ell}_{\pi}(x)-\ell(x)\\}^{2}dx\right]-tr({Q}^{-1}{\Omega}_{\pi})\right\\}\\\
=tr\left(\left[E_{\pi}\left\\{\bar{Q}_{\pi}^{-1}\bar{U}_{\pi}\bar{U}_{\pi}^{T}\bar{Q}_{\pi}^{-1}I({\cal
E}_{\pi}^{C})\right\\}-{Q}^{-1}{\Omega}_{\pi}{Q}^{-1}\right]{Q}\right)+c_{n},$

where $c_{n}$ satisfies $|c_{n}|\leq c^{n}$ for $c<1$. Thus, in order to show
(7), the latter trace needs to be bounded. To this end, write

$E_{\pi}\left\\{\bar{Q}_{\pi}^{-1}\bar{U}_{\pi}\bar{U}_{\pi}^{T}\bar{Q}_{\pi}^{-1}I({\cal
E}_{\pi}^{C})\right\\}-{Q}^{-1}{\Omega}_{\pi}{Q}^{-1}=E_{\pi}\left\\{\left(\bar{Q}_{\pi}^{-1}-{Q}^{-1}\right)\bar{U}_{\pi}\bar{U}_{\pi}^{T}\bar{Q}_{\pi}^{-1}I({\cal
E}_{\pi}^{C})\right\\}\\\
+{Q}^{-1}E_{\pi}\left\\{\bar{U}_{\pi}\bar{U}_{\pi}^{T}\left(\bar{Q}_{\pi}^{-1}-{Q}^{-1}\right)I({\cal
E}_{\pi}^{C})\right\\}+{Q}^{-1}E_{\pi}\left\\{\bar{U}_{\pi}\bar{U}_{\pi}^{T}I({\cal
E}_{\pi}^{C})-{\Omega}_{\pi}\right\\}{Q}^{-1}\\\ =I+II+III.$ (14)

In order to prove the theorem, we need to bound $I,II,III$. We start with
bounding $I$. We have

$\bar{Q}_{\pi}^{-1}-{Q}^{-1}={Q}^{-1}({Q}-\bar{Q}_{\pi})\bar{Q}_{\pi}^{-1}.$

Therefore,

${I}={Q}^{-1}E_{\pi}\left\\{\left(\bar{Q}_{\pi}-{Q}\right){Q}^{-1}\bar{U}_{\pi}\bar{U}_{\pi}^{T}\bar{Q}_{\pi}^{-1}I({\cal
E}_{\pi}^{C})\right\\}.$

An element of the matrix
$\left(\bar{Q}_{\pi}-{Q}\right){Q}^{-1}\bar{U}_{\pi}\bar{U}_{\pi}^{T}\bar{Q}_{\pi}^{-1}I({\cal
E}_{\pi}^{C})$ is of the form $\sum_{j}{\cal A}_{j}{\cal B}_{j}$, where ${\cal
A}_{j}$ and ${\cal B}_{j}$ are elements of the matrices $\bar{Q}_{\pi}-{Q}$
and ${Q}^{-1}\bar{U}_{\pi}\bar{U}_{\pi}^{T}\bar{Q}_{\pi}^{-1}I({\cal
E}_{\pi}^{C})$, respectively. In order to bound $I$, it is enough to consider
$E_{\pi}(|{\cal A}_{j}{\cal B}_{j}|)$. By the Cauchy-Schwarz inequality,
$E_{\pi}(|{\cal A}_{j}{\cal B}_{j}|)<\left\\{E_{\pi}\left({\cal
A}_{j}^{2}\right)\right\\}^{1/2}\left\\{E_{\pi}\left({\cal
B}_{j}^{2}\right)\right\\}^{1/2}$. Consider first $E_{\pi}\left({\cal
B}_{j}^{2}\right)$; $\bar{Q}_{\pi}^{-1}I({\cal E}_{\pi}^{C})$ is bounded
because every entry in a positive definite matrix is smaller than the maximal
eigenvalue and the latter is bounded by the definition of the event ${\cal
E}_{\pi}$ in (6). Elements of $\bar{U}_{\pi}\bar{U}_{\pi}^{T}$ have second
moments because $X_{i}$ are bounded (and so is $1/\pi(X_{i})$) and $e_{i}$ has
a finite second moment. It follows that $E_{\pi}\left({\cal B}_{j}^{2}\right)$
is bounded. Consider now $E_{\pi}\left({\cal A}_{j}^{2}\right)$. We have for
certain $j_{1},j_{2}$,

$E_{\pi}\left({\cal
A}_{j}^{2}\right)=E_{\pi}\left\\{\frac{1}{n}\sum_{i=1}^{n}\left(\frac{1}{\pi(X_{i})}X_{i}^{j_{1}}X_{i}^{j_{2}}-\\{{Q}\\}_{j_{1},j_{2}}\right)\right\\}^{2}\\\
=\frac{1}{n^{2}}\sum_{i=1}^{n}E_{\pi}\left(\frac{1}{\pi(X_{i})}X_{i}^{j_{1}}X_{i}^{j_{2}}-\\{{Q}\\}_{j_{1},j_{2}}\right)^{2}\leq
C/n,$

where the second equality is true because
$E_{\pi}\left(\frac{1}{\pi(X_{i})}X_{i}^{j_{1}}X_{i}^{j_{2}}\right)=\\{{Q}\\}_{j_{1},j_{2}}$
and the mixed terms fall. It follows that $|I|\leq C/\sqrt{n}$.

Term II in (14) can be bounded similarly to I. Consider now Term III. Again,
by Theorem 5.1 of Tropp (2012), when $e$ have a bounded fourth moment,
$E_{\pi}\left\\{\bar{U}_{\pi}\bar{U}_{\pi}^{T}I({\cal E}_{\pi}^{C})\right\\}$
is equal to $E_{\pi}\left(\bar{U}_{\pi}\bar{U}_{\pi}^{T}\right)$ up to an
error term that is bounded by $d^{n}$ for $d<1$, which is negligible.
Therefore, since
$E_{\pi}\left(\bar{U}_{\pi}\bar{U}_{\pi}^{T}\right)={\Omega}_{\pi}$, the proof
of the theorem is now completed. ∎

### Proof of Theorem 2

For a given $\pi_{0}\in{\Pi}$, define
$y_{0}=\sup_{x\in[-1,1]}\frac{h(x)}{\pi_{0}(x)}$. By Lemma 1 below, every
solution of the variation problem

$\text{minimize }\int_{-1}^{1}\frac{h(x)}{\pi(x)}dx\text{ under the
constraints }\int_{-1}^{1}\pi(x)dx=1\text{ and }\pi(x)\geq h(x)/y_{0},$

denoted by ${\pi}^{*}_{0}$, satisfies that for all $x\in[-1,1]$, either
${\pi}^{*}_{0}(x)=c_{0}h^{1/2}(x)$, for a normalizing constant $c_{0}$, or
${\pi}^{*}_{0}(x)=h(x)/y_{0}$, and ${\pi}^{*}_{0}$ is continuous. It follows
that ${\pi}^{*}_{0}$ has the form

${\pi}^{*}_{0}(x)=\left\\{\begin{array}[]{cc}ch_{0}^{1/2}h^{1/2}(x)&x\in
A_{h_{0}}\\\ ch(x)&x\in B_{h_{0}}\end{array}\right.,$ (15)

where $h_{0}=y_{0}^{2}c_{0}^{2}$, $c=c_{0}/h_{0}^{1/2}$ and
$A_{h_{0}},B_{h_{0}}$ are defined in (10). Notice that these definitions imply
that ${\pi}^{*}_{0}$ is continuous. Therefore, for every $\pi_{0}\in{\Pi}$
there exists ${\pi}^{*}_{0}$ of the form (15) such that ${\cal
R}_{{\pi}^{*}_{0}}\leq{\cal R}_{{\pi}_{0}}$. An alternative proof to this
result can be found in Theorem 1 of Nie et al. (2018).

The problem of minimizing ${\cal R}_{\pi}$ is, thus, reduced to finding the
optimal $h_{0}$ in (15). It can be formalized by

$\min_{h_{0}}\frac{1}{c}\left\\{\frac{\frac{\sigma^{2}}{2}\int_{{A}_{h_{0}}}h^{1/2}(x)dx}{h_{0}^{1/2}}+\frac{\sigma^{2}}{2}\int_{B_{h_{0}}}dx+1\right\\}\\\
\text{ under the constraint
}c\left\\{\int_{{A}_{h_{0}}}h^{1/2}(x)dx+\int_{{B}_{h_{0}}}{h(x)}dx\right\\}=1.$

Since under the constraint,
$\frac{1}{c}=\int_{{A}_{h_{0}}}h^{1/2}(x)dx+\int_{{B}_{h_{0}}}{h(x)}dx$, one
can write the above problem as

$\min_{h_{0}}\left\\{\int_{{A}_{h_{0}}}h^{1/2}(x)dx+\int_{{B}_{h_{0}}}{h(x)}dx\right\\}\left\\{\frac{\int_{{A}_{h_{0}}}h^{1/2}(x)dx}{h_{0}^{1/2}}+\int_{B_{h_{0}}}dx+\frac{2}{\sigma^{2}}\right\\}=g(h_{0}).$

Let

$u(h_{0})=h_{0}^{1/2}\int_{A_{h_{0}}}h^{1/2}(x)dx+\int_{B_{h_{0}}}h(x)dx~{}\text{
and
}~{}v(h_{0})=\frac{\int_{A_{h_{0}}}h^{1/2}(x)dx}{h_{0}^{1/2}}+{\int_{B_{h_{0}}}dx+\frac{2}{\sigma^{2}}};$

thus, $g(h_{0})=u(h_{0})v(h_{0})$. We have

$u^{\prime}(h_{0})=\frac{1}{2h_{0}^{1/2}}\int_{A_{h_{0}}}h^{1/2}(x)dx~{}\text{
and
}~{}v^{\prime}(h_{0})=\frac{-\frac{1}{2h_{0}^{1/2}}\int_{A_{h_{0}}}h^{1/2}(x)dx}{{h_{0}}}.$

The derivative of $g(h_{0})$ is therefore

$g^{\prime}(h_{0})=\\\
\frac{1}{2h_{0}^{1/2}}\int_{A_{h_{0}}}h^{1/2}(x)dx\left\\{\frac{\int_{A_{h_{0}}}h^{1/2}(x)dx}{h_{0}^{1/2}}+{\int_{B_{h_{0}}}dx+\frac{2}{\sigma^{2}}}-\frac{\int_{A_{h_{0}}}h^{1/2}(x)dx}{h_{0}}-\frac{\int_{B_{h_{0}}}h(x)dx}{h_{0}}\right\\}\\\
=\frac{1}{2h_{0}^{1/2}}\int_{A_{h_{0}}}h^{1/2}(x)dx\left\\{{\int_{B_{h_{0}}}dx+\frac{2}{\sigma^{2}}}-\frac{\int_{B_{h_{0}}}h(x)dx}{h_{0}}\right\\}\\\
=\frac{1}{2h_{0}^{1/2}}\int_{A_{h_{0}}}h^{1/2}(x)dx\left\\{f(h_{0})+\frac{2}{\sigma^{2}}\right\\},$

where $f(h_{0})$ is defined in (11). Recall the properties of $f$ that were
mentioned before Theorem 2. If $\sigma^{2}\leq\sigma^{2}_{min}$, then
$g^{\prime}(h_{0})>0$ for all $h_{0}$ because $f$ is monotone increasing, and
therefore, the optimal $h_{0}$ is $h_{0}^{*}=h_{min}$. If
$\sigma^{2}>\sigma^{2}_{min}$, let $h_{0}^{*}$ be such that
$f(h_{0}^{*})=-\frac{2}{\sigma^{2}}$. It follows that in this case,
$g^{\prime}(h_{0})<0$ (respectively, $g^{\prime}(h_{0})>0$) for
$h_{0}<h_{0}^{*}$ (respectively, $h_{0}>h_{0}^{*}$) and therefore $g(h_{0})$
is minimized when $h_{0}=h_{0}^{*}$ and the theorem follows. ∎

######  Lemma 1.

Let $\bar{\pi}$ be a minimizer of the variation problem

$\text{ minimize }\int_{-1}^{1}\frac{h(x)}{\pi(x)}dx\text{ under the
constraints}\\\ \int_{-1}^{1}\pi(x)dx=1\text{ and }\pi(x)\geq kh(x)\text{ for
all }x\in[-1,1],$ (16)

where $k$ is a positive constant. Then for all $x\in[-1,1]$, either
$\bar{\pi}(x)=ch^{1/2}(x)$, for a normalizing constant $c$, or
$\bar{\pi}(x)=kh(x)$; furthermore, $\bar{\pi}$ is continuous.

Proof of Lemma 1
Since $\pi(x)\geq kh(x)$, one can write $\pi(x)=\frac{kh(x)}{1+s^{2}(x)}$ for
some function $s(x)$. The variation problem (16) can be now written in terms
of $s(x)$,

$\text{ minimize }\int_{-1}^{1}s^{2}(x)dx\text{ under the
constraint}\int_{-1}^{1}\frac{kh(x)dx}{1+s^{2}(x)}=1.$

By the Lagrange multiplier rule for calculus of variations, the optimal
$s^{2}(x)$ must satisfy $\\{1+s^{2}(x)\\}^{2}=\lambda kh(x)$ for some
$\lambda$ or equivalently that $s^{2}(x)=\max\\{(\lambda kh(x)-1)^{1/2},0\\}$,
which implies the result because $\pi(x)=\frac{kh(x)}{1+s^{2}(x)}$. ∎

## Acknowledgment

I would like to thank Amos Ori for useful discussions about the variation
problem of Theorem 2. The close reading and useful comments of two anonymous
referees are also gratefully acknowledged.

## References

  * Box and Draper (1959) Box, G. E. and N. R. Draper (1959).  A basis for the selection of a response surface design.  Journal of the American Statistical Association 54(287), 622–654.
  * Buja et al. (2019) Buja, A., L. Brown, R. Berk, E. George, E. Pitkin, M. Traskin, K. Zhang, and L. Zhao (2019).  Models as approximations I: Consequences illustrated with linear regression.  Statistical Science 34(4), 523–544.
  * Cook et al. (2015) Cook, R. D., L. Forzani, and A. Rothman (2015).  Letter to the editor.  The American Statistician 69(3), 253–254.
  * Cox (2009) Cox, D. (2009).  Randomization in the design of experiments.  International Statistical Review 77(3), 415–429.
  * Cox and Hinkley (1974) Cox, D. R. and D. V. Hinkley (1974).  Theoretical Statistics. London : Chapman & Hall, c1974.
  * Fedorov (2013) Fedorov, V. V. (2013).  Theory of Optimal Experiments.  Elsevier.
  * Fisher (1926) Fisher, R. (1926).  The arrangement of field experiments.  Journal of the Ministry of Agriculture 33, 503–515.
  * Hansen (2021) Hansen, B. E. (2021).  Econometrics.  Online.
  * Heo et al. (2001) Heo, G., B. Schmuland, and D. P. Wiens (2001).  Restricted minimax robust designs for misspecified regression models.  Canadian Journal of Statistics 29(1), 117–128.
  * Huber (2004) Huber, P. J. (2004).  Robust Statistics.  John Wiley & Sons.
  * Kiefer and Wolfowitz (1959) Kiefer, J. and J. Wolfowitz (1959).  Optimum designs in regression problems.  The Annals of Mathematical Statistics 30(2), 271–294.
  * Knoll and Wonodi (2021) Knoll, M. D. and C. Wonodi (2021).  Oxford–astrazeneca covid-19 vaccine efficacy.  The Lancet 397(10269), 72–74.
  * Kohavi and Longbotham (2017) Kohavi, R. and R. Longbotham (2017).  Online controlled experiments and a/b testing.  Encyclopedia of Machine Learning and Data Mining 7(8), 922–929.
  * Nie et al. (2018) Nie, R., D. P. Wiens, and Z. Zhai (2018).  Minimax robust active learning for approximately specified regression models.  Canadian Journal of Statistics 46(1), 104–122.
  * Tarpey et al. (2014) Tarpey, T., R. T. Ogden, E. Petkova, and R. Christensen (2014).  A paradoxical result in estimating regression coefficients.  The American Statistician 68(4), 271–276.
  * Tropp (2012) Tropp, J. A. (2012).  User-friendly tail bounds for sums of random matrices.  Foundations of Computational Mathematics 12(4), 389–434.
  * Waite and Woods (2021) Waite, T. W. and D. C. Woods (2021).  Minimax efficient random experimental design strategies with application to model-robust design for prediction.  Journal of the American Statistical Association. In press.
  * Wiens (1992) Wiens, D. P. (1992).  Minimax designs for approximately linear regression.  Journal of Statistical Planning and Inference 31(3), 353–371.
  * Wiens (1998) Wiens, D. P. (1998).  Minimax robust designs and weights for approximately specified regression models with heteroscedastic errors.  Journal of the American Statistical Association 93(444), 1440–1450.
  * Wiens (2000) Wiens, D. P. (2000).  Robust weights and designs for biased regression models: Least squares and generalized m-estimation.  Journal of Statistical Planning and Inference 83(2), 395–412.
  * Wiens (2015) Wiens, D. P. (2015).  Robustness of design.  In A. M. Dean, M. Morris, J. Stufken, and D. Bingham (Eds.), Handbook of Design and Analysis of Experiments, pp. 719–753.