Detecting and Correcting for Label Shift with Black Box Predictors

Introduction

Assume that in August we train a pneumonia predictor. Our features consist of chest X-rays administered in the previous year (distribution $P$) and the labels binary indicators of whether a physician diagnoses the patient with pneumonia. We train a model $f$ to predict pneumonia given an X-ray image. Assume that in the training set $.1\%$ of patients have pneumonia. We deploy $f$ in the clinic and for several months, it reliably predicts roughly $.1\%$ positive.

Fast-forward to January (distribution $Q$): Running $f$ on the last week’s data, we find that $5\%$ of patients are predicted to have pneumonia! Because $f$ remains fixed, the shift must owe to a change in the marginal $p(\boldsymbol{x})$, violating the familiar iid assumption. Absent familiar guarantees, we wonder: Is $f$ still accurate? What’s the real current rate of pneumonia? Shouldn’t our classifier, trained under an obsolete prior, underestimate pneumonia when uncertain? Thus, we might suspect that the real prevalence is greater than $5\%$.

Given only labeled training data, and unlabeled test data, we desire to: (i) detect distribution shift, (ii) quantify it, and (iii) correct our model to perform well on the new data. Absent assumptions on how $p(y,\boldsymbol{x})$ changes, the task is impossible. However, under assumptions about what P and Q have in common, we can still make headway. Two candidates are covariate shift (where $p(y|\boldsymbol{x})$ does not change) and label shift (where $p(\boldsymbol{x}|y)$ does not change). Schölkopf et al. (2012) observe that covariate shift corresponds to causal learning (predicting effects), and label shift to anticausal learning (predicting causes).

We focus on label shift, motivated by diagnosis (diseases cause symptoms) and recognition tasks (objects cause sensory observations). During a pneumonia outbreak, $p(y|\boldsymbol{x})$ (e.g. flu given cough) might rise but the manifestations of the disease $p(\boldsymbol{x}|y)$ might not change. Formally, under label shift, we can factorize the target distribution as

We introduce Black Box Shift Estimation (BBSE) to estimate label shift using a black box predictor $f$. BBSE estimates the ratios $w_{l}=q(y_{l})/p(y_{l})$ for each label $l$, requiring only that the expected confusion matrix is invertible For degenerate confusion matrices, a variant using soft predictions may be preferable.. We estimate $\hat{\boldsymbol{w}}$ by solving a linear system $A\boldsymbol{x}=b$ where $A$ is the confusion matrix of $f$ estimated on training data (from P) and $b$ is the average output of $f$ calculated on test samples (from Q). We make the following contributions:

Applications of BBSE to statistical tests for detecting distribution label shift

Model correction through importance-weighted Empirical Risk Minimization.

A comprehensive empirical validation of BBSE.

Compared to approaches based on Kernel Mean Matching (KMM) (Zhang et al., 2013), EM (Chan & Ng, 2005), and Bayesian inference (Storkey, 2009), BBSE offers the following advantages: (i) Accuracy does not depend on data dimensionality; (ii) Works with arbitrary black box predictors, even biased, uncalibrated, or inaccurate models; (iii) Exploits advances in deep learning while retaining theoretical guarantees: better predictors provably lower sample complexity; and (iv) Due to generality, could be a standard diagnostic / corrective tool for arbitrary ML models.

Prior Work

Despite its wide applicability, learning under label shift with unknown $q(y)$ remains curiously under-explored. Noting the difficulty of the problem, Storkey (2009) proposes placing a (meta-)prior over $p(y)$ and inferring the posterior distribution from unlabeled test data. Their approach requires explicitly estimating $p(\boldsymbol{x}|y)$, which may not be feasible in high-dimensional datasets. Chan & Ng (2005) infer $q(y)$ using EM but their method also requires estimating $p(\boldsymbol{x}|y)$. Schölkopf et al. (2012) articulates connections between label shift and anti-causal learning and Zhang et al. (2013) extend the kernel mean matching approach due to (Gretton et al., 2009) to the label shift problem. When $q(y)$ is known, label shift simplifies to the problem of changing base rates (Bishop, 1995; Elkan, 2001). Previous methods require estimating $q(\boldsymbol{x})$, $q(\boldsymbol{x})/p(\boldsymbol{x})$, or $p(\boldsymbol{x}|y)$, often relying on kernel methods, which scale poorly with dataset size and underperform on high-dimensional data.

