acceptodds
Under review as a conference paper at ICLR 2027

Online Adaptation to Class-Prior Shift from Positive and Unlabeled Data

Abstract

Class-prior shift is a common distribution shift in which the class-conditional distributions remain stable while the class proportions change. Existing online label-shift methods assume labeled source data from every class. We ask: what is the statistical price of online adaptation when the source supervision itself is incomplete? We study this question when the source data contain only positive and unlabeled (PU) examples, while unlabeled target observations arrive sequentially and the class prior changes over time. Such data arise, for example, in protein screening, where only sequences that pass the screen are labeled. We show that labeled negatives are not needed to preserve the online tracking rate. Under a source-sample stability condition, the temporal component of the cumulative squared prior-tracking error retains the dependence on the horizon and total variation achieved with positive and negative source data. The effect of PU supervision appears in the finite-source term: reconstructing the unobserved negative class amplifies source-estimation errors with weights that depend on where the target-prior path lies, beyond alone. We further derive a dynamic classification-regret bound for online threshold adaptation against the best threshold of the same fixed score at each target prior. Experiments on image and text benchmarks show that threshold adaptation improves classification under substantial prior shift with low online cost without retraining the initial model.

Primary area:
learning theory
Keywords:
online label shift, class-prior shift, positive-unlabeled learning, online adaptation, distribution shift, weak supervision, dynamic regret

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_EEDEOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies online adaptation to time-varying class-prior shift when the source data contain only positive and unlabeled examples. The authors derive prior-tracking error bounds that separate temporal variation from finite-source estimation error, together with corresponding lower bounds. They also develop a threshold adaptation procedure with a dynamic classification-regret guarantee. Experiments on image and text datasets demonstrate improved classification performance without online model retraining.

Critical strengths
  1. The paper addresses an interesting setting where online label-shift adaptation is performed without labeled negative source examples.

  2. The separation of temporal tracking error and path-dependent finite-source error is theoretically meaningful. The corresponding lower bounds strengthen the contribution.

  3. The proposed method is computationally efficient and does not require storing or revisiting raw source data during online adaptation.

Critical weaknesses
  1. The prior-tracking algorithm mainly builds on existing online regression methods, particularly ALIGATOR. The methodological contribution lies primarily in the PU reduction and its error analysis rather than a new online learning algorithm.

  2. The tracking guarantees depend on a fixed statistic with sufficient class separation. The effectiveness of this statistic is important in practice, but its selection is not addressed by the proposed procedure.

  3. The theoretical results for prior tracking are relatively strong, but the classification-regret bound is less conclusive when the source sample sizes remain fixed. The connection between the theoretical guarantees and the empirical classification gains could be better explained.

Questions for authors

1. In Section 3.1, the prior estimation procedure relies on a statistic ϕ\phi with class-mean separation d≥dmin⁡>0d\geq d_{\min}>0. How is dmin⁡d_{\min} chosen in the experiments? Since dd is not directly observable from negative samples, how sensitive is the tracking procedure to an inaccurate lower bound?

2. Theorem 1 separates temporal tracking error from finite-source error, while Theorem 2 gives a lower bound with matching path dependence. However, the lower-bound construction allows different underlying models to induce different prior paths. Could the authors clarify the precise minimax interpretation of this result for a fixed target-prior path?

3. In Section 5, the threshold rule minimizes an empirical PU risk reconstructed from positive and unlabeled source samples. The reconstructed negative-class probabilities may fall outside [0,1][0,1] for finite samples. Does the implementation use the raw estimates or apply any correction? Could such corrections affect the threshold selected by Eq. (20)?

4. In the experiments, PU-ATLAS achieves a lower aggregate classification error (4.62%) than the proposed PU-FLH-FTL method (5.50%). How much of this difference is attributable to updating the classifier rather than estimating the class prior? A comparison using the same prior estimates would help isolate the contribution of threshold-only adaptation.

5 comments

We sincerely thank the reviewer for the thoughtful and technically insightful review. We address each point below.

The prior-tracking algorithm mainly builds on existing online regression methods, particularly ALIGATOR. The methodological contribution lies primarily in the PU reduction and its error analysis rather than a new online learning algorithm.

We agree with the reviewer and thank you for constructive comments.

Algorithmically, our PU reduction enables online adaptation using only precomputed source statistics and unlabeled target batches, without revisiting raw source training data or updating the pretrained classifier. This provides a simple and computationally efficient alternative to methods requiring repeated source-data access and online model updates.

