PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Validation: Confident Predictions Even When Distributions Shift

Maxime Cauchois, Suyash Gupta, Alnur Ali, John C. Duchi

arXiv:2008.04267v3stat.MLcs.LGstat.ME

TL;DR

Distribution shifts can undermine the validity of predictions, while existing robust-model approaches may not provide tools to validate new-data performance. The paper uses conformal prediction sets with robustness to shifts and reports better coverage than standard split conformal on shifted benchmark test sets.

  • Problem

    Distribution shifts can reduce predictive performance, while common robust-model approaches may sacrifice accuracy and offer few tools to validate performance on new data.

    Source: §1 · p. 2

  • Method

    The paper combines conformal inference with f-divergence neighborhoods and proposes methods to estimate plausible shifts and assess coverage sensitivity.

    Source: §1 · pp. 2–3, balls · p. 9

  • Results

    On shifted CIFAR-10 and ImageNet test sets, the proposed inference consistently gives more coverage, while split conformal averages .88 instead of .95 and .8 instead of .9, respectively.

    Source: §5.1 · p. 29

  • Takeaways & Limitations

    Estimating plausible shifts and assessing coverage sensitivity can help identify which shifts warrant protection, since guarding against all possible shifts may make prediction sets overly conservative.

    Source: §1 · p. 3, §3 · p. 14

    The appropriate level of robustness remains unresolved, although the paper proposes leveraging available validation data to guide it.

    Source: §6 · p. 30

Abstract

from arXiv · show

While the traditional viewpoint in machine learning and statistics assumes training and testing samples come from the same population, practice belies this fiction. One strategy -- coming from robust statistics and optimization -- is thus to build a model robust to distributional perturbations. In this paper, we take a different approach to describe procedures for robust predictive inference, where a model provides uncertainty estimates on its predictions rather than point predictions. We present a method that produces prediction sets (almost exactly) giving the right coverage level for any test distribution in an $f$-divergence ball around the training population. The method, based on conformal inference, achieves (nearly) valid coverage in finite samples, under only the condition that the training data be exchangeable. An essential component of our methodology is to estimate the amount of expected future data shift and build robustness to it; we develop estimators and prove their consistency for protection and validity of uncertainty estimates under shifts. By experimenting on several large-scale benchmark datasets, including Recht et al.'s CIFAR-v4 and ImageNet-V2 datasets, we provide complementary empirical results that highlight the importance of robust predictive validity.

1 Introduction

Distribution shifts expose limits in conventional validation and robust-model approaches, motivating prediction sets that remain calibrated under shifts. The introduction also frames conformal inference, related work, and examples showing coverage failures under covariate shift.

1 Introduction

  • Published accuracies dropped 3–15% on CIFAR and more than 11% on ImageNet after new test sets were created, while robust models may sacrifice accuracy and lack validation tools.The cited benchmark changes followed the original dataset creation processes.Source: §1 · p. 2
  • The paper shifts focus from robust point predictors to calibrated confidence sets, proposing conformal inference for distribution shifts and methods to identify plausible shifts and coverage sensitivities.The authors note that protecting against all possible shifts may yield overly conservative sets.Source: §1 · pp. 2–3

1.1 Background: split conformal inference under exchangeability

  • Standard conformal prediction relies on exchangeability, can fail when even the marginal distribution over X changes, and does not guarantee conditional coverage.The background describes split conformal inference with validation data and a score-based prediction set.Source: §1.1 · pp. 4–5

1.2 Related work

  • Prior work includes covariate-shift methods requiring known likelihood ratios; this paper takes a more general approach that does not restrict shifts to a specific structure.The introduction contrasts predictive validity with work focused on model estimation and selection.Source: §1.2 · pp. 5–6

1.3 A few motivating examples

  • Across nine UCI regression datasets, standard conformal intervals frequently missed true responses under even small covariate shifts, making randomly split validation overly optimistic about future validity.The motivating experiments repeated 50 random train/validation/test splits and tilted test covariates along a principal direction.Source: §1.3 · p. 7

