Batch Multivalid Conformal Prediction

1 Introduction

• The goal is coverage conditional on each potentially intersecting group and on the chosen threshold, beyond ordinary marginal coverage.The threshold condition avoids meeting the target by overcovering at some thresholds and undercovering at others, such as by randomizing between full and empty sets.Source: §1 · pp. 1–2

1.1 Our Results

• The algorithms provide PAC-style guarantees and, although the theorems assume i.i.d. data, the analysis extends to exchangeable data by De Finetti’s theorem [Ressel, 1985].Source: §1.1 · p. 3
• BatchGCP uses a single |G|-dimensional convex pinball-loss minimization to provide group-conditional, but not threshold-calibrated, coverage.The approach extends conformalized quantile regression and uses an arbitrary initial model.Source: §1.1 · p. 3
• BatchMVP iteratively patches group-threshold pairs that miss target coverage, achieving full multivalid guarantees; each patch substantially improves pinball loss, implying fast convergence.Its guarantees hold simultaneously conditional on group membership and threshold value.Source: §1.1 · p. 3
• Both algorithms obtain significantly better group-wise coverage and threshold calibration than the compared baselines, while calibrating datasets with tens of thousands of points in a few seconds.Source: §1.1 · p. 4

1.2 Additional Related Work

• The methods complement non-conformity-score research as drop-in replacements for split conformal prediction, while prior intersecting-group calibration can over-cover and sequential approaches require labels after prediction or impractical reductions.The paper presents its batch predictor as direct, simple, and deterministic.Source: §1.2 · p. 4

2 Preliminaries

• A prediction task has domain Z = X × Y; groups are subsets of X represented by indicator functions, and labels may be real-valued or finite unordered classes.Source: §2 · p. 5
• The non-conformity score is bounded in [0, 1], and each conditional score distribution S(x) is assumed continuous.The text notes that arbitrarily small continuous noise can enforce continuity.Source: §2 · p. 5
• A ρ-Lipschitz conditional score distribution limits how quickly its probability mass below a threshold can increase as the threshold rises.The paper also parameterizes convergence results by the Lipschitz parameter of the score-distribution CDF.Source: §2 · pp. 5–6
• The paper aims to approximate conditional quantiles through coverage guarantees conditioned on group membership and predictor output, rather than on every feature vector.The predictor’s range is restricted to finite cardinality to support guarantees conditional on its output values.Source: §2 · p. 6

3.1 Algorithmic Preliminaries

• Pinball loss is the shared potential: shifting a predictor to marginal quantile consistency reduces loss when inconsistency is large, while small perturbations of a consistent predictor add little loss.The stated properties rely on a Lipschitz underlying distribution.Source: §3.1 · p. 6, We write · pp. 6–7

We write

• A patch shifts predictions by a constant only on a selected feature-space subset, and correcting marginal quantile inconsistency there can substantially improve pinball loss.The update is localized to the chosen subset.Source: We write · p. 7

3.2 BatchGCP: Obtaining Group Conditional Guarantees

• BatchGCP minimizes pinball loss over the initial threshold model and group indicators, obtaining group-conditional guarantees but not threshold calibration.The optimization is a single convex problem.Source: §3.2 · pp. 7–8

3.3 BatchMVP: Obtaining Full Multivalid Coverage

• BatchMVP’s α-approximate quantile multicalibration yields coverage-error bounds for every group and predicted threshold, giving full multivalid coverage.The bound applies when conditioning on group membership and threshold value simultaneously.Source: §3.3 · pp. 9–10
• BatchMVP repeatedly patches a group-and-threshold pair that violates calibration; under a Lipschitz score distribution, each patch reduces pinball loss and supports fast convergence.The update preserves a discretized range for the threshold model.Source: §3.3 · pp. 8–9

• BatchMVP’s out-of-sample analysis uses one sufficiently large calibration sample directly, unlike prior analyses relying on fresh samples each round or noise perturbations.The authors describe this as closer to how the algorithm would actually be run.Source: §4 · p. 10
• For a run of T rounds, BatchMVP is α′-approximately q-quantile multicalibrated on S with probability 1−δ under Theorem 4.1’s assumptions.The bound is uniform over T, so it can use the empirical stopping time.Source: §4 · p. 11
• A worst-case upper bound on convergence time combines with Theorem 4.1 to yield a PAC-style generalization guarantee for sufficiently large samples.The theorem assumes a continuous, ρ-Lipschitz score distribution.Source: §4 · p. 11

5.1 A Synthetic Regression Task

• Across 50 synthetic runs, BatchGCP achieved nearly perfect group coverage, while BatchMVP sometimes deviated from target by up to 1%.Foygel Barber et al.'s method significantly overcovered nearly all groups, while naive split conformal undercovered high-noise groups and overcovered low-noise groups.Source: Figure 1 · p. 12, §5.1 · p. 12
• The synthetic experiment used 20 intersecting groups, a 0.9 target coverage, and a predictor calibrated with absolute residual scores.The data-generating process added group-dependent noise; the study compared BatchGCP and BatchMVP with naive split conformal and Foygel Barber et al. [2020].Source: §5.1 · pp. 11–12

5.2 An Income Prediction Task on Census Data

• On Folktables California data, BatchGCP and BatchMVP achieved nearly perfect group coverage, with BatchGCP slightly better and BatchMVP lower in group calibration error.The conservative method generally produced larger prediction sets; the experiment averaged results over 50 rounds.Source: Figure 3 · p. 14, §5.2 · p. 14

A.1 Missing Details from Section 3.1

