📊 statistics

Optimal MILP Approach to Group Sequential Hypothesis Test

This paper proposes a sample average approximation combined with mixed integer linear programming (S-MILP) approach to optimize group sequential hypothesis tests, demonstrating that it outperforms classical methods like Lan-DeMets, Pocock, and O'Brien-Fleming by enabling earlier rejection of the null hypothesis while maintaining strict error control.

Original authors: Dae Woong Ham, Stefanus Jasin, Xuejun Zhao

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dae Woong Ham, Stefanus Jasin, Xuejun Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a case. You have a limited budget of "clues" (data) you can collect, but you want to catch the criminal (reject the null hypothesis) as quickly as possible to save time and resources. However, you can't just guess; you need to be sure you aren't making a mistake (a "false alarm" or Type 1 error).

In the world of science and medicine, this is called Group Sequential Hypothesis Testing (GST). Instead of waiting until you have all your clues to make a decision, you check your progress at specific checkpoints (groups). The big question has always been: How much "risk" (or error budget) should you spend at each checkpoint?

For decades, researchers have used fixed rules (like the "O'Brien-Fleming" or "Pocock" methods) to decide this. Think of these rules like a strict parent giving you a fixed allowance: "You can spend $1 on Monday, $1 on Tuesday, and $1 on Wednesday." It's safe, but it might not be the most efficient way to get what you need.

This paper introduces a new, smarter way to solve this problem using a method called S-MILP (Sample Average Approximation combined with Mixed Integer Linear Programming). Here is the breakdown in simple terms:

1. The Problem: The "Allowance" Dilemma

Imagine you have a total of $50 to spend on a trip. You want to buy the best ticket as soon as possible.

Old Methods: You follow a pre-written plan. Maybe you spend $10 on day 1, $10 on day 2, and $30 on day 3. This guarantees you don't run out of money (control the error rate), but it might force you to wait until day 3 even if the ticket was available on day 1.
The Goal: The researchers wanted to find the perfect spending plan that lets you buy the ticket the earliest possible day without ever running out of money.

2. The Solution: The "Smart Optimizer"

The authors didn't just guess a new plan; they built a mathematical machine (an optimization algorithm) to find the absolute best plan.

The Simulation: Since they can't predict the future, they ran thousands of "what-if" scenarios (simulations) on a computer. They imagined thousands of different versions of the experiment happening at once.
The Math Magic (MILP): They turned this complex guessing game into a giant puzzle that a computer solver can crack. They used "binary variables" (think of them as light switches that are either ON or OFF) to represent whether a specific clue was strong enough to stop the experiment.
The Result: The computer found a strategy that is mathematically proven to be the fastest way to reach a conclusion while keeping the risk of a false alarm exactly where it needs to be.

3. The Big Discovery: "Spend Early, Win Early"

One of the most interesting findings is how the optimal strategy behaves compared to the old rules.

Old Rules: Tend to be very conservative early on. They save most of their "error budget" for the end, like a cautious driver who barely touches the gas pedal until the highway is clear.
The New Optimal Strategy: It is aggressive. It spends a huge chunk of the error budget right at the very first checkpoint.
The Metaphor: Imagine the old methods are like a person who checks their watch every hour to see if they are late. The new method is like someone who checks their watch immediately, realizes they have a chance to leave early, and goes for it. The paper shows that by being bold early, you can often stop the experiment much sooner than the traditional methods allow.

4. Real-World Proof: The Kidney Study

To prove this wasn't just a theory, the authors tested it on a real medical study about Acute Kidney Injury (AKI).

The Scenario: A real study looked at whether a computer alert system helped doctors stop giving harmful drugs to patients. The original study took data from over 3,200 patients to reach a conclusion.
The Test: The researchers asked, "If we had used our new 'Smart Optimizer' on this data, could we have stopped earlier?"
The Outcome: Yes.
- In one scenario, their method would have stopped the experiment after just 2 groups of patients, while the old method needed 3 groups.
- In another scenario (averaging over many random orders of patients), their method reached the conclusion with 175 fewer patients.
- Compared to the original study's full size, their method could have reached the same "statistically significant" conclusion with 807 fewer patients.