2 Robust predictive inference

The section develops robust validation: rather than changing a predictor, it constructs confidence sets designed to remain valid across specified distribution shifts. Its empirical coverage guarantee depends on the shift being no larger than the chosen radius.

balls

  • The method robustly validates an existing model by choosing confidence sets valid across score distributions in an f-divergence ball around the training score distribution.It does not change the model; the data processing inequality connects bounded shifts in (X, Y) to bounded shifts in scores.Source: balls · p. 10
  • The worst-case quantile reduces to an ordinary quantile at a level determined by f, ρ, and α, independent of the underlying score distribution.Source: balls · p. 10

Then the inverse

  • The inverse characterization can be computed by efficient binary search over a one-dimensional convex optimization problem.The described search reaches accuracy ε in time logarithmic in the search interval.Source: Then the inverse · p. 11

2.2 Achieving coverage with empirical estimates

  • Empirical score quantiles yield conditional future-coverage guarantees from standard quantile statistics.The coverage bound is related to the amount of shift.Source: §2.2 · p. 12
  • The main coverage guarantee applies when the true shift between the validation and test score distributions is no greater than the chosen radius.The theorem assumes the test score is independent of the validation scores.Source: §2.2 · p. 12
  • For variation-distance shifts of at most ρ, an identical increase in the quantile level gives (nearly) correct coverage.Source: §2.2 · p. 13

3 Procedures for estimating future distribution shift

The section develops ways to estimate plausible future shift from validation data and use that estimate to construct prediction sets with robust coverage. It considers coverage over likely shift directions and procedures for finding directions that challenge coverage.

3 Procedures for estimating future distribution shift

  • Validation-data variability and regions with high nonconformity scores guide the estimated shift amount ρ, reflecting both observed variation and plausible future shifts.The motivation includes protecting coverage across mixtures of subpopulations represented in the validation data.Source: §3 · p. 14
  • Uniform worst-coverage computation is generally intractable in high dimensions, so the procedures target coverage over most plausible directions or optimize a surrogate for the worst direction.For a fixed direction, the cited procedures can compute worst coverage in O(d·n) time.Source: §3 · p. 16

3.1 High-probability coverage over specific classes of shifts

  • For a given direction class, the procedure provides 1 − α coverage over all R ∈ Rv with Q0(X ∈ R) ≥ δ, and approaches uniform 1 − α coverage when subsets in R have finite VC-dimension.Coverage becomes more conservative as αv decreases to 0, reducing to condition (10) at αv = 0.Source: §3.1 · pp. 16–17

3.2 Finding directions of maximal shift

  • The worst-direction procedure separates high-score from low-score observations to identify challenging shifts and protect coverage against score distributions within an estimated divergence bound.It requires one M-estimation problem rather than sampling many directions; consistency of the nonparametric estimator depends on stochastic-order assumptions.Source: §3.2 · pp. 19, 21
  • The high-dimensional experiments use least-squares or SVM estimators for linear shifts, a more restrictive approach whose consistency requires stronger distributional assumptions.The paper presents an example of such assumptions in Appendix A.2.1.Source: §3.2 · p. 21

4 Coverage sensitivity under covariate shifts

This section measures how covariate shifts affect predictive-set coverage, complementing broad shift protection with analysis of specific covariate subsets. It defines sensitivity measures and develops estimators, including a debiased cross-fit approach.

4 Coverage sensitivity under covariate shifts

  • Coverage sensitivity targets a practical trade-off: protection against all possible shifts can produce conservative sets, while subset-specific analysis identifies directions of instability.The analysis focuses on covariate shifts that change selected features while preserving the conditional score distribution given those features.Source: §4 · pp. 21–22

