- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies online conformal prediction under a hard cumulative miscoverage constraint that must hold at every time step. In an i.i.d. setting and under suitable geometric assumptions on the coverage–efficiency frontier, it establishes matching bounds on cumulative excess prediction-set size: , , and , depending on the evaluation criterion. It also provides algorithms that attain these rates and analyzes the additional cost of implementing them using empirical ranks when the score distribution is unknown.
Critical strengths
-
The authors provide a rigorous theoretical analysis of the efficiency cost of enforcing hard cumulative miscoverage constraints, establishing matching upper and lower bounds under the stated assumptions.
-
The paper develops nontrivial algorithms that attain the optimal rates and quantifies the additional efficiency loss introduced by empirical threshold estimation.
Critical weaknesses
-
The practical motivation for the hard constraint is unclear. Much of the conformal prediction literature studies marginal coverage, finite-sample high-probability guarantees, or asymptotic error control. The paper does not sufficiently explain when a deterministic restriction on cumulative miscoverage at every time step is necessary. The document retrieval example does not convincingly establish this need. The protocol also assumes that each label becomes available before the next prediction.
-
A substantial gap remains between the assumptions and practical prediction models. Assumption 2 requires more than ordinary smoothness: the threshold rule must attain the population coverage–efficiency frontier at the target miscoverage level. Scores produced by learned models may not satisfy this requirement. The connection of current theory to existing methods in online conformal prediction and adaptation is not explained. I am not convinced why the oracle analysis in this paper is potentially useful in practice.
-
The presentation has substantial clarity and organization problems. First, several symbols serve unrelated roles: denotes both prediction-set rules and the constant in Assumption 2; appears in the notation for both expected set size and random seeds; and denotes both a barrier potential and a threshold-size curve. The logic can be much improved. I found frequent defensive qualifications and abrupt transitions, which make the arguments difficult to follow.
Questions for authors
-
Could the authors provide a concrete application in which the cumulative miscoverage budget must hold at every time step and labels are available before the next prediction? In the retrieval example, controlling the total number of omissions over a specified period seems more directly motivated. What operational requirement makes every-step, pathwise control necessary?
-
Could the authors systematically revise the notation, terminology, and organization? In particular, could they: (a) Resolve the overlapping uses of notation; (b) Explain Algorithm 3, the empirical-rank implementation, in Section 4.2, before discussing Assumption 2. (c) Present Table 1 earlier to clarify the structure of the results.
-
The efficiency upper bounds rely on Assumption 2. Under what conditions do commonly used nonconformity scores, such as residual or scaled-residual scores, satisfy this assumption?
5 comments
Response to Reviewer WzcX (2/2): residual scores and practical implications
W2/Q3: Under what conditions do commonly used nonconformity scores, such as residual or scaled-residual scores, satisfy Assumption 2? Why is the oracle analysis potentially useful in practice?
A3: Assumption 2 requires minimum expected set size at the target coverage within the chosen family, including randomized rules. Proposition 9 in the updated version gives sufficient conditions for correctly specified models : positive bounded , bounded symmetric noise independent of , and all responses inside the bounded response domain.
Residual scores. With constant noise scale and a noise density strictly decreasing away from zero, residual intervals minimize expected length among all prediction rules at the same coverage: they contain exactly the outcomes above a common conditional-density cutoff. A positive, Lipschitz density of near the target quantile supplies Assumption 2's smoothness.
Scaled-residual scores. If the density of is nonincreasing throughout its support, expected length is convex in miscoverage, so randomizing thresholds cannot reduce it at the target coverage. With the same local density condition, Assumption 2 holds within this threshold family. These intervals generally do not minimize length among all prediction rules when varies.
Learned models. These conditions are unverified for Housing. Let be the score's excess expected size above the chosen optimum at target coverage. Proposition 4 in the updated version adds at most to the upper bounds, assuming i.i.d. data, a fixed score with a continuous distribution, and a locally Lipschitz derivative of expected size with respect to miscoverage near . Thus preserves the order if the proposition's constants stay bounded. Proposition 5 bounds the gap from independent data against the best mixture of that score's thresholds and the full and empty sets. Housing's simultaneous 95% upper bounds, –, are too wide to certify the required gap.
Why the oracle analysis is useful. Under the lower-bound conditions, the quota's cost persists with perfect distribution knowledge. The upper bounds are attainable without that knowledge using past-score ranks under the fixed-score and efficiency conditions above. Evaluation time also matters: Corollary 1 shows that expected final-time cost forces expected cost at some earlier time.
Connection to ACI. ACI has a coverage guarantee with an additive error allowance ([1], Proposition 4.1), and its asymptotic average interval length has been studied under oracle assumptions ([2], Theorem 3.1). Our question is the cumulative excess set size required by the hard quota. Proposition 2 in Appendix H shows that any fixed additional-error allowance retains the lower bound on the largest expected cost, under our lower-bound assumptions. Proposition 3 in the updated version applies this to ACI. Under its additional population-quantile and endpoint conditions, fixed-step ACI also has an asymptotic linear lower bound on cumulative excess size. This does not predict the measured finite-horizon widths.
Measured practical cost. In Housing, ACI violates the running quota in every tested run, by up to 12 errors. The full-set guard removes all violations and increases mean width by 2.9% for Ridge and 4.1% for Extra Trees. Identical proposals and error updates within each pair isolate the quota's cost without assuming a population-optimal score.
References
[1] Isaac Gibbs and Emmanuel J. Candès. Adaptive Conformal Inference Under Distribution Shift. NeurIPS 2021.
[2] Margaux Zaffran, Olivier Feron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive Conformal Predictions for Time Series. ICML 2022.
Thank you for this example and modifications on notation. A real-data example maybe better, rather than a thought experiment. I will maintain my positive score.
Response to Reviewer WzcX (1/2): motivation and presentation
Thank you for your insightful review and positive assessment of our paper. We address your concerns below.
W1/Q1: Could the authors provide a concrete application in which the cumulative miscoverage budget must hold at every time step and labels are available before the next prediction?
A1: Consider an inspection station that processes one part at a time. Before inspecting each part, a model predicts a shortlist of possible faults, and the operator prepares the tools for those faults. The inspection reveals the actual fault before the model predicts for the next part. A longer shortlist takes more preparation time. If the shortlist omits the actual fault, the operator needs one emergency tool setup to finish the current part.
Suppose the station starts with zero emergency setup credits and receives one just before each of parts 10, 20, 30, and so on. Unused credits carry over, and each omission consumes one credit immediately. Thus, after every part t, the cumulative number of omissions must satisfy Mt≤⌊t/10⌋. For example, omissions on parts 12 and 17 would be within the budget of two by part 20. At part 17, however, the first credit has already been spent and the second has yet to arrive. A high-probability guarantee would still allow such a shortage on some runs.
The retrieval example illustrates the tradeoff between omissions and shortlist size; the inspection example shows why the budget may need to hold after every prediction.
We added this example to the introduction and Appendix I.5. When feedback can arrive up to d rounds later, Proposition 7 in the updated version extends the guarantee by rotating among d+1 copies of the controller. Each copy receives its previous label before predicting again, and their individual quotas imply the overall quota.
W3/Q2: Could the authors systematically revise the notation, terminology, and organization?
A2: We have revised the notation and organization as follows. The constant in Assumption 2 is now c+, the random seed is ϖt, and the quadratic Barrier function is Φt. Proposition 6 uses ϖt′ for its separate mixing coin. Prediction-set rules remain C, expected size remains VD(C), and the threshold-size curve remains h(q). These replacements apply throughout the statements and proofs.
Table 1 now ends the introduction. Section 4.2 explains Algorithm 3 before introducing Assumption 2, which relates miscoverage to expected set size. Algorithm 3 selects a threshold from stored scores, randomizing between adjacent ranks when the desired rank is noninteger. This avoids systematic rounding toward larger sets without requiring the score distribution. Section 5 states the question each experiment answers, and Section 4.6 explains the implications for existing methods.