Conformal prediction with localization

1 Introduction

• When the score distribution varies across test locations, treating all training samples equally can leave ordinary conformal bands unable to capture that heterogeneity.The motivating example uses Yi = Xi + ϵi with ϵi|Xi distributed as |Xi|/(|Xi|+1) times N(0, 1), and Xi ∼ Unif(−2, 2).Source: §1 · p. 1, Figure 1 · p. 2
• Localized conformal inference up-weights training samples near the test point and includes a candidate response when its score is below a weighted empirical quantile.The procedure uses a localizer H to assign weights to training scores.Source: §1 · p. 2
• Localized conformal bands capture heterogeneity in the underlying confidence bands better than ordinary conformal bands in the illustrated example.The figure compares the bands at level α = .95.Source: §1 · p. 2, Figure 1 · p. 2
• The paper states that localized inference can provide finite-sample coverage guarantees while giving the test point a special role.The introduction describes this as the first method to provide a theoretical guarantee for this setting.Source: §1 · p. 2

2 Related work

• Finite-sample conditional validity cannot be achieved without infinite-length intervals at every non-atom point of the distribution.This impossibility motivates alternatives with approximate conditional or local coverage.Source: §2 · p. 2
• Partition-based conformal methods target coverage within each feature-space subset, but can perform poorly for test points near subset boundaries.They divide the feature space into K finite subsets and apply conformal inference within each subset.Source: §2 · pp. 2–3
• Fixed-center kernel methods take the union of multiple intervals, which can be unnecessarily wide; localized conformal prediction instead up-weights training samples near each test point.The related-work discussion distinguishes localization from choosing a more homogeneous fixed score function, and says the approaches can be combined.Source: §2 · p. 3

3 Localized conformal inference with fixed score function V (.)

• The fixed-score setting includes a prespecified prediction function, and the paper also allows a score learned on separate data or previous data.Sample splitting is one stated way to separate score training from conformal inference.Source: §3 · p. 3
• Weights proportional to the test-centered localizer emphasize nearby samples, while considering localizers centered at every sample restores some underlying exchangeability.The method uses a weighted empirical distribution and calibrates its level using localizers around both the test point and training points.Source: §3 · pp. 3–4
• Selecting a separate level for every candidate response is too computationally expensive, motivating a procedure that selects one level for all responses simultaneously.The practical procedure searches candidate levels to find a small one satisfying the stated condition.Source: §3 · p. 4
• The fixed-score procedure achieves finite-sample coverage of at least α by selecting a level that satisfies its coverage condition and inverting the score threshold.Usual conformal inference is recovered when all localizer weights equal 1.Source: §3 · p. 4
• Randomizing the decision rule makes coverage tight, whereas coverage may otherwise fail to equal the nominal level because of rounding.The section also shows that using the nominal level without calibration can lead to either over-coverage or under-coverage.Source: §3 · p. 5
• With a sufficiently narrow exponential localizer, coverage can exceed the nominal level with probability at least any chosen ε greater than α.This example assumes a jointly continuous feature density and chooses the localizer bandwidth sufficiently small.Source: §3 · p. 5
• For the fixed-width distance localizer example, the asymptotic coverage can be below α when the nominal level is used without calibration.The example gives conditional coverage tending to zero at test feature values 1 and −1.Source: §3 · p. 5

3.1 Choice of H

• Choosing the localizer bandwidth trades off locality against volatility; the main paper focuses on low-dimensional features because finding useful high-dimensional projections is a separate, non-trivial problem.The authors describe distance-based and nearest-neighbor localizers and propose data-adaptive tuning for relatively narrow, stable intervals.Source: §3.1 · p. 5, Table 1 · p. 6

