Adaptive Conformal Inference through the Lens of Blackwell Approachability

Technische Samenvatting: Adaptieve Conformal Inference door de lens van de Blackwell-benadering

Probleemstelling
Adaptive Conformal Inference (ACI), geïntroduceerd door Gibbs en Candès (2021), adresseert de beperking van standaard conformal inference, die steunt op de aanname van uitwisselbaarheid (exchangeability) die vaak wordt geschonden in sequentiële of tijdsafhankelijke settings (bijv. tijdreeksvoorspelling). ACI beoogt predictiesets sequentieel te construeren zodat de empirische dekking convergeert naar een gewenst niveau $1-\alpha$ voor willekeurige datasequenties. Hoewel bestaande ACI-strategieën validiteit garanderen (empirische dekking $\geq 1-\alpha$), missen ze over het algemeen simultane theoretische garanties op efficiëntie (de gemiddelde lengte van predictie-intervallen). In adversariële settings zijn er geen niet-triviale efficiëntiegaranties mogelijk zonder aanvullende aannames, terwijl in uitwisselbare settings bestaande methoden vaak suboptimale intervallengtes opleveren. De kernuitdaging is het ontwerpen van een verenigde strategie die validiteit garandeert voor willekeurige sequenties, terwijl de efficiëntie wordt aangepast aan de mate van stochasticiteit van de data.

Methodologie
De auteurs herformuleren ACI als een herhaalde tweespeler eindige game met vector-waardige payoffs.

1. Actie van de Learner: Selecteert een miscoverageniveau $a_t \in A$, waarbij $A$ een eindig rooster is afgeleid van de orde statistieken van de kalibratieset. Dit bepaalt de predictieset $C_{1-a_t}(x_t)$.
2. Actie van de Opponent: Selecteert een uitkomst $y_t$, die wordt gemapt naar een discrete actie $b_t \in B$ die de "strakste" conformal set representeert die $y_t$ bevat.
3. Payoff Vector: De learner ontvangt een vector $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$, die de miscoverage indicator (validiteit) en de intervallengte (efficiëntie) codeert.
4. Approachability Framework:
   • Het doel is om de gemiddelde payoff vector $m_T$ te sturen naar een doelset $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$.
   • De doelset hangt af van een restrictie $Q \subseteq \Delta(B)$ op de acties van de opponent. $Q$ representeert de verzameling distributies die de acties van de opponent asymptotisch volgen.
   • Opportunistische Approachability: De auteurs maken gebruik van de theorie van Blackwell approachability en de uitbreiding daarvan door Bernstein et al. (2014), bekend als opportunistische approachability. Dit framework staat de learner toe om een kleinere, efficiëntere doelset te benaderen als de play van de opponent beperkt is tot een specifieke verzameling $Q$, zonder dat de learner $Q$ vooraf hoeft te kennen.
5. Algoritme (BO-ACI):
   • De voorgestelde strategie, Blackwell Opportunistic Adaptive Conformal Inference (BO-ACI), maakt gebruik van een hulp-gekalibreerde forecaster $F$.
   • In elke ronde voorspelt $F$ de distributie van de volgende actie $b_t$ van de opponent.
   • De learner selecteert deterministisch de actie $a_t$ die de verwachte lengte minimaliseert terwijl de validiteitsrestrictie tegen de voorspelde distributie wordt voldaan (via een responsfunctie $p^*$).

Kernbijdragen

