acceptodds
Under review as a conference paper at ICLR 2027

The Price of Hard Coverage Constraints in Online Conformal Prediction

Abstract

Conformal prediction provides distribution-free uncertainty quantification, but in sequential deployment, standard coverage guarantees can still allow substantial fluctuations in the number of realized errors over time. We study an online setting in which prediction sets are produced one round at a time and the cumulative number of miscoverages must stay within a prescribed budget throughout deployment. Such a hard coverage guarantee can be enforced by enlarging prediction sets, but how much additional prediction-set size is fundamentally necessary remains unclear. We characterize this unavoidable efficiency cost over prediction rounds. Remarkably, the cost persists even with i.i.d. data, a known score distribution, and perfect knowledge of the population-optimal prediction set. Under suitable regularity conditions relating coverage and prediction-set size, we determine the minimum cumulative excess prediction-set size required by any online method satisfying the hard coverage constraint. This minimum cost is for expected cost at a fixed time known in advance, for the largest expected cost over all fixed times up to , and for the expected worst realized cost when the evaluation time is chosen in hindsight. We further show that these rates can be attained using past scores, without knowing the score distribution. Thus, even perfect statistical knowledge does not make sequential reliability free.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Online Learning, Conformal Prediction, Hard Coverage Constraints

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_WzcXOpenReview ↗
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: Θ(log⁡T)\Theta(\log T), Θ(T1/3)\Theta(T^{1/3}), and Θ(T)\Theta(\sqrt T), 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
  1. 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.

  2. 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.

  3. The presentation has substantial clarity and organization problems. First, several symbols serve unrelated roles: CC denotes both prediction-set rules and the constant in Assumption 2; VV appears in the notation for both expected set size and random seeds; and hh 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
  1. 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?

  2. 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.

  3. 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
AuthorsOpenReview ↗

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 tt, the cumulative number of omissions must satisfy Mt≤⌊t/10⌋M_t \le \lfloor t/10 \rfloor. 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 dd rounds later, Proposition 7 in the updated version extends the guarantee by rotating among d+1d+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+c_+, the random seed is ϖt\varpi_t, and the quadratic Barrier function is Φt\Phi_t. Proposition 6 uses ϖt′\varpi'_t for its separate mixing coin. Prediction-set rules remain CC, expected size remains VD(C)V_D(C), and the threshold-size curve remains h(q)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.

AuthorsOpenReview ↗

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 Y=m(X)+σ(X)εY=m(X)+\sigma(X)\varepsilon: positive bounded σ(X)\sigma(X), bounded symmetric noise independent of XX, 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 ∣ε∣|\varepsilon| near the target quantile supplies Assumption 2's smoothness.

Scaled-residual scores. If the density of ∣ε∣|\varepsilon| 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 σ(X)\sigma(X) varies.

Learned models. These conditions are unverified for Housing. Let Δα\Delta_\alpha be the score's excess expected size above the chosen optimum at target coverage. Proposition 4 in the updated version adds at most 2TΔα2T\Delta_\alpha 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 α\alpha. Thus Δα=O(T−2/3)\Delta_\alpha=O(T^{-2/3}) preserves the T1/3T^{1/3} 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, 0.1580.158–0.1750.175, 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 O(log⁡T)O(\log T) expected final-time cost forces Ω(T/log⁡T)\Omega(\sqrt{T/\log T}) 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 Ω(T1/3)\Omega(T^{1/3}) 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.

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

This paper investigates the fundamental efficiency cost of enforcing hard cumulative miscoverage constraints in online conformal prediction. By introducing a population coverage–efficiency frontier and an excess set-size decomposition, the authors establish three optimal asymptotic rates: Θ(log⁡T)\Theta(\log T) for terminal expected cost,Θ(T1/3)\Theta(T^{1/3}) for the maximum expected prefix cost, and Θ(T)\Theta(\sqrt{T}) for the expected worst realized prefix cost. The paper proposes Counting and Barrier controllers, together with an empirical-rank implementation that does not require knowledge of the score distribution. The theoretical results are complemented by synthetic experiments and regression experiments on California Housing.

