Résumé Technique : Prédiction Conformale en Ligne via l'Optimisation en Ligne

Énoncé du Problème

La prédiction conformale offre un cadre fondé sur des principes pour la quantification de l'incertitude, avec des garanties de couverture à échantillon fini. Bien que des avancées récentes aient étendu ces méthodes aux contextes en ligne et séquentiels, les approches existantes fonctionnent généralement à un seul niveau de couverture ($1-\alpha$). Lorsque plusieurs niveaux de couverture sont requis simultanément — un scénario courant dans des applications telles que les prévisions météorologiques, la prévision macroéconomique et la gestion des risques, où les utilisateurs ont des tolérances au risque hétérogènes — les méthodes en ligne standard doivent être exécutées indépendamment pour chaque $\alpha$.

Cette exécution indépendante conduit à une limitation critique : les ensembles de prédiction résultants ne sont pas garantis d'être imbriqués. En termes pratiques, un ensemble de prédiction pour un niveau de confiance plus élevé (par exemple, 99 %) devrait être un sur-ensemble de celui pour un niveau de confiance plus faible (par exemple, 90 %). Sans cette propriété d'imbriqué, les estimations d'incertitude peuvent être incohérentes et difficiles à interpréter. De plus, l'estimation indépendante ne tire pas parti des gains d'efficacité statistique connus de la régression quantile conjointe, où l'imposition de contraintes de non-croisement permet un partage d'information entre les quantiles.

L'article aborde le défi de développer des méthodes de prédiction conformale en ligne qui produisent simultanément des ensembles de prédiction imbriqués sur une gamme de niveaux de couverture tout en maintenant des garanties de couverture à long terme, même sous des séquences de données non stationnaires ou adverses.

Méthodologie

Les auteurs proposent deux algorithmes novateurs basés sur une perspective d'optimisation en ligne. Ils formulent le problème de la mise à jour des seuils conformes comme une tâche d'apprentissage en ligne où l'objectif est de minimiser une fonction de perte conjointe tout en imposant des contraintes de monotonie sur les seuils.

1. Formulation du Problème

Soit $s_t$ un score de non-conformité borné au temps $t$. Pour une séquence de niveaux de non-couverture $0 = \alpha_0 < \alpha_1 < \dots < \alpha_K < \alpha_{K+1} = 1$, l'objectif est d'estimer des seuils $q_{t,i}$ tels que les ensembles de prédiction $C^i_t = \{y : s_t(x,y) \le q_{t,i}\}$ soient imbriqués ($C^{i+1}_t \subseteq C^i_t$). Cela nécessite que les seuils soient décroissants de manière monotone : $q_{t,1} \ge q_{t,2} \ge \dots \ge q_{t,K}$.

