Quantile Optimization for Honest Conformal Prediction under Label Shift

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 $n$ calibration samples. In this work, we present QuiCK (Quantile Computation for $K$-class HCP), an advanced computational suite that fundamentally fuses exact statistical honesty with practical computational efficiency. By decoupling the calibration sample size $n$ from the class dimension $K$ 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.