1. Game-Theoretische Herformulering: Het artikel vestigt een nieuwe formulering van ACI als een herhaalde eindige game met vector-waardige payoffs, en legt expliciet de link tussen validiteit en efficiëntie aan een multi-objective approachability probleem.
2. Verenigde Strategie (BO-ACI): De auteurs introduceren een strategie gebaseerd op opportunistische approachability die validiteit garandeert voor elke datasequentie (stochastisch of adversarieel), terwijl ze efficiëntiegaranties biedt die adapteren aan de onbekende stochasticiteit van de data.
3. "Best of Many Worlds" Garanties: De strategie bereikt een verenigde set van garanties:
   • Uitwisselbare Setting: Herstelt de optimale efficiëntiegarantie $L(C_{1-\alpha})$, wat overeenkomt met de prestaties van standaard conformal prediction onder ideale condities.
   • Adversariële Setting: Garandeert validiteit maar accepteert de triviale efficiëntiebound (intervallengte $2L$), consistent met onmogelijkheidsresultaten in volledig adversariële settings.
   • Intermediaire Settings: Biedt betekenisvolle efficiëntiegaranties voor scenario's zoals enkelvoudige distributieverschuivingen of "bijna-uitwisselbare" data (bijv. tijdreeksen met zwakke afhankelijkheden), waar de intervallengte adapteert aan de mate van niet-uitwisselbaarheid.

Resultaten

• Theoretische Convergentie: Stelling 19 bewijst dat onder de BO-ACI strategie de gemiddelde payoff vector $m_T$ bijna zeker convergeert naar de doelset $C_{\alpha, Q}$ voor elke convexe verzameling $Q$ die de play van de opponent beperkt.
• Specifieke Scenario's:
  • Uitwisselbare Data: Als de opponent wordt beperkt tot de uniforme distributie $q_{unif}$, convergeert de gemiddelde intervallengte naar $L(C_{1-\alpha})$.
  • Enkelvoudige Distributieverschuiving: Als testscores een distributie $V$ volgen die verschilt van de kalibratiedistributie $S$, convergeert de strategie naar de lengte $L(C_{1-a_{S,V}})$, waarbij $a_{S,V}$ het optimale miscoverage niveau is voor de verschoven distributie.
  • $\epsilon$-Uitwisselbaar/Tijdreeksen: Voor data met kleine afwijkingen van uitwisselbaarheid (gemeten via Total Variation of Kolmogorov afstand), bereikt de strategie lengtes die dicht bij de optimale uitwisselbare lengte liggen, en degradeert deze gracieus naarmate de afwijking toeneemt.
  • Adversarieel: In de afwezigheid van restricties ($Q = \Delta(B)$), garandeert de strategie validiteit maar kan zij geen efficiëntie garanderen die beter is dan de triviale bound, wat de noodzaak van $Q$-restricties voor niet-triviale efficiëntie bevestigt.
• $\epsilon$-Kalibratie: De resultaten worden uitgebreid naar strategieën die gebruikmaken van $\epsilon$-gekalibreerde forecasters (Stelling 34), waarbij convergentiebounds afhankelijk zijn van $\epsilon$.

Betekenis en Claims
Het artikel claimt een verenigd theoretisch framework te bieden voor adaptieve conformal inference dat de spanning tussen validiteit en efficiëntie oplost. Door gebruik te maken van Blackwell approachability, demonstreren de auteurs dat het mogelijk is om een enkel algoritme te ontwerpen dat:

1. Validiteit garandeert ongeacht het datagenererende mechanisme.
2. Automatisch adapteert aan de "mate van stochasticiteit" van de data om de efficiëntie te maximaliseren.
3. Bekende optimale resultaten herstelt in extreme gevallen (uitwisselbaar en adversarieel) terwijl het nieuwe, betekenisvolle garanties biedt in intermediaire, realistische scenario's (zoals tijdreeksvoorspelling) waar voorheen een theoretische onderbouwing ontbrak.

De auteurs positioneren dit werk als een "best of many worlds"-oplossing, waarbij de noodzaak om hyperparameters af te stemmen op de veronderstelde datadistributie wordt vermeden, aangeما de strategie "onbewust" is van de specifieke $Q$-restrictie, maar deze toch exploiteert indien deze aanwezig is. Het werk benadrukt ook de beperkingen van de volledig adversariële setting, wat de noodzaak van $Q$-restricties voor niet-triviale efficiëntie bevestigt.