Generalized Distribution-Free Semi-Supervised Learning with Risk Rewrite

Hiroo Irobe; Takafumi Kanamori; Yushi Hirose

REVIEW 4 major objections 4 minor 12 references

This paper shows that every unbiased risk rewrite for distribution-free semi-supervised classification is a linear combination of class-conditional and unlabeled risks, and that the variance-optimal member of this family provably matches or

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 07:18 UTC pith:JYF62XWF

load-bearing objection Solid multiclass extension of PNU risk rewriting with a clean variance characterization, but the theoretical link to the adaptive SSL algorithm is not closed; deserves conditional acceptance. the 4 major comments →

arxiv 2607.11947 v2 pith:JYF62XWF submitted 2026-07-11 cs.LG cs.AI

Generalized Distribution-Free Semi-Supervised Learning with Risk Rewrite

Yushi Hirose , Hiroo Irobe , Takafumi Kanamori This is my paper

classification cs.LG cs.AI MSC 68T0562H30

keywords semi-supervised learningrisk rewritingunbiased risk estimatorPNU learningvariance reductionmulticlass classificationgeneralization bounddistribution-free

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Most semi-supervised learning relies on distributional assumptions that can hurt when those assumptions are violated. PNU learning avoids this by rewriting the risk, but it only works for binary classification and lacks a variance-optimality story. This paper proposes one family of unbiased risk estimators built from all linear combinations of class-conditional and unlabeled risks, shows it subsumes PNU and extends to multiclass problems, and derives the exact minimum variance of that family. Under asymmetric losses the optimum beats PNU's variance; under symmetric losses the paper shows PNU was already optimal. It then proves a generalization bound in which lower estimator variance translates into a tighter excess-risk guarantee, and reports two algorithms that match or outperform strong baselines.

Core claim

The central claim is that the set Slin of unbiased risk estimators expressible as linear combinations of per-class risks Rij and unlabeled risks RUj is exactly parametrized by a k-dimensional vector a (Theorem 1), so every such rewrite is one member of a unified family, not an ad hoc construction. For a fixed classifier g and nU → ∞, the minimum variance over this family equals Σ_m θ_m²/n_m (C_m)_mm − u^T S^{-1}u (Theorem 3), where the first term is the supervised variance and the second is a non-negative reduction coming from unlabeled data. In binary problems with asymmetric loss, this optimum is provably no worse than the best PNU estimator (Theorem 5), with an explicit gap; when the loss

What carries the argument

The load-bearing object is Slin, the family of all unbiased estimators formed as linear combinations of component risks Rij(g) = E_{x∼p_i}[l(g(x),j)] and unlabeled risks RUj(g) = E_{x∼p}[l(g(x),j)]. Under linear independence of the component risks, the unbiasedness constraint collapses to k free coefficients (Theorem 1), turning variance minimization into a convex quadratic in a. The exact solution (Theorem 3) is the algebraic identity min Var = Σ_m θ_m²/n_m (C_m)_mm − u^T S^{-1}u, where S and u are built from per-class loss covariances; this identity powers both the comparison with PNU and the generalization bound (Theorem 10).

Load-bearing premise

The theory fixes the risk-reweighting coefficients a before training and takes the unlabeled sample size to infinity; the proposed algorithm re-estimates a during training, and the paper does not prove that this re-estimation keeps the worst-case variance over the hypothesis class small, so the connection from variance reduction to the reported SSL gains is only heuristic if that transfer fails.

What would settle it

On a balanced binary problem with asymmetric loss and large nU, estimate the covariance matrices and compute both the optimal PNU variance and the optimal linear variance for a fixed trained g. Theorem 5 predicts the linear one is strictly smaller, with a specific gap; if the measured variance is not lower, the central variance claim fails.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