Critical strengths
  1. The paper addresses a fundamental limitation of conventional online conformal prediction: marginal or long-run coverage guarantees do not prevent substantial temporary violations of a cumulative miscoverage budget. This is an important and well-motivated theoretical problem.
  2. Theorem 1 provides an elegant decomposition connecting coverage control and prediction-set efficiency.
Critical weaknesses
  1. Assumption 2 requires the score-threshold predictor to attain the randomized population frontier at the target miscoverage level. This is a strong condition for learned nonconformity scores and is not generally guaranteed by standard conformal prediction procedures. Discrete or convexified piecewise-linear frontiers may also fall outside the combined assumptions. Although the paper provides examples satisfying these conditions and explicitly discusses their limitations, the California Housing diagnostics do not establish that the assumptions hold for the evaluated models. Consequently, the applicability of the main Θ(⋅)\Theta(\cdot) characterizations to typical learned predictors remains uncertain.
  2. The theoretical setting excludes several central challenges of online conformal prediction. The main results assume i.i.d. observations, and the exact empirical-rank analysis additionally requires a continuous score distribution. In contrast, many motivating online applications involve distribution shift, model updates, tied scores, or delayed feedback. Although isolating the intrinsic constraint cost under stationarity is theoretically justified, it remains unclear whether the proposed methods retain meaningful efficiency guarantees in these more realistic settings.
Questions for authors

Assumption 2 requires the threshold family to attain the population frontier at the target level. How can this condition be verified or approximated reliably in practice? Could the authors develop a correction based on mixtures of learned thresholds or provide practical guarantees in terms of an estimable frontier-approximation error? In particular, under what conditions can the additional TΔT\Delta term be prevented from dominating the intrinsic sublinear constraint price?

6 comments
AuthorsOpenReview ↗

Response to Reviewer T4oA (1/3): target-gap bounds and learned scores

We thank the reviewer's insightful feedback. We address your concerns as below.

W1/Q1. Assumption 2 requires the score-threshold predictor to attain the randomized population frontier at the target miscoverage level. This is a strong condition for learned nonconformity scores. Under what conditions can the additional TΔT\Delta term be prevented from dominating the intrinsic sublinear constraint price?

A1: A fixed positive score gap can dominate the sublinear constraint cost. However, the original rates are preserved if this gap decreases sufficiently fast with the horizon.

Let Δα\Delta_\alpha denote the score's extra expected set size above the chosen family's optimum at the target coverage. Proposition 4 in the updated version bounds the additional cost by 2TΔα2T\Delta_\alpha, under i.i.d. data and the stated continuity, boundedness, and smoothness conditions. For Counting and Barrier using past-score ranks, we obtain

  • Expected cost at TT: O(log⁡T)+2TΔαO(\log T)+2T\Delta_\alpha.
  • Largest expected cost over t≤Tt\le T: O(T1/3)+2TΔαO(T^{1/3})+2T\Delta_\alpha.
  • Expected largest realized cost over t≤Tt\le T: O(T)+2TΔαO(\sqrt{T})+2T\Delta_\alpha.

Thus, Δα=O(log⁡T/T)\Delta_\alpha=O(\log T/T), O(T−2/3)O(T^{-2/3}), or O(T−1/2)O(T^{-1/2}), respectively, preserves the original order, provided the assumption constants remain bounded. For a fixed positive gap, the average expected excess size converges to Δα\Delta_\alpha for these implementations (Remark 6).

Learning a small gap. Lemma 8 in the updated version shows that a fitted conditional density with uniform error at most η\eta yields Δα=O(η2)\Delta_\alpha=O(\eta^2) under its density and cutoff conditions. Both sets must attain the target population coverage, and the benchmark includes all prediction-set rules. Appendix I.2 further proves an O(1/n)O(1/n) gap averaged over training in a controlled two-group model. Consistently, Table 9 shows that the mean gap decreases from 5.43×10−35.43\times10^{-3} at n=64n=64 to 2.08×10−52.08\times10^{-5} at n=16,384n=16{,}384 observations per group, using population thresholds for exactly 90% coverage. If the smoothness constants remain uniformly bounded, n≳T2/3n\gtrsim T^{2/3} preserves the expected-prefix bound. The gap estimate alone does not establish this smoothness.

