1 Introduction↩︎

Quantifying uncertainty is a central problem in statistics, often addressed by constructing prediction intervals for a new response \(y_{n+1}\) given training data \(\mathcal{D}=\{(\boldsymbol{x}_i,y_i)\}_{i=1}^n\) and \(\boldsymbol{x}_{n+1}\). Conformal prediction methods provide distribution-free guarantees, with Full Conformal Prediction (FCP) [1] being a canonical approach. However, FCP is computationally expensive due to its requirement of searching over candidate response values. In contrast, Jackknife+ [2] directly output prediction intervals and are more suitable for continuous-response settings, but still incur a computational cost scaling linearly with \(n\). In this work, we focus on Jackknife+ and Jackknife-minmax as practical alternatives to FCP.

To address this limitation, recent work has explored ALO techniques. For example, [3] proposed using AMP-based estimator to accelerate FCP; [4]–[6] proposed influence function-based approach for constructing ALO estimators. Another line of work [7], [8] proves ALO error bounds and use them to show central limit theorems of the estimator, but the latter requires stronger assumptions.

However, existing approaches lack rigorous error control for ALO in this setting, which may lead to suboptimal efficiency in practice. Moreover, [3] assumes i.i.d.covariates with diagonal covariance, whereas we consider a more general Gaussian model \(\mathcal{N}(0,\Sigma)\) with \(\Sigma\) (not necessarily diagonal).

In this paper, we develop accelerated versions of Jackknife+ and Jackknife-minmax by incorporating ALO estimators derived via Newton updates and the Woodbury identity. Our approach significantly reduces computational cost while preserving the statistical guarantees of the original methods.

Contribution.

• We establish uniform error bounds for ALO-based predictions with a new covariate \(x_{n+1}\), showing that the approximation error \[\begin{align} \label{approximation95error} \bigl|\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} - \boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i}\bigr| \end{align}\tag{1}\] remains uniformly controlled, whereas prior work [9]–[11] focused only on approximation for \(\boldsymbol{x}_i\), \(i\in \{1,2,\ldots,n\}\). Our proof leverages some decomposition techniques to decompose (1 ) to terms can be controlled, thereby reducing the new-covariate case to the setting studied in [10]. Compared with [3], we weaken the assumption on the covariance structure of the distribution of \(\boldsymbol{x}_i\); in particular, we no longer require the covariance matrix to be diagonal.

• We propose the accelerated Jackknife+ and Jackknife-minmax methods for constructing prediction intervals based on ALO estimator \(\tilde{\theta}_{/i}\), and prove they asymptotically retain the same coverage probability and efficiency (interval length) as their original counterparts.

• In a special high-dimensional linear model, we establish that Full Conformal, Split Conformal, Jackknife+, and Jackknife-minmax prediction intervals are asymptotically equivalent.

Related work. A substantial body of work has examined the construction and error bounds of ALO estimators. [9]–[15] develop explicit forms of ALO estimators using the Woodbury identity and analyze their theoretical and empirical performance in estimating out-of-sample risk. In particular, [9], [10], [15] investigate ALO estimators under smoothed regularizers, covering \(\ell_1\) penalties, non-smooth but piecewise twice-differentiable regularizers, and more general non-smooth convex Lipschitz regularizers. Another line of work [7], [8] prove ALO error bounds and use them to show central limit theorems of the estimator, but the latter requires stronger assumptions.

Notations. Consider a model parametrized by \(\theta\in\mathbb{R}^p\) trained on data \(\mathcal{D}\). Let \(r(\theta)=(1 - \eta) r_0(\theta) + \eta \theta^{\top} \theta\) where \(\eta\in(0,1)\) and \(r_0\) is a smooth non-negative convex regularizer. Let \(\boldsymbol{x}_i^\top \in \mathbb{R}^{1 \times p}\) stand for the \(i\)-th row of \(X:=(\boldsymbol{x}_1,\boldsymbol{x}_2,...,\boldsymbol{x}_n)^\top\in \mathbb{R}^{n \times p}\); and we define \(\mathbf{y}:=(y_1,y_2,...,y_n)^\top\). \(\mathbf{y}_{/i} \in \mathbb{R}^{(n-1)\times 1}\) and \(X_{/i}\in \mathbb{R}^{(n-1)\times p}\) stand for \(\mathbf{y}\) and \(X\), excluding the \(i\)th entry \(y_i\) and the \(i\)th row \(x_i^\top\), respectively. We assume that \[\begin{align} \label{optimization951} \hat{\theta}:=\arg\min_{\theta\in\mathbb{R}^p}\left\{\sum_{j=1}^n\ell(y_j,\boldsymbol{x}_j^\top\theta)+\lambda r(\theta)\right\} \end{align}\tag{2}\] is the empirical risk minimizer (ERM), where the loss function \(\ell(y_j,\boldsymbol{x}_j^\top\theta)\) and regularizer \(r(\theta)\) are twice-differentiable in \(\theta\), and \(\ell(y_j,\boldsymbol{x}_j^\top\theta)\) is convex in \(\theta\). Similarly, we define the leave-\(i\)-out ERM estimator by \[\begin{align} \label{exact} \hat{\theta}_{/i}:=\arg\min_{\theta\in\mathbb{R}^p}\left\{\sum_{j\neq i}\ell(y_j,\boldsymbol{x}_j^\top\theta)+\lambda r(\theta)\right\}. \end{align}\tag{3}\] Define \[\dot{\ell}_i(\theta) := \left. \frac{\partial \ell(y_i, z)}{\partial z} \right|_{z = \boldsymbol{x}_i^\top \theta}, \ddot{\ell}_i(\theta) := \left. \frac{\partial^2 \ell(y_i, z)}{\partial z^2} \right|_{z = \boldsymbol{x}_i^\top \theta}.\] Similarly, we define \(\ddot{r}(\theta)=\nabla^2_\theta r(\theta)\).

Define \(f(\boldsymbol{x}^\top\theta)\) as the prediction model \(f:\mathbb{R}\to\mathbb{R}\), with parameter \(\theta\). Polynomials of \(\log(n)\) are denoted by \(\mathrm{polylog}(n)\). We define \(\hat{q}_{n,\alpha}^+\{d_i\}\) as the \(\lceil (1 - \alpha)(n + 1) \rceil\)-th smallest value of \(d_1, \ldots, d_n\), and \(\hat{q}_{n, \alpha}^- \{d_i\}\) as the \(\lfloor \alpha(n + 1) \rfloor\)-th smallest value of \(d_1, \ldots, d_n\). We use \(o(1)\) to denote a deterministic sequence that vanishes as \(n \to \infty\), and \(o_{\mathbb{P}}(1)\) to denote a sequence of random variables that converges to zero in probability.

2 Preliminaries↩︎

2.1 Full conformal prediction↩︎

Let \(\mathcal{D}_n=\{(\boldsymbol{x}_i,y_i)\}_{i=1}^{n}\) be the training data, and let \(\boldsymbol{x}_{n+1}\) denote a test covariate for which the response \(y_{n+1}\) is unobserved. Full conformal prediction (FCP) outputs a prediction set \(\hat{C}^{\mathrm{FCP}}_{\alpha}(\boldsymbol{x}_{n+1})\) satisfying \[\mathbb{P}\bigl\{y_{n+1}\in \hat{C}^{\mathrm{FCP}}_{\alpha}(\boldsymbol{x}_{n+1})\bigr\} \geq 1-\alpha,\] for any user-specified miscoverage level \(\alpha\in(0,1)\), under the exchangeability of \((\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_n,y_n), (\boldsymbol{x}_{n+1},y_{n+1})\).