5. Why This Matters (According to the Paper)

Efficiency: You can get the same scientific answer with fewer people, less time, and less money.
Ethics: In medical trials, this means fewer patients are exposed to potentially ineffective or harmful treatments for longer than necessary.
Speed: In digital testing (like A/B testing for apps), companies can decide if a new feature works much faster.

The Catch (Limitations Mentioned)

The paper is honest about two practical hurdles:

Computing Power: Finding this "perfect" plan takes a lot of computer power. It's not a simple calculation you can do on a napkin; it requires a powerful computer running for a while (about 30 minutes in their tests) to solve the puzzle.
Knowing the Target: The method works best if you have a good guess about how big the effect actually is (the "alternative hypothesis"). If your guess is wildly wrong, the math guarantees might not hold perfectly, though the authors found it still performed better than the old methods even when guesses were off.

In Summary:
This paper replaces the "one-size-fits-all" rules for checking scientific data with a custom-tailored, mathematically optimized strategy. It proves that by spending your "error budget" more aggressively at the start, you can often finish your experiment much faster, saving resources and potentially helping patients sooner.

Technical Summary: Optimal MILP Approach to Group Sequential Hypothesis Test

Problem Statement
Group Sequential Hypothesis Testing (GST) is a standard framework for performing multiple tests on data arriving sequentially at $K$ fixed time points (groups) with a pre-specified total sample size $N$ . The primary goal in many applications, such as clinical trials and online digital experimentation, is to reach a valid decision (rejecting the null hypothesis $H_0$ ) as early as possible to minimize the expected sample size (ESS).

Existing GST methods, including Lan-DeMets, Pocock, and O'Brien-Fleming, rely on pre-specified "alpha-spending functions" to distribute the Type-1 error budget ( $\alpha$ ) across the $K$ stages. While these methods guarantee uniform Type-1 error control, the choice of spending function is often heuristic. The literature has not sufficiently explored the optimal alpha-spending function that minimizes the expected stopping time while satisfying constraints on both Type-1 error ( $\alpha$ ) and Type-2 error ( $\beta$ ). The authors note that while Silva et al. (2020) addressed this for binary outcomes, the general case involving continuous, unbounded outcomes remains an open optimization problem.

Methodology: S-MILP Approach
The paper proposes a novel optimization-based approach to directly determine the optimal rejection thresholds $\theta_1, \dots, \theta_K$ rather than relying on deterministic alpha-spending functions. The methodology proceeds in two main steps:

Formulation as a Stochastic Optimization Problem:
The authors formulate the problem of minimizing the expected sample size under the alternative hypothesis $H_a$ subject to constraints on Type-1 and Type-2 errors. The objective function and constraints involve probabilities of complex events (e.g., the test statistic crossing a threshold at stage $k$ without having crossed previous thresholds). This formulation is generally intractable due to the non-convex and discontinuous nature of the indicator functions involved in the probability calculations.
Sample Average Approximation (SAA) and Mixed Integer Linear Programming (MILP):
To render the problem tractable, the authors employ a Sample Average Approximation (SAA). They generate $M$ independent sample paths of the test statistics under both $H_0$ and $H_a$ . The probability terms in the original formulation are replaced by empirical averages (Monte Carlo estimates) over these $M$ paths.

The resulting SAA problem is then reformulated as a Mixed Integer Linear Program (MILP). This is achieved by introducing auxiliary binary variables to linearize the indicator functions (e.g., $\mathbb{I}(S_k \leq \theta_k)$ ). Specifically:
- Binary variables represent whether a sample path crosses a threshold.
- Logical constraints (using "big-M" formulations) link these binary variables to the continuous decision variables (the thresholds $\theta_k$ ).
- The objective becomes a linear function of these binary variables weighted by the sample sizes at each stage.
This S-MILP formulation allows the use of standard commercial solvers (e.g., Gurobi, CPLEX) to find the optimal thresholds.

Extensions and Generalizations
The paper extends the core S-MILP framework to several practical scenarios:

Unknown Variance ( $t$ -tests): Since the distribution of the $t$ -statistic under $H_a$ depends on the unknown variance $\sigma$ , the authors propose two fixes: (1) reformulating the hypothesis in terms of the standardized effect size $\delta$ , or (2) using a pilot study to estimate $\sigma$ and treating it as a plug-in parameter.
General Test Statistics: The convergence guarantees are generalized to arbitrary continuous test statistics, provided their distributions can be sampled and satisfy certain density boundedness conditions.
Symmetric Designs: The framework is extended to allow early stopping not only for rejection ( $H_a$ ) but also for acceptance ( $H_0$ ), optimizing the expected sample size under a hybrid strategy.

Theoretical Guarantees
The paper provides rigorous finite-sample convergence analysis for the S-MILP approach:

Feasibility: With high probability, the feasible region of the SAA problem approximates the true feasible region of the original optimization problem as $M$ increases.
Optimality Gap: The difference between the optimal objective value of the SAA solution and the true optimal value converges to zero at a rate of $O(1/\sqrt{M})$ (up to logarithmic factors), assuming the Mangasarian-Fromovitz Constraint Qualification (MFCQ) holds. The authors demonstrate that MFCQ holds almost everywhere (except on a set of zero Lebesgue measure).
Convergence of Solutions: The optimal solution of the SAA problem converges to the set of optimal solutions of the original problem with probability 1 as $M \to \infty$ .

Results and Empirical Evaluation
The authors validate their approach through simulations and a real-world application:

Simulation Results: Comparing the S-MILP approach against Lan-DeMets, Pocock, and O'Brien-Fleming methods, the S-MILP approach consistently achieves a lower Expected Sample Size (ESS). For instance, with $K=5$ and $K=7$ , the S-MILP method showed improvements of approximately 13% and 12% over Lan-DeMets, and up to 33% over O'Brien-Fleming.
Alpha-Spending Behavior: The optimization reveals that the optimal strategy involves "aggressively" spending the alpha-budget in the early stages, significantly more so than even the most aggressive traditional methods (like Pocock). This sheds insight into the efficiency of early stopping.
Clinical Application: The method was applied to a re-analysis of a randomized controlled trial on Acute Kidney Injury (AKI) interventions. Using the S-MILP approach, the authors demonstrated that the same statistically significant conclusion could be reached with fewer samples (saving approximately 175 patients on average in permutations, and 807 patients compared to the full original study) compared to the O'Brien-Fleming method used in the original analysis.

Significance and Claims
The paper claims to be one of the first to provide a general, optimal approach to GST problems by directly optimizing rejection regions rather than specifying them via deterministic alpha-spending functions. The key contributions are:

Optimality: Demonstrating that optimization-based threshold selection yields strictly lower expected sample sizes than classical methods.
Methodological Innovation: Successfully bridging the gap between stochastic sequential testing and deterministic MILP solvers via SAA, handling continuous outcomes where previous linear programming approaches failed.
Practical Insight: Challenging the long-standing debate on alpha-spending by showing that the mathematically optimal strategy is to spend the error budget very early, contrary to the conservative nature of many standard methods.

The authors acknowledge practical limitations, noting that the computational cost of solving the MILP for large $M$ (e.g., $M=2000$ ) can be significant, though solvable within reasonable timeframes (e.g., ~30 minutes for $K=5$ ). They also note that the optimality guarantees depend on the correct specification of the alternative hypothesis effect size, though empirical results suggest robustness even under misspecification.