AuthorsOpenReview ↗

Response to Reviewer T4oA (2/3): confidence bounds and threshold mixtures

W1/Q1 continued: How can this condition be verified or approximated reliably in practice? Could the authors develop a correction based on mixtures of learned thresholds or provide practical guarantees in terms of an estimable frontier-approximation error?

A2: Checking the gap. Proposition 5 in the updated version provides an upper confidence bound using independent i.i.d. data for a fixed score with a continuous distribution, accounting for uncertainty in both miscoverage and mean set size. The benchmark is the best mixture of that score's thresholds and the full and empty sets. Comparison against all prediction-set rules additionally requires a lower bound on their optimum. For the same benchmark, this confidence bound can replace Δα\Delta_\alpha in Proposition 4's 2TΔα2T\Delta_\alpha term, on the same confidence event and under its local smoothness condition.

In the Housing experiments, estimated gaps are at most 0.00293, but simultaneous 95% upper bounds range from 0.158 to 0.175, too wide to certify the required small gap. Thus, the Housing diagnostics do not establish Assumption 2. The bound's O(n−1/2)O(n^{-1/2}) term requires n≳T4/3n\gtrsim T^{4/3} to reach O(T−2/3)O(T^{-2/3}). This limitation concerns this confidence bound, not all gap estimators.

Mixing two thresholds. Proposition 6 in the updated version provides a correction based on threshold mixtures. Under the i.i.d. and continuous-score assumptions, fix q−<α<q+q_- < \alpha < q_+ before the online run. When Counting or Barrier requests a level between them, randomly select q−q_- or q+q_+ so that the mean equals the requested level, then use past-score ranks. Otherwise, retain the original method. This preserves the controller's conditional error probabilities and hard quota.

Let Δmix\Delta_{\mathrm{mix}} denote the gap above the chosen benchmark when the two population sets are mixed to miscoverage α\alpha. Under local smoothness at the selected levels in (0,1)(0,1), A1's bounds hold with Δmix\Delta_{\mathrm{mix}} replacing Δα\Delta_\alpha, with an additional O(log⁡T)O(\log T) rank-estimation cost. Mixing does not necessarily eliminate the gap: zero gap requires the mixed population sets to attain the benchmark, which data-chosen levels need not achieve. Levels 0 and 1 correspond to the literal full and empty sets, respectively.

Discrete and piecewise-linear frontiers. A finite collection of prediction rules has a piecewise-linear frontier when mixtures are allowed; discrete labels alone do not guarantee this when rules depend on covariates. If α\alpha lies inside a linear segment, the terminal and expected-prefix curvature assumptions fail (Remark 7). Mixtures can still give the upper bounds (Proposition 6), under its conditions, but these bounds need not be tight. Appendix E.4 gives a counterexample to all three matching rates: for a uniform outcome, j(q)=1−qj(q)=1-q, and a full/empty policy keeps all three costs below one. The third lower bound can still hold under Theorem 3(iii)'s separate condition.

AuthorsOpenReview ↗

Response to Reviewer T4oA (3/3): distribution shift, tied scores, model updates, delay

W2: Many motivating online applications involve distribution shift, model updates, tied scores, or delayed feedback. It remains unclear whether the proposed methods retain meaningful efficiency guarantees in these more realistic settings.

A3: The updated version gives the following extensions.

Delayed feedback. Proposition 7 in the updated version runs d+1d+1 copies in rotation when YtY_t arrives before round t+d+1t+d+1. Each receives its previous label before predicting again, and their individual quotas imply the overall quota. Under the original i.i.d. and efficiency assumptions, the upper bounds are O((d+1)log⁡T)O((d+1)\log T) for expected final-time cost, O((d+1)2/3T1/3)O((d+1)^{2/3}T^{1/3}) for the largest expected prefix cost, and O((d+1)T)O(\sqrt{(d+1)T}) for the expected largest realized cost over t≤Tt\le T, with T≥2(d+1)T\ge 2(d+1). The original lower bounds still apply, so these rates remain optimal in TT for fixed dd.

