CP-POL + PPI: Conformal Guarantees in Partially-Observed Label Space
Authors: Christian NGNIE
Venue: Accepted by TMLR ()

Abstract: We study Conformal Prediction (CP) in the practical and challenging regime where labeled training and calibration data observe only a subset of the label space. In this setting, classical Conformal guarantees no longer control marginal risk and naive unseen labels detection methods are either overconservative or uninformative. We introduce CP-POL, a simple operational pipeline that couples Split CP over observed labels with a calibrated novelty test and integrates Prediction-Powered Inference (PPI) for finite sample population estimation. We provide a non-asymptotic theory that (i) proves Le Cam impossibility result: novelty test from features alone is hopeless without structural assumptions, (ii) derives tight finite-sample coverage decompositions that isolate the role of the non-conforming event $s(X)>q$, (iii) gives Dvoretzky-Kiefer-Wolfowitz (DKW)-based conservative estimators and anytime martingale analogues for the novel mass function $\pi_{nov}$, (iv) identifies practically meaningful structural conditions under which strong guarantees for novel region prediction hold, and (v) proves finite-sample PPI bounds that cleanly separate sampling fluctuation, trained model error and novel-mass effects. We validate the theory with reproducible simulations. All bounds are non-asymptotic and designed for immediate use in deployed monitoring pipelines.

Published in Transactions on Machine Learning Research (04/2026)
CP-POL + PPI: Conformal Guarantees in Partialy--Observed Label Space
Christian Ngnie Code For Africa, South-Africa
ngnie.christion@@yaho. christionn@coleefrfffiio
Reviewed on OpenReview: https: // openreview. net/ forum? id- GBy2BtBQKa
Abstract
We study Conformal Prediction (CP) in the practical and challenging regime where labeled training and calibration data observe only subset of the label space. In this setting, classical Conformal guarantees no longer control marginal risk and naive unseen labels detection methods are either overconservalive or uninformative. We introduce CP-POL, a simple operational pipeline that couples Split CP over observed labels with a calibrated novelty test and integrates Prediction-Poeeadd Inference (PPI) for finite sample population estimation. We provide non-asymptotic theory that (i) proves Le Cam impossibillty result: novelty test from features alone is hopeless without structural assumptions, (ii) derives tight finite-sample coverage decompositions that isolate the role of the non-conforming event s(X) > (iii) gives Dvoretzky-Kiefer Wolfoowizz (DKW)-based conservative estimators and anytime martingale analogues for the novel mass function Tnou: (iv) identifies practically meaningful structural conditions under which strong guarantces for novel region prediction hold, and (v) proves finite-sample PPI bounds that cleanly separate sampling fluctuation, trained model error and novel-mass effects. We validate the theory with reprodueible simulations. All bounds are non-asymptotic and designed for immediate use in deployed monitoring pipelines.
1 Introduction
Modern deployed classification systems increasingly face simple-but-hard reality: the list of label categories that appears at training time is rarely the full label space the system will meet in the wild. Indeed, labels can be expensive to obtain, categorics evolve and long-tailed or rare phenomena regularly create new labels. At the same time, practitioners demand calibrated and auditable behavior from models in such a way that when the system unsure, it must. either produce reliable set of candidate labels or clearly flag an input as 'NOVEL" that downstream decisions can proceed safely. This practical tension is the motivating problem of this paper.
Conformal Prediction (CP) is attractive foundation for uncertainty quantification precisely because it supplies finite-sample and distributional-free marginal guarantees with minimal modeling assumptions. However, the canonical CP setup builds on the implicit assumption that the calibration data covers the label space, such that the labels the system will see at test time are represented in the calibration data. When that assumption fails, the standard CP framework can no longer provide marginal guarantocs, and naive extensions either over-claim coverage or impose impractically large human-review burdens.
Related work spans several interconnected strands. CP has been extended in many directions (Vovk et al. 2005 Shafer & Vovk 2008: Angelopoulos & Bates 2023 Open-set and missing-mass formulations study uncertainu when new calegories appear or when generative oracles are used to probe support [Nooraui et al.) 2025 Quach et al., 2023). Partial-label Conformal constructions treat per-example candidate sets that contain the true class (Javanmardi al. 2023). a different data model from singleton annotated labels with partially-observed labels space. Recent work on calibrated semi-supervised and pseudo-label methods Zhoou et al. 2025). Rodriguez et. al. (2023) investigates how unlabeled data and model pseudo-labels can be

---