To construct the prediction set, FCP considers each candidate value \(y\in\mathbb{R}\) as a hypothetical response for the test point and refits the model on the augmented dataset \[\mathcal{D}_n^{(y)} = \mathcal{D}_n\cup\{(\boldsymbol{x}_{n+1},y)\}.\] Let \(\hat{\theta}(y)\) denote the estimator obtained from \(\mathcal{D}_n^{(y)}\). Define the corresponding nonconformity scores by \[\sigma_i(y) := \bigl|f(\boldsymbol{x}_i^\top\hat{\theta}(y))-y_i\bigr|, \qquad i=1,\ldots,n,\] and \[\sigma_{n+1}(y) := \bigl|f(\boldsymbol{x}_{n+1}^\top\hat{\theta}(y))-y\bigr|.\] Let \(\sigma_{(1)}(y)\leq\cdots\leq\sigma_{(n+1)}(y)\) denote the order statistics of \(\{\sigma_i(y)\}_{i=1}^{n+1}\). Then the full conformal prediction set is given by \[\hat{C}(\boldsymbol{x}_{n+1}) = \left\{ y\in\mathbb{R}: \sigma_{n+1}(y) \leq \sigma_{(\lceil(1-\alpha)(n+1)\rceil)}(y) \right\}. \label{e95full}\tag{4}\] Equivalently, FCP includes a candidate value \(y\) if the residual of the hypothetical test point conforms with the residuals computed from the augmented sample. This method is distribution-free and enjoys finite-sample coverage, but it is computationally expensive because \(\hat{\theta}(y)\) must be recomputed for each candidate value \(y\), or for each value on a fine grid in practice; see [1], [16].

2.2 Jackknife+↩︎

Specifically, we consider two variants of FCP in our paper, called Jackknife+ and Jackknife-minmax [2]. The construction of prediction intervals is introduced in (5 ) and (6 ), respectively. Let \(R_i^{LOO}:=|y_i-f(\boldsymbol{x}_i^\top\hat{\theta}_{/i})|\), and define \[\begin{align} \label{orginal95conclusion} \hat{C}_{n,\alpha}^{\text{jackknife+}} &:= \Big[ \hat{q}_{n,\alpha}^{-} \big\{ f(\boldsymbol{x}_{n+1}^\top \hat{\theta}_{/i}) - R_i^{\text{LOO}} \big\}, \hat{q}_{n,\alpha}^{+} \big\{ f(\boldsymbol{x}_{n+1}^\top \hat{\theta}_{/i}) + R_i^{\text{LOO}} \big\} \Big], \end{align}\tag{5}\] \[\begin{align} \label{original95conclusion95mm} \hat{C}_{n,\alpha}^{\text{jack-mm}} &:= \Big[ \min_{i=1,\dots,n} f(\boldsymbol{x}_{n+1}^\top \hat{\theta}_{/i}) - \hat{q}_{n,\alpha}^{+} \big\{ R_i^{\text{LOO}} \big\}, \max_{i=1,\dots,n} f(\boldsymbol{x}_{n+1}^\top \hat{\theta}_{/i}) + \hat{q}_{n,\alpha}^{+} \big\{ R_i^{\text{LOO}} \big\} \Big], \end{align}\tag{6}\]

In [2], the authors established following results: \[\begin{align} \mathbb{P}\{y_{n+1} \in \hat{C}_{n,\alpha}^{\text{jackknife+}}\} &\geq 1 - 2\alpha, \tag{7} \\ \mathbb{P}\{y_{n+1} \in \hat{C}_{n,\alpha}^{\text{jack-mm}}\} &\geq 1 - \alpha. \tag{8} \end{align}\]

2.3 Leave-one-out approximation↩︎

Following [10], using the Newton step and the Woodbury identity, the approximate leave-\(i\)-out estimator \(\tilde{\theta}_{/i}\in\mathbb{R}^{p\times1}\) is defined as follows \[\begin{align} \label{apps95est} \tilde{\theta}_{/i} := \hat{\theta} + \frac{\mathbf{J}^{-1} \boldsymbol{x}_i \, \dot{\ell}_i( \hat{\theta})}{1 - \boldsymbol{x}_i^\top \mathbf{J}^{-1} \boldsymbol{x}_i \, \ddot{\ell}_i(\hat{\theta})}, \end{align}\tag{9}\] where \(\mathbf{J}:=\left( \sum_{j=1}^n \boldsymbol{x}_j \boldsymbol{x}_j^\top \ddot{\ell}_j(\hat{\theta}) + \lambda \, \mathrm{diag}\left[ \ddot{r}(\hat{\theta}) \right] \right)\).

2.4 Assumptions in [10] and [15]↩︎

2.5 Approximation error bound in [10]↩︎

Under Assumption 1 to Assumption 3, [10] proved that \[\max_{1 \leq i \leq n} \left| x_i^\top \hat{\theta}_{/i} - x_i^\top \hat{\theta} - \left( \frac{\dot{\ell}_i(\hat{\theta})}{\ddot{\ell}_i(\hat{\theta})} \right) \left( \frac{H_{ii}}{1-H_{ii}} \right) \right| \leq \frac{C_0}{\sqrt{p}}\] holds with probability at least \(1 - 4ne^{-p} - \frac{8n}{p^3} - \frac{8n}{(n-1)^3} - q_n - \tilde{q}_n\), where \(C_0\) is defined as same as ?? . This result however is not sufficient for our application to conformal prediction, and we will adapt the proof technique to bound the approximation error of \(x_{n+1}^\top \hat{\theta}_{/i}\).

2.6 Lemma 25 in [10]↩︎

3 Main results↩︎

Compared with Assumptions 1-3, the newly added Assumption 4 is used to control the effect of the deviation of approximate intervals from the exact ones on the resulting coverage guarantee. For simplicity, under Assumption 3, we define \[\begin{align} &p_1(n):=\left(\frac{16n}{(n-1)^3}+\frac{16n}{p^3}+8ne^{-p}\right)+q_n+\tilde{q}_n \tag{10},\\ &p_2(n):=\left(\frac{8n}{(n-1)^3}+\frac{8n}{p^3}+4ne^{-p}\right)+q_n+\tilde{q}_n \tag{11}, \end{align}\] and when \(n/p=\delta_0\in(0,\infty)\) it is clear that \[\begin{align} p_1(n)\xrightarrow{\;\text{n\to\infty}\;} 0,\quad p_2(n)\xrightarrow{\;\text{n\to\infty}\;} 0. \end{align}\]

3.1 Algorithm↩︎

Motivated by 9 , we introduce \(\tilde{R}_i^{LOO}:=|y_i-f(\boldsymbol{x}_i^\top\tilde{\theta}_{/i})|\), \(i=1,2,\dots,n\). Then the jackknife+ prediction interval based on estimators in (9 ) is constructed as in (12 ), \[\label{ourmethod} \begin{align} \tilde{C}_{n,\alpha}^{\text{jackknife+}} &:= \Big[ \hat{q}_{n,\alpha}^{-} \big\{ f(\boldsymbol{x}_{n+1}^\top \tilde{\theta}_{/i}) - \tilde{R}_i^{\text{LOO}} \big\}, \hat{q}_{n,\alpha}^{+} \big\{ f(\boldsymbol{x}_{n+1}^\top \tilde{\theta}_{/i}) + \tilde{R}_i^{\text{LOO}} \big\} \Big]. \end{align}\tag{12}\] and the jackknife-minmax prediction interval based on estimators in (9 ) is constructed as in (13 ) \[\label{ourmethod-mm} \begin{align} \tilde{C}_{n,\alpha}^{\text{jack-mm}} &:= \Big[ \min_{i=1,\dots,n} f(\boldsymbol{x}_{n+1}^\top \tilde{\theta}_{/i}) - \hat{q}_{n,\alpha}^{+} \big\{ \tilde{R}_i^{\text{LOO}} \big\}, \max_{i=1,\dots,n} f(\boldsymbol{x}_{n+1}^\top \tilde{\theta}_{/i}) + \hat{q}_{n,\alpha}^{+} \big\{ \tilde{R}_i^{\text{LOO}} \big\} \Big]. \end{align}\tag{13}\]

For simplicity, let \(\tilde{C}_{n,\alpha}^{\text{jackknife+}}=[\tilde{L}_{jk+},\tilde{U}_{jk+}]\), \(\hat{C}_{n,\alpha}^{\text{jackknife+}}=[L_{jk+},U_{jk+}]\), \(\tilde{C}_{n,\alpha}^{\text{jack-mm}}=[\tilde{L}_{jkm}, \tilde{U}_{jkm}]\), and \(\hat{C}_{n,\alpha}^{\text{jack-mm}}=[L_{jkm},U_{jkm}]\).

