Approximate Least-Favorable Distributions and Nearly Optimal Tests via Stochastic Mirror Descent

Andres Fernandez, José Blanchet, José Luis Montiel Olea, Chen Qiu, Jörg Stoye, Lezhi TanarXiv 2025 · DOI · arXiv

TL;DR

This paper provides the first rigorous theoretical guarantees for finding nearly optimal statistical tests in complex scenarios with many possible null distributions. By framing the search for a "least-favorable distribution" as a convex optimization problem, the authors show that a technique called Stochastic Mirror Descent can efficiently produce high-quality tests with a computational cost that scales remarkably well—logarithmically—with the number of distributions involved.

What Problem Does This Paper Address?

In statistics and econometrics, we often want to find the "Most Powerful Test"—the one most likely to correctly reject a false null hypothesis while keeping the risk of a "false alarm" (Type I error) below a fixed level $\alpha$. This is easy when the null hypothesis is simple (one distribution), but it becomes a nightmare when the null is composite (e.g., $M$ different possible distributions due to unknown "nuisance" parameters).

To solve this, researchers look for a Least-Favorable Distribution (LFD): a specific mixture of those $M$ distributions that is hardest to distinguish from the alternative. While previous work (notably Elliott, Müller, and Watson, 2015) suggested heuristic algorithms to find these, they lacked "provable" guarantees. We didn't know for sure if those algorithms would converge, how many iterations they needed, or how many simulations were required at each step.

Methods

The authors bridge the gap between statistical testing and modern optimization theory. They demonstrate that finding the LFD is equivalent to solving a dual convex optimization problem. To solve it, they employ Stochastic Mirror Descent (S-MD) with a negative entropy mirror map.

Key technical choices include:

  • Negative Entropy Map: This specific "mirror" is mathematically ideal for optimization over a probability simplex (the set of possible mixtures of the $M$ distributions).
  • Single-Draw Estimation: Crucially, they prove the algorithm works even if you only take a single Monte Carlo draw ($N=1$) from each null distribution per iteration to estimate the gradient.
  • Polyak-Ruppert Averaging: Instead of just taking the result of the very last iteration, the "nearly optimal" test is constructed by averaging the results across all iterations.
  • Randomized Implementation: To save memory, they show you can implement this "average test" by picking a random iteration to stop at, rather than storing the history of all iterations.

Datasets

The paper does not use real-world empirical datasets. Instead, it validates the theory using a controlled illustrative example:

  • Univariate Gaussian Location Model: A standard benchmark where the data follows a normal distribution $Y \sim \mathcal{N}(\theta, 1)$.
  • Setup: The null hypothesis consists of $M=200$ different values of $\theta$ spread across an interval, while the alternative is a single point ($\theta=2$). Because the "true" optimal test is known for this specific case, it serves as a perfect yardstick to measure how close the S-MD algorithm gets to perfection.

Key Insights and Ideas

  • Logarithmic Scaling is a Game Changer: The number of iterations required scales with $\ln(M)$. This means if you increase the complexity of your model from 100 possible null distributions to 10,000, the computational effort doesn't increase 100x; it only increases by a small fraction.
  • The Power of "Good Enough": By shifting the goal from finding the exact LFD to an approximate ($\epsilon$-least favorable) one, the authors unlock the use of efficient first-order optimization methods that are standard in machine learning but less common in classical testing theory.
  • Simulation Efficiency: You don't need high-precision simulations at every step. The "noise" from using just one draw per distribution is actually handled gracefully by the Mirror Descent framework, allowing the algorithm to move toward the truth very quickly.
  • Averaging vs. Last-Iterate: The paper highlights a conceptual flaw in previous heuristics: looking at the last update is theoretically unstable. Averaging the trajectory is what provides the "provable" guarantee.

Key Results

  • Theoretical Convergence: The authors provide explicit formulas for the step size and number of iterations ($T$) needed to guarantee an $\epsilon-approximation$ with high probability.
  • Computational Speed: In their Gaussian simulation ($M=200, \alpha=10\%$), the algorithm completed over 171,000 iterations in just 280 seconds (under 5 minutes) on a standard laptop.
  • High Accuracy: While the theoretical bound was set for a 10% error ($\epsilon=0.1$), the actual run achieved an error of only 1.6%, showing the algorithm often performs even better in practice than the "worst-case" theory suggests.
  • Efficiency Gain: Comparing runtimes, using 1 draw per round took ~314 seconds, whereas using 1,000 draws (a more traditional approach) took over 36,000 seconds—a 100x slowdown for marginal gains in accuracy.

Limitations and Future Work

  • Simple Alternatives: The current proofs focus on a "simple" alternative hypothesis (one distribution). While the authors discuss extending this to "weighted average power" for composite alternatives, a full theoretical treatment for more complex alternative spaces remains open.
  • Size Control Jitter: The upper bound on the Type I error contains a term that depends on the specific random "run" of the algorithm. While it stays small in simulations, the authors note they couldn't yet derive a tighter, purely deterministic bound.
  • Unbiased Testing: The paper briefly explores "approximately unbiased tests" (tests that are never less powerful than the significance level), but notes that this requires more complex constraints on the multipliers that are harder to satisfy ex-ante.

Summary updated

Abstract

We consider a class of hypothesis testing problems where the null hypothesis postulates $M$ distributions for the observed data, and there is only one possible distribution under the alternative. We show that one can use a stochastic mirror descent routine for convex optimization to provably obtain - after finitely many iterations - both an approximate least-favorable distribution and a nearly optimal test, in a sense we make precise. Our theoretical results yield concrete recommendations about the algorithm's implementation, including its initial condition, its step size, and the number of iterations. Importantly, our suggested algorithm can be viewed as a slight variation of the algorithm suggested by Elliott, Müller, and Watson (2015), whose theoretical performance guarantees are unknown.
BibTeX
@misc{fernandez2025approximate,
  author = {Andres Fernandez and José Blanchet and José Luis Montiel Olea and Chen Qiu and Jörg Stoye and Lezhi Tan},
  title = {{Approximate Least-Favorable Distributions and Nearly Optimal Tests via Stochastic Mirror Descent}},
  year = {2025},
  eprint = {2511.16925},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.16925},
  howpublished = {arXiv},
}
Figure