Generalized Distribution-Free Semi-Supervised Learning with Risk Rewrite

# Generalized Distribution-Free Semi-Supervised Learning with Risk Rewrite
Source: [https://arxiv.org/html/2607.11947](https://arxiv.org/html/2607.11947)
Hiroo IrobeDepartment of Mathematical and Computing Science Institute of Science Tokyo Takafumi KanamoriDepartment of Mathematical and Computing Science Institute of Science Tokyo RIKEN Center for Advanced Intelligence Project

###### Abstract

Typical semi\-supervised learning \(SSL\) methods rely on distributional assumptions, and their performance degrades when these are violated\. While PNU learning, a risk rewriting method, offers a distribution\-free alternative, it is restricted to binary classification and its variance optimality remains unclear\. In this paper, we propose a generalized framework that constructs unbiased risk estimators using linear combinations of component risks, subsuming PNU learning and extending to multiclass classification\. We derive the minimum achievable variance, demonstrating our estimator can attain lower variance than PNU in asymmetric loss scenarios\. Furthermore, we establish a generalization bound directly linking this variance reduction to improved learning performance\. Based on these theoretical insights, we introduce two practical SSL methods that empirically match or outperform existing approaches on binary and multiclass benchmarks\.

## 1Introduction

Although machine learning models typically require substantial labeled data to achieve good performance, acquiring such labels in real\-world scenarios is often difficult and expensive\. In contrast, unlabeled data is cheaper to acquire\. Consequently, semi\-supervised learning \(SSL\) has been extensively studied to leverage this unlabeled data when labeled data is scarce\. Existing methods generally rely on specific distributional assumptions about the data or heuristics\[chapelle06semi,ouali20overview,mass25self\]\. Typical distributional assumptions include themanifold assumption, which posits that high\-dimensional data lie on a lower\-dimensional manifold, and thecluster assumption, which assumes that the decision boundary should pass through low\-density regions to separate data clusters\[ouali20overview\]\. To encode these distributional assumptions into training a classifier, two main research directions have been studied\.

The first is consistency regularization, which regularizes a classifier so that the prediction does not change significantly against the perturbation of unlabeled data\. This improves the smoothness of the classifier along the data manifold\. Early works were developed with graph\-based regularization\[zhou03l,belkin06mani\]\. Recent methods based on deep models employ regularizers to enhance model robustness against input perturbations, data augmentation and dropout\[miyato19vat,laine17temp,tar17mean,xie20uda\]\.

The second is Self\-Training, which jointly trains a classifier and assigns labels \(pseudo labels\) to unlabeled data using current predictions\. It pushes the decision boundary into low\-density regions by discouraging low\-confidence predictions\[ouali20overview\]\. The pseudo\-labeling process has traditionally been managed by fixed confidence thresholds\[yaro95uns\], and recent works have adjusted them with training progress\[zhang21flex,wang23free\]\. These methods are refined by multiple classifiers\[blum98co,zhi05tri,pham21meta\]to derive more accurate pseudo labels\. Please refer tomass25self,ouali20overviewfor other SSL methods, which are generally based on the distributional assumptions mentioned above\.

While these approaches have achieved remarkable success, their performance is often contingent on whether the underlying distributional assumptions hold for the target dataset\. If these assumptions are violated, the inductive bias introduced by the unlabeled data can behave adversely, potentially degrading performance below that of supervised learning\[coz03semi,li11tow,krij17rob,wang22deb,arazo20pseudo\]\.

Unbiased Risk Estimators and Risk Rewriting\.A distinct line of research focuses on utilizing unlabeled data for risk evaluation without relying on restrictive distributional assumptions\. This is achieved throughrisk rewriting\[sugiyama22ws\], which reformulates the standard expected risk into an unbiased estimator computable directly from the available data distributions \(e\.g\., combinations of labeled and unlabeled data\)\. For instance, Positive\-Unlabeled \(PU\) learning trains a classifier using only positive and unlabeled data by constructing such a rewritten risk estimator\[du14analysis\]\.sakai17semiextended this to the semi\-supervised setting by proposing PNU learning, which combines PN \(supervised\), PU, and NU \(Negative\-Unlabeled\) risks\. They theoretically demonstrated that PNU learning can reduce the variance of risk estimators compared to standard supervised learning\. This approach is compelling as it is theoretically supported and applicable to any model without requiring strong distributional assumptions \(such as the cluster or manifold assumptions\)\.

Limitations and Open Problems\.Despite its theoretical advantages, the PNU learning framework proposed bysakai17semileaves several open problems\. First, their method is limited to binary classification\. Second, it is unclear whether PNU is variance\-optimal among broader classes of unbiased risk\-rewriting estimators\. In this paper, we address these limitations by generalizing the method to a linear combination set of risksSl​i​nS\_\{lin\}and proposing new SSL methods to minimize the variance of the risk estimator\.

Our contributions are summarized as follows:

- •We propose a generalized framework for risk\-rewriting SSL that subsumes PNU risk and extends naturally to the multiclass setting\. As discussed in Section[7](https://arxiv.org/html/2607.11947#S7), our framework has a potential impact on a broad range of SSL and weakly supervised learning problems\.
- •We derive the theoretical minimum variance achievable by the setSl​i​nS\_\{lin\}and show it can have a smaller minimum variance than PNU risk in the general \(asymmetric\) loss case\. In the symmetric loss case, we show PNU risk can achieve optimal minimum variance inSl​i​nS\_\{lin\}\.
- •We propose two novel SSL methods: \(1\) an iterative optimization method and \(2\) a data\-free method under an equal covariance assumption, and empirically demonstrate that they consistently outperform or match existing SSL methods\.

## 2Problem setting

We consider a multiclass classification problem where the input space is𝒳⊂ℝd\\mathcal\{X\}\\subset\\mathbb\{R\}^\{d\}and the output label space is𝒴=\{1,…,k\}\\mathcal\{Y\}=\\\{1,\\dots,k\\\}\. We assume the data is generated from a joint distributionp​\(x,y\)p\(x,y\)over𝒳×𝒴\\mathcal\{X\}\\times\\mathcal\{Y\}\. Letpi​\(x\)=p​\(x∣y=i\)p\_\{i\}\(x\)=p\(x\\mid y=i\)denote the class\-conditional density for classii, and letθi=P​\(y=i\)\\theta\_\{i\}=P\(y=i\)be the class prior probability, such that∑i=1kθi=1\\sum\_\{i=1\}^\{k\}\\theta\_\{i\}=1\. The distribution of unlabeled data is given by the mixture model:p​\(x\)=∑i=1kθi​pi​\(x\)p\(x\)=\\sum\_\{i=1\}^\{k\}\\theta\_\{i\}p\_\{i\}\(x\)\. In the semi\-supervised setting, we are provided with labeled datasets𝒳i=\{xji\}j=1ni∼i\.i\.d\.pi​\(x\)\\mathcal\{X\}\_\{i\}=\\\{x\_\{j\}^\{i\}\\\}\_\{j=1\}^\{n\_\{i\}\}\\stackrel\{\{\\scriptstyle i\.i\.d\.\}\}\{\{\\sim\}\}p\_\{i\}\(x\)for each classi∈𝒴i\\in\\mathcal\{Y\}, and an unlabeled dataset𝒳U=\{xjU\}j=1nU∼i\.i\.d\.p​\(x\)\\mathcal\{X\}\_\{U\}=\\\{x\_\{j\}^\{U\}\\\}\_\{j=1\}^\{n\_\{U\}\}\\stackrel\{\{\\scriptstyle i\.i\.d\.\}\}\{\{\\sim\}\}p\(x\)\.

Risk Definitions\.Letg:𝒳→ℝkg:\\mathcal\{X\}\\to\\mathbb\{R\}^\{k\}be a decision function \(e\.g\., a neural network\) andl:ℝk×𝒴→ℝl:\\mathbb\{R\}^\{k\}\\times\\mathcal\{Y\}\\to\\mathbb\{R\}be a loss function\. Assume thatggbelongs to a function class𝒢\\mathcal\{G\}\. The goal of standard supervised learning is to minimize the true riskR​\(g\):=𝔼\(x,y\)∼p​\(x,y\)​\[l​\(g​\(x\),y\)\]R\(g\):=\\mathbb\{E\}\_\{\(x,y\)\\sim p\(x,y\)\}\[l\(g\(x\),y\)\]\.

To investigate unbiased risk estimators, we decompose the risk into components based on the data distribution and the label used for loss evaluation\. We define component risksRi​j​\(g\)R\_\{ij\}\(g\)as:

Ri​j​\(g\):=𝔼x∼pi​\[l​\(g​\(x\),j\)\],R\_\{ij\}\(g\):=\\mathbb\{E\}\_\{x\\sim p\_\{i\}\}\[l\(g\(x\),j\)\],\(1\)which is the expected loss of predictorggcalculated over the distribution of classiibut evaluated with respect to a fixed labeljj\. Similarly, we define the risk over the unlabeled distribution with respect to labeljjas:

RU​j​\(g\):=𝔼x∼p​\(x\)​\[l​\(g​\(x\),j\)\]\.R\_\{Uj\}\(g\):=\\mathbb\{E\}\_\{x\\sim p\(x\)\}\[l\(g\(x\),j\)\]\.\(2\)Using these components, the standard supervised risk can be expressed asR​\(g\)=∑i=1kθi​Ri​i​\(g\)R\(g\)=\\sum\_\{i=1\}^\{k\}\\theta\_\{i\}R\_\{ii\}\(g\)\.

### 2\.1Revisiting Binary Risk Rewriting: PU, NU, and PNU Risks

Although the standard supervised risk is written asR​\(g\)=∑i=1kθi​Ri​i​\(g\)R\(g\)=\\sum\_\{i=1\}^\{k\}\\theta\_\{i\}R\_\{ii\}\(g\), it is not the only expression\. In binary classification, several different formulations have been proposed forR​\(g\)R\(g\)with unlabeled data\. Consider the case wherek=2k=2, withy=1y=1andy=2y=2representing the positive and negative classes, respectively\. Then the standard supervised risk \(PN risk\) isRP​N​\(g\):=θ1​R11​\(g\)\+θ2​R22​\(g\)R\_\{PN\}\(g\):=\\theta\_\{1\}R\_\{11\}\(g\)\+\\theta\_\{2\}R\_\{22\}\(g\)\.

PU Risk\.Positive\-Unlabeled \(PU\) learning\[du14analysis\]addresses scenarios where negative labels are unavailable\. By exploiting the density equalityθ2​p2​\(x\)=p​\(x\)−θ1​p1​\(x\)\\theta\_\{2\}p\_\{2\}\(x\)=p\(x\)\-\\theta\_\{1\}p\_\{1\}\(x\), one can rewrite the risk on the negative class asθ2​R22​\(g\)=RU​2​\(g\)−θ1​R12​\(g\)\\theta\_\{2\}R\_\{22\}\(g\)=R\_\{U2\}\(g\)\-\\theta\_\{1\}R\_\{12\}\(g\)\. This yields the PU risk:

RP​U​\(g\):=θ1​R11​\(g\)−θ1​R12​\(g\)\+RU​2​\(g\)\.R\_\{PU\}\(g\):=\\theta\_\{1\}R\_\{11\}\(g\)\-\\theta\_\{1\}R\_\{12\}\(g\)\+R\_\{U2\}\(g\)\.\(3\)
This risk is equivalent to the PN risk, but formulated without requiring the negative distribution\.

NU Risk\.By applying a symmetric transformation \(substituting the positive component viaθ1​p1​\(x\)=p​\(x\)−θ2​p2​\(x\)\\theta\_\{1\}p\_\{1\}\(x\)=p\(x\)\-\\theta\_\{2\}p\_\{2\}\(x\)\), we obtain the Negative\-Unlabeled \(NU\) risk:

RN​U​\(g\):=θ2​R22​\(g\)−θ2​R21​\(g\)\+RU​1​\(g\)\.R\_\{NU\}\(g\):=\\theta\_\{2\}R\_\{22\}\(g\)\-\\theta\_\{2\}R\_\{21\}\(g\)\+R\_\{U1\}\(g\)\.\(4\)
PNU Risk\.Under certain conditions and asnU→∞n\_\{U\}\\rightarrow\\infty, PU and NU learning outperform PN learning\[niu16\]\. To exploit this advantage further,sakai17semiproposed PNU learning111They also proposed PUNU risk, but we omit it since it was shown to be inferior to PNU risk\., which considers the following risk that linearly combines PU, NU, and PN risks with a parameterη∈\[−1,1\]\\eta\\in\[\-1,1\]:

RPNUη​\(g\):=\{RPNPUη​\(g\)\(η≥0\)RPNNU\|η\|​\(g\)\(η<0\)R\_\{\\text\{PNU\}\}^\{\\eta\}\(g\):=\\begin\{cases\}R\_\{\\text\{PNPU\}\}^\{\\eta\}\(g\)&\(\\eta\\geq 0\)\\\\ R\_\{\\text\{PNNU\}\}^\{\|\\eta\|\}\(g\)&\(\\eta<0\)\\end\{cases\}where

RPNPUη​\(g\):=\(1−η\)​RPN​\(g\)\+η​RPU​\(g\),\\displaystyle R\_\{\\mathrm\{PNPU\}\}^\{\\eta\}\(g\):=\(1\-\\eta\)R\_\{\\mathrm\{PN\}\}\(g\)\+\\eta R\_\{\\mathrm\{PU\}\}\(g\),RPNNUη​\(g\):=\(1−η\)​RPN​\(g\)\+η​RNU​\(g\)\.\\displaystyle R\_\{\\mathrm\{PNNU\}\}^\{\\eta\}\(g\):=\(1\-\\eta\)R\_\{\\mathrm\{PN\}\}\(g\)\+\\eta R\_\{\\mathrm\{NU\}\}\(g\)\.
The estimation of PNU risk with empirical distributions has a smaller variance than that of PN risk, which leads to more efficient SSL\. This method has several advantages: \(i\) no requirement of distributional assumptions unlike other SSL methods, \(ii\) compatibility with any loss and classification model, and \(iii\) minimal additional computational costs\. Unlike augmentation\-heavy or teacher\-student SSL methods\[zhang21flex,pham21meta\], our methods do not require augmentation passes or extra networks\.

Despite these advantages, PNU learning is limited to binary classification\. How to extend it to multiclass classification is not obvious\. In addition, it is not clear if we can construct a risk with a smaller estimation variance than that of the PNU risk\.

## 3Our proposed framework: Generalized Risk Rewrite

In this section, we propose a generalized framework for semi\-supervised learning based on risk rewriting\. We introduce a broad class of unbiased risk estimators formed by linear combinations of component risks and analyze their variance properties\.

### 3\.1Generalized Unbiased Estimators via Linear Combinations

We define the set of linear combinations of risk functionals,Sl​i​nS\_\{lin\}, as

Sl​i​n\\displaystyle S\_\{lin\}:=\{Rl​i​n\{ai​j\},\{bj\}\(⋅\):=∑i,j=1kai​jRi​j\(⋅\)\+∑j=1kbjRU​j\(⋅\)\\displaystyle:=\\Biggl\\\{R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(\\cdot\):=\\sum\_\{i,j=1\}^\{k\}a\_\{ij\}R\_\{ij\}\(\\cdot\)\+\\sum\_\{j=1\}^\{k\}b\_\{j\}R\_\{Uj\}\(\\cdot\)\|ai​j,bj∈ℝ,∀g∈𝒢,Rl​i​n\{ai​j\},\{bj\}\(g\)=R\(g\)\}\.\\displaystyle\\Biggm\|a\_\{ij\},b\_\{j\}\\in\\mathbb\{R\},\\quad\\forall g\\in\\mathcal\{G\},\\ R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(g\)=R\(g\)\\Biggr\\\}\.\(5\)The set is defined as linear combinations of component risks and unlabeled risks, which are equal toR​\(g\)R\(g\)for allg∈𝒢g\\in\\mathcal\{G\}\. It is important to note that this formulation generalizes existing risks such as PU, NU, and PNU risks\. We can build unbiased estimators for eachRl​i​n\{ai​j\},\{bj\}​\(⋅\)∈Sl​i​nR\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(\\cdot\)\\in S\_\{lin\}by using empirical distributions\. By optimizing the parametersai​ja\_\{ij\}andbjb\_\{j\}over the full setSl​i​nS\_\{lin\}, we can derive a risk that has a lower estimation variance than the existing methods\.

### 3\.2Characterization under Linear Independence

The number of parameters that define the risks inSl​i​nS\_\{lin\}can be reduced under the following mild assumption\.

###### Assumption 1\(Linear Independence\)\.

The risk components are linearly independent in the sense that:

∑i,j=1kci​j​Ri​j​\(g\)=0\(∀g∈𝒢\)⟹∀i,j,ci​j=0\.\\sum\_\{i,j=1\}^\{k\}c\_\{ij\}R\_\{ij\}\(g\)=0\\quad\(\\forall g\\in\\mathcal\{G\}\)\\implies\\forall i,j,\\ c\_\{ij\}=0\.\(6\)

This assumption is satisfied when𝒢\\mathcal\{G\}is reasonably large and the loss function is not constrained by linear relations\. In particular, it cannot be met by symmetric loss functions \(such as the 0\-1 loss\), because∑j=1kl​\(g​\(x\),j\)\\sum\_\{j=1\}^\{k\}l\(g\(x\),j\)is constant and the risk components are linearly dependent\. The symmetric\-loss case is discussed in Section[4](https://arxiv.org/html/2607.11947#S4)\.

Under Assumption[1](https://arxiv.org/html/2607.11947#Thmasmp1), we can characterize the parameters that satisfy the constraint∀g∈𝒢,Rl​i​n\{ai​j\},\{bj\}​\(g\)=R​\(g\)\\forall g\\in\\mathcal\{G\},R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(g\)=R\(g\)\.

###### Theorem 1\(Parametrization ofSl​i​nS\_\{lin\}\)\.

Under Assumption[1](https://arxiv.org/html/2607.11947#Thmasmp1),Sl​i​nS\_\{lin\}can be rewritten as

Sl​i​n=\\displaystyle S\_\{lin\}=\{Rl​i​n𝒂\(⋅\):=∑i=1kθiRi​i\(⋅\)\+∑i,j=1kθi\(ajθj−1\)Ri​j\(⋅\)\\displaystyle\\Biggl\\\{R^\{\\boldsymbol\{a\}\}\_\{lin\}\(\\cdot\):=\\sum^\{k\}\_\{i=1\}\\theta\_\{i\}R\_\{ii\}\(\\cdot\)\+\\sum^\{k\}\_\{i,j=1\}\\theta\_\{i\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)R\_\{ij\}\(\\cdot\)−∑j=1k\(ajθj−1\)RU​j\(⋅\)\|𝒂∈ℝk\}\.\\displaystyle\\quad\-\\sum^\{k\}\_\{j=1\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)R\_\{Uj\}\(\\cdot\)\\Biggm\|\\boldsymbol\{a\}\\in\\mathbb\{R\}^\{k\}\\Biggr\\\}\.\(7\)

This theorem implies that each risk inSl​i​nS\_\{lin\}is parametrized by akk\-dimensional vector\.

### 3\.3Minimum variance calculation

In the following, we use a fixedggand often omit the argument of the risk term, denotingRi​j​\(g\)R\_\{ij\}\(g\)asRi​jR\_\{ij\}when the context is clear\. LetR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}andR^i​j\\hat\{R\}\_\{ij\}denote the empirical estimators that are defined by replacing true distributions with empirical distributions\. We consider the asymptotic regime where the number of unlabeled samplesnU→∞n\_\{U\}\\to\\infty\.

LetCm∈ℝk×kC\_\{m\}\\in\\mathbb\{R\}^\{k\\times k\}be the covariance matrix for classmm, defined as\(Cm\)i​j:=Covx∼pm⁡\[l​\(g​\(x\),i\),l​\(g​\(x\),j\)\]\(C\_\{m\}\)\_\{ij\}:=\\operatorname\{Cov\}\_\{x\\sim p\_\{m\}\}\[l\(g\(x\),i\),l\(g\(x\),j\)\]\. The covariance of the empirical risk estimates is given byCov⁡\[R^m​i,R^m​j\]=1nm​\(Cm\)i​j\\operatorname\{Cov\}\[\\hat\{R\}\_\{mi\},\\hat\{R\}\_\{mj\}\]=\\frac\{1\}\{n\_\{m\}\}\(C\_\{m\}\)\_\{ij\}\. We define the diagonal matrixQ=diag⁡\(θ1−1,…,θk−1\)Q=\\operatorname\{diag\}\(\\theta\_\{1\}^\{\-1\},\\dots,\\theta\_\{k\}^\{\-1\}\)and the shift vectors𝐝m=𝟏−𝐞m\\mathbf\{d\}\_\{m\}=\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}, where𝟏\\mathbf\{1\}is the all\-ones vector and𝐞m\\mathbf\{e\}\_\{m\}is the standard basis vector\. We now derive the variance of the estimatorR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\.

###### Theorem 2\(Variance ofR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\)\.

Var⁡\[R^l​i​n𝒂\]\\displaystyle\\operatorname\{Var\}\\left\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\\right\]=∑m=1kθm2nm​\(Q​𝒂−𝐝m\)T​Cm​\(Q​𝒂−𝐝m\)\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\left\(Q\\boldsymbol\{a\}\-\\mathbf\{d\}\_\{m\}\\right\)^\{T\}C\_\{m\}\\left\(Q\\boldsymbol\{a\}\-\\mathbf\{d\}\_\{m\}\\right\)=𝒂T​A​𝒂−2​𝐛T​𝒂\+c,\\displaystyle=\\boldsymbol\{a\}^\{T\}A\\boldsymbol\{a\}\-2\\mathbf\{b\}^\{T\}\\boldsymbol\{a\}\+c,\(8\)where we define the system matrices as

A\\displaystyle A=∑m=1kθm2nm​Q​Cm​Q,𝐛=∑m=1kθm2nm​Q​Cm​𝐝m,\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}QC\_\{m\}Q,\\quad\\mathbf\{b\}=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}QC\_\{m\}\\mathbf\{d\}\_\{m\},c\\displaystyle c=∑m=1kθm2nm​𝐝mT​Cm​𝐝m\.\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\mathbf\{d\}\_\{m\}^\{T\}C\_\{m\}\\mathbf\{d\}\_\{m\}\.

SinceAAis a sum of positive semi\-definite matrices, the variance is a convex function of𝒂\\boldsymbol\{a\}\. Definef​\(𝒂\):=Var⁡\[R^l​i​n𝒂\]f\(\\boldsymbol\{a\}\):=\\operatorname\{Var\}\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\]\. The optimal parameter vector𝒂∗\\boldsymbol\{a\}^\{\*\}that minimizes the variance satisfies the first\-order condition:

∇𝒂f​\(𝒂\)=2​A​𝒂−2​𝐛=0⟹A​𝒂∗=𝐛\.\\nabla\_\{\\boldsymbol\{a\}\}f\(\\boldsymbol\{a\}\)=2A\\boldsymbol\{a\}\-2\\mathbf\{b\}=0\\implies A\\boldsymbol\{a\}^\{\*\}=\\mathbf\{b\}\.\(9\)IfAAis invertible, the minimum variance is given byf​\(𝒂∗\)=c−𝐛T​A−1​𝐛f\(\\boldsymbol\{a\}^\{\*\}\)=c\-\\mathbf\{b\}^\{T\}A^\{\-1\}\\mathbf\{b\}\. For simplicity, we define the total weighted covariance matrixSSand the weighted covariance vector𝐮\\mathbf\{u\}:

S:=∑m=1kθm2nm​Cm,𝐮:=∑m=1kθm2nm​Cm​𝐞m\.S:=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\},\\quad\\mathbf\{u\}:=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\mathbf\{e\}\_\{m\}\.Then, we derive the following theorem:

###### Theorem 3\(Minimum Variance ofR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\)\.

AssumenU→∞n\_\{U\}\\rightarrow\\inftyand thatSSis invertible\. The minimum variance achievable by the linear risk estimatorR^l​i​n𝐚\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}is given by

min𝒂⁡Var⁡\[R^l​i​n𝒂\]=∑m=1kθm2nm​\(Cm\)m​m−𝐮T​S−1​𝐮\.\\min\_\{\\boldsymbol\{a\}\}\\operatorname\{Var\}\\left\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\\right\]=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(C\_\{m\}\)\_\{mm\}\-\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}\.\(10\)

The first term represents the pointwise variance of the supervised estimator for the same fixedgg, and the second term𝐮T​S−1​𝐮\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}\(which is non\-negative asSSis positive semi\-definite\) represents the variance reduction from the proposed semi\-supervised method\.

### 3\.4Magnitude of variance reduction

The variance reduction𝐮T​S−1​𝐮\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}depends on the sample sizes, class priors and covariance matrices\. To analyze when the reduction is large, we assume∀m∈\[k\],Cm=C\\forall m\\in\[k\],C\_\{m\}=Cwhere\(C\)i​i=ρ1\>0\(C\)\_\{ii\}=\\rho\_\{1\}\>0and\(C\)i​j=ρ2<0\(C\)\_\{ij\}=\\rho\_\{2\}<0fori≠ji\\neq j, since\(Cm\)i​j\(C\_\{m\}\)\_\{ij\}fori≠ji\\neq jtends to be negative for usual loss functions\.

###### Theorem 4\(Variance reduction\)\.

AssumeCCis invertible and∀m∈\[k\],Cm=C\\forall m\\in\[k\],C\_\{m\}=C\. Then,

𝐮T​S−1​𝐮\\displaystyle\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}=\(ρ1−ρ2\)​∑m=1kwm2W\+ρ2​W\\displaystyle=\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\frac\{\\sum\_\{m=1\}^\{k\}w\_\{m\}^\{2\}\}\{W\}\+\\rho\_\{2\}W≤ρ1​maxm∈\[k\]⁡wm\+ρ2​\(W−maxm∈\[k\]⁡wm\),\\displaystyle\\leq\\rho\_\{1\}\\max\_\{m\\in\[k\]\}w\_\{m\}\+\\rho\_\{2\}\\left\(W\-\\max\_\{m\\in\[k\]\}w\_\{m\}\\right\),wherewm:=θm2nmw\_\{m\}:=\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}andW:=∑m=1kwmW:=\\sum\_\{m=1\}^\{k\}w\_\{m\}\.

Considering the upper bound of𝐮T​S−1​𝐮\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}, the variance reduction is large whenmaxm∈\[k\]⁡wm\\max\_\{m\\in\[k\]\}w\_\{m\}is large andW−maxm∈\[k\]⁡wmW\-\\max\_\{m\\in\[k\]\}w\_\{m\}is small, which meansθi\\theta\_\{i\}andnin\_\{i\}should be disproportionate, i\.e\., there exists class imbalance in labeled samples\.

### 3\.5Comparison of Optimal Variances with PNU Learning

We compare the minimum variance achievable by our proposed method with that of PNU learning in binary classification\. This analysis is different from the section[3\.4](https://arxiv.org/html/2607.11947#S3.SS4), which studies the absolute variance reduction relative to supervised learning\. Here, we instead quantify the relative advantage of the proposed estimator over PNU learning\. For simplicity, we compare our proposed estimator against the PNPU and PNNU estimators\.

###### Theorem 5\(Variance comparison\)\.

Assumek=2k=2andnU→∞n\_\{U\}\\rightarrow\\infty\. LetηP​U∗:=argminη∈ℝ⁡Var⁡\(R^PNPUη\)\\eta^\{\*\}\_\{PU\}:=\\operatorname\{argmin\}\_\{\\eta\\in\\mathbb\{R\}\}\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta\}\)andηN​U∗:=argminη∈ℝ⁡Var⁡\(R^PNNUη\)\\eta^\{\*\}\_\{NU\}:=\\operatorname\{argmin\}\_\{\\eta\\in\\mathbb\{R\}\}\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNNU\}\}^\{\\eta\}\)be the optimal parameters for the PNPU and PNNU estimators respectively\. Then,

Var⁡\(R^l​i​n𝒂∗\)≤min⁡\(Var⁡\(R^PNPUηP​U∗\),Var⁡\(R^PNNUηN​U∗\)\)\.\\operatorname\{Var\}\(\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}\)\\leq\\min\\left\(\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta^\{\*\}\_\{PU\}\}\),\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNNU\}\}^\{\\eta^\{\*\}\_\{NU\}\}\)\\right\)\.\(11\)Furthermore, under the same assumption as Theorem[4](https://arxiv.org/html/2607.11947#Thmthm4),

min\\displaystyle\\min\(Var⁡\(R^PNPUηP​U∗\),Var⁡\(R^PNNUηN​U∗\)\)−Var⁡\(R^l​i​n𝒂∗\)\\displaystyle\\left\(\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta^\{\*\}\_\{PU\}\}\),\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNNU\}\}^\{\\eta^\{\*\}\_\{NU\}\}\)\\right\)\-\\operatorname\{Var\}\(\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}\)=min⁡\(w12​\(ρ12−ρ22\)\(w1\+w2\)​ρ1,w22​\(ρ12−ρ22\)\(w1\+w2\)​ρ1\)\\displaystyle=\\min\\left\(\\frac\{w\_\{1\}^\{2\}\(\\rho\_\{1\}^\{2\}\-\\rho\_\{2\}^\{2\}\)\}\{\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\},\\frac\{w\_\{2\}^\{2\}\(\\rho\_\{1\}^\{2\}\-\\rho\_\{2\}^\{2\}\)\}\{\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\}\\right\)\(12\)

Eq\. \([11](https://arxiv.org/html/2607.11947#S3.E11)\) implies our proposed estimator has a minimum variance less than or equal to that of PNPU and PNNU estimators, which is rather trivial since the set ofR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}subsumes the sets ofR^PNPUη\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta\}andR^PNNUη\\hat\{R\}\_\{\\text\{PNNU\}\}^\{\\eta\}\. Eq\. \([12](https://arxiv.org/html/2607.11947#S3.E12)\) implies the gap in minimum variances becomes small whenw1≫w2w\_\{1\}\\gg w\_\{2\}orw1≪w2w\_\{1\}\\ll w\_\{2\}, which means our method is more advantageous whenθi\\theta\_\{i\}andnin\_\{i\}are proportional, i\.e\., the labeled data is balanced\.

## 4Symmetric Loss Case

The preceding sections analyzed the properties ofSl​i​nS\_\{lin\}under Assumption[1](https://arxiv.org/html/2607.11947#Thmasmp1)\. For symmetric loss functions such as the 0\-1 loss, Assumption[1](https://arxiv.org/html/2607.11947#Thmasmp1)does not hold, and we need a modified analysis, as described in this section\.

### 4\.1Problem Setup under Symmetric Loss

We assume the loss functionl​\(⋅,⋅\)l\(\\cdot,\\cdot\)satisfies the symmetric condition:

###### Definition 1\(Symmetric Loss\)\.

A loss functionl​\(⋅,⋅\)l\(\\cdot,\\cdot\)is said to besymmetricif, for any inputxxand any prediction vectorg​\(x\)g\(x\), the sum of losses over all possible class labelsj∈\{1,…,k\}j\\in\\\{1,\\dots,k\\\}is constant:

∑j=1kl​\(g​\(x\),j\)=α,∀x∈𝒳,∀g,\\sum\_\{j=1\}^\{k\}l\(g\(x\),j\)=\\alpha,\\quad\\forall x\\in\\mathcal\{X\},\\forall g,\(13\)whereα\\alphais a constant\.

Common examples include the 0\-1 loss and ramp loss\[char19ons\]\. This constraint implies a deterministic linear dependency among the risk components:∑j=1kRi​j​\(g\)=α\\sum\_\{j=1\}^\{k\}R\_\{ij\}\(g\)=\\alpha\. Consequently, the linear independence assumption \(Assumption[1](https://arxiv.org/html/2607.11947#Thmasmp1)\) does not hold, and we need a different reparametrization forSl​i​nS\_\{lin\}\.

### 4\.2Reparametrization ofSl​i​nS\_\{lin\}with symmetric loss

To analyze the class of risks, we introduce a modified assumption similar to linear independence\.

###### Assumption 2\.

∑ik∑jk−1\\displaystyle\\sum\_\{i\}^\{k\}\\sum\_\{j\}^\{k\-1\}ci​j​Ri​j​\(g\)\+c=0​\(∀g∈𝒢\)\\displaystyle c\_\{ij\}R\_\{ij\}\(g\)\+c=0\(\\forall g\\in\\mathcal\{G\}\)⇒∀i∈\[k\],j∈\[k−1\],ci​j=0​and​c=0\.\\displaystyle\\Rightarrow\\forall i\\in\[k\],j\\in\[k\-1\],\\ c\_\{ij\}=0\\text\{ and \}c=0\.

Under this assumption, we can characterizeSl​i​nS\_\{lin\}similarly to Theorem[1](https://arxiv.org/html/2607.11947#Thmthm1)\.

###### Theorem 6\.

Under Assumption[2](https://arxiv.org/html/2607.11947#Thmasmp2),Sl​i​nS\_\{lin\}with a symmetric loss can be rewritten as

Sl​i​n=\\displaystyle S\_\{lin\}=\{Rl​i​n𝒂\(⋅\):=∑i=1kθiRi​i\(⋅\)\+∑i=1k∑j=1k−1θi\(ajθj−1\)Ri​j\(⋅\)\\displaystyle\\Biggl\\\{R^\{\\boldsymbol\{a\}\}\_\{lin\}\(\\cdot\):=\\sum^\{k\}\_\{i=1\}\\theta\_\{i\}R\_\{ii\}\(\\cdot\)\+\\sum^\{k\}\_\{i=1\}\\sum^\{k\-1\}\_\{j=1\}\\theta\_\{i\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)R\_\{ij\}\(\\cdot\)−∑j=1k−1\(ajθj−1\)RU​j\(⋅\)\|𝒂∈ℝk−1\}\.\\displaystyle\\qquad\-\\sum^\{k\-1\}\_\{j=1\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)R\_\{Uj\}\(\\cdot\)\\Biggm\|\\boldsymbol\{a\}\\in\\mathbb\{R\}^\{k\-1\}\\Biggr\\\}\.\(14\)

Thus,Sl​i​nS\_\{lin\}with a symmetric loss is parametrized by thek−1k\-1parameters,𝒂i,i∈\[k−1\]\\boldsymbol\{a\}\_\{i\},i\\in\[k\-1\]\.

### 4\.3Variance ofR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}with Symmetric Loss

Since the symmetric loss constraint impliesRm​k=α−∑j=1k−1Rm​jR\_\{mk\}=\\alpha\-\\sum\_\{j=1\}^\{k\-1\}R\_\{mj\}, thekk\-th row and column of the covariance matrixCmC\_\{m\}are entirely determined by the covariance of the firstk−1k\-1risk terms\. Thus, the variance ofR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}is expressed with truncated matrices ofCmC\_\{m\}\. LetCˇm\\check\{C\}\_\{m\}be the top\-left\(k−1\)×\(k−1\)\(k\-1\)\\times\(k\-1\)submatrix ofCmC\_\{m\}\.

###### Theorem 7\(Variance ofR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}with symmetric loss\)\.

With a symmetric loss functionl​\(⋅,⋅\)l\(\\cdot,\\cdot\),

Var⁡\[R^l​i​n𝒂\]\\displaystyle\\operatorname\{Var\}\\left\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\\right\]=∑m=1kθm2nm​\(Qˇ​𝒂−𝐝ˇm\)T​Cˇm​\(Qˇ​𝒂−𝐝ˇm\)\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\left\(\\check\{Q\}\\boldsymbol\{a\}\-\\check\{\\mathbf\{d\}\}\_\{m\}\\right\)^\{T\}\\check\{C\}\_\{m\}\\left\(\\check\{Q\}\\boldsymbol\{a\}\-\\check\{\\mathbf\{d\}\}\_\{m\}\\right\)whereQˇ=diag⁡\(1θ1,…,1θk−1\)\\check\{Q\}=\\operatorname\{diag\}\(\\frac\{1\}\{\\theta\_\{1\}\},\\dots,\\frac\{1\}\{\\theta\_\{k\-1\}\}\)and𝐝ˇm=\{𝟏−𝐞mif​m<k2​𝟏if​m=k\.\\check\{\\mathbf\{d\}\}\_\{m\}=\\begin\{cases\}\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}&\\text\{if \}m<k\\\\ 2\\mathbf\{1\}&\\text\{if \}m=k\\end\{cases\}\.

To derive the minimum variance, we defineSˇ:=∑m=1kθm2nm​Cˇm,𝐮ˇ:=∑m=1k−1θm2nm​Cˇm​𝐞m−θk2nk​Cˇk​𝟏\\check\{S\}:=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\check\{C\}\_\{m\},\\quad\\check\{\\mathbf\{u\}\}:=\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\check\{C\}\_\{m\}\\mathbf\{e\}\_\{m\}\-\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\check\{C\}\_\{k\}\\mathbf\{1\}\. The minimum variance is derived similarly to Theorem[3](https://arxiv.org/html/2607.11947#Thmthm3)\.

###### Theorem 8\(Minimum Variance with Symmetric Loss\)\.

AssumeSˇ\\check\{S\}is invertible\. The minimum variance achievable by the linear risk estimatorR^l​i​n𝐚\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}under symmetric loss is given by

min𝒂⁡Var⁡\[R^l​i​n𝒂\]=∑m=1kθm2nm​\(Cm\)m​m−𝐮ˇT​Sˇ−1​𝐮ˇ\.\\min\_\{\\boldsymbol\{a\}\}\\operatorname\{Var\}\\left\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\\right\]=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(C\_\{m\}\)\_\{mm\}\-\\check\{\\mathbf\{u\}\}^\{T\}\\check\{S\}^\{\-1\}\\check\{\\mathbf\{u\}\}\.\(15\)

### 4\.4Comparison in Binary Classification with Symmetric Loss

We compare the proposed method, PNPU and PNNU learning in binary classification \(k=2k=2\) under the symmetric loss assumption\. We demonstrate that in this restricted setting, these methods are mathematically equivalent\.

###### Theorem 9\(Equivalence of risk estimators\)\.

Consider the binary classification setting \(k=2k=2\) with a symmetric loss function\. LetSPNPU:=\{RPNPUη∣η∈ℝ\}S\_\{\\text\{PNPU\}\}:=\\\{R\_\{\\text\{PNPU\}\}^\{\\eta\}\\mid\\eta\\in\\mathbb\{R\}\\\}andSPNNU:=\{RPNNUη∣η∈ℝ\}S\_\{\\text\{PNNU\}\}:=\\\{R\_\{\\text\{PNNU\}\}^\{\\eta\}\\mid\\eta\\in\\mathbb\{R\}\\\}denote the sets of PNPU and PNNU risks\. Then,

Sl​i​n=SPNPU=SPNNU\.S\_\{lin\}=S\_\{\\text\{PNPU\}\}=S\_\{\\text\{PNNU\}\}\.\(16\)

Therefore, they achieve the same minimum variance, which implies that, PNU is already variance\-optimal within the class of linear unbiased risk rewritings in this setting\.

## 5Relationship between semi\-supervised learning and variance reduction

The analysis in the previous sections focused on the pointwise variance of the unbiased risk estimator for a fixed classifiergg\. The goal of semi\-supervised learning is to identify the optimal predictorg^\\hat\{g\}using the empirical risk\. In this section, we establish the theoretical connection between reducing the variance of the risk estimator and improving the generalization bound of the learned classifier\.

### 5\.1Generalization bound with reduced variance

We considernU→∞n\_\{U\}\\rightarrow\\inftyto analyze the generalization performance\. Letg^=argming∈𝒢⁡R^l​i​n𝒂​\(g\)\\hat\{g\}=\\operatorname\{argmin\}\_\{g\\in\\mathcal\{G\}\}\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)be the empirical risk minimizer using our proposed estimator, and letg∗=argming∈𝒢⁡R​\(g\)g^\{\*\}=\\operatorname\{argmin\}\_\{g\\in\\mathcal\{G\}\}R\(g\)be the true risk minimizer\.

###### Theorem 10\(Generalization Bound forR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\)\.

AssumenU→∞n\_\{U\}\\rightarrow\\inftyand that the loss functionl​\(z,y\)l\(z,y\)isLL\-Lipschitz continuous with respect to the predictionz∈ℝkz\\in\\mathbb\{R\}^\{k\}, and bounded such that0≤l​\(⋅,⋅\)≤cl0\\leq l\(\\cdot,\\cdot\)\\leq c\_\{l\}\. Assumemaxi⁡\|aiθi−1\|≤c𝐚\\max\_\{i\}\\left\|\\frac\{a\_\{i\}\}\{\\theta\_\{i\}\}\-1\\right\|\\leq c\_\{\\boldsymbol\{a\}\}\. Let𝒩\(𝒢,ν,∥⋅∥∞\)\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)be theν\\nu\-covering number of𝒢\\mathcal\{G\}with respect to theL∞L\_\{\\infty\}norm\[wain19high\]\. Define the maximum variance on theν\\nu\-coverCνC\_\{\\nu\}asσmax2​\(𝐚,ν\):=maxg′∈Cν⁡Var⁡\[R^l​i​n𝐚​\(g′\)\]\\sigma^\{2\}\_\{\\max\}\(\\boldsymbol\{a\},\\nu\):=\\max\_\{g^\{\\prime\}\\in C\_\{\\nu\}\}\\operatorname\{Var\}\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\]\. Then, for anyν\>0\\nu\>0, with probability at least1−δ1\-\\delta, the excess risk ofg^\\hat\{g\}satisfies:

R​\(g^\)−R​\(g∗\)≤4​L𝒂​ν\+8​σmax2​\(𝒂,ν\)​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\+43​B𝒂​maxm∈\[k\]⁡\(θmnm\)​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\),\\begin\{aligned\} R\(\\hat\{g\}\)\-R\(g^\{\*\}\)&\\leq 4L\_\{\\boldsymbol\{a\}\}\\nu\+\\sqrt\{8\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)\}\\\\ &\\quad\+\\frac\{4\}\{3\}B\_\{\\boldsymbol\{a\}\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\),\\end\{aligned\}