4.1 Covariate-specific sensitivity analysis

  • Covariate-specific sensitivity measures worst miscoverage over shifts within an f-divergence ball that preserves the conditional distribution of scores given the selected covariates.Only the marginal distribution of the selected covariates changes under this shift definition.Source: §4 · p. 22, §4.1 · pp. 22–23
  • A debiasing correction with an additional large unlabeled covariate sample yields a consistent, asymptotically normal sensitivity estimate.The method uses unlabeled examples to estimate the relevant quantile from the estimated miscoverage function.Source: §4.1 · p. 23, §4.2 · p. 25

4.2 Cross-fit dual estimation of the sensitivity function

  • The cross-fit estimator successively estimates the miscoverage function, its quantile, and an augmentation term before combining them into a debiased sensitivity estimate.Debiasing typically sacrifices monotonicity of the estimate in the shift amount ρ.Source: §4.1 · p. 23, §4.2 · p. 24

5 Empirical analysis

Experiments on new CIFAR-10, MNIST, and ImageNet test sets assess whether data-driven shift estimates provide marginal coverage under real distribution shifts. Standard split conformal undercovers on CIFAR-10 and ImageNet, while the proposed methods give more coverage without substantially larger sets.

5.1 CIFAR-10, MNIST, and ImageNet datasets

  • The evaluation uses CIFAR-10.1 v4, QMNIST50K, and ImageNetV2 Threshold0.7 as new test sets, with nominal coverage 0.95 for CIFAR-10 and MNIST and 0.9 for ImageNet.The models are trained on 70% of the original datasets and validated on the remaining 30%.Source: §5.1 · pp. 27–28
  • 0.88 versus nominal 0.95 coverage on new CIFAR-10 and 0.8 versus nominal 0.9 on ImageNet: split conformal undercovers, while the proposed methods consistently give more coverage.The sampling strategy delivers marginal coverage without over-covering, and this pattern holds across shift-estimation strategies despite their structural assumptions.Source: Figure 2 · p. 27, Figure 3 · p. 28, Figure 4 · p. 28
  • Regression- and classification-based shift-direction estimation are faster than sampling directions, with costs O(nd min{n, d}) and O(knd), respectively.The sampling cost depends on the number k of directions sampled.Source: §5.1 · pp. 29–30
  • The proposed confidence sets are not substantially larger than standard conformal sets, despite the large number of ImageNet classes.The comparison is reported for Figures 2–4.Source: Figure 2 · p. 27, Figure 3 · p. 28, Figure 4 · p. 28

6 Discussion and conclusions

The discussion argues for robust predictive inference and identifies calibration of the appropriate robustness level as an unresolved question.

6 Discussion and conclusions

  • Fully understanding the “right” level of robustness remains an open question; the paper offers approaches that leverage available validation data.The authors suggest comparing new test covariates with validation data, while noting likelihood-ratio reweighting may be infeasible in high dimensions.Source: §6 · p. 30
  • Likelihood-ratio reweighting is described as sometimes feasible but likely impossible in high-dimensional scenarios.The authors propose exploring projections to match statistics of new test covariates as a possible alternative.Source: §6 · p. 30

A.1 High-probability coverage over specific classes of shifts

The section develops guarantees for coverage across specified distribution shifts and studies how to identify the worst shift direction. It also establishes when estimating that direction can support asymptotically uniform coverage.

A.1 High-probability coverage over specific classes of shifts

  • With finite VC-dimension, Procedure 1 approaches uniform 1−α coverage over the specified classes of shifts.For sampled directions, worst coverage is at least 1−α−O(1/√n) with probability nearly 1−α_v; for at least an α_v fraction of directions it is at most 1−α+O(1/√n), for regions with training mass at least δ.Source: §A.1 · pp. 31–32

A.2 Population-level consistency of the worst direction

  • Under Assumption A2, the worst shift direction aligns large covariate values with large nonconformity scores; RKHS estimation can recover its hardness ranking asymptotically.The recovery is up to a non-decreasing transformation under appropriate conditions on the RKHS.Source: §A.2 · pp. 33, 35, 36

