Accuracy of Uniform Inference on Fine Grid Points

Accuracy of Uniform Inference on Fine Grid Points

\baselineskip=18pt

\affil[1]{Graduate School of Economics, Kyoto University}

Introduction

Uniform confidence bands are a useful device for quantifying uncertainty of estimates on an unknown function over a continuum of points. A long line of work on uniform inference in nonparametric problems dates back at least to early contributions such as bickel1973some and related papers.

Nowadays, by virtue of the seminal studies by chernozhukov2014anti,chernozhukov2014gaussian (hereafter CCK) and their extensions like chernozhukov2016empirical,ChKa20 , we can readily validate the uniform Gaussian approximation and the implementation of uniform critical value for a variety of possibly non-Donsker nonparametric estimators. Specifically, CCK established approximation result between suprema of empirical processes and suprema of Gaussian processes under fairly general setting. Therefore, using the quantile of supremum of approximating Gaussian process as the critical value results in the confidence band which attains asymptotically correct coverage. More importantly for practical implementation, CCK also show that multiplier bootstrap-based critical values can be used as a feasible critical value and yields asymptotically correct coverage. CCK theory has been widely used in applied econometrics and statistics to justify both analytic (Gaussian) critical values and bootstrap-based critical values for uniform inference, for example lee2017doubly,kato2018uniform,fan2022estimation,imai2025doubly to name but a few.

However, in practice, neither supremum of Gaussian process nor supremum of bootstrap statistic over continuous interval is computationally feasible. Accordingly, implementations replace supremum over continuous interval by maximum over a finite evaluation grid and compute critical values from the corresponding maximum of bootstrap statistics over finite grid points. Then, the natural question is how fine the evaluation grid must be in order for the resulting procedure to remain theoretically valid while being computationally feasible. In this study, we address the problem.

This paper provides a quantitative answer to this question. More precisely, as (ref), we quantify how well the conditional $(1-\alpha)$-quantile of the grid maximum of the multiplier-bootstrap statistics (the critical value used in practice) approximates the infeasible $(1-\alpha)$-quantile of the supremum of the studentized statistic over continuous interval. The key feature of (ref) is that it separates the approximation error to two distinct sources of error. One is a discretization error arising from replacing the continuum supremum of the studentized statistic by its maximum over the grid. This discretization component has two elements. First, the discretization error includes a term that captures the probability of the existence of sharp local spikes between grid points and the grid maximum can miss such peaks. Second, even when no sharp between-grid spikes occur, a coarse grid can still miss the true peak simply because the between-grid space is too sparse. The discretization error therefore includes an explicit mesh condition requiring the grid to be fine enough that this miss due to sparsity is negligible. The other reflects how accurately the multiplier bootstrap approximates the distribution of the finite-dimensional vector of studentized statistics over fine grid points. This term is controlled by Gaussian and multiplier-bootstrap approximation theory for high-dimensional maxima by CCKK22. This decomposition directly translates into a practical recipe for choosing the grid size; see (ref) for a detailed implementation workflow.

To illustrate how the bound in (ref) can be used in practice, (ref) works out a kernel density estimation example under standard regularity conditions. The example translates the abstract ingredients of the bound into familiar quantities and yields a simple, implementable rule for choosing the grid size.

\paragraph{Organization:} The remainder of the paper is organized as follows. (ref) introduces the general framework and presents the main coverage error bound for grid-based multiplier-bootstrap uniform inference. (ref) develops and illustration with kernel density estimators. (ref) contains the proofs.

Main Results

Suppose that we are interested in construction of uniform confidence band for some function $f$ over the compact region $\mathcal{X} \coloneqq[\underline{x}, \overline{x}] \subset \mathbb{R}$ and we have an estimator for $f$ with the sum of independent variables form $\hat{f}_{h_n}(x) \coloneqq n^{-1}\sum_{i=1}^n\psi_{h_n}(X_i,x) $ and

where $\{X_i\}_{i=1}^n$ is a sample from i.i.d. observations and $h_n$ denotes a tuning parameter possibly depending on $n$.

Assume that $\sigma_n^2(x)\coloneqq n^{-1}\text{Var}[ \psi_{h_n}(X_i,x)]$ and let $\hat{\sigma}^2_n(x)$ be its estimator:

Define the standardized and studentized estimator as

respectively. For each bootstrap iteration, we generate sets of i.i.d. bootstrap weights $\{w_i^{\star}\}_{i=1}^n$ independently of the original data and compute

For simplicity, we suppose that $\{w_i^{\star}\}_{i=1}^n$ follows the standard normal distribution. Ideally, we would construct the critical value based on the conditional $(1-\alpha)$-quantile of the supremum of the bootstrap process over the continuum,

where $\mathbb{P}^\star(\cdot \mid X_{1:n})$ denotes probability with respect to the bootstrap weights conditional on the original sample. However, evaluating $\sup_{x\in\mathcal{X}}|\hat T_n^\star(x)|$ is not computationally feasible in general. Therefore, we approximate the continuum supremum by a maximum over a finite grid.

To proceed, we introduce some notation about discrete grids. Let $\delta_n>0$ be a mesh size. Set grid points $\{x_j\}_{j=1}^{p}\subset\mathcal X$ by \[ x_j := \underline x + (j-1)\delta_n,\quad j=1,\dots,p-1, ~~~ x_{p} := \overline x, \text{ with } p := \left\lfloor \frac{\overline x-\underline x}{\delta_n}\right\rfloor+2. \] We write $\mathcal X_{\delta_n}:=\{x_1,\dots,x_{p}\}$. Define the maximum gap as

Note that $x_1=\underline x$ and $x_{p}=\overline x$, and that the maximum gap satisfies $\Delta_n \le \delta_n$, since $x_{j+1}-x_j=\delta_n$ for $j\le p-2$ and $x_{p}-x_{p-1}\in(0,\delta_n]$.

In this study, we use the following feasible bootstrap critical value, which approximates the (infeasible) critical value based on $\sup_{x\in\mathcal{X}}|\hat T_n^\star(x)|$.

and investigate the quality of this approximation and provide conditions under which the resulting critical value delivers valid uniform inference. To this end, we introduce the following assumptions.

Two assumptions (ii) and (v) deserve further explanation. (ref)(ii) is imposed to control the high-dimensional Gaussian approximation and multiplier-bootstrap approximation errors using the results of CCKK22. See conditions E and M in CCKK22. (ref)(v) is a high-level condition that controls the discretization error. We discuss (ref)(v) in detail later and provide primitive sufficient conditions for (ref)(v) in the KDE example in (ref).

The following theorem provides an explicit bound on the approximation error that arises when the $(1-\alpha)$-quantile of the supremum statistic $\sup_{x\in\mathcal{X}} |\hat{T}_n(x)| $ is approximated by the feasible bootstrap critical value $\hat{c}^\star_{n,1-\alpha} $ computed from the grid-based bootstrap maximum $\max_{1\le j \le p}|\hat T_n^\star(x_j)|$.

We first provide a detailed explanation on three terms in the right hand side of (ref), and then present a workflow for valid implementation ((ref)).

The first two terms on the right-hand side of (ref) quantify the discretization error arising from replacing the infeasible continuum supremum by a maximum over the finite grid. The final term corresponds to the high-dimensional Gaussian approximation and multiplier bootstrap approximation error on the grid, whose rate follows from the results of CCKK22.

The first term captures the probability that $\hat{T}_n(x)$ exhibits rapid local variation between nearby points, so that the grid maximum may miss a sharp peak occurring between grid points. To see why this term appears, recall that the grid spacing is at most $\Delta_n$. Hence, for any location $x\in\mathcal{X}$ there exists a grid point $x_j$ within distance of $\Delta_n$. If $\hat{T}_n(x)$ does not change too much over such short distances, then the value of $\hat{T}_n(x)$ is well approximated by $\hat{T}_n(x_j)$ and consequently the continuum supremum $\sup_{x\in\mathcal{X}}|\hat{T}_n(x)|$ is well approximated by the grid maximum $\max_{1\le j\le p}|\hat{T}_n(x_j)|$. More precisely, the quantity