Covariate shift, also called sample selection bias, is well-studied (Zadrozny, 2004; Huang et al., 2007; Sugiyama et al., 2008; Gretton et al., 2009). Shimodaira (2000) proposed correcting models via weighting examples in ERM by $q(\boldsymbol{x})/p(\boldsymbol{x})$. Later works estimate importance weights from the available data, e.g., Gretton et al. (2009) propose kernel mean matching to re-weight training points.

The earliest relevant work to ours comes from econometrics and addresses the use of non-random samples to estimate behavior. Heckman (1977) addresses sample selection bias, while (Manski & Lerman, 1977) investigates estimating parameters under choice-based and endogenous stratified sampling, cases analogous to a shift in the label distribution. Also related, Rosenbaum & Rubin (1983) introduce propensity scoring to design unbiased experiments. Finally, we note a connection to cognitive science work showing that humans classify items differently depending on other items they appear alongside (Zhu et al., 2010).

Post-submission, we learned of antecedents for our estimator in epidemiology (Buck et al., 1966) and revisited by Forman (2008); Saerens et al. (2002). These papers do not develop our theoretical guarantees or explore the modern ML setting where $\boldsymbol{x}$ is massively higher-dimensional than $y$, bolstering the value of dimensionality reduction.

Problem setup

In general, this task is impossible – $P$ and $Q$ might not share support. This paper considers $3$ extra assumptions: {enumerate*}

The label shift (also known as target shift) assumption

For every $y\in\mathcal{Y}$ with $q(y)>0$ we require $p(y)>0$.Assumes the absolute continuity of the (hidden) target label’s distribution with respect to the source’s, i.e. $dq(y)/dp(y)$ exists.

Access to a black box predictor $f:\mathcal{X}\rightarrow\mathcal{Y}$ where the expected confusion matrix $\mathbf{C}_{p}(f)$ is invertible.

We now comment on the assumptions. A.1 corresponds to anti-causal learning. This assumption is strong but reasonable in many practical situations, including medical diagnosis, where diseases cause symptoms. It also applies when classifiers are trained on non-representative class distributions: Note that while visions systems are commonly trained with balanced classes (Deng et al., 2009), the true class distribution for real tasks is rarely uniform.

Assumption A.2 addresses identifiability, requiring that the target label distribution’s support be a subset of training distribution’s. For discrete $\mathcal{Y}$, this simply means that the training data should contain examples from every class.

Assumption A.3 requires that the expected predictor outputs for each class be linearly independent. This assumption holds in the typical case where the classifier predicts class $y_{i}$ more often given images actually belong to $y_{i}$ than given images from any other class $y_{j}$. In practice, $f$ could be a neural network, a boosted decision-tree or any other classifier trained on a holdout training data set. We can verify at training time that the empirical estimated normalized confusion matrix is invertible. Assumption A.3 generalizes naturally to soft-classifiers, where $f$ outputs a probability distribution supported on $\mathcal{Y}$. Thus BBSE can be applied even when the confusion matrix is degenerate.

Main results

We now derive the main results for estimating $w(y)$ and $q(y)$. Assumption A.1 has the following implication:

Denote by $\hat{y}=f(\boldsymbol{x})$ the output of a fixed function $f:\mathcal{X}\rightarrow\mathcal{Y}$. If Assumption A.1 holds, then

The proof is simple: recall that $\hat{y}$ depends on $y$ only via $\boldsymbol{x}$. By A.1, $p(\boldsymbol{x}|y)=q(\boldsymbol{x}|y)$ and thus $q(\hat{y}|y)=p(\hat{y}|y)$.

Next, combine the law of total probability and Lemma 1 and we arrive at

