Adaptive Conformal Inference through the Lens of Blackwell Approachability

Résumé Technique : L'Inférence Conforme Adaptative sous l'Angle de l'Approchabilité de Blackwell

Énoncé du Problème
L'Inférence Conforme Adaptative (ACI), introduite par Gibbs et Candès (2021), répond à la limitation de l'inférence conforme standard, qui repose sur l'hypothèse d'échangeabilité souvent violée dans les contextes séquentiels ou dépendants du temps (ex. : prévision de séries temporelles). L'ACI vise à construire des ensembles de prédiction séquentiellement de telle sorte que la couverture empirique converge vers un niveau souhaité $1-\alpha$ pour des séquences de données arbitraires. Bien que les stratégies d'ACI existantes garantissent la validité (couverture empirique $\geq 1-\alpha$), elles manquent généralement de garanties théoriques simultanées sur l'efficacité (la longueur moyenne des intervalles de prédiction). Dans les contextes adverses, aucune garantie d'efficacité non triviale n'est possible sans hypothèses supplémentaires, tandis que dans les contextes échangeables, les méthodes existantes produisent souvent des longueurs d'intervalles sous-optimales. Le défi central est de concevoir une stratégie unifiée qui assure la validité pour des séquences arbitraires tout en adaptant l'efficacité au degré de stochasticité sous-jacent des données.

Méthodologie
Les auteurs reformulent l'ACI comme un jeu fini répété à deux joueurs avec des gains vectoriels.

1. Action du Apprenant : Sélectionne un niveau de sous-couverture $a_t \in A$, où $A$ est une grille finie dérivée des statistiques d'ordre de l'ensemble de calibration. Cela détermine l'ensemble de prédiction $C_{1-a_t}(x_t)$.
   • Action de l'Opposant : Sélectionne un résultat $y_t$, qui est mappé vers une action discrète $b_t$ représentant l'ensemble conforme le plus "serré" contenant $y_t$.
   • Vecteur de Gain : L'apprenant reçoit un vecteur $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$, encodant l'indicateur de sous-couverture (validité) et la longueur de l'intervalle (efficacité).
2. Cadre d'Approchabilité :
   • L'objectif est de diriger le gain moyen $m_T$ vers un ensemble cible $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$.
   • L'ensemble cible dépend d'une contrainte $Q \subseteq \Delta(B)$ sur le jeu de l'opposant. $Q$ représente l'ensemble des distributions que les actions de l'opposant suivent asymptotiquement.
   • Approchabilité Opportuniste : Les auteurs emploient la théorie de l'approchabilité de Blackwell et son extension par Bernstein et al. (2014), connue sous le nom d'approchabilité opportuniste. Ce cadre permet à l'apprenant d'approcher un ensemble cible plus petit et plus efficace si le jeu de l'opposant est restreint à un ensemble $Q$ spécifique, sans que l'apprenant n'ait besoin de connaître $Q$ à l'avance.
3. Algorithme (BO-ACI) :
   • La stratégie proposée, Blackwell Opportunistic Adaptive Conformal Inference (BO-ACI), utilise un prévisionniste calibré auxiliaire $F$.
   • À chaque tour, $F$ prédit la distribution de la prochaine action $b_t$ de l'opposant.
   • L'apprenant sélectionne de manière déterministe l'action $a_t$ qui minimise la longueur attendue tout en satisfaisant la contrainte de validité face à la distribution prédite (via une fonction de réponse $p^*$).

Contributions Clés

1. Reformulation par la Théorie des Jeux : L'article établit une nouvelle formulation de l'ACI comme un jeu fini répété avec des gains vectoriels, liant explicitement la validité et l'efficacité à un problème d'approchabilité multi-objectif.
2. Stratégie Unifiée (BO-ACI) : Les auteurs introduisent une stratégie basée sur l'approchabilité opportuniste qui garantit la validité pour n'importe quelle séquence de données (stochastique ou adverse) tout en fournissant des garanties d'efficacité qui s'adaptent à la stochasticité inconnue des données.
3. Garanties "Best of Many Worlds" (Le meilleur de plusieurs mondes) : La stratégie atteint un ensemble unifié de garanties :
   • Contexte Échangeable : Récupère la garantie d'efficacité optimale $L(C_{1-\alpha})$, égalant la performance de la prédiction conforme standard dans des conditions idéales.
   • Contexte Adversaire : Garantit la validité mais accepte la borne d'efficacité triviale (longueur d'intervalle $2L$), cohérent avec les résultats d'impossibilité dans les contextes totalement adverses.
   • Contextes Intermédiaires : Fournit des garanties d'efficacité significatives pour des scénarios tels que les changements de distribution uniques ou les données "presque échangeables" (ex. : séries temporelles avec des dépendances faibles), où la longueur de l'intervalle s'adapte au degré de non-échangeabilité.

Résultats

• Convergence Théorique : Le Théorème 19 prouve que sous la stratégie BO-ACI, le vecteur de gain moyen $m_T$ converge presque sûrement vers l'ensemble cible $C_{\alpha, Q}$ pour tout ensemble convexe $Q$ restreignant le jeu de l'opposant.
• Scénarios Spécifiques :
  • Données Échangeables : Si l'opposant est restreint à la distribution uniforme $q_{unif}$, la longueur moyenne de l'intervalle converge vers $L(C_{1-\alpha})$.
  • Changement de Distribution Unique : Si les scores de test suivent une distribution $V$ différente de la distribution de calibration $S$, la stratégie converge vers la longueur $L(C_{1-a_{S,V}})$, où $a_{S,V}$ est le niveau de sous-couverture optimal pour la distribution décalée.
  • $\epsilon$-Échangeable / Séries Temporelles : Pour les données présentant de faibles déviations par rapport à l'échangeabilité (mesurées par la distance de Total Variation ou de Kolmogorov), la stratégie atteint des longueurs proches de la longueur échangeable optimale, se dégradant progressivement à mesure que la déviation augmente.
  • Adversaire : En l'absence de restrictions ($Q = \Delta(B)$), la stratégie assure la validité mais ne peut garantir une efficacité meilleure que la borne triviale, confirmant la nécessité des restrictions $Q$ pour une efficacité non triviale.
• $\epsilon$-Calibration : Les résultats sont étendus aux stratégies utilisant des prévisionnistes $\epsilon$-calibrés (Théorème 34), fournissant des bornes de convergence dépendantes de $\epsilon$.

Signification et Revendications
L'article prétend fournir un cadre théorique unifié pour l'inférence conforme adaptative qui résout la tension entre validité et efficacité. En s'appuyant sur l'approchabilité de Blackwell, les auteurs démontrent qu'il est possible de concevoir un algorithme unique qui :

1. Garantit la validité quel que soit le mécanisme de génération des données.
2. S'adapte automatiquement au "degré de stochasticité" des données pour maximiser l'efficacité.
3. Récupère les résultats optimaux connus dans les cas extrêmes (échangeables et adverses) tout en offrant de nouvelles garanties significatives dans des scénarios intermédiaires et réalistes (tels que la prévision de séries temporelles) où les méthodes précédentes manquaient de fondement théorique.

Les auteurs positionnent ce travail comme une solution "best of many worlds", évitant la nécessité de régler des hyperparamètres basés sur l'hypothèse de la distribution des données, car la stratégie est "inconsciente" de la restriction spécifique de $Q$ tout en l'exploitant si elle existe. Le travail souligne également les limites du cadre totalement adverse, renforçant l'idée que les garanties d'efficacité nécessitent une certaine hypothèse structurelle sur les données.