Estimating the Fundamental Limits is Easier Than Achieving the Fundamental Limits

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

doi:10.1109/TIT.2019.2927697

Estimating the Fundamental Limits is Easier Than Achieving the Fundamental Limits

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

Mathematics

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Article number	8758354
Pages (from-to)	6704-6715
Number of pages	12
Journal	IEEE Transactions on Information Theory
Volume	65
Issue number	10
DOIs	https://doi.org/10.1109/TIT.2019.2927697
State	Published - Oct 2019

Keywords

Bayes envelope estimation
entropy estimation
generalized entropy
prediction under logarithmic loss
total variation distance estimation

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2019.2927697

Cite this

@article{1ccd71d732674402a3dd9f85d7269d7a,

title = "Estimating the Fundamental Limits is Easier Than Achieving the Fundamental Limits",

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.",

keywords = "Bayes envelope estimation, entropy estimation, generalized entropy, prediction under logarithmic loss, total variation distance estimation",

author = "Jiantao Jiao and Yanjun Han and Irena Fischer-Hwang and Tsachy Weissman",

note = "Publisher Copyright: {\textcopyright} 1963-2012 IEEE.",

year = "2019",

month = oct,

doi = "10.1109/TIT.2019.2927697",

language = "English (US)",

volume = "65",

pages = "6704--6715",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "10",

}

TY - JOUR

T1 - Estimating the Fundamental Limits is Easier Than Achieving the Fundamental Limits

AU - Jiao, Jiantao

AU - Han, Yanjun

AU - Fischer-Hwang, Irena

AU - Weissman, Tsachy

PY - 2019/10

Y1 - 2019/10

N2 - 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.

AB - 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.

KW - Bayes envelope estimation

KW - entropy estimation

KW - generalized entropy

KW - prediction under logarithmic loss

KW - total variation distance estimation

UR - http://www.scopus.com/inward/record.url?scp=85077362532&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85077362532&partnerID=8YFLogxK

U2 - 10.1109/TIT.2019.2927697

DO - 10.1109/TIT.2019.2927697

M3 - Article

AN - SCOPUS:85077362532

SN - 0018-9448

VL - 65

SP - 6704

EP - 6715

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 10

M1 - 8758354

ER -

Estimating the Fundamental Limits is Easier Than Achieving the Fundamental Limits

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this