3.2 Approximation guarantees↩︎

To prove Theorem 2, we introduce the following lemma.

Proof of the lemma 2 is deferred to Section 10 in the appendix.

4 Numerical experiments↩︎

4.1 Synthetic data↩︎

In this section, we conduct simulations to support the results in Theorem 3-4. We report the mean of coverage, mean of operation time, mean of interval length and mean of Jaccard index of original methods (labeled as “JK+” and “JK-minmax”, where “JK” stands for "Jackknife") and accelerated methods (labeled as “Fast JK+” and “Fast JK-minmax”). Recall that the Jaccard index between two sets \(\mathcal{S}_1, \mathcal{S}_2\) is defined as \[\mathcal{J}(\mathcal{S}_1,\mathcal{S}_2) = \frac{|\mathcal{S}_1 \cap \mathcal{S}_2|}{|\mathcal{S}_1 \cup \mathcal{S}_2|} \in [0,1].\] Values closer to \(1\) indicate more precise approximations. In Table 3 we report the Jaccard index between Jackknife+ and Fast Jackknife+, Jackknife-minmax and Fast Jackknife-minmax.

In our simulation, we set \(\alpha=0.1\), which means our target coverage level is \(1-\alpha=0.9\) (in the jackknife+ case, as shown in [2], the coverage level is \(1-2\alpha=0.8\)). We use training sample size \(n =100\), test sample size \(n_{test}=100\), and repeat the experiment at each dimension \(p=50,100,200\), with i.i.d. data points \((\boldsymbol{x}_i,y_i)\) generated as \(\boldsymbol{x}_i\sim \mathcal{N}(0,I_p/\sqrt{p})\) and \(y_i|\boldsymbol{x}_i\sim\mathcal{N}(\boldsymbol{x}_i^\top\theta,1)\). The true coefficient vector \(\theta\) is randomly generated from a standard normal distribution . For the Ridge regression model, we define the loss function as \(\ell(y,\boldsymbol{x}^\top\theta)=(y-\boldsymbol{x}^\top\theta)^2/2\) and the regularization term as \(r(\theta)=\frac{1}{2}r_0(\beta)+\frac{1}{2}\theta^{\top} \theta\), where Pseudo-Huber regularizer (this setting allows our simulation results to be compared with those reported in [3]) \(r_0(\beta)=\sum_{j=1}^p4(\sqrt{1+\frac{\beta_j^2}{4}}-1)\), with the ridge parameter \(\lambda=0.1,1\), separately. To obtain stable results, we repeat the procedures above for 50 iterations and report the averaged outcomes.

2.8pt

2.8pt

4pt

Table 1 and Table 2 present the mean of coverage, mean of operation time and mean of interval length of Jackknife+, Fast Jackknife+, Jackknife-minmax and Fast Jackknife-minmax, respectively. Table 3 shows the similarity, measured by Jaccard Index, between the prediction intervals constructed by the accelerated methods and their corresponding original methods.

We find that our accelerated methods substantially reduce the average computational time while maintaining coverage, and without significantly altering the length (efficiency) of the prediction intervals. The prediction intervals constructed by the accelerated methods exhibit a high degree of similarity to those from the original methods. We can observe that, in most cases, a smaller value of \(\lambda\) tends to result in a wider interval, and the interval length also increases as \(p\) grows. Moreover, our methods exhibit more significant acceleration when the dimensionality of the covariates is higher.

Compared with the synthetic-data simulation results reported in Table 1 of [3], both of our acceleration methods achieve higher coverage than Taylor-AMP, while also providing more efficient prediction (in terms of shorter average interval length) compared with Taylor-AMP, SCP [1] and CQP [17]. With respect to Table 2 of [3], fast Jackknife+ and fast Jackknife-minmax exhibit higher Jaccard similarity to exact LOO than Taylor-AMP and SCP. Under Gaussian settings (Table 3 of [3]), our methods deliver more efficient prediction than Bayes posterior and FCP combined with Taylor-AMP. In comparison with Table 4 of [3], both of our accelerated procedures achieve higher prediction efficiency and higher coverage than Taylor-AMP and approximate homotopy [18], while exhibiting comparable computation time. Furthermore, our framework systematically explores multiple dimensions (\(p=50,100,200\)), corresponding to different \(n/p\) ratios, and two regularization strengths (\(\lambda=0.1,1\)), demonstrating consistent performance across regimes.

These improvements can be attributed to two main factors. First, unlike [3], which assumes i.i.d. features with a diagonal covariance matrix, our framework accommodates a general covariance structure \(\Sigma\). This relaxation is more realistic in practice and ensures that the resulting ALO characterization remains accurate even when the features are correlated, thereby preventing the deterioration observed for AMP and Taylor-AMP under non-isotropic designs. Second, while AMP-based methods rely on an ALO heuristic whose approximation error is not rigorously controlled, our approach benefits from a explicit and tighter ALO error bound derived via the Newton step and Woodbury identity. This leads to more accurate leave-one-out predictions, which in turn improves the quality of the prediction intervals and enhances efficiency.

4.2 Application to Real Data↩︎

We evaluate the proposed methods on the Concrete Compressive Strength Dataset [19] and the Energy Efficiency Dataset [20]. For both datasets, we consider a linear prediction model \[f(\boldsymbol{x}^{\top}\theta)=\boldsymbol{x}^{\top}\theta,\] where the full sample estimator is obtained by minimizing the regularized empirical risk objective \[\hat{\theta} = \arg\min_{\theta\in\mathbb{R}^{p}} \left\{ \frac{1}{2}\sum_{i=1}^{n}\left(y_i-\boldsymbol{x}_i^{\top}\theta\right)^2 + \lambda \left[ 2\sum_{j=1}^{p} \left( \sqrt{1+\frac{\theta_j^2}{4}}-1 \right) + \frac{1}{2}\|\theta\|_2^2 \right] \right\},\] with the regularization parameter fixed at \(\lambda=0.1\). For each dataset, the first \(80\%\) of the observations are used for training, and the remaining \(20\%\) are used for testing.

As shown in Table 4 and Table 5, the accelerated methods achieve nearly identical empirical coverage and comparable average interval lengths to the original Jackknife+ and Jackknife-minmax methods, while substantially reducing the computational time.

4.3 Code↩︎

The code used to produce the results in Table 1, Table 2, Table 3, Table 4 and Table 5 can be found in the following github repository: https://github.com/JiachenCong/Accelerating_Conformal_Prediction_via_Approximate_Leave-One-Out.git. All experiments were run on an Apple M4 laptop with 16 GB of memory.

5 Discussion↩︎

In this section, we address two natural questions regarding our algorithm’s asymptotic performance in high-dimensional settings [8]:

Q1:

We applied the leave-one-out approximation formula to accelerate jackknife+ and jackknife-mm, rather than full conformal prediction, so that rigorous results in [10], [11], [15] can be used to control the approximation error. Does this lead to worse efficiency (longer intervals)?

Q2:

[7] used leave-one-out to prove the central limit theorem M-estimators. Is it possible to further accelerate our algorithm by directly using the central limit theorem result?

In this section, we address these questions by studying the asymptotic performances of full conformal prediction, split conformal prediction, jackknife+, and jackknife-mm in a high-dimensional setting rigorously studied in [8], although some of the conclusions are expected to hold in broader settings. Following [8], we consider the model \(y_i = X_i^{\top} \beta_0 + \epsilon_i\), and \[\begin{align} \hat{\beta} = \arg\min_{\beta \in \mathbb{R}^p} \frac{1}{n} \sum_{i=1}^n \rho_i\!\left(y_i - X_i^{\top} \beta\right) + \frac{\tau}{2}\|\beta\|^2. \label{e95ka} \end{align}\tag{14}\] Similarly, we define \(\hat{\beta}_{/i}\) as the estimator calculated without the \(i\)-th sample. Note that, following [8], we assume the scaling \(\|X_i\|_2=\Theta(\sqrt{n})\) and \(\|\beta\|_2=\Theta(1)\), which is consistent with the scaling in the preceding sections if we take \(X_i:=\sqrt{n}x_i\) and \(\beta:=\frac{1}{\sqrt{n}}\theta\). Within the general framework in the preceding sections, 14 can be understood as the special case where the regularizer is ridge, the log-likelihood \(\ell(y,z)=\rho(y-z)\) for some \(\rho\), and \(y_i=X_i^{\top}\beta+\epsilon_i\) under \(p(y_i|X_i^{\top}\beta)\), where \(\epsilon_1,\dots,\epsilon_n\) are i.i.d.noise. The main contribution of [8] was to use leave-one-out (both observation and predictor) to prove the asymptotic distribution of \(\hat{\beta}\). Though more general sufficient conditions can be found in [8], for simplicity let us assume the following condition (see [8]):