We estimate $p(\hat{y}|y)$ and $p(\hat{y},y)$ using $f$ and data from source distribution $P$, and $q(\hat{y})$ with unlabeled test data drawn from target distribution $Q$. This leads to a novel method-of-moments approach for consistent estimation of the shifted label distribution $q(y)$ and the weights $w(y)$.

We can now rewrite Equation (1) in matrix form:

Using plug-in maximum likelihood estimates of the above quantities yields the estimators

where $\hat{\boldsymbol{\nu}}_{y}$ is the plug-in estimator of $\boldsymbol{\nu}_{y}$.

Next, we establish that the estimators are consistent.

If Assumption A.1, A.2, A.3 are true, then as $n,m\rightarrow\infty$, $\hat{\boldsymbol{w}}\overset{\text{a.s.}}{\longrightarrow}\boldsymbol{w}$ and $\hat{\boldsymbol{\mu}}_{y}\overset{\text{a.s.}}{\longrightarrow}\boldsymbol{\mu}_{y}.$

The proof (see Appendix B) uses the First Borel-Cantelli Lemma to show that the probability that the entire sequence of empirical confusion matrices with data size $n+1,...,\infty$ are simultaneously invertible converges to $1$, thereby enabling us to use the continuous mapping theorem after applying the strong law of large numbers to each component.

We now address our estimators’ convergence rates.

Assume that A.3 holds robustly. Let $\sigma_{\min}$ be the smallest eigenvalue of ${\mathbf{C}}_{\hat{y},y}$. There exists a constant $C>0$ such that for all $n>80\log(n)\sigma_{\min}^{-2}$, with probability at least $1-3kn^{-10}-2km^{-10}$ we have

The bounds give practical insights (explored more in Section 7). In (2), the square error depends on the sample size and is proportional to $1/n$ (or $1/m$). There is also a $\|\boldsymbol{w}\|^{2}$ term that reflects how different the source and target distributions are. In addition, $\sigma_{\min}$ reflects the quality of the given classifier $f$. For example, if $f$ is a perfect classifier, then $\sigma_{\min}=\min_{y\in\mathcal{Y}}p(y)$. If $f$ cannot distinguish between certain classes at all, then ${\mathbf{C}}_{\hat{y},y}$ will be low-rank, $\sigma_{\min}=0$, and the technique is invalid, as expected.

We now parse the error bound of $\hat{\boldsymbol{\mu}}_{y}$ in (3). The first term $\|\boldsymbol{w}\|^{2}/n$ is required even if we observe the importance weight $\boldsymbol{w}$ exactly. The second term captures the additional error due to the fact that we estimate $\boldsymbol{w}$ with predictor $f$. Note that $\|\boldsymbol{\nu}_{y}\|_{\infty}^{2}\leq 1$ and can be as small as $1/k^{2}$ when $p(y)$ is uniform. Note that when $f$ correctly classifies each class with the same probability, e.g. $0.5$, then $\|\boldsymbol{\nu}_{y}\|^{2}/\sigma_{\min}^{2}$ is a constant and the bound cannot be improved.

Assumption A.2 ensures that $\boldsymbol{w}<\infty$.

By completing the square and Cauchy-Schwartz inequality,

Substitute into the above inequality and use (1) we get

We now provide a high probability bound on the Euclidean norm of $E_{2}$, the operator norm of $E_{1}$, which will give us an operator norm bound of $[E_{1}^{-1}+{\mathbf{C}}_{\hat{y},y}^{-1}]^{-1}$ and $({\mathbf{C}}_{\hat{y},y}+E_{1})^{-1}$ under our assumption on $n$, and these will yield a high probability bound on the square estimation error.

Take $t=\sqrt{20n\log n}$ and use the assumption that $n\geq 4\log n/9$ (which holds under our assumption on $n$ since $\sigma_{\min}<1$). Then with probability at least $1-2kn^{-10}$

Using the assumption on $n$, we have $\|E_{1}\|\leq\sigma_{\min}/2$