whereB𝐚:=k​cl​\(1\+c𝐚\)B\_\{\\boldsymbol\{a\}\}:=kc\_\{l\}\\left\(1\+c\_\{\\boldsymbol\{a\}\}\\right\)andL𝐚:=L​\(1\+k​c𝐚\)L\_\{\\boldsymbol\{a\}\}:=L\(1\+kc\_\{\\boldsymbol\{a\}\}\)\.

Letn=minm⁡\(nm\)n=\\min\_\{m\}\(n\_\{m\}\)\. Asn→∞n\\rightarrow\\infty, the maximum varianceσmax2​\(𝒂,ν\)\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)scales as𝒪​\(1/n\)\\mathcal\{O\}\(1/n\), which implies that the second term of the generalization bound is𝒪​\(1/n\)\\mathcal\{O\}\(1/\\sqrt\{n\}\)\. Furthermore, since the third term is proportional tomaxm∈\[k\]⁡\(θmnm\)\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\), it scales as𝒪​\(1/n\)\\mathcal\{O\}\(1/n\)\. Considering only the dominant𝒪​\(1/n\)\\mathcal\{O\}\(1/\\sqrt\{n\}\)term and assumingν\\nuis small, this theorem implies that the generalization error is small when the maximum varianceσmax2​\(𝒂,ν\)\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)is small\. Thus, a good choice of𝒂\\boldsymbol\{a\}improves the SSL performance\.

### 5\.2Practical implementation of SSL

Based on the relationship established above, we propose two SSL methods to learn the classifierg^\\hat\{g\}\.

##### 1\. Iterative optimization method

Algorithm 1Iterative Optimization SSL1:

𝒳L=∪i=1k𝒳i\\mathcal\{X\}\_\{L\}=\\cup\_\{i=1\}^\{k\}\\mathcal\{X\}\_\{i\},

𝒳U\\mathcal\{X\}\_\{U\},

𝒳v​a​l\\mathcal\{X\}\_\{val\}, update interval

mm, learning rate

η\\eta, epochs

EE\.

2:Initialize classifier

g^\\hat\{g\}and risk parameter

𝒂\\boldsymbol\{a\}\.

3:for

e=1e=1to

EEdo

4:if

e\(modm\)==0e\\pmod\{m\}==0then

5:Estimate covariance

CiC\_\{i\}using outputs of

g^\\hat\{g\}on

𝒳v​a​l\\mathcal\{X\}\_\{val\}\.

6:Update

𝒂←𝒂∗\\boldsymbol\{a\}\\leftarrow\\boldsymbol\{a\}^\{\*\}minimizing variance \(Theorem[3](https://arxiv.org/html/2607.11947#Thmthm3)\) on

𝒳v​a​l\\mathcal\{X\}\_\{val\}\.

7:endif

8:Update

g^←g^−η​∇g^R^l​i​n𝒂​\(g^\)\\hat\{g\}\\leftarrow\\hat\{g\}\-\\eta\\nabla\_\{\\hat\{g\}\}\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(\\hat\{g\}\)using

𝒳L∪𝒳U\\mathcal\{X\}\_\{L\}\\cup\\mathcal\{X\}\_\{U\}\.

9:endfor

10:return

g^\\hat\{g\}

Since the optimal parameter𝒂\\boldsymbol\{a\}that minimizes the bound in Theorem[10](https://arxiv.org/html/2607.11947#Thmthm10)is unknown in practice, we propose empirical iterative optimization ofggand𝒂\\boldsymbol\{a\}\. The algorithm is described in Algorithm[1](https://arxiv.org/html/2607.11947#alg1)\. It optimizesg^\\hat\{g\}withR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}, calculating𝒂\\boldsymbol\{a\}everymmepochs to minimize the variance with the currentg^\\hat\{g\}using validation data\.

##### 2\. Data\-free method under equal covariance assumption

The first method requires a certain size of validation data to accurately estimate𝒂∗\\boldsymbol\{a\}^\{\*\}\. The estimation becomes difficult when the number of classeskkis large\. If we assume the equal covariance∀m∈\[k\],Cm=C\\forall m\\in\[k\],C\_\{m\}=C, the optimal𝒂∗\\boldsymbol\{a\}^\{\*\}is calculated as𝒂i∗=θi​\(1−wi∑m=1kwm\)\\boldsymbol\{a\}^\{\*\}\_\{i\}=\\theta\_\{i\}\\left\(1\-\\frac\{w\_\{i\}\}\{\\sum\_\{m=1\}^\{k\}w\_\{m\}\}\\right\)wherewi:=θi2/niw\_\{i\}:=\\theta\_\{i\}^\{2\}/n\_\{i\}\. We use the linear risk with this𝒂∗\\boldsymbol\{a\}^\{\*\}to learng^\\hat\{g\}\. This does not require validation data to estimate𝒂∗\\boldsymbol\{a\}^\{\*\}\.

##### Non\-negative risk correction for complex models

Note that we can express the linear risk estimator as

R^l​i​n𝒂​\(g\)=∑j=1k\(aj​R^j​j​\(g\)\+\(1−ajθj\)​Δj​\(g\)\),\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)=\\sum^\{k\}\_\{j=1\}\\left\(a\_\{j\}\\hat\{R\}\_\{jj\}\(g\)\+\\left\(1\-\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\\right\)\\Delta\_\{j\}\(g\)\\right\),whereΔj​\(g\):=R^U​j​\(g\)−∑i≠jkθi​R^i​j​\(g\)\\Delta\_\{j\}\(g\):=\\hat\{R\}\_\{Uj\}\(g\)\-\\sum\_\{i\\neq j\}^\{k\}\\theta\_\{i\}\\hat\{R\}\_\{ij\}\(g\)\. Here,Δj​\(g\)\\Delta\_\{j\}\(g\)can be viewed as a risk\-rewriting estimator forθj​Rj​j​\(g\)\\theta\_\{j\}R\_\{jj\}\(g\)\. As seen in PU and other risk\-rewriting methods\[kiryo17pu,lu20mit,tang23multi\], when𝒢\\mathcal\{G\}consists of complex models such as deep neural networks,Δj​\(g\)\\Delta\_\{j\}\(g\)can become negative even whenRj​j​\(g\)R\_\{jj\}\(g\)is non\-negative, which leads to overfitting\. To mitigate this issue, similarly to the approach bykiryo17pu, we replaceΔj​\(g\)\\Delta\_\{j\}\(g\)withinRl​i​n𝒂​\(g\)R\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)with a non\-negative counterpart,Δjn​n​\(g\):=max⁡\{0,Δj​\(g\)\}\\Delta\_\{j\}^\{nn\}\(g\):=\\max\\\{0,\\Delta\_\{j\}\(g\)\\\}, when training complex models\.

## 6Experiments

### 6\.1Variance comparison ofRP​NR\_\{PN\},RP​N​UR\_\{PNU\}andRl​i​n𝒂∗R\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}

In this subsection, we empirically validate the variance reduction achieved by the proposed linear risk estimatorR^l​i​n𝒂​\(g\)\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)\. We compare the variance of three unbiased risk estimators for a pre\-trained classifiergg: the standard supervised risk estimatorR^​\(g\)\\hat\{R\}\(g\)\(PN risk, which corresponds toR^l​i​n𝒂​\(g\)\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)where𝒂i=θi\\boldsymbol\{a\}\_\{i\}=\\theta\_\{i\}\), the PNU risk estimator, and our proposed linear risk estimator with optimal parameter𝒂∗\\boldsymbol\{a\}^\{\*\}\. We present binary classification results \(k=2k=2\) here; multiclass results are deferred to the Appendix\.

##### Datasets\.

We use two datasets: a synthetic two\-dimensional Gaussian dataset and Credit default dataset from the UCI Machine Learning Repository\[kelly23UCI\]\. For the Gaussian dataset, the class\-conditional distributions arep1​\(x\)=𝒩​\(\(1,1\)⊤,I2\)p\_\{1\}\(x\)=\\mathcal\{N\}\\\!\\bigl\(\(1,\\;1\)^\{\\\!\\top\},I\_\{2\}\\bigr\)andp2​\(x\)=𝒩​\(\(0,0\)⊤,I2\)p\_\{2\}\(x\)=\\mathcal\{N\}\\\!\\bigl\(\(0,\\;0\)^\{\\\!\\top\},I\_\{2\}\\bigr\)\.

##### Model and training\.

We train a logistic regression modelg​\(x\)=w⊤​x\+bg\(x\)=w^\{\\\!\\top\}\\\!x\+bby minimizing the binary cross\-entropy \(BCE\) loss withn1=n2=30n\_\{1\}=n\_\{2\}=30labeled samples via stochastic gradient descent\.

##### Evaluation loss\.

For the variance comparison, we use two loss functions: the BCE lossl​\(g​\(x\),y\)=−y​log⁡σ​\(g​\(x\)\)−\(1−y\)​log⁡\(1−σ​\(g​\(x\)\)\)l\(g\(x\),y\)=\-y\\log\\sigma\(g\(x\)\)\-\(1\-y\)\\log\(1\-\\sigma\(g\(x\)\)\)as an asymmetric loss, and the 0\-1 loss as a symmetric loss\.

##### Evaluation protocol\.