measures the largest change of $\hat{T}_n$ per unit change in $x$ over distances up to $\Delta_n$. When this local slope is bounded by $L_n$ moving from any $x$ to a nearby grid point changes $\hat{T}_n$ by at most $L_n\Delta_n/2$. Therefore, any peak that occurs between grid points cannot exceed the observed grid maximum by more than $L_n\Delta_n/2$; the first term is the probability that this favorable behavior fails.

The second term is a deterministic grid-design condition that complements the first term. As explained above, when the local slope of $\hat{T}_n$ over distances up to $\Delta_n$ is bounded by $L_n$, moving from any location $x\in\mathcal{X}$ to a nearby grid point $x_j$ changes $\hat{T}_n$ by at most $L_n\Delta_n/2$. Consequently, on this event, it holds that

so the discrepancy between the continuum supremum and the grid maximum is controlled by the worst-case between-grid fluctuation $L_n\Delta_n/2$. The indicator $1\{L_n\Delta_n/2 > r\}$ checks whether this worst-case fluctuation is small enough relative to the tolerance level $r$, which stems from the high-dimensional Gaussian approximation error and an anti-concentration inequality used in the proof of high-dimensional Gaussian approximation and bootstrap approximation. If $L_n\Delta_n/2 \le r$, then the discretization error contributed by replacing the continuum supremum with the grid maximum is guaranteed to be no larger than $r$ (up to the probability of the event captured by the first term). In practice, this term provides a transparent guideline for choosing the grid: one should select the mesh fine enough so that $L_n\Delta_n/2$ is dominated by $r$.

The last term reflects how accurately the multiplier bootstrap based on the maximum over the grids approximates the distribution of the target statistic after reducing the continuum supremum to a finite-dimensional problem. The rate is inherited from the high-dimensional Gaussian approximation and multiplier bootstrap theory developed in CCKK22. In chernozhukov2023nearly, they conjecture that the bound is “near-optimal when the covariance is unrestricted". A key feature of CCKK22 is that it does not require the covariance matrix of the high-dimensional vector $(\hat{T}_n(x_1), \dots, \hat{T}_n(x_p))$ to be uniformly invertible. This robustness is particularly relevant in nonparametric applications, where the grid becomes dense, nearby evaluations of the estimator are typically strongly correlated, and the resulting finite-dimensional covariance matrix may approach singularity as $p$ increases. For this reason, it is a reasonable choice to benchmark the bootstrap approximation error under the unrestricted covariance rate delivered by CCKK22. It should be desirable, for practical implementation, to characterize the constant in the Gaussian and multiplier bootstrap approximation error by CCKK22. Nevertheless, developing such a result appears technically demanding and we leave it for future work.

In the next section, we provide a concrete implementation discussion through a KDE example. For first-order validity, see (ref) and Remarks (ref)--(ref) for an explicit grid rule and practical guidance. Regarding the stronger goal of making discretization negligible relative to the high-dimensional approximation error, though a fully constant-level prescription is currently out of reach, we record one simple order-based implementation strategy in (ref).

Illustration: Kernel Density Estimator

As an illustration, we consider the construction of uniform confidence bands for the expectation of kernel density estimator.

Theoretical Analysis

In this section, we illustrate how the quantities $B_n$ and $L_n$ are determined in the case of kernel density estimator (KDE) and how they in turn guide an appropriate choice of the grid spacing $\Delta_n$. KDE is defined as

where $K$ is a kernel function and $h_n>0$ is a bandwidth which satisfy assumptions introduced later. For notational simplicity, define

This kind of assumption is standard in the literature (cf. wasserman2006all,li2007nonparametric,tsybakov2008nonparametric, for example). The condition $nh_n^3\to\infty$ in (ref)(iii) is stronger than the most standard condition $nh_n \to \infty$ for the analysis of KDE, but this restriction is not unduly strong for practical purposes, since commonly used bandwidth choices such as MISE-optimal rate ($h_n \asymp n^{-1/5}$) satisfy $nh_n^3\to\infty$.

The following lemma provides explicit quantities needed for the grid selection in the KDE example. In particular, (ref)(ii) provides a valid choice of $B_n$ in (ref)(ii), while (ref)(iii) verifies (ref)(v) by constructing $L_n(\varepsilon_n)$. We use (ref)(i) in the discussion on an implementation issue later.

