Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
This work highlights a gap between theoretical limits and practical implementation, which is incremental but relevant for researchers in information theory and machine learning.
The paper demonstrates that estimating fundamental limits in data processing tasks like binary classification, compression, and prediction is easier than achieving them, showing that while estimation can be done with n samples, explicit algorithms may require at least n ln n samples.
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 $n\ln n$ samples to construct an explicit algorithm to achieve the limits.