C1

\(p/n\) has a finite nonzero limit.

C2

\(\rho\) is convex, whose first and second derivatives are uniformly bounded: \(\|\rho'\|_{\infty}<\infty\), \(\|\rho''\|_{\infty}<\infty\). Furthermore, \(\mathop{\mathrm{sign}}(\rho'(t))=\mathop{\mathrm{sign}}(t)\) and \(\rho(t)\ge \rho(0)=0\) for all \(t\in \mathbb{R}\).

C3

\(X_1,\dots,X_n\) are i.i.d.following \(\mathcal{N}(0,I_p)\), or with i.i.d.entries with bounded support, symmetric density, and unit variance.

C4

\(\epsilon_1,\dots,\epsilon_n\) are i.i.d.following a differentiable, symmetric, unimodal distribution with variance \(\sigma_{\epsilon}^2\), whose density \(f\) satisfies \(\lim_{t\to\infty}tf(t)=0\).

C5

\(\|\beta_0\|_2\) remains bounded as \(n\to\infty\), and \(\|\beta_0\|_{\infty}=O(n^{-\epsilon})\) for some \(\epsilon>1/4\).

We denote by \(\mathop{\mathrm{prox}}_{\rho}\) the proximal map: \[\begin{align} \mathop{\mathrm{prox}}_{\rho}(x):= \mathop{\mathrm{arg\,min}}_{y\in\mathbb{R}} \{\rho(y)+\frac{1}{2}(x-y)^2\}. \end{align}\]

Under the conditions above, the general result in Theorem 2.1 in [8] implies the following:

Denote by \(U_{\rm J}\) and \(U_{\rm mm}\) the upper limits of the conformal prediction intervals for the \((n+1)\)-th observation produced by the jackknife+ and jackknife-minmax algorithms. For any given \(M>0\), let \(U_{\rm f}(M)\) be the upper limit of the discretized interval \(\hat{C}(X_{n+1})\cap [-M,M]\cap \{0,\pm\frac{1}{M},\frac{2}{M},\dots\}\), where \(\hat{C}(X_{n+1})\) is the full conformal interval. Similarly, define \(L_{\rm f}(M)\), \(L_{\rm J}\), \(L_{\rm mm}\) as the lower limits. Under our assumptions, the differences of these intervals vanish as \(n, M \to \infty\):

The proof of Theorem 6 can be found in the appendix.

This theorem demonstrates that under the idealized assumptions in [8], all considered conformal prediction algorithms are asymptotically equivalent, partially answering Q1.

Regarding Q2, we note that the asymptotic approximation in Theorem 6 relies on the CLT result, which requires independence of \(X_1,\dots,X_n\) and is much stronger than leave-observation-out approximation. Conversely, jackknife+ (and our proposed ALO version) remains valid in the general exchangeable case, which partially answers Q2. It is an interesting direction for future research to identify settings in which leave-one-out approximations remain asymptotically valid while asymptotic normality fails. A related work [21] shows that leave-one-feature-out approximations remain asymptotically accurate for general correlated sub-Gaussian feature vectors, and the techniques developed there may be extendable to the leave-one-observation-out setting.

Appendix↩︎

In this appendix, we provide detailed proofs of the theorems presented in the main paper.

Organization↩︎

Table 6 presents the organization of the appendix.

6 Existing Results↩︎

In this section, we present existing results used in our proof, which are adapted from [10].

6.1 [10]↩︎

Define \(g_{/i}(\theta)=\lambda\dot{r}(\theta)+X_{/i}^\top \dot{\boldsymbol{\ell}}_{/i}(\theta)\). The leave-one-out estimate, \(\hat{\theta}_{/i} = \hat{\theta} + \Delta_{/i}^*\), satisfies \(g_{/i}(\Delta_{/i}^*+\hat{\theta}) = 0\). The multivariate mean-value Theorem yields \[0 = g_{/i}(\hat{\theta} + \Delta_{/i}^*) = g_{/i}(\hat{\theta}) + \left( \int_0^1 \boldsymbol{J}_{/i}(\hat{\theta} + t \Delta_{/i}^*) dt \right) \Delta_{/i}^*,\] where the Jacobian is \[\boldsymbol{J}_{/i}(\theta) = \lambda \, \mathrm{diag}[\ddot{r}(\theta)] + X_{/i}^{\top} \, \mathrm{diag}[\ddot{\boldsymbol{\ell}}_{/i}(\theta)] \, X_{/i}.\] Moreover, \(\hat{\beta}\) satisfies \[0 = \lambda \dot{r}(\hat{\theta}) + X^{\top} \dot{\boldsymbol{\ell}}(\hat{\theta}) = g_{/i}(\hat{\theta}) + \dot{\boldsymbol{\ell}}_i(\hat{\theta}) x_i.\] We obtain \[\dot{\boldsymbol{\ell}}_i(\hat{\theta}) x_i = - \left( \int_0^1 \boldsymbol{J}_{/i}(\hat{\theta} + t \Delta_{/i}^*) dt \right) \Delta_{/i}^*,\] so that \[\Delta_{/i}^* = - \dot{\boldsymbol{\ell}}_i(\hat{\theta}) \left( \int_0^1 \boldsymbol{J}_{/i}(\hat{\theta} + t \Delta_{/i}^*) dt \right)^{-1} x_i,\] leading to the following inequality \[\|\Delta_{/i}^*\|_2 \le \left( \frac{|\dot{\ell}_i(\hat{\theta})|}{\nu} \right) \|\boldsymbol{x}_i\|_2.\] By Assumption 3.(b), we obtain the Eq.136 in [10] \[\begin{align} \|\Delta_{/i}^*\|_2 \leq\frac{c_1(n)}{\nu} \|\boldsymbol{x}_i\|_2 \end{align}\]

6.2 [10]↩︎

The proof of this lemma can be found on pages 60 and 61 of [10].

6.3 [10]↩︎

6.4 [10]↩︎

The proof of this lemma can be found on pages 34 and 35 of [10].

6.5 [10]↩︎

7 Proof of Theorem 1↩︎

We introduce the following definitions:

• (1) \(\Delta_{/i}^*:=\hat{\theta}_{/i} -\hat{\theta}\), and \(\boldsymbol{J}_{/i}:= \lambda \, \mathrm{diag}\!\big[\ddot{r}_s(\hat{\theta}_{/i})\big] + X_{/i}^\top \, \mathrm{diag}\!\big[\ddot{\boldsymbol{\ell}}_{/i}(\hat{\theta}_{/i})\big] \, X_{/i}\), where \(X_{/i}=(\boldsymbol{x}_{1},...,\boldsymbol{x}_{i-1},\boldsymbol{x}_{i+1},...,\boldsymbol{x}_{n})^\top\).

• (2) Events \(\tilde{E}_i:=\left\{ 3\bar{C}_i \left( \left\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_i \right\|_4^2 + \left\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \right\|_4^2 \right) > C \frac{\log p}{\sqrt{p}} \right\}\),
  and \(\tilde{E}_{n+1,i}:=\left\{ 3\bar{C}_{i} \left( \left\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \right\|_4^2 + \left\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \right\|_4^2 \right) > C \frac{\log p}{\sqrt{p}} \right\}\).