Also, we have $\|({\mathbf{C}}_{\hat{y},y}+E_{1})^{-1}\|\leq\frac{2}{\sigma_{\min}}$.

Euclidean norm of $E_{2}$. Note that $[E_{2}]_{l}=\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}(f(\boldsymbol{x}_{i}^{\prime})=l)-q(f(\boldsymbol{x}_{i}^{\prime})=l)$. By the standard Hoeffding’s inequality and union bound argument, we have that with probability larger than $1-2km^{-10}$

By Hoeffding’s inequality $\|E_{0}\|_{\infty}\leq\sqrt{\frac{20\log n}{n}}$ with probability larger than $1-kn^{-10}$. Combining with (5) yields

which holds with probability $1-3kn^{-10}-2km^{-10}$. ∎

Application of the results

Formally, detection can be cast as a hypothesis testing problem where the null hypothesis is $\mathbf{H}_{0}:q(y)=p(y)$ and the alternative hypothesis is that $\mathbf{H}_{1}:q(y)\neq p(y).$ Recall that we observe neither $q(y)$ nor any samples from it. However, we do observe unlabeled data from the target distribution and our predictor $f$.

Under Assumption A.1, A.2 and for each classifier $f$ satisfying A.3 we have that $q(y)=p(y)$ if and only if $p(\hat{y})=q(\hat{y})$.

Plug $P$ and $Q$ into (1) and apply Lemma 1 with assumption A.1. The result follows directly from our analysis in the proof of Proposition 2 that shows $p(\hat{y},y)$ is invertible under the assumptions A.2 and A.3. ∎

Thus, under weak assumptions, we can test $\mathbf{H}_{0}$ by running two-sample tests on readily available samples from $p(\hat{y})$ and $q(\hat{y})$. Examples include the Kolmogorov-Smirnoff test, Anderson-Darling or the Maximum Mean Discrepancy. In all tests, asymptotic distributions are known and we can almost perfectly control the Type I error. The power of the test ($1$-Type II error) depends on the classifier’s performance on distribution $P$, thereby allowing us to leverage recent progress in deep learning to attack the classic problem of detecting non-stationarity in the data distribution.

One could also test whether $p(x)=q(x)$. Under the label-shift assumption this is implied by $q(y)=p(y)$. The advantage of testing the distribution of $f(\boldsymbol{x})$ instead of $\boldsymbol{x}$ is that we only need to deal with a one-dimensional distribution. Per theory and experiments in (Ramdas et al., 2015) two-sample tests in high dimensions are exponentially harder.

One surprising byproduct is that we can sometimes use this approach to detect covariate-shift, concept-shift, and more general forms of nonstationarity.

For any fixed measurable $f:\mathcal{X}\rightarrow\mathcal{Y}$

This follows directly from the measurability of $f$.

While the converse is not true in general, $p(\hat{y})=q(\hat{y})$ does imply that for every measurable $\mathcal{S}\subset\mathcal{Y}$,

This suggests that testing $\hat{\mathbf{H}}_{0}:p(\hat{y})=q(\hat{y})$ may help us to determine if there’s sufficient statistical evidence that domain adaptation techniques are required.

2 Black Box Shift Correction (BBSC)

Our estimator also points to a systematic method of correcting for label-shift via importance-weighted ERM. Specifically, we propose the following algorithm:

Note that for classes that occur rarely in the test set, BBSE may produce negative importance weights. During ERM, a flipped sign would cause us to maximize loss, which is unbounded above. Thus, we clip negative weights to .

Owing to its efficacy and generality, our approach can serve as a default tool to deal with domain adaptation. It is one of the first things to try even when the label-shift assumption doesn’t hold. By contrast, the heuristic method of using logistic-regression to construct importance weights (Bickel et al., 2009) lacks theoretical justification that the estimated weights are correct.

Even in the simpler problem of average treatment effect (ATE) estimation, it’s known that using estimated propensity can lead to estimators with large variance (Kang & Schafer, 2007). The same issue applies in supervised learning. We may prefer to live with the biased solution from the unweighted ERM rather than suffer high variance from an unbiased weighted ERM. Our proposed approach offers a consistent low-variance estimator under label shift.