PNU learning, and any other risk-rewriting scheme built by mixing rewritten risks, becomes a special case of one family; applying the same variance-minimization recipe to those schemes could lower their variance too.
Multiclass SSL can be done without manifold or cluster assumptions: given class priors plus labeled and unlabeled data, the optimal linear risk is computable and comes with a guarantee.
In binary symmetric-loss settings, the theory says PNU already achieves the best variance within Slin, so there is nothing to gain from a more general linear rewrite there.
In asymmetric-loss settings with balanced labeled data, the gap formula in Theorem 5 predicts a concrete variance advantage of the new estimator over PNU; the experiments confirm this ordering on Gaussian and Credit data.
The equal-covariance closed form a*_i = θ_i(1 − w_i/W) gives a validation-free way to obtain most of the benefit, with no covariance estimation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

[Editorial inference] If the variance-to-generalization link survives the online re-estimation of a, the same quadratic minimization could be applied to any weakly supervised risk-rewriting problem—complementary labels, pairwise similarities, delayed feedback—where a linear rewrite exists. The paper names this as future work rather than demonstrating it.
[Editorial inference] The equal-covariance diagnostic suggests a cheap practical rule: measure pairwise Frobenius distances between class-conditional loss covariances; when they are small, the data-free method should be close to the iterative method. The paper's own data, however, show no clear correlation, so this remains an open empirical question.
[Editorial inference] The non-negative correction that makes deep models work changes the effective estimator, so the optimal a* derived for the raw linear risk may not be optimal for the corrected one. The severe-imbalance MNIST ablation, where the correction shifts accuracy by about 6 percentage points, makes this tension visible.
[Editorial inference] A targeted experiment could test Theorem 5's prediction directly: with balanced labeled samples and an asymmetric loss, the gap between PNU and the linear optimum should shrink as the labeled class sizes become more imbalanced; measuring that trend would validate the mechanism outside the paper's settings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Solid multiclass extension of PNU risk rewriting with a clean variance characterization, but the theoretical link to the adaptive SSL algorithm is not closed; deserves conditional acceptance.

read the letter

The core of this paper is a real contribution: it defines a linear family Slin of unbiased risk estimators that subsumes PNU, extends cleanly to multiclass, and gives the exact minimum variance under nU → ∞. The multiclass parameterization (Theorem 1) and the variance reduction formula (Theorem 3) are new and check out, as do the symmetric-loss specialization (Theorem 6) and the binary equivalence showing PNU is already optimal in Slin for symmetric losses (Theorem 9). The proofs in the appendix are careful and readable, and the paper is honest about the equal-covariance approximation in the data-free method, even reporting a diagnostic showing it is not directly predictive. That is good practice.

The main soft spot is the gap between theory and algorithm. Theorem 10 gives a generalization bound that links variance reduction to excess risk, but it is proven for a fixed a with nU → ∞. Algorithm 1 re-estimates a during training from validation data and the current classifier, so the bound doesn't literally apply to the procedure being run. The pointwise variance reduction at one g need not control the worst-case variance over the hypothesis class, and variance minimization could in principle worsen the constants L_a and B_a. The paper's claim that 'a good choice of a improves SSL performance' is therefore heuristic for the actual algorithm. The experiments do show modest gains (1–2 points over supervised), but the PNU baseline is not tuned—it uses the fixed equal-variance η—so the empirical comparison is mildly favorable to the proposed method. A tuned PNU baseline would be the right check.

These issues are not fatal. The variance analysis is a standalone theoretical contribution regardless of the SSL algorithm, and the experiments at least demonstrate practical viability. The paper deserves peer review, but the authors should either prove a bound for the adaptive procedure (or a variant of it), or clearly reframe the theory as motivation rather than justification. They should also release code and report a tuned PNU baseline. The core math is sound, the writing is clear, and the problem is worth solving.

Referee Report

4 major / 4 minor

