Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

Résumé technique : Le regret est égal à la covariance : une caractérisation sous forme close pour l'optimisation stochastique

Énoncé du problème
En optimisation stochastique, les décideurs agissent souvent sur la base d'une estimation de coûts incertains (généralement la moyenne, $E[c]$) plutôt que de la réalisation réelle $c$. Le « regret » de cette politique est la perte espérée de la valeur de l'objectif par rapport à une politique omnisciente qui connaît $c$ à l'avance. Formellement, pour une région réalisable $Z$ et un vecteur de coûts $c$, le regret espéré est défini par :
$$\text{Regret}(c) \equiv E[c^\top \pi^*(c)] - E[c^\top \pi^*(E[c])]$$
où $\pi^*(c)$ est la décision optimale pour la réalisation $c$.

L'estimation de cette quantité repose traditionnellement sur l'approximation par moyenne empirique (SAA). Cela consiste à tirer $B$ scénarios de coûts, à résoudre le problème d'optimisation pour chacun, puis à moyenner les résultats. Cette approche est prohibitivement coûteuse en calcul pour une évaluation répétée (par exemple, dans la sélection de modèles ou l'apprentissage en ligne), avec une complexité de $O(Bn^2d^3)$ pour les programmes linéaires (LP) et les programmes quadratiques (QP) comportant $n$ variables et $d$ contraintes. L'article répond au besoin d'une caractérisation sous forme close et computationnellement efficace de ce regret.

Méthodologie : La décomposition Regret-Covariance
La contribution méthodologique centrale est une décomposition algébrique exacte du regret espéré en un terme de covariance et un terme résiduel. L'article démontre que pour tout problème d'optimisation stochastique satisfaisant de légères conditions de régularité :
$$\text{Regret}(c) = \text{Cov}(c, \pi^*(c)) + R(c)$$
où :

• $\text{Cov}(c, \pi^*(c)) = E[c^\top \pi^*(c)] - E[c]^\top E[\pi^*(c)]$ est la covariance scalaire entre le vecteur de coûts et la décision optimale.
• $R(c) = E[c]^\top (E[\pi^*(c)] - \pi^*(E[c]))$ est un terme résiduel capturant la non-linéarité de la carte de décision $c \mapsto \pi^*(c)$ (essentiellement l'erreur résultant de l'inégalité de Jensen appliquée à la fonction de décision).

L'article dérive des bornes supérieures explicites pour l'amplitude du résidu $|R(c)|$ sous trois conditions de régularité :

1. Continuité Lipschitzienne : $|R(c)| \leq L \|E[c]\| \sqrt{\text{tr}(\Sigma_c)}$.
2. Lissité ($C^2$) : $|R(c)| \leq \frac{M}{2} \|E[c]\| \text{tr}(\Sigma_c) + O(\|\Sigma_c\|^{3/2})$.
3. Convexité forte : $|R(c)| \leq \frac{L^2}{2\mu} \text{tr}(\Sigma_c)$.

Contributions clés

1. Conditions d'égalité exacte : L'article établit que le résidu $R(c)$ s'annule exactement ($R(c)=0$) dans des cas spécifiques, rendant le regret égal à la covariance sans approximation. Cela vaut pour :

   • Programmes linéaires (LP) : Lorsque les coûts suivent une distribution continue (absolue continuité par rapport à la mesure de Lebesgue), la carte de décision est constante par morceaux, et les frontières où elle change ont une mesure nulle.
   • Programmes quadratiques sans contrainte (QP) : La décision optimale $\pi^*(c)$ est globalement affine en $c$, satisfaisant la condition d'égalité exacte.
   • Pour les QP contraints et les problèmes Lipschitziens généraux, le résidu est non nul mais borné, fournissant une approximation contrôlée.

2. Réduction de la complexité computationnelle :

   • Scénario A (Données historiques disponibles) : Si un praticien dispose d'un archive historique de paires coût-décision $\{(c_i, \pi^*(c_i))\}_{i=1}^n$, la covariance peut être estimée en un seul passage sur les données avec une complexité de $O(nd^2)$. C'est plusieurs ordres de grandeur plus rapide que la SAA, qui nécessite de résoudre $B$ problèmes d'optimisation ($O(Bn^2d^3)$).
   • Scénario B (Aucune donnée historique) : Si les décisions doivent être calculées à partir de zéro, la formule de covariance offre un aperçu structurel (gradients analytiques) mais ne réduit pas le coût computationnel de la résolution des problèmes d'optimisation.
   • QP sans contrainte : Pour les QP sans contrainte, la covariance peut être calculée analytiquement à partir de la seule matrice de covariance des coûts $\Sigma_c$, ne nécessitant aucune résolution d'optimisation.