• (3) \(\bar{C}_{i}:=4\|\boldsymbol{x}_{i}\|_2 \left( \frac{c_1^2(n) c_2(n)}{\nu} \right) \left( 1 + \frac{2c_1(n) c_2(n)}{\nu^2} (1 + \omega_{\max}) \|\boldsymbol{x}_{i}\|_2 \right)\).

• (4) Define \(\Phi_1:=\boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) - \left( \boldsymbol{J}_{/i}(\hat{\theta}_{/i} ) + \bar{X}_{/i}^\top \, \mathrm{diag}\!\left[\int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) dt \right] \bar{X}_{/i}\right)^{-1}\) and
  \(\Phi_2:=\boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) - \left( \boldsymbol{J}_{/i}(\hat{\theta}_{/i} ) + \bar{X}_{/i}^\top \, \mathrm{diag}\!\left[ \gamma_{ {-\Delta_{/i}^*} \, /i } (\hat{\theta}_{/i} ) \right] \bar{X}_{/i} \right)^{-1}\) , where for \(\delta,\theta\in\mathbb{R}^p\) \[\gamma_{\delta / i}(\theta):= \begin{bmatrix} \ddot{\boldsymbol{\ell}}_{/i}(\theta + \delta) - \ddot{\boldsymbol{\ell}}_{/i}(\theta) \\ \lambda \big( \ddot{r}(\theta + \delta) - \ddot{r}(\theta) \big) \end{bmatrix},\quad\bar{X}_{/i} := \begin{bmatrix} X_{/i} \\ I \end{bmatrix} \in \mathbb{R}^{(n-1+p)\times p},\] \[\quad\mathbf{D}_{/i}(\theta) := \mathrm{diag}\!\begin{bmatrix} \ddot{\boldsymbol{\ell}}_{/i}(\theta) \\ \lambda \ddot{r}(\theta) \end{bmatrix} \in \mathbb{R}^{(n-1+p)\times(n-1+p)} .\] Define \(\boldsymbol{J}_{/i}(\theta):=\bar{X}_{/i}^\top \mathbf{D}_{/i}(\theta)\bar{X}_{/i}\).

Consider \[\begin{align} &\quad\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} -\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i} \nonumber \\ & =\dot{\ell}_i(\hat{\theta }) \boldsymbol{x}_{n+1}^\top M\boldsymbol{x}_{i} \\ &=\frac{1}{2}\dot{\ell}_i(\hat{\theta }) (\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top M (\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) - \frac{1}{2}\dot{\ell}_i(\hat{\theta }) \boldsymbol{x}_{n+1}^\top M\boldsymbol{x}_{n+1} -\frac{1}{2}\dot{\ell}_i(\hat{\theta }) \boldsymbol{x}_i^\top M\boldsymbol{x}_i \\ &=A_1-A_2-A_3, \label{e218} \end{align}\tag{15}\] where we defined \[\begin{align} M:=\left( \int_0^1 \boldsymbol{J}_{/i}(\hat{\theta}_{/i} - (1-t)\Delta_{/i}^*) dt \right)^{-1} - \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} - \Delta_{/i}^*). \end{align}\] Clearly we have \[\begin{align} |\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} -\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i} | \le |A_1|+|A_2|+|A_3|. \end{align}\]

