acceptodds
Under review as a conference paper at ICLR 2027

Quantile Optimization for Honest Conformal Prediction under Label Shift

Abstract

Weighted conformal prediction (WCP) provides finite-sample coverage guarantees under label shift given true importance weights. However, under-coverage happens in practice when the discrepancy between estimated weights and the truth is not negligible, invalidating these guarantees. To restore validity, honest conformal prediction (HCP) evaluates the worst-case calibration sample quantile over a weight confidence region, yet this typical formulation poses a computational challenge, as it naturally requires non-convex fractional programming over calibration samples. In this work, we present QuiCK (Quantile Computation for -class HCP), an advanced computational suite that fundamentally fuses exact statistical honesty with practical computational efficiency. By decoupling the calibration sample size from the class dimension when evaluating empirical cumulative distribution functions, QuiCK leverages coordinate monotonicity for fast sequential optimization of quantile thresholds over marginal hyperboxes, and reformulates the original fractional programming form into a pure linear program (LP) over joint polytopes. Strategically, we streamline the optimization route for both cases by first computing a class-shared base solution, then efficiently localizing class-specific thresholds either by continuing the class-wise search directly from the base solution, or by applying LP sensitivity analysis to prune unaffected classes beforehand. Extensive experiments on synthetic datasets and real-world benchmarks validate that QuiCK strictly achieves honest conformal prediction guarantees. With a C++ and OpenMP backend, QuiCK delivers exact statistical honesty while maintaining computational efficiency.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Conformal prediction, Fractional programming, Label shift, Linear programming, Prediction coverage, Uncertainty quantification, Weighted sample quantiles

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_y3AyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the computational problem behind honest conformal prediction under label shift when the importance weights are unknown and only known to lie in a finite-sample confidence region. The authors propose QuiCK, with a coordinate-wise exact solver for hyperbox confidence regions and an LP-based solver for joint polytope regions, together with warm starts and sensitivity-based pruning to compute worst-case weighted quantile thresholds for all classes. The statistical coverage guarantee is inherited from worst-case calibration over a valid weight confidence region, while the main contribution of this paper is making that optimization substantially faster.

Critical strengths

S1. The paper identifies a concrete computational bottleneck in honest conformal prediction.

S2. The separation between calibration-sample counts and class-level weights is useful.

S3. The experimental evaluation covers both statistical validity and computational behavior.

Critical weaknesses

W1. The statistical framework itself is largely inherited from prior work, and the novelty is primarily computational.
The honest conformal construction based on a confidence region for the unknown importance weights is already present in Li et al. (2026), and the same prior work also reports exact maximization over marginal hyperboxes. The paper should be much more precise about how much of the statistical methodology is actually new.

W2. The computational experiments omit the most relevant exact baselines.
The paper's main claim is computational efficiency, yet the primary nontrivial computational baseline is BBHR, a heuristic boundary-biased MCMC procedure introduced by the authors. There is no runtime comparison against straightforward exact alternatives such as Charnes-Cooper, Dinkelbach iterations, a naive threshold scan with LPs, or a per-class LP/binary-search implementation without the proposed warm start and sensitivity pruning. Without these comparisons, it is difficult to quantify how much speedup comes from the genuinely new algorithmic ideas.

W3. The proposed honest prediction sets can be extremely conservative.
For a nominal 90% target, the reported coverage is often around 97% in small-sample regimes,. Thus, the method obtains honesty partly by paying a very large statistical-efficiency cost. Computational efficiency alone does not resolve this limitation.

W4. The claimed high-dimensional scalability is partly masked by increasing the amount of estimation data with KK.
When studying the number of classes, the paper sets ns=nt=200Kn_s=n_t=200K. Thus larger label spaces are automatically given proportionally more data. This isolates computational scaling, but it does not demonstrate statistical scalability at a fixed data budget. Moreover, constructing the weight confidence region requires estimating a K×KK\times K confusion matrix, which itself becomes statistically and computationally difficult as KK grows.

W5. The empirical language sometimes overstates what the experiments establish.
Statements such as the experiments "strictly guarantee" or "perfectly provide" coverage conflate empirical coverage observed over 200 trials with the theorem-level guarantee. Likewise, the manuscript repeatedly uses highly promotional phrases such as "fundamentally fuses," "absolute statistical validity," and "remarkable" scalability. A more precise and less promotional presentation would improve the paper.

Questions for authors

See weaknesses

1 comment

Thank you for the thorough review, especially for recognizing the value of separating calibration-sample counts from class-level weights. We will add more exact baselines and tone down the overstated language.

Reviewer_FnKWOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work aims to improve the computational efficiency of conformal prediction for honest prediction sets under label shift. A valid prediction set under label shift is constructed using the worst-case weighted conformal quantile computed from a finite-sample confidence region for the importance weights. The authors propose QuiCK to compute the quantile efficiently from the confidence region, for both hyperbox and polytype regions. This is achieved by leveraging the structure of the weighted eCDF, using a linear program over joint polytopes, and relying on a class-shared base solution. The experiments on synthetic and real datasets show that the proposed method achieves valid empirical coverage and that its runtime is faster than sampling-based baselines.

Critical strengths
  1. This work focuses on a relevant and practical problem: label shift. This framework also does not assume that the true weights are known, which increases its flexibility.
  2. The proposed QuiCK method constructs the prediction sets faster than the baseline, and it preserves the coverage guarantee of HCP.