Distribution shift and model updates. Proposition 8 in the updated version restarts Barrier over NN periods with boundaries fixed in advance. Each period uses a fixed score and i.i.d. data conditional on all information at its start, including fitting data. Under the stated efficiency assumptions with constants bounded across periods, the largest expected prefix cost is O(N2/3T1/3)O(N^{2/3}T^{1/3}), relative to the sum of the periods' population benchmarks. This retains cube-root growth for fixed NN and is sublinear when N=o(T)N=o(T). Scores may be refitted between periods. These bounds do not cover unknown changes or gradual drift. With immediate labels, the full-set guard still enforces the quota on any data stream.

Tied scores. Counting, Barrier, and the guard satisfy the quota despite ties. For i.i.d. data, Remark 8 in the updated version restores uniform ranks by ordering ties with one independent uniform random number per round, shared by all candidate labels. Miscoverage probabilities and expected set sizes are averaged over the tie-breaking randomness. Efficiency still requires Assumption 2 for the randomized prediction-set family: tie-breaking alone does not establish it.

Reviewer_hKrLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies online conformal prediction, a growing area of research in which the goal is to provide conformal prediction-style guarantees in online settings. A number of works study methods to give improved / tighter coverage given a target conformal prediction confidence level alpha. This paper studies various trade-offs involved in changing the definitions of coverage, from at the end at time T, all time t<T, and so on (Table 1). The paper studies several natural notions of coverage guarantees, and then provides characterizations for each of these notions.

Critical strengths

I think this idea of simplifying the object of study (the price of hard coverage) via their oracle approach is nice, and it seems to get them a clear set of results, like matching upper and lower bounds, on a number of different criteria (that are given in Table 1).

The technical arguments in the main text, to the extent that I could follow them within my time constraints, seemed sound.

Critical weaknesses

This is maybe something to be clarified in the rebuttal, but Assumption 1 seems too strong to me? I understand that there's some basic price that one has to pay due to coverage control, and this paper is establishing a type of existence result, but i worry that the analyses here are not particularly informative of the actual costs of algorithms like ACI. I am guessing this will show up as additional costs in the more complex case, but it'd be good to understand.

Related to the above, I think the paper doesn't do a very good job of relating the results derived under Assumption 1, to the actual price that one would incur in running and studying conformal prediction algorithms. It's probably the case that we don't actually care about the oracle setting in the paper, and we'd want to map these findings to implications for more general online conformal settings. What implications can we get from your bounds?

Unfortunately, there were parts of the paper that were difficult for me to read. I am generally familiar with the online conformal literature, but there are parts of the paper that are very compressed. The experiment section especially felt this way, and I am not sure that I have a great picture of the experimental setup and why the specific experimental setting here was chosen.

Questions for authors

See the weaknesses. Specifically,

Isnt assumption 1 too strong, in that it would produce too weak of a result?

What are the implications for more general online conformal settings?

Apologies if I've missed this in the existing paper.

6 comments
AuthorsOpenReview ↗

Response to Reviewer hKrL (1/2): oracle lower bounds and ACI

Thank you for your careful review of our paper. We address your concerns below.

W1–W2/Q1–Q2: Is Assumption 1 too strong, producing too weak a result? What are the implications for ACI and more general online conformal settings?

A1: Assumption 1 strengthens the lower-bound conclusion: the quota has an unavoidable cost even with i.i.d. data and a known distribution and horizon.

What the lower bounds imply. They apply to every feasible policy under the lower-bound assumptions. Neither Assumption 2 nor a continuous score distribution is required, and these conditions support the matching upper bounds. Distribution knowledge removes estimation uncertainty without revealing future outcomes. Any broader data model containing this i.i.d. case inherits the worst-case lower bound for the same prediction-set family and benchmark (Section 4.6 in the updated version).