Published in Transactions on Machine Learning Research (04/2026)
safely combined with Conformal techniques. Parallel to this, the Prediction-Powere Inference (PPI) program [Angelopoulos et al. 2023b develops finite-sample methods that exploit learned models to reduce variance in M-estimation while using a labeled anchor to protect against bias.
This work unifies these perspectives by anchoring Conformal calibration to human labels (preserving Split Conformal guarantees on the observed subpopulation) using model scores to define a principled novelty region, and applying PPI framework produce provably conservative, finite-sample population estimates in partially-observed label space setting. First, we prove important fact which is without structural assumptions linking features to novelty, detection of unobserved labels from features alone is fundamentally unidentifiable. Second, we develop set of complementary positive results that are useful under realistic assumptions. We present finite-sample, non-parametric bounds allowing à practitioner to use labeled calibration anchor together with an unlabeled feature pool to obtain conservative lower and upper bounds on quantities of interest. Third, we identify structural separation conditions that make guarantees possible. The first is margin separation condition: novel-class examples uniformly acquire larger novelty scores than known-class examples above some margin, then a simple thresholding rule will reliably flag novel points and marginal CP coverage can be recovered. The second is stochastic dominance: if the tail of the novelty-score distribution under novel labels dominates the tail under known labels by a fixed factor, then we can translate an enpirieally-ooservedd calibration false-positive rate into a quantitative lower bound on novelty detection power. Fourth, we develop a comprehensive PPT analysis tailored to the partially-observed label space setting. We show how to frame population estimation task under PPI one-step correction and provide non-asymptotic guarantees in both batch and sequential settings.
The results deliver concrete toolkit for practitioners who deploy calibrated systems without priori exhaustive label categories. Equally important, the paper clarifies the limits of what can be known and in the limited knowledge setting, provide as safe operational response to collect labels or enlarge the calibration anchor rather than over-trusting model predictions.
2
Setup and notation
Let (X ~ P on X' x y with possibly large y. The observed labeled dataset D=
= {(X,, Y;))== contains
only a subset
Vobe == ty E y: 3i S i s.t. Y, = y}
Define the novel event Now = (Y & Vole) and novel mass nnov = P(Nov)
We train a model f(x)= = (z)))))ooo on a training split and hold out a calibration anchor Sealib of size m, exchangeable with Lest points. For E Vabs define the nonconformity scores:
a(x,y)== = (x) E [0,
s(x) = min a(x,y) 1 max (x)).
VeVa
y
Let q be the (1 (x) ar) empirical quantile of calibration nonconformities. The conformal set of known labels is
Cknown (2; q) {y E Vobs a(x,y) s g).
Crucial identity:
Cknown
(0: (x:g)=
Ø
s(x)
We will study coverage, detection and estimation properties for Cknown and the novel region S, := (x s(x) > (), and we will integrate PPT for population. parameters via M-estimators.
3 Theoretical framework
We present a unified framework that addresses both saiile-saple uncertainty quantification and population parameter estimation in partially-observed label space.
2

---

Published in Transactions on Machine Learning Research (04/2026)
3.1 Conformal Prediction with novelty detection
3.1.1
Prediction sets and operational procedure
We define the overall prediction set C(X) as follows:
Definition 3.1 (CP-POL Prediction Set). Por a lest sample X, the CP-POL prediction set defined as:
(X;
if Knoww (X; q) *
Ō(X)
{NOVEL} farg max (x()) otherwise (fallback)
if Cknown (X:q) q) = 0 and s(X)
This definition leads to the operational procedure:
Algorithm CP-POL: Conformal Prediction for Partially-Observer Labels
Calibration set Sealib size m, imputer f, miscoverage level a E (0, 1), novelty threshold t E [0, 1] Ensure: Prediction set ((z) for new test point
Require:
Compute calibration nonconformity scores a; = 1 (X,) for i Scalib
Set q = empirical (1 a) quantile of {a, km
For new x: compute Cknown g) = {y Vobs 1 1 s { if Cknown g) * then
5: return (xx) Cknown (z; q)
Prediction from known labels
else s(x) > then
Novelty score exceods threshold b Flag as novel
7: return (xx) (NOVEL)
8: else
return C(x)) (arg maxye (x)
Fallback top prediction
10: end if
3.1.2 Coverage guarantees and fundamental limits
Theorem 3.2 (Marginal guarantee for known labels (Vovk et al, 2005
Angelopoulos & Bates
2023 ). 1f
test sample (X, is ezchangeable with the calibration set Scalib and
Vobe: then:
(Y E (x; g) E Vons) 2 -
The overall coverage decomposes into known and novel components: Theorem 3.3 (Global Coverage Decomposition). For any novelly threshold I,
Pr Pr ((x)) 2 (1- (1-TTow Tnow) - ai) + noov TPR(t),
where TPR()) Pr(s(X) N) is the true positive rate for novelty detection.
Proof.
Pr(Y Ō(()) Pr(Y E Ō(x) -Nov) Tnov) Pr(V E Č(X) Now) .anv
= =Pr(Y E Oknown (X:4)
-Nav) (n- + Pr(NOVEL E Õ(X) Now) Toov
= =Pr(Y E Cuuwwn (X:q) -Nov) (1 Tnov) + TPR(()) Tnov-
We get the result by applying Theorem
3.2
Theorem 3.3 shows global coverage depends on TPR(t). We state below the detection impossible without linking test sample label novelty. To understand that fundamental limit from features alone, we employ Le Cam's two-point method.
3

---

Published in Transactions on Machine Learning Research (04/2026)
Lemma 3.4 (Testing Lower Bound via Total Variation). For any two distributions Po and P1, and any test A: - {0, 1}, the sum of Type. I and Type 11 errors is bounded below by:
+(A==))
PA).
In particular, if (Po Pı) 0, then no test outperform random guessing:
1) Pi
Proof. For any test A, we have:
= [PoLA = 0) PI(A= = 0)
2 sup (P((A) PI())
AEF
= (r,
Notation. For any joint distribution P on X' x y we denote by Px the marginal distribution of the feature X (i.e. (A) = P(X E A) for measurable A S X). Similarly, for E {0,1} we write P3 for a joint distribution on X x y and Pj.x for its X-marginal.
Theorem 3.5 (Fundamental Impossibility). For any measurable novelty detector A: X - (NOVEL, KNOWN) and any sample size n, there exist distribulions Po, Ps on X' x y with:
Po,x PI, (ídentical feature marginals)
Under Po: nnov = O, under P1: Tnov >
such that:
sup Pr(A(X) is incorrect) 2 2' jo P3
Proof. Let Px be any distribution on X. We define Po: X Px, with yo for some fixed 3/ E Vona
and P1: X Px where yo with probability Tnov 0 and Y Ynovel with probability noov > 0. By construction, Po.x Pı,x Px- Therefore, Srv(Pa,x, Pi,x) 0. By lemma 3.4 deduce (A(A(X)
NOVEL) + (i((()) KNOWN) 2 1, which implies max (Po(A(X) NOVEL), ((A KNOWN)) 2 Z ]
3.1.3 Positive results under structural assumptions
While Theorem shows that detection is impossible without assumptions, the following structural conditions, which are thcoretical, enable dotection. In practice, one can assess their plausibility using calibration diagnostics. For instance, comparing the empirical CDFs of novelty scores on calibration data (known) and an unlabeled pool (mixture) via two-sample tests can indicate separation. Moreover, the DKW lower bound for nuo (Thcorem 3.8) provides conservative estimate. A positive lower bound suggests that the mixture distribution differs from the known distribution, hinting at delectable novelty.
Theorem 3.6 (Perfect Detection Under Margin). IJ there exists E (0, such that s(X) almost surely for novel instances, and t < T, then TPR(t) and CP-POL achieves coverage at least 1
Proof. If for novel (X,Y) we have s(X) and t T, then every novel point satisfies s(X) t, hence TPR(() 1. The result follows from Theorem 3.3
Theorem 3.7 (Detection Under Stochastic Dominance). If there exist to and such that for all to:
dFnav d.F Fkknown (u) 2 X.
4

---

Published in Transactions on Machine Learning Research (04/2026)
then for 2 to:
A FFF(((t) A- 1-FPR(())112)))) -1-FP((()
TPR(t) 2
-
where FPR(1) PP)(s())>>() > E Votx).
Proof. For u 2 to, by definition of the likelihood ratio, 1 - Fnov (t) St dF dFnnvv 2 A Sf d'Fnnon (1 Fknown (t)). Rearranging using (PR(t) = FLov (t) and FPR(t) = Fknown (t) give the result.
3.2 Finite-sample estimation of Tuor and novelty detection performance
The estimation of [(noo) serves crucial purposes in CP-POL pipeline:
It quantifies the prevalence of novel labels at inference time, providing operators with a direct measure of how frequently the model encounters unobserved labels.
allows practitioners to understand and potentially adjust the actual coverage guarantees they can expect in practice 3.3
it helps determine the appropriate additional labeling budget.
3.2.1 Theoretical lower bound of Tnov
Assumc an unlabeled pool of size N, ii.dd drawn from Px. Let Fkuown(u) and Fmix(u), CDFs of nonconformity scores defined respectively on calibration and unlabeled pool. By the mixture identity,
Fui (1 F) known (u) + (n)) S (1 T)) Fknown (u) + n
for any u,
F Mmix (u) F known (u)
(3.1)
Fknown (1)
3.2.2 DKW-based finite-sample bounds
Theorem 3.8 (Finite-sample DKW lower bound for Tnov). Let 8 (0, such that 1- Fknowalu) > 0 and :: maxl
log(4/8) log(4/6)),
With probability at least - over the joint draw of calibration and unlabeled
pool, 2m
2N
Fmix(w) (u) Frnown (u) 2e
Fknown (u)
provided the denominator is positive.
Proof. For Lid. sample of size N and any 1 > 0, DKW inequality implies
Pr (sup Fx(x) F(x) m) S 2e 2Nn²
By applying DKW separately the calibration sample and unlabeled pool, with probability at least have simultaneously
8
log(4/0)
log(4/0) (3.2)
Pxnown (u)
Pknown (u) S
2m S e, | (u) Fmix (u)
Se.
2N
From equation
3.2 have with probability at least 1 5 the conservative replacements
Fiixx (u) > Fiix(u) -,
Fknown (u) < Fknowa (u) + e.
Substituting these into equation 3.1 yiclds,
(mixx (u) c) Fanowr (u) +
F Emix(u) Frnown (u) 26
π
1 Fknown (u) +c)
1 Prnown (u)
5

---

Published in Transactions on Machine Learning Research (04/2026)
3.3 Sequential anytime bounds for streaming unlabeled pools
In many deployed settings, unlabeled fealures arrive sequentially and operators want at every time & a valid lower bound I, for the novel mass and corresponding guarantees for TPR at pre-defined threshold to. The DKW is not uniform in time, so we replace it with time-uniform confidence sequenees for CDFs.
Let the unlabeled stream X2.... from Px; a threshold u E (0, 1], the scores 8; == s(X;) and the indicators Z = {(s; uj. Let the Bernoulli mean p E|Z]] and the empirical mean P. St/t where St Ei= Zz We want confidence sequences (L), (u( such that:
Pr (vt 2 1: L (u) & Fmii(()) - U,(u)) 2 1 -
3.3.1 Confidence sequences for streaming CDF estimation
Theorem 3.9 (Hoeffdingg-See -teye Confidence Sequence). Using error schedule & マ Hoeffding's 's inequality gives for each t,
66 with D 8c 8,
log(2/6;)
Pr Pt P>>
I o1,
2t
and a union bound over t gives the time-uniform statement. Therefore, a valid one-sided lower CS is:
log (2/02/).)
L Lmix (8) max 0,
2/
Theorem 3.10 [KL-Inversion Confidence Sequence (5) is the largest E [0. Pc] such that:
(Howard et al. 2021 )) A tighter one-sided lower CS
c(t + 1)
t. (L(pel))) log
where (L(x]) is the binary KL, divergence and e 2 is constant.
Theorem 3.11 Warianco-Adaptive Empirical Bernstein Confidence Sequence). Let V, = 1 Ei= (7₁ - - the sample variance. A valid one-sided lower CS is:
27, log (3/6) 7 (lo((//).) 3(t - 1)
LEB (6) =
where 8, for 2 2.
Comparison:
Hoeffding (Theorem 3.9 Most conservative, simplest implement, ideal for initial prototyping
KL-inversion (Theorem 3.10 root-finding
Tighter bounds for probabilities near or 1, requires numerical
Variance-adaptive, particularly effective for right-tail detection where variance is small, idcal for production use when computational overhead is acceptable
Empirical Bernstein (Theorem 3.11):
3.3.2 Time-Unifome Novelty Detection
Combining streaming CDF bounds with fixed calibration bounds:
Theorem 3.12 (Time-Unifomm Lower Bound for Tnow). With probability at least 1 8, for all t 2 simultancously:
Tnov 2 max (o, Le(u) Uknown (u) {
Uknown (u)
where Uknowa(U) ) = min 1, known (u) +
1ox(2/ 2/0cr)) and Le(u) can be any of the confidence sequences from 2mm
Theorems
3.9
3.10
8.17

---

Published in Transactions on Machine Learning Research (04/2026)
4 Prediction-Powered Inference (PPI) for partially-observed label space
Prediction-Powereed Inference introduced by Angelopoulos et al. 2023b leverages predictions from trained model to improve statistical efficiency while preserving valid fmileesample inference. In the standard setting, one observes: (i) large unlabeled sample {X,]==1 from target population, (ii) smaller labeled subsample (X,YY of size < N, and (iii) predictive model producing Y, for all i. PPI constructs estimator by combining a large-sample plug-in term based model predictions and a labeled-sample correction term that removes bias. For convex risk minimization problems, the authors define measure-of-fi fit term ma computed on the large unlabcled set using model predictions, and a rectificr Ag computed on the labeled sample. Their inference procedure is base on the quantity
mg + Ag.
Our goal is to extend this framework to the partially-observed label space, providing finite-sample guarantees for general M-estimators in both batch and sequential settings. The central idea is to leverage a trained model to approximate conditional expectations in estimating equations, calibrate via the labeled sample to remove bias and explicitly account for novel-label through [(noo)-
4.1 M-estimation formulation
Let Z = (X,Y) and suppose the target parameter 0* satisfies
([;02)0))] =.
If all labels were observed, the empirical classical M-estimator would solve
N
V (Z;;)) = O.
N
In partially-observed setting, observe X XN, and for each i an indicator & E {0, 1} denotes whether Y; is observed. We assume the sampling probability = =PG 1) is known.
Define
m( 0) = E. (Y. X:0) X =].
Following the PPI principle, we approximate m(x; 0) with predictive model mix;; 0) trained on the labeled sample.
We define the PPI contribution:
&
(,( m(X;; 0) + (V (x:
(4.1)
The estimator Ø solves
N N
17 0 =0
(4.2)
4.2 Connection to Standard PPI Formulation
Equation equation
4.2 algebraically equivalent the standard PPI contribution. Indeed, writing for the labeled set (size n),, and using n, n/N under uniform sampling, obtains:
N
N
( = N Σ
( A
obss (Y, X):0) mxx;;)))
N
IEC

---

Published in Transactions on Machine Learning Research (04/2026)
Thus, the empirical estimating equation coincides with the PPI quantity me Ag used in Angelopoulos et al. (Angelopoulos et al. (2023b)). In the special case of mean estimation, this reduces exactly to their closed-form PPI estimator:
(Y - ).) IEC
N
==1
Our formulation therefore generalizes standard PPI to arbitrary M-estimation problems under partial label observation.
4.3 simite-sample guarantees in batch setting
Assumption 4.1 (Boundedness and approximation). There exists a consland B > such that for all in neighbourhood of f and all (z,z) y)
Wyb x; 0) S B,
[[([;;) - -x;; 0)1 S A(x).
where A + [0, B] is measurable.
Assumption 4.2 (Jacobian invortibility). Let ((0) == E V V (Z;0)) denote the population Jacobian. There exist. conslants k. oo and L oo such that
|J(00) 1lop S K,
v),00) T.- I.-Täpschilz in near 0r
Assumption 4.3 (Sampling TPW cross-fitting). The data ((X,, No. Y. are i.i.d. The sampling mechanism satisfies:
(i) For each i, conditional on X₃ the labeling indicator &a is independent of Y;: & 1 Y; X,
(8) B[ei/ms X.] 1 a.s.
(tG) There erists Tiin with n, 2 Tuin a.s., hence Ei/m; S //Mmin a.s.
The muisancce 0m);0")) is constructed by K-fold cross-fitting and salisfies the uniform mean-bias control
sup B[mi!->)x;; (x; - m(x)) S nn.
with deterministic IN 2 0 and nn AN wher AN == 1/2 D. |l (Xx;00))))) - m( [1]
Theorem 4.4 (PPT finite-sample bound - batch). Under Assumplions 4-1 4.2 and
4.3
let 0 solve
== ({X;i0) & (Wobe (Y;, -) N Σ ()) =0
ni
Then for any 8 (0, 1), with probability at least 1 -,
1 10-011 0r 2 =
log (2p/5)
+ AN + B Tuow)
(4.3)
N
where C - 3 (1 1/ Tmin).
Discussion The finito-sample bound in Theorem 4.4 rests on thrce stated structural assumptions. First, the PW conditions (g .. Y X, known inclusion probabilities Ti and a positive lower bound Tmmn) are used only to guarantee unbiasedness of the IPW correction and to control the magnitude of the weights in concentration inqqualitics. In practice extremely small n, blow up the stochastic term, which reflected quantitatively by the (1 + 1/Tmia) factor in the constant C. Second, the Jacobian invertibility and local Lipschitz conditions provide the classical M-estimator regularity needed to convert uniform concentration bound the empirical

---

Published in Transactions on Machine Learning Research (04/2026)
PPI moment into bound on the parameter error via one-step mean-value expansion. The inverse Jacobian norm & therefore scales every error contribution and encodes local stability of the estimating equation. Third, the boundedness packages the cost of replacing conditional expectations with predictions: the averaged approximation error AN is the explicit price paid for using a plug-in model and is the only term in the bound that does not vanish automatically with N unless the model consistent fast enough. These three ingredients map directly onto the three terms equation 4.3 (i) a concentration term of order O(N-1/3) inflated by IPW weights, (ii) the model approximation penalty AN, and (iii) a novelty penalty proportional Wnov that captures irreducible bias when parts of the label space never observed during training. Unlike the classical PPT exposition which emphasizes convex-risk, grid-testing recipe built from + 4s, our statement treats general M-estimation moment and hence replaces convexity assumptions by the standard facobian/Lipschiie regularity while making the approximation error explicit and finile-sample. Operationally, this gives clear guidance: (a) use cross-fitting or honest sample splitting so that the nuisance term behaves like a higher-order remainder (we impose uniform mcan-bias control scparate deterministic bias from stochastic flueon)tion) (b) avoid designs with very small मi (or stabilize IPW weights) to limit inflation of the sampling term, and (c) monitor AN and naov when AN o(N-1/2) and Tnov o(N-1123 the bound collapses to the usual root-N asymptotic regime and the oracle PP1 variance is recovered. Conversely, if the model error dominates the sampling term the estimator's performance is governed by ÅN and the user should prioritize improving the nuisance model or expanding labeled coverage. Finally, the explicit constants the bound (notably = 3(1 1//mmi) and the Jacobian factor k) are conservative artifacts of the concentration proofs. They reveal qualitatively how design (through min)) and local curvature (through x) affect finite-sane sample behaviour and therefore provide immediate, actionable diagnostics for practitioners.
4.4 Sequential PPI with anytime guarantees
In streaming settings, we extend PPT provide time-uniform guarantees using martingale concentration. We assume the data arrive sequentially. At each time t, we observe Xt, then & and possibly Y, if & We maintain sequence of ostimators Or solving 1 + (.()r) = O. Under assumptions analogous to the batch case, oblaín both fixed-Lime and time-uniform bounds.
Let F,P) be a probability space, {Fihe20 a filtration with Fo = (0,2). For each 2 1, let the random objects
X N E (0,1), Y, & (0,1),
on FP). At time t:
(S1) Given Fi-1, the covariate X, is realized (not assumed --esurrblarr
(S2) Conditional on (I) the triplet (N, Ex) is drawn according to conditional distribution that may depend on (F--1, Xt).
(S3) The observed record at time t is O, = (Xe, & Y1ffs = 1)). The filtration is updated by Fi = (F (o().))
Assumption 4.5 (Weight unbiasedness). For every 2 the sampling indicator & and the inclusion probability na satisfy
E
F X, =
& LL1(Y (L, (f).
T
Equivalently P(E, = F,, Y, N,) ) = P(E. = F, =: क..
Assumption 4.6 (Nuisance conditional mean control). The nuisance estimator's 's conditional bias is controlled on avernge:
1
Σ [[mm(x;00)) 0*) Fr-1]] Ar.
T
Assumption 4.7 (Novelty frequency). Let the novelty probability at time t.
nnov. Pr(N, F(-1).
9

---

Published in Transactions on Machine Learning Research (04/2026)
There erists nno (0,1) with Toov, Tnov for all t.
Theorem 4.8 (PPI Sequential Estimation). Assume 4-1 4.2 4.5
4.6
and 4.7
Let the marlingale differences
A, = (0) (0) Fe-il satisfy ||,, S a.s. Define
TT T Im(x;00) ml m(x:000|1
Σ
and
T
T Fe-1] - (0)A, Fe-I)-
Vi((0) = max 1SJSP
E A (0)
Fized-time guarantee: For any T' 2 1, d (0, with probability at least 1 1 6,
(0+ log(2p/6)
B Blog(2p/0)
|0, 00 s 2k
+TT B Tnov
T
3T
Time-uniform guarantee: For any ò E (0, 1), with probability at least 1 - Ö, uniformly for all T 2 1,
0 1 2m (0*) log(2p/0r)
B Blog(2p/or)
Dr + B knov)
T
3T
where dr 66
Discussion The sequential theorem trades static concentration for predictable-variance martingale control and mirrors the same three-term structure while providing time-uniform (anytime) guarantees useful for soquential monitoring and stopping rules. Assumptionally; the streaming setup replaces i.i.d. sampling with conditional unbiasedness of the IPW weights relative to the filtration (so TT F,-1, = 1) and requires uniform boundedness of the single-step martingale increments apply Bernstein/ HooeeeiinnHoffdiingg..... type martingale incqualities. These conditions ensure the predictable variance process (r*) accurately summarizes the accumulated stochastic variability and permits self-normalized control of the empirical PPI moment. The online nuisance condition is the time-conditional analogue of cross-fitting: instead of independence require that the average conditional bias of the online or cross fitted nuisance be small (quantified by AT), which ensures the nuisance term remains a lower-order correction when Ay = OTT--//), Interpretationally, the fixed-time bound decomposes into (i) a martingale variance term scaling like 7-2/2 (with predictable variance VrrTT", (ii) a Bernstein higher-order term of order T-1, (iii) the averaged nuisance bias, and (iv) the novelty penalty B Tnov. The time-uniform variant obtained by the usual ôr scheduling (we use d7 65/ (*²()) and therefore yields valid uniform control over all stopping times-this is useful in practice for designing sequential tests or anytime confidence intervals that incorporate PPI augmentation. Practically, the sequential result implies the same operational guidelines as in batch: stabilize IPW weights to control variance inflation, enforce online debiasing / cross-fitting to keep nuisance bias negligible, and monitor novelty frequency since a persistent high noo produces a constant bias floor regardless of horizon. Limitations worth noting: if inclusion probabilitics the labeling mechanism can adversarially depend on history in ways that violate weight-unbiasedness our martingale control no longer holds and modeling of the sampling mechanism is necessary. Similarly, the boundedness assumption increments may be relaxed to sub-Gaussian tails at the expense of more elaborate pentictable-variance control. Overall, the sequential theorem extends PPI-style variance reduction to strcaming problems while preserving explicit inite-sample diagnostics (through Vr, Ar, Wnov, and Tiin) that pract itioners can compute and monitor in real time to understand when PPT provides reliable efficiency gains versus when the approximation or novelty terms dominate.
5 Empirical Validation
We conduct comprchensive experiments to validate the theoretical results (Thcorems 3.5 3.6 3.7
from our frameworks. They systematically examine detection power, finite-sample coverage, bias- variance tradeoffs and sequential derivations under conditions that mirror real-world partially observed label settings.
10

---

Published in Transactions on Machine Learning Research (04/2026)
5.1 Novelty Detection and DKW Bounds
5.1.1
Experimental Design
We simulate scalar novelty scores 8(X), with parameters spanning regimes from Theorem 3.5 impossibility detectable regimes. Calibration samples (m 5000) are drawn from known distribution Fknown Beta (2, 5) for realistic right-tail behavior, while unlabeled pools (N 10000) follow mixture (1 T) Finoww + nov with [0,0.15]. We examine three separation regimes, each corresponding to a theoretical condition:
to Theorems 3.6 3.7
No separation (Fnov = knnnww):: Tests Theorem 3.5
impossibility
Moderate separation (Fnov 3)) Tests Theorem 3.7
detectable regime
Strong separation (Fnov Beta(6, 2)): Validates Theorem 3.6
perfect detection
5.1.2 Results and Analysis
Detaction
m=5000, N-10000)
nat sep moderate strang
Detecttion power oPtiower bound +.0
0.1
Detection power true across separation regimes. Dashed line shows theoretical detection boundary.
3.8
on 113hicum-nn Co 1x11
calo hrnv 30 Oor wi'1
14:1
12
02
(b) Empirical CDFs illustrating separation regimes at 0.05, showing detectability conditions.
Figure 1: CP-POL detection performance validating theoretical predictions. (a) Detection power increases with separation strength and novel mass, confirming Theorems 3.6 3.7 Under no separation, detection power remains near zero, consistent with Theorem 3.5 (b) CDF separation enables detection under moderate and strong regimes.
Fundamental Limits: Under no separation, detection power remains near zero even for large n 0.15 and N 10000, empirically validating Theorem 3.5 impossibility result. This confirms that without structural assumptions linking features to novelty, detection from features alone is fundamentally limited.
11

---

Published in Transactions on Machine Learning Research (04/2026)
Separation Enables Detection: Under moderate and strong separation, detection power increases substan- tially with both knov and separation strength (Figure Tap. The strong separation regime achieves near-perfect detection (> 95% power) for Knov 2 0.05, demonstrating the practical relevance of our margin condition. Figure 1b illustrates the CDF separation underlying this detectability.
DKW Bound Performance: Our DKW-based lower bounds maintain validity across all conditions, with coverage exceeding 95%. The bounds show expected conservatism that decreases with larger sample sizes, making them increasingly informative in data-rich regimes while maintaining theoretical guarantees.
Threshold Selection and Effect on Calibration: In practice, the novelty threshold can be selected directly from the calibration scores to target & user-specified false positive rate (FPR) on known data. Concretely, for a desired FPR = q (e.g., E 0.001,0005,, 0.10)), set.
t = F-1
known (1 - q);
where Fknown is the empirical CDF of calibration scores. This choice directly impacts the overall coverage via Theorem 3.3 decreasing (i..., raising t) reduces the rate NOVEL flags on known data (lower FPR) but may decrease TPR, thereby affecting the second term the coverage bound. In our experiments, we find that q = 0.1 provides good balance, achieving TPR around 0.5 in moderate soparation and near 1.0 in strong separation, while maintaining high coverage on know classes.
5.1.3 Real-Data Validation on CIFAR-100 with Withheld Classes
We complement the synthetic experiments above with experiment on CIFAR-100, where we treat a subset of classes as observed and the remaining classes as novel. We train a ResNet-18 classifier on the observed classes and compute novelty scores on a held-out calibration split of observed-clase examples.
Novelty scores (MSP and Energy): We evaluate two widely-used uncertainty scores for novelty detection: (i) mazimum softmar probability (MSP), using novelty score max; (x), and (ii) the energy score, using novelty score E(x) with E(x) - log Σ, ex)(f)
Operational thresholding: Following the heuristic described in Sec. 5.1
we choose t by targeting a calibration-set FPR level E {0.01, 0.05, 0.10} and report the achieved TPR for detecting withheld classes.
C7N09-000 novelity
-75P
CIAR--20
ROC. PSS"
ROC: Energy
100m1
2a0 1700N
0.14
1447 Equel
2.0
2.6
0.00
0.4
2.4
0.2
0.
600
0.0
3.0
-2
-10
-26
-26
-24
-23
-22
-25
-22
-15
-13
-5
190
(a) Score distributions on CIFAR-100 for known
(b) ROC curves for novelty detection using MSP and Energy.
withheld classes (MSP and Energy).
Figure 2: CIFAR-100 withheld-class experiment. Both MSP and Energy exhibit partial separation bet ween known and withheld classes, illustrating the practical regime where novelty detection is feasible but imperfect; calibration-based thresholding enables an operational trado-off via target FPR.
As shown in Figure 2 both MSP and Energy scores exhibit partial separation between known and novel classes. Using the target FPR = 0.05, we achieve TPR of approximately 0.14 (MSP) and 0.15 (Energy). This non-zero detection rate confirms that CP-POL can provide actionable novelty signals even challenging real-world datasets, while maintaining valid coverage on known classes (as verified by coverage checks in
Section 5.2
12

---

Published in Transactions on Machine Learning Research (04/2026)
5.2
Comparative Analysis: CP-POL Classical Conformal Methods
We conduct comprehensive benchmark experiments comparing CP-POL against Split CP (APS) Romano et al.
2020)), ) RAPS (Angelopoulos et al. (2021)), TPS/Top-k (Sadinle et al. (2019) Jackknife+ (Barber
et al. (2021) on both synthetic and real-world datasets. These methods are representative of state-of-the-art conformal prediction. None them explicitly handle novel classes, serving as baselines to highlight the advantages of CP-POT.
5.2.1 Synthetic Experiments
We extend our synthetic novelty-score experiments to evaluate all methods under the three separation regimes (no separation, moderate, strong) with 150 trials per configuration. The experimental setup uses observed classes, 5 novel classes, 500 calibration samples, and test splits of 500 observed and 100 novel examples.
Table 1: Comparative Performance on Synthetic Data Across Soparation Regimes (a = 0.1)
(a) Coverage on Known Classes
Method
No Separation
Moderate
Strong
CP-POL (Ours)
0.948
0.948
0.948
Jackknife+
1.000
1.000
1.000
RAPS
1.000
1.000
1.000
Split CP (APS)
1.000
1.000
1.000
TPS/Top-k
1.000
1.000
1.000
Target (I-a)
0.900
(b) Novel detection rate
Method
No Separation
Moderate
Strong
CP-POL (Ours)
0.052
1.000
1.000
Jackknife+
0.000
0.000
0.000
RAPS
0.000
0.000
0.000
Split CP (APS)
0.000
0.000
0.000
TPS/Top-k
0.000
0.000
0.000
Target (1-a)
0.900
(c) Average Prediction Set Size (Known Classes)
Method
No Separation
Moderate
Strong
CP-POL (Ours)
1.00
1.00
1.00
Jackknife+
1.00
1.00
1.00
RAPS
1.00
1.00
1.00
Split CP (APS)
3.099
3.099
3.099
TPS/Top-k
1.197
1.197
1.197
13

---

Published in Transactions on Machine Learning Research (04/2026)
(a) Coverage on Known Classes
(b) Novel Detection Rate
1.000
0.975
Coverage Known Classes
0.960
Novel Detection Rete (TPR)
0.925
0.6-
0.755
0.600
orget jabtn
CPOCL (Des)
CANOL (D
0.525
TPST
Jacóvale-
jackknitee
0.800
0.0
Strong
Strong
(c) Average Prediction Set Size on Known
(d) Overall Coverage (Known Novel)
CP-PLL ICunl
Splt JAFSI
0.95
Avg. Set Size (Kown))
0.90
Overall Coverage
1.0
Tangd
ch-CCl (Ceno
0.5
0.75
(P-ARG)
TPS/kpp
0.0
0.70
Strong
Strong
Figure Comprehensive comparison of CP-POL classical conformal methods on synthetic data. (a)
Coverage known classes: All the methods maintain target coverage across all regimes. (b) Novel detection rate: Our method outperforms the other methods in covering novel classes in moderate and strong separation
regimes, but fails as the other methods with no separation regime, confirming Theorem 3.5 (c) Average set
sizes: All the methods produce relatively small sets. (d) Overall coverage accounting for novel detection.
Key Observations:
1. Coverage Validity: All methods, including CP-POL and the baseline approaches, maintain the target coverage rate (1-x=0.9) on known classes.
2. Novel Detection Capability: CP-POL demonstrates significant novel detection rates that vary with separation strength: perfect detection (100%) in moderate and strong separation regimes, and 5.2% detection in the no-separation regime (consistent with Theorem 3.5 detection is impossible without separation). In stark contrast, all baseline methods show 0% novel detection across all regimes, highlighting their fundamental limitation in open-world scenarios.
3. Set Size Efficiency: CP-POL, Jackknife+t, RAPS and TPS/Top-k achieve efficient singleton near-singleton predictions (avg. size =1-1.2) for known classes while maintaining coverage validity. Split CP (APS) produces larger prediction sets (avg. size =3.1) due to its differont calibration approach.
5.2.2 CIFAR-100 Withheld- Classes Experiments
We extend the CIFAR-100 experiment compare all methods using both MSP and Energy novelty scores. The setup withholds 20 classes novel, trains on 80 observed classes, and evaluates separate test sets.
14

---

Published in Transactions on Machine Learning Research (04/2026)
Table 2: Comparative Performance on CIFAR-100 Withheld-Classes (a 0.1, Target FPR=0.05)
Known Coverage
Known Avg. Set Size
Novel Detection
Method
MSP
Energy
MSP
Energy
MSP
Energy
CP-POL (Ours)
0.856
0.861
2.14
2.19
0.136
0.151
Jackknife+
0.709
0.709
1.00
1.00
0.000
0.000
TPS/Top-k
0.89
0.89
2.05
2.05
0.000
0.000
RAPS
0.709
0.709
1.00
1.00
0.000
0.000
Split CP (APS)
0.99
0.99
20.19
20.19
0.000
0.000
Target (1-a)
0.900
MSP Score
Energy Score
0.8
0.8
0.8
0.6
Srget (3-4 Known coverage Neval Dutection
Rate
Known Coverage hovel Detection
Teger (1-enD.9)
0.2
0.2
CH-3 (MSM)
CAPOL (EReng)
Figure 4: CIFAR-100 comparative results. CP-POL with Both MSP and Energy scores maintains high known covergae (>85%) and achieves measurable novel detection rate 14-15%), unlike baseline methods which fail completely at novel detection. Among baselines, known coverage varies but all show novel detection.
Key Observations:
1. Coverage Breakdown in Classical Methods: All baseline methods exhibit a complete failure in novel detection (0%). While known coverage varies, these methods are not designed to adapt to out-of-distribution b-novel classes, leading to compromised overall coverage when such classes are present.
CP-POL Robustness: CP-POL with both MSP and Energy scores maintains strong known coverage 86%). More importantly, it achieves non-zero detection rate 13..6-1..%). which validates our theoretical framework.
5.2.3 Discussion and Implications
Our comparative analysis conformal methods in open- woeldworld settings. Classical methods designed for closed-worts scenarios where all test labels reside within the calibration label space. In such settings, they successfully maintain coverage while optimizing set sizes. However, in open-world settings with novel classes, these methods maintain coverage on novel classes but fail to detect novel instances.
real-world and synthetic benchmarks reveals critical limilation of classical
In contrast, CP-POL addresses this limitation by explicitly separating the conformal guarantee from novel detection. This dual-capability approach allows it simultancously maintain valid coverage on known classes while detecting novel instances that appropriately scale with feature separation.
15

---

Published in Transactions on Machine Learning Research (04/2026)
For practitioners operating in environments where novel classes may appear, several practical considerations emerge:
CP-POL should be prioritized when both coverage guaranlees and novel class awareness are required, as its explicit novelty detection mechanism provides actionable signals about distribution shifts.
Classical methods should be used only when the absence of novel classes can be guaranteed; they provide safeguard against unknown categories.
Prediction sets should be interpreted differently in open-world settings: in CP-POL, the NOVEL flag replaces empty sets as the indicator for out-of-distribution samples, allowing efficient predictions for known classes while still identifying novel instances.
Realistic expectations should be calibrated: novel detection performance depends on feature separation between known and novel classes, and even optimized methods achieve limited detection rates in challenging cases like CIFAR- 100 (as Theorem 3.5 fundamentally limits detection without separation).
5.3 PPI Performance: Batch and Sequential Settings
5.3.1
Experimental Design
We simulate a realistic partially observed label setting with binary classification. Data generation follows:
X₂ NN Is)
(5.1)
X (ernoulli(o (O)).))
(5.2)
with 0 ~ (O0, 1), true prevalence Rs 0.3, and labeling probability m = 0.1. Imputer quality is controlled via additive noise: m, (X,) = o00 X, + Et), & ~ NN(0 =9) with T E [0.
We conduct 400 trials across calibration sizes m E 50, 100, 200, 400, 800, 1600, comparing:
Human-only: Uses only labeled data (bascline)
PPI: Our proposed estimator using all data with imputed labels
Oracle: Uses all true labels (performance upper bound)
5.3.2 Batch PPI Results
Error Reduction: Figure 5a shows PPI achieves 3-5x MSE reduction compared to human-only estimation for t S 0.5. AL m 400, PPI with т = 0.2 matches the MSE of human-only estimation with m 1500, demonstrating substantial sample efficiency gains, consistent with the bound in Theorem 4.4 where the dominant term scales (1//N)).
Imputer Quality Threshold: Figure 5b reveals R 2 0.25 as the ical threshold for PPT improvement, with performance degrading gracefully below this point. This provides practical guidance for when to deploy PPI in real applications.
Bias- Variance Tradeoff: Figure 5c validates Theorem 4.4 8 error decomposition. PPT dramatically reduces variance (by 60-80%) while introducing minimal bias, with bias controlled by imputation quality Ar. This confirms the core bias-variance tradeoff underlying our theoretical framework.
Imputer Bias Concentration and Novelty Gating: Figure 5d shows that imputer misspecification can be highly localized to novel classes while remaining negligible on obscrved classes and can translate into a noticeable bias of the PPI point estimate. Moreover, novelty gating concentrales the most biased novel points among the flagged set, indicating that the novelty score is aligned with the imputer failure region. However, because gating induces selection and can reduce effective labeled correction, does not automatically guarantee improved finito-sample PPI point estimates, a nuance captured by the noo term in Theorem 4.4
16

---

Published in Transactions on Machine Learning Research (04/2026)
MSE ratio vs imputer R~2 (m=400)
1.1
5.00
0200
Pepulation
19900 2016
(a) MSE vs calibration size for different imputer qualities
(b) MSE ratio (PPI/human-only vs imputtr Rº showing performance threshold.
(c) Bias-variance decomposition at
100 across imputte qualities.
0301
(d) Imputer bias in novel region.
Figure 5: Batch PPT performance validating theoretical predictions. (a) PPT achieves substantial MSE roduction with good imputers (r S 0.5). (b) Performance threshold at R = 0.25. (c) PPI reduces variance while controlling bias. (d) Bias concentraaed on novel samples can hurt PPI and gating/removing
predicted-novel samples can increase that harm.
5.3.3
Sequential PPI Results
Sequential PPI CS timewise coverage (per trial)
Sequential PPI CI widths (Hoettdinggsttte)
50
0.00
medan with
10 40
40
30
C3
20
10
0.05
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.3
500
1000
1250
1500
1750
2000
Proportio times covered prevalence trial)
(a) Distribution of per-trial coverage proportions across 200 streams.
(b) CI width trajectories with median and 10-90 percentiles.
Figure 6: Sequential PPI performance validating Theorem 4.8 (a) Timo-uniform coverage maintains validity
(mean coverage: 0.954). (b) Confidence widths follow theoretical O(L/VF) scaling.
Time- Uniform Coverage: Figure 0a shows sequential confidence sequences maintain the promised 95% coverage uniformly across time (mean coverage: 0.954, std: 0.021), validating Theorem 4.8 coverage guarantees. Coverage remains valid even during initial convergence, demonstrating robustness to non- stationary early estimates.
Convergence and Early Stopping: Figure db demonstrates that confidence widths follow the thooretical O(1/Vl) rate, enabling practical early stopping. Researchers can stop data collection when confidence sequences reach pre-specified widths, reducing labeling costs by 60-80% while maintaining statistical validity.
17

---

Published in Transactions on Machine Learning Research (04/2026)
6 Discussion
Our proposed CP-POL framework addresses the critical challenge of maintaining statistical validity when deploying models in environments with partially observed labels. By inlegraling split-conformal prediction with principled novelty detection and Prddiction-Poeeeee Inference, we provide finite-sample guarantees while explicitly quantifying the impact of unknown categorics.
6.1 Limitations and Interpretations
Exchangeability requirement The validity of conformal guarantees relies exchangeability with cali- bration set. In practical deployments, significant violations of such requirement. from distribution shift, geographic sampling biases or adversarial manipulations.
Fundamental detection boundaries Theorem 3.5 establishes that feature-based novelty detection re- quires measurable separation between known and novel distributions. Our empirical results (Figure D validate this thcoretical boundary: detection power remains negligible when feature distributions overlap completely. This underscores that reliable novelty detection necessitates either explicit geometric separation or additional structural assumptions. Practitioners should not expect a detoctor to work when the feature distributions are indistinguishable, an important sanity check when deploying novelty detection systems.
Conservative but Valid Bounds The distribution-free nature of DKW bounds and confidence sequences ensures robustness at the cost of conservalism. Figure illustrates this tradeoff: while bounds maintain coverage across all conditions, detecting small novel masses (Tnov 0.05) requires substantial sample sizes. Practitioners should view this conservatism as the price for assumption-free validity.
Threshold Selection and Coverage As shown in Theorem 3.3 the choice of novelty threshold t directly impacts overall coverage: higher t reduces FPR (fewer false alarms on known data) but may lower TPR, polentially decreasing the second term. In practice, one can tune / via a validation set to achieve a desired trade-off, or use the FPR-based heuristic described in Section 5.1 to set t from calibration data. Our CIFAR-100 results demonstrate that even with modest TPR ( 15%). CP-POL provides actionable novelty signals while maintaining high known coverage.
6.2 Relation to Other Conformal Methods for Out-of-Distribttion Detection
Several recent works extend CP to handle OOD or novelty detection. For instance, Bates et al. (0021 propose
a framework for testing for distribution shift using conformal p-values, and Cauchois et al. (2021 develop methods that know when they don't know. Our comparative analysis (Section 5.2) shows that while these methods maintain coverage on known classes, they do not explicitly flag novel instances; CP-POL fills this gap by coupling the conformal set with a separate novelty test. achieving non-zero detection rates in separable regimes. Moreover, approach is complementary: one could use CP-POL as wrapper around any base conformal method to add novelty detection.
6.3 Future Research Directions
Geometric approaches to label space characterization without complete category knowledge could provide more robust detection under weaker and more practical assumptions than margin or stochastic dominance. Variance-adaptive confidence sequences and higher-order corrections for DKW bounds are also promising directions for sharper inference.
6.4 Conclusion
CP-POL provides a principled framework for maintaining statistical validity in partially observed label environments. By making explicit the fundamental limits of detection, the costs of distribution-frt guarantees, and the dependencies imputation quality, our approach enables auditable and efficient deployment. The
18

---

Published in Transactions on Machine Learning Research (04/2026)
theoretical results are validated through extensive simulations and real-data experiments, demonstrating practical utility in open-world scenarios. The geometric perspectives outlined for future work hold significant. promise for advancing our ability to work with unknown and evolving category structures. As real-world systems increasingly confront the challenges of partial observability, frameworks enhanced by geometric insights will be essential for maintaining finite-sample statistical validity.
References
Anastasios N. Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution- free uncertainty quantification. Foundations and Trends in Machine Learning, 16(4):494-591, 2023.
Anastasios N. Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I. Jordan. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations (ICLR), 2021.
Anastasios N. Angelopoulos, Stephen Bates, Clara Fannjiang, Michael I. Jordan, and Tijana Zrnie. Prediction- powered inference. arXie preprint, 2023a. arXiv:2301.09633.
Anastasios N. Angelopoulos, John C. Duchi, and Tijana Zrnic. +pi++: Efficient prediction-powered inference. arXiv preprint, 2023b. arXiv:2311.0145..
Rina Foygel Barber, Emmanuel J. Candes, Aaditya Ramdas, and Ryan Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-507, 2021.
Stephen Bates, Anastasios N. Angelopoulos, Lihua Lci, Jitendra Malik, and Michael I. Jordan. Distribution- free, risk-controlling prediction sets. Journal of the American Stalistical Association, 116(536):2025 2040, 2021.
Maxime Cauchois, Saurabh Gupta, and John C. Duchi. Knowing what you know: Valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research, 22(1):1 42, 2021.
Steven R. Howard, Aaditya Ramdas, Jonathan McAuliffe, and Raffaele Mazza. Time-uniform chernoff bounds and confidence sequences for bounded random variables. Annals of Statistics, 49(5))1055-1080, 2021.
A. Javanmardi, S. Yusuf, P. Hofman, and E. Hüllermeier. Conformal prediction with partially labeled data. Tn Proceedings of the Twelfth Symposium on Conformal and Probabilistäc Prediction with Applications, COPA, PMLR, 2023.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT), 2009.
S. Noorani, K. Shayan, G. Pappas, and H. Hamed. Conformal prediction beyond the seen: A missing- mass mass perspective for uncertainty quantification in generative models. arXiv preprint, 2025. arXiv:2506.05497
Victor Quach, Adam Fisch, Tal Schuster, Adam Yala, Jae Ho Sohn, Tommi Jaakkola, and Regina Barzilay. Conformal language modeling. arXie preprint, 2023. arXiv:2306.
C. Rodriguez, Vitor M. Bordini, Sebastien Destercke, and Benjamin Quost. Self learning using venn aan-rbers predictors. In COPA / PMLR, 2023.
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candes, Classification with valid and adaptive coverage. In Advances Newral Information Processing Systems (NewrIPS), volume 33, 2020.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous sct-valued classifiers with bounded error levels. Journal of the American Statistical Associalion, 114(525):223 234, 2019.
Glenn Shafer and Vladimir Vovk. tutorial on conformal prediction. Journal of Machine Learning Research, 9:371-421, 2008.
19

---

Published in Transactions on Machine Learning Research (04/2026)
Joel A. Tropp. Freedman's incquality for matrix martingales. arXiv preprint, 2011. arXiv:1101.3039
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in Random World. Springer, 2005.
Xuanning Zhou, Hao Zeng, Xiaobo Xia, Bingyi Jing, and Hongxin Wei. Semi-supervised conformal prediction with unlabeled nonconformity score. orXiv preprint, 2025. arXiv:2505.21147.
A Appendix
B Detailed proof of Theorem 4.4
performing Taylor expansion around 0, we get.
N
N
Σ
(0") + (x())=+)()0000)))))
N
N
hence
N
8-8 = (~x(0
1
Σ ((*))
N
and consequently
N (0
10 - 0- (O)(0)-11ln))
(B.1)
By continuity of J and Assumption
4.2 there exists neighbourhood of 0* where 11(00~>1lop
2x; we have
i lies that neighbourhood so ||JN 'llop S 2x.
Let
m(x) = E[V obs xz 0²) X = x].
:= E(m((X)) R. Vobe (Y, X;0*)]
We decompose
N
N
1
Σ
(0*) =
(0)())) - 14) +
(A)
N
N
=T
By Assumption 4.3
E (.) x.] = (X,) + E E (Voss m) X. m((x))) + (m(X.) m(X.)) m(X)).
Taking expectations yiclds E ((0) Eim μ.
let a coordinate j (1,..... For unit i, let the scalar
Vi (0*) mdj--
From the definition of V
(0(0') - (m(()) m(x)) + & (Vora (Y, X.), - m(X))) + (m((x) - 1).
Taking the j-th coordinate and absolute value, then using triangle inequality gives
V < [,x) - m(X,) + T
(Y,, X,) - fxXx)) + [Im(X,)) - Hell-
(B)
Let bound each term using Assumption 4.1 and elementary bounds:
20

---

Published in Transactions on Machine Learning Research (04/2026)
[m()),) mxx))l ( B (by definition A(x) E [0, B)). This justifies the used inequality S B.
Wo (Y, X;) (XX))) < obs (Y, + [X,)] Σ + (lIm(X))) + [m((,) m(X))ll -
B+ BB B) 3B, since ||m(Xx)]| Voll (Y, X;)l X B and || ml B.
llm(X,) - Mlll - [|m( + |al|| & B + ||/||| & 2B, using |l (X,) s B and ||
S E v obs S B.
Combining these bounds into equation bound
and using Assumption 4.3 yiclds the deterministic per-coordinate
V S B
(3B) + 2B = 3B
min
min
Thus each coordinate of (,((") - is almost surcly bounded by the explicit constant
M := 3B + [))
(C)
Tmin
For fixed coordinate j, the scalars (Vis)= are i..d. mean-zero and bounded in [-M, By Hocffding's inequality,
N Σ
2N222
Nr²
Pr
Vis 21 & 2exp
ΣN (2M))) = 2xx
N
2M
Applying union bound over j = 1,... p and setting the right side to 8 give that with probability at least. 1-8. 5,
N ViJ
2 (2g//2/0))
max SS
Σ
S My
f=1
Consequently, we obtain the vector concentration bound
[Ti = | Σ (0))') - 1)|
(og(2p/))
M
(B.2)
with probability at least 1
We have: P V oot (Y,X)1(N -0} + obs (Y, =1}
By construction the first term vanishes; therefore
|a] < E V I(N =}]] S B Tnov-
(D)
The empirical average of the muisance error satisfies deterministically
N
Σ (m(x))-mXX.)) m(xi))
<
N (m(X)) m(X.)l = AN.
(E)
Assumption
4.3 further guarantees the population mean-bias 7n < AN.
21