A.2.1 Consistency of linear shifts estimators

  • Under the stated conditions, least-squares estimation identifies the worst linear shift direction up to proportionality, but need not do so in more general models.The paper presents Gaussian covariates and typical nonconformity scores in Example 4 as satisfying the proposition’s conditions.Source: §A.2.1 · p. 36

A.3 Asymptotic estimation of the worst direction

  • Under Assumptions A2–A4, Algorithm 2’s estimated confidence sets achieve asymptotically uniform coverage over the specified shifts; the authors also recommend examining within-dataset coverage variation.The paper describes the assumptions required for this guarantee as strong, while arguing that the methodology remains useful for assessing possible future shifts.Source: §A.3 · pp. 37–38

B.1 Intuition and sketch proof for the cross-fit augmented esti-

The section sketches a debiased cross-fit estimator for sensitivity and establishes its asymptotic behavior. The estimator uses a first-order correction, and under stated assumptions its path converges to a tight Gaussian process and is √n-consistent.

B.1 Intuition and sketch proof for the cross-fit augmented esti-

  • A debiased cross-fit estimator uses a first-order correction to an empirical sensitivity calculation, with unlabeled covariates helping estimate needed expectations.The construction splits observations into batches, computes batch-specific augmented estimates, and averages them.Source: §B.1 · pp. 38–39

B.2 Consistency and convergence rate of the augmented estima-

  • Under Assumptions A6–A8, the sensitivity estimator converges in L∞(K) to a tight Gaussian process, implying √n-consistency.The theorem also characterizes the limiting process’s covariance in its proof.Source: §B.2 · pp. 40–41

C.1 UCI datasets

Across UCI shifts, robust conformal prediction often restores coverage where standard conformal undercovers. In COVID-19 forecasting and covariate-sensitivity experiments, the results compare coverage and interval length under estimated shifts and identify covariates associated with the largest coverage losses.

C.1 UCI datasets

  • Robust conformal prediction restores average coverage above nominal on abalone, delta ailerons, kinematics, puma, and airfoil, where standard conformal undercovers.The reported median chi-squared divergences for those datasets are .03, .02, .04, .05, and 3.65, respectively.Source: §C.1 · p. 42
  • Coverage losses on ailerons, banking, and Boston and California housing coincide with median chi-squared divergences roughly twice as large as on most improved datasets.Ailerons still covers; the passage attributes the losses on the remaining datasets to the higher divergence.Source: §C.1 · p. 42

C.2 COVID-19 forecasting

  • Standard conformal undercovers on the COVID-19 time series, while both robust procedures retain validity; the α/2 heuristic gives slightly longer intervals than most alternatives.The robust procedures use regression-based and nonparametric divergence estimates; the α/2 heuristic does not adapt its miscoverage level to the estimated shift.Source: §C.2 · p. 44, Figure 6 · p. 45, Figure 7 · p. 46
  • The robust procedure paired with Nguyen et al.’s nonparametric divergence estimator appears to offer the best balance between coverage and interval length in this instance.The comparison is on COVID-19 time series data.Source: §C.2 · pp. 44–45
  • On April 16, 2021, robust prediction intervals generally contain the true response across the United States, including Michigan during a pronounced incidence spike.The paper illustrates the comparison using maps of observed cases and interval endpoints.Source: §C.2 · p. 45, Figure 8 · p. 46, Figure 9 · p. 47

C.3 Experiments on covariate sensitivity

  • Coverage is most sensitive to shifts in House age for real-estate data and Pressure for weather data, while wine-quality coverage is nearly equally sensitive to all covariates.Across all three datasets, observed miscoverage on upper- or lower-quantile subsets falls below the estimated maximum-miscoverage line.Source: §C.3 · pp. 48–49

D.1 Proof of Proposition 1

The proof characterizes how the worst-case distribution function changes with the divergence radius and connects it to worst-case quantiles. Subsequent proof steps invoke exchangeability, independence, and empirical bounds under stated assumptions.

