# Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits

arXiv: https://arxiv.org/abs/1707.01203 · HTML: https://mlsanity.com/paper/1707.01203/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2017.

## Built on by (most cited first, 1 of 1)

- [The Ceiling Is in the Channel: Auditing Learner Gaps and Measurement Frontiers in Clinical Prediction](https://mlsanity.com/paper/2609.01909/) (2026)

## Abstract (arXiv)

We show through case studies that it is easier to estimate the fundamental limits of data processing than to construct 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 nln n samples to construct an explicit algorithm to achieve the limits.