---

Published in Transactions on Machine Learning Research (04/2026)
Combining (A), equation
B.2
(D) and (E) gives with probability at least 1 - 8,
1
2 2log(2p/0)
Σ L (0())
V
+ĀN B nov
N
N
Inserting this into equation
B.1 and using (0)
(1)0)) llop S 2x yields
log 2p/0)
10 0- s 2x MM
AN + Wnov)
N
C Detailed proof of Theorem 4.8
By definition, # Ei (.(Or) = O. Performing Taylor expansion of 0 + + Et= v.( around 0*, there exists
matrix -= So ( E Vo s0Or -0))) ds such that
1 Σ T
V.(0*) -+(00) 0.)
(C.1)
ie
Or -0))
1 Σ (8')
For any T:
- T E(V.(0)) Fi-1] + 1
1
(0))
(0*)
(MoTTE; M (0*) a {Fi} --a--migaanae......
Let the coordinate-wist processes M.,j E'= (t.) for = 1..... Each M. is real-valued martingale with:
Bounded increments: |Ar < B, since ||| < B
Predictable quadratic variation: (M.))r = E F(-1]
Freedman's inequality Tropp 2001 gives for each fixed j and any 17 > 0:
x/2
P Mr. 2 and (M.))r S V2(( < 2exp
2( Bn/3)
Applying the same incquality to Myr leads to
172 ((+) + Bn/3)
P P(|Mr,12n and (M.r)r S V2((1)) s 2exp
Let's take the right-hand side equal to (/p) and solve for n, This yields to
2p
Blog 2
n= V 2Vr log
8 3
Union bound over j = 1,..., P yields:
2p
B log
2p
P max
Mrral S (Vr log
+
8
2 1 - d.
1515p
8
3
22

---

Published in Transactions on Machine Learning Research (04/2026)
Dividing by T gives the martingale contribution bound
T
1 T
Σ
(0))))
s 1 T
(2277(0))088
2p
5
+
B log 2p
3
8
(C.2)
t=
Let A, (()) Fi-1]. Let's rewrite
= (1- (Xx) + f Mobs (X).
Condition on (Fi-1, Xi) and use of unbiasedness yields:
B((1 (x)) [r = 0,
E Lt v V Yo,
Fr-1, = E[V (Y,, X,) Fr Xi).
Then,
A, obb (Y,, F(-1).
But,
V (v, Ft-1] Vobe (,, (,), = 1 F2-1]
B Vosa (,,, X,) = 13 [2-1].
And,
E V. obo (Y;; =0} Fi-1] E E V obs (Y,, Xt) Fi-1, N1 = 0] Pr(N, = 0 Fi-1, Fi-1]
E Paov X,) (X.)) m(x:) [[-1)],
Then,
E V obs (V,, =E((1 Pnov (x)))m(Xx) Ft-1] + (V. = [F-1)
(Ye, = 13 Fr (V, (Yr, =1 Fr- < B nov.t
T
T
T
ト
1
Σ
4.
S
B[m((x))
B Tnoe.
T
By the muisance-control assumption and Tnov, Anov
1
Σ A S AT B Anov.
(C.3)
1=1
Combining equation
C.2 and equation
C.3
we obtain that with probability at least 8,
T Σ i.
(0
s 1
(2227(00) log
4p B Bog
4g o
Ar + B Tnov-
(C.4)
8
Denote the right-hand side by sT for brevity. From the Taylor identity equation
(r'0") - -())--))-- 1 Σ
(8')
Thus on the event where Tx*) is invertible,
+ T + 1000
100 - 0-1 < ())
-11
23

---

Published in Transactions on Machine Learning Research (04/2026)
By contimuity of (() at 8* and Assumption 4.2
there exists ro such that
sup 1m
|1(0)-
for 10 -0-1 Fos the integrand in (Or) lies within the ball where J() is close to J(0"), and therefore
|| - J(O 2
Consequently (000)) J(0))) 1/2 S 1, and by the Neumann series
(rr) -11 '1 1- |1(0 J(8M)] S 1 K (1/(2x))
|
n
2x.
Hence, on 0r - 0*1| < ro, we gel
|00-- 8' 2 21 (
2p B Blog o
+ Dr B Tnov)
For Part B, we apply the above argument for each T with or 65 Let
A, == - -,W, Fi-1),
Mr :=
Σ
A
t=1
: [
Sr A
t=1
and the predictable quadratic variation matrix
WT Σ BA Fr-i.
Vy Amax
By decomposition,
T
ΣΣ v.((') 7 Mr + Sr.
1
7
We use the predictable-term bound
| S STr Ar B Tno--
We have | < B a.s. Vector Freedman yields: for any fixed T and any > 0,
n72 P (11MM11 m (V s 2pexp( 2( + (Bn)/3)
Solving this inequality for n with v = Vy and target failure probability dr gives
2p 0T
B
2p Dr
WT = 2VT log
+
log
3
and therefore for each fixed T,
P( S mr) 2 1- 8r.
Let 8y 65/(n?222) Then D 87 8. By the union bound,
P(VT 2: |M < mr) 2-
Σ 8x
8.
24

---

Published in Transactions on Machine Learning Research (04/2026)
On the event (VT: || I mor
have for every T:
1 Σ
1
t (0000)
1 "T
+ Ar + B nnov-
T
From the Taylor expansion we have:
1 0 (1) T Σ (1(()) + Fx (0r - -0)).
let To > 0, by contimuity of J(0) at 0 we have sup 1 ri ( S 1. For given T the bound
2x
and for |0, 8*1l S ro, the integrand in (r()r) lies within the ball where J(.) is close to [(0),, and therefore
(0r) - J(OT) 2k
Consequently [J(0))- -(0))) - 1/2 1, and by the Neumann series
|
(0r) 1- |J((8))~1
J(A*)l S n (1/(2x) 2xx -1 (1
Hence, for every T such that 0r 0* S ro. we get
|0r 0* - 2x
IT
+ + B knov):
T
Combining the union-bound event with the incquality above yiclds: with probability at least 5, the time-uniform bound
22 log (2g(2//))) log(2p/67)
0 - 0-11 < 2k
+ AT + B Tnov)
T
holds simultaneously for all such T.
D Width scaling of the stitching Hoeffding CS
Using the polynomial scheduler & = C5/t2 (with C= 7² and Σiz1 1/F = x2/6) we obtain
log( (1({))
log 23
2 2log 1 + log(1/(C6))
2t
2t
2t
Hence
OV logt + log(1/6)
E,
t which the claimed scaling. The logt term is the stitching (uniformity) price; constants depend on the particular scheduler chosen.
KL-based (Chernoff) time-uniform CS and proof E
Define the binary KL divergence
(l()lv)) = x log T. + x) log
1 - x
y E (0, 1),
y
y
and let. Pr be the empirical mean of / i.i.d. Bernoulli observations with true mean For any fixed and any E [0, P.] the Chernoff method (Bernoulli tail) gives the exact bound
Pr (pt 2 4) < (t e)exp( (k(()))))
(A)
25

---

Published in Transactions on Machine Learning Research (04/2026)
Equivalently, for any u >> O,
Pr (kl(fellp) 2 u) S 11
(B)
Now fix an overall error budget 8 E (0, 1) and allocate per-time budgets f6:b21 with Eez1 6, = For a particular time t, pick
Ur log ((t + 1)/6,)
6
By (B) we have Pr (kl(pellp) 2 ue) S 8,. Thus with probability least de,
kl(prlpp) < ur-
As kl(-Il-) is continuous and strictly increasing its second argument when the first argument is fixed and smaller than the second, may define for observed Pr the lower bound
(6)) suplg E [0. kk((eellg) S log((t + 1)/6))}
By construction, for fixed we have Pr(p < L (6:)) S 8, Applying the union bound over
Pr 32 :: p (6)) - > 8==6.
121
Therefore the time-uniform guarantee holds:
Pr
Vt 2 1: p (..( 2 11-6.
F Equivalence of the method-of-types (KL) tail bound and the KL-event bound
Recall the two useful forms that appeared in the text:
(A) One-sided Chernoff. For any fixed 2 1, any g E [0, and Bernoulli mean p,
Pr (p: 2 q) s (t 1) exp( kl(lp))))
Pr
(A)
where Po is the empirical mean and kl(-ll-) is the binary KL divergence.
(B) KL-event bound. For any u > 0,
Pr (kl(Fellp) 2 u) S (t tM
(B)
Let & f0.1.....f t} and write p. = k/t. The exact probability mass is
Pr(fe = k/t) = ()) -
The ofthod-of-types (or Chernoff / Sanov bounding) inequality gives
( (1 (1-pp)) p)- < exp( tkl(k/tlpp).
(1)
The event (kl(p.lpp) 2 u) is the union of the events (p. k/t} over all indices & with kl(k/tllp) 2 Applying (1) and union bound over at most (++ 1) possible k values yields
Pr (k(l((ulpp) 2 u)
Σ
exp( (kl(k/(lp)) S (1+1)e TM,
k: 21
which is exactly (B).
26

---

Published in Transactions on Machine Learning Research (04/2026)
Fix E [0.1]. q P, then for any 2 the function > kl(x]ppp is nondecreasing (g. 1] (KL is convex and has positive derivative for x > p). Hence
(ee 2 g) S (kl(p))pp) 2 kl(glp)))
Applying (B) with = kl(gllp) gives
Pr(pt 2 q) S Pr (kl(f)llp) 2 kl(g)pp) = (t + cxp( tkl(q)p)).
which is (A). (If p. the one-sided bound (A) is asymptotically trivial for the upper tail because Pr(p: g) =
G Empirical-Bernstrr Bernsteen
time-unifone CS
A commonly used one-sided ampirical-Bernstern style lower bound is
2 log(3/6))
7log(3/51)
L. po: -V t
(G.1)
3(t 1)
where = -i (2: - p.)3
the sample variance and 6, is the per-time error budget.
The bound is derived by combining Freedman's martingale inequality with a concentration control for the variance estimator. Concretely:
For fixed i, Freedman's inequality yields that, for any fixed predictable variance proxy ii
20, log((/n))
clog(1/n) S 17.
Pr
pr P
p2
+ t
for an absolute constant
Replace the unknown predictable variance by the empirical variance V. The randomness of Va is handled by paying a small additional factor the failure probability. One convenient way is split 7) into three equal parts and apply (i) Freedman with a grid of variance values, (ii) a union bound over the grid, and (iii) a Chernoff toooofff/Hfffdinggg control for the grid membership of V.. This standard machinery yields the particular numeric constants in equation G.I the displayed formula is nixtuure-f-Bernntein Bernstein style bound found in the literature (see Maurer & Pontil (2009) a representative mixture-of
empirical-Berrstennn.CC Howard et al. for related time-uniform empirical- Bernstein-CS constructions).
Finally, to make this time-uniform we allocate per-time budgets 6, and apply union bound or a mixture-martingale instead of naive union bound. Using the splitting 5, yields a time-uniform guarantee:
Pr 3t 1: p L EB (5))
8c.
Choose {8eh221 with E, 5. Then the family {L. EB (8+) Ja defined by equation
G.1 satisfies
Pr Vt 2 1: p
EB (6.) 2 1 - 8,
provided the (standard) technical condition 2 2 holds for the denominators. The constants (2,7/3,3 in the formula) come from carefully carrying constants through Freedman + peeling: they are conservative but work well in practice. For references and refined constants see Howard et al. (2021) and Maurer & Pontil 2009).
27

---

Published in Transactions on Machine Learning Research (04/2026)
H DKW Hoeffding connection for calibration CDF.
The Dvonttly-Kicooo-oofoittt (DKW) incquality applied to the empirical CDF of indicators ((s(X,) s u) yields, for a calibration sample of size m and any 8eal E (0, 1),
Pr sup Fuup/Fknowu(t) Fknown (x)o > c) S 2e 2mm2?
Solving for with right-hand side deat gives the one-sided upper bound
Uknown (u) min {1, Fknown(u) (u) log (2/22/0a))
2m
This expression equivalent applying Hoeffding's inequality to the single Bernoulli random variable (xx(X) u} and then taking supremum. Thus writing the calibration bound DKW is correct and not mismatch with Hoeffding; the DKW inequality can be derived by applying Hoeffding to all thresholds and mmion-bounding. For operational purposes the displayed Uknown(u) is the standard conservative one-sided calibration bound.
Why (0) is martingale difference and relation to assumptions.
The filtration Fi-1 contains all information to time t - 1 (past features X1:-11, past calibration indicators S1--11 past labels observed when & = 1, and any randomness used to construct out-of-fold imputers). For a fixed parameter 0,
(0) = き, (0)
By construction (,) is Fr-meauurable and satisfies (0) [F-1] i.c. 1Eis (2)0))21 martingale. The martingale property requires that the PPI contribution (0) be measurable w.r.t. F, and the conditional expectation be well-defined and predictable given Ft-1.
28


Reviews:
[{"review_id": "KS1r8IpxKF", "reviewer": "Reviewer_EdpU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper tackles the problem of preserving the coverage of conformal prediction's sets for observed classes while detecting when a sample at deployment does not belong to the observed classes (\"novel\"). The proposed approach is based on utilization of a novelty detector. Without distributional assumptions, a negative result is presented. Positive results are presented when building on distributional assumptions for defining the novelty detector (of limited practicality). Other extensions include deriving bounds on the novelty probability and integration with Prediction-Powered Inference (PPI) framework.\nThe empirical section is mostly based on simulations rather than real data.", "claims_and_evidence_yn": "No", "claims_explanation": "The readability should be improved. There should also be more discussion on the relation to other CP methods that consider out-of-distribution / outlier detection. The experiment section should be improved as well.\n\nSee the comments below.", "audience_yn": "Yes", "audience_explanation": "This paper tackles a well motivated problem: preserving the coverage of conformal prediction's sets for observed classes while detecting when a sample at deployment does not belong to observed classes (\"novel\"). The negative result is useful. The positive results have their merits, though I am not sure about their practicality.", "requested_changes": "- The readability should be improved.  In particular, discuss more the implications of the theoretical results.  \nRemind the reader of notations when they are used. \nDefine P_{0,X} and P_{0,X} in Theorem 3.5.\n\n- The conditions for the positive results in Section 3.1.3 do not seem to be verifiable (or hold) in practice when the distributions are unknown.\n\n- The PPI Section 4 is hard to follow, and lacks discussions on the motivation, assumptions and results.  \nWhere in the PPI paper is there a formula similar to Eq. 4.1?  \nWhere in the PPI paper is it stated that \"The PPI estimator θ_hat solves 1/N Psi_hat_i(θ_hat) = 0\"?  \nGive preliminary details on PPI and carefully explain the relation of your results to existing PPI works, including explanations of your assumptions and those made in earlier works.\n\n- Formally show the stated claim on the detectable regimes in Section 5.1.1.\n\n- In Figure 1a, I do not see the \"Dashed line shows theoretical detection boundary\".\nDiscuss more how the results in Figure 1 corroborate the theory.\n\n- There is no discussion or even pointer to Figure 2 (CIFAR experiments).\n\n- The experiments do not explain well how to set the novelty detector and do not examine its effect on the coverage and other properties of CP.\n\n- You should also discuss the relation and compare with other CP methods that consider out-of-distribution / outlier detection.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gbKMtXTxsB", "reviewer": "Reviewer_fPN7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the limitation of classical Conformal Prediction (CP) in scenarios where training and calibration data observe only a subset of the full label space. It introduces CP-POL, a framework that combines Split CP with a calibrated novelty test and integrates Prediction-Powered Inference (PPI) for population estimation under these conditions. The authors provide a non-asymptotic theoretical framework including impossibility results and finite-sample bounds, which are validated through reproducible simulations.\n\nThe main contributions of this paper can be summarized as:\n* This paper establishes a fundamental impossibility result using Le Cam's two-point method, proving that novelty detection from features alone is unidentifiable without structural assumptions.\n* Identifies specific structural conditions (margin separation and stochastic dominance) that allow for valid coverage guarantees and novelty detection.\n* Derives non-asymptotic, finite-sample lower bounds for the novel label mass ($\\pi_{nov}$) using both batch (DKW-based) and sequential (martingale-based) approaches.\n* Provides an algorithm named CP-POL, a practical pipeline for practitioners to deploy calibrated systems that can safely flag novel inputs rather than over-relying on model predictions", "claims_and_evidence_yn": "Yes", "claims_explanation": "The proposed claims are supported by a combination of rigorous mathematical proofs and targeted simulations. The theoretical bounds (e.g., Theorems 3.8, 4.4, and 4.8) are derived with detailed proofs. The empirical results in Section 5 directly mirror the theoretical regimes: Figure 1 confirms the impossibility result versus the detectable regimes under separation, while Figures 2 and 3 demonstrate the MSE reduction and coverage validity of the PPI and sequential estimators. The evidence is clear and convincing within the scope of the presented simulations.\n\n[Strengths]\n* This paper addresses the \"simple-but-hard reality\" that deployed systems often encounter labels not present during training.\n* The authors provide a comprehensive theoretical treatment from impossibility proofs to tight, non-asymptotic coverage bounds.\n* The framework is applicable to both batch settings and streaming/sequential data environments through time-uniform confidence sequences.\n* The paper clearly separates the fundamental limits of what can be known from the positive results achievable under realistic assumptions\n\n[Weaknesses]\n* Dependence on Structural Assumptions: The \"positive results\" for novelty detection rely on assumptions like margin separation, which may be difficult to verify or may not hold for complex, high-dimensional datasets\n* Synthetic Evaluation: The empirical validation is restricted to simulated data; the lack of testing on real-world \"long-tailed\" or \"open-set\" datasets limits the immediate assessment of its practical performance.\n* Threshold Sensitivity: While an optimal threshold ($t=0.7$) is identified in simulations, the paper provides limited guidance on how a practitioner should adaptively select this threshold in diverse real-world applications.", "audience_yn": "Yes", "audience_explanation": "The paper intersects several active areas of machine learning research: Conformal Prediction, Open-Set Recognition, and Statistical Inference (PPI). Its focus on providing \"auditable behavior\" and \"finite-sample guarantees\" aligns with TMLR's interest in reliable and theoretically grounded machine learning.", "requested_changes": "1. For experiments in Sec. 5, the paper's reliance on synthetic Beta-distributed scores may oversimplify real-world feature overlaps. It is suggested to include at least one experiment on a real-world dataset (e.g., ImageNet or a text classification task) where certain classes are withheld during calibration to simulate the partially-observed label space.\n2. In Sec. 5.1.2, the novelty threshold $t$ is fixed. It is better to discuss or provide a heuristic for selecting $t$ based on a target False Positive Rate (FPR) on the calibration set, which would make the pipeline more operational for users.\n3. While Fig. 2b discusses imputer $R^2$ thresholds, more detail on how CP-POL behaves when the imputer is biased in the \"novel\" region would be beneficial.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hji62x2nHI", "reviewer": "Reviewer_6D52", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Strengths**\n\n1.The study innovatively integrates split conformal prediction, novelty detection, and prediction-powered inference, providing a unified framework with finite-sample guarantees and theoretical rigor for partially observed label spaces. \n\n2.Through core theories such as the Le Cam impossibility result and structural separation conditions, it clearly defines the boundaries and feasibility of novelty detection, while simulation experiments effectively validate the method’s practicality in both batch and sequential settings.\n\n**Weaknesses**\n\n1.The paper’s Le Cam impossibility result in Theorem 3.5 and structural separation conditions rigorously define the limits of novelty detection, a key contribution. However, the practical verifiability of structural assumptions may be overlooked. \n\nHow can practitioners confirm uniform margin separation or stochastic dominance in real-world data where novel labels are unobserved? \n\nThe empirical validation uses simulated Beta distributions, but no guidance is provided for messy, high-dimensional real data, e.g., images, text,  where feature-novelty links are opaque.\n\n2.The experiments rely on simulated data, including scalar novelty scores and binary classification, that simplify key real-world challenges. However, no evaluation on natural distribution shifts, the covariate shift between calibration and test data, which violate exchangeability, the core assumption of conformal guarantees. \n\nFurthermore, similar to W1, novelty detection is tested on synthetic Beta distributions, but real-world novel labels often differ in semantic or structural ways, e.g., a new object class in computer vision, that may not align with scalar score separability.\n\nOverall, this work is good. However, personally, the theoretical work should establish certain connections with the issues of practical concern or provide valuable perspectives.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical derivations and simulation experiments have initially verified the arguments to be proved.", "audience_yn": "No", "audience_explanation": "This paper is overly theoretical, with insufficient discussion on the data types and scenarios of practical concern, and may fail to attract the attention of relevant researchers.", "requested_changes": "Please complete the discussions listed in the contributions.", "broader_impact_concerns": "N/A", "additional_comments": "Please refet to the Summary/Changes.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)