Given (ref) and (ref), we can proceed to determine the grid size. For each mesh size $\delta\in(0,\overline{x}-\underline{x}]$, let $\mathcal X_\delta=\{x_1,\ldots,x_{p(\delta)}\}$ be the equispaced grid defined in Section 2. In view of (ref)(ii), we may take \[ B_n=\sup_{x\in\mathcal{X}}\Big(B_{\psi,n}(x)\vee B_{4,n}(x)\Big), \] where \[ B_{\psi,n}(x)=\frac{1}{\log 2}\cdot \frac{2\sup_{u\in\mathbb R}|K(u)|}{h_n\sqrt{\text{Var}[K_{i,h_n}(x)]}}, \qquad B_{4,n}(x)=\sqrt{\frac{16\sup_{t\in\mathcal X}|f(t)|}{h_n^3\text{Var}[K_{i,h_n}(x)]^2}\int_{\mathbb R}K^4(u)\,du }. \] Inserting $p=p(\delta)$ and $B_n$ into the definition of $r$ in (ref) yields \[ r(\delta)=2\left\{\frac{B_n^2\log^3\!\big(n\,p(\delta)\big)}{n}\right\}^{1/4}. \]

The following proposition gives how to choose $\delta_n$ to ensure the first order validity of uniform inference.

We now discuss practical aspects of implementing Proposition (ref). In particular, we highlight several bottlenecks that arise in applications in (ref) and (ref). Also (ref) provides a simple implementation procedure.

Proofs

Proof of (ref)

First, observe that

Since $(\rho^\star.I) \le 1$, the bound $(\rho^\star.I) \le C\{n^{-1}B_n^2\log^5(np)\}^{1/4}$ is trivial when $n^{-1}B_n^2\log^5(np) > 1$, so we can assume $n^{-1}B_n^2\log^5(np) \le 1$ without loss of generality. In the following evaluation, we often use this inequality.

First, in terms of $ (\rho^\star. I)$, it holds that

with $T_n^\star(x) \coloneqq n^{-1}\sigma_n^{-1}\sum_{i=1}^n w_i^\star\{\psi_{h_n}(X_i,x) - \hat{f}_{h_n}(x)\}$. From Lemma 4.6 in CCKK22, we can see that

Also, from Lemma 15 in le1986asymptotic, we have

with $r \coloneqq 2\left( n^{-1}B_n^2 \log^3(pn)\right)^{1/4}$. In terms of the first term in (ref), observe that

Nazarov's inequality gives

and Theorem 2.1 in CCKK22 states that there exists a universal constant $C$ such that

Therefore

Next, we evaluate the second term in (ref). Since

we can see that

Since the variance estimator $\hat{\sigma}_n^2(x)$ is defined as (ref), under (ref)(ii), Lemma 4.2 in CCKK22 gives

Also, it holds that

Since, from the union bound and the standard property of the Gaussian tail, we have

From $r = 2\left( n^{-1}B_n^2 \log^3(pn)\right)^{1/4}$ and $B_n^2 \log^5(np)/ \le 1$ we have

In conjunction with (ref), we have

Summing up

Inserting the evaluation (ref) and (ref) to (ref), we have

Similarly, we can see that

From (ref), (ref) and (ref), we have

In terms of $(\rho^\star.II)$, from Lemma 15 in le1986asymptotic, we have

Nazarov's inequality gives

Also, from (ref) and (ref), we have

Finally, in terms of $ (\rho^\star.II.III)$, observe that

Recall that we define the maximum gap as $\Delta_n := \max_{1\le j\le p_n-1}(x_{j+1}-x_j)$. Then, it holds that

This implies

Under Assumption (ref), it holds that

Therefore

where the final inequality follows from $\sup_{x\in\mathcal{X}}\min_{1\le j \le p} |x-x_j|\le \Delta_n/2 $. Summing up, we have

From (ref) and (ref), we have

In the same way as Step 3 in the proof of Theorem 2 in kato2018uniform, we have

This completes the proof.

Proof of (ref)

Before the proof of (ref)(iii), we provide additional auxiliary results. The proofs of these Lemmas are provided in (ref).

Proof of (ref)

Proof of (ref)

Proof of (ref)

First we show (ref)(ii), then show (ref)(i).