By Assumption 3.(a), we have \[\dot{\ell}_i(\hat{\theta} )=O(\text{polylog}(n)).\] By the definition of \(\gamma_{\delta/i}(\theta)\), we have \[\begin{align} \label{aux95definition} \boldsymbol{J}_{/i}(\theta + \delta) = \boldsymbol{J}_{/i}(\theta) + \bar{X}_{/i}^{\top} \operatorname{diag}\!\big[\gamma_{\delta/i}(\theta)\big] \bar{X}_{/i}. \end{align}\tag{16}\] For the new \(A_1\) term, we have \[\begin{align} \label{newa1} &\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top M(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})\right| \nonumber\\ =&\left|(\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})^\top\left[ \left( \int_0^1 \boldsymbol{J}_{/i}(\hat{\theta}_{/i} - (1-t)\Delta_{/i}^*) dt \right)^{-1} - \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} - \Delta_{/i}^*) \right](\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})\right|\nonumber\\ =&\left|(\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})^\top\left[ \left( \int_0^1 \boldsymbol{J}_{/i}(\hat{\theta}_{/i} - (1-t)\Delta_{/i}^*) dt \right)^{-1} - \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i}) \right](\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})\right| \notag\\&+\left|(\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})^\top\left[\boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i})-\boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} - \Delta_{/i}^*) \right](\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1}) \right|\notag \\ \leq^1&\left|(\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})^\top\left[ \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) -\left( \boldsymbol{J}_{/i}(\hat{\theta}_{/i} ) + \bar{X}_{/i}^\top \, \mathrm{diag}\!\left[\int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i } (\hat{\theta}_{/i} ) dt \right] \bar{X}_{/i}\right)^{-1}\right](\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})\right| \notag\\ &+\left|(\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})^\top\left[ \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) -\left(\boldsymbol{J}_{/i}(\hat{\theta}_{/i} ) + \bar{X}_{/i}^\top \, \mathrm{diag}\!\left[ \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right] \bar{X}_{/i}\right)^{-1}\right](\boldsymbol{x}_{i}+\boldsymbol{x}_{n+1})\right| \notag\\ =&\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top\Phi_1(\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right|+\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top\Phi_2(\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right|, \end{align}\tag{17}\] where \(\leq^1\) is due to (16 ).

For the \(\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top\Phi_2(\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right|\) term, using [10] we have \[\begin{align} \label{xixnphi2} &\quad \left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top \Phi_2 (\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right| \nonumber\\ &\leq \left( \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) (\boldsymbol{x}_i +\boldsymbol{x}_{n+1}) \right\|_4^2\nonumber \\ &\le \left( \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2^2 \right) \left(\left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_i\right\|_4 + \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1}\right\|_4 \right)^2\nonumber \\ &\le 2\left( \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_i \right\|_4^2 \nonumber\\ &\quad+ 2\left( \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \right\|_4^2. \end{align}\tag{18}\] Similarly, for the term \(\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top\Phi_1(\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right|\), we can prove the following bound \[\begin{align} \label{xixnphi1} &\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top\Phi_1(\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right|\notag\\ \leq&2\left( \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt\right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_i \right\|_4^2 \nonumber\\ &+ 2\left( \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt \right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \right\|_4^2. \end{align}\tag{19}\] Under Assumption 4, we have \[\begin{align} \label{c2951} \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2 &\leq \bigl\| \ddot{\boldsymbol{\ell}}_{/i}(\hat{\theta}_{/i} - \Delta^*_{/i}) - \ddot{\boldsymbol{\ell}}_{/i}(\hat{\theta}_{/i} ) \bigr\|_2 + \bigl\| \lambda \bigl( \ddot{r}_s(\hat{\theta}_{/i} - \Delta^*_{/i}) - \ddot{r}_s(\hat{\theta}_{/i} ) \bigr) \bigr\|_2 \nonumber \\ &\leq 2 c_2(n) \, \bigl\| \Delta^*_{/i} \bigr\|_2 . \end{align}\tag{20}\] Likewise, \[\begin{align} \label{c2952} \Biggl\| \int_{0}^{1} \gamma_{-(1-t)\Delta^*_{/i}/i}(\hat{\theta}_{/i} ) \, dt \Biggr\|_2 &\leq \int_{0}^{1} \bigl\| \gamma_{-(1-t)\Delta^*_{/i}/i}(\hat{\theta}_{/i} ) \bigr\|_2 \, dt \nonumber \\ &\leq \int_{0}^{1} \bigl\| \ddot{\boldsymbol{\ell}}_{/i}(\hat{\theta}_{/i} - (1-t)\Delta^*_{/i}) - \ddot{\boldsymbol{\ell}}_{/i}(\hat{\theta}_{/i} ) \bigr\|_2 \, dt \nonumber \\&+ \int_{0}^{1} \bigl\| \lambda \bigl( \ddot{r}_s(\hat{\theta}_{/i} - (1-t)\Delta^*_{/i}) - \ddot{r}_s(\hat{\theta}_{/i} ) \bigr) \bigr\|_2 \, dt \nonumber \\ &\leq 2 c_2(n) \, \bigl\| \Delta^*_{/i} \bigr\|_2 . \end{align}\tag{21}\]

By the result in Section 6.1, we have \[\begin{align} \label{c1951} \bigl\| \Delta^*_{/i} \bigr\|_2 \;\leq\; \left( \frac{\bigl| \dot{\ell}_i(\hat{\theta} ) \bigr|}{\nu} \right) \bigl\| \boldsymbol{x}_i \bigr\|_2 \leq\frac{c_1(n)}{\nu} \|\boldsymbol{x}_i\|_2. \end{align}\tag{22}\] Using results in (20 ), (21 ) and (22 ), we obtain \[\begin{align} \label{newa195result} |A_1|\leq&\frac{1}{2}|\dot{\ell}_i(\hat{\theta} )|\cdot\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top\Phi_1(\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right|+\frac{1}{2}|\dot{\ell}_i(\hat{\theta} )|\cdot\left|(\boldsymbol{x}_i+\boldsymbol{x}_{n+1})^\top\Phi_2(\boldsymbol{x}_i+\boldsymbol{x}_{n+1}) \right|\notag\\ \leq&|\dot{\ell}_i(\hat{\theta} )|\cdot\left( \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_i \right\|_4^2 \nonumber\\ &+|\dot{\ell}_i(\hat{\theta} )|\cdot\left( \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \gamma_{ {-\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \right\|_4^2\notag\\ &+|\dot{\ell}_i(\hat{\theta} )|\cdot\left( \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt\right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_i \right\|_4^2 \nonumber\\ &+|\dot{\ell}_i(\hat{\theta} )|\cdot\left( \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt \right\|_2 + \left( \frac{\bar{\omega}_{\max,i}}{\nu} \right) \left\| \int_0^1 \gamma_{ {-(1-t)\Delta_{/i}^*} \, /i }(\hat{\theta}_{/i} ) \, dt \right\|_2^2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \right\|_4^2\notag\\ \leq&4\|\boldsymbol{x}_{i}\|_2 \left( \frac{c_1^2(n) c_2(n)}{\nu} \right) \left( 1 + \frac{2c_1(n) c_2(n)}{\nu^2} (1 + \omega_{\max,i}) \|\boldsymbol{x}_{i}\|_2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \right\|_4^2\notag\\ &+4\|\boldsymbol{x}_{i}\|_2 \left( \frac{c_1^2(n) c_2(n)}{\nu} \right) \left( 1 + \frac{2c_1(n) c_2(n)}{\nu^2} (1 + \omega_{\max,i}) \|\boldsymbol{x}_{i}\|_2 \right) \left\| \bar{X}_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \right\|_4^2\notag\\ \leq&4\|\boldsymbol{x}_{i}\|_2 \left( \frac{c_1^2(n) c_2(n)}{\nu} \right) \left( 1 + \frac{2c_1(n) c_2(n)}{\nu^2} (1 + \omega_{\max,i}) \|\boldsymbol{x}_{i}\|_2 \right) \sqrt{ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^4 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^4 }\notag\\ &+4\|\boldsymbol{x}_{i}\|_2 \left( \frac{c_1^2(n) c_2(n)}{\nu} \right) \left( 1 + \frac{2c_1(n) c_2(n)}{\nu^2} (1 + \omega_{\max,i}) \|\boldsymbol{x}_{i}\|_2 \right) \sqrt{ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^4 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^4 }\notag\\ \leq& \bar{C}_{i}\left[\bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 \right]+\bar{C}_{i}\left[\bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 \right], \end{align}\tag{23}\] where \(\omega_{\max,i}:=\sigma_{\max}(X_{/i}X_{/i}^\top)\), \(\omega_{\max}:=\sigma_{\max}(XX^\top)\) and \(\bar{\omega}_{\max,i} := \sigma_{\max}\!\left(\bar{X}_{/i}\bar{X}_{/i}^\top\right)\). By this definition, we can derive that \[\begin{align} \bar{\omega}_{\max,i} &= \sigma_{\max}\!\left(\bar{X}_{/i}\bar{X}_{/i}^\top\right) = \sigma_{\max}\!\left(\bar{X}_{/i}^\top\bar{X}_{/i}\right) = \sigma_{\max}\!\left( \begin{bmatrix} X_{/i}\\ I \end{bmatrix}^\top \begin{bmatrix} X_{/i}\\ I \end{bmatrix} \right) \notag\\[4pt] &= \sigma_{\max}\!\left(I + X_{/i}^\top X_{/i}\right) \le 1 + \sigma_{\max}\!\left(X_{/i}^\top X_{/i}\right) = 1 + \omega_{\max,i}, \end{align}\]

For \(|A_2|\) and \(|A_3|\), we can use a similar method to show that \[\begin{align} \label{newa295result} |A_2|\leq\frac{1}{2}\bar{C}_{i}\left[\bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 \right] \end{align}\tag{24}\] and \[\begin{align} \label{newa395result} |A_3|\leq\frac{1}{2}\bar{C}_{i}\left[\bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 \right]. \end{align}\tag{25}\] Combining the results in (23 ), (24 ) and (25 ), we obtain \[\begin{align} |\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} -\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i} |\leq&\frac{3}{2}\bar{C}_{i}\left[\bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 \right]\nonumber \\ +&\frac{3}{2}\bar{C}_{i}\left[\bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 \right]\nonumber\\ \leq&3\bar{C}_{i}\cdot\max_{j\in\{i,n+1\}}\left[\bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{j} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{j} \bigr\|_4^2 \right]. \end{align}\] Next, we define the event \[G:=\left\{\max_{1\leq i\leq n}|\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i} -\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} |\geq C\frac{\log(p)}{\sqrt{p}}\right\}.\]

Adopting the reasoning on pages 54–55 of [10], where \(S\) denotes the event that Assumption 3 in our paper holds (trivially we have \(\mathbb{P}(S^c)\leq q_n+\tilde{q}_n\)), and \(q_n\) and \(\tilde{q}_n\) follow the definitions in Assumption 3, we have \[\begin{align} \mathbb{P}[G]&\leq\mathbb{P}[G|S]+\mathbb{P}[S^c]\nonumber \\ &\leq\mathbb{P}[\max_{1\leq i\leq n}(\max_{j\in\{i,n+1\}}|\mathbf{x}_{j}^\top\hat{\theta}_{/i} -\mathbf{x}_{j}^\top\tilde{\theta}_{/i} |>C\frac{\log(p)}{\sqrt{p}}|S]+q_n+\tilde{q}_n\nonumber \\ &\leq\frac{\mathbb{P}[\max_{1\leq i\leq n}|\boldsymbol{x}_{i}^\top\hat{\theta}_{/i} -\boldsymbol{x}_{i}^\top\tilde{\theta}_{/i} |>C\frac{\log(p)}{\sqrt{p}}]+\mathbb{P}[\max_{1\leq i\leq n}|\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i} -\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} |>C\frac{\log(p)}{\sqrt{p}}]}{1-q_n-\tilde{q}_n}+q_n+\tilde{q}_n\nonumber \\ &\leq\frac{\mathbb{P}[3\bar{C}_{i}\cdot \left[ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2\right]>C\frac{\log(p)}{\sqrt{p}}]}{1-q_n-\tilde{q}_n}\nonumber \\ &\quad+\frac{\mathbb{P}[3\bar{C}_{i}\cdot \left[ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2\right]>C\frac{\log(p)}{\sqrt{p}}]}{1-q_n-\tilde{q}_n}+q_n+\tilde{q}_n. \end{align}\] For \(\mathbb{P}[3\bar{C}_{i}\cdot \left[ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2\right]>C\frac{\log(p)}{\sqrt{p}}]\) and
\(\mathbb{P}[3\bar{C}_{i}\cdot \left[ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2\right]>C\frac{\log(p)}{\sqrt{p}}]\), we have \[\begin{align} &\mathbb{P}[3\bar{C}_{i}\cdot \left[ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{i} \bigr\|_4^2\right]>C\frac{\log(p)}{\sqrt{p}}]\leq\sum_{i=1}^n\mathbb{P}[\tilde{E}_i]; \\ &\mathbb{P}[3\bar{C}_{i}\cdot \left[ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2 + \bigl\| \boldsymbol{J}_{/i}^{-1}(\hat{\theta}_{/i} ) \boldsymbol{x}_{n+1} \bigr\|_4^2\right]>C\frac{\log(p)}{\sqrt{p}}]\leq\sum_{i=1}^n\mathbb{P}[\tilde{E}_{n+1,i}]. \end{align}\] For simplicity, we define \[\begin{align} C_i &:= 6(1+c)\left( \frac{\rho_{\max}}{\nu^2} \right) \left( 1 + \omega_{\max} \sqrt{\tfrac{n-1}{p} \, \tfrac{\log(n-1)}{\log p}} \right),\nonumber \\ F_{n+1,i} &:= \left\{3 \,\bar{C}_i \left( \left\| X_{/i} \boldsymbol{J}_{/i}^{-1} \boldsymbol{x}_{n+1} \right\|_4^2 + \left\| \boldsymbol{J}_{/i}^{-1} \boldsymbol{x}_{n+1} \right\|_4^2 \right) > \bar{C}_i C_i \sqrt{p} \log p \,\right\},\nonumber \\ K_i &:= \left\{ \,\frac{C}{\sqrt{p}} \geq \bar{C}_i C_i \sqrt{p} \,\right\}, \nonumber \\ W_{n+1} &:= \left\{ \,\|\boldsymbol{x}_{n+1}\|_2^2 > 5p \rho_{\max} \,\right\} \;\cup\; \left\{ \,\omega_{\max} > (\sqrt{n} + 3\sqrt{p})^2 \rho_{\max} \,\right\}.\nonumber \end{align}\]

Hence, we now obtain an upper bound for \(\mathbb{P}[\tilde{E}_{n+1,i}]\) \[\begin{align} \mathbb{P}[\tilde{E}_{n+1,i}] &\leq \mathbb{P}[\tilde{E}_{n+1,i} \mid K_i] + \mathbb{P}[K_i^c] \nonumber \\ &\leq \mathbb{P}[F_{n+1,i} \mid K_i] + \mathbb{P}[K_i^c] \;\leq\; \frac{\mathbb{P}(F_{n+1,i})}{\mathbb{P}(K_i)} + \mathbb{P}[K_i^c] \nonumber \\ &\leq \frac{\mathbb{P}\!\left[ \bigl\| X_{/i} \boldsymbol{J}_{/i}^{-1} \boldsymbol{x}_{n+1} \bigr\|_4^2 > 2(1+c)\left(\tfrac{\rho_{\max}}{\nu^2}\omega_{\max}\right) \sqrt{n-1}\,\log(n-1) \right]}{\mathbb{P}(K_i)} \nonumber \\ &\quad + \frac{\mathbb{P}\!\left[ \bigl\| \boldsymbol{J}_{/i}^{-1} \boldsymbol{x}_{n+1} \bigr\|_4^2 > 2(1+c)\left(\tfrac{\rho_{\max}}{\nu^2}\right) \sqrt{p}\log p \right]}{\mathbb{P}(K_i)} + \mathbb{P}[K_i^c] \nonumber \\ &\leq^1 \left( \frac{2}{(n-1)^c} + \frac{2}{p^c} \right) \frac{1}{\mathbb{P}(K_i)} + \mathbb{P}[K_i^c], \end{align}\] where \({\leq}^1\) is due to (?? ). To bound \(\mathbb{P}[K_i^c]\) we define \[C := 96 \sqrt{5} \left( \frac{c_1^2(n)c_2(n)\,(p \rho_{\max})^{3/2}}{\nu^3} \right) \left( 1 + \left(\sqrt{\tfrac{n}{p}} + 3\right)^2 p \rho_{\max} \sqrt{\tfrac{n-1}{p}\,\tfrac{\log(n-1)}{\log p}} \right)\] \[\times \left( 1 + \frac{2 c_1(n) c_2(n) \sqrt{5} \left( 1 + \left(\sqrt{\tfrac{n}{p}} + 3\right)^2 p \rho_{\max}\right) \sqrt{p \rho_{\max}}}{\nu^2} \right).\] obtained by setting \(c=3\), and computing \(p\bar{C}_i C_i\) after putting \(\sqrt{5p\rho_{\max}}\) and \((\sqrt{n/p} + 3\sqrt{p})^2\rho_{\max}\) bounds in event \(W_{n+1}\), into \(\|\boldsymbol{x}_{n+1}\|_2\) and \(\omega_{\max}\), respectively. Next, \[\begin{align} \mathbb{P}[K_i^c] &= \mathbb{P}\!\left[ \frac{C}{p} < \bar{C}_i C_i \right] \;\leq\; \mathbb{P}\!\left[ C < p \bar{C}_i C_i \,\big|\, W_{n+1}^c \right] + \mathbb{P}[W_{n+1}] \nonumber \\ &= \mathbb{P}[C < C] + \mathbb{P}[W_{n+1}] \;=\; \mathbb{P}[W_{n+1}] . \end{align}\] The term \(\mathbb{P}[W_{n+1}]\) is exponentially small because \(\boldsymbol{x}_{n+1} \sim N(0,\Sigma)\) with \(\rho_{\max} = \sigma_{\max}(\Sigma)\), leading to \[\mathbb{P}[W_{n+1}] \;\leq\; \mathbb{P}\!\left[ \|\boldsymbol{x}_{n+1}\|_2^2 > 5p\rho_{\max} \right] + \mathbb{P}\!\left[ \sigma_{\max}(XX^\top) > (\sqrt{n}+3\sqrt{p})^2 \rho_{\max} \right] \;\leq\; 2e^{-p},\] due to result in Section 6.3 and Section 6.4. In summary, since for \(p \geq 1\) we have \(\tfrac{1}{1-e^{-p}} < 2\), for \(c=3\) we obtain \[\mathbb{P}[\tilde{E}_{n+1,i}] \;\leq\; \frac{4}{(n-1)^3} + \frac{4}{p^3} + 2e^{-p}.\]

Since \(\boldsymbol{x}_{i}\) and \(\boldsymbol{x}_{n+1}\) follow same distribution, that is \(\boldsymbol{x}_i\sim N(0,\Sigma)\), the same argument implies that \[\mathbb{P}[\tilde{E}_{i}]\leq\frac{4}{(n-1)^3}+\frac{4}{p^3}+2e^{-p}.\] The detailed proof for the bound of \(\mathbb{P}[\tilde{E}_{i}]\) can also be found in [10].

As a result, we have \[\begin{align} \mathbb{P}[G]&\leq\frac{1}{1-q_n-\tilde{q}_n}\left(\frac{8n}{(n-1)^3}+\frac{8n}{p^3}+4ne^{-p}\right)+q_n+\tilde{q}_n\nonumber \\ &\leq\left(\frac{16n}{(n-1)^3}+\frac{16n}{p^3}+8ne^{-p}\right)+q_n+\tilde{q}_n. \end{align}\] It is clear that \(\left[\left(\frac{16n}{(n-1)^3}+\frac{16n}{p^3}+8ne^{-p}\right)+q_n+\tilde{q}_n\right]\to0\) when \(n\to\infty\).

Thus, we obtain a result similar to the result in Section 6.5. That is, with probability at least \(1-\left(\frac{16n}{(n-1)^3}+\frac{16n}{p^3}+8ne^{-p}\right)-q_n-\tilde{q}_n\), the following bound is valid \[\max_{1\leq i\leq n}|\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} -\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i} |\leq\frac{C_0}{\sqrt{p}},\] where \(C_0\) is defined as follows \[\begin{align} &C_0 := \; \left( \frac{216 c^{3/2}}{\nu^{3}} \right) \left( 1 + \sqrt{\delta_{0}}(\sqrt{\delta_{0}}+3)^{2} \frac{c \log n}{\log p} \right)\left( c_{1}^{2}(n)c_{2}(n) + c_{1}^{3}(n)c_{2}^{2}(n) \, \frac{5\big(c^{1/2} + c^{3/2}(\sqrt{\delta_{0}}+3)^{2}\big)}{\nu^{2}} \right). \end{align}\]

Note that in the presentation of Theorem 1, we replaced respectively \(96\sqrt{5}\) and \(2\sqrt{3}\) with the upper-bounds \(216\) and \(5\), and we replaced \(\sqrt{\frac{n-1}{p} \frac{\log(n-1)}{\log p}}\) with the upper bound \(\sqrt{\frac{n}{p} \frac{\log n}{\log p}}\). We also used \(\delta_0\) to denote \(n/p\).

8 Proof of Theorem 2↩︎

Using result Section 6.5, with probability at least \(1-p_2(n)\), the following holds \[\begin{align} \label{prof95thm2951} \max_{1\leq i\leq n}|\boldsymbol{x}_{i}^\top\tilde{\theta}_{/i} -\boldsymbol{x}_{i}^\top\hat{\theta}_{/i} |\leq\frac{Q_0}{\sqrt{p}}. \end{align}\tag{26}\] Then with probability at least \(1-p_2(n)\), following holds \[\begin{align} \label{prof95thm2953} \max_{1\leq i\leq n}|\boldsymbol{x}_{i}^\top\tilde{\theta}_{/i} -\boldsymbol{x}_{i}^\top\hat{\theta}_{/i}|=o(1). \end{align}\tag{27}\] Plugging (27 ) into \(\left|R_{i}^{LOO}-\tilde{R}_{i}^{LOO}\right|\), using Assumption 4, with probability at least \(1-p_2(n)\) the following result holds \[\begin{align} \label{prof95thm2954} \left|R_{i}^{LOO}-\tilde{R}_{i}^{LOO}\right|=&\left|(|y_i-f(\boldsymbol{x}_i^\top\hat{\theta}_{/i})|-|y_i-f(\boldsymbol{x}_i^\top\tilde{\theta}_{/i})|)\right|\notag \\ \leq&\left|f(\boldsymbol{x}_i^\top\hat{\theta}_{/i})-f(\boldsymbol{x}_i^\top\tilde{\theta}_{/i})\right|\notag \\ \leq& L\cdot\max_{1\leq i\leq n}|\boldsymbol{x}_i^\top\hat{\theta}_{/i}-\boldsymbol{x}_i^\top\tilde{\theta}_{/i}|\notag \\ =&o(1). \end{align}\tag{28}\] Using Theorem 1 and Assumption 4, with probability at least \(1-p_1(n)\) the following result holds \[\begin{align} \label{prof95thm2955} \left|f(\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i})-f(\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i})\right|\leq L\cdot\left|\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i} -\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i}\right|=o(1). \end{align}\tag{29}\] Then with probability at least \((1-p_1(n)-p_2(n))\), the following results hold for \(i=1,2,...,n\): \[\begin{align} \label{prof95thm2956} \left|(f(\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i})-\tilde{R}_i^{LOO})-(f(\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i})-R_i^{LOO})\right|=o(1); \end{align}\tag{30}\] \[\begin{align} \label{prof95thm2957} \left|(f(\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i})+\tilde{R}_i^{LOO})-(f(\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i})+R_i^{LOO})\right|=o(1). \end{align}\tag{31}\] With (30 ) and (31 ), using Lemma 2, we can easily derive that \[\begin{align} \label{prof95thm2958} \hat{q}_{n,\alpha}^-\{f(\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i})-\tilde{R}_i^{LOO}\}=\hat{q}_{n,\alpha}^-\{f(\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i})-R_i^{LOO}\}+o(1); \end{align}\tag{32}\] \[\begin{align} \label{prof95thm2959} \hat{q}_{n,\alpha}^+\{f(\boldsymbol{x}_{n+1}^\top\tilde{\theta}_{/i})+\tilde{R}_i^{LOO}\}=\hat{q}_{n,\alpha}^+\{f(\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i})+R_i^{LOO}\}+o(1). \end{align}\tag{33}\] That is, with probability at least \((1-p_1(n)-p_2(n))\), the following results hold \[\begin{align} \tilde{U}_{jk+}=U_{jk+}+o(1),\;\tilde{L}_{jk+}=L_{jk+}+o(1). \end{align}\] We can utilize similar method to conclude that, with probability at least \((1-p_1(n)-p_2(n))\), the following results hold \[\begin{align} \tilde{U}_{jkm}=U_{jkm}+o(1),\;\tilde{L}_{jkm}=L_{jkm}+o(1). \end{align}\] Theorem 2 has been proved.

