Optimal MILP Approach to Group Sequential Hypothesis Test

Résumé technique : Approche MILP optimale pour le test d'hypothèse séquentiel par groupes

Énoncé du problème
Le test d'hypothèse séquentiel par groupes (GST) est un cadre standard pour effectuer plusieurs tests sur des données arrivant de manière séquentielle à $K$ points temporels fixes (groupes) avec une taille d'échantillon totale pré-spécifiée $N$. L'objectif principal dans de nombreuses applications, telles que les essais cliniques et l'expérimentation numérique en ligne, est de parvenir à une décision valide (rejet de l'hypothèse nulle $H_0$) aussi tôt que possible afin de minimiser la taille d'échantillon attendue (ESS).

Les méthodes GST existantes, notamment Lan-DeMets, Pocock et O'Brien-Fleming, reposent sur des « fonctions de dépense d'alpha » pré-spécifiées pour répartir le budget d'erreur de type I ($\alpha$) sur les $K$ étapes. Bien que ces méthodes garantissent un contrôle uniforme de l'erreur de type I, le choix de la fonction de dépense est souvent heuristique. La littérature n'a pas suffisamment exploré la fonction de dépense d'alpha optimale qui minimise le temps d'arrêt attendu tout en satisfaisant les contraintes sur l'erreur de type I ($\alpha$) et l'erreur de type II ($\beta$). Les auteurs notent que si Silva et al. (2020) ont abordé ce problème pour des résultats binaires, le cas général impliquant des résultats continus et non bornés reste un problème d'optimisation ouvert.

Méthodologie : Approche S-MILP
L'article propose une approche novatrice basée sur l'optimisation pour déterminer directement les seuils de rejet optimaux $\theta_1, \dots, \theta_K$ plutôt que de s'appuyer sur des fonctions de dépense d'alpha déterministes. La méthodologie se déroule en deux étapes principales :

1. Formulation comme problème d'optimisation stochastique :
   Les auteurs formulent le problème de minimisation de la taille d'échantillon attendue sous l'hypothèse alternative $H_a$, soumis à des contraintes sur les erreurs de type I et de type II. La fonction objectif et les contraintes impliquent des probabilités d'événements complexes (par exemple, la statistique de test franchissant un seuil à l'étape $k$ sans avoir franchi les seuils précédents). Cette formulation est généralement ingérable en raison de la nature non convexe et discontinue des fonctions indicatrices impliquées dans les calculs de probabilité.

2. Approximation par moyenne d'échantillon (SAA) et programmation linéaire en nombres entiers mixtes (MILP) :
   Pour rendre le problème traitable, les auteurs utilisent une Approximation par Moyenne d'Échantillon (SAA). Ils génèrent $M$ trajectoires d'échantillons indépendantes des statistiques de test sous $H_0$ et $H_a$. Les termes de probabilité de la formulation originale sont remplacés par des moyennes empiriques (estimations de Monte Carlo) sur ces $M$ trajectoires.

   Le problème SAA résultant est ensuite reformulé comme un Programme Linéaire en Nombres Entiers Mixtes (MILP). Cela est réalisé en introduisant des variables binaires auxiliaires pour linéariser les fonctions indicatrices (par exemple, $\mathbb{I}(S_k \leq \theta_k)$). Plus précisément :

   • Les variables binaires représentent si une trajectoire d'échantillon franchit un seuil.
   • Des contraintes logiques (utilisant des formulations « big-M ») relient ces variables binaires aux variables de décision continues (les seuils $\theta_k$).
   • L'objectif devient une fonction linéaire de ces variables binaires pondérées par les tailles d'échantillon à chaque étape.

   Cette formulation S-MILP permet d'utiliser des solveurs commerciaux standards (par exemple, Gurobi, CPLEX) pour trouver les seuils optimaux.

Extensions et généralisations
L'article étend le cadre S-MILP central à plusieurs scénarios pratiques :

