Adaptive Conformal Inference through the Lens of Blackwell Approachability

Technische Zusammenfassung: Adaptive Konforme Inferenz durch die Linse des Blackwell-Ansatzes

Problemstellung
Adaptive Konforme Inferenz (Adaptive Conformal Inference, ACI), eingeführt von Gibbs und Candès (2021), adressiert die Einschränkung der Standard-Konformen Inferenz, die auf der Annahme der Austauschbarkeit beruht, welche in sequentiellen oder zeitabhängigen Szenarien (z. B. Zeitreihenprognose) oft verletzt wird. ACI zielt darauf ab, prädiktive Mengen sequentiell so zu konstruieren, dass die empirische Abdeckung gegen ein gewünschtes Niveau $1-\alpha$ konvergiert, unabhängig von der Datensequenz. Während bestehende ACI-Strategien die Validität (empirische Abdeckung $\geq 1-\alpha$) garantieren, mangelt es ihnen im Allgemeinen an simultanen theoretischen Garantien bezüglich der Effizienz (der durchschnittlichen Länge von Prädiktionsintervallen). In adversariellen Szenarien sind keine nicht-trivialen Effizienzgarantien ohne zusätzliche Annahmen möglich, während bestehende Methoden in austauschbaren Szenarien oft suboptimale Intervalllängen liefern. Die zentrale Herausforderung besteht darin, eine einheitliche Strategie zu entwerfen, die Validität für beliebige Sequenzen sicherstellt und gleichzeitig die Effizienz an den Grad der Stochastizität der Daten anpasst.

Methodik
Die Autoren formulieren ACI als ein wiederholtes Zwei-Spieler-Endliches Spiel mit vektorwertigen Payoffs um.

1. Aktion des Lernenden: Wählt ein Fehldeckungsniveau $a_t \in A$, wobei $A$ ein endliches Gitter ist, das aus den Ordnungsstatistiken des Kalibrierungsdatensatzes abgeleitet wurde. Dies bestimmt die Prädiktionsmenge $C_{1-a_t}(x_t)$.

• Aktion des Gegners: Wählt ein Ergebnis $y_t$, das auf eine diskrete Aktion $b_t \in B$ abgebildet wird, welche die „engste“ konforme Menge darstellt, die $y_t$ enthält.
• Payoff-Vektor: Der Lernende erhält einen Vektor $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$, der die Fehldeckungs-Indikatorfunktion (Validität) und die Intervalllänge (Effizienz) kodiert.

2. Approachability-Framework:
   • Das Ziel ist es, den durchschnittlichen Payoff-Vektor $m_T$ auf eine Zielmenge $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$ zu steuern.
   • Die Zielmenge hängt von einer Beschränkung $Q \subseteq \Delta(B)$ auf das Spiel des Gegners ab. $Q$ repräsentiert die Menge der Verteilungen, denen die Aktionen des Gegners asymptotisch folgen.
   • Opportunistische Approachability: Die Autoren nutzen die Theorie der Blackwell-Approachability und deren Erweiterung durch Bernstein et al. (2014, bekannt als opportunistische Approachability). Dieses Framework ermöglicht es dem Lernenden, eine kleinere, effizientere Zielmenge anzusteuern, wenn das Spiel des Gegners auf eine spezifische Menge $Q$ beschränkt ist, ohne dass der Lernende $Q$ im Voraus kennen muss.
3. Algorithmus (BO-ACI):
   • Die vorgeschlagene Strategie, Blackwell Opportunistic Adaptive Conformal Inference (BO-ACI), nutzt einen Hilfs-kalibrierten Forecaster $F$.
   • In jeder Runde prognostiziert $F$ die Verteilung der nächsten Aktion $b_t$ des Gegners.
   • Der Lernende wählt deterministisch die Aktion $a_t$, welche die erwartete Länge minimiert und gleichzeitig die Validitätsbeschränkung gegenüber der prognostizierten Verteilung erfüllt (über eine Response-Funktion $p^*$).

Zentrale Beiträge