9 Proof of Theorem 3 & 4↩︎

Recall that in Assumption 4 we defined that \[p_1(n)=\left(\frac{16n}{(n-1)^3}+\frac{16n}{p^3}+8ne^{-p}\right)+q_n+\tilde{q}_n\] and \[p_2(n)=\left(\frac{8n}{(n-1)^3}+\frac{8n}{p^3}+4ne^{-p}\right)+q_n+\tilde{q}_n.\] Under Assumption 1 to Assumption 4, and the condition that \(n,p\to\infty\), \(n/p=\delta_0\in(0,\infty)\), it is clear that \[p_1(n)\xrightarrow{\;\text{n\to\infty}\;} 0,\quad p_2(n)\xrightarrow{\;\text{n\to\infty}\;} 0.\] Using (32 ), (33 ) and Assumption 4, we obtain that, with probability at least \((1-p_1(n)-p_2(n))\), the following holds \[\begin{align} \mathbb{P}\{y_{n+1}\in\tilde{C}_{n,\alpha}^{Jackknife+}\}=\mathbb{P}\{y_{n+1}\in\hat{C}_{n,\alpha}^{Jackknife+}\}+L\cdot o(1)=\mathbb{P}\{y_{n+1}\in\hat{C}_{n,\alpha}^{Jackknife+}\}+o(1). \end{align}\] According to [2], we have \[\begin{align} \label{orginal95conclusion95jk43951} \hat{C}_{n,\alpha}^{Jackknife+}=[\hat{q}_{n,\alpha}^{-}\{f(\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i})-R_i^{LOO}\},\hat{q}_{n,\alpha}^{+}\{f(\boldsymbol{x}_{n+1}^\top\hat{\theta}_{/i})+R_i^{LOO}\}] \end{align}\tag{34}\] and \[\begin{align} \label{orginal95conclusion95jk43952} \mathbb{P}\{y_{n+1}\in\hat{C}_{n,\alpha}^{Jackknife+}\}\geq 1-2\alpha. \end{align}\tag{35}\]

