Black-box shift estimation

Predictions inherit the invariance, and that gives a linear system. Because $\hat y$ depends on $y$ only through $x$, A1 gives $q(\hat y|y)=p(\hat y|y)$, and total probability under $Q$ reads $$q(\hat y)=\sum_yp(\hat y|y)\,q(y)=\sum_yp(\hat y,y)\,w(y),\qquad\text{that is,}\qquad \mu_{\hat y}=Cw.$$ The left side is estimated from unlabeled target data, $C$ from labeled source data, and A3 makes the system solvable. It is a method of moments in a $k$-dimensional space chosen by the classifier. A biased or miscalibrated $f$ does no harm, because its bias is measured on the source and enters $C$ and $\mu_{\hat y}$ in the same way. In the binary case this is the old adjusted count, $\hat q(y=1)=(\hat q(\hat y=1)-\mathrm{FPR})/(\mathrm{TPR}-\mathrm{FPR})$; the conditional confusion matrix has determinant $\mathrm{TPR}-\mathrm{FPR}$, so an estimate built on a weakly discriminating score is unstable however well that score is calibrated. For a fraud or credit model, this is the base-rate estimate read off the scores of an unlabeled recent month.

Consistency is eventual invertibility plus the strong law. Let $\delta=\sigma_{\min}(C)$. $\hat C$ is invertible once $\|\hat C-C\|_2<\delta/2$, which Hoeffding and a union bound make fail with probability exponentially small in $n$, so by Borel-Cantelli $\hat C$ is singular only finitely often. The strong law for $\hat C$, $\hat\mu_{\hat y}$ and $\hat\nu_y$, with continuity of matrix inversion at an invertible matrix, gives the almost-sure limits.

The error bound is a perturbation bound for a linear solve. Write $\hat C=C+E_1$ and $\hat\mu_{\hat y}=\mu_{\hat y}+E_2$. Since $\mu_{\hat y}=Cw$, $$\hat w-w=(C+E_1)^{-1}(E_2-E_1w),\qquad \|\hat w-w\|_2\le\frac2{\sigma_{\min}}\big(\|E_1\|_2\|w\|_2+\|E_2\|_2\big),$$ once $\|E_1\|_2\le\sigma_{\min}/2$ (Weyl). $\hat C-C$ is an average of independent centered rank-one matrices of bounded norm, so matrix Bernstein gives $\|E_1\|_2\lesssim\sqrt{\log n/n}$, which is where the sample-size condition comes from; Hoeffding on the $k$ coordinates gives $\|E_2\|_2\lesssim\sqrt{k\log m/m}$. Read the bound term by term: the rates are parametric in the label dimension; $\|w\|_2^2$ grows with the size of the shift and is large when a class rare in the source becomes common; and $1/\sigma_{\min}^2$ measures the classifier, with $\sigma_{\min}=\min_yp(y)$ for a perfect classifier and $0$ for one that cannot tell two classes apart. For $\hat\mu_y$, the term $\mathrm{diag}(\hat\nu_y-\nu_y)w$ costs $\|w\|^2\log n/n$ even if $w$ were known.

Testing for label shift reduces to a two-sample test on predictions. From Step 1, $q(\hat y)-p(\hat y)=C_{\hat y|y}\,(q(y)-p(y))$ with $C_{\hat y|y}=C\,\mathrm{diag}(\nu_y)^{-1}$ invertible, so the prediction distributions agree exactly when the label distributions do. To test $H_0:q(y)=p(y)$, compare $f$ on held-out source data with $f$ on target data by any two-sample test (Kolmogorov-Smirnov in the experiments). Validity needs nothing beyond A1, since under $H_0$ $P=Q$ and the two samples come from one law; power comes from $f$, and the low-dimensional test avoids a kernel test in dimension $d$. Since $P=Q$ implies $p(\hat y)=q(\hat y)$ for any $f$, a rejection also flags covariate or concept shift and can be read as label shift only under A1, and some shifts leave $p(\hat y)$ unchanged.

Correction is importance-weighted ERM with the estimated weights. Under label shift $q(x,y)/p(x,y)=w(y)$, so minimizing $\sum_iw(y_i)\,\ell(y_i,x_i)$ over source data targets the risk under $Q$. The algorithm trains $f$ on one half of the source data and estimates $\hat C$ on the other, falls back to $\hat w=1$ when $\sigma_{\min}(\hat C)\le\delta$, and otherwise retrains with weights $\max(\hat w,0)$; negative weights, possible for classes rare in the target, are clipped because they would make the objective unbounded below. There is no guarantee for the corrected classifier beyond consistency of its weights, and the paper suggests correcting only when the test of Step 4 rejects, since reweighting when nothing has shifted only adds variance.

In experiments the test on predictions has high power, and much of the accuracy gain comes from the prior. On resampled MNIST and CIFAR-10 with a two-layer MLP as $f$, the Kolmogorov-Smirnov test on $f$'s outputs has uniform p-values under no shift, power far above a kernel B-test on raw images and close to an infeasible oracle test on the labels, and more power for a better-trained $f$, matching its larger $\sigma_{\min}$. Kernel mean matching has lower weight error at the smallest $n$, but BBSE's error falls faster and is lower by about $n=8{,}000$; hard and soft BBSE are close. Reweighting raises MNIST accuracy under the largest Dirichlet shift, and the gain fades as the shift shrinks. On CIFAR-10 the unweighted MLP sits near 43% under every shift while BBSE climbs toward 100% as the target concentrates on one class, and that gain comes mostly from the prior: under tweak-one shift, always predicting the tweaked class scores $\rho$, and for $\rho\ge0.6$ BBSE scores about $\rho$. Splitting the data to train $f$ makes BBSE worse than the baseline at very small $n$, a cost a classifier already in deployment avoids.