Experiments

We experimentally demonstrate the power of BBSE with real data and simulated label shift. We organize results into three categories — shift detection with BBSD, weight estimation with BBSE, and classifier correction with BBSC. BBSE-hard denotes our method where $f$ yields classifications. In BBSE-soft, $f$ outputs probabilities.

Label Shift Simulation To simulate distribution shift in our experiments, we adopt the following protocols: First, we split the original data into train, validation, and test sets. Then, given distributions $p(y)$ and $q(y)$, we generate each set by sampling with replacement from the appropriate split. In knock-out shift, we knock out a fraction $\delta$ of data points from a given class from training and validation sets. In tweak-one shift, we assign a probability $\rho$ to one of the classes, the rest of the mass is spread evenly among the other classes. In Dirichlet shift, we draw $p(y)$ from a Dirichlet distribution with concentration parameter $\alpha$. With uniform $p(y)$, Dirichlet shift is bigger for smaller $\alpha$.

Label-shift detection We conduct nonparametric two-sample tests as described in Section 5.1 using the MNIST handwritten digits data set. To simulate the label-shift, we randomly split the training data into a training set, a validating set and a test set, each with 20,000 data points, and apply knock-out shift on class $y=5$ Random choice for illustration, method works on all classes.. Note that $p(y)$ and $q(y)$ differ increasingly as $\delta$ grows large, making shift detection easier. We obtain $f$ by training a two-layer ReLU-activated Multilayer Perceptron (MLP) with 256 neurons on the training set for five epochs. We conduct a two-sample test of whether the distribution of $f(\text{Validation Set})$ and $f(\text{Test Set})$ are the same using the Kolmogorov-Smirnov test. The results, summarized in Figure 1, demonstrate that BBSD (1) produces a $p$-value that distributes uniformly when $\delta=0$ Thus we can control Type I error at any significance level. (2) provides more power (less Type II error) than the state-of-the-art kernel two-sample test that discriminates $p(\boldsymbol{x})$ and $q(\boldsymbol{x})$ at $\delta=0.5$, and (3) gets better as we train the black-box predictor even more.

Weight estimation and label-shift correction We evaluate BBSE on MNIST by simulating label shift and datasets of various sizes. Specifically, we split the training data set randomly in two, using first half to train $f$ and the second half to estimate $\boldsymbol{w}$. We use then use the full training set for weighted ERM. As before, $f$ is a two-layer MLP. For fair comparisons with baselines, the full training data set is used throughout (since they do not need $f$ without data splitting). We evaluate our estimator $\hat{\boldsymbol{w}}$ against the ground truth $\boldsymbol{w}$ and by the prediction accuracy of BBSC on the test set. To cover a variety of different types of label-shift, we take $p(y)$ as a uniform distribution and generate $q(y)$ with Dirichlet shift for $\alpha=0.1,1.0,10.0$ (Figure 2).

Label-shift correction for CIFAR10 Next, we extend our experiments to the CIFAR dataset, using the same MLP and this time allowing it to train for 10 epochs. We consider both tweak-one and Dirichlet shift, and compare BBSE to the unweighted classifier under varying degrees of shift (Figure 4). For the tweak-one experiment, we try $\rho\in\{0.0,0.1,...,1.0\}$, averaging results over all 10 choices of the tweaked label, and plotting the variance. For the Dirichlet experiments, we sample $20$ $q(y)$ for every choice of $\alpha$ in the range {1000, 100, …, .001}. Because kernel-based baselines cannot handle datasets this large or high-dimensional, we compare only to unweighted ERM.

Kernel mean matching (KMM) baselines We compare BBSE to the state-of-the-art kernel mean matching (KMM) methods. For the detection experiments (Figure 1), our baseline is the kernel B-test (Zaremba et al., 2013), an extension of the kernel max mean discrepancy (MMD) test due to Gretton et al. (2012) that boasts nearly linear-time computation and little loss in power. We compare BBSE to a KMM approach Zhang et al. (2013), that solves