D.1 Proof of Proposition 1

  • The function g_f,ρ is non-increasing in ρ, non-decreasing in β, continuous, and bounded above by β.For β above β0(ρ), it is strictly increasing; equality in the bound holds at β = 0, while strict inequality holds for β in (0, 1).Source: §D.1 · p. 49

D.1.2 Proof of Lemma D.2

  • The worst-case cumulative distribution function is bounded through g_f,ρ applied to the original CDF value F(t).The proof handles boundary cases F(t) = 0 and F(t) = 1 separately and uses data processing for the reverse inequality when 0 < F(t) < 1.Source: §D.1 · p. 51, §D.1.2 · pp. 53–54

D.1.1 Proof of Lemma D.1

  • The proof establishes convexity of g_f,ρ by expressing it as a partial minimization involving the perspective transform of f.The perspective transform is defined as f_per(t, β) = βf(t/β).Source: §D.1.1 · p. 52

D.2 Proof of Proposition 2

  • The proof of Proposition 2 uses independence of the test score from the training sample.The passage identifies this independence in the step involving the test score and the training observations.Source: §D.2 · p. 55

D.3 Proof of Theorem 1

  • Theorem 1’s proof uses exchangeability to make the test score’s rank uniform over {1, . . . , n + 1}.The proof also invokes the quantile-coverage lemma and considers finite divergence ρ⋆ = D_f(P_test||P_0).Source: §D.3 · pp. 55–56

D.4 Proof of Corollaries 2.1 and 2.2

  • For the corollary proofs, monotonicity of g_f,ρ relates the bound at ρ to a true divergence ρ⋆ ≥ ρ; the first corollary also uses convexity.The supplied proof passages identify these proof ingredients without stating the resulting corollary bounds.Source: §D.4 · pp. 56–57

E Proof of Theorem 2

The proof of Theorem 2 develops empirical bounds for worst-case quantiles and uses them to relate the algorithm’s selected quantile to its confidence sets. Additional lemmas use conditional-region arguments and linear-projection properties.

E Proof of Theorem 2

  • Theorem 2’s proof combines VC-covering bounds with monotonicity of worst-case coverage in the quantile to derive simultaneous bounds over v ∈ V.Some of the stated inequalities require Assumption A1, which entails distinct scores.Source: E Proof of Theorem 2 · pp. 57–59

E.1 Proof of Lemma A.1

  • The proof identifies the algorithm’s selected quantile with the robust conformal threshold, using the empirical quantile construction.The passage states that the resulting confidence set equals the robust conformal set for all x.Source: E Proof of Theorem 2 · p. 58, §E.1 · p. 61

F.1.1 Proof of Lemma A.2

  • The Lemma A.2 proof considers miscoverage conditional on thresholded covariate regions and invokes Assumption A2 and continuity.Source: §F.1.1 · p. 62

F.1.2 Proof of Lemma A.3

  • For linear covariate projections, the Lemma A.3 proof uses the bound P(A ∩ B) ≤ min(P(A), P(B)) and the uniform distribution of each Xᵀv.Source: §F.1.2 · p. 63

F.1.3 Proof of Lemma A.4

This section develops proof tools for the paper’s results, including order, estimator, continuity, and convergence arguments. It establishes uniform closeness of worst-coverage estimates for estimated and true scores, then uses continuity and monotonicity to complete Lemma A.4 and finalize Theorem 3.

F.1.3 Proof of Lemma A.4

  • Under Assumption A2, the proof uses upper-orthant ordering to bound joint score-and-ranking probabilities by corresponding probabilities involving v⋆.The accompanying lemma gives a functional characterization of upper-orthant ordering using nonnegative, nondecreasing functions.Source: §F.1.3 · pp. 63–64

F.1.4 Proof of Lemma A.5

  • The proof of Lemma A.5 rewrites E[sign(S1 − S2) | X1] using conditional probabilities of strict ordering and ties.It gives the identity as 2P(S1 > S2 | X1) − 1 + P(S1 = S2 | X1).Source: §F.1.4 · p. 65

