1 Introduction↩︎

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 [1]–[3] . Typical distributional assumptions include the manifold assumption, which posits that high-dimensional data lie on a lower-dimensional manifold, and the cluster assumption, which assumes that the decision boundary should pass through low-density regions to separate data clusters [2]. 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 [4], [5]. Recent methods based on deep models employ regularizers to enhance model robustness against input perturbations, data augmentation and dropout [6]–[9].

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 [2]. The pseudo-labeling process has traditionally been managed by fixed confidence thresholds [10], and recent works have adjusted them with training progress [11], [12]. These methods are refined by multiple classifiers [13]–[15] to derive more accurate pseudo labels. Please refer to [2], [3] for 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 [16]–[20].

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 through risk rewriting [21], 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 [22]. [23] extended 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 by [23] leaves 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 risks \(S_{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, 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 set \(S_{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 in \(S_{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.

2 Problem setting↩︎

We consider a multiclass classification problem where the input space is \(\mathcal{X} \subset \mathbb{R}^d\) and the output label space is \(\mathcal{Y} = \{1, \dots, k\}\). We assume the data is generated from a joint distribution \(p(x, y)\) over \(\mathcal{X} \times \mathcal{Y}\). Let \(p_i(x) = p(x \mid y=i)\) denote the class-conditional density for class \(i\), and let \(\theta_i= P(y=i)\) be the class prior probability, such that \(\sum_{i=1}^k \theta_i = 1\). The distribution of unlabeled data is given by the mixture model: \(p(x) = \sum_{i=1}^k \theta_i p_i(x)\). In the semi-supervised setting, we are provided with labeled datasets \(\mathcal{X}_i = \{x_j^i\}_{j=1}^{n_i} \stackrel{i.i.d.}{\sim} p_i(x)\) for each class \(i \in \mathcal{Y}\), and an unlabeled dataset \(\mathcal{X}_U = \{x_j^U\}_{j=1}^{n_U} \stackrel{i.i.d.}{\sim} p(x)\).

Risk Definitions. Let \(g: \mathcal{X} \to \mathbb{R}^k\) be a decision function (e.g., a neural network) and \(l: \mathbb{R}^k \times \mathcal{Y} \to \mathbb{R}\) be a loss function. Assume that \(g\) belongs to a function class \(\mathcal{G}\). The goal of standard supervised learning is to minimize the true risk \(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 risks \(R_{ij}(g)\) as: \[R_{ij}(g) := \mathbb{E}_{x \sim p_i}[l(g(x), j)],\] which is the expected loss of predictor \(g\) calculated over the distribution of class \(i\) but evaluated with respect to a fixed label \(j\). Similarly, we define the risk over the unlabeled distribution with respect to label \(j\) as: \[R_{Uj}(g) := \mathbb{E}_{x \sim p(x)}[l(g(x), j)].\] Using these components, the standard supervised risk can be expressed as \(R(g) = \sum_{i=1}^k \theta_i R_{ii}(g)\).

2.1 Revisiting Binary Risk Rewriting: PU, NU, and PNU Risks↩︎

Although the standard supervised risk is written as \(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 for \(R(g)\) with unlabeled data. Consider the case where \(k=2\), with \(y=1\) and \(y=2\) representing the positive and negative classes, respectively. Then the standard supervised risk (PN risk) is \(R_{PN}(g) := \theta_1 R_{11}(g) + \theta_2 R_{22}(g)\).

PU Risk. Positive-Unlabeled (PU) learning [22] addresses scenarios where negative labels are unavailable. By exploiting the density equality \(\theta_2 p_2(x) = p(x) - \theta_1 p_1(x)\), one can rewrite the risk on the negative class as \(\theta_2 R_{22}(g) = R_{U2}(g) - \theta_1 R_{12}(g)\). This yields the PU risk: \[R_{PU}(g) := \theta_1 R_{11}(g) - \theta_1 R_{12}(g) + R_{U2}(g).\]

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 \(\theta_1 p_1(x) = p(x) - \theta_2 p_2(x)\)), we obtain the Negative-Unlabeled (NU) risk: \[R_{NU}(g) := \theta_2 R_{22}(g) - \theta_2 R_{21}(g) + R_{U1}(g).\]

PNU Risk. Under certain conditions and as \(n_U\rightarrow\infty\), PU and NU learning outperform PN learning [24]. To exploit this advantage further, [23] proposed PNU learning¹, which considers the following risk that linearly combines PU, NU, and PN risks with a parameter \(\eta \in [-1, 1]\): \[R_{\text{PNU}}^{\eta}(g) := \begin{cases} R_{\text{PNPU}}^{\eta}(g) & (\eta \ge 0) \\ R_{\text{PNNU}}^{|\eta|}(g) & (\eta < 0) \end{cases}\] where \[\begin{align} & R_{\mathrm{PNPU}}^\eta(g):=(1-\eta) R_{\mathrm{PN}}(g)+\eta R_{\mathrm{PU}}(g), \\ & R_{\mathrm{PNNU}}^\eta(g):=(1-\eta) R_{\mathrm{PN}}(g)+\eta R_{\mathrm{NU}}(g) . \end{align}\]

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 [11], [15], 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.

3 Our 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.1 Generalized Unbiased Estimators via Linear Combinations↩︎

We define the set of linear combinations of risk functionals, \(S_{lin}\), as \[\begin{align} S_{lin} &:= \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) \nonumber \\ &\Biggm| a_{ij}, b_j \in \mathbb{R}, \quad \forall g\in\mathcal{G}, \;R_{lin}^{\{a_{ij}\}, \{b_j\}}(g) = R(g) \Biggr\}. \end{align}\] The set is defined as linear combinations of component risks and unlabeled risks, which are equal to \(R(g)\) for all \(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 each \(R_{lin}^{\{a_{ij}\}, \{b_j\}}(\cdot)\in S_{lin}\) by using empirical distributions. By optimizing the parameters \(a_{ij}\) and \(b_j\) over the full set \(S_{lin}\), we can derive a risk that has a lower estimation variance than the existing methods.

3.2 Characterization under Linear Independence↩︎

The number of parameters that define the risks in \(S_{lin}\) can be reduced under the following mild assumption.

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 \(\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.

Under Assumption 1, we can characterize the parameters that satisfy the constraint \(\forall g\in\mathcal{G}, R_{lin}^{\{a_{ij}\}, \{b_j\}}(g) = R(g)\).

This theorem implies that each risk in \(S_{lin}\) is parametrized by a \(k\)-dimensional vector.

3.3 Minimum variance calculation↩︎

In the following, we use a fixed \(g\) and often omit the argument of the risk term, denoting \(R_{ij}(g)\) as \(R_{ij}\) when the context is clear. Let \(\hat{R}_{lin}^{\boldsymbol{a}}\) and \(\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 samples \(n_U \to \infty\).

Let \(C_m \in \mathbb{R}^{k \times k}\) be the covariance matrix for class \(m\), defined as \((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 by \(\operatorname{Cov}[\hat{R}_{mi}, \hat{R}_{mj}] = \frac{1}{n_m}(C_m)_{ij}\). We define the diagonal matrix \(Q = \operatorname{diag}(\theta_1^{-1}, \dots, \theta_k^{-1})\) and the shift vectors \(\mathbf{d}_m = \mathbf{1} - \mathbf{e}_m\), where \(\mathbf{1}\) is the all-ones vector and \(\mathbf{e}_m\) is the standard basis vector. We now derive the variance of the estimator \(\hat{R}_{lin}^{\boldsymbol{a}}\).

Since \(A\) is a sum of positive semi-definite matrices, the variance is a convex function of \(\boldsymbol{a}\). Define \(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: \[\nabla_{\boldsymbol{a}} f(\boldsymbol{a}) = 2A\boldsymbol{a} - 2\mathbf{b} = 0 \implies A\boldsymbol{a}^* = \mathbf{b}.\] If \(A\) is invertible, the minimum variance is given by \(f(\boldsymbol{a}^*) = c - \mathbf{b}^T A^{-1} \mathbf{b}\). For simplicity, we define the total weighted covariance matrix \(S\) and the weighted covariance vector \(\mathbf{u}\): \[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:

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

3.4 Magnitude of variance reduction↩︎

The variance reduction \(\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 \(\forall m\in[k], C_m=C\) where \((C)_{ii}=\rho_1>0\) and \((C)_{ij}=\rho_2<0\) for \(i\neq j\), since \((C_m)_{ij}\) for \(i\neq j\) tends to be negative for usual loss functions.

Considering the upper bound of \(\mathbf{u}^T S^{-1} \mathbf{u}\), the variance reduction is large when \(\max_{m \in [k]}w_m\) is large and \(W-\max_{m \in [k]}w_m\) is small, which means \(\theta_i\) and \(n_i\) should be disproportionate, i.e., there exists class imbalance in labeled samples.

3.5 Comparison 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, 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.

Eq. ?? 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 of \(\hat{R}_{lin}^{\boldsymbol{a}}\) subsumes the sets of \(\hat{R}_{\text{PNPU}}^{\eta}\) and \(\hat{R}_{\text{PNNU}}^{\eta}\). Eq. ?? implies the gap in minimum variances becomes small when \(w_1\gg w_2\) or \(w_1\ll w_2\), which means our method is more advantageous when \(\theta_i\) and \(n_i\) are proportional, i.e., the labeled data is balanced.

4 Symmetric Loss Case↩︎

The preceding sections analyzed the properties of \(S_{lin}\) under Assumption 1. For symmetric loss functions such as the 0-1 loss, Assumption 1 does not hold, and we need a modified analysis, as described in this section.

4.1 Problem Setup under Symmetric Loss↩︎

We assume the loss function \(l(\cdot, \cdot)\) satisfies the symmetric condition:

Common examples include the 0-1 loss and ramp loss [25]. This constraint implies a deterministic linear dependency among the risk components:\(\sum_{j=1}^k R_{ij}(g) = \alpha\). Consequently, the linear independence assumption (Assumption 1) does not hold, and we need a different reparametrization for \(S_{lin}\).

4.2 Reparametrization of \(S_{lin}\) with symmetric loss↩︎

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

Under this assumption, we can characterize \(S_{lin}\) similarly to Theorem 1.

Thus, \(S_{lin}\) with a symmetric loss is parametrized by the \(k-1\) parameters, \(\boldsymbol{a}_{i},i\in[k-1]\).

4.3 Variance of \(\hat{R}_{lin}^{\boldsymbol{a}}\) with Symmetric Loss↩︎

Since the symmetric loss constraint implies \(R_{mk} = \alpha - \sum_{j=1}^{k-1} R_{mj}\), the \(k\)-th row and column of the covariance matrix \(C_m\) are entirely determined by the covariance of the first \(k-1\) risk terms. Thus, the variance of \(\hat{R}_{lin}^{\boldsymbol{a}}\) is expressed with truncated matrices of \(C_m\). Let \(\check{C}_m\) be the top-left \((k-1) \times (k-1)\) submatrix of \(C_m\).

To derive the minimum variance, we define \(\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.

4.4 Comparison in Binary Classification with Symmetric Loss↩︎

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

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.

5 Relationship 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 classifier \(g\). The goal of semi-supervised learning is to identify the optimal predictor \(\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.1 Generalization bound with reduced variance↩︎

We consider \(n_U\rightarrow\infty\) to analyze the generalization performance. Let \(\hat{g} = \operatorname{argmin}_{g \in \mathcal{G}} \hat{R}_{lin}^{\boldsymbol{a}}(g)\) be the empirical risk minimizer using our proposed estimator, and let \(g^* = \operatorname{argmin}_{g \in \mathcal{G}} R(g)\) be the true risk minimizer.

Let \(n = \min_m(n_m)\). As \(n \rightarrow \infty\), the maximum variance \(\sigma_{\max}^2(\boldsymbol{a}, \nu)\) scales as \(\mathcal{O}(1/n)\), which implies that the second term of the generalization bound is \(\mathcal{O}(1/\sqrt{n})\). Furthermore, since the third term is proportional to \(\max_{m\in[k]}\left(\frac{\theta_m}{n_m}\right)\), it scales as \(\mathcal{O}(1/n)\). Considering only the dominant \(\mathcal{O}(1/\sqrt{n})\) term and assuming \(\nu\) is small, this theorem implies that the generalization error is small when the maximum variance \(\sigma_{\max}^2(\boldsymbol{a}, \nu)\) is small. Thus, a good choice of \(\boldsymbol{a}\) improves the SSL performance.

5.2 Practical implementation of SSL↩︎

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

5.2.0.1 1. Iterative optimization method

Since the optimal parameter \(\boldsymbol{a}\) that minimizes the bound in Theorem 10 is unknown in practice, we propose empirical iterative optimization of \(g\) and \(\boldsymbol{a}\). The algorithm is described in Algorithm 1. It optimizes \(\hat{g}\) with \(\hat{R}_{lin}^{\boldsymbol{a}}\), calculating \(\boldsymbol{a}\) every \(m\) epochs to minimize the variance with the current \(\hat{g}\) using validation data.

5.2.0.2 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 classes \(k\) is large. If we assume the equal covariance \(\forall m\in[k], C_m=C\), the optimal \(\boldsymbol{a}^*\) is calculated as \(\boldsymbol{a}^*_i=\theta_i\left(1-\frac{w_i}{\sum_{m=1}^k w_m}\right)\) where \(w_i:=\theta_i^2/n_i\). We use the linear risk with this \(\boldsymbol{a}^*\) to learn \(\hat{g}\). This does not require validation data to estimate \(\boldsymbol{a}^*\).

5.2.0.3 Non-negative risk correction for complex models

Note that we can express the linear risk estimator as\[\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 \(\Delta_j(g):=\hat{R}_{Uj}(g)-\sum_{i\neq j}^k\theta_i\hat{R}_{ij}(g)\). Here, \(\Delta_j(g)\) can be viewed as a risk-rewriting estimator for \(\theta_j R_{jj}(g)\). As seen in PU and other risk-rewriting methods [27]–[29], when \(\mathcal{G}\) consists of complex models such as deep neural networks, \(\Delta_j(g)\) can become negative even when \(R_{jj}(g)\) is non-negative, which leads to overfitting. To mitigate this issue, similarly to the approach by [27], we replace \(\Delta_j(g)\) within \(R_{lin}^{\boldsymbol{a}}(g)\) with a non-negative counterpart, \(\Delta_j^{nn}(g):=\max\{0,\Delta_j(g)\}\), when training complex models.

6 Experiments↩︎

6.1 Variance comparison of \(R_{PN}\), \(R_{PNU}\) and \(R_{lin}^{\boldsymbol{a}^*}\)↩︎

In this subsection, we empirically validate the variance reduction achieved by the proposed linear risk estimator \(\hat{R}_{lin}^{\boldsymbol{a}}(g)\). We compare the variance of three unbiased risk estimators for a pre-trained classifier \(g\): the standard supervised risk estimator \(\hat{R}(g)\) (PN risk, which corresponds to \(\hat{R}_{lin}^{\boldsymbol{a}}(g)\) where \(\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=2\)) here; multiclass results are deferred to the Appendix.

6.1.0.1 Datasets.

We use two datasets: a synthetic two-dimensional Gaussian dataset and Credit default dataset from the UCI Machine Learning Repository [30]. For the Gaussian dataset, the class-conditional distributions are \(p_1(x) = \mathcal{N}\!\bigl((1,\; 1)^{\!\top}, I_2\bigr)\) and \(p_2(x) = \mathcal{N}\!\bigl((0,\; 0)^{\!\top}, I_2\bigr)\).

6.1.0.2 Model and training.

We train a logistic regression model \(g(x) = w^{\!\top}\!x + b\) by minimizing the binary cross-entropy (BCE) loss with \(n_1 = n_2 = 30\) labeled samples via stochastic gradient descent.

6.1.0.3 Evaluation loss.

For the variance comparison, we use two loss functions: the BCE loss \(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.

6.1.0.4 Evaluation protocol.

With the trained classifier \(g\) fixed, 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 matrices \(C_m\) for all \(m \in [k]\) using the entire held-out data. For the PNU risk, we consider the set \(S_{PNU}:=S_{PNPU}\cup S_{PNNU}\) as defined in Theorem 9.

For each experimental condition (class prior \(\theta_1\), unlabeled sample size \(n_U\)), we conduct \(5{,}000\) independent trials to estimate the risk variances. We vary \(\theta_1 \in \{0.3, 0.5, 0.7\}\) and \(n_U \in \{50, 100, 200, 500, 1000\}\). The labeled sample sizes for risk estimation are fixed at \(n_1 = n_2 = 30\) across all settings.

6.1.1 Results↩︎

Figure 2 visualizes the variance ratios \(\mathrm{Var}(\hat{R}_{\mathrm{PNU}})/ \mathrm{Var}(\hat{R})\) and \(\mathrm{Var}(\hat{R}_{lin}^{\boldsymbol{a}^{*}})/ \mathrm{Var}(\hat{R})\) as a function of \(n_U\) for each class prior.

6.1.1.1 Effect of unlabeled sample size.

As the number of unlabeled samples \(n_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.

6.1.1.2 Effect of class prior.

When the class prior is imbalanced (\(\theta_1 = 0.3\) or \(\theta_1 = 0.7\)), both methods achieve substantial variance reduction. These results are consistent with Theorem 4. In the balanced case (\(\theta_1 = 0.5\)) with the asymmetric loss (BCE), the PNU risk shows only marginal improvement (e.g., a ratio of \(0.953\) at \(n_U = 1{,}000\)), whereas the proposed linear risk estimator still achieves a meaningful reduction (a ratio of \(0.883\)) , as predicted by Theorem 5.

6.1.1.3 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.

6.2 Comparison with existing semi-supervised learning methods↩︎

We compare the proposed SSL methods against four baselines on binary and multiclass classification tasks: (1) Sup.: standard supervised learning (linear risk with \(\boldsymbol{a}_i:=\theta_i\)); (2) PNU: the PNU risk estimator of [23] with the equal variance assumption (binary only); (3) Pseudo Label (PL): self-training with pseudo-labels assigned by confidence thresholding, based on [10]; and (4) VAT: virtual adversarial training [6], which is a representative consistency regularization method. We denote our iterative method for optimizing \(g\) and \(\boldsymbol{a}\) in this subsection as Ours (Iter). For multiclass tasks, we additionally report Ours (EC), the data-free method under the equal covariance assumption. We assume class priors \(\theta_i\) are known. In practice, we can estimate the class priors using methods such as those proposed by [31]–[34]. We use the cross-entropy loss for all methods. Detailed settings are provided in the Appendix.

6.2.0.1 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 [30]. Binary image: MNIST digits 4 vs. (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 \((n_1, n_2) \in \{(15,45), (30,30), (50,150), (100,100)\}\) with \(n_U = 300\) (tabular) or \(n_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—with \(n_U = 5{,}000\). Please refer to the Appendix for further details. The validation set consists of \(60\) samples for all settings, except for the multiclass image task, which uses \(200\) samples.

6.2.0.2 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 to our methods and PNU learning.

6.2.1 Results↩︎

6.2.1.1 Binary classification results.

Table ¿tbl:tab:binary? 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 \((n_1{=}15)\). However, on CIFAR-10 cat vs.dog, a more challenging task, it fails to yield comparable performance.

6.2.1.2 Multiclass classification results.

Table 1 presents the multiclass results for the tabular datasets and MNIST. On Covertype and Shuttle, our methods Ours (Iter) and Ours (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-free Ours (EC) method demonstrates highly competitive accuracy, matching or closely following the iterative optimization approach without requiring a validation set for parameter tuning.

7 Conclusions↩︎

We proposed a generalized framework for distribution-free semi-supervised learning based on risk rewriting. By formulating the set of linear combinations of component risks \(S_{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[35]–[43]. 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.

8 Omitted Proofs↩︎

9 Variance 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. Since PNU learning is limited to binary classification, we compare only the supervised risk estimator \(\hat{R}(g)\) and the proposed linear risk estimator \(\hat{R}_{lin}^{\boldsymbol{a}^*}(g)\).

9.0.0.1 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.

9.0.0.2 Model and training.

We train a two-layer neural network with hidden dimension 256 by minimizing the cross-entropy loss with \(n_i = 10\) labeled samples per class via the Adam optimizer (learning rate \(10^{-3}\), weight decay \(10^{-4}\)), with early stopping on validation accuracy.

9.0.0.3 Evaluation loss.

We use the cross-entropy (CE) loss \(l(g(x), j) = -\log \mathrm{softmax}(g(x))_j\) for the variance comparison.

9.0.0.4 Evaluation protocol.

With the trained classifier \(g\) fixed, 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 at \(n_i = 5\) for all \(i \in [k]\), and we vary \(n_U \in \{100, 200, 500, 1000, 2000\}\). We consider two class prior settings: (1) uniform, where \(\boldsymbol{\theta} = (1/7, \dots, 1/7)\), and (2) skewed, where \(\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 assuming \(n_U \to \infty\) using the covariance matrices estimated from the all evaluation data. For each condition, we conduct \(5{,}000\) independent trials to estimate the variance.

As the number of unlabeled samples \(n_U\) increases, the variance ratio decreases. The proposed method achieves greater variance reduction under the skewed class prior, consistent with Theorem 4.

10 SSL Experimental details↩︎

We provide full details omitted from the main text for the SSL experiments in Section 6.2.

10.0.0.1 Validation set.

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

10.0.0.2 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]\) (total 140) and \([81, 65, 57, 49, 41, 33, 24]\) (total 350).

• Severe imbalance: \([57, 34, 21, 13, 7, 5, 3]\) (total 140) and \([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]\) (total 500) and \([306, 245, 214, 184, 153, 122, 92, 77, 61, 46]\) (total 1500).

• Severe imbalance: \([200, 120, 72, 44, 26, 16, 10, 6, 4, 2]\) (total 500) and \([600, 360, 216, 132, 78, 48, 30, 18, 12, 6]\) (total 1500).

For all multiclass tasks, \(n_U = 5{,}000\).

10.0.0.3 Model architectures.

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

CNN (image, LeNet-like): Here, let \(\text{Conv}(c_{in}, c_{out}, k, \text{pad})\) denote a 2D convolutional layer with \(c_{in}\) input channels, \(c_{out}\) output channels, kernel size \(k\times k\), and the specified padding. Let \(\text{MaxPool}(k)\) denote a max pooling layer with kernel size \(k\times k\). Let \(\text{FC}(d_{in}, d_{out})\) denote a fully connected layer with input dimension \(d_{in}\) and output dimension \(d_{out}\). For MNIST, the architecture is \(\text{Conv}(1, 32, 3, \text{pad}{=}1)\) \(\to\) ReLU \(\to\) \(\text{MaxPool}(2)\) \(\to\) \(\text{Conv}(32, 64, 3, \text{pad}{=}1)\) \(\to\) ReLU \(\to\) \(\text{MaxPool}(2)\) \(\to\) \(\text{FC}(64{\times}7{\times}7, 128)\) \(\to\) ReLU \(\to\) \(\text{FC}(128, K)\). For CIFAR-10, the architecture is \(\text{Conv}(3, 64, 3, \text{pad}{=}1)\) \(\to\) ReLU \(\to\) \(\text{MaxPool}(2)\) \(\to\) \(\text{Conv}(64, 128, 3, \text{pad}{=}1)\) \(\to\) ReLU \(\to\) \(\text{MaxPool}(2)\) \(\to\) \(\text{FC}(128{\times}8{\times}8, 256)\) \(\to\) ReLU \(\to\) \(\text{FC}(256, K)\).

10.0.0.4 Training protocol.

All models are trained with the Adam optimizer (\(\text{learning rate} =10^{-3}\), weight decay \(10^{-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 threshold \(10^{-4}\).

10.0.0.5 Method-specific settings.

PNU (binary only): The mixing parameter \(\eta\) is computed as \(\eta = (\psi_2 - \psi_1)/(\psi_1 + \psi_2)\) where \(\psi_m = \theta_m^2 / n_m\), following the equal variance assumption [23]. Non-negative risk correction (\(\Delta_j^{nn}\)) is applied.

Ours (Iter): Training begins with a \(20\)-epoch warm-up period utilizing standard supervised risk prior to joint optimization. The covariance matrices are estimated on the validation split with diagonal shrinkage \(\hat{\Sigma}_m \leftarrow (1-\alpha)\hat{\Sigma}_m + \alpha\,\mathrm{diag}(\hat{\Sigma}_m)\) (\(\alpha=0.5\)), and Tikhonov regularization \(\lambda=10^{-4}\) is added when solving the linear system for the optimal \(\boldsymbol{a}\). Non-negative risk correction (\(\Delta_j^{nn}\)) is applied.

Ours (EC): The closed-form parameter \(a_j = \theta_j (1 - w_j / W)\) with \(w_j = \theta_j^2/n_j\) and \(W = \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 (\(\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\}\) for tabular multiclass tasks and \(\{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 \(\lambda_U = 1.0\), the finite-difference step size for approximating the adversarial direction is \(\xi = 10^{-6}\), and \(1\) power-iteration step is used. Batch-normalization running statistics are frozen during the adversarial perturbation computation. The perturbation radius \(\epsilon\) is selected from \(\{0.2, 0.5, 1.0, 2.0\}\) for tabular tasks and \(\{0.5, 1.0, 2.0, 4.0\}\) for image tasks.

11 Additional 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\(\pm\)std over 30 random seeds. The section is organized as follows. Section 11.1 reports results for FixMatch, a recent semi-supervised learning baseline. Section 11.2 studies how the number of examples used for covariance estimation affects our method. Section 11.3 reports diagnostics for the equal-covariance approximation used by the proposed estimators. Finally, Section 11.4 studies the effect of the non-negative risk correction.

11.1 Results for a recent SSL baseline↩︎

We report additional results for FixMatch [44], 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\}\). 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 2. The unlabeled-loss weight is fixed at \(\lambda_U=1.0\).

For tabular datasets, the weak view is generated by adding Gaussian noise with \(\sigma=0.1\). The strong view uses Gaussian noise with \(\sigma=0.2\) and feature dropout with drop probability \(p=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, \(\mathrm{degrees}=5\) and translation \((0.05,0.05)\), followed by normalization. The strong view uses a larger random affine transform, \(\mathrm{degrees}=15\), translation \((0.1,0.1)\), and scale range \((0.9,1.1)\), followed by random erasing with probability \(0.5\) and erased-area scale \((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/saturation \(0.4\) and hue \(0.1\), random grayscale with probability \(0.1\), and random erasing with probability \(0.5\).

2pt

11.2 Covariance-set size effect↩︎

Our method uses a small held-out set to estimate covariance-related quantities. This ablation examines how sensitive Ours (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 3 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.

4pt

11.3 Equal-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 4, Cov.rel.Fro.denotes the average pairwise relative Frobenius distance between class covariance matrices: \[\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 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.

2pt

11.4 Non-negative risk-correction ablation↩︎

We study the effect of the non-negative risk correction introduced in Section 5.2. Tables 5–9 compare Ours (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 \[\Delta = \text{accuracy(NN off)} - \text{accuracy(NN on)}\] in percentage points. A negative \(\Delta\) means that the correction improves accuracy, while a positive \(\Delta\) means 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.

3pt

3pt

3pt

3pt

3pt

References↩︎

---

1. They also proposed PUNU risk, but we omit it since it was shown to be inferior to PNU risk.↩︎