For fair comparison, we used the original authors’ implementations as baselines https://github.com/wojzaremba/btest, http://people.tuebingen.mpg.de/kzhang/Code-TarS.zip and also used the median trick to adaptively tune the RBF kernel’s hyperparameter. A key difference is that BBSE matches the distribution of $\hat{y}$ rather than distribution of $\boldsymbol{x}$ like (Zhang et al., 2013) and we learn $f$ through supervised learning rather than by specifying a feature map $\phi$ by choosing a kernel up front.

Note that KMM, like many kernel methods, requires the construction and inversion of an $n\times n$ Gram matrix, which has complexity of $O(n^{3})$. This hinders its application to real-life machine learning problems where $n$ will often be 100s of thousands. In our experiments, we find that the largest $n$ for which we can feasibly run the KMM code is roughly $8,000$ and that is where we unfortunately have to stop for the MNIST experiment. For the same reason, we cannot run KMM for the CIFAR10 experiments. The MSE curves in Figure 2 for estimating $\boldsymbol{w}$ suggest that the convergence rate of KMM is slower than BBSE by a polynomial factor and that BBSE better handles large datasets.

Discussion

Constructing the training Set The error bounds on our estimates depend on the norm of the true vector $w(y):=q(y)/p(y)$. This confirms the common sense that absent any assumption on $q(y)$, and given the ability to select class-conditioned examples for annotations one should build a dataset with uniform $p(y)$. Then it’s always possible to apply BBSE successfully at test time to correct $f$.

Sporadic Shift In some settings, $p(y)$ might change only sporadically. In these cases, when no label shift occurs, applying BBSC might damage the classifier. For these cases, we prose to combine detection and estimation, correcting the classifier only when a shift has likely occurred.

Using known predictor In our experiments, $f$ has been trained using a random split of the data set, which makes BBSEto perform worse than baseline when the data set is extremely small. In practice, especially in the context of web services, there could be a natural predictor $f$ that is currently being deployed whose training data were legacy and have little to do with the two distributions that we are trying to distinguish. In this case, we do not lose that factor of $2$ and we do not suffer from the variance in training $f$ with a small amount of data. This could allow us to detect mild shift in distributions in very short period of time. Making it suitable for applications such as financial market prediction.

BBSE with degenerate confusion matrices In practice, sometime confusion matrices will be degenerate. For instance, when a class $i$ is rare under $P$, and the features are only partially predictive, we might find that $p(f(\boldsymbol{x})=i)=0$. In these cases, two straightforward variations on the black box method may still work: First, while our analysis focuses on confusion matrices, it easily extends to any operator $f$, such as soft probabilities. If each class $i$, even if $i$ is never the argmax for any example, so long as $p(\hat{y}=i|y=i)>p(\hat{y}=i|y=j)$ for any $j\neq i$, the soft confusion matrix will be invertible. Even when we produce and operator with an invertible confusion matrix, two options remain: We can merge $c$ classes together, yielding a $(k-c)\times(k-c)$ invertible confusion matrix. While we might not be able to estimate the frequencies of those $c$ classes, we can estimate the others accurately. Another possibility is to compute the pseudo-inverse.

Future Work As a next step, we plan to extend our methodology to the streaming setting. In practice, label distributions tend to shift progressively, presenting a new challenge: if we apply BBSE on trailing windows, then we face a trade-off. Looking far back increases $m$, lowering estimation error, but the estimate will be less fresh. The use of propensity weights $w$ on $y$ makes BBSE amenable to doubly-robust estimates, the typical bias-variance tradeoff, and related techniques, common in covariate shift correction.

Acknowledgments

We are grateful for extensive insightful discussions and feedback from Kamyar Azizzadenesheli, Kun Zhang, Arthur Gretton, Ashish Khetan Kumar, Anima Anandkumar, Julian McAuley, Dustin Tran, Charles Elkan, Max G’Sell, Alex Dimakis, Gary Marcus, and Todd Gureckis.