• The simulations used a fixed absolute-residual score with normally distributed features and compared distance-based and nearest-neighbor localizers.The study evaluated three noise-generating mechanisms and several fixed or automatically selected tuning values.Source: §4 · p. 6
• Both localized and ordinary conformal prediction achieved the desired coverage across three noise mechanisms at α=.80 and α=.95.The experiments used 500 training samples and 1,000 repetitions; the coverage comparison is reported in Table 1.Source: §4 · p. 6
• Automatic tuning selected larger bandwidths for homogeneous score distributions and smaller bandwidths when scores were heterogeneous across feature values.As the bandwidth increases, localized bands become more similar to ordinary conformal bands; smaller bandwidths reveal more local structure.Source: §4 · p. 6

5.1 Local and asymptotic conditional coverage

• Figure 2 compares true responses, conformal bands, and localized bands; LCB1 has some infinite-length intervals, whereas CB and LCB2 do not by construction.The figure shows bands from 1000 repetitions at targeted level α = .95.Source: §5.1 · p. 7, Figure 2 · p. 7
• With a fixed score function, localized conformal inference constructs a unique interval for each test sample satisfying the paper’s type of local-coverage requirement.The method uses a localizer around x0 to define a localized distribution and weighted score distribution.Source: §5.1 · p. 7
• Theorem 5.1 gives local coverage of at least α for every x0 under its localized construction, and asymptotic local coverage as bandwidth h tends to zero under regularity conditions.The conditions include a bounded positive covariate density and a conditional score density that is Lipschitz in the covariates; with a Gaussian kernel, setting the tuning level to α yields local coverage as h → 0 under relatively mild regularity conditions.Source: §5.1 · p. 7

5.2 Localized conformal inference with data-dependent score function

• Theorem 5.2 extends localized conformal inference to data-dependent score functions that depend on the sample set but not its ordering, with exchangeable training and test samples.The paper also extends its randomized decision-rule result for tight coverage to this setting.Source: §5.2 · pp. 7–8
• The authors omit experiments with data-dependent scores because each candidate response requires retraining the prediction model and recalculating the relevant quantities.They include the setting for completeness and to show the extension applies where conformal prediction itself works.Source: §5.2 · p. 8

6 Discussion

• Localized conformal prediction focuses on a region around the test sample and provides finite-sample coverage without distributional assumptions on Y|X.The authors describe localized, assumption-free confidence intervals as a central application.Source: §6 · p. 8
• Distance-based localization may support outlier prediction in regression and classification if a suitable localizer can be found.The authors note that prediction-error distributions can provide response information for this application.Source: §6 · p. 8
• Under covariate shift, the localized version could yield more desirable constructions when test samples differ greatly from training samples.The appendix compares it with conformal prediction under covariate shift [8].Source: §6 · pp. 8–9

A Localized conformal prediction under covariate shift

• Under covariate shift, the finite-sample coverage result assumes independent samples, a known density ratio, and the same conditional response distribution for training and test data.When the density ratio is one everywhere, the setting reduces to i.i.d. data.Source: A Localized conformal prediction under… · p. 9
• Theorem A.4 gives a coverage-guaranteed choice of the threshold by considering localizers centered at each sample to restore exchangeability.Corollary A.8 states coverage of at least α when its stated condition holds.Source: A Localized conformal prediction under… · pp. 9–10
• For covariate shift, the method modifies the weighted evaluation equations for both fixed and data-dependent score functions.The paper identifies Theorems 3.2/Algorithm 1 and 5.2 as the respective cases.Source: A Localized conformal prediction under… · p. 10
• Localization may limit the influence of extremely high-weight training samples when the training and test feature distributions differ substantially.The concern is that weighted conformal prediction can be strongly influenced by a few such samples even when they are far from the test feature.Source: A Localized conformal prediction under… · p. 10
• For x ≤ 2, localized inference gives less volatile CIs; for x > 2, it can give wider CIs and more infinite-length CIs than conformal prediction.The authors note that wider or infinite intervals may characterize regions with few training samples.Source: A Localized conformal prediction under… · p. 10

B Proofs