With the trained classifierggfixed, we evaluate the variance of each risk estimator by repeatedly sampling from held\-out data\. To compute the optimal parametersη∗\\eta^\{\*\}and𝒂∗\\boldsymbol\{a\}^\{\*\}, we estimate the covariance matricesCmC\_\{m\}for allm∈\[k\]m\\in\[k\]using the entire held\-out data\. For the PNU risk, we consider the setSP​N​U:=SP​N​P​U∪SP​N​N​US\_\{PNU\}:=S\_\{PNPU\}\\cup S\_\{PNNU\}as defined in Theorem[9](https://arxiv.org/html/2607.11947#Thmthm9)\.

For each experimental condition \(class priorθ1\\theta\_\{1\}, unlabeled sample sizenUn\_\{U\}\), we conduct5,0005\{,\}000independent trials to estimate the risk variances\. We varyθ1∈\{0\.3,0\.5,0\.7\}\\theta\_\{1\}\\in\\\{0\.3,0\.5,0\.7\\\}andnU∈\{50,100,200,500,1000\}n\_\{U\}\\in\\\{50,100,200,500,1000\\\}\. The labeled sample sizes for risk estimation are fixed atn1=n2=30n\_\{1\}=n\_\{2\}=30across all settings\.

#### 6\.1\.1Results

Figure[1](https://arxiv.org/html/2607.11947#S6.F1)visualizes the variance ratiosVar​\(R^PNU\)/Var​\(R^\)\\mathrm\{Var\}\(\\hat\{R\}\_\{\\mathrm\{PNU\}\}\)/\\mathrm\{Var\}\(\\hat\{R\}\)andVar​\(R^l​i​n𝒂∗\)/Var​\(R^\)\\mathrm\{Var\}\(\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}\)/\\mathrm\{Var\}\(\\hat\{R\}\)as a function ofnUn\_\{U\}for each class prior\.

![Refer to caption](https://arxiv.org/html/2607.11947v1/exp/fig_var_compare_gaussian_bce.png)\(a\)Gaussian \(BCE loss\)
![Refer to caption](https://arxiv.org/html/2607.11947v1/exp/fig_var_compare_credit_bce.png)\(b\)Credit \(BCE loss\)
![Refer to caption](https://arxiv.org/html/2607.11947v1/exp/fig_var_compare_gaussian_01.png)\(c\)Gaussian \(0\-1 loss\)
![Refer to caption](https://arxiv.org/html/2607.11947v1/exp/fig_var_compare_credit_01.png)\(d\)Credit \(0\-1 loss\)

Figure 1:Variance ratio \(each method / PN\) as a function of the unlabeled sample sizenUn\_\{U\}forθ1∈\{0\.3,0\.5,0\.7\}\\theta\_\{1\}\\in\\\{0\.3,\\;0\.5,\\;0\.7\\\}\. Solid lines denote the proposed linear risk estimator \(R^l​i​n𝒂∗\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}\); dotted lines denote the PNU risk estimator\. The red dashed line indicates the supervised baseline \(ratio=1\\mathrm\{ratio\}=1\)\. Both methods benefit from increasingnUn\_\{U\}, and the proposed method consistently achieves equal or lower variance than PNU\.##### Effect of unlabeled sample size\.

As the number of unlabeled samplesnUn\_\{U\}increases, both the PNU and the proposed linear risk estimator achieve progressively lower variance ratios, confirming that unlabeled data effectively reduces the variance of risk estimation\.

##### Effect of class prior\.

When the class prior is imbalanced \(θ1=0\.3\\theta\_\{1\}=0\.3orθ1=0\.7\\theta\_\{1\}=0\.7\), both methods achieve substantial variance reduction\. These results are consistent with Theorem[4](https://arxiv.org/html/2607.11947#Thmthm4)\. In the balanced case \(θ1=0\.5\\theta\_\{1\}=0\.5\) with the asymmetric loss \(BCE\), the PNU risk shows only marginal improvement \(e\.g\., a ratio of0\.9530\.953atnU=1,000n\_\{U\}=1\{,\}000\), whereas the proposed linear risk estimator still achieves a meaningful reduction \(a ratio of0\.8830\.883\) , as predicted by Theorem[5](https://arxiv.org/html/2607.11947#Thmthm5)\.

##### Effect of loss function symmetry\.

When the loss function is symmetric, the variance ratios of the proposed estimator and the PNU estimator are nearly identical\. This is expected, since their optimal variances coincide under symmetric loss, as established in Theorem[9](https://arxiv.org/html/2607.11947#Thmthm9)\.

### 6\.2Comparison with existing semi\-supervised learning methods

Table 1:Binary classification results \(test accuracy %, mean±\\pmstd over 30 seeds\)\. The best and second\-best methods per row areboldedandunderlined, respectively\.Table 2:Multiclass classification results \(test accuracy %, mean±\\pmstd over 30 seeds\)\. The best and second\-best methods per row areboldedandunderlined, respectively\.We compare the proposed SSL methods against four baselines on binary and multiclass classification tasks: \(1\)Sup\.: standard supervised learning \(linear risk with𝒂i:=θi\\boldsymbol\{a\}\_\{i\}:=\\theta\_\{i\}\); \(2\)PNU: the PNU risk estimator ofsakai17semiwith the equal variance assumption \(binary only\); \(3\)Pseudo Label \(PL\): self\-training with pseudo\-labels assigned by confidence thresholding, based onyaro95uns; and \(4\)VAT: virtual adversarial training\[miyato19vat\], which is a representative consistency regularization method\. We denote our iterative method for optimizingggand𝒂\\boldsymbol\{a\}in this subsection asOurs \(Iter\)\. For multiclass tasks, we additionally reportOurs \(EC\), the data\-free method under the equal covariance assumption\. We assume class priorsθi\\theta\_\{i\}are known\. In practice, we can estimate the class priors using methods such as those proposed bykawakubo16comp,ram16kernel,moreo25kernel,lipton18black\. We use the cross\-entropy loss for all methods\. Detailed settings are provided in the Appendix\.

##### Datasets\.

We use six binary and four multiclass classification tasks\.*Binary tabular*: Adult, Banknote, Breast Cancer, and Credit Default from the UCI Machine Learning Repository\[kelly23UCI\]\.*Binary image*: MNIST digits 4 vs\. 9 \(MNIST 4v9\) and CIFAR\-10 cat vs\. dog \(CIFAR CvD\)\.*Multiclass*: Covertype, Shuttle, and Dry Beans \(7 classes\), and MNIST \(10 classes\)\. For binary tasks, labeled samples are specified as\(n1,n2\)∈\{\(15,45\),\(30,30\),\(50,150\),\(100,100\)\}\(n\_\{1\},n\_\{2\}\)\\in\\\{\(15,45\),\(30,30\),\(50,150\),\(100,100\)\\\}withnU=300n\_\{U\}=300\(tabular\) ornU=5,000n\_\{U\}=5\{,\}000\(image\)\. For multiclass tasks, we test three regimes of labeled sample sizes—*balanced*\(equal samples per class\),*mild imbalance*, and*severe imbalance*—withnU=5,000n\_\{U\}=5\{,\}000\. Please refer to the Appendix for further details\. The validation set consists of6060samples for all settings, except for the multiclass image task, which uses200200samples\.

##### Models and training\.

We use multi\-layer perceptrons \(MLPs\) for tabular datasets and convolutional neural networks \(CNNs\) for image datasets\. All models are trained using the Adam optimizer\. Since these models are complex, we apply non\-negative risk correction in Section[5\.2](https://arxiv.org/html/2607.11947#S5.SS2)to our methods and PNU learning\.

#### 6\.2\.1Results

##### Binary classification results\.

Table[1](https://arxiv.org/html/2607.11947#S6.T1)summarizes the binary classification results\. Across tabular datasets, risk\-rewriting methods \(Ours and PNU\) consistently outperform Pseudo Label and VAT, often by a large margin\. This is expected, as tabular datasets typically do not satisfy the distributional assumptions relied upon by those methods\. In almost all settings, our method ranks first or second\.

On MNIST 4v9, Pseudo Label benefits from the well\-separated cluster structure of the MNIST digits, achieving the best accuracy with very few labels\(n1=15\)\(n\_\{1\}\{=\}15\)\. However, on CIFAR\-10 cat vs\. dog, a more challenging task, it fails to yield comparable performance\.

##### Multiclass classification results\.

Table[2](https://arxiv.org/html/2607.11947#S6.T2)presents the multiclass results for the tabular datasets and MNIST\. On Covertype and Shuttle, our methodsOurs \(Iter\)andOurs \(EC\)consistently rank first or second, while PL and VAT sometimes underperform compared to standard supervised learning\.

For Dry Beans and MNIST, although PL and VAT show strong performance, our methods achieve better or comparable accuracy to standard supervised learning\. In summary, our methods are more robust than PL and VAT, which rely on distributional assumptions\.

It is worth highlighting that the data\-freeOurs \(EC\)method demonstrates highly competitive accuracy, matching or closely following the iterative optimization approach without requiring a validation set for parameter tuning\.

## 7Conclusions

We proposed a generalized framework for distribution\-free semi\-supervised learning based on risk rewriting\. By formulating the set of linear combinations of component risksSl​i​nS\_\{lin\}, our framework subsumes existing methods such as PNU learning and naturally extends to multiclass classification\. Experiments confirmed that our methods consistently match or outperform existing approaches\.

PNU learning has had a major impact on subsequent research in SSL and weakly supervised learning\[ishida17comple,shimada21pair,hien24anomaly,sakai18auc,hamm20pushift,wang25multi,kato20delayed,tsuchiya21ord,hayashi18mat\]\. These studies attempt to reduce the variance of risks by simply mixing rewritten risks similarly to PNU learning\. By applying our framework, these methods can be formulated using the linear combination set to construct risk estimators with smaller variances, thereby improving learning efficiency\. We leave the application of our generalized framework to these broad problem settings for future work\.

###### Acknowledgements\.

This work was supported in part by JSPS KAKENHI Grant Numbers JP24K14849 and JP26H02491\.

## References

Appendix

## Appendix AOmitted Proofs

###### Proof of Theorem[1](https://arxiv.org/html/2607.11947#Thmthm1)\.

We can writeRl​i​n\{ai​j\},\{bj\}​\(g\)R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(g\)as

Rl​i​n\{ai​j\},\{bj\}​\(g\)\\displaystyle R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(g\)=∑i,jai​j​Ri​j​\(g\)\+∑jbj​RU​j​\(g\)\\displaystyle=\\sum\_\{i,j\}a\_\{ij\}R\_\{ij\}\(g\)\+\\sum\_\{j\}b\_\{j\}R\_\{Uj\}\(g\)=∑i,jai​j​Ri​j​\(g\)\+∑jbj​\(∑iθi​Ri​j​\(g\)\)\\displaystyle=\\sum\_\{i,j\}a\_\{ij\}R\_\{ij\}\(g\)\+\\sum\_\{j\}b\_\{j\}\\left\(\\sum\_\{i\}\\theta\_\{i\}R\_\{ij\}\(g\)\\right\)=∑i,jai​j​Ri​j​\(g\)\+∑i,jθi​bj​Ri​j​\(g\)\\displaystyle=\\sum\_\{i,j\}a\_\{ij\}R\_\{ij\}\(g\)\+\\sum\_\{i,j\}\\theta\_\{i\}b\_\{j\}R\_\{ij\}\(g\)=∑i,j\(ai​j\+θi​bj\)​Ri​j​\(g\)\.\\displaystyle=\\sum\_\{i,j\}\(a\_\{ij\}\+\\theta\_\{i\}b\_\{j\}\)R\_\{ij\}\(g\)\.
In addition,

R​\(g\)=∑i=1kθi​Ri​i​\(g\)=∑i,jδi​j​θi​Ri​j​\(g\)\.R\(g\)=\\sum\_\{i=1\}^\{k\}\\theta\_\{i\}R\_\{ii\}\(g\)=\\sum\_\{i,j\}\\delta\_\{ij\}\\theta\_\{i\}R\_\{ij\}\(g\)\.
Considering∀g∈𝒢,Rl​i​n​\(g\)=R​\(g\)\\forall g\\in\\mathcal\{G\},R\_\{lin\}\(g\)=R\(g\),

∑i,j\(ai​j\+θi​bj−δi​j​θi\)​Ri​j​\(g\)=0\(∀g∈𝒢\)\.\\sum\_\{i,j\}\\left\(a\_\{ij\}\+\\theta\_\{i\}b\_\{j\}\-\\delta\_\{ij\}\\theta\_\{i\}\\right\)R\_\{ij\}\(g\)=0\\quad\(\\forall g\\in\\mathcal\{G\}\)\.
Then, under Assumption[1](https://arxiv.org/html/2607.11947#Thmasmp1),∀i,θi=ai​i\+θi​bi\\forall i,\\theta\_\{i\}=a\_\{ii\}\+\\theta\_\{i\}b\_\{i\}and∀i≠j,ai​j\+θi​bj=0\\forall i\\neq j,a\_\{ij\}\+\\theta\_\{i\}b\_\{j\}=0\. Substitutingbi=1−ai​iθib\_\{i\}=1\-\\frac\{a\_\{ii\}\}\{\\theta\_\{i\}\}andai​j=−θi​bj=θiθj​aj​j−θia\_\{ij\}=\-\\theta\_\{i\}b\_\{j\}=\\frac\{\\theta\_\{i\}\}\{\\theta\_\{j\}\}a\_\{jj\}\-\\theta\_\{i\}intoRl​i​n\{ai​j\},\{bj\}​\(g\)R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(g\), we derive the objective set\. ∎

###### Proof of Theorem[3](https://arxiv.org/html/2607.11947#Thmthm3)\.

The minimum value of the convex quadratic functionf​\(𝒂\)f\(\\boldsymbol\{a\}\)is given by the algebraic identity:

f​\(𝒂∗\)=c−𝐛T​A−1​𝐛f\(\\boldsymbol\{a\}^\{\*\}\)=c\-\\mathbf\{b\}^\{T\}A^\{\-1\}\\mathbf\{b\}\(17\)
Step 1: Simplifying the Term𝐛T​A−1​𝐛\\mathbf\{b\}^\{T\}A^\{\-1\}\\mathbf\{b\}First, we expressAAand𝐛\\mathbf\{b\}in terms ofSSandQQ\.

A=∑m=1kθm2nm​Q​Cm​Q=Q​\(∑m=1kθm2nm​Cm\)​Q=Q​S​QA=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}QC\_\{m\}Q=Q\\left\(\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\right\)Q=QSQ𝐛=∑m=1kθm2nm​Q​Cm​𝐝m=Q​∑m=1kθm2nm​Cm​𝐝m\\mathbf\{b\}=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}QC\_\{m\}\\mathbf\{d\}\_\{m\}=Q\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\mathbf\{d\}\_\{m\}Let𝐯:=∑m=1kθm2nm​Cm​𝐝m\\mathbf\{v\}:=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\mathbf\{d\}\_\{m\}\. Then𝐛=Q​𝐯\\mathbf\{b\}=Q\\mathbf\{v\}\. Substituting these into the quadratic term in Eq\. \([17](https://arxiv.org/html/2607.11947#A1.E17)\):

𝐛T​A−1​𝐛\\displaystyle\\mathbf\{b\}^\{T\}A^\{\-1\}\\mathbf\{b\}=\(Q​𝐯\)T​\(Q​S​Q\)−1​\(Q​𝐯\)\\displaystyle=\(Q\\mathbf\{v\}\)^\{T\}\(QSQ\)^\{\-1\}\(Q\\mathbf\{v\}\)=𝐯T​Q​\(Q−1​S−1​Q−1\)​Q​𝐯\\displaystyle=\\mathbf\{v\}^\{T\}Q\(Q^\{\-1\}S^\{\-1\}Q^\{\-1\}\)Q\\mathbf\{v\}=𝐯T​S−1​𝐯\\displaystyle=\\mathbf\{v\}^\{T\}S^\{\-1\}\\mathbf\{v\}Next, we simplify𝐯\\mathbf\{v\}using𝐝m=𝟏−𝐞m\\mathbf\{d\}\_\{m\}=\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}:

𝐯\\displaystyle\\mathbf\{v\}=∑m=1kθm2nm​Cm​\(𝟏−𝐞m\)\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\(\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}\)=\(∑m=1kθm2nm​Cm\)​𝟏−∑m=1kθm2nm​Cm​𝐞m\\displaystyle=\\left\(\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\right\)\\mathbf\{1\}\-\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\mathbf\{e\}\_\{m\}=S​𝟏−𝐮\\displaystyle=S\\mathbf\{1\}\-\\mathbf\{u\}Thus, the reduction term is𝐯T​S−1​𝐯=\(S​𝟏−𝐮\)T​S−1​\(S​𝟏−𝐮\)\\mathbf\{v\}^\{T\}S^\{\-1\}\\mathbf\{v\}=\(S\\mathbf\{1\}\-\\mathbf\{u\}\)^\{T\}S^\{\-1\}\(S\\mathbf\{1\}\-\\mathbf\{u\}\)\.

Step 2: Expansion of𝐯T​S−1​𝐯\\mathbf\{v\}^\{T\}S^\{\-1\}\\mathbf\{v\}Expanding the term derived above:

𝐯T​S−1​𝐯\\displaystyle\\mathbf\{v\}^\{T\}S^\{\-1\}\\mathbf\{v\}=\(𝟏T​S−𝐮T\)​S−1​\(S​𝟏−𝐮\)\\displaystyle=\(\\mathbf\{1\}^\{T\}S\-\\mathbf\{u\}^\{T\}\)S^\{\-1\}\(S\\mathbf\{1\}\-\\mathbf\{u\}\)=𝟏T​S​S−1​S​𝟏−𝐮T​S−1​S​𝟏−𝟏T​S​S−1​𝐮\+𝐮T​S−1​𝐮\\displaystyle=\\mathbf\{1\}^\{T\}SS^\{\-1\}S\\mathbf\{1\}\-\\mathbf\{u\}^\{T\}S^\{\-1\}S\\mathbf\{1\}\-\\mathbf\{1\}^\{T\}SS^\{\-1\}\\mathbf\{u\}\+\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}=𝟏T​S​𝟏−2​𝟏T​𝐮\+𝐮T​S−1​𝐮\.\\displaystyle=\\mathbf\{1\}^\{T\}S\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\mathbf\{u\}\+\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}\.
Step 3: Expansion of the ConstantccWe expandc=∑m=1kθm2nm​𝐝mT​Cm​𝐝mc=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\mathbf\{d\}\_\{m\}^\{T\}C\_\{m\}\\mathbf\{d\}\_\{m\}:

c\\displaystyle c=∑m=1kθm2nm​\(𝟏−𝐞m\)T​Cm​\(𝟏−𝐞m\)\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}\)^\{T\}C\_\{m\}\(\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}\)=∑m=1kθm2nm​\(𝟏T​Cm​𝟏−2​𝟏T​Cm​𝐞m\+𝐞mT​Cm​𝐞m\)\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\left\(\\mathbf\{1\}^\{T\}C\_\{m\}\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}C\_\{m\}\\mathbf\{e\}\_\{m\}\+\\mathbf\{e\}\_\{m\}^\{T\}C\_\{m\}\\mathbf\{e\}\_\{m\}\\right\)=𝟏T​\(∑m=1kθm2nm​Cm\)​𝟏−2​𝟏T​\(∑m=1kθm2nm​Cm​𝐞m\)\+∑m=1kθm2nm​𝐞mT​Cm​𝐞m\\displaystyle=\\mathbf\{1\}^\{T\}\\left\(\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\right\)\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\left\(\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}C\_\{m\}\\mathbf\{e\}\_\{m\}\\right\)\+\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\mathbf\{e\}\_\{m\}^\{T\}C\_\{m\}\\mathbf\{e\}\_\{m\}=𝟏T​S​𝟏−2​𝟏T​𝐮\+∑m=1kθm2nm​\(Cm\)m​m\\displaystyle=\\mathbf\{1\}^\{T\}S\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\mathbf\{u\}\+\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(C\_\{m\}\)\_\{mm\}
Final CalculationSubstituting the expanded forms ofccand𝐯T​S−1​𝐯\\mathbf\{v\}^\{T\}S^\{\-1\}\\mathbf\{v\}back into Eq\. \([17](https://arxiv.org/html/2607.11947#A1.E17)\):

f​\(𝒂∗\)\\displaystyle f\(\\boldsymbol\{a\}^\{\*\}\)=c−𝐯T​S−1​𝐯\\displaystyle=c\-\\mathbf\{v\}^\{T\}S^\{\-1\}\\mathbf\{v\}=\(𝟏T​S​𝟏−2​𝟏T​𝐮\+∑m=1kθm2nm​\(Cm\)m​m\)−\(𝟏T​S​𝟏−2​𝟏T​𝐮\+𝐮T​S−1​𝐮\)\\displaystyle=\\left\(\\mathbf\{1\}^\{T\}S\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\mathbf\{u\}\+\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(C\_\{m\}\)\_\{mm\}\\right\)\-\\left\(\\mathbf\{1\}^\{T\}S\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\mathbf\{u\}\+\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}\\right\)=∑m=1kθm2nm​\(Cm\)m​m−𝐮T​S−1​𝐮\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(C\_\{m\}\)\_\{mm\}\-\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}∎

###### Proof of Theorem[4](https://arxiv.org/html/2607.11947#Thmthm4)\.

Let us define the weight for classmmaswmw\_\{m\}and the total weightWW:

wm:=θm2nm,W:=∑m=1kwm=∑m=1kθm2nm\.w\_\{m\}:=\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\},\\quad W:=\\sum\_\{m=1\}^\{k\}w\_\{m\}=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\.We also define a weight vector𝐰∈ℝk\\mathbf\{w\}\\in\\mathbb\{R\}^\{k\}as𝐰=\[w1,w2,…,wk\]T\\mathbf\{w\}=\[w\_\{1\},w\_\{2\},\\dots,w\_\{k\}\]^\{T\}\. Under the assumption thatCm=CC\_\{m\}=Cfor allmm, the total weighted covariance matrixSSsimplifies to:

S=∑m=1kwm​Cm=\(∑m=1kwm\)​C=W​C\.S=\\sum\_\{m=1\}^\{k\}w\_\{m\}C\_\{m\}=\\left\(\\sum\_\{m=1\}^\{k\}w\_\{m\}\\right\)C=WC\.Similarly, the weighted covariance vector𝐮\\mathbf\{u\}simplifies to

𝐮=∑m=1kwm​Cm​𝐞m=C​∑m=1kwm​𝐞m=C​𝐰\.\\mathbf\{u\}=\\sum\_\{m=1\}^\{k\}w\_\{m\}C\_\{m\}\\mathbf\{e\}\_\{m\}=C\\sum\_\{m=1\}^\{k\}w\_\{m\}\\mathbf\{e\}\_\{m\}=C\\mathbf\{w\}\.Then we can write

𝐮T​S−1​𝐮\\displaystyle\\mathbf\{u\}^\{T\}S^\{\-1\}\\mathbf\{u\}=\(C​𝐰\)T​\(W​C\)−1​\(C​𝐰\)=𝐰T​C​1W​C−1​C​𝐰\\displaystyle=\(C\\mathbf\{w\}\)^\{T\}\(WC\)^\{\-1\}\(C\\mathbf\{w\}\)=\\mathbf\{w\}^\{T\}C\\frac\{1\}\{W\}C^\{\-1\}C\\mathbf\{w\}=1W​𝐰T​C​𝐰\.\\displaystyle=\\frac\{1\}\{W\}\\mathbf\{w\}^\{T\}C\\mathbf\{w\}\.Under the assumption thatCChas diagonal elementsρ1\\rho\_\{1\}and off\-diagonal elementsρ2\\rho\_\{2\}, we have

C=\(ρ1−ρ2\)​I\+ρ2​𝟏𝟏T\.C=\(\\rho\_\{1\}\-\\rho\_\{2\}\)I\+\\rho\_\{2\}\\mathbf\{1\}\\mathbf\{1\}^\{T\}\.
Evaluating the quadratic form𝐰T​C​𝐰\\mathbf\{w\}^\{T\}C\\mathbf\{w\}yields

𝐰T​C​𝐰\\displaystyle\\mathbf\{w\}^\{T\}C\\mathbf\{w\}=𝐰T​\(\(ρ1−ρ2\)​I\+ρ2​𝟏𝟏T\)​𝐰=\(ρ1−ρ2\)​\|𝐰\|2\+ρ2​\(𝐰T​𝟏\)2\\displaystyle=\\mathbf\{w\}^\{T\}\\left\(\(\\rho\_\{1\}\-\\rho\_\{2\}\)I\+\\rho\_\{2\}\\mathbf\{1\}\\mathbf\{1\}^\{T\}\\right\)\\mathbf\{w\}=\(\\rho\_\{1\}\-\\rho\_\{2\}\)\|\\mathbf\{w\}\|^\{2\}\+\\rho\_\{2\}\(\\mathbf\{w\}^\{T\}\\mathbf\{1\}\)^\{2\}=\(ρ1−ρ2\)​∑m=1kwm2\+ρ2​W2,\\displaystyle=\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\sum\_\{m=1\}^\{k\}w\_\{m\}^\{2\}\+\\rho\_\{2\}W^\{2\},This completes the proof of the equality\. To derive the upper bound, we note that∑m=1kwm2≤\(maxm⁡wm\)​∑m=1kwm=W​maxm⁡wm\\sum\_\{m=1\}^\{k\}w\_\{m\}^\{2\}\\leq\(\\max\_\{m\}w\_\{m\}\)\\sum\_\{m=1\}^\{k\}w\_\{m\}=W\\max\_\{m\}w\_\{m\}\. Sinceρ1\>ρ2\\rho\_\{1\}\>\\rho\_\{2\}, we have

𝐮⊤​S−1​𝐮\\displaystyle\\mathbf\{u\}^\{\\top\}S^\{\-1\}\\mathbf\{u\}≤\(ρ1−ρ2\)​W​maxm⁡wmW\+ρ2​W\\displaystyle\\leq\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\frac\{W\\max\_\{m\}w\_\{m\}\}\{W\}\+\\rho\_\{2\}W=ρ1​maxm⁡wm−ρ2​maxm⁡wm\+ρ2​W\\displaystyle=\\rho\_\{1\}\\max\_\{m\}w\_\{m\}\-\\rho\_\{2\}\\max\_\{m\}w\_\{m\}\+\\rho\_\{2\}W=ρ1​maxm∈\[k\]⁡wm\+ρ2​\(W−maxm∈\[k\]⁡wm\)\.\\displaystyle=\\rho\_\{1\}\\max\_\{m\\in\[k\]\}w\_\{m\}\+\\rho\_\{2\}\\left\(W\-\\max\_\{m\\in\[k\]\}w\_\{m\}\\right\)\.∎

###### Proof of Theorem[5](https://arxiv.org/html/2607.11947#Thmthm5)\.

Dominance inequality \([11](https://arxiv.org/html/2607.11947#S3.E11)\):Recall that

RPNPUη​\(g\)\\displaystyle R\_\{\\text\{PNPU\}\}^\{\\eta\}\(g\)=\(1−η\)​\(θ1​R11\+θ2​R22\)\+η​\(θ1​R11−θ1​R12\+RU​2\)\\displaystyle=\(1\-\\eta\)\(\\theta\_\{1\}R\_\{11\}\+\\theta\_\{2\}R\_\{22\}\)\+\\eta\(\\theta\_\{1\}R\_\{11\}\-\\theta\_\{1\}R\_\{12\}\+R\_\{U2\}\)=θ1​R11\+\(1−η\)​θ2​R22−η​θ1​R12\+η​RU​2\.\\displaystyle=\\theta\_\{1\}R\_\{11\}\+\(1\-\\eta\)\\theta\_\{2\}R\_\{22\}\-\\eta\\theta\_\{1\}R\_\{12\}\+\\eta R\_\{U2\}\.This risk is equivalent toRl​i​n𝒂​\(g\)R\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)where\(a1,a2\)=\(θ1,θ2​\(1−η\)\)\(a\_\{1\},a\_\{2\}\)=\(\\theta\_\{1\},\\theta\_\{2\}\(1\-\\eta\)\)\. Similarly,

RPNNUη​\(g\)\\displaystyle R\_\{\\text\{PNNU\}\}^\{\\eta\}\(g\)=\(1−η\)​\(θ1​R11\+θ2​R22\)\+η​\(RU​1−θ2​R21\+θ2​R22\)\\displaystyle=\(1\-\\eta\)\(\\theta\_\{1\}R\_\{11\}\+\\theta\_\{2\}R\_\{22\}\)\+\\eta\(R\_\{U1\}\-\\theta\_\{2\}R\_\{21\}\+\\theta\_\{2\}R\_\{22\}\)=\(1−η\)​θ1​R11\+θ2​R22−η​θ2​R21\+η​RU​1,\\displaystyle=\(1\-\\eta\)\\theta\_\{1\}R\_\{11\}\+\\theta\_\{2\}R\_\{22\}\-\\eta\\theta\_\{2\}R\_\{21\}\+\\eta R\_\{U1\},which is equivalent toRl​i​n𝒂​\(g\)R\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)where\(a1,a2\)=\(θ1​\(1−η\),θ2\)\(a\_\{1\},a\_\{2\}\)=\(\\theta\_\{1\}\(1\-\\eta\),\\theta\_\{2\}\)\.

The sets of estimators for PNPU and PNNU learning are subsets of the generalized linear estimator setSl​i​nS\_\{lin\}\. Thus, Eq\. \([11](https://arxiv.org/html/2607.11947#S3.E11)\) holds\.

Derivation of PNPU Minimum Variance:We explicitly derive the minimum variance for the PNPU estimator in the binary setting \(k=2k=2\)\. The variance of the estimatorR^PNPUη\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta\}whennU→∞n\_\{U\}\\rightarrow\\inftyis given by:

Var⁡\(R^PNPUη\)\\displaystyle\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta\}\)=Var⁡\(θ1​R^11−η​θ1​R^12\+\(1−η\)​θ2​R^22\)\\displaystyle=\\operatorname\{Var\}\\left\(\\theta\_\{1\}\\hat\{R\}\_\{11\}\-\\eta\\theta\_\{1\}\\hat\{R\}\_\{12\}\+\(1\-\\eta\)\\theta\_\{2\}\\hat\{R\}\_\{22\}\\right\)=θ12​Var⁡\(R^11−η​R^12\)\+\(1−η\)2​θ22​Var⁡\(R^22\)\.\\displaystyle=\\theta\_\{1\}^\{2\}\\operatorname\{Var\}\(\\hat\{R\}\_\{11\}\-\\eta\\hat\{R\}\_\{12\}\)\+\(1\-\\eta\)^\{2\}\\theta\_\{2\}^\{2\}\\operatorname\{Var\}\(\\hat\{R\}\_\{22\}\)\.
AssumingC1=C2=CC\_\{1\}=C\_\{2\}=Cwith diagonal elementsρ1\\rho\_\{1\}and off\-diagonal elementsρ2\\rho\_\{2\}:

Var⁡\(R^11−η​R^12\)\\displaystyle\\operatorname\{Var\}\(\\hat\{R\}\_\{11\}\-\\eta\\hat\{R\}\_\{12\}\)=Var⁡\(R^11\)−2​η​Cov⁡\(R^11,R^12\)\+η2​Var⁡\(R^12\)\\displaystyle=\\operatorname\{Var\}\(\\hat\{R\}\_\{11\}\)\-2\\eta\\operatorname\{Cov\}\(\\hat\{R\}\_\{11\},\\hat\{R\}\_\{12\}\)\+\\eta^\{2\}\\operatorname\{Var\}\(\\hat\{R\}\_\{12\}\)=ρ1n1−2​η​ρ2n1\+η2​ρ1n1\.\\displaystyle=\\frac\{\\rho\_\{1\}\}\{n\_\{1\}\}\-\\frac\{2\\eta\\rho\_\{2\}\}\{n\_\{1\}\}\+\\frac\{\\eta^\{2\}\\rho\_\{1\}\}\{n\_\{1\}\}\.Substituting this back into the total variance expression and usingwi=θi2/niw\_\{i\}=\\theta\_\{i\}^\{2\}/n\_\{i\}:

Var⁡\(R^PNPUη\)\\displaystyle\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta\}\)=θ12​\(ρ1−2​η​ρ2\+η2​ρ1n1\)\+\(1−η\)2​θ22​ρ1n2\\displaystyle=\\theta\_\{1\}^\{2\}\\left\(\\frac\{\\rho\_\{1\}\-2\\eta\\rho\_\{2\}\+\\eta^\{2\}\\rho\_\{1\}\}\{n\_\{1\}\}\\right\)\+\(1\-\\eta\)^\{2\}\\theta\_\{2\}^\{2\}\\frac\{\\rho\_\{1\}\}\{n\_\{2\}\}=w1​\(ρ1−2​η​ρ2\+η2​ρ1\)\+w2​\(1−2​η\+η2\)​ρ1\\displaystyle=w\_\{1\}\(\\rho\_\{1\}\-2\\eta\\rho\_\{2\}\+\\eta^\{2\}\\rho\_\{1\}\)\+w\_\{2\}\(1\-2\\eta\+\\eta^\{2\}\)\\rho\_\{1\}=\(w1\+w2\)​ρ1​η2−2​\(w1​ρ2\+w2​ρ1\)​η\+\(w1\+w2\)​ρ1\.\\displaystyle=\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\\eta^\{2\}\-2\(w\_\{1\}\\rho\_\{2\}\+w\_\{2\}\\rho\_\{1\}\)\\eta\+\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\.
Then,

Var⁡\(R^PNPUη∗\)\\displaystyle\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta^\{\*\}\}\)=\(w1\+w2\)​ρ1−\(−2​\(w1​ρ2\+w2​ρ1\)\)24​\(w1\+w2\)​ρ1\\displaystyle=\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\-\\frac\{\\left\(\-2\(w\_\{1\}\\rho\_\{2\}\+w\_\{2\}\\rho\_\{1\}\)\\right\)^\{2\}\}\{4\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\}=\(w1\+w2\)​ρ1−4​\(w1​ρ2\+w2​ρ1\)24​\(w1\+w2\)​ρ1\\displaystyle=\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\-\\frac\{4\(w\_\{1\}\\rho\_\{2\}\+w\_\{2\}\\rho\_\{1\}\)^\{2\}\}\{4\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\}=\(w1\+w2\)2​ρ12−\(w1​ρ2\+w2​ρ1\)2ρ1​\(w1\+w2\)\\displaystyle=\\frac\{\(w\_\{1\}\+w\_\{2\}\)^\{2\}\\rho\_\{1\}^\{2\}\-\(w\_\{1\}\\rho\_\{2\}\+w\_\{2\}\\rho\_\{1\}\)^\{2\}\}\{\\rho\_\{1\}\(w\_\{1\}\+w\_\{2\}\)\}=w12​\(ρ12−ρ22\)\+2​w1​w2​ρ1​\(ρ1−ρ2\)ρ1​\(w1\+w2\)\.\\displaystyle=\\frac\{w\_\{1\}^\{2\}\(\\rho\_\{1\}^\{2\}\-\\rho\_\{2\}^\{2\}\)\+2w\_\{1\}w\_\{2\}\\rho\_\{1\}\(\\rho\_\{1\}\-\\rho\_\{2\}\)\}\{\\rho\_\{1\}\(w\_\{1\}\+w\_\{2\}\)\}\.
Variance gap \([12](https://arxiv.org/html/2607.11947#S3.E12)\):Using the result from Theorem[4](https://arxiv.org/html/2607.11947#Thmthm4)fork=2k=2, the minimum variance of our proposed estimator is:

Var⁡\(R^l​i​n𝒂∗\)\\displaystyle\\operatorname\{Var\}\(\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}\)=∑m=12wm​ρ1−\[\(ρ1−ρ2\)​w12\+w22W\+ρ2​W\]\\displaystyle=\\sum\_\{m=1\}^\{2\}w\_\{m\}\\rho\_\{1\}\-\\left\[\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\frac\{w\_\{1\}^\{2\}\+w\_\{2\}^\{2\}\}\{W\}\+\\rho\_\{2\}W\\right\]=ρ1​W−ρ2​W−\(ρ1−ρ2\)​w12\+w22W\\displaystyle=\\rho\_\{1\}W\-\\rho\_\{2\}W\-\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\frac\{w\_\{1\}^\{2\}\+w\_\{2\}^\{2\}\}\{W\}=\(ρ1−ρ2\)​\(W−w12\+w22W\)\\displaystyle=\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\left\(W\-\\frac\{w\_\{1\}^\{2\}\+w\_\{2\}^\{2\}\}\{W\}\\right\)=\(ρ1−ρ2\)​\(w1\+w2\)2−\(w12\+w22\)W\\displaystyle=\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\frac\{\(w\_\{1\}\+w\_\{2\}\)^\{2\}\-\(w\_\{1\}^\{2\}\+w\_\{2\}^\{2\}\)\}\{W\}=\(ρ1−ρ2\)​2​w1​w2w1\+w2\.\\displaystyle=\(\\rho\_\{1\}\-\\rho\_\{2\}\)\\frac\{2w\_\{1\}w\_\{2\}\}\{w\_\{1\}\+w\_\{2\}\}\.We compute the gapVar⁡\(R^PNPUηP​U∗\)−Var⁡\(R^l​i​n𝒂∗\)\\operatorname\{Var\}\(\\hat\{R\}\_\{\\text\{PNPU\}\}^\{\\eta^\{\*\}\_\{PU\}\}\)\-\\operatorname\{Var\}\(\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}\):

Gap=w12​\(ρ1−ρ2\)​\(ρ1\+ρ2\)\+2​w1​w2​ρ1​\(ρ1−ρ2\)ρ1​W−2​w1​w2​\(ρ1−ρ2\)W\\displaystyle=\\frac\{w\_\{1\}^\{2\}\(\\rho\_\{1\}\-\\rho\_\{2\}\)\(\\rho\_\{1\}\+\\rho\_\{2\}\)\+2w\_\{1\}w\_\{2\}\\rho\_\{1\}\(\\rho\_\{1\}\-\\rho\_\{2\}\)\}\{\\rho\_\{1\}W\}\-\\frac\{2w\_\{1\}w\_\{2\}\(\\rho\_\{1\}\-\\rho\_\{2\}\)\}\{W\}=\(ρ1−ρ2\)W​\[w12​\(ρ1\+ρ2\)\+2​w1​w2​ρ1ρ1−2​w1​w2\]\\displaystyle=\\frac\{\(\\rho\_\{1\}\-\\rho\_\{2\}\)\}\{W\}\\left\[\\frac\{w\_\{1\}^\{2\}\(\\rho\_\{1\}\+\\rho\_\{2\}\)\+2w\_\{1\}w\_\{2\}\\rho\_\{1\}\}\{\\rho\_\{1\}\}\-2w\_\{1\}w\_\{2\}\\right\]=\(ρ1−ρ2\)W​\[w12​\(ρ1\+ρ2\)ρ1\+2​w1​w2−2​w1​w2\]\\displaystyle=\\frac\{\(\\rho\_\{1\}\-\\rho\_\{2\}\)\}\{W\}\\left\[\\frac\{w\_\{1\}^\{2\}\(\\rho\_\{1\}\+\\rho\_\{2\}\)\}\{\\rho\_\{1\}\}\+2w\_\{1\}w\_\{2\}\-2w\_\{1\}w\_\{2\}\\right\]=w12​\(ρ12−ρ22\)\(w1\+w2\)​ρ1\.\\displaystyle=\\frac\{w\_\{1\}^\{2\}\(\\rho\_\{1\}^\{2\}\-\\rho\_\{2\}^\{2\}\)\}\{\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\}\.
By symmetry, the gap for PNNU isw22​\(ρ12−ρ22\)\(w1\+w2\)​ρ1\\frac\{w\_\{2\}^\{2\}\(\\rho\_\{1\}^\{2\}\-\\rho\_\{2\}^\{2\}\)\}\{\(w\_\{1\}\+w\_\{2\}\)\\rho\_\{1\}\}\. The result follows\. ∎

###### Proof of Theorem[6](https://arxiv.org/html/2607.11947#Thmthm6)\.

From the definition of symmetric loss∑j=1kRi​j=α\\sum\_\{j=1\}^\{k\}R\_\{ij\}=\\alpha, the following holds:

Ri​k=α−∑j=1k−1Ri​j,RU​k=α−∑j=1k−1RU​jR\_\{ik\}=\\alpha\-\\sum\_\{j=1\}^\{k\-1\}R\_\{ij\},\\quad R\_\{Uk\}=\\alpha\-\\sum\_\{j=1\}^\{k\-1\}R\_\{Uj\}\(18\)
Substituting the above expressions intoRl​i​n​\(g\)R\_\{lin\}\(g\), we derive

Rl​i​n\{ai​j\},\{bj\}\\displaystyle R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}=∑i,jai​j​Ri​j​\(g\)\+∑jbj​RU​j\\displaystyle=\\sum\_\{i,j\}a\_\{ij\}R\_\{ij\}\(g\)\+\\sum\_\{j\}b\_\{j\}R\_\{Uj\}=∑i\[∑j=1k−1ai​j​Ri​j\+ai​k​\(α−∑j=1k−1Ri​j\)\]\+∑j=1k−1bj​RU​j\+bk​\(α−∑j=1k−1RU​j\)\\displaystyle=\\sum\_\{i\}\\left\[\\sum\_\{j=1\}^\{k\-1\}a\_\{ij\}R\_\{ij\}\+a\_\{ik\}\\left\(\\alpha\-\\sum\_\{j=1\}^\{k\-1\}R\_\{ij\}\\right\)\\right\]\+\\sum\_\{j=1\}^\{k\-1\}b\_\{j\}R\_\{Uj\}\+b\_\{k\}\\left\(\\alpha\-\\sum\_\{j=1\}^\{k\-1\}R\_\{Uj\}\\right\)=∑i∑j=1k−1\(ai​j−ai​k\)⏟a~i​j​Ri​j\+∑j=1k−1\(bj−bk\)⏟b~j​RU​j\+α​\(∑iai​k\+bk\)\\displaystyle=\\sum\_\{i\}\\sum\_\{j=1\}^\{k\-1\}\\underbrace\{\(a\_\{ij\}\-a\_\{ik\}\)\}\_\{\\tilde\{a\}\_\{ij\}\}R\_\{ij\}\+\\sum\_\{j=1\}^\{k\-1\}\\underbrace\{\(b\_\{j\}\-b\_\{k\}\)\}\_\{\\tilde\{b\}\_\{j\}\}R\_\{Uj\}\+\\alpha\\left\(\\sum\_\{i\}a\_\{ik\}\+b\_\{k\}\\right\)
where we definea~i​j:=ai​j−ai​k\\tilde\{a\}\_\{ij\}:=a\_\{ij\}\-a\_\{ik\}andb~j:=bj−bk\\tilde\{b\}\_\{j\}:=b\_\{j\}\-b\_\{k\}\. UsingRU​j=∑iθi​Ri​jR\_\{Uj\}=\\sum\_\{i\}\\theta\_\{i\}R\_\{ij\}, the second term can be rewritten as:

∑j=1k−1\(bj−bk\)​RU​j=∑j=1k−1\(bj−bk\)​∑iθi​Ri​j=∑i∑j=1k−1\(bj−bk\)​θi​Ri​j\\sum\_\{j=1\}^\{k\-1\}\(b\_\{j\}\-b\_\{k\}\)R\_\{Uj\}=\\sum\_\{j=1\}^\{k\-1\}\(b\_\{j\}\-b\_\{k\}\)\\sum\_\{i\}\\theta\_\{i\}R\_\{ij\}=\\sum\_\{i\}\\sum\_\{j=1\}^\{k\-1\}\(b\_\{j\}\-b\_\{k\}\)\\theta\_\{i\}R\_\{ij\}\(19\)
Substituting these back intoRl​i​nR\_\{lin\}and rearranging:

Rl​i​n\{ai​j\},\{bj\}=∑i∑j=1k−1\(ai​j−ai​k\+\(bj−bk\)​θi\)​Ri​j\+α​\(∑iai​k\+bk\)R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}=\\sum\_\{i\}\\sum\_\{j=1\}^\{k\-1\}\\left\(a\_\{ij\}\-a\_\{ik\}\+\(b\_\{j\}\-b\_\{k\}\)\\theta\_\{i\}\\right\)R\_\{ij\}\+\\alpha\\left\(\\sum\_\{i\}a\_\{ik\}\+b\_\{k\}\\right\)\(20\)
On the other hand, the true riskR​\(g\)R\(g\)can be written as follows \(expandingRi​kR\_\{ik\}\):