References

Appendix A Additional discussion

In this section we provide a few answers to some questions people may have when using our proposed techniques.

The LHS can be estimated by plugging in $\hat{\boldsymbol{w}}$ and a stochastic approximation of the expectation using labeled data from the source domain and the RHS can be estimated by the sample mean using unlabeled data from the target domain. In particular, if label-shift assumption is true or a good approximation, then

should be on the same order as the statistical error that we can calculate by $m,n$ and the error of $\hat{\boldsymbol{w}}$ in estimating $\boldsymbol{w}$.

Model selection criterion and the choice of f𝑓f.

Our analysis assumes that $f$ is fixed and given, but in practice, often we need to train $f$ from the same data set. Given a number of choices, one may wonder which blackbox predictor $f$ should we prefer out of a collection of $\mathcal{F}$? Our theoretical results suggest a natural quantity: the smallest singular value of the confusion matrix, for choosing the blackbox predictors. Note that the smallest singular value is a quantity that can be estimated using only labeled data from the source domain. Therefore a practical heuristic to use is to the $f$ that maximizes the smallest singular value of the corresponding $\hat{C}_{f}$. Figure 5 plots the smallest singular value of the confusion matrices as the number of epochs of training $f$ gets larger. The model we use is the same multi-layer perceptron that we used for our experiments and the source distribution is one that we knocks off 80% of the fifth class. This is the same model and data set we used in Figure 1(c). Referring to $\delta=0.8$ in Figure 1(c), we see that the test power of $f$ that is trained for only one epoch is much lower than the $f$ that is trained for five epochs, and the gap in the smallest singular values is predicative of the fact at least qualitatively.

Is data splitting needed?

Recall that we train the model $f$ and estimate $\boldsymbol{w}$ using two independent splits of the labeled data set drawn from the same distribution. In practice, especially when $n$ is large, using the same data to train $f$ and to estimate $\boldsymbol{w}$ will be more data efficient. This comes at a price of a small bias. It is unclear how to quantify that bias but the data-reuse version could be useful in practice as a heuristic.

Appendix B Proofs

We present the proofs of Lemma 1 and Proposition 2 in this Appendix.

We applied A.1 to the second equality, and used the conditional independence \hat{y}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}y|x under $P$ and $Q$ together with $p(\hat{y}|\boldsymbol{x})$ being determined by $f$, which is fixed. ∎

A.2 ensures that $\boldsymbol{w}<\infty$. By Assumption A.3, ${\mathbf{C}}_{\hat{y},y}$ is invertible. Let $\delta>0$ be its smallest singular value. We bound the probability that $\hat{\mathbf{C}}_{\hat{y},y}$ is not invertible:

This ensures that as $n\rightarrow\infty$, $\hat{\mathbf{C}}_{\hat{y},y}$ is invertible almost surely. By the strong law of large numbers (SLLN), as $n\rightarrow\infty$ $\hat{\mathbf{C}}_{\hat{y},y}\overset{\text{a.s.}}{\longrightarrow}\mathbf{C}_{\hat{y},y}$ and $\hat{\boldsymbol{\nu}}_{y}\overset{\text{a.s.}}{\longrightarrow}\boldsymbol{\nu}_{y}$. Similarly, as $m\rightarrow\infty$, $\hat{\boldsymbol{\mu}}_{\hat{y}}\overset{\text{a.s.}}{\longrightarrow}\boldsymbol{\mu}_{\hat{y}}$. Combining these with (6) and applying the continuous mapping theorem with the fact that the inverse of an invertible matrix is a continuous mapping we get that

Appendix C Concentration inequalities

Let $x_{1},...,x_{n}$ be independent random variables bounded by $[a_{i},b_{i}]$. Then $\bar{x}=\frac{1}{n}\sum_{i=1}^{n}x_{i}$ obeys for any $t>0$

Let $\mathbf{Z}_{1},...,\mathbf{Z}_{n}$ be independent random matrices with dimension $d_{1}\times d_{2}$ and each satisfy

almost surely. Define the variance parameter