Minimax-Optimal Bounds for Detectors Based on Estimated Prior Probabilities

Jiantao Jiao, Lin Zhang, Robert D. NowakIEEE Trans. Information Theory 2011 · DOI · OpenReview

TL;DR

This paper establishes theoretical limits on how accurately we can detect signals when we know the underlying models but have to estimate how often each signal occurs (the "prior probabilities"). The authors prove that using a Maximum Likelihood Estimate (MLE) for these priors allows the detector to approach optimal performance at rates that depend on the "flatness" of the risk function, often achieving much faster convergence than standard machine learning models.

What Problem Does This Paper Address?

In classical signal detection (like radar or medical diagnosis), we often have excellent models for what a "target" looks like versus "noise" (the conditional densities). However, we frequently don't know the prior probability—exactly how likely it is that a target is present in the first place.

Standard practice is to estimate these priors from training data. This paper asks a fundamental question: How much does our detection accuracy suffer because we are using an estimate instead of the true prior?

The authors quantify this "excess risk" (the gap between our detector and the perfect Bayes detector) and determine how quickly this gap vanishes as we collect more training data ($n$). They look at two scenarios:

  1. Labeled data: We know which training samples are targets and which are noise.
  2. Unlabeled data: We only see a mixture of samples and have to figure out the proportions.

Methods

The researchers employ a "plug-in" approach. They use the Maximum Likelihood Estimate (MLE) to guess the prior probability from the training data and then "plug" that guess into the standard Bayes decision rule.

To analyze the performance, they use Tsybakov’s Margin Assumption. This is a mathematical way of describing how "ambiguous" the boundary is between two classes. If the classes are well-separated (a "flat" risk function), small errors in estimating the prior won't change the decision for most points. If they overlap significantly, even a tiny error in the prior estimate could lead to many wrong classifications.

Visualizing the impact of the Margin Assumption on the risk function $R(\hat{q})$ and posterior probability $\eta(x)$ across difficult, moderate, and best cases.

The paper provides:

  • Minimax Lower Bounds: The absolute best performance any possible estimator could achieve.
  • Upper Bounds: The actual performance achieved by the MLE.

Key Insights and Ideas

  • The "Flatness" Advantage: The speed at which a detector improves depends on the local behavior of the risk function. As shown in Figure 1, if the risk function is "flat" near the true prior, the detector is robust to estimation errors, leading to "super-fast" convergence rates.
  • Dimension-Free Bounds: Surprisingly, the bounds on the excess risk do not depend on the dimensionality of the data ($d$). Whether your signal is a single number or a million-pixel image, the convergence rate depends only on the number of training samples and the overlap between the two models.
  • The Cost of Not Knowing Labels: The authors show that you can achieve the same rate of convergence using unlabeled data as you can with labeled data. However, you pay a "constant factor" penalty determined by the Total Variation distance—essentially, how easy it is to tell the two underlying distributions apart.

Key Results

  • General Convergence: Without any special assumptions, the excess risk is guaranteed to be no worse than $O(n^{-1/2})$.
  • Fast Rates: Under the Margin Assumption (parameterized by $\alpha$), the rate improves significantly. For a "typical" smooth problem ($\alpha=1$), the error vanishes at $O(n^{-1})$. In the "best case" ($\alpha = \infty$), where there is a clear gap between classes, the error vanishes exponentially fast.
  • Optimality: The authors prove that these rates are "minimax-optimal" for labeled data, meaning no other algorithm can ever do better than the MLE-based approach in these settings.
Comparison of convergence rates for passive learning under different knowledge scenarios, highlighting the impact of knowing the conditional densities $p_1, p_0$.

Limitations and Future Work

  • Perfect Model Assumption: The biggest limitation is the assumption that the conditional densities ($p_0$ and $p_1$) are known perfectly. In many real-world tasks, these models are also estimated from data, which would likely slow down the convergence rates.
  • Trimmed MLE: To prove some of the bounds, the authors use a "trimmed" MLE that assumes the prior $q$ isn't extremely close to 0 or 1. While mathematically useful, this might require tuning in practical applications.
  • Unlabeled Optimality: While the authors show the MLE achieves certain rates with unlabeled data, they leave it as an open question to prove that these rates are the absolute best possible (minimax-optimal) for the unlabeled case.

Summary updated

Abstract

In many signal detection and classification problems, we have knowledge of the distribution under each hypothesis, but not the prior probabilities. This paper is aimed at providing theory to quantify the performance of detection via estimating prior probabilities from either labeled or unlabeled training data. The error or risk is considered as a function of the prior probabilities. We show that the risk function is locally Lipschitz in the vicinity of the true prior probabilities, and the error of detectors based on estimated prior probabilities depends on the behavior of the risk function in this locality. In general, we show that the error of detectors based on the maximum likelihood estimate (MLE) of the prior probabilities converges to the Bayes error at a rate of <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$n^{-1/2}$</tex></formula> , where <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$n$</tex></formula> is the number of training data. If the behavior of the risk function is more favorable, then detectors based on the MLE have errors converging to the corresponding Bayes errors at optimal rates of the form <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$n^{-(1+\alpha)/2}$</tex> </formula> , where <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\alpha &gt; 0$</tex></formula> is a parameter governing the behavior of the risk function with a typical value <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\alpha = 1$</tex></formula> . The limit <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\alpha \rightarrow{} \infty$</tex></formula> corresponds to a situation where the risk function is flat near the true probabilities, and thus insensitive to small errors in the MLE; in this case, the error of the detector based on the MLE converges to the Bayes error exponentially fast with <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$n$</tex></formula> . We show that the bounds are achievable no matter given labeled or unlabeled training data and are minimax-optimal in the labeled case.
BibTeX
@article{jiao2011minimax,
  author = {Jiantao Jiao and Lin Zhang and Robert D. Nowak},
  title = {{Minimax-Optimal Bounds for Detectors Based on Estimated Prior Probabilities}},
  journal = {IEEE Trans. Information Theory},
  year = {2011},
  doi = {10.1109/tit.2012.2201914},
}
Figure