Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Competitive Distribution Estimation   Estimating an unknown distribution from its samples is a fundamental problem
in statistics. The common, min-max, formulation of this goal considers the
performance of the best estimator over all distributions in a class. It shows
that with $n$ samples, distributions over $k$ symbols can be learned to a KL
divergence that decreases to zero with the sample size $n$, but grows
unboundedly with the alphabet size $k$.
  Min-max performance can be viewed as regret relative to an oracle that knows
the underlying distribution. We consider two natural and modest limits on the
oracle's power. One where it knows the underlying distribution only up to
symbol permutations, and the other where it knows the exact distribution but is
restricted to use natural estimators that assign the same probability to
symbols that appeared equally many times in the sample.
  We show that in both cases the competitive regret reduces to
$\min(k/n,\tilde{\mathcal{O}}(1/\sqrt n))$, a quantity upper bounded uniformly
for every alphabet size. This shows that distributions can be estimated nearly
as well as when they are essentially known in advance, and nearly as well as
when they are completely known in advance but need to be estimated via a
natural estimator. We also provide an estimator that runs in linear time and
incurs competitive regret of $\tilde{\mathcal{O}}(\min(k/n,1/\sqrt n))$, and
show that for natural estimators this competitive regret is inevitable. We also
demonstrate the effectiveness of competitive estimators using simulations.

36
The categories of this paper are: cmp-lg
27
The categories of this paper are: comp-gas
9
The categories of this paper are: nlin
12
The categories of this paper are: nucl-th
34
The categories of this paper are: chem-ph
31
The categories of this paper are: ao-sci
0
The categories of this paper are: hep-ph
14
The categories of this paper are: math-ph
11
The categories of this paper are: hep-lat
37
The categories of this paper are: supr-con
32
The categories of this paper are: atom-ph
13
The categories of this paper are: quant-ph
29
The categories of this paper are: funct-an
10
The categories of this paper are: q-bio
23
The categories of this paper are: solv-int
30
The categories of this paper are: q-alg