Summary. The paper proposes a generalized linear risk-rewriting framework for distribution-free semi-supervised classification. It defines the class Slin of unbiased risk estimators formed by linear combinations of component risks and unlabeled risks, parametrizes this class (Theorem 1), derives the minimum achievable variance for fixed g as nU→∞ (Theorem 3), and compares it with PNU learning in the binary setting (Theorem 5). A symmetric-loss variant is analyzed (Theorems 6–9), and a generalization bound is presented (Theorem 10). Based on these theoretical results, two practical SSL algorithms are introduced: an iterative optimization method that periodically re-estimates the risk parameter a on a validation set, and a data-free method under an equal-covariance assumption. Experiments on binary and multiclass benchmarks show that the proposed methods match or exceed several baselines.

Significance. The paper's algebraic framework is clean and the derivations of Theorems 1–9 are careful and appear sound. The minimum-variance characterization may be a useful contribution to the risk-rewriting literature, and the explicit comparison with PNU under symmetric/asymmetric losses clarifies the scope of PNU optimality. The paper also provides detailed proofs and extensive experiments, including ablations and a covariance-diagnostic analysis. However, the advertised direct link between variance reduction and improved SSL performance is not established for the algorithm actually run: Theorem 10 is proven for a fixed parameter a, while Algorithm 1 adapts a during training. Unless this gap is addressed, the theoretical significance of the paper is substantially weaker than claimed.

major comments (4)

[§5.1 (Theorem 10) vs §5.2 (Algorithm 1)] Theorem 10 assumes a fixed parameter vector a and nU→∞. Algorithm 1 updates a every m epochs using validation data and the current classifier, and the objective minimized changes with g_t. No analysis shows that this adaptive procedure controls σ²_max(a_t,ν) or that the sequence of a_t converges. The sentence at the end of §5.1, 'a good choice of a improves the SSL performance,' is therefore a heuristic for the algorithm that is actually evaluated. The empirical gains could equally stem from validation-based tuning rather than from the provable variance-reduction mechanism.
[§5.2, 'Non-negative risk correction'] The non-negative correction replaces Δ_j(g) with max{0,Δ_j(g)}, which makes the estimator used in the experiments a biased estimator of R(g). Theorem 10 applies to the unbiased estimator R̂^a_lin. No bias analysis, nor an analogue of Theorem 10 for the corrected estimator, is provided. Since the correction is applied to 'Ours (Iter)' and PNU in all deep-model experiments (Section 6.2), the stated generalization guarantee does not cover the method whose results are reported.
[§5.1, Theorem 10 proof] The bound is asymptotic in nU: the proof explicitly sets the variance of unlabeled risk components to zero. Consequently, the theoretical variance reduction in Theorem 3 concerns only the labeled-component variance after algebraic rewriting, not the finite-nU estimation variance that the experiments measure when nU varies. The finite-nU behavior claimed in Figures 1 and 2 — where variance decreases as nU grows — is not explained by Theorem 10, and the connection between the asymptotic theory and the finite-sample experiments is left implicit.
[§6.2, Tables 1 and 2] The abstract and introduction state that the proposed methods 'consistently outperform or match existing approaches.' In Table 2, Pseudo Label is frequently better than both proposed methods on Dry Beans and MNIST (e.g., MNIST Bal. (200): PL 89.7 vs Ours (EC) 87.3). The claim is thus too strong. The accurate statement is that the proposed methods are competitive and more robust on certain tabular tasks.

minor comments (4)

[§3.2 / Theorem 1] The notation Rlin in the definition of Slin is later replaced by R^a_lin without an explicit notational transition; this may confuse readers.
[§4.3, proof of Theorem 7] The vector '21' in the expression for ˇd_k should be written as 2·1 or (2,2,…,2)⊤, as '21' is ambiguous.
[§5.2, Algorithm 1] Line 5 says 'Update a←a* minimizing variance (Theorem 3)' but Theorem 3 assumes known covariance matrices and nU→∞. In finite samples the covariance estimates carry noise; the algorithm should state that it uses empirical covariances and the resulting a is an approximation.
[References] Reference 'Hideko KAWAKUBO' is formatted inconsistently; the author name should be standardized (e.g., 'H. Kawakubo').

Circularity Check

0 steps flagged