3. Théorie statistique : L'article dérive des bornes de concentration, un théorème central limite (TCL) avec une variance asymptotique correcte via la méthode delta, et un estimateur asymptotiquement sans biais pour le résidu $R(c)$. Il démontre que la forme de covariance est la représentation unique du regret sous les hypothèses données.

4. Relation avec l'apprentissage en ligne : L'article clarifie la distinction entre ce regret stochastique (comparaison par rapport à une politique optimale dépendante du coût) et le regret de l'optimisation convexe en ligne (OCO) (comparaison par rapport à la meilleure action fixe a posteriori). Il montre que, bien que les algorithmes OLO minimisent l'erreur cumulative par rapport à un comparateur fixe, ils ne minimisent pas nécessairement le regret stochastique défini ici, qui requiert d'exploiter la structure de covariance de la distribution.

Résultats et validation empirique
Les auteurs valident la théorie sur des données synthétiques et réelles :

• Programmation linéaire : Dans les simulations, la covariance théorique correspond exactement au regret empirique au niveau de la population. Les expériences sur des échantillons finis montrent un petit écart (13,57 %) dû aux taux de convergence différents des deux estimateurs, et non à un échec de l'affirmation de résidu nul.
• Programmation quadratique (Gestion de portefeuille) : Pour les QP sans contrainte (portefeuilles de Markowitz), l'estimateur de covariance correspond exactement au regret empirique. Pour les QP contraints, l'erreur est faible (31 % dans des simulations spécifiques), cohérente avec la borne de résidu $O(\|\Sigma_c\|^2)$.
• Programmation en nombres entiers : Pour les problèmes combinatoires (Sac à dos), le résidu est significatif (jusqu'à 132 % d'erreur relative dans les expériences), indiquant que la formule de covariance doit être utilisée avec prudence pour les problèmes non convexes et discrets.
• Application réelle : En utilisant 10 ans de données d'actions CRSP, l'estimateur basé sur la covariance suit de près le regret de portefeuille réalisé sur des fenêtres glissantes.
• Efficacité de l'entraînement : Dans une boucle d'entraînement « prédire puis optimiser » (PtO), l'utilisation de l'oracle de covariance pour la validation était 71 à 97 fois plus rapide que la SAA (avec $B=50$) et 159 fois plus rapide que la SAA avec $B=1000$, tout en sélectionnant des points de contrôle de qualité identique.

Signification et affirmations
L'article prétend faire progresser la littérature de trois manières fondamentales :

1. Innovation méthodologique : C'est la première étude à prouver que le regret est égal à la covariance exactement pour les LP et les QP sans contrainte, et à fournir des bornes de résidu explicites pour les cas généraux. Elle atteint une complexité de $O(nd^2)$ pour l'estimation exacte du regret, une amélioration significative par rapport aux méthodes basées sur la simulation.
2. Profondeur théorique : Elle comble le fossé entre la performance opérationnelle (regret) et la structure statistique (covariance), révélant des propriétés inaccessibles par la simulation numérique. Elle fournit des repères théoriques pour les algorithmes d'apprentissage.
3. Impact pratique : Le cadre permet une surveillance en temps réel du regret et une comparaison rapide des modèles dans les flux de travail PtO. Il découple le coût de validation de la taille du problème, rendant la validation fréquente réalisable dans des contextes à grande échelle.

Les auteurs positionnent ce travail comme un complément aux domaines existants : il fournit une fondation analytique pour les fonctions de perte utilisées dans « prédire puis optimiser », offre une alternative plus rapide à la SAA pour la validation, et complète l'optimisation robuste distributionnelle (DRO) en quantifiant le regret espéré pour des distributions spécifiques plutôt que des bornes de pire cas. L'article conclut que, bien que la formule de covariance soit une approximation pour les problèmes non convexes généraux, elle est un outil exact et computationnellement supérieur pour la large classe des problèmes linéaires et quadratiques sans contrainte.