Estimating the Fundamental Limits is Easier Than Achieving the Fundamental Limits

Jiantao Jiao, Yanjun Han, Irena Fischer-Hwang, Tsachy Weissman

In machine learning and information theory, researchers are often obsessed with "fundamental limits"—the absolute best performance any algorithm could possibly achieve on a given dataset, such as the Bayes error for classification or Shannon entropy for compression. Traditionally, these limits are estimated by building the most sophisticated model possible and measuring its performance. This paper asks a provocative question: Is this the most efficient way to find the limit?

The Logarithmic Gap

The authors prove a fundamental "logarithmic gap" between knowing what is possible and actually doing it. They demonstrate that estimating the theoretical performance limit of a task requires significantly fewer samples—specifically a factor of $\ln n$ fewer—than constructing an algorithm that actually achieves that limit.

This leads to the concept of Effective Sample Size Enlargement. An optimal estimator using $n$ samples achieves the same accuracy as an optimal "achiever" (an algorithm) using $n \ln n$ samples. In essence, the estimator acts as if it has access to a much larger dataset than the algorithm it is evaluating.

Comparative Framework

The study uses a minimax analysis to compare three mathematical approaches:

  1. $R_{EST}$ (Direct Estimation): Directly estimating the Bayes envelope or entropy from samples without building the underlying tool.
  2. $R_{ACH}$ (Achievement): Building a predictor/classifier and measuring its regret (how much worse it is than the theoretical best).
  3. $R_{PLU}$ (The "Plug-in" approach): Using the empirical distribution of the data to calculate the limit.
Figure 1: Risk comparison for estimation ($R_{EST}$), achievement ($R_{ACH}$), and plug-in ($R_{PLU}$) methods as sample size $n$ increases.

Why Achievement is Harder

The performance gap is driven by the Bias Constraint. When building a classifier, performance is strictly bounded "from the top"—it can never exceed the Bayes error. Similarly, the "plug-in" empirical entropy is always biased "from the bottom." Direct estimators ($R_{EST}$), however, are not bound by these specific directional biases, allowing them to converge much faster, as seen in the simulation results.

Figure 2: Simulation results showing the consistent statistical advantage of direct estimation over achievement and plug-in methods.

Key Results and Implications

  • Universal Relationship: The paper establishes the informal relationship: $R_{EST}(n) \approx R_{ACH}(n \ln n) \approx R_{PLU}(n \ln n)$.
  • Classification Complexity: For a feature space of size $S$, achieving vanishing error requires $n \gg S$ samples, whereas estimating the limit only requires $n \gg S / \ln S$ samples.
  • ML Sub-optimality: Surprisingly, standard Maximum Likelihood (ML) classifiers do not achieve the minimax optimal rate for reaching the fundamental limit. The authors propose modified classifiers that handle rare symbols differently to reach optimal rates.

Conclusion

This research has significant implications for how we benchmark AI systems. It suggests that we can determine the "unachievable" limits in complex fields—like biology or physics—even if we cannot yet build the "perfect" model. While currently focused on discrete spaces (finite alphabets), extending this "enlargement" phenomenon to continuous, high-dimensional spaces remains a vital area for future work.

Summary updated

Abstract

We show through case studies that it is easier to estimate the fundamental limits of data processing than to construct the explicit algorithms to achieve those limits. Focusing on binary classification, data compression, and prediction under logarithmic loss, we show that in the finite space setting, when it is possible to construct an estimator of the limits with vanishing error with n samples, it may require at least n ln n samples to construct an explicit algorithm to achieve the limits.
BibTeX
@misc{jiao2017estimating,
  author = {Jiantao Jiao and Yanjun Han and Irena Fischer-Hwang and Tsachy Weissman},
  title = {{Estimating the Fundamental Limits is Easier Than Achieving the Fundamental Limits}},
  year = {2017},
  eprint = {1707.01203},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.01203},
}
Figure