No significant circularity: the variance and generalization derivations are self-contained; the adaptive-algorithm concern is a gap, not a circular step.

full rationale

The paper's core derivation chain is self-contained. Slin is defined as the set of all unbiased linear combinations of component risks; Theorem 1 derives its parametrization from the linear-independence assumption, and Theorems 2-3 compute the variance and its minimum by direct quadratic algebra. The quantities C_m, S, and u are defined from the loss and class-conditional distributions, not from any fitted result. Theorem 5's inequality is admittedly 'rather trivial' because PNU risks are subsets of Slin, but the paper immediately supplies a nontrivial gap formula (Eq. 2), and the main theoretical content does not reduce to this containment. The comparison with PNU is an external baseline, not a self-citation; the authors cite no prior work of their own as load-bearing. Theorem 10 is proved for a fixed a via a covering argument and Bernstein's inequality, with the variance term entering through sigma^2_max(a,nu); the statement that a good choice of a improves SSL performance is explicitly framed as a heuristic motivation for Algorithm 1. Algorithm 1 re-estimates a during training, and the paper does not prove that this adaptive choice controls sigma^2_max or preserves the Bernstein constants; this is a genuine limitation/gap, but it is not a circular reduction because the adaptive a is not an input to Theorem 10's derivation. Likewise, the non-negative correction and equal-covariance approximation are stated as heuristics and empirically ablated, not presented as predictions forced by the theory. No fitted parameter is renamed as a theoretical quantity, and no self-citation chain is used to forbid alternatives. Therefore the appropriate circularity score is 0.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 0 invented entities

The central theory is largely self-contained; the main external inputs are known class priors and the asymptotic/independence assumptions. The practical SSL methods add hand-chosen numerical stabilization hyperparameters.

free parameters (3)

diagonal shrinkage α = 0.5
Used in Ours(Iter) covariance estimation (Appendix C); chosen by hand, not derived.
Tikhonov regularization λ = 1e-4
Added when solving for optimal a in Ours(Iter); chosen by hand.
warm-up epochs = 20
Ours(Iter) trains supervised for 20 epochs before joint optimization; chosen by hand.

axioms (6)

domain assumption Class priors θ_i are known
All rewritten risks and the variance formulas require θ_i; the paper assumes knowledge in experiments (§6.2) but does not provide an estimator within the framework.
domain assumption nU → ∞ for variance and generalization theorems
Thms 2, 3, 10 and the variance comparisons drop the unlabeled-sample variance; finite nU corrections are not given.
domain assumption Linear independence of risk components (Assumption 1) or its symmetric-loss analogue (Assumption 2)
Needed for the k-parameter (or k−1) parametrization of Slin; fails for symmetric losses, which the paper handles separately.
domain assumption S and ˇS invertible
Required for closed-form minimum variance (Thms 3, 8); the practical method uses Tikhonov regularization to handle near-singularity.
domain assumption Equal covariance C_m = C across classes in Thm 4/5 and Ours(EC)
Used for the closed-form variance-reduction formula and the data-free method; Appendix D.3 shows it is violated in practice.
domain assumption Loss is L-Lipschitz and bounded in [0,c_l] for Thm 10
Needed for the covering and Bernstein arguments in the generalization bound.

pith-pipeline@v1.3.0-alltime-deepseek · 30019 in / 23422 out tokens · 241144 ms · 2026-08-02T07:18:15.701587+00:00 · methodology

0 comments

read the original 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.

Figures

Figures reproduced from arXiv: 2607.11947 by Hiroo Irobe, Takafumi Kanamori, Yushi Hirose.

**Figure 2.** Figure 2: Variance ratio (Rˆa ∗ lin / Rˆ) as a function of the unlabeled sample size nU for uniform and skewed class priors (k = 7). The red dashed line indicates the supervised baseline (ratio = 1). C SSL EXPERIMENTAL DETAILS We provide full details omitted from the main text for the SSL experiments in Section 6.2. Validation set. For all settings, the validation set is independently sampled from the original datas… view at source ↗

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 3 canonical work pages