Theoretically, we characterize how finite PU supervision introduces persistent, path-dependent uncertainty through WUW_U and W+W_+, and establish an information-theoretic lower bound showing that these costs are unavoidable in a constructed family.

More broadly, we view PU learning under class-prior shift as a concrete, analytically tractable setting for understanding the interaction between weak supervision and distribution shift, potentially informing future extensions to other forms of weak supervision and shift. We will clarify this positioning in the revision.

The tracking guarantees depend on a fixed statistic with sufficient class separation. The effectiveness of this statistic is important in practice, but its selection is not addressed by the proposed procedure.

We thank the reviewer for highlighting this point, which we regard as a particularly important and interesting direction for future direction.

We agree that selecting an informative statistic is crucial and remains outside the scope of our current analysis. In our experiments, we simply use ϕ=g\phi=g, the score learned through standard offline nnPU training.

There is also a principled connection to density-ratio estimation. As discussed in the Appendix (“Exact density-ratio special case”), the exact source posterior satisfies $ g(x)=\pi_0,dP_+/dP_{\mathrm U,\pi_0}(x)$. Taking $ \phi=g$ then yields

=\frac{Var_{P_{\mathrm U,\pi_0}}(g(X))}{\pi_0(1-\pi_0)}.$$ Thus, the exact posterior provides positive separation whenever the class-conditional distributions differ. This suggests density-ratio-based approaches, including those related to Nakajima and Sugiyama (2023), as promising candidates for statistic design. However, estimating a statistic with guaranteed sufficient separation remains an open problem. We will clarify this connection and limitation in the revised manuscript. Please also kindly see our response to Reviewer 7CoU (W4) for the proposed concentration-based separation condition for a fixed statistic.

The theoretical results for prior tracking are relatively strong, but the classification-regret bound is less conclusive when the source sample sizes remain fixed. The connection between the theoretical guarantees and the empirical classification gains could be better explained.

We thank the reviewer for this observation. Our main point is that accurate prior tracking directly controls classification regret under class-prior shift, even with a fixed classifier. Specifically,

\le 2\sqrt{\frac{L_T^{\mathrm{trk}}}{T}}+2\overline\epsilon_R.$$ Here, $\overline\epsilon_R$ is uniformly controlled by the PU holdout samples via the DKW inequality, at rate $O(n_+^{-1/2}+n_u^{-1/2})$. Thus, the bound explicitly connects tracking accuracy to classification performance relative to the best threshold of the same fixed score. The experiments support this connection (Sec. 6 and Appendix E.1, Table 2): aggregate classification error decreases from 15.24% (static) to 5.50% (PU–FLH–FTL), compared with 3.83% for the true-prior oracle using the same fixed classifier and threshold map. Thus, our method achieves approximately 85% of the observed static-to-oracle improvement without retraining or revisiting source data. We agree that fixed source sizes do not guarantee vanishing average regret. We will clarify the distinction between this theoretical guarantee and the finite-horizon empirical gains.

Q1. Choice and misspecification of the separation bound

We thank the reviewer for this important question. We use dmin⁡=0.02d_{\min}=0.02 as a common preset, fixed before observing the PU holdout data (Appendix E.1). Although labeled negatives are unavailable, separation can be estimated from PU data as d^=(μ^+−μ^0)/(1−π0)\widehat d=(\widehat\mu_+-\widehat\mu_0)/(1-\pi_0). The reported estimates lie in [0.392,0.777][0.392,0.777], although passing the original separation check alone does not certify d≥dmin⁡d\ge d_{\min}. We conducted additional sensitivity experiments, varying dmin⁡d_{\min} from 0.005 to 0.4 on MNIST and Fashion-MNIST (20 seeds, four paths), while holding the score, source data, and target stream fixed (here all runs passed the stopping check). Relative to dmin⁡=0.02d_{\min}=0.02, the largest change in mean classification error was only 0.0035 percentage points for ALIGATOR and 0.049 for FLH–FTL.

We also derive a simple sufficient condition: if d^≥dmin⁡+2r\widehat d\ge d_{\min}+2r, where rr is the PU concentration radius, then d≥dmin⁡d\ge d_{\min} holds with high probability under our assumptions. The proof follows directly from the concentration bound ∣d^−d∣≤2r|\widehat d-d|\le2r. We will add this result and its short proof to the revised Appendix. Please also see our response to Reviewer 7CoU (W4) for relevant details.

Q2. Fixed-path interpretation of Theorem 2

Thank you for this important question.

For any prescribed prior path, Theorem 2 establishes a worst-case lower bound over a constructed family of PU models (rather than a pointwise lower bound for that path) as the reviewer correctly understands. More precisely, for any reference path π\pi, we construct three models Q0,QU,Q+Q_0,Q_U,Q_+, with π(0)=π\pi^{(0)}=\pi, such that, in the non-saturated regime,