Les mises à jour en ligne standard (par exemple, l'Inférence Conformale Adaptative) traitent chaque quantile indépendamment :
$$q_{t+1,i} = q_{t,i} - \eta_t (\alpha_i - \text{err}_{t,i})$$
où $\text{err}_{t,i}$ est l'indicateur de non-couverture. Cette approche manque de couplage entre les niveaux et ne garantit pas la monotonie.

2. Algorithmes Proposés

L'article introduit deux méthodes qui modifient la règle de mise à jour pour imposer la monotonie via des techniques d'optimisation en ligne :

A. Descente de Gradient Exponentié (EG)

Cette méthode exploite l'algorithme de Gradient Exponentié appliqué à un espace de paramètres transformé.

• Paramétrisation : Au lieu de mettre à jour directement les seuils, l'algorithme met à jour les écarts normalisés entre quantiles consécutifs ($w_{t,i}$) sur un simplexe tronqué. Ce changement de variables ($q_{t,i} = B \sum_{j=i}^K w_{t,j}$) garantit intrinsèquement que si les poids sont non négatifs, les quantiles sont ordonnés.
• Règle de Mise à Jour : L'algorithme minimise une fonction de perte conjointe $g_t(\bar{w})$ en utilisant des mises à jour EG. Le gradient pour chaque coordonnée agrège les écarts de non-couverture sur tous les niveaux de quantiles pertinents, induisant un couplage global.
• Mécanisme : Lorsque la méthode est trop conservatrice ou sous-couvre, le terme d'erreur cumulative ajuste les écarts sur toute la courbe de quantiles simultanément. Cela permet à la méthode de « puiser de la force » entre les niveaux, en coordonnant les ajustements pour préserver naturellement l'imbriqué.

B. Descente de Gradient Projeté (PG)

Cette méthode utilise la descente de Gradient Projeté avec un ensemble de contraintes spécifique.

• Règle de Mise à Jour : L'algorithme effectue d'abord des mises à jour de gradient indépendantes sur le vecteur de quantiles $\bar{q}_t$ basé sur la perte conjointe.
• Projection : Le vecteur résultant est ensuite projeté sur l'ensemble convexe des séquences décroissantes ($Q = \{\bar{q} : B \ge q_1 \ge \dots \ge q_K \ge 0\}$).
• Mécanisme : Cette projection est mise en œuvre en utilisant l'Algorithme des Violateurs Adjacents Poolés (PAVA). Contrairement à EG, PG opère via une correction locale : il met à jour les quantiles indépendamment, puis les ajuste minimalement pour restaurer la contrainte d'ordonnancement. Il ne redistribue pas intrinsèquement l'information entre les niveaux lors de l'étape de gradient.

3. Garanties Théoriques

Les auteurs établissent des bornes théoriques pour les deux méthodes :

• Couverture : Les deux méthodes fournissent des garanties de couverture à long terme, assurant que le taux empirique de non-couverture converge vers le $\alpha_i$ cible pour tous les niveaux.
• Regret et Erreur : L'article dérive des bornes sur le regret dynamique et l'écart des quantiles estimés par rapport aux quantiles vrais ($\|\bar{q}_t - \bar{q}^*_t\|_2$). Ces bornes dépendent de la variation dynamique des quantiles vrais ($V_T$) et du pas de mise à jour $\eta$. La borne de la méthode EG suggère une efficacité améliorée grâce au couplage structuré, tandis que PG garantit la faisabilité (l'imbriqué) à chaque pas de temps.

Contributions Clés

1. Nouvelle Formulation : Introduction d'un cadre de prédiction conformale en ligne produisant des ensembles de prédiction imbriqués sur plusieurs niveaux de couverture, permettant une quantification de l'incertitude calibrée sur tout le spectre des risques.
2. Innovation Algorithmique : Proposition de deux algorithmes en ligne (EG et PG) basés sur l'optimisation convexe qui estiment conjointement les seuils conformes tout en imposant strictement la monotonie.
3. Garanties Théoriques : Établissement de garanties de couverture à long terme pour tous les niveaux, accompagnées de preuves assurant des ensembles de prédiction imbriqués à chaque pas de temps.
4. Validation Empirique : Démonstration que ces méthodes atteignent une couverture stable, des ensembles strictement imbriqués et une efficacité statistique améliorée par rapport aux bases de référence indépendantes à niveau unique.

Résultats Expérimentaux

Les méthodes ont été évaluées sur des données synthétiques et réelles.

Données Synthétiques

• Configuration : Un environnement non stationnaire où les distributions de scores évoluent via une marche aléatoire réfléchie latente.
• Constats : La méthode de Gradient Exponentié (EG) a obtenu une erreur de suivi $\ell_1$ plus faible que le suiveur de quantiles indépendant et la méthode de Gradient Projeté. Cela soutient l'hypothèse que le partage d'information entre les quantiles améliore l'efficacité statistique dans le suivi de distributions variant dans le temps. La méthode PG a performé de manière similaire au suiveur indépendant, indiquant des gains limités de l'optimisation conjointe dans ce contexte spécifique par rapport à EG.

Données Réelles (Inflation aux États-Unis)

• Configuration : Prévision de l'inflation de l'Indice des Prix à la Consommation (IPC) aux États-Unis utilisant un modèle AR(3) avec des fenêtres glissantes.
• Constats :
  • Calibration : Toutes les méthodes ont fini par converger vers une faible erreur de calibration. Cependant, le suiveur de quantiles non contraint a exhibé un comportement oscillatoire (surcorrection), tandis que les méthodes contraintes proposées ont montré des trajectoires plus stables.
  • Imbriqué et Lissage : Les méthodes de base (suiveur indépendant et projection a posteriori) ont produit des bandes de prédiction avec des distorsions occasionnelles et des régions non imbriquées. En revanche, les méthodes proposées (surtout EG) ont produit des ensembles de prédiction plus lisses et plus cohérents qui ont strictement préservé la structure imbriquée.
  • Interprétabilité : La mise à jour EG a généré des bandes de prédiction plus lisses en coordonnant les quantiles adjacents via les écarts cumulatifs, réduisant les changements abrupts entre les niveaux.

Importance et Revendications

L'article affirme que son importance principale réside dans la résolution de l'incohérence des estimations d'incertitude dans les contextes en ligne multi-niveaux. En imposant des contraintes structurelles (monotonie) via l'optimisation en ligne, les méthodes proposées fournissent un spectre de risques cohérent.

Les revendications clés incluent :

• Efficacité Statistique : L'estimation conjointe améliore l'efficacité en partageant l'information entre les quantiles, un bénéfice explicitement démontré par la performance de suivi supérieure de la méthode EG.
• Interprétabilité : Les ensembles de prédiction imbriqués résultants sont essentiels pour les contextes de prise de décision où les parties prenantes nécessitent des estimations d'incertitude cohérentes à travers différentes tolérances au risque (par exemple, les planificateurs d'urgence par rapport aux décideurs politiques).
• Stabilité : L'imposition de la monotonie conjointement avec les mises à jour stabilise la dynamique d'apprentissage, empêchant les oscillations erratiques observées dans les suiveurs non contraints.
• Contexte Plus Large : Ce travail comble le fossé entre la robustesse aux attaques adverses (garanties dans les scénarios pires cas) et l'efficacité statistique (suivi de distributions variant dans le temps), présentant la prédiction conformale en ligne comme un problème de suivi de quantiles variant dans le temps avec une analyse de regret dynamique.

Les auteurs notent que des travaux futurs pourraient explorer des taux d'apprentissage adaptatifs pour améliorer davantage les performances dans les environnements non stationnaires, mais la contribution actuelle se concentre sur les avantages structurels de l'estimation conjointe sous des régimes de pas de mise à jour fixes.