• Theorems 3.2, 5.2, and 5.5 are special cases of Theorems A.7, A.4, and A.6, respectively, when w(X) = 1.The proof section proceeds through Proposition 3.4 and Theorems A.4, A.6, A.7, and 5.1.Source: B Proofs · p. 10
• The proof roadmap uses Lemmas B.1 and B.2 in proving Theorems A.4 and A.6.The appendix states that these lemmas are important components of those proofs.Source: B Proofs · p. 10
• Figure 3 compares conformal and localized conformal inference at α = .95, with the localized intervals less volatile for test samples close to training data.The localized method uses automatically chosen h.Source: Figure 3 · p. 11

B.1 Proof of Proposition 3.4

• When H_i,j = 1 and ˜α = α, Proposition 3.4 reduces the quantities to empirical quantiles of the score values.The proof orders V_1 through V_n and identifies v̄* with V_⌈(n+1)α⌉.Source: §B.1 · p. 11
• For the second threshold quantity, the proof identifies v*_{i,2} as a quantile of V_1:n.The provided proof passage gives the quantile level as [α − 1/(n+1)]^+ n/(n+1).Source: §B.1 · p. 11
• The proof concludes that setting ˜α = α yields v̄* = ∞ or satisfies equation (G2).The finite-threshold case is considered when ⌈(n+1)α⌉ ≤ n.Source: §B.1 · p. 11

B.2 Proofs Theorems of A.4 and A.6

• The passage identifies Lemma B.1 and Lemma B.2 as important components for proofs of Theorems A.4 and A.6, but does not establish when they are developed.Source: §B.2 · p. 11

B.2.1 Proof of Theorem A.4

• For Theorem A.4, the decision rule is invariant to data ordering conditional on the unordered sample, enabling a permutation-based coverage argument.The proof conditions on T, applies Lemma B.2, then marginalizes over T.Source: §B.2.1 · p. 13

B.2.2 Proof of Theorem A.6

• For Theorem A.6, the proof treats the threshold choices as fixed conditional on the unordered sample before applying the same lemma-based argument.It then marginalizes over T and invokes Lemma B.1.Source: §B.2.2 · pp. 13–14

B.3 Proof of Theorem A.7

• For any value set, permuting the observations lets the proof use the symmetrized argument and establish P{Vn+1 ≤ Q(α̃; F̂)} ≥ α.The proof handles the non-symmetric α̃ by considering possible test-sample positions across permutations.Source: §B.3 · p. 15

B.4.1 Part (a)

• Part (a) establishes P{Ỹn+1 ∈ Ĉ(Xn+1) | Xn+1 = x0} ≥ α for every x0.Source: §B.4.1 · p. 15

B.4.2 Part (b)

• Part (b) derives a bound using a Lipschitz assumption and a regularity condition.Source: §B.4.2 · p. 16

C Choice of H

• The paper considers distance-based and nearest-neighbor-based localizers.Source: C Choice of H · p. 16
• The proposed h-selection criterion minimizes γl × (sl + σl), balancing empirical under-coverage, average interval length, and estimated variability.The procedure excludes choices producing too many infinite-length intervals; by default, the evaluation subset contains 90% of samples.Source: C Choice of H · p. 17
• For high-dimensional features, the paper suggests applying the localizer to a lower-dimensional transformation t(x); finding a suitable transformation is beyond its scope.The simulated illustration uses the feature direction with the largest mutual information with the score.Source: C Choice of H · p. 17
• The Example C.1 simulations use separate training and inference sets of 500 samples and 1000 repetitions, with h selected automatically using the training set.Source: C Choice of H · p. 17
• Both distance-based and nearest-neighbor localized predictions capture the underlying heterogeneity of confidence intervals across Xi,p.Figure 4 plots constructed interval boundaries against feature values and compares them with the actual values and conformal intervals.Source: C Choice of H · pp. 17–18, Figure 4 · p. 18