[1]

Using the ν-cover Cν, we can bound the deviation for any g∈ Gby mapping it to its closest element g′ ∈C ν

Decomposition of Excess Risk and Covering BoundFirst, we relate the excess risk to the maximum estimation error overG: R(ˆg)−R(g∗) =R(ˆg)− ˆRa lin(ˆg) +ˆRa lin(ˆg)− ˆRa lin(g∗) + ˆRa lin(g∗)−R(g ∗) ≤R(ˆg)− ˆRa lin(ˆg) +ˆRa lin(g∗)−R(g ∗) (since ˆRa lin(ˆg)≤ ˆRa lin(g∗)) ≤2 sup g∈G | ˆRa lin(g)−R(g)|. Using the ν-cover Cν, we can bound the deviation for an...
[2]

+ 2w1w2ρ1(ρ1 −ρ 2) ρ1(w1 +w 2) . Variance gap(2):Using the result from Theorem 4 fork= 2, the minimum variance of our proposed estimator is: Var( ˆRa∗ lin) = 2X m=1 wmρ1 − (ρ1 −ρ 2) w2 1 +w 2 2 W +ρ 2W =ρ 1W−ρ 2W−(ρ 1 −ρ 2) w2 1 +w 2 2 W = (ρ1 −ρ 2) W− w2 1 +w 2 2 W = (ρ1 −ρ 2) (w1 +w 2)2 −(w 2 1 +w 2 2) W = (ρ1 −ρ 2) 2w1w2 w1 +w 2 . We compute the gapVar...
[3]

NN on” is the default method with the non-negative risk correction, and “NN off

Final PAC Bound DerivationCombining this result with the decomposition from Step 1 and Eq. (8), we bound the total excess risk: R(ˆg)−R(g∗)≤4L aν+ 2 max g′∈Cν | ˆRa lin(g′)−R(g ′)| ≤4L aν+ s 8σ2max(a, ν) ln 2N(G, ν,∥ · ∥∞) δ + 4 3 Ba max m∈[k] θm nm ln 2N(G, ν,∥ · ∥∞) δ This completes the proof. B V ARIANCE COMPARISON RESULTS FOR MULTICLASS SETTING We pre...

2000
[6]

Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V

URL https://openreview.net/forum? id=PDrUPTXJI_A. Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V . Le. Unsupervised data augmentation for consistency training. InProceedings of the 34th Inter- national Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY , USA, 2020. Curran Associates Inc. ISBN 9781713829546. David...

2020
[11]

Bernstein’s Inequality on the Finite CoverWe now bound the estimation error for the finite set of hypotheses in Cν. For any fixedg ′ ∈C ν, the estimator ˆRa lin(g′)is a sum of independent random variables: ˆRa lin(g′) = kX m=1 nmX q=1 θm nm  l(g′(xm q ), m) + kX j=1 aj θj −1 l(g′(xm q ), j)   | {z } Zmq (g′) +const. Since0≤l(·,·)≤c l, the variablesZ m...
[1995]

doi: 10.3115/981658.981684

Association for Computational Linguistics. doi: 10.3115/981658.981684. URL https://doi.org/ 10.3115/981658.981684. Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jin- dong Wang, Manabu Okumura, and Takahiro Shinozaki. Flexmatch: boosting semi-supervised learning with cur- riculum pseudo labeling. InProceedings of the 35th Inter- national Conference on Neur...

arXiv 2021
[2005]