Critical weaknesses
  1. My main reservation is that the theoretical validity and the construction of the prediction sets and the confidence regions are mostly inherited from Li et al. (2026) simply by employing a union bound. That is, the novelties of the proposed approach seem limited to me. The work of Li et al. (2026) already proposes optimizing the quantiles over hyperboxes and using Monte Carlo for polytopes. The main novelty of QuiCK, on the other hand, is the computational efficiency and exact optimization. Furthermore, the experiments show that the prediction sets produced by QuiCK are larger and less informative than those of BBHR.
  2. It is not clear where the gains of QuiCK come from. Specifically, the correctness of the solver is not checked directly; its efficiency is compared to BBHR, which is employed with arbitrary parameters for the burn-in period and number of samples, and it is not compared against alternatives that solve the optimization exactly.
Questions for authors
  1. Can the authors clarify the difference between QuiCK.hyperbox and the optimization over hyperboxes proposed by Li et al. (2026)? And compare their runtimes?
  2. Can the authors please compare their approach to Algorithm 5?
  3. Is the confidence region constructed in Appendix F necessarily bounded? If not, how does the proposed framework handle unbounded regions?
  4. Could the authors compare the computed worst-case quantiles to the solution of an exact optimizer? This comparison can be conducted on a small synthetic dataset.
  5. Some tables display inconsistent measurements. For example, why do Tables 2 and 4 show different runtimes for QuiCK.hyperbox+ for K=100?
1 comment

Thank you for the detailed review. QuiCK is exact by construction. Also, we have verified that QuiCK matches exact solvers (Charnes–Cooper, Dinkelbach, LP scan, per-class bisection as Reviewer y3Ay advised) on all 1000 testing samples. BBHR, as Reviewer y3Ay noted, is a heuristic: its smaller sets come from underestimating the worst-case threshold and carry no coverage guarantee, so they are not directly comparable for the informativeness. The runtime gap between Tables 2 and 4 stems from different estimation sample sizes (50,000 vs. 20,000), hence different confidence regions (see different pruning rates in Tables 3 and 7).

Reviewer_1ZwsOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies weighted conformal prediction under label shift when the importance weights are unknown and need to be estimated. Instead of using plug-in estimators for the importance weights, the authors consider worst-case quantiles over confidence regions for the true importance weights and propose QuiCK as a computationally efficient framework for computing these worst-case thresholds. The authors consider two types of confidence regions: marginal hyperboxes and joint polytopes. For joint polytopes, the authors propose an LP-based algorithm, along with several optimizations, to efficiently compute the worst-case threshold. The empirical results show that QuiCK is faster than sampling-based approximations, but the resulting prediction sets can be conservative.

Critical strengths
  • The paper identifies a computational bottleneck in using confidence regions for the true importance weights to find the worst-case quantile. The proposed method, QuiCK, replaces sampling-based approximation with exact worst-case quantile optimization over both hyperbox and joint-polytope confidence regions.

  • The computational improvements are meaningful compared to the MCMC baseline, and the improvements become larger as the number of classes increases. These results, particularly Tables 2 and 3, should be in the main body.

Critical weaknesses
  • The novelty and framing of this paper are unclear, especially compared with [1], which appears to provide the confidence-region formulation and already considers worst-case quantile optimization. Further, the uncited introduction of “honest conformal prediction,” which does not appear to be standard terminology, raises an issue with the provenance of the terminology and surrounding motivation.

  • The experimental results only compare against an MCMC-based approximation rather than a generic exact optimization approach. While QuiCK is substantially faster than the MCMC approach, it also tends to overcover and produce conservative prediction sets, which can become uninformative. A clearer evaluation of exact-computation speedups and the validity–informativeness tradeoff is needed.

[1] Li et al. 2026, From matrix inversion to constraints: provably tighter confidence regions for importance weights in label shift.

Questions for authors

(See weaknesses)

  1. Do you have a citation for “honest conformal prediction,” or is this terminology being introduced in this paper?

  2. What precisely is the difference between and novelty of QuiCK relative to [1]?

  3. How does QuiCK compare computationally against a generic exact optimization approach, rather than a sampling-based approximation?

  4. How does the conservativeness of the method affect its practicality?

  5. Why set ϵ=1/n\epsilon = 1/n such that there is now a dependence on the number of calibration points? How does the calibration set size affect the coverage and prediction set sizes given this choice?

[1] Li et al. 2026, From matrix inversion to constraints: provably tighter confidence regions for importance weights in label shift.

1 comment

Thank you for the careful reading. We agree that the positioning relative to Li et al. (2026) was unclear and that most of the concerns stem from this. As Reviewer FnKW also notes, Li et al. (2026) optimize exactly only over hyperboxes and use Monte Carlo for polytopes; QuiCK explores the latter with an exact solver.

Comments on the paper

1 comment

We thank the reviewers and the AC for their time and constructive feedback. We acknowledge that the manuscript does not distinguish our contribution from Li et al. (2026) clearly enough, which caused confusion. To clarify: QuiCK computes the worst-case threshold exactly over a given confidence region, as long as it is a hyperbox and/or a polytope. We believe all raised concerns are addressable, but we have decided to withdraw and revise.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.