All three criteria enforce the same quota at every time and only the cost evaluation time differs. Corollary 1 shows that O(log⁡T)O(\log T) expected final-time cost forces Ω(T/log⁡T)\Omega(\sqrt{T/\log T}) expected cost at an earlier time. The matching upper bounds use stationarity. Under Assumption 2, with a fixed score whose distribution is continuous, Theorem 2 adds only O(log⁡T)O(\log T) for threshold estimation, preserving all three rate orders without knowing the score distribution.

Implications for ACI. ACI controls cumulative miscoverage with an additive allowance ([1], Proposition 4.1), and its asymptotic average interval length has also been analyzed under oracle assumptions ([2], Theorem 3.1). These results do not determine the minimum cumulative excess prediction-set size required by a hard quota at every time. Proposition 3 in the updated version connects these formulations. For fixed-step ACI initialized at a1=αa_1=\alpha, without projection and with the full set at adjusted levels at or below zero, every stream satisfies $ M_t-\alpha t\le\alpha/\gamma+1-\alpha. $

At α=0.1\alpha=0.1 and γ=0.005\gamma=0.005, this permits at most 21 errors above the quota. Under the lower-bound assumptions, Appendix H shows that any fixed allowance retains an Ω(T1/3)\Omega(T^{1/3}) lower bound on the largest expected cost. With a continuous score, exact population quantiles, and the empty set at adjusted levels at or above one, Proposition 3 also gives an asymptotic linear lower bound for a fixed step: ACI's requested error probability keeps fluctuating. This does not predict measured finite-horizon costs.

Housing directly measures the cost of enforcing the quota (Table R1 in Part 2): ACI exceeds it in every tested run despite 10.00% final miscoverage. Adding the guard increases mean width by 2.9% for Ridge and 4.1% for Extra Trees.

Beyond stationarity. With immediate labels, returning the full set whenever another error could exceed the quota enforces it on every stream, including under drift. Propositions 7–8 in the updated version give efficiency bounds for bounded delays and refitting between stationary periods with boundaries fixed in advance (T4oA, A3). Our population-frontier efficiency bounds do not cover arbitrary drift.

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.

AuthorsOpenReview ↗

Response to Reviewer hKrL (2/2): experimental questions and results

W3: What is the experimental setup, and why were these settings chosen?

A2: The synthetic model satisfies the assumptions exactly, so it lets us compare the three cost criteria and isolate the cost of threshold estimation. Housing measures the cost of enforcing the quota for learned scores whose population optimality is unverified. Section 5 in the updated version explains each experiment's purpose.

Synthetic experiments. We generate Y=(3U+U2)/4Y=(3U+U^2)/4 with UU uniform on [0,1][0,1], use intervals [0,τ][0,\tau], and target miscoverage α=0.1\alpha=0.1. The optimal expected length is j(q)=1−5q/4+q2/4j(q)=1-5q/4+q^2/4, so the assumptions and benchmark are known and predictor approximation cannot obscure the quota's cost. Comparing population quantiles with ranks under the same controller isolates threshold estimation. State probabilities give Counting's expected final-time cost and Barrier's largest expected cost, and 512 independent streams estimate the expected largest realized cost. Numerical optimization bounds the smallest achievable costs at selected horizons. Theorem 1's decomposition identifies the source of cost: at T=16,380T=16{,}380, default Barrier's expected-prefix cost is 18.92618.926, including 18.04318.043 from unused error budget, while the numerical optimum lies in [5.6547,5.6598][5.6547,5.6598] (Section 5.3). Conservative budget use thus explains most of this finite-horizon gap.

At T=262,144T=262{,}144, horizon-tuned guarded ACI [1] costs 29.429.4, versus 43.943.9 for default Barrier (Tables 3 and 2): optimal asymptotic rates need not minimize finite-horizon cost. ACI is retuned on validation streams at each horizon, and Barrier uses one run without knowing the final time. Table 3 also compares a Barrier width and our decaying-step ACI comparator, both selected once at T=16,380T=16{,}380 and held fixed. Motivated by decreasing-step methods [2], the comparator updates ACI's miscoverage level rather than the threshold. At T=262,144T=262{,}144, this Barrier variant costs 36.536.5, versus 40.040.0 for decaying ACI, which is cheaper at shorter reported horizons. The ranking depends on settings and horizon.