E_{Q_j} \left[\sum_{t=1}^T (\hat{\pi}_t-\pi_t^{(j)})^2\right]$$ $$\geq c \frac{W_U(\pi)/n_u+W_+(\pi)/n_+}{d^2(1-\pi_0)^2}.$$ As you correctly observe, the alternative models have different prior paths. This is essential to the lower-bound construction: they induce identical target distributions, yet finite PU source samples cannot reliably distinguish them. Their path differences are proportional to $1-\pi_t$ and $\pi_t-\pi_0$, respectively, explaining the two weights $W_U$ and $W_+$. The alternative paths also have no greater total variation. Thus, the theorem shows that the path-dependent finite-source cost is unavoidable in the worst case around any prescribed path. It does not establish pointwise optimality for the reference model or minimax optimality among models sharing one identical path. We will clarify these quantifiers in Sec. 4 and the Appendix.
Reviewer_xuMmOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript studies the online class prior shift adaptation problem when the source domain only has positive examples and unlabeled (PU) data. The main conclusions are as follows: (1) The cumulative squared prior tracking error LTtrkL^{trk}_T can be decomposed into a time term, i.e., O~(T1/3VT2/3)\tilde O(T^{1/3}V_T^{2/3}), of the same order as the PN situation, and a finite source sample term, i.e., depending on the path weights WU,W+W_U, W_+ and the amplification factor (1−π0)−2(1-\pi_0)^{-2}. (2) Two lower bounds are given, corresponding to the above two terms, respectively. (3) Threshold adaptation is performed for a fixed fraction gg, a dynamic classification regret bound is provided, and experimental verification is conducted.

Critical strengths
  1. The problem is clearly defined, and the decomposition is insightful. There is an intuitive and technically clean statement that the error of the limited source sample accumulates along the target prior path, and the weight depends on the position of the path rather than only on VTV_T. The disappearance of the Δ+\Delta_+ term at π=π0\pi=\pi_0 and the degeneration to PN observation when π0=0\pi_0=0 is also very convincing.
  2. The theory is quite complete. The upper bound, two lower bounds, regret bound, and exact posterior special cases form a closed loop. The appendix explains the differences between PU and PN quite honestly, without exaggerating "equivalence".
  3. The writing is candid. Limitations, such as known π0\pi_0, fixed ϕ\phi, known dmin⁡d_{\min}, and a lack of a classification regret lower bound, are clearly stated.
Critical weaknesses
  1. The technological increment is limited, and the novelty description is overly strong. Specifically, the proof of Theorem 1 actually consists of only three steps: hoeffding controls the means of two samples, decomposes using (a+b)2≤2a2+2b2(a+b)^2 \le 2a^2 + 2b^2, and directly invokes Baby et al. (2023, Prop. 20). The time term is entirely inherited from existing work. Then, "PU does not change the time term exponent" becomes a constructive conclusion after being reduced to scalar mean tracking. The part of the classification regret (Prop. 5) is essentially three lines of triangular inequalities. Besides, Appendix A claims that these characterizations are "neglected in the literature", but it fails to compare the specific forms of source estimation errors in Bai et al. (2022) and Baby et al. (2023) item by item. The evidence is insufficient. The truly new content mainly consists of path-dependent weights and the lower bound of Theorem 2.
  2. The "necessity" statement of the lower bound goes beyond the applicable scope of the theorem. Specifically, Theorem 2 contains min⁡{1,⋅}\min\{1,\cdot\} and only matches the upper bound in the non-saturated region where d2(1−π0)2nu≳1d^2(1-\pi_0)^2 n_u \gtrsim 1. The manuscript does not compare this condition with the experimental configuration for verification. The estimator in the lower bound is given an exact target distribution, additionally, while the upper bound only uses the mean of ϕ\phi, and their information structures are different. Therefore, "each term is necessary" can only be understood as holding true under this information structure. The lower bound is taken as the worst result for each path on three constructed models, not the sup result of ΠT(V)\Pi_T(V) and the source model jointly. In the construction, ϕ\phi is Bernoulli, μ±∈[1/8,7/8]\mu_\pm \in [1/8, 7/8], and the paper does not discuss whether (1−π0)−2(1-\pi_0)^{-2} is tight under the general ϕ\phi and π0→1\pi_0 \to 1 limit.
  3. The presentation of the main experiment conclusion is selective, and the statistical evidence is weak. Specifically, some of the improvements in the experimental report may be interpreted as either a weak baseline, a small absolute difference, or a lack of significance tests. Besides, it would be better to have experimental verification in a real PU scenario, such as the protein screening mentioned in the abstract.
  4. The key assumptions remove the most difficult part of the PU problem. Specifically, the core difficulty of PU learning is the identifiability and estimation of the mixing ratio, while in this work, π0\pi_0 is known and will enter the reconstruction through (1−π0)−1(1-\pi_0)^{-1}. The manuscript does not indicate this premise, which may lead readers to overestimate the generality of the conclusion. Besides, I doubt that the selection of dmin⁡d_{\min} and ϕ\phi has almost no predictive power in the theoretical community in experiments.
Questions for authors
  1. Please compare the bounds of source estimation errors in Bai et al. (2022) and Baby et al. (2023) with those of your path dependence bounds, addressing each item individually. Clearly explain where the "path dependence" is particularly strong and weaken the wording of "overlooked".
  2. Add a distinct conclusion, such as a numerical demonstration comparing the upper bounds of different paths, i.e., near π0\pi_0 vs. far away, under fixed T,VTT, V_T.
  3. Clearly state the conditions for the non-saturation of the lower bound and compare them with the experimental configuration, i.e., n+=300,nu=800,d≈0.4–0.8n_+=300, n_u=800, d\approx0.4–0.8. Is d2(1−π0)2nud^2(1-\pi_0)^2 n_u much greater than 1 at this time? It should be explicitly verified.
  4. Design a control experiment. Fix T,VT,π0T, V_T, \pi_0, let the path oscillate around π0\pi_0, around 0.5, and around 0.9, respectively, and report the correlation between MSE and WU,W+W_U, W_+. Separately change nu,n+n_u, n_+ for the 1/n1/n scaling test.
  5. Add a scaling experiment for TT and VTV_T to verify T1/3VT2/3T^{1/3}V_T^{2/3}.
  6. Add an extension. The perturbation bound is when π0\pi_0 is estimated with ϵ0\epsilon_0 error, and conduct an experiment.
6 comments

We thank the reviewer for the detailed suggestions and helpful comments. We address each concern below.

W1 / Q1. Novelty and comparison with prior work

We agree that Theorem 1 inherits the temporal rate from Baby et al. (2023), and Proposition 5 uses a standard regret reduction. We do not claim novelty in these proof techniques. Our main new theoretical contribution is the finite-PU-source lower bound (Theorem 2).

Regarding prior work, Bai et al. (2022) bound source-induced bias in online risk estimation, while Baby et al. (2023) primarily assumes population source quantities and discusses empirical estimation error. Neither characterizes the path-dependent accumulation of finite PU source error.

Our analysis identifies the distinct weights WU=∑t(1−πt)2W_U=\sum_t(1-\pi_t)^2 and W+=∑t(πt−π0)2W_+=\sum_t(\pi_t-\pi_0)^2, showing that paths with identical TT and VTV_T can incur different finite-source costs. Theorem 2 establishes that this dependence is unavoidable in a constructed family, in the non-saturated regime.

We will clarify this distinction and soften the wording “overlooked".

W2 / Q3. Lower-bound scope and nonsaturation

Theorem 2 establishes that finite-source error is unavoidable over a constructed family of three models around any given prior path, even when exact target distributions are revealed. It does not establish a pointwise lower bound for each model or joint additive minimax optimality.

The lower bound matches the upper bound's source-sample and path-weight dependence in the non-saturated regime, where d2(1−π0)2min⁡(nu,n+)≳1d^2(1-\pi_0)^2 \min ( n_u, n_+) \gtrsim 1. Substituting the reported experimental values gives a minimum of 38.88, well above 1. However, the construction assumes d≤1/8d\le1/8, and thus this numerical check does not establish direct applicability to these benchmarks or universal tightness as π0→1\pi_0\to1.

We will clarify these qualifications in Sec. 4 and the Appendix, and appropriately narrow our necessity claims.

W3. Experimental evidence and practical scope

We thank the reviewer for this constructive comment. We would like to remark that complete results across five datasets and four paths appear in Appendix E.1 (Table 2) of the submitted manuscript. We conducted additional comparisons with strong simple baselines, including EMA and window averaging, and 20-seed experiments with paired bootstrap confidence intervals. Some baselines outperform our methods and we will report these results and clarify our conclusions in the revised Appendix.

Our PU extension of Bai et al. (2022)'s ATLAS achieves better accuracy (4.62% vs. 5.50%), but requires repeated access to raw PU source samples and online classifier-head updates. Extending its theoretical guarantees to finite PU supervision is highly nontrivial: existing Bai et al. (2022)' analysis relies on convexity and controlled risk-estimation errors, while PU risk reconstruction introduces persistent finite-source uncertainty as nnPU corrections would introduce additional bias. Our focus is adaptation without retraining or revisiting source data, with explicit theoretical guarantees.

Regarding protein screening, we have actually had discussions with proteomics researchers. However, adapting our assumptions and algorithms to biological settings, acquiring suitable data, and conducting biological validation require a separate interdisciplinary research project. It is beyond the scope of this paper.

W4. Known source prior and statistic selection

We thank the reviewer for this comment. The known source prior $ \pi_0$ is explicitly stated in Sec. 2 (Lines 124–126), where we also explain that estimating it from PU data is a separate mixture-proportion-estimation problem, citing relevant literature. Known class priors are standard in PU learning (e.g., Kiryo et al., 2017). Our focus is online adaptation to an unknown, time-varying target prior. This assumption is also acknowledged in Sec. 7 (Lines 480–481).

We are not entirely sure how to interpret the concern about the “predictive power” of $ d_{\min}$ and ϕ\phi. If the reviewer means their practical selection and the validity of the separation assumption, we agree this is an important limitation, already acknowledged in Sec. 7 (Lines 482–483). In our experiments, ϕ=g\phi=g is learned through offline nnPU training, and $ d_{\min}=0.02$ is fixed (Appendix E.1). We conducted additional sensitivity and score-degradation experiments, which we will include in the revised Appendix.

Q2. Numerical path comparison

We thank the reviewer for this suggestion. We conducted a controlled experiment fixing T=1000T=1000, VT=.2997V_T=.2997, while shifting the prior path from [0.05,0.35] to [0.65,0.95], with π0=0.1\pi_0=0.1. The path-dependent finite-source factor in our upper bound increases from 1.071×10−31.071\times10^{-3} to 2.120×10−32.120\times10^{-3}, while the empirical affine-map MSE increases from 0.254×10−40.254\times10^{-4} to 1.665×10−41.665\times10^{-4}. Additional experiments with translated oscillating paths on MNIST and AG News show the same qualitative dependence on path location. We will include these results in the revised Appendix.

Q4. Oscillating paths, correlations and source-size scaling

We conducted both experiments (20 replicates each). Fixing T=1000T=1000, VT=0.400V_T=0.400, and π0=0.1\pi_0=0.1, we varied the center of oscillating prior paths. On MNIST, FLH–FTL tracking MSE increased as the center moved from 0.1 to 0.9, with correlations of 0.9840.984 with W+W_+ and −0.942-0.942 with WUW_U across five reported centers.

Separately varying n+n_+ and nun_u on AG News yielded source-map MSE reductions consistent with the predicted W+/n+W_+/n_+ and WU/nuW_U/n_u contributions, though not establishing exact 1/n1/n scaling. We thank the reviewer for this concrete suggestion, and we will include both experiments in the revised Appendix.

As detailed in our response to Reviewer 7CoU (W4), we also derived a concentration-based sufficient condition that addresses the separation assumption for a fixed statistic.

Q5. Scaling in TT and VTV_T

Following your suggestion, we conducted additional experiments varying T∈{1000,2000,4000,8000}T \in \{1000,2000,4000,8000\} and VT∈{0.5,1,2,4}V_T\in\{0.5,1,2,4\} independently, under gradual and abrupt shifts, including a true-map control and 64 repetitions. For ALIGATOR with the known population map, the empirical log–log slopes of cumulative tracking error were 0.748/0.739 in TT (at VT=1V_T=1) and 0.413/0.816 in VTV_T (at T=8000T=8000), for gradual/abrupt paths, respectively. The observed slopes do not numerically match the nominal exponents. This does not contradict the theoretical guarantee, which is a worst-case upper bound rather than an exact scaling law for individual prior paths.

Q6. Perturbation from an inaccurate source prior

We thank the reviewer for this suggestion. A perturbation bound for an estimated source prior follows directly from the PU mixture identity, and we will add a short lemma to the revised Appendix. Specifically, when ∣s−p∣≤ϵ0|s-p|\leq\epsilon_0, the cumulative squared calibration bias of the raw prior observations admits an additional term of order ϵ02WU/(1−p)2\epsilon_0^2W_U/(1-p)^2, alongside a rescaling of the original bias term. This does not imply a full tracker-robustness guarantee.

We also conducted a 20-replicate AG News experiment varying the supplied prior around the true π0=0.1\pi_0=0.1. Source-map MSE is lowest at the correct prior among the tested values, while classification error is nonmonotonic. We will include these results in the revised Appendix. Please also see our response to Reviewer 7CoU (Q2) for further details on the sensitivity experiments.

Thank you once again for your suggestions and your time for careful reading. Hope we answered your concerns. Happy to address more if needed!

Reviewer_7CoUOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper helps a classifier adjust as the percentage of positives changes, using only positive and unlabeled training data. It estimates how negatives typically score, tracks the positive percentage in new unlabeled data, and changes the prediction cutoff without retraining. Under its assumptions, missing negative labels do not change the theoretical tracking rate but add error from limited samples. Across five image and text datasets, the method reduces average classification error.

Critical strengths

The paper addresses a meaningful problem of online adaptation with incomplete supervision (no labeled negatives). Its main strength is separating temporal tracking error from uncertainty caused by finite positive–unlabeled source data, while showing how the latter depends on the target-prior trajectory. Lower bounds showing that both error terms are unavoidable in general strengthen this theoretical contribution. The method is computationally efficient, adapting only the decision threshold without retraining or revisiting raw source examples. Experiments across five image and text datasets demonstrate consistent improvements over the static classifier, and the paper clearly states its assumptions and the scope of its guarantees.

Critical weaknesses

Estimating information about negatives from positive and unlabeled data, tracking a changing percentage with existing algorithms, and adjusting a prediction cutoff are already established ideas. The main new contribution is explaining how errors from the original data affect tracking over time and showing that some of these errors are unavoidable. This could be a useful theoretical contribution, but the paper needs to explain more clearly why this new understanding is substantial enough beyond combining known methods.

The paper shows that missing negative labels do not worsen the theoretical rate for following changes in the positive percentage. However, errors caused by limited original data can persist throughout deployment. Therefore, receiving more unlabeled examples does not guarantee that the overall estimation error will eventually disappear.

With fixed source data, the regret bound does not guarantee that average excess error vanishes over time. It generally compares only against the best cutoff of the same fixed model, and its optimality remains unproven.

The reported experiments do not satisfy the stated conditions for the main theoretical guarantee. These conditions require more positive holdout examples than the experiments use to ensure sufficiently accurate estimates from the original data. Checking that positive and negative scores appear sufficiently separated does not establish that their estimated averages are accurate enough. The authors should provide a guarantee that applies to their experimental settings or clearly explain this gap between theory and experiments.

The proposed trackers often estimate the class prior less accurately than a much simpler estimator. In Table 3, the estimate based on the previous batch, used by PU–UOGD and PU–ATLAS, has lower mean squared error than PU–ALIGATOR in all dataset and shift combinations, and lower error than PU–FLH–FTL in most combinations. The paper also omits a classification baseline that pairs this simple estimator with the same fixed classifier and threshold map. Consequently, the experiments do not establish whether the proposed trackers provide a practical classification advantage over this simpler alternative.

The paper omits several important baseline comparisons (though cited). The previous-batch prior estimator should be evaluated with the same fixed classifier and threshold map to isolate the benefit of the proposed trackers. Simple alternatives, including exponential moving averages and the full-history and fixed-window averaging methods studied by Wu et al. (2021), are also missing. A fixed threshold selected using the source data would help distinguish improvements from threshold selection from those due to online adaptation. Existing PU label-shift methods, such as (Mielniczuk et al., 2026) and (Nakajima and Sugiyama, 2023), would provide additional relevant comparisons through clearly specified online adaptations, with their data-access and computational requirements reported.

References:

  • Wu, R., Guo, C., Su, Y., and Weinberger, K. Q. Online Adaptation to Label Distribution Shift. NeurIPS 2021.

  • Nakajima, S., and Sugiyama, M. Positive-unlabeled classification under class-prior shift: a prior-invariant approach based on density ratio estimation. Machine Learning 2023.

  • Mielniczuk, J., Rejchel, W., and Teisseyre, P. Prior Shift Estimation for Positive Unlabeled Data Through the Lens of Kernel Embedding. AISTATS 2026.

Minor:

The paper distinguishes its contribution from concurrent work cited as “Anonymous authors (2026),” but this reference cannot be verified.

Anonymous authors. Online positive-unlabeled learning under continuous class-prior shift, 2026.

Questions for authors
  • The paper argues that error depends on where the positive percentage lies over time, beyond how much it changes. A direct test would compare two streams with equally large changes, where positives remain relatively rare in one stream and common in the other. The paper should also vary the numbers of original positive and unlabeled examples separately.

  • The method assumes that the original positive percentage is known, that labeled positives represent the full positive class, and that the characteristics of positives and negatives remain unchanged. It also assumes that the scoring function separates the two classes sufficiently well and that a suitable separation bound is known beforehand. These are legitimate assumptions for theoretical analysis, but the experiments do not establish robustness when they are imperfect.

Suggestion:

The paper would benefit from clearer explanations and improved readability, particularly in presenting the main ideas, assumptions, and theoretical results.

Tests with an inaccurate original positive percentage, biased positive examples, weaker scores, and small changes within each class would strengthen the practical case. A real positive unlabeled deployment dataset would also better support the motivating applications.

5 comments

We thank the reviewer for the detailed suggestions and helpful comments. We address each concern below.

W1. Contribution beyond combining established components

Thank you for raising this point, which is important for positioning the paper. Our main contribution is to characterize the statistical structure of online PU adaptation, particularly the finite-source uncertainty arising from incomplete source supervision.

In particular, we identify the path-dependent finite-source contribution.

\qquad W_U=\sum_t(1-\pi_t)^2,\quad W_+=\sum_t(\pi_t-\pi_0)^2,$$ up to the theorem's separation and confidence factors. This characterization reveals a statistical distinction not captured by total variation alone: two prior paths with identical $T$ and $V_T$ can have different source-estimation difficulty. Our source lower bound establishes that these path-dependent uncertainties are unavoidable in the constructed PU family, even when the exact target distributions are available. Thus, additional online observations cannot generally eliminate uncertainty from finite source data. The $\widetilde{O}(1+T^{1/3}V_T^{2/3})$ temporal rate is inherited from existing online-regression results. In the revised version, we will emphasize that our contribution is not a new online-regression algorithm, but a characterization of the persistent statistical cost of finite PU supervision, together with its information-theoretic lower bound. **W2. Persistent source error** We understand the reviewer's comment as referring to the finite-source term in Theorem 1, which need not vanish in the average tracking error as $T\to\infty$ when the source sample sizes remain fixed. We agree with this observation. Our result preserves the temporal tracking rate, but does not imply that the overall average tracking error vanishes with fixed source sample sizes. Indeed, characterizing this persistent finite-source uncertainty is a central contribution of our paper. We quantify its dependence on the target-prior path through $W_U$ and $W_+$, and establish a corresponding information-theoretic lower bound in a constructed PU family. Thus, increasing the number of online observations alone cannot generally eliminate uncertainty caused by finite source supervision. We will clarify this distinction in the revised manuscript. **W3. Classification comparator and optimality** The comparator is the best threshold of the same fixed score. Fixed source sizes do not generally yield vanishing average classification regret, and classification minimax optimality is unproved. Finite-horizon gains over static thresholds are compatible with these limitations.

W4. Theorem–experiment gap

We agree that the benchmarks do not satisfy the original sufficient condition r≤dmin⁡/4r \le d_{\min}/4. To address this, we will add a corollary using the alternative, empirically checkable condition d^≥dmin⁡+2r\widehat{d} \ge d_{\min} + 2r, where r=radPU(δoff)r = rad_{PU}(δ_{off}).

When the score and rescaling factor are fixed before calibration, the source concentration event guarantees ∣d^−d∣≤2r|\widehat{d}-d| \le 2r and ∥M^−M∥∞≤r\lVert \widehat{M}-M \rVert_{\infty} \le r.

The new condition therefore ensures d≥dmin⁡d \ge d_{\min}, r/d^≤1/2r/\widehat{d} \le 1/2, and d/d^≤2d/\widehat{d} \le 2, allowing the same form of ALIGATOR tracking bound.

Importantly, this condition is satisfied in our main experiments. For δoff=0.05\delta_{\mathrm{off}}=0.05, the required thresholds are at most 0.1910.191, while the observed separations satisfy d^≥0.392\widehat{d} \ge 0.392 across all reported runs.

We will include the corollary and verification of the experimental conditions in the revision.

W5. Previous-batch classification baseline

Thank you for this observation. We have added comparisons using the same fixed classifier and threshold map, including previous-batch estimation, EMA, and window-based averaging. The results show that these simple methods are competitive with ALIGATOR and FLH–FTL. We therefore do not claim a uniform empirical advantage. The key distinction is theoretical. The previous-batch estimator relies on a single noisy batch, so its average tracking error need not vanish even for a constant prior. In contrast, ALIGATOR achieves the variation-adaptive tracking rate without knowing VTV_T, and existing FLH–FTL theory provides an analogous guarantee.

We will clarify that the strength of these trackers lies in their variation-adaptive guarantees rather than uniformly superior empirical performance.

W6. Averaging, static controls and existing PU methods

Thank you for these suggestions. We have added the requested baseline comparisons.

First, we compare previous-batch estimation, EMA, full-history averaging, and fixed-window averaging using the same fixed classifier, PU holdout estimates, and threshold map as ALIGATOR and FLH–FTL. We also include both a fixed threshold of 0.5 and a source-selected fixed threshold to isolate the benefits of online adaptation. The results show that simple baselines are highly competitive, with EMA achieving the lowest aggregate classification error.

Second, we have conducted additional causal comparisons with TCPU (Mielniczuk et al., 2026) and a score-space DRPU variant (Nakajima and Sugiyama, 2023). These methods estimate the prior from previously observed target batches, without using target labels. We report their performance under different prior paths, together with data-access and computational requirements. We will include the complete results and implementation details in the revised Appendix.

Thank you again for your time and feedback. Happy to discuss more if you have questions and concerns!

Thank you for the response and the added baselines. My main concerns remain. The simple baselines (especially EMA) match or beat the proposed trackers, which leaves the practical benefit unclear. The questions on path dependence, separately varying the source sample sizes, and robustness to assumption violations were also not addressed, so I will keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of rebuttal and revisions

We sincerely thank all reviewers and chairs for their time, careful consideration, and constructive feedback.

We have uploaded a revised manuscript, with changes highlighted in color. The main theorem statements remain unchanged, and revisions to the main text primarily clarify their scope and point to additional material. Corollary 1 (Appendix C.6) follows from the existing analysis, Lemma 1 (Appendix B.3) addresses source-prior misspecification, and Appendix F contains experiments addressing specific reviewer questions. Here is the summary of our responses in the rebuttal.

  • The main contribution is a new statistical characterization of online adaptation under incomplete source supervision, rather than a new online tracking algorithm (EEDE W1/Q2; 7CoU W1–W2; xuMm W1–W2). While the temporal tracking rate follows existing online regression theory, our analysis reveals that finite PU source uncertainty depends on where the target-prior trajectory lies, not merely on how much it varies. In particular, two paths with identical horizon and total variation can incur substantially different source-estimation errors, with distinct contributions from positive and unlabeled source samples. Importantly, Theorem 2 establishes that this path dependence is information-theoretically unavoidable in the worst case over a constructed PU family in the nonsaturated regime, even when exact target distributions are available. Thus, our contribution identifies a persistent statistical limitation that temporal tracking guarantees alone do not capture.

  • The observable separation condition holds in all main benchmarks (7CoU W4; EEDE Q1; xuMm W4/Q6). Corollary 1 provides a sufficient condition that can be checked from data, and this condition is numerically satisfied in all main benchmark runs. Its high-probability guarantee remains subject to the stated sampling assumptions. Lemma 1 and additional experiments examine source-prior misspecification.

  • EMA is competitive, while PU-ALIGATOR provides variation adaptivity and the finite-source error decomposition is tracker-independent. (7CoU W5–W6; xuMm W3). Among fixed-score trackers, EMA achieves the lowest average classification error, which we explicitly acknowledge. However, with its preset step size, EMA is less accurate than PU-ALIGATOR on all five tested Bernoulli paths. Our PU source-error decomposition applies independently of the tracker, while ALIGATOR provides a theoretically optimal (up to logarithmic factors) variation-adaptive temporal tracking rate without knowing VTV_T. Thus, the framework accommodates different trackers according to practical requirements, without relying on uniform empirical superiority of any particular algorithm.

  • Controlled experiments support the theoretical predictions and clarify practical trade-offs (7CoU W6/Q1; xuMm Q2/Q4; EEDE Q4). At fixed TT and VTV_T, changing the prior-path location increases source-map error 6.6-fold. Separately increasing n+n_+ and nun_u reduces this error by 86% and 33%, respectively (Appendices F.3–F.4). TCPU and a score-space DRPU variant are also competitive, with no method best on every path (Appendix F.2). In the matched-prior comparison, classifier updating improves accuracy but requires repeated source-data access and 12.5–14.8 times the online computation (Appendix F.7).

  • The scope and limitations of the guarantees are clarified (EEDE W2–W3; 7CoU W3/Q2; xuMm W4). Classification regret is measured against the best threshold of the same fixed score, and fixed source sample sizes do not generally guarantee vanishing average regret. Extending our analysis to unknown source priors, score selection, biased positive labeling, and class-conditional drift requires additional identification and error analysis and remains an important direction for future work.

Thank you again for your helpful comments.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.