• Variance inconnue (tests $t$) : Puisque la distribution de la statistique $t$ sous $H_a$ dépend de la variance inconnue $\sigma$, les auteurs proposent deux correctifs : (1) reformuler l'hypothèse en termes de taille d'effet standardisée $\delta$, ou (2) utiliser une étude pilote pour estimer $\sigma$ et la traiter comme un paramètre d'insertion.
• Statistiques de test générales : Les garanties de convergence sont généralisées à des statistiques de test continues arbitraires, à condition que leurs distributions puissent être échantillonnées et satisfont certaines conditions de bornitude de densité.
• Conceptions symétriques : Le cadre est étendu pour permettre un arrêt précoce non seulement pour le rejet ($H_a$) mais aussi pour l'acceptation ($H_0$), optimisant la taille d'échantillon attendue sous une stratégie hybride.

Garanties théoriques
L'article fournit une analyse rigoureuse de la convergence à échantillon fini pour l'approche S-MILP :

• Faisabilité : Avec une forte probabilité, la région faisable du problème SAA approxime la région faisable réelle du problème d'optimisation original à mesure que $M$ augmente.
• Fossé d'optimalité : La différence entre la valeur objectif optimale de la solution SAA et la valeur optimale réelle converge vers zéro à un taux de $O(1/\sqrt{M})$ (jusqu'à des facteurs logarithmiques), en supposant que la qualification des contraintes de Mangasarian-Fromovitz (MFCQ) est vérifiée. Les auteurs démontrent que la MFCQ est vérifiée presque partout (sauf sur un ensemble de mesure de Lebesgue nulle).
• Convergence des solutions : La solution optimale du problème SAA converge vers l'ensemble des solutions optimales du problème original avec une probabilité de 1 lorsque $M \to \infty$.

Résultats et évaluation empirique
Les auteurs valident leur approche par des simulations et une application réelle :

• Résultats de simulation : En comparant l'approche S-MILP aux méthodes Lan-DeMets, Pocock et O'Brien-Fleming, l'approche S-MILP atteint systématiquement une taille d'échantillon attendue (ESS) plus faible. Par exemple, avec $K=5$ et $K=7$, la méthode S-MILP a montré des améliorations d'environ 13 % et 12 % par rapport à Lan-DeMets, et jusqu'à 33 % par rapport à O'Brien-Fleming.
• Comportement de dépense d'alpha : L'optimisation révèle que la stratégie optimale consiste à dépenser « agressivement » le budget d'alpha aux premiers stades, de manière nettement plus marquée que même les méthodes traditionnelles les plus agressives (comme Pocock). Cela éclaire l'efficacité de l'arrêt précoce.
• Application clinique : La méthode a été appliquée à une réanalyse d'un essai contrôlé randomisé sur les interventions pour l'insuffisance rénale aiguë (AKI). En utilisant l'approche S-MILP, les auteurs ont démontré que la même conclusion statistiquement significative pouvait être atteinte avec moins d'échantillons (économisant environ 175 patients en moyenne dans les permutations, et 807 patients par rapport à l'étude originale complète) par rapport à la méthode O'Brien-Fleming utilisée dans l'analyse originale.

Importance et revendications
L'article revendique être l'un des premiers à fournir une approche générale et optimale pour les problèmes GST en optimisant directement les régions de rejet plutôt que de les spécifier via des fonctions de dépense d'alpha déterministes. Les contributions clés sont :

1. Optimalité : Démontrer que la sélection de seuils basée sur l'optimisation produit des tailles d'échantillon attendues strictement inférieures à celles des méthodes classiques.
2. Innovation méthodologique : Réussir à combler le fossé entre les tests séquentiels stochastiques et les solveurs MILP déterministes via la SAA, traitant des résultats continus là où les approches de programmation linéaire précédentes échouaient.
3. Perspective pratique : Remettre en question le débat de longue date sur la dépense d'alpha en montrant que la stratégie mathématiquement optimale consiste à dépenser le budget d'erreur très tôt, contrairement à la nature conservatrice de nombreuses méthodes standard.

Les auteurs reconnaissent des limitations pratiques, notant que le coût computationnel de la résolution du MILP pour de grands $M$ (par exemple, $M=2000$) peut être significatif, bien que soluble dans des délais raisonnables (par exemple, ~30 minutes pour $K=5$). Ils notent également que les garanties d'optimalité dépendent de la spécification correcte de la taille d'effet de l'hypothèse alternative, bien que les résultats empiriques suggèrent une robustesse même en cas de mauvaise spécification.