Housing. Each of five frozen splits has 10,320 fitting, 5,160 validation, and 5,160 test observations. Settings are selected on 16 validation orderings and fixed for 32 paired test orderings. Every test run starts without past calibration scores. ACI and guarded ACI use identical proposals and update on proposal errors, isolating the guard's cost: mean-length increases of 0.010170.01017 for Ridge and 0.011500.01150 for Extra Trees, with paired 95% intervals [0.00962,0.01072][0.00962,0.01072] and [0.01087,0.01212][0.01087,0.01212]. Barrier reduces mean width relative to guarded ACI by 1.33% and 1.83% across splits. With the same empirical-rank implementation for both methods, reductions are 1.68% and 2.21%, respectively (Table 5), separating controller effects from threshold implementation. The uncertainty intervals condition on the fixed data pools and capture ordering and controller randomness, excluding training and population uncertainty.

Table R1. Housing at α=0.1\alpha=0.1, T=5,160T=5{,}160, and 32 paired orderings per frozen split (five splits). Peak excess is the largest number of misses above quota across all rounds and runs. Submitted Tables 6–7.

PredictorMethodMean lengthFinal miscoverageRuns violating quotaPeak excess
RidgeACI0.354210.00%100%12
RidgeGuarded ACI0.36449.84%0%0
RidgeBarrier0.35959.79%0%0
Extra TreesACI0.279510.00%100%12
Extra TreesGuarded ACI0.29109.84%0%0
Extra TreesBarrier0.28569.79%0%0

References

[1] Isaac Gibbs and Emmanuel J. Candès. Adaptive Conformal Inference Under Distribution Shift. NeurIPS 2021.

[2] Anastasios N. Angelopoulos, Rina Foygel Barber, and Stephen Bates. Online Conformal Prediction with Decaying Step Sizes. ICML 2024.

AuthorsOpenReview ↗

Looking forward to post-rebuttal feedback!

Dear Reviewer hKrL,

As the discussion period is coming to an end, we would greatly appreciate any feedback you may have on our rebuttal and revised manuscript. Please let us know if there are any remaining concerns we could address.

If you find that our responses have adequately addressed your concerns, we would also appreciate your reconsideration of the overall rating.

Thank you for your time and consideration.

Best,

Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Comments

Thank you for the constructive reviews. We study settings that enforce the same quota after every prediction but differ in when prediction-set costs are evaluated. Our lower bounds hold under the stated assumptions, even when the i.i.d. distribution and time horizon are known.

To address the issues mentioned by reviewers, We have updated the PDF and new explanations and results are marked in blue. We summarize the main revisions below, followed by individual responses to each reviewer.

  • Implications for existing methods. New Section 4.6 and Proposition 3 clarify the implications of our lower bounds for fixed-step ACI and more general data models (hKrL Q1–Q2, WzcX W2).

  • Learned scores. Section 4.3 and Appendix I quantify the additional cost of suboptimal scores (Proposition 4), bound this gap using independent data (Proposition 5), and introduce a correction that mixes two thresholds (Proposition 6). Lemma 8 and Table 9 further examine how learning reduces this gap in a controlled model (T4oA Q1).

  • Extensions and sufficient conditions. Propositions 7–8 address bounded label delays and refitting between stationary periods. Remark 8 discusses tied scores, and Proposition 9 provides sufficient conditions for residual and scaled-residual scores to satisfy Assumption 2 (T4oA W2, WzcX Q3).

  • Motivation and presentation. Section 1 adds an inspection example and Table 1. Section 4.2 explains Algorithm 3 before introducing Assumption 2. Section 5 clarifies the purpose of each experiment. We also resolve conflicting notation throughout the paper (hKrL W3, WzcX Q1–Q2).

  • Finite-horizon comparisons. At T=262,144T=262{,}144, horizon-tuned guarded ACI has lower cost than default Barrier (29.4 vs. 43.9). With parameters tuned once and held fixed, Barrier has lower cost than decaying-step ACI at this horizon (36.5 vs. 40.0), whereas ACI performs better at shorter horizons (Table 3).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.