Timezone: »

 
Oral
Doubly-Competitive Distribution Estimation
Yi Hao · Alon Orlitsky

Tue Jun 11 03:00 PM -- 03:05 PM (PDT) @ Room 102
in Information Theory and Estimation »

Distribution estimation is a statistical-learning cornerstone. Its classical min-max formulation minimizes the estimation error for the worst distribution, hence under-performs for practical distributions that, like power-law, are often rather simple. Modern research has therefore focused on two frameworks: structural estimation that improves learning accuracy by assuming a simple structure of the underlying distribution; and competitive, or instance-optimal, estimation that achieves the performance of a genie aided estimator up to a small excess error that vanishes as the sample size grows, regardless of the distribution. This paper combines and strengthens the two frameworks. It designs a single estimator whose excess error vanishes both at a universal rate as the sample size grows, as well as when the (unknown) distribution gets simpler. We show that the resulting algorithm significantly improves the performance guarantees for numerous competitive- and structural-estimation results. The algorithm runs in near-linear time and is robust to model misspecification and domain-symbol permutations.

[ Slides]  [ Video] 

Author Information

Yi Hao (University of California, San Diego)
Alon Orlitsky (UCSD)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors