- 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
-
The paper addresses an interesting setting where online label-shift adaptation is performed without labeled negative source examples.
-
The separation of temporal tracking error and path-dependent finite-source error is theoretically meaningful. The corresponding lower bounds strengthen the contribution.
-
The proposed method is computationally efficient and does not require storing or revisiting raw source data during online adaptation.
Critical weaknesses
-
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.
-
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.
-
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 with class-mean separation . How is chosen in the experiments? Since 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 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
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 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 . The reported estimates lie in , although passing the original separation check alone does not certify . We conducted additional sensitivity experiments, varying 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 , 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 , where is the PU concentration radius, then holds with high probability under our assumptions. The proof follows directly from the concentration bound . 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 , we construct three models , with , 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.
We sincerely thank the reviewer for the thoughtful and technically insightful review. We address each point below.
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 WU and 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.
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, 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.