F.1.5 Proof of Proposition 3

  • The Proposition 3 proof compares the finite-sample estimator with a theoretical estimator, using a bounded sign-threshold class and a bounded kernel.The excerpt invokes Donsker’s theorem for the sign-threshold class, whose VC-dimension is at most 2.Source: §F.1.5 · pp. 66–67
  • The Proposition 3 proof establishes Fv⋆(v⋆(X)) = FηS(ηS(X)) almost surely, connecting the distributions of the transformed v⋆ and ηS values.The excerpt says this equality concludes the proof of the proposition’s second part.Source: §F.1.5 · pp. 68–69

F.1.6 Proof of Proposition 4

  • In the Proposition 4 proof, Assumption A2 and isotropy of the transformed covariates are used to compare equal covariance-norm vectors; the proposition also assumes E[s(X, Y)X] ≠ 0.The excerpt states the comparison step but does not include the proposition’s full conclusion.Source: §F.1.6 · p. 70

F.2 Proof of Theorem 3

  • Theorem 3’s proof is organized into lemmas on worst-coverage regularity and convergence, followed by a section combining those results.Source: §F.2 · p. 71

F.2.1 Lemmas on worst coverage estimation

  • Under Assumption A4, Lemma F.2 states that worst coverage is continuous at tuples (q, v⋆, δ), with V considered as a subset of L2(PX).Source: §F.2.1 · p. 71
  • The excerpt also states convergence results for the confidence-set mapping and a Glivenko–Cantelli result for worst coverages under Assumption A4.The supplied passages do not show the full convergence statements or their rates.Source: §F.2.1 · pp. 73–74
  • Under Assumptions A3 and A4, the estimated score s_n and true score s have uniformly close worst coverage.The proof controls differences in thresholded probabilities using score approximation and continuity of the distribution of S.Source: §F.2.1 · pp. 76–77

Proof

  • The Lemma A.4 proof uses monotonicity in q and continuity in v to pass from finite approximations to the desired result as ε is arbitrary.For each fixed v, worst coverage is bounded and non-decreasing in q; for each fixed q, it is continuous in v.Source: Proof · pp. 77–78

F.2.2 Finalizing the proof of Theorem 3

  • Combining Lemmas F.3–F.6 gives estimated worst coverage 1 − α + u_n, and Assumption A2 identifies the worst coverage over R_v⋆ with that over R.The passage states u_n ≥ 0 and uses Assumption A5 in the finalization argument.Source: §F.2.2 · pp. 78–79

G Proof of Theorem 4

The proof of Theorem 4 reduces the result to a Donsker property and a uniformly negligible remainder, then establishes supporting bounds through technical lemmas.

G Proof of Theorem 4

  • Theorem 4’s proof establishes that the function class is Donsker and that the remainder is uniformly negligible over ρ ∈ K.The argument invokes Slutsky’s lemma to reduce the proof to these two requirements.Source: G Proof of Theorem 4 · p. 80

G.1 Proof of technical lemmas

  • Lemma G.4 establishes quantile stability under sup-norm perturbations, which is used to bound differences between threshold indicators.The proof compares the quantiles of bounded random variables and applies the result to indicator functions defined by thresholds.Source: §G.1 · pp. 83–84

G.1.1 Proof of Lemma G.2

  • Lemma G.2’s proof applies a maximal inequality to function families for both subsampled and full estimator pairs, using envelope and covering-number bounds.The proof states that both estimator pairs satisfy the inequality’s application conditions.Source: §G.1.1 · pp. 85–86

G.1.2 Proof of Lemma G.3

  • The augmentation’s benefit appears in Lemma G.3: the population-average difference is o(n^-1/2) under Assumptions A6 and A7.The proof identifies this rate as sufficient to control the difference between expectations under P.Source: §G.1.2 · pp. 86–87
Loading 2008.04267v3…