Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationData CompressionGeneral ClassificationSimilar Papers 제목 키워드 기반
Limits of Approximating the Median Treatment Effect
Average Treatment Effect (ATE) estimation is a well-studied problem in causal inference. However, it does not necessarily capture the heterogeneity in the data, and several approaches have been proposed to tackle the iss…
Causal InferenceTowards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
In this paper, we consider a new Multi-Armed Bandit (MAB) problem where arms are nodes in an unknown and possibly changing graph, and the agent (i) initiates random walks over the graph by pulling arms, (ii) observes the…
Multi-Armed BanditsRecommendation SystemsLimits of Estimating Heterogeneous Treatment Effects: Guidelines for Practical Algorithm Design
Estimating heterogeneous treatment effects from observational data is a central problem in many domains. Because counterfactual data is inaccessible, the problem differs fundamentally from supervised learning, and e…
counterfactualGaussian ProcessesSelection biasEstimating Certain Integral Probability Metric (IPM) is as Hard as Estimating under the IPM
We study the minimax optimal rates for estimating a range of Integral Probability Metrics (IPMs) between two unknown probability measures, based on $n$ independent samples from them. Curiously, we show that estimating th…
Improving Pairwise Ranking for Multi-label Image Classification
Learning to rank has recently emerged as an attractive technique to train deep convolutional neural networks for various computer vision tasks. Pairwise ranking, in particular, has been successful in multi-label image cl…
ClassificationGeneral Classificationimage-classificationImage Classification+2