As s result, using (35 ), we have \[\begin{align} \mathbb{P}\{y_{n+1}\in\tilde{C}_{n,\alpha}^{Jackknife+}\}\geq (1-2\alpha-o(1))\cdot(1-p_1(n)-p_2(n))=1-2\alpha-o(1). \end{align}\]

Theorem 3 has been proved.

Proof of Theorem 4 is similar to Theorem 3.

10 Proof of lemmas↩︎

10.1 Proof of Lemma 2↩︎

Lemma 2 follows from the following more precise version:

11 Proof of Theorem 6↩︎

The proof of Theorem 6 relies on some auxiliary results (for simplicity, we define \(\hat{\mu}_{/i}(X)=X^\top\hat{\beta}_{/i}\) and \(\hat{\mu}(X)=X^\top\hat{\beta}\)):

Next, recall that \(\hat{\mu}^y(X_i):=X_i^{\top}\hat{\beta}^y\), \(i=1,\dots,n+1\), where \(\hat{\beta}^y\) denotes the output of the regression algorithm trained on the augmented dataset \(\{(X_1,y_1),\dots,(X_n,y_n),(X_{n+1},y)\}\). Also, adopt the notations \[\begin{align} R_i&:=y_i-X_i^{\top}\hat{\beta}, \quad i=1,\dots, n, \\ \psi(t)&:=\rho'(t), \quad t\in\mathbb{R}. \end{align}\] We then have:

References↩︎

---

1. Emails: jcong3@illinois.edu, jingbol@illinois.edu. This research was supported in part by NSF Grant DMS-2515510.↩︎