• For continuous, ρ-Lipschitz score distributions, the appendix analyzes threshold shifts that restore target quantile consistency and bounds the local area under H.The area bounds use extremal increasing curves, illustrated by the maximum- and minimum-area CDF curves.Source: §A.1 · pp. 17–18, Figure 5 · p. 19
• Lemma 3.2 states that patching a predictor on B restores marginal quantile consistency on S|B when that conditional score distribution is continuous and ρ-Lipschitz.The proof relates the original quantile error to a threshold shift that makes the patched predictor consistent.Source: §A.1 · p. 20

A.2 Missing Details from Section 3.2

• For any input model f, groups G, and q in [0,1], Theorem 3.1 says Algorithm 1 returns fhat(x; λ*); its proof rules out group marginal quantile inconsistency by λ*'s optimality.The prediction sets are T_fhat(x) = {y: s(x, y) ≤ fhat(x; λ*)}.Source: §A.2 · p. 21

A.3 Missing Details from Section 3.3

• BatchMVP's guarantee applies to every group and threshold value, yielding approximate quantile multicalibration after a bounded number of rounds under the theorem's stated conditions.The proof decomposes each patch into two operations and bounds their effects on the loss and quantile consistency.Source: §A.3 · pp. 22–23

B.1 On the i.i.d. versus exchangeability assumption

• The appendix explains that its i.i.d. generalization guarantees extend to exchangeable sequences by applying them to the i.i.d. mixture components in a de Finetti representation.The stated guarantee is low quantile multicalibration error with probability 1 − δ, in expectation over the mixture component.Source: §B.1 · p. 24

B.2 Helpful Concentration Bounds

• The additive and multiplicative Chernoff bounds consider independent random variables Xi in [0, 1], with their sum denoted Sn; the statements apply for all ε > 0 and η > 0, respectively.Source: §B.2 · p. 25

B.3 Out of sample guarantees for BatchGCP

• Theorem B.3 analyzes BatchGCP fitted on an iid calibration sample against the true-distribution optimum, with probability 1−δ over the sample draw.The theorem compares the sample-based solution with the optimal solution for the true distribution.Source: §B.3 · pp. 28, 30
• A finite ε-net and the Lipschitzness of pinball loss extend concentration from net points to every parameter in a bounded ball.The proof first union-bounds concentration over a finite net, then uses the loss's Lipschitz property to extend the control.Source: §B.3 · p. 29
• A maximal ε-separated subset gives an ε-cover, whose size is bounded by comparing the volumes of disjoint balls with a containing ball.This cover provides a finite set over which the concentration argument can be applied.Source: §B.3 · p. 29

B.4.1 Out-of-sample quantile multicalibration bound for fixed T

• With probability 1−δ, Theorem 4.1 guarantees that the BatchMVP output is α′-approximately q-quantile multicalibrated on S.The theorem assumes S is ρ-Lipschitz and the algorithm runs for T rounds; the error is assessed conditional on both group membership and the output threshold value.Source: §B.4.1 · pp. 31, 33
• The proof uses concentration over groups and candidate models to transfer quantile consistency from the empirical distribution to S.At termination, the output is α-approximately multicalibrated on the empirical distribution.Source: §B.4.1 · pp. 31, 33
• The conditional error compares q with the probability that the score is at most the predicted threshold, given both that threshold value and group membership.Source: §B.4.1 · p. 33

B.4.2 Sample complexity of maintaining convergence speed of BatchMVP

• Each BatchMVP round patches examples sharing a predicted threshold and group membership, and the proof establishes a decrease in empirical pinball loss.The patch increment is selected by minimizing empirical pinball loss over a grid.Source: §B.4.2 · pp. 33, 34, 36
• After t rounds, the number of possible models is bounded by ((m + 1)^2|G|)^t.The count follows by considering the possible threshold-group patch choices at each round.Source: §B.4.2 · p. 33
• Theorem 4.2 gives a halting-round bound for BatchMVP when S is continuous and ρ-Lipschitz, m = ρ^2, and the iid sample size is sufficiently large.The theorem's stated bound is T ≤ 8ρ^3 followed by further terms in the supplied statement.Source: §B.4.2 · p. 33
• The proof controls empirical pinball loss across the round's candidate models by concentration around population loss.Source: §B.4.2 · p. 35

C.1 A Direct Test of Group Conditional Quantile Consistency and Quantile Multicalibration

• The synthetic data uses 15 intersecting groups defined by multiples of j, with label noise based on the number of groups containing each covariate.The data are split 80%/20% into training and test sets; the experiment uses m = 100 buckets.Source: §C.1 · p. 37
• Both methods attain target group-wise coverage, with BatchMVP showing less variation in attained coverage across runs.The comparison uses groups of multiples of integers and a target coverage q = 0.9.Source: §C.1 · p. 37
• Both methods have groupwise quantile calibration errors on the order of 10−3, although BatchGCP does not explicitly enforce this constraint.Source: §C.1 · p. 37

C.2 Further Comparisons On State Census Data

• Figures 8–10 compare methods on group-wise coverage, average prediction-set size, and calibration error across states, averaging 50 runs with standard-deviation error bars.Source: §C.2 · p. 39, Figure 8 · p. 39, Figure 9 · p. 40

C.2.1 Halting Time

• Although the generalization theorem gives a worst-case upper bound on BatchMVP iterations, it empirically halts sooner; the subsection reports per-state mean iterations and standard deviations.Source: §C.2.1 · p. 39
• Figure 11 plots threshold-group pair counts against conditional average coverage across tested methods and nine states, with target coverage q=0.9.Source: Figure 11 · p. 42