Adaptive Conformal Inference through the Lens of Blackwell Approachability

Sintesi Tecnica: Inferenza Conforme Adattiva attraverso la lente dell'Approccio di Blackwell

Problema
L'Inferenza Conforme Adattiva (ACI), introdotta da Gibbs e Candès (2021), affronta il limite della standard inferenza conforme, che si basa sull'assunto di scambiabilità spesso violato in contesti sequenziali o dipendenti dal tempo (ad esempio, previsioni di serie temporali). L'ACI mira a costruire set di predizione sequenzialmente affinché la copertura empirica converga a un livello desiderato $1-\alpha$ per arbitrarie sequenze di dati. Sebbene le strategie ACI esistenti garantiscano la validità (copertura empirica $\geq 1-\alpha$), esse generalmente mancano di garanzie teoriche simultanee sulla efficienza (la lunghezza media degli intervalli di predizione). In scenari avversari, non sono possibili garanzie di efficienza non banali senza assunti aggiuntivi, mentre in scenari di scambiabilità, i metodi esistenti producono spesso lunghezze degli intervalli subottimali. La sfida centrale è progettare una strategia unificata che garantisca la validità per sequenze arbitrarie pur adattando l'efficienza al grado di stocasticità sottostante dei dati.

Metodologia
Gli autori riformulano l'ACI come un gioco finito ripetuto a due giocatori con payoff vettoriali.

1. Azione del Learner: Seleziona un livello di miscopertura $a_t \in A$, dove $A$ è una griglia finita derivata dagli ordini statistici del set di calibrazione. Questo determina il set di predizione $C_{1-a_t}(x_t)$.
   • Azione dell'Opponente: Seleziona un esito $y_t$, che viene mappato in un'azione discreta $b_t \in B$ rappresentante il set conforme più "stretto" che contiene $y_t$.
   • Vettore di Payoff: Il learner riceve un vettore $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$, che codifica l'indicatore di miscopertura (validità) e la lunghezza dell'intervallo (efficienza).
2. Framework di Approcciabilità:
   • L'obiettivo è guidare il payoff medio vettoriale $m_T$ verso un insieme target $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$.
   • L'insieme target dipende da un vincolo $Q \subseteq \Delta(B)$ sul gioco dell'opponente. $Q$ rappresenta l'insieme delle distribuzioni che le azioni dell'opponente seguono asintoticamente.
   • Approcciabilità Opportunistica: Gli autori utilizzano la teoria dell'approcciabilità di Blackwell e la sua estensione da parte di Bernstein et al. (2014, nota come approcciabilità opportunistica). Questo framework permette al learner di avvicinarsi a un insieme target più piccolo ed efficiente se il gioco dell'opponente è limitato a un set specifico $Q$, senza che il learner debba conoscere $Q$ in anticipo.
3. Algoritmo (BO-ACI):
   • La strategia proposta, Blackwell Opportunistic Adaptive Conformal Inference (BO-ACI), utilizza un forecaster calibrato ausiliario $F$.
   • Ad ogni round, $F$ predice la distribuzione della prossima azione $b_t$ dell'opponente.
   • Il learner seleziona deterministicamente l'azione $a_t$ che minimizza la lunghezza attesa soddisfacendo il vincolo di validità rispetto alla distribuzione prevista (tramite una funzione di risposta $p^*$).

Contributi Chiave

1. Riformulazione Teoria-Gioco: Il paper stabilisce una nuova formulazione dell'ACI come un gioco finito ripetuto con payoff vettoriali, collegando esplicitamente validità ed efficienza a un problema di approcciabilità multi-obiettivo.
2. Strategia Unificata (BO-ACI): Gli autori introducono una strategia basata sull'approcciabilità opportunistica che garantisce la validità per qualsiasi sequenza di dati (stocastica o avversaria) fornendo al contempo garanzie di efficienza che si adattano alla stocasticità sconosciuta dei dati.
3. Garanzie "Best of Many Worlds": La strategia ottiene un insieme unificato di garanzie:
   • Scenario di Scambiabilità: Recupera la garanzia di efficienza ottimale $L(C_{1-\alpha})$, eguagliando le prestazioni della standard predizione conforme in condizioni ideali.
   • Scenario Avversario: Garantisce la validità ma accetta il limite di efficienza banale (lunghezza dell'intervallo $2L$), coerentemente con i risultati di impossibilità in scenari pienamente avversari.
   • Scenari Intermedi: Fornisce garanzie di efficienza significative per scenari come i cambiamenti distribuzionali singoli o i dati "quasi-scambiabili" (ad esempio, serie temporali con deboli dipendenze), dove la lunghezza dell'intervallo si adatta al grado di non-scambiabilità.

Risultati

• Convergenza Teorica: Il Teorema 19 dimostra che, sotto la strategia BO-ACI, il vettore di payoff medio $m_T$ converge quasi certamente all'insieme target $C_{\alpha, Q}$ per qualsiasi insieme convesso $Q$ che limiti il gioco dell'opponente.
• Scenari Specifici:
  • Dati Scambiabili: Se l'opponente è limitato alla distribuzione uniforme $q_{unif}$, la lunghezza media dell'intervallo converge a $L(C_{1-\alpha})$.
  • Singolo Cambio Distribuzionale: Se i punteggi di test seguono una distribuzione $V$ diversa dalla distribuzione di calibrazione $S$, la strategia converge alla lunghezza $L(C_{1-a_{S,V}})$, dove $a_{S,V}$ è il livello di miscopertura ottimale per la distribuzione spostata.
  • $\epsilon$-Scambiabilità/Serie Temporali: Per dati con piccole deviazioni dalla scambiabilità (misurate tramite distanza di Total Variation o Kolmogorov), la strategia raggiunge lunghezze vicine alla lunghezza ottimale scambiabile, degradando con grazia all'aumentare della deviazione.
  • Avversario: In assenza di restrizioni ($Q = \Delta(B)$), la strategia assicura la validità ma non può garantire un'efficienza migliore del limite banale, confermando la necessità di restrizioni $Q$ per ottenere un'efficienza non banale.
• $\epsilon$-Calibrazione: I risultati sono estesi a strategie che utilizzano forecaster $\epsilon$-calibrati (Teorema 34), fornendo limiti di convergenza dipendenti da $\epsilon$.

Significatività e Rivendicazioni
Il paper rivendica di fornire un framework teorico unificato per l'inferenza conforme adattiva che risolve la tensione tra validità ed efficienza. Sfruttando l'approcciabilità di Blackwell, gli autori dimostrano che è possibile progettare un singolo algoritmo che:

1. Garantisce la validità indipendentemente dal meccanismo di generazione dei dati.
2. Si adatta automaticamente al "grado di stocasticità" dei dati per massimizzare l'efficienza.
3. Recupera i risultati noti negli casi estremi (scambiabili e avversari) offrendo al contempo nuovi, significativi risultati in scenari intermedi e realistici (come le previsioni di serie temporali) dove i metodi precedenti mancavano di supporto teorico.

Gli autori posizionano questo lavoro come una soluzione "best of many worlds", evitando la necessità di sintonizzare gli iperparametri in base alla distribuzione assunta dei dati, poiché la strategia è "non consapevole" della specifica restrizione $Q$ pur sfruttandola se essa esiste. Il lavoro evidenzia anche i limiti del setting pienamente avversario, rinforzando la necessità di assunti strutturali sui dati per ottenere garanzie di efficienza.