doi: 10.1109/TKDE.2005.186. Appendix Yushi Hirose1 Hiroo Irobe1 Takafumi Kanamori1,2 1Department of Mathematical and Computing Science, Institute of Science Tokyo, 2RIKEN Center for Advanced Intelligence Project A OMITTED PROOFS Proof of Theorem 1.We can writeR {aij },{bj } lin (g)as R{aij },{bj } lin (g) = X i,j aijRij(g) + X j bjRU j(g) = X i,j aijRij(g...

work page doi:10.1109/tkde.2005.186 2005
[2017]

ISBN 9781510860964

Curran Associates Inc. ISBN 9781510860964. Jesse H. Krijthe and Marco Loog. Robust semi-supervised least squares classification by implicit constraints.Pattern Recogn., 63(C):115–126, March 2017. ISSN 0031-3203. doi: 10.1016/j.patcog.2016.09.009. URL https:// doi.org/10.1016/j.patcog.2016.09.009. Samuli Laine and Timo Aila. Temporal ensembling for semi-su...

work page doi:10.1016/j.patcog.2016.09.009 2017
[2018]

Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama

URL https://proceedings.mlr.press/ v80/lipton18a.html. Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction ap- proach. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Confer- ence on Artificial Inte...

arXiv 2020
[2020]

org/CorpusID:221970624

URL https://api.semanticscholar. org/CorpusID:221970624. Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. The UCI Machine Learning Repository. https:// archive.ics.uci.edu, 2023. Ryuichi Kiryo, Gang Niu, Marthinus C. du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non- negative risk estimator. InProceedings of the 31st Inter- nati...

2023
[2021]

Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D

doi: 10.1162/neco_a_01373. Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel. Fixmatch: simplifying semi-supervised learning with consistency and confi- dence. InProceedings of the 34th International Con- ference on Neural Information Processing Systems, NIPS ’20, Red Hook...

work page doi:10.1162/neco_a_01373 2020
[2023]

Antti Tarvainen and Harri Valpola

URL https://proceedings.mlr.press/ v189/tang23a.html. Antti Tarvainen and Harri Valpola. Mean teachers are bet- ter role models: Weight-averaged consistency targets im- prove semi-supervised deep learning results. InProceed- ings of the 31st International Conference on Neural Infor- mation Processing Systems, NIPS’17, page 1195–1204, Red Hook, NY , USA, 2...

arXiv 2017

[1] [1]

Using the ν-cover Cν, we can bound the deviation for any g∈ Gby mapping it to its closest element g′ ∈C ν

Decomposition of Excess Risk and Covering BoundFirst, we relate the excess risk to the maximum estimation error overG: R(ˆg)−R(g∗) =R(ˆg)− ˆRa lin(ˆg) +ˆRa lin(ˆg)− ˆRa lin(g∗) + ˆRa lin(g∗)−R(g ∗) ≤R(ˆg)− ˆRa lin(ˆg) +ˆRa lin(g∗)−R(g ∗) (since ˆRa lin(ˆg)≤ ˆRa lin(g∗)) ≤2 sup g∈G | ˆRa lin(g)−R(g)|. Using the ν-cover Cν, we can bound the deviation for an...

[2] [2]

+ 2w1w2ρ1(ρ1 −ρ 2) ρ1(w1 +w 2) . Variance gap(2):Using the result from Theorem 4 fork= 2, the minimum variance of our proposed estimator is: Var( ˆRa∗ lin) = 2X m=1 wmρ1 − (ρ1 −ρ 2) w2 1 +w 2 2 W +ρ 2W =ρ 1W−ρ 2W−(ρ 1 −ρ 2) w2 1 +w 2 2 W = (ρ1 −ρ 2) W− w2 1 +w 2 2 W = (ρ1 −ρ 2) (w1 +w 2)2 −(w 2 1 +w 2 2) W = (ρ1 −ρ 2) 2w1w2 w1 +w 2 . We compute the gapVar...

[3] [3]

NN on” is the default method with the non-negative risk correction, and “NN off

Final PAC Bound DerivationCombining this result with the decomposition from Step 1 and Eq. (8), we bound the total excess risk: R(ˆg)−R(g∗)≤4L aν+ 2 max g′∈Cν | ˆRa lin(g′)−R(g ′)| ≤4L aν+ s 8σ2max(a, ν) ln 2N(G, ν,∥ · ∥∞) δ + 4 3 Ba max m∈[k] θm nm ln 2N(G, ν,∥ · ∥∞) δ This completes the proof. B V ARIANCE COMPARISON RESULTS FOR MULTICLASS SETTING We pre...

2000

[4] [6]

Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V

URL https://openreview.net/forum? id=PDrUPTXJI_A. Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V . Le. Unsupervised data augmentation for consistency training. InProceedings of the 34th Inter- national Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY , USA, 2020. Curran Associates Inc. ISBN 9781713829546. David...

2020

[5] [11]

Bernstein’s Inequality on the Finite CoverWe now bound the estimation error for the finite set of hypotheses in Cν. For any fixedg ′ ∈C ν, the estimator ˆRa lin(g′)is a sum of independent random variables: ˆRa lin(g′) = kX m=1 nmX q=1 θm nm  l(g′(xm q ), m) + kX j=1 aj θj −1 l(g′(xm q ), j)   | {z } Zmq (g′) +const. Since0≤l(·,·)≤c l, the variablesZ m...

[6] [1995]

doi: 10.3115/981658.981684

Association for Computational Linguistics. doi: 10.3115/981658.981684. URL https://doi.org/ 10.3115/981658.981684. Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jin- dong Wang, Manabu Okumura, and Takahiro Shinozaki. Flexmatch: boosting semi-supervised learning with cur- riculum pseudo labeling. InProceedings of the 35th Inter- national Conference on Neur...

arXiv 2021

[7] [2005]

doi: 10.1109/TKDE.2005.186. Appendix Yushi Hirose1 Hiroo Irobe1 Takafumi Kanamori1,2 1Department of Mathematical and Computing Science, Institute of Science Tokyo, 2RIKEN Center for Advanced Intelligence Project A OMITTED PROOFS Proof of Theorem 1.We can writeR {aij },{bj } lin (g)as R{aij },{bj } lin (g) = X i,j aijRij(g) + X j bjRU j(g) = X i,j aijRij(g...

work page doi:10.1109/tkde.2005.186 2005

[8] [2017]

ISBN 9781510860964

Curran Associates Inc. ISBN 9781510860964. Jesse H. Krijthe and Marco Loog. Robust semi-supervised least squares classification by implicit constraints.Pattern Recogn., 63(C):115–126, March 2017. ISSN 0031-3203. doi: 10.1016/j.patcog.2016.09.009. URL https:// doi.org/10.1016/j.patcog.2016.09.009. Samuli Laine and Timo Aila. Temporal ensembling for semi-su...

work page doi:10.1016/j.patcog.2016.09.009 2017

[9] [2018]

Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama

URL https://proceedings.mlr.press/ v80/lipton18a.html. Nan Lu, Tianyi Zhang, Gang Niu, and Masashi Sugiyama. Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction ap- proach. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Confer- ence on Artificial Inte...

arXiv 2020

[10] [2020]

org/CorpusID:221970624

URL https://api.semanticscholar. org/CorpusID:221970624. Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. The UCI Machine Learning Repository. https:// archive.ics.uci.edu, 2023. Ryuichi Kiryo, Gang Niu, Marthinus C. du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non- negative risk estimator. InProceedings of the 31st Inter- nati...

2023

[11] [2021]

Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D

doi: 10.1162/neco_a_01373. Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel. Fixmatch: simplifying semi-supervised learning with consistency and confi- dence. InProceedings of the 34th International Con- ference on Neural Information Processing Systems, NIPS ’20, Red Hook...

work page doi:10.1162/neco_a_01373 2020

[12] [2023]

Antti Tarvainen and Harri Valpola

URL https://proceedings.mlr.press/ v189/tang23a.html. Antti Tarvainen and Harri Valpola. Mean teachers are bet- ter role models: Weight-averaged consistency targets im- prove semi-supervised deep learning results. InProceed- ings of the 31st International Conference on Neural Infor- mation Processing Systems, NIPS’17, page 1195–1204, Red Hook, NY , USA, 2...

arXiv 2017