R​\(g\)\\displaystyle R\(g\)=∑iθi​Ri​i=∑i=1k−1θi​Ri​i\+θk​Rk​k\\displaystyle=\\sum\_\{i\}\\theta\_\{i\}R\_\{ii\}=\\sum\_\{i=1\}^\{k\-1\}\\theta\_\{i\}R\_\{ii\}\+\\theta\_\{k\}R\_\{kk\}=∑i=1k−1θi​Ri​i\+θk​\(α−∑j=1k−1Rk​j\)\\displaystyle=\\sum\_\{i=1\}^\{k\-1\}\\theta\_\{i\}R\_\{ii\}\+\\theta\_\{k\}\\left\(\\alpha\-\\sum\_\{j=1\}^\{k\-1\}R\_\{kj\}\\right\)
Under Assumption[2](https://arxiv.org/html/2607.11947#Thmasmp2), we derive the conditions for the identity∀g∈𝒢,Rl​i​n​\(g\)=R​\(g\)\\forall g\\in\\mathcal\{G\},R\_\{lin\}\(g\)=R\(g\)to hold :

\{∀i,j∈\[k−1\],ai​j−ai​k\+\(bj−bk\)​θi−δi​j​θi=0\(Coeff\. of​Ri​j\)∀j∈\[k−1\],ak​j−ak​k\+\(bj−bk\)​θk\+θk=0\(Coeff\. of​Rk​j\)∑iai​k\+bk−θk=0\(Constant term\)\\begin\{cases\}\\forall i,j\\in\[k\-1\],&a\_\{ij\}\-a\_\{ik\}\+\(b\_\{j\}\-b\_\{k\}\)\\theta\_\{i\}\-\\delta\_\{ij\}\\theta\_\{i\}=0\\quad\(\\text\{Coeff\. of \}R\_\{ij\}\)\\\\ \\forall j\\in\[k\-1\],&a\_\{kj\}\-a\_\{kk\}\+\(b\_\{j\}\-b\_\{k\}\)\\theta\_\{k\}\+\\theta\_\{k\}=0\\quad\(\\text\{Coeff\. of \}R\_\{kj\}\)\\\\ &\\sum\_\{i\}a\_\{ik\}\+b\_\{k\}\-\\theta\_\{k\}=0\\quad\(\\text\{Constant term\}\)\\end\{cases\}\(21\)
Suppose we are given arbitrarya~i​j∈ℝ\\tilde\{a\}\_\{ij\}\\in\\mathbb\{R\}andb~j∈ℝ\\tilde\{b\}\_\{j\}\\in\\mathbb\{R\}for alli∈\[k\]i\\in\[k\]andj∈\[k−1\]j\\in\[k\-1\]that satisfy the above equations\. There are values ofai​j,bja\_\{ij\},b\_\{j\}that satisfy the above equations anda~i​j=ai​j−ai​k\\tilde\{a\}\_\{ij\}=a\_\{ij\}\-a\_\{ik\}andb~j=bj−bk\\tilde\{b\}\_\{j\}=b\_\{j\}\-b\_\{k\}\. Thus, we can simplifyRl​i​n\{ai​j\},\{bj\}​\(g\)R\_\{lin\}^\{\\\{a\_\{ij\}\\\},\\\{b\_\{j\}\\\}\}\(g\)as

Rl​i​n​\(g\)=∑i∑jk−1a~i​j​Ri​j\+∑jk−1b~j​RU​j\+α​θk,where​a~i​j,b~j∈ℝR\_\{lin\}\(g\)=\\sum\_\{i\}\\sum\_\{j\}^\{k\-1\}\\tilde\{a\}\_\{ij\}R\_\{ij\}\+\\sum\_\{j\}^\{k\-1\}\\tilde\{b\}\_\{j\}R\_\{Uj\}\+\\alpha\\theta\_\{k\},\\quad\\text\{where \}\\tilde\{a\}\_\{ij\},\\tilde\{b\}\_\{j\}\\in\\mathbb\{R\}\(22\)
The conditions are:

1. 1\.a~i​j\+b~j​θi−δi​j​θi=0∀i,j∈\[k−1\]\\tilde\{a\}\_\{ij\}\+\\tilde\{b\}\_\{j\}\\theta\_\{i\}\-\\delta\_\{ij\}\\theta\_\{i\}=0\\quad\\forall i,j\\in\[k\-1\]
2. 2\.a~k​j\+b~j​θk\+θk=0∀j∈\[k−1\]\\tilde\{a\}\_\{kj\}\+\\tilde\{b\}\_\{j\}\\theta\_\{k\}\+\\theta\_\{k\}=0\\quad\\forall j\\in\[k\-1\]

Solving these yields:

∀i∈\[k−1\],\\displaystyle\\forall i\\in\[k\-1\],\\quada~i​i\+b~i​θi−θi=0\\displaystyle\\tilde\{a\}\_\{ii\}\+\\tilde\{b\}\_\{i\}\\theta\_\{i\}\-\\theta\_\{i\}=0⇒\\displaystyle\\Rightarrow\\quadb~i=1−a~i​iθi\\displaystyle\\tilde\{b\}\_\{i\}=1\-\\frac\{\\tilde\{a\}\_\{ii\}\}\{\\theta\_\{i\}\}\(23\)
Also, wheni≠ji\\neq j,a~i​j\+b~j​θi=0\\tilde\{a\}\_\{ij\}\+\\tilde\{b\}\_\{j\}\\theta\_\{i\}=0\. From these, we get:

∀i,j∈\[k−1\]​s\.t\.​i≠j,a~i​j\\displaystyle\\forall i,j\\in\[k\-1\]\\text\{ s\.t\. \}i\\neq j,\\quad\\tilde\{a\}\_\{ij\}=−θi​b~j\\displaystyle=\-\\theta\_\{i\}\\tilde\{b\}\_\{j\}=−θi​\(1−a~j​jθj\)\\displaystyle=\-\\theta\_\{i\}\\left\(1\-\\frac\{\\tilde\{a\}\_\{jj\}\}\{\\theta\_\{j\}\}\\right\)\(24\)
Furthermore, for thekk\-th class:

a~k​j\\displaystyle\\tilde\{a\}\_\{kj\}=−θk​\(1\+b~j\)\\displaystyle=\-\\theta\_\{k\}\(1\+\\tilde\{b\}\_\{j\}\)=−θk​\(2−a~j​jθj\)\\displaystyle=\-\\theta\_\{k\}\\left\(2\-\\frac\{\\tilde\{a\}\_\{jj\}\}\{\\theta\_\{j\}\}\\right\)\(25\)
Substituting the above equations intoRl​i​n​\(g\)R\_\{lin\}\(g\), we derive the target set\. ∎

###### Proof of Theorem[7](https://arxiv.org/html/2607.11947#Thmthm7)\.

We derive the variance of the estimatorR^l​i​n𝒂\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}under the symmetric loss assumption\. Recall that the estimator is given by:

R^l​i​n𝒂=∑i=1kθi​R^i​i\+∑i=1k∑j=1k−1θi​\(ajθj−1\)​R^i​j−∑j=1k−1\(ajθj−1\)​R^U​j\.\\hat\{R\}^\{\\boldsymbol\{a\}\}\_\{lin\}=\\sum^\{k\}\_\{i=1\}\\theta\_\{i\}\\hat\{R\}\_\{ii\}\+\\sum^\{k\}\_\{i=1\}\\sum^\{k\-1\}\_\{j=1\}\\theta\_\{i\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)\\hat\{R\}\_\{ij\}\-\\sum^\{k\-1\}\_\{j=1\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)\\hat\{R\}\_\{Uj\}\.\(26\)In the asymptotic regime wherenU→∞n\_\{U\}\\to\\infty, the variance of the unlabeled component vanishes\. Thus, we focus on the labeled components\. Since the labeled datasets𝒳m\\mathcal\{X\}\_\{m\}form∈\{1,…,k\}m\\in\\\{1,\\dots,k\\\}are independent, the total variance is the sum of the variances contributed by each class\. We defineTmT\_\{m\}as the terms inR^l​i​n𝒂\\hat\{R\}^\{\\boldsymbol\{a\}\}\_\{lin\}dependent on𝒳m\\mathcal\{X\}\_\{m\}:

Tm=θm​R^m​m\+∑j=1k−1θm​\(ajθj−1\)​R^m​j\.T\_\{m\}=\\theta\_\{m\}\\hat\{R\}\_\{mm\}\+\\sum\_\{j=1\}^\{k\-1\}\\theta\_\{m\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)\\hat\{R\}\_\{mj\}\.\(27\)Let𝐑ˇm=\[R^m​1,…,R^m,k−1\]⊤\\check\{\\mathbf\{R\}\}\_\{m\}=\[\\hat\{R\}\_\{m1\},\\dots,\\hat\{R\}\_\{m,k\-1\}\]^\{\\top\}be the vector of component risks for classmmrestricted to the firstk−1k\-1labels\. The covariance matrix of𝐑ˇm\\check\{\\mathbf\{R\}\}\_\{m\}is1nm​Cˇm\\frac\{1\}\{n\_\{m\}\}\\check\{C\}\_\{m\}\. We expressTmT\_\{m\}as a linear combination𝐜m⊤​𝐑ˇm\+const\\mathbf\{c\}\_\{m\}^\{\\top\}\\check\{\\mathbf\{R\}\}\_\{m\}\+\\text\{const\}and determine the coefficient vector𝐜m∈ℝk−1\\mathbf\{c\}\_\{m\}\\in\\mathbb\{R\}^\{k\-1\}\.

Case 1:m<km<k\.Form∈\{1,…,k−1\}m\\in\\\{1,\\dots,k\-1\\\}, the termR^m​m\\hat\{R\}\_\{mm\}is explicitly contained in the sum∑j=1k−1\\sum\_\{j=1\}^\{k\-1\}\. The coefficient forR^m​j\\hat\{R\}\_\{mj\}wherej≠mj\\neq misθm​\(aj/θj−1\)\\theta\_\{m\}\(a\_\{j\}/\\theta\_\{j\}\-1\)\. The coefficient forR^m​m\\hat\{R\}\_\{mm\}combines the first term and the summation term:θm\+θm​\(am/θm−1\)=am\\theta\_\{m\}\+\\theta\_\{m\}\(a\_\{m\}/\\theta\_\{m\}\-1\)=a\_\{m\}\. Thus, thejj\-th element of𝐜m\\mathbf\{c\}\_\{m\}is:

\(𝐜m\)j=\{θm​\(ajθj−1\)j≠mθm​\(amθm\)j=m\.\(\\mathbf\{c\}\_\{m\}\)\_\{j\}=\\begin\{cases\}\\theta\_\{m\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)&j\\neq m\\\\ \\theta\_\{m\}\\left\(\\frac\{a\_\{m\}\}\{\\theta\_\{m\}\}\\right\)&j=m\\end\{cases\}\.\(28\)Using the diagonal matrixQˇ=diag⁡\(1/θ1,…,1/θk−1\)\\check\{Q\}=\\operatorname\{diag\}\(1/\\theta\_\{1\},\\dots,1/\\theta\_\{k\-1\}\)and vector𝐝ˇm=𝟏−𝐞m\\check\{\\mathbf\{d\}\}\_\{m\}=\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}, we can write this compactly as:

𝐜m=θm​\(Qˇ​𝒂−𝐝ˇm\)\.\\mathbf\{c\}\_\{m\}=\\theta\_\{m\}\(\\check\{Q\}\\boldsymbol\{a\}\-\\check\{\\mathbf\{d\}\}\_\{m\}\)\.\(29\)
Case 2:m=km=k\.For classkk,R^k​k\\hat\{R\}\_\{kk\}is not included in𝐑ˇk\\check\{\\mathbf\{R\}\}\_\{k\}\. We invoke the symmetric loss property∑j=1kR^k​j=α\\sum\_\{j=1\}^\{k\}\\hat\{R\}\_\{kj\}=\\alpha\(constant\) to substituteR^k​k=α−∑j=1k−1R^k​j\\hat\{R\}\_\{kk\}=\\alpha\-\\sum\_\{j=1\}^\{k\-1\}\\hat\{R\}\_\{kj\}\. Substituting this intoTkT\_\{k\}:

Tk\\displaystyle T\_\{k\}=θk​\(α−∑j=1k−1R^k​j\)\+∑j=1k−1θk​\(ajθj−1\)​R^k​j\\displaystyle=\\theta\_\{k\}\\left\(\\alpha\-\\sum\_\{j=1\}^\{k\-1\}\\hat\{R\}\_\{kj\}\\right\)\+\\sum\_\{j=1\}^\{k\-1\}\\theta\_\{k\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)\\hat\{R\}\_\{kj\}\(30\)=const\+∑j=1k−1\[−θk\+θk​\(ajθj−1\)\]​R^k​j\\displaystyle=\\text\{const\}\+\\sum\_\{j=1\}^\{k\-1\}\\left\[\-\\theta\_\{k\}\+\\theta\_\{k\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)\\right\]\\hat\{R\}\_\{kj\}\(31\)=const\+∑j=1k−1θk​\(ajθj−2\)​R^k​j\.\\displaystyle=\\text\{const\}\+\\sum\_\{j=1\}^\{k\-1\}\\theta\_\{k\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-2\\right\)\\hat\{R\}\_\{kj\}\.\(32\)Here, the coefficient vector corresponds to𝐝ˇk=2​𝟏\\check\{\\mathbf\{d\}\}\_\{k\}=2\\mathbf\{1\}\. Thus:

𝐜k=θk​\(Qˇ​𝒂−2​𝟏\)=θk​\(Qˇ​𝒂−𝐝ˇk\)\.\\mathbf\{c\}\_\{k\}=\\theta\_\{k\}\(\\check\{Q\}\\boldsymbol\{a\}\-2\\mathbf\{1\}\)=\\theta\_\{k\}\(\\check\{Q\}\\boldsymbol\{a\}\-\\check\{\\mathbf\{d\}\}\_\{k\}\)\.\(33\)
Total Variance\.The variance of the estimator is the sum of variances ofTmT\_\{m\}:

Var⁡\[R^l​i​n𝒂\]\\displaystyle\\operatorname\{Var\}\\left\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\\right\]=∑m=1kVar⁡\[Tm\]=∑m=1k𝐜m⊤​\(1nm​Cˇm\)​𝐜m\\displaystyle=\\sum\_\{m=1\}^\{k\}\\operatorname\{Var\}\[T\_\{m\}\]=\\sum\_\{m=1\}^\{k\}\\mathbf\{c\}\_\{m\}^\{\\top\}\\left\(\\frac\{1\}\{n\_\{m\}\}\\check\{C\}\_\{m\}\\right\)\\mathbf\{c\}\_\{m\}\(34\)=∑m=1kθm2nm​\(Qˇ​𝒂−𝐝ˇm\)⊤​Cˇm​\(Qˇ​𝒂−𝐝ˇm\)\.\\displaystyle=\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(\\check\{Q\}\\boldsymbol\{a\}\-\\check\{\\mathbf\{d\}\}\_\{m\}\)^\{\\top\}\\check\{C\}\_\{m\}\(\\check\{Q\}\\boldsymbol\{a\}\-\\check\{\\mathbf\{d\}\}\_\{m\}\)\.\(35\)∎

###### Proof of Theorem[8](https://arxiv.org/html/2607.11947#Thmthm8)\.

First, we simplify the reduction term𝐛ˇT​Aˇ−1​𝐛ˇ\\check\{\\mathbf\{b\}\}^\{T\}\\check\{A\}^\{\-1\}\\check\{\\mathbf\{b\}\}\. SubstitutingAˇ−1=Qˇ−1​Sˇ−1​Qˇ−1\\check\{A\}^\{\-1\}=\\check\{Q\}^\{\-1\}\\check\{S\}^\{\-1\}\\check\{Q\}^\{\-1\}and𝐛ˇ=Qˇ​\(Sˇ​𝟏−𝐮ˇ\)\\check\{\\mathbf\{b\}\}=\\check\{Q\}\(\\check\{S\}\\mathbf\{1\}\-\\check\{\\mathbf\{u\}\}\):

𝐛ˇT​Aˇ−1​𝐛ˇ\\displaystyle\\check\{\\mathbf\{b\}\}^\{T\}\\check\{A\}^\{\-1\}\\check\{\\mathbf\{b\}\}=\(Sˇ​𝟏−𝐮ˇ\)T​Sˇ−1​\(Sˇ​𝟏−𝐮ˇ\)\\displaystyle=\(\\check\{S\}\\mathbf\{1\}\-\\check\{\\mathbf\{u\}\}\)^\{T\}\\check\{S\}^\{\-1\}\(\\check\{S\}\\mathbf\{1\}\-\\check\{\\mathbf\{u\}\}\)=\(𝟏T​Sˇ−𝐮ˇT\)​\(𝟏−Sˇ−1​𝐮ˇ\)\\displaystyle=\(\\mathbf\{1\}^\{T\}\\check\{S\}\-\\check\{\\mathbf\{u\}\}^\{T\}\)\(\\mathbf\{1\}\-\\check\{S\}^\{\-1\}\\check\{\\mathbf\{u\}\}\)=𝟏T​Sˇ​𝟏−2​𝟏T​𝐮ˇ\+𝐮ˇT​Sˇ−1​𝐮ˇ\.\\displaystyle=\\mathbf\{1\}^\{T\}\\check\{S\}\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\check\{\\mathbf\{u\}\}\+\\check\{\\mathbf\{u\}\}^\{T\}\\check\{S\}^\{\-1\}\\check\{\\mathbf\{u\}\}\.
Next, we expand the constant termcˇ\\check\{c\}\. Recalling𝐝ˇm=𝟏−𝐞m\\check\{\\mathbf\{d\}\}\_\{m\}=\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}form<km<kand𝐝ˇk=2​𝟏\\check\{\\mathbf\{d\}\}\_\{k\}=2\\mathbf\{1\}:

cˇ\\displaystyle\\check\{c\}=∑m=1k−1θm2nm​\(𝟏−𝐞m\)T​Cˇm​\(𝟏−𝐞m\)\+θk2nk​\(2​𝟏\)T​Cˇk​\(2​𝟏\)\\displaystyle=\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}\)^\{T\}\\check\{C\}\_\{m\}\(\\mathbf\{1\}\-\\mathbf\{e\}\_\{m\}\)\+\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\(2\\mathbf\{1\}\)^\{T\}\\check\{C\}\_\{k\}\(2\\mathbf\{1\}\)=∑m=1k−1θm2nm​\(𝟏T​Cˇm​𝟏−2​𝟏T​Cˇm​𝐞m\+\(Cˇm\)m​m\)\+4​θk2nk​𝟏T​Cˇk​𝟏\.\\displaystyle=\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\left\(\\mathbf\{1\}^\{T\}\\check\{C\}\_\{m\}\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\check\{C\}\_\{m\}\\mathbf\{e\}\_\{m\}\+\(\\check\{C\}\_\{m\}\)\_\{mm\}\\right\)\+4\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\mathbf\{1\}^\{T\}\\check\{C\}\_\{k\}\\mathbf\{1\}\.We regroup the terms usingSˇ=∑m=1k−1θm2nm​Cˇm\+θk2nk​Cˇk\\check\{S\}=\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\check\{C\}\_\{m\}\+\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\check\{C\}\_\{k\}:

- •Quadratic terms in𝟏\\mathbf\{1\}: 𝟏T​\(∑m=1k−1θm2nm​Cˇm\)​𝟏\+4​θk2nk​𝟏T​Cˇk​𝟏=𝟏T​\(Sˇ−θk2nk​Cˇk\)​𝟏\+4​θk2nk​𝟏T​Cˇk​𝟏=𝟏T​Sˇ​𝟏\+3​θk2nk​𝟏T​Cˇk​𝟏\.\\mathbf\{1\}^\{T\}\\left\(\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\check\{C\}\_\{m\}\\right\)\\mathbf\{1\}\+4\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\mathbf\{1\}^\{T\}\\check\{C\}\_\{k\}\\mathbf\{1\}=\\mathbf\{1\}^\{T\}\(\\check\{S\}\-\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\check\{C\}\_\{k\}\)\\mathbf\{1\}\+4\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\mathbf\{1\}^\{T\}\\check\{C\}\_\{k\}\\mathbf\{1\}=\\mathbf\{1\}^\{T\}\\check\{S\}\\mathbf\{1\}\+3\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\mathbf\{1\}^\{T\}\\check\{C\}\_\{k\}\\mathbf\{1\}\.
- •Linear terms in𝟏\\mathbf\{1\}: −2​𝟏T​∑m=1k−1θm2nm​Cˇm​𝐞m=−2​𝟏T​\(𝐮ˇ\+θk2nk​Cˇk​𝟏\)=−2​𝟏T​𝐮ˇ−2​θk2nk​𝟏T​Cˇk​𝟏\.\-2\\mathbf\{1\}^\{T\}\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\\check\{C\}\_\{m\}\\mathbf\{e\}\_\{m\}=\-2\\mathbf\{1\}^\{T\}\(\\check\{\\mathbf\{u\}\}\+\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\check\{C\}\_\{k\}\\mathbf\{1\}\)=\-2\\mathbf\{1\}^\{T\}\\check\{\\mathbf\{u\}\}\-2\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\mathbf\{1\}^\{T\}\\check\{C\}\_\{k\}\\mathbf\{1\}\.
- •Remaining diagonal terms:∑m=1k−1θm2nm​\(Cˇm\)m​m\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(\\check\{C\}\_\{m\}\)\_\{mm\}\.

Thus:

cˇ\\displaystyle\\check\{c\}=𝟏T​Sˇ​𝟏−2​𝟏T​𝐮ˇ\+\(∑m=1k−1θm2nm​\(Cˇm\)m​m\+θk2nk​𝟏T​Cˇk​𝟏\)\\displaystyle=\\mathbf\{1\}^\{T\}\\check\{S\}\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\check\{\\mathbf\{u\}\}\+\\left\(\\sum\_\{m=1\}^\{k\-1\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(\\check\{C\}\_\{m\}\)\_\{mm\}\+\\frac\{\\theta\_\{k\}^\{2\}\}\{n\_\{k\}\}\\mathbf\{1\}^\{T\}\\check\{C\}\_\{k\}\\mathbf\{1\}\\right\)=𝟏T​Sˇ​𝟏−2​𝟏T​𝐮ˇ\+∑m=1kθm2nm​\(Cm\)m​m\\displaystyle=\\mathbf\{1\}^\{T\}\\check\{S\}\\mathbf\{1\}\-2\\mathbf\{1\}^\{T\}\\check\{\\mathbf\{u\}\}\+\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}^\{2\}\}\{n\_\{m\}\}\(C\_\{m\}\)\_\{mm\}Subtracting the reduction term fromcˇ\\check\{c\}cancels the𝟏T​Sˇ​𝟏\\mathbf\{1\}^\{T\}\\check\{S\}\\mathbf\{1\}and linear terms, yielding the result\. ∎

###### Proof of Theorem[9](https://arxiv.org/html/2607.11947#Thmthm9)\.

First, we derive the explicit forms of the risks under the symmetric loss assumption\. Recall the symmetric condition impliesR12=α−R11R\_\{12\}=\\alpha\-R\_\{11\}andR21=α−R22R\_\{21\}=\\alpha\-R\_\{22\}\. Substituting these into the definitions of PU and NU risks, we obtain:

RPU​\(g\)\\displaystyle R\_\{\\text\{PU\}\}\(g\)=θ1​R11​\(g\)−θ1​\(α−R11​\(g\)\)\+RU​2​\(g\)\\displaystyle=\\theta\_\{1\}R\_\{11\}\(g\)\-\\theta\_\{1\}\(\\alpha\-R\_\{11\}\(g\)\)\+R\_\{U2\}\(g\)=2​θ1​R11​\(g\)\+RU​2​\(g\)−θ1​α,\\displaystyle=2\\theta\_\{1\}R\_\{11\}\(g\)\+R\_\{U2\}\(g\)\-\\theta\_\{1\}\\alpha,\(36\)RNU​\(g\)\\displaystyle R\_\{\\text\{NU\}\}\(g\)=θ2​R22​\(g\)−θ2​\(α−R22​\(g\)\)\+RU​1​\(g\)\\displaystyle=\\theta\_\{2\}R\_\{22\}\(g\)\-\\theta\_\{2\}\(\\alpha\-R\_\{22\}\(g\)\)\+R\_\{U1\}\(g\)=2​θ2​R22​\(g\)\+RU​1​\(g\)−θ2​α\.\\displaystyle=2\\theta\_\{2\}R\_\{22\}\(g\)\+R\_\{U1\}\(g\)\-\\theta\_\{2\}\\alpha\.\(37\)
Next, we consider the PNPU estimatorRPNPUη=\(1−η\)​RPN\+η​RPUR\_\{\\text\{PNPU\}\}^\{\\eta\}=\(1\-\\eta\)R\_\{\\text\{PN\}\}\+\\eta R\_\{\\text\{PU\}\}\. Substituting \([36](https://arxiv.org/html/2607.11947#A1.E36)\):

RPNPUη​\(g\)\\displaystyle R\_\{\\text\{PNPU\}\}^\{\\eta\}\(g\)=\(1−η\)​\(θ1​R11\+θ2​R22\)\+η​\(2​θ1​R11\+RU​2−θ1​α\)\\displaystyle=\(1\-\\eta\)\(\\theta\_\{1\}R\_\{11\}\+\\theta\_\{2\}R\_\{22\}\)\+\\eta\(2\\theta\_\{1\}R\_\{11\}\+R\_\{U2\}\-\\theta\_\{1\}\\alpha\)=θ1​\(1\+η\)​R11\+θ2​\(1−η\)​R22\+η​RU​2−η​θ1​α\.\\displaystyle=\\theta\_\{1\}\(1\+\\eta\)R\_\{11\}\+\\theta\_\{2\}\(1\-\\eta\)R\_\{22\}\+\\eta R\_\{U2\}\-\\eta\\theta\_\{1\}\\alpha\.\(38\)Similarly, for the PNNU estimatorRPNNUη=\(1−η\)​RPN\+η​RNUR\_\{\\text\{PNNU\}\}^\{\\eta\}=\(1\-\\eta\)R\_\{\\text\{PN\}\}\+\\eta R\_\{\\text\{NU\}\}, using \([37](https://arxiv.org/html/2607.11947#A1.E37)\):

RPNNUη​\(g\)\\displaystyle R\_\{\\text\{PNNU\}\}^\{\\eta\}\(g\)=\(1−η\)​\(θ1​R11\+θ2​R22\)\+η​\(2​θ2​R22\+RU​1−θ2​α\)\\displaystyle=\(1\-\\eta\)\(\\theta\_\{1\}R\_\{11\}\+\\theta\_\{2\}R\_\{22\}\)\+\\eta\(2\\theta\_\{2\}R\_\{22\}\+R\_\{U1\}\-\\theta\_\{2\}\\alpha\)=θ1​\(1−η\)​R11\+θ2​\(1\+η\)​R22\+η​RU​1−η​θ2​α\.\\displaystyle=\\theta\_\{1\}\(1\-\\eta\)R\_\{11\}\+\\theta\_\{2\}\(1\+\\eta\)R\_\{22\}\+\\eta R\_\{U1\}\-\\eta\\theta\_\{2\}\\alpha\.\(39\)
Now, we examine the general linear estimator setSl​i​nS\_\{lin\}fork=2k=2with symmetric loss\. From Theorem[6](https://arxiv.org/html/2607.11947#Thmthm6), the estimator is parametrized by a scalara1a\_\{1\}:

Rl​i​na1​\(g\)=a1​R11\+θ2​R22\+θ2​\(a1θ1−1\)​R21−\(a1θ1−1\)​RU​1\.R\_\{lin\}^\{a\_\{1\}\}\(g\)=a\_\{1\}R\_\{11\}\+\\theta\_\{2\}R\_\{22\}\+\\theta\_\{2\}\\left\(\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\-1\\right\)R\_\{21\}\-\\left\(\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\-1\\right\)R\_\{U1\}\.\(40\)Using the identityR21=α−R22R\_\{21\}=\\alpha\-R\_\{22\}andRU​1\+RU​2=αR\_\{U1\}\+R\_\{U2\}=\\alphato align terms with \([38](https://arxiv.org/html/2607.11947#A1.E38)\), we rewriteRl​i​na1R\_\{lin\}^\{a\_\{1\}\}:

Rl​i​na1​\(g\)\\displaystyle R\_\{lin\}^\{a\_\{1\}\}\(g\)=a1​R11\+θ2​R22\+θ2​\(a1θ1−1\)​\(α−R22\)−\(a1θ1−1\)​\(α−RU​2\)\\displaystyle=a\_\{1\}R\_\{11\}\+\\theta\_\{2\}R\_\{22\}\+\\theta\_\{2\}\\left\(\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\-1\\right\)\(\\alpha\-R\_\{22\}\)\-\\left\(\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\-1\\right\)\(\\alpha\-R\_\{U2\}\)=a1​R11\+\[θ2−θ2​\(a1θ1−1\)\]​R22\+\(a1θ1−1\)​RU​2\+const\.\\displaystyle=a\_\{1\}R\_\{11\}\+\\left\[\\theta\_\{2\}\-\\theta\_\{2\}\\left\(\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\-1\\right\)\\right\]R\_\{22\}\+\\left\(\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\-1\\right\)R\_\{U2\}\+\\text\{const\.\}=a1​R11\+θ2​\(2−a1θ1\)​R22\+\(a1θ1−1\)​RU​2\+const\.\\displaystyle=a\_\{1\}R\_\{11\}\+\\theta\_\{2\}\\left\(2\-\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\\right\)R\_\{22\}\+\\left\(\\frac\{a\_\{1\}\}\{\\theta\_\{1\}\}\-1\\right\)R\_\{U2\}\+\\text\{const\.\}Comparing this with the PNPU form in \([38](https://arxiv.org/html/2607.11947#A1.E38)\), we see that they match if we seta1=θ1​\(1\+η\)a\_\{1\}=\\theta\_\{1\}\(1\+\\eta\)\. Specifically:

- •Coefficient ofR11R\_\{11\}:a1⇔θ1​\(1\+η\)a\_\{1\}\\iff\\theta\_\{1\}\(1\+\\eta\)
- •Coefficient ofR22R\_\{22\}:θ2​\(2−\(1\+η\)\)=θ2​\(1−η\)\\theta\_\{2\}\(2\-\(1\+\\eta\)\)=\\theta\_\{2\}\(1\-\\eta\)
- •Coefficient ofRU​2R\_\{U2\}:\(1\+η\)−1=η\(1\+\\eta\)\-1=\\eta

Since this mapping is bijective forη,a1∈ℝ\\eta,a\_\{1\}\\in\\mathbb\{R\}, we haveSl​i​n=SPNPUS\_\{lin\}=S\_\{\\text\{PNPU\}\}\.

Similarly, comparingRl​i​na1R\_\{lin\}^\{a\_\{1\}\}with PNNU form in \([39](https://arxiv.org/html/2607.11947#A1.E39)\) by settinga1=θ1​\(1−η\)a\_\{1\}=\\theta\_\{1\}\(1\-\\eta\)shows thatSl​i​n=SPNNUS\_\{lin\}=S\_\{\\text\{PNNU\}\}\. Thus, all three sets are equivalent\. ∎

###### Proof of Theorem[10](https://arxiv.org/html/2607.11947#Thmthm10)\.

We consider a hypothesis class𝒢\\mathcal\{G\}and its minimalν\\nu\-coverCνC\_\{\\nu\}with respect to theL∞L\_\{\\infty\}norm\. By definition,\|Cν\|=𝒩\(𝒢,ν,∥⋅∥∞\)\|C\_\{\\nu\}\|=\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\), and for anyg∈𝒢g\\in\\mathcal\{G\}, there exists ag′∈Cνg^\{\\prime\}\\in C\_\{\\nu\}such that‖g−g′‖∞≤ν\\\|g\-g^\{\\prime\}\\\|\_\{\\infty\}\\leq\\nu\.

Letg^\\hat\{g\}be the empirical risk minimizer andg∗g^\{\*\}be the true risk minimizer\. AsnU→∞n\_\{U\}\\to\\infty, the variance of the unlabeled risk components vanishes, so we focus on the empirical estimates derived from the labeled datasets\.

1\. Decomposition of Excess Risk and Covering BoundFirst, we relate the excess risk to the maximum estimation error over𝒢\\mathcal\{G\}:

R​\(g^\)−R​\(g∗\)\\displaystyle R\(\\hat\{g\}\)\-R\(g^\{\*\}\)=R​\(g^\)−R^l​i​n𝒂​\(g^\)\+R^l​i​n𝒂​\(g^\)−R^l​i​n𝒂​\(g∗\)\+R^l​i​n𝒂​\(g∗\)−R​\(g∗\)\\displaystyle=R\(\\hat\{g\}\)\-\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(\\hat\{g\}\)\+\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(\\hat\{g\}\)\-\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\*\}\)\+\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\*\}\)\-R\(g^\{\*\}\)≤R​\(g^\)−R^l​i​n𝒂​\(g^\)\+R^l​i​n𝒂​\(g∗\)−R​\(g∗\)\(since​R^l​i​n𝒂​\(g^\)≤R^l​i​n𝒂​\(g∗\)\)\\displaystyle\\leq R\(\\hat\{g\}\)\-\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(\\hat\{g\}\)\+\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\*\}\)\-R\(g^\{\*\}\)\\quad\(\\text\{since \}\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(\\hat\{g\}\)\\leq\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\*\}\)\)≤2​supg∈𝒢\|R^l​i​n𝒂​\(g\)−R​\(g\)\|\.\\displaystyle\\leq 2\\sup\_\{g\\in\\mathcal\{G\}\}\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)\-R\(g\)\|\.\(41\)
Using theν\\nu\-coverCνC\_\{\\nu\}, we can bound the deviation for anyg∈𝒢g\\in\\mathcal\{G\}by mapping it to its closest elementg′∈Cνg^\{\\prime\}\\in C\_\{\\nu\}\. Because the loss function isLL\-Lipschitz continuous, we have\|l​\(g​\(x\),j\)−l​\(g′​\(x\),j\)\|≤L​‖g​\(x\)−g′​\(x\)‖∞≤L​ν\|l\(g\(x\),j\)\-l\(g^\{\\prime\}\(x\),j\)\|\\leq L\\\|g\(x\)\-g^\{\\prime\}\(x\)\\\|\_\{\\infty\}\\leq L\\nu\.

For the empirical risk estimator, the difference is bounded by:

\|R^l​i​n𝒂​\(g\)−R^l​i​n𝒂​\(g′\)\|\\displaystyle\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)\-\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\|≤∑m=1kθmnm​∑q=1nm\(\|l​\(g​\(xqm\),m\)−l​\(g′​\(xqm\),m\)\|\+∑j=1k\|ajθj−1\|​\|l​\(g​\(xqm\),j\)−l​\(g′​\(xqm\),j\)\|\)\\displaystyle\\leq\\sum\_\{m=1\}^\{k\}\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\sum\_\{q=1\}^\{n\_\{m\}\}\\left\(\|l\(g\(x\_\{q\}^\{m\}\),m\)\-l\(g^\{\\prime\}\(x\_\{q\}^\{m\}\),m\)\|\+\\sum\_\{j=1\}^\{k\}\\left\|\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\|\|l\(g\(x\_\{q\}^\{m\}\),j\)\-l\(g^\{\\prime\}\(x\_\{q\}^\{m\}\),j\)\|\\right\)≤∑m=1kθm​\(L​ν\+k​c𝒂​L​ν\)=L​ν​\(1\+k​c𝒂\)=L𝒂​ν\.\\displaystyle\\leq\\sum\_\{m=1\}^\{k\}\\theta\_\{m\}\\left\(L\\nu\+kc\_\{\\boldsymbol\{a\}\}L\\nu\\right\)=L\\nu\(1\+kc\_\{\\boldsymbol\{a\}\}\)=L\_\{\\boldsymbol\{a\}\}\\nu\.
Similarly, for the true risk,\|R​\(g\)−R​\(g′\)\|≤𝔼​\[\|l​\(g​\(x\),y\)−l​\(g′​\(x\),y\)\|\]≤L​ν≤L𝒂​ν\|R\(g\)\-R\(g^\{\\prime\}\)\|\\leq\\mathbb\{E\}\[\|l\(g\(x\),y\)\-l\(g^\{\\prime\}\(x\),y\)\|\]\\leq L\\nu\\leq L\_\{\\boldsymbol\{a\}\}\\nu\. Thus, using the triangle inequality for any fixedg∈𝒢g\\in\\mathcal\{G\}and its closest elementg′∈Cνg^\{\\prime\}\\in C\_\{\\nu\}\(where‖g−g′‖∞≤ν\\\|g\-g^\{\\prime\}\\\|\_\{\\infty\}\\leq\\nu\), we have:

\|R^l​i​n𝒂​\(g\)−R​\(g\)\|\\displaystyle\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)\-R\(g\)\|≤\|R^l​i​n𝒂​\(g\)−R^l​i​n𝒂​\(g′\)\|\+\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\+\|R​\(g′\)−R​\(g\)\|\\displaystyle\\leq\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)\-\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\|\+\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\+\|R\(g^\{\\prime\}\)\-R\(g\)\|≤2​L𝒂​ν\+\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\\displaystyle\\leq 2L\_\{\\boldsymbol\{a\}\}\\nu\+\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|≤2​L𝒂​ν\+maxg′′∈Cν⁡\|R^l​i​n𝒂​\(g′′\)−R​\(g′′\)\|\.\\displaystyle\\leq 2L\_\{\\boldsymbol\{a\}\}\\nu\+\\max\_\{g^\{\\prime\\prime\}\\in C\_\{\\nu\}\}\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\\prime\}\)\-R\(g^\{\\prime\\prime\}\)\|\.\(42\)
Since the right\-hand side is independent of the choice ofgg, we can now take the supremum over allg∈𝒢g\\in\\mathcal\{G\}on the left\-hand side:

supg∈𝒢\|R^l​i​n𝒂​\(g\)−R​\(g\)\|≤maxg′∈Cν⁡\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\+2​L𝒂​ν\.\\sup\_\{g\\in\\mathcal\{G\}\}\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g\)\-R\(g\)\|\\leq\\max\_\{g^\{\\prime\}\\in C\_\{\\nu\}\}\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\+2L\_\{\\boldsymbol\{a\}\}\\nu\.\(43\)
2\. Bernstein’s Inequality on the Finite CoverWe now bound the estimation error for the finite set of hypotheses inCνC\_\{\\nu\}\. For any fixedg′∈Cνg^\{\\prime\}\\in C\_\{\\nu\}, the estimatorR^l​i​n𝒂​\(g′\)\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)is a sum of independent random variables:

R^l​i​na​\(g′\)=∑m=1k∑q=1nmθmnm​\(l​\(g′​\(xqm\),m\)\+∑j=1k\(ajθj−1\)​l​\(g′​\(xqm\),j\)\)⏟Zqm​\(g′\)\+const\.\\hat\{R\}^\{a\}\_\{lin\}\(g^\{\\prime\}\)=\\sum\_\{m=1\}^\{k\}\\sum\_\{q=1\}^\{n\_\{m\}\}\\underbrace\{\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\left\(l\(g^\{\\prime\}\(x\_\{q\}^\{m\}\),m\)\+\\sum\_\{j=1\}^\{k\}\\left\(\\frac\{a\_\{j\}\}\{\\theta\_\{j\}\}\-1\\right\)l\(g^\{\\prime\}\(x\_\{q\}^\{m\}\),j\)\\right\)\}\_\{Z\_\{q\}^\{m\}\(g^\{\\prime\}\)\}\+\\text\{const\}\.\(44\)Since0≤l​\(⋅,⋅\)≤cl0\\leq l\(\\cdot,\\cdot\)\\leq c\_\{l\}, the variablesZqm​\(g′\)Z\_\{q\}^\{m\}\(g^\{\\prime\}\)are bounded bymaxm∈\[k\]⁡\(θmnm\)​k​cl​\(1\+c𝒂\)=maxm∈\[k\]⁡\(θmnm\)​B𝒂\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)kc\_\{l\}\(1\+c\_\{\\boldsymbol\{a\}\}\)=\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)B\_\{\\boldsymbol\{a\}\}\.

First, for any fixedg′∈Cνg^\{\\prime\}\\in C\_\{\\nu\}, applying Bernstein’s inequality yields:

P​\(\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\>ϵ\)≤2​exp⁡\(−ϵ22​Var⁡\[R^l​i​n𝒂​\(g′\)\]\+23​maxm∈\[k\]⁡\(θmnm\)​B𝒂​ϵ\)\.P\\left\(\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\>\\epsilon\\right\)\\leq 2\\exp\\left\(\\frac\{\-\\epsilon^\{2\}\}\{2\\operatorname\{Var\}\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\]\+\\frac\{2\}\{3\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)B\_\{\\boldsymbol\{a\}\}\\epsilon\}\\right\)\.\(45\)SinceVar⁡\[R^l​i​n𝒂​\(g′\)\]≤σmax2​\(𝒂,ν\)\\operatorname\{Var\}\[\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\]\\leq\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)for allg′∈Cνg^\{\\prime\}\\in C\_\{\\nu\}, we can upper bound this probability by:

P​\(\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\>ϵ\)≤2​exp⁡\(−ϵ22​σmax2​\(𝒂,ν\)\+23​maxm∈\[k\]⁡\(θmnm\)​B𝒂​ϵ\)\.P\\left\(\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\>\\epsilon\\right\)\\leq 2\\exp\\left\(\\frac\{\-\\epsilon^\{2\}\}\{2\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)\+\\frac\{2\}\{3\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)B\_\{\\boldsymbol\{a\}\}\\epsilon\}\\right\)\.\(46\)
Next, applying the union bound over all\|Cν\|=𝒩\(𝒢,ν,∥⋅∥∞\)\|C\_\{\\nu\}\|=\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)elements, we obtain:

P​\(maxg′∈Cν⁡\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\>ϵ\)\\displaystyle P\\left\(\\max\_\{g^\{\\prime\}\\in C\_\{\\nu\}\}\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\>\\epsilon\\right\)=P​\(⋃g′∈Cν\{\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\>ϵ\}\)\\displaystyle=P\\left\(\\bigcup\_\{g^\{\\prime\}\\in C\_\{\\nu\}\}\\left\\\{\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\>\\epsilon\\right\\\}\\right\)≤∑g′∈CνP​\(\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\>ϵ\)\\displaystyle\\leq\\sum\_\{g^\{\\prime\}\\in C\_\{\\nu\}\}P\\left\(\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\>\\epsilon\\right\)≤2𝒩\(𝒢,ν,∥⋅∥∞\)exp\(−ϵ22​σmax2​\(𝒂,ν\)\+23​maxm∈\[k\]⁡\(θmnm\)​B𝒂​ϵ\)\.\\displaystyle\\leq 2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\\exp\\left\(\\frac\{\-\\epsilon^\{2\}\}\{2\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)\+\\frac\{2\}\{3\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)B\_\{\\boldsymbol\{a\}\}\\epsilon\}\\right\)\.\(47\)
Equating the right\-hand side of the union bound toδ\\delta, we find the boundϵ\\epsilonthat holds with probability at least1−δ1\-\\delta:

ϵ22​σmax2​\(𝒂,ν\)\+23​maxm∈\[k\]⁡\(θmnm\)​B𝒂​ϵ=ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\.\\frac\{\\epsilon^\{2\}\}\{2\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)\+\\frac\{2\}\{3\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)B\_\{\\boldsymbol\{a\}\}\\epsilon\}=\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)\.
Rearranging terms yields a quadratic equation forϵ\\epsilon:

ϵ2−\(23​maxm∈\[k\]⁡\(θmnm\)​B𝒂​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\)⏟b​ϵ−\(2​σmax2​\(𝒂,ν\)​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\)⏟c=0\.\\epsilon^\{2\}\-\\underbrace\{\\left\(\\frac\{2\}\{3\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)B\_\{\\boldsymbol\{a\}\}\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)\\right\)\}\_\{b\}\\epsilon\-\\underbrace\{\\left\(2\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)\\right\)\}\_\{c\}=0\.
Using the quadratic formula, the positive root isϵ=b\+b2\+4​c2\\epsilon=\\frac\{b\+\\sqrt\{b^\{2\}\+4c\}\}\{2\}\. By the subadditivity of the square root function \(x\+y≤x\+y\\sqrt\{x\+y\}\\leq\\sqrt\{x\}\+\\sqrt\{y\}forx,y≥0x,y\\geq 0\), we can simplify this as:

ϵ≤b\+b\+2​c2=b\+c\.\\epsilon\\leq\\frac\{b\+b\+2\\sqrt\{c\}\}\{2\}=b\+\\sqrt\{c\}\.
Substituting the definitions ofbbandccback into the inequality, we obtain that with probability at least1−δ1\-\\delta:

maxg′∈Cν⁡\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|≤2​σmax2​\(𝒂,ν\)​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\+23​B𝒂​maxm∈\[k\]⁡\(θmnm\)​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\.\\max\_\{g^\{\\prime\}\\in C\_\{\\nu\}\}\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|\\leq\\sqrt\{2\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)\}\+\\frac\{2\}\{3\}B\_\{\\boldsymbol\{a\}\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)\.
3\. Final PAC Bound DerivationCombining this result with the decomposition from Step 1 and Eq\. \([43](https://arxiv.org/html/2607.11947#A1.E43)\), we bound the total excess risk:

R​\(g^\)−R​\(g∗\)\\displaystyle R\(\\hat\{g\}\)\-R\(g^\{\*\}\)≤4​L𝒂​ν\+2​maxg′∈Cν⁡\|R^l​i​n𝒂​\(g′\)−R​\(g′\)\|\\displaystyle\\leq 4L\_\{\\boldsymbol\{a\}\}\\nu\+2\\max\_\{g^\{\\prime\}\\in C\_\{\\nu\}\}\|\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}\}\(g^\{\\prime\}\)\-R\(g^\{\\prime\}\)\|≤4​L𝒂​ν\+8​σmax2​\(𝒂,ν\)​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\+43​B𝒂​maxm∈\[k\]⁡\(θmnm\)​ln⁡\(2𝒩\(𝒢,ν,∥⋅∥∞\)δ\)\\displaystyle\\leq 4L\_\{\\boldsymbol\{a\}\}\\nu\+\\sqrt\{8\\sigma\_\{\\max\}^\{2\}\(\\boldsymbol\{a\},\\nu\)\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)\}\+\\frac\{4\}\{3\}B\_\{\\boldsymbol\{a\}\}\\max\_\{m\\in\[k\]\}\\left\(\\frac\{\\theta\_\{m\}\}\{n\_\{m\}\}\\right\)\\ln\\left\(\\frac\{2\\mathcal\{N\}\(\\mathcal\{G\},\\nu,\\\|\\cdot\\\|\_\{\\infty\}\)\}\{\\delta\}\\right\)This completes the proof\. ∎

## Appendix BVariance comparison results for multiclass setting

We present the variance comparison results for the multiclass setting\. The procedure is analogous to the binary case described in Section[6\.1](https://arxiv.org/html/2607.11947#S6.SS1)\. Since PNU learning is limited to binary classification, we compare only the supervised risk estimatorR^​\(g\)\\hat\{R\}\(g\)and the proposed linear risk estimatorR^l​i​n𝒂∗​\(g\)\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}\(g\)\.

##### Datasets\.

We use two multiclass datasets from the UCI Machine Learning Repository: Covertype and Dry Beans\. For each dataset, we use 20% of the data for training and 80% as a held\-out pool for evaluation\.

##### Model and training\.

We train a two\-layer neural network with hidden dimension 256 by minimizing the cross\-entropy loss withni=10n\_\{i\}=10labeled samples per class via the Adam optimizer \(learning rate10−310^\{\-3\}, weight decay10−410^\{\-4\}\), with early stopping on validation accuracy\.

##### Evaluation loss\.

We use the cross\-entropy \(CE\) lossl​\(g​\(x\),j\)=−log⁡softmax​\(g​\(x\)\)jl\(g\(x\),j\)=\-\\log\\mathrm\{softmax\}\(g\(x\)\)\_\{j\}for the variance comparison\.

##### Evaluation protocol\.

With the trained classifierggfixed, we evaluate the variance of each risk estimator by repeatedly sampling from the held\-out data\. The labeled sample sizes for risk estimation are fixed atni=5n\_\{i\}=5for alli∈\[k\]i\\in\[k\], and we varynU∈\{100,200,500,1000,2000\}n\_\{U\}\\in\\\{100,200,500,1000,2000\\\}\. We consider two class prior settings: \(1\)*uniform*, where𝜽=\(1/7,…,1/7\)\\boldsymbol\{\\theta\}=\(1/7,\\dots,1/7\), and \(2\)*skewed*, where𝜽=\[57/140,34/140,21/140,13/140,7/140,5/140,3/140\]≈\(0\.41,0\.24,0\.15,0\.09,0\.05,0\.04,0\.02\)\\boldsymbol\{\\theta\}=\[57/140,34/140,21/140,13/140,7/140,5/140,3/140\]\\approx\(0\.41,\\;0\.24,\\;0\.15,\\;0\.09,\\;0\.05,\\;0\.04,\\;0\.02\)\. The optimal parameter𝒂∗\\boldsymbol\{a\}^\{\*\}is computed assumingnU→∞n\_\{U\}\\to\\inftyusing the covariance matrices estimated from the all evaluation data\. For each condition, we conduct5,0005\{,\}000independent trials to estimate the variance\.

![Refer to caption](https://arxiv.org/html/2607.11947v1/exp/fig_var_compare_cov_ce.png)\(a\)Covertype \(CE loss\)
![Refer to caption](https://arxiv.org/html/2607.11947v1/exp/fig_var_compare_drybean_ce.png)\(b\)Dry Beans \(CE loss\)

Figure 2:Variance ratio \(R^l​i​n𝒂∗\\hat\{R\}\_\{lin\}^\{\\boldsymbol\{a\}^\{\*\}\}/R^\\hat\{R\}\) as a function of the unlabeled sample sizenUn\_\{U\}for uniform and skewed class priors \(k=7k=7\)\. The red dashed line indicates the supervised baseline \(ratio=1\\mathrm\{ratio\}=1\)\.As the number of unlabeled samplesnUn\_\{U\}increases, the variance ratio decreases\. The proposed method achieves greater variance reduction under the skewed class prior, consistent with Theorem[4](https://arxiv.org/html/2607.11947#Thmthm4)\.

## Appendix CSSL Experimental details

We provide full details omitted from the main text for the SSL experiments in Section[6\.2](https://arxiv.org/html/2607.11947#S6.SS2)\.

##### Validation set\.

For all settings, the validation set is independently sampled from the original dataset\.

##### Labeled data configurations for multiclass tasks\.

The per\-class labeled sample counts for each regime are as follows\.

*7\-class tasks*\(Covertype, Shuttle, Dry Beans\):

- •Balanced: 10, 20, or 50 per class \(totals: 70, 140, 350\)\.
- •Mild imbalance:\[33,26,23,19,16,13,10\]\[33,26,23,19,16,13,10\]\(total 140\) and\[81,65,57,49,41,33,24\]\[81,65,57,49,41,33,24\]\(total 350\)\.
- •Severe imbalance:\[57,34,21,13,7,5,3\]\[57,34,21,13,7,5,3\]\(total 140\) and\[143,86,52,32,19,11,7\]\[143,86,52,32,19,11,7\]\(total 350\)\.

*10\-class tasks*\(MNIST\):

- •Balanced: 20, 50, or 150 per class \(totals: 200, 500, 1500\)\.
- •Mild imbalance:\[102,82,71,61,51,41,31,26,20,15\]\[102,82,71,61,51,41,31,26,20,15\]\(total 500\) and\[306,245,214,184,153,122,92,77,61,46\]\[306,245,214,184,153,122,92,77,61,46\]\(total 1500\)\.
- •Severe imbalance:\[200,120,72,44,26,16,10,6,4,2\]\[200,120,72,44,26,16,10,6,4,2\]\(total 500\) and\[600,360,216,132,78,48,30,18,12,6\]\[600,360,216,132,78,48,30,18,12,6\]\(total 1500\)\.

For all multiclass tasks,nU=5,000n\_\{U\}=5\{,\}000\.

##### Model architectures\.

*MLP \(tabular\):*We use an MLP with two hidden layers for all tabular datasets, using ReLU activations and a dropout rate of0\.20\.2\. For the Adult, Banknote, Breast Cancer, and Credit Default datasets, we use hidden layer dimensions of\[256,256\]\[256,256\]\. For Covertype, we use\[512,512\]\[512,512\], and for Shuttle and Dry Beans, we use\[512,256\]\[512,256\]\.

*CNN \(image, LeNet\-like\):*Here, letConv​\(ci​n,co​u​t,k,pad\)\\text\{Conv\}\(c\_\{in\},c\_\{out\},k,\\text\{pad\}\)denote a 2D convolutional layer withci​nc\_\{in\}input channels,co​u​tc\_\{out\}output channels, kernel sizek×kk\\times k, and the specified padding\. LetMaxPool​\(k\)\\text\{MaxPool\}\(k\)denote a max pooling layer with kernel sizek×kk\\times k\. LetFC​\(di​n,do​u​t\)\\text\{FC\}\(d\_\{in\},d\_\{out\}\)denote a fully connected layer with input dimensiondi​nd\_\{in\}and output dimensiondo​u​td\_\{out\}\. For MNIST, the architecture isConv​\(1,32,3,pad=1\)\\text\{Conv\}\(1,32,3,\\text\{pad\}\{=\}1\)→\\toReLU→\\toMaxPool​\(2\)\\text\{MaxPool\}\(2\)→\\toConv​\(32,64,3,pad=1\)\\text\{Conv\}\(32,64,3,\\text\{pad\}\{=\}1\)→\\toReLU→\\toMaxPool​\(2\)\\text\{MaxPool\}\(2\)→\\toFC​\(64×7×7,128\)\\text\{FC\}\(64\{\\times\}7\{\\times\}7,128\)→\\toReLU→\\toFC​\(128,K\)\\text\{FC\}\(128,K\)\. For CIFAR\-10, the architecture isConv​\(3,64,3,pad=1\)\\text\{Conv\}\(3,64,3,\\text\{pad\}\{=\}1\)→\\toReLU→\\toMaxPool​\(2\)\\text\{MaxPool\}\(2\)→\\toConv​\(64,128,3,pad=1\)\\text\{Conv\}\(64,128,3,\\text\{pad\}\{=\}1\)→\\toReLU→\\toMaxPool​\(2\)\\text\{MaxPool\}\(2\)→\\toFC​\(128×8×8,256\)\\text\{FC\}\(128\{\\times\}8\{\\times\}8,256\)→\\toReLU→\\toFC​\(256,K\)\\text\{FC\}\(256,K\)\.

##### Training protocol\.

All models are trained with the Adam optimizer \(learning rate=10−3\\text\{learning rate\}=10^\{\-3\}, weight decay10−410^\{\-4\}\) for up to 200 epochs\. Batch sizes are 64 for labeled data and 256 for unlabeled data\. Early stopping is based on validation accuracy with patience 20 epochs and minimum improvement threshold10−410^\{\-4\}\.

##### Method\-specific settings\.

*PNU*\(binary only\): The mixing parameterη\\etais computed asη=\(ψ2−ψ1\)/\(ψ1\+ψ2\)\\eta=\(\\psi\_\{2\}\-\\psi\_\{1\}\)/\(\\psi\_\{1\}\+\\psi\_\{2\}\)whereψm=θm2/nm\\psi\_\{m\}=\\theta\_\{m\}^\{2\}/n\_\{m\}, following the equal variance assumption\[sakai17semi\]\. Non\-negative risk correction \(Δjn​n\\Delta\_\{j\}^\{nn\}\) is applied\.

*Ours \(Iter\):*Training begins with a2020\-epoch warm\-up period utilizing standard supervised risk prior to joint optimization\. The covariance matrices are estimated on the validation split with diagonal shrinkageΣ^m←\(1−α\)​Σ^m\+α​diag​\(Σ^m\)\\hat\{\\Sigma\}\_\{m\}\\leftarrow\(1\-\\alpha\)\\hat\{\\Sigma\}\_\{m\}\+\\alpha\\,\\mathrm\{diag\}\(\\hat\{\\Sigma\}\_\{m\}\)\(α=0\.5\\alpha=0\.5\), and Tikhonov regularizationλ=10−4\\lambda=10^\{\-4\}is added when solving the linear system for the optimal𝒂\\boldsymbol\{a\}\. Non\-negative risk correction \(Δjn​n\\Delta\_\{j\}^\{nn\}\) is applied\.

*Ours \(EC\):*The closed\-form parameteraj=θj​\(1−wj/W\)a\_\{j\}=\\theta\_\{j\}\(1\-w\_\{j\}/W\)withwj=θj2/njw\_\{j\}=\\theta\_\{j\}^\{2\}/n\_\{j\}andW=∑mwmW=\\sum\_\{m\}w\_\{m\}is used, requiring no validation data for parameter estimation\. The parameter𝒂\\boldsymbol\{a\}is fixed throughout training \(no warmup\)\. Non\-negative risk correction \(Δjn​n\\Delta\_\{j\}^\{nn\}\) is applied\.

*Pseudo Label \(PL\):*The loss is the sum of a standard supervised cross\-entropy term and an unsupervised CE term computed from pseudo labels\. Initially, a supervised classifier is trained, followed by generating predictions on unlabeled data to create pseudo labels for instances exceeding a specific confidence threshold\. The classifier is then retrained using both the original and pseudo labels\. The confidence threshold is selected from the set\{0\.8,0\.9,0\.95\}\\\{0\.8,0\.9,0\.95\\\}for tabular multiclass tasks and\{0\.9,0\.95,0\.99\}\\\{0\.9,0\.95,0\.99\\\}for image tasks\.

*VAT:*Supervised cross\-entropy plus KL\-divergence\-based local distributional smoothness regularization with the consistency regularization weight isλU=1\.0\\lambda\_\{U\}=1\.0, the finite\-difference step size for approximating the adversarial direction isξ=10−6\\xi=10^\{\-6\}, and11power\-iteration step is used\. Batch\-normalization running statistics are frozen during the adversarial perturbation computation\. The perturbation radiusϵ\\epsilonis selected from\{0\.2,0\.5,1\.0,2\.0\}\\\{0\.2,0\.5,1\.0,2\.0\\\}for tabular tasks and\{0\.5,1\.0,2\.0,4\.0\}\\\{0\.5,1\.0,2\.0,4\.0\\\}for image tasks\.

## Appendix DAdditional experimental results

This section provides the experimental details and ablation studies that were omitted from the main text because of space constraints\. Unless otherwise stated, all table entries report mean±\\pmstd over 30 random seeds\. The section is organized as follows\. Section[D\.1](https://arxiv.org/html/2607.11947#A4.SS1)reports results for FixMatch, a recent semi\-supervised learning baseline\. Section[D\.2](https://arxiv.org/html/2607.11947#A4.SS2)studies how the number of examples used for covariance estimation affects our method\. Section[D\.3](https://arxiv.org/html/2607.11947#A4.SS3)reports diagnostics for the equal\-covariance approximation used by the proposed estimators\. Finally, Section[D\.4](https://arxiv.org/html/2607.11947#A4.SS4)studies the effect of the non\-negative risk correction\.

### D\.1Results for a recent SSL baseline

We report additional results for FixMatch\[kihy20fixmatch\], a representative recent SSL method based on pseudo\-labeling and consistency regularization\. For each unlabeled example, FixMatch first predicts a pseudo\-label from a weakly augmented view\. It then applies an unsupervised cross\-entropy loss to a strongly augmented view of the same example, but only when the maximum predicted class probability exceeds a confidence threshold\. Because this threshold can substantially affect performance, we sweep the threshold over\{0\.8,0\.9,0\.95\}\\\{0\.8,0\.9,0\.95\\\}\. For each task and labeled\-data configuration, we select the threshold that gives the highest mean best\-validation accuracy\. The selected threshold, the corresponding test accuracy, and the best\-validation accuracy are reported in Table[3](https://arxiv.org/html/2607.11947#A4.T3)\. The unlabeled\-loss weight is fixed atλU=1\.0\\lambda\_\{U\}=1\.0\.

For tabular datasets, the weak view is generated by adding Gaussian noise withσ=0\.1\\sigma=0\.1\. The strong view uses Gaussian noise withσ=0\.2\\sigma=0\.2and feature dropout with drop probabilityp=0\.1p=0\.1\. For MNIST\-family image tasks, including the binary 4\-vs\-9 and multiclass MNIST settings, the weak view uses a small random affine transform,degrees=5\\mathrm\{degrees\}=5and translation\(0\.05,0\.05\)\(0\.05,0\.05\), followed by normalization\. The strong view uses a larger random affine transform,degrees=15\\mathrm\{degrees\}=15, translation\(0\.1,0\.1\)\(0\.1,0\.1\), and scale range\(0\.9,1\.1\)\(0\.9,1\.1\), followed by random erasing with probability0\.50\.5and erased\-area scale\(0\.02,0\.1\)\(0\.02,0\.1\), then normalization\. For CIFAR\-style image tasks, the weak view uses random horizontal flip and random crop with padding 4; the strong view additionally applies color jitter with brightness/contrast/saturation0\.40\.4and hue0\.10\.1, random grayscale with probability0\.10\.1, and random erasing with probability0\.50\.5\.

Table 3:Classification results for FixMatch\. Results are test accuracy and best\-validation accuracy in %, reported as mean±\\pmstd over 30 seeds\. For binary tasks, Bal\. and Imb\. denote balanced and imbalanced labeled data setting used in the section[6\.2](https://arxiv.org/html/2607.11947#S6.SS2)\. For MNIST, Bal\., Mild, and Sev\. follow the regime notation used in the main text\.
### D\.2Covariance\-set size effect

Our method uses a small held\-out set to estimate covariance\-related quantities\. This ablation examines how sensitiveOurs \(Iter\)is to the number of held\-out covariance\-estimation examples per class\. We run the experiment on MNIST under two labeled\-data regimes: a balanced regime and a severe\-imbalance regime\. Table[4](https://arxiv.org/html/2607.11947#A4.T4)shows that performance is fairly stable once a modest number of covariance\-estimation examples is available\. In particular, performance does not collapse even with very small covariance sets, likely helped by diagonal shrinkage and Tikhonov regularization, and largely saturates around 20–50 examples per class\.

Table 4:MNIST covariance\-set size ablation usingOurs \(Iter\)\. Results are test accuracy in %, reported as mean±\\pmstd over 30 seeds\.
### D\.3Equal\-covariance diagnostic

The proposed data\-free method relies on an equal\-covariance approximation across classes\. This diagnostic quantifies how closely the class\-conditional covariance matrices agree with one another\. In Table[5](https://arxiv.org/html/2607.11947#A4.T5), Cov\. rel\. Fro\. denotes the average pairwise relative Frobenius distance between class covariance matrices:

∥Σi−Σj∥F\(∥Σi∥F\+∥Σj∥F\)/2\.\\frac\{\\lVert\\Sigma\_\{i\}\-\\Sigma\_\{j\}\\rVert\_\{F\}\}\{\(\\lVert\\Sigma\_\{i\}\\rVert\_\{F\}\+\\lVert\\Sigma\_\{j\}\\rVert\_\{F\}\)/2\}\.Smaller values of this measure indicate that the class\-conditional covariance matrices are closer to the equal\-covariance approximation\. These distances are not exactly zero; hence, equal covariance \(EC\) should be viewed as a data\-free approximation, analogous to the equal\-variance simplification used for binary PNU\. Nevertheless, our experimental results do not show a clear correlation between the degree of EC violation and performance\. One possible reason is that this diagnostic measures covariance discrepancies at fixed trained models, whereas Theorem[10](https://arxiv.org/html/2607.11947#Thmthm10)suggests the performance is affected by the maximum variance over the hypothesis class\. This distinction may explain why this local measure of EC violation is not directly predictive of empirical performance\.

Table 5:Equal\-covariance diagnostic summary\. Results are mean±\\pmstd over 30 seeds\. Smaller Cov\. rel\. Fro\. values indicate closer agreement with the equal\-covariance approximation\.
### D\.4Non\-negative risk\-correction ablation

We study the effect of the non\-negative risk correction introduced in Section[5\.2](https://arxiv.org/html/2607.11947#S5.SS2)\. Tables[6](https://arxiv.org/html/2607.11947#A4.T6)–[10](https://arxiv.org/html/2607.11947#A4.T10)compareOurs \(Iter\)with and without this correction\. In the tables, “NN on” is the default method with the non\-negative risk correction, and “NN off” is the same method without it\. We also report

Δ=accuracy\(NN off\)−accuracy\(NN on\)\\Delta=\\text\{accuracy\(NN off\)\}\-\\text\{accuracy\(NN on\)\}in percentage points\. A negativeΔ\\Deltameans that the correction improves accuracy, while a positiveΔ\\Deltameans that removing the correction gives higher accuracy\. Overall, the correction has a small effect on many tabular datasets\. However, it is highly effective on image datasets with larger accuracy improvements\.

Table 6:Non\-negative risk\-correction ablation on binary tabular tasks\. Results are test accuracy in %, reported as mean±\\pmstd over 30 seeds\.Table 7:Non\-negative risk\-correction ablation on binary image tasks\. Results are test accuracy in %, reported as mean±\\pmstd over 30 seeds\.Table 8:Non\-negative risk\-correction ablation on multiclass tasks with equal labeled samples per class\. Results are test accuracy in %, reported as mean±\\pmstd over 30 seeds\.Table 9:Non\-negative risk\-correction ablation on multiclass tasks with mild imbalance\. Results are test accuracy in %, reported as mean±\\pmstd over 30 seeds\.Table 10:Non\-negative risk\-correction ablation on multiclass tasks with severe imbalance\. Results are test accuracy in %, reported as mean±\\pmstd over 30 seeds\.