1. Spieltheoretische Reformulierung: Die Arbeit etabliert eine neuartige Formulierung von ACI als wiederholtes endliches Spiel mit vektorwertigen Payoffs und verknüpft Validität und Effizienz explizit mit einem Multi-Objective-Approachability-Problem.
2. Einheitliche Strategie (BO-ACI): Die Autoren führen eine Strategie basierend auf opportunistischer Approachability ein, die Validität für beliebige Datensequenzen (stochastisch oder adversariell) garantiert und gleichzeitig Effizienzgarantien bietet, die sich an die unbekannte Stochastizität der Daten anpassen.
3. „Best of Many Worlds“-Garantien: Die Strategie erzielt einen Satz einheitlicher Garantien:
   • Austauschbares Szenario: Rekuperiert die optimale Effizienzgarantie $L(C_{1-\alpha})$ und erreicht damit die Leistung der Standard-Konformen Prädiktion unter idealen Bedingungen.
   • Adversarielles Szenario: Garantiert Validität, akzeptiert jedoch die triviale Effizienzgrenze (Intervalllänge $2L$), was konsistent mit den Impossibility-Resultaten in vollumfänglich adversariellen Settings ist.
   • Intermediäre Szenarien: Liefert aussagekräftige Effizienzgarantien für Szenarien wie einzelne Verteilungsverschiebungen oder „fast-austauschbare“ Daten (z. B. Zeitreihen mit schwachen Abhängigkeiten), bei denen sich die Intervalllänge an den Grad der Nicht-Austauschbarkeit anpasst.

Ergebnisse

• Theoretische Konvergenz: Theorem 19 beweist, dass unter der BO-ACI-Strategie der durchschnittliche Payoff-Vektor $m_T$ fast sicher gegen die Zielmenge $C_{\alpha, Q}$ konvergiert, für jede konvexe Menge $Q$, die das Spiel des Gegners einschränkt.
• Spezifische Szenarien:
  • Austauschbare Daten: Wenn der Gegner auf die Gleichverteilung $q_{unif}$ beschränkt ist, konvergiert die durchschnittliche Intervalllänge gegen $L(C_{1-\alpha})$.
  • Einzelne Verteilungsverschiebung: Wenn die Test-Scores einer Verteilung $V$ folgen, die sich von der Kalibrierungsverteilung $S$ unterscheidet, konvergiert die Strategie gegen die Länge $L(C_{1-a_{S,V}})$, wobei $a_{S,V}$ das optimale Fehldeckungsniveau für die verschobene Verteilung ist.
  • $\epsilon$-Austauschbar / Zeitreihen: Für Daten mit geringfügigen Abweichungen von der Austauschbarkeit (gemessen durch Total Variation oder Kolmogorov-Distanz) erzielt die Strategie Längen nahe der optimalen Austauschbarkeitslänge und degradiert kontrolliert, wenn die Abweichung zunimmt.
  • Adversariell: In Abwesenheit von Beschränkungen ($Q = \Delta(B)$) stellt die Strategie die Validität sicher, kann aber keine Effizienz besser als die triviale Grenze garantieren, was die Notwendigkeit von $Q$-Beschränkungen für nicht-triviale Effizienz bestätigt.
• $\epsilon$-Kalibrierung: Die Ergebnisse werden auf Strategien mit $\epsilon$-kalibrierten Forecastern erweitert (Theorem 34), wobei die Konvergenzgrenzen von $\epsilon$ abhängen.

Bedeutung und Behauptungen
Das Paper beansprucht, einen einheitlichen theoretischen Rahmen für adaptive konforme Inferenz bereitzustellen, der das Spannungsverhältnis zwischen Validität und Effizienz auflöst. Durch die Nutzung der Blackwell-Approachability demonstrieren die Autoren, dass es möglich ist, einen einzigen Algorithmus zu entwerfen, der:

1. Validität unabhängig vom datengenerierenden Mechanismus garantiert.
2. Automatisch zum „Grad der Stochastizität“ der Daten passt, um die Effizienz zu maximieren.
3. Bekannte optimale Ergebnisse in Extremfällen (austauschbar und adversariell) wiederherstellt und gleichzeitig neue, aussagekräftige Garantien für intermediäre, realistische Szenarien (wie die Zeitreihenprognose) bietet, für die es zuvor keine theoretische Untermauerung gab.

Die Autoren positionieren diese Arbeit als eine „Best of Many Worlds“-Lösung, die keine Notwendigkeit zur Feinabstimmung von Hyperparametern basierend auf der angenommenen Datenverteilung hat, da die Strategie „unbewusst“ gegenüber der spezifischen $Q$-Beschränkung ist, diese aber dennoch ausnutzt, falls sie existiert. Die Arbeit hebt zudem die Grenzen des vollumfänglich adversariellen Settings hervor und unterstreicht, dass Effizienzgarantien strukturelle Annahmen über die Daten erfordern.