Competitive regret

Consider estimating a discrete probability distribution ${\displaystyle p}$ on a discrete set ${\displaystyle {\mathcal {X}}}$ based on data ${\displaystyle X}$, the regret of an estimator[1] ${\displaystyle q}$ is defined as

${\displaystyle \max _{p\in {\mathcal {P}}}r_{n}(q,p).}$

where ${\displaystyle {\mathcal {P}}}$ is the set of all possible probability distribution, and

${\displaystyle r_{n}(q,p)=\mathbb {E} (D(p||q(X))).}$

where ${\displaystyle D(p||q)}$ is the Kullback–Leibler divergence between ${\displaystyle p}$ and ${\displaystyle q}$.

For the estimator ${\displaystyle q}$ proposed in Acharya et al.(2013),[2]

${\displaystyle r_{n}^{\mathbb {P} _{\sigma }}(q,\Delta _{k})\leq r_{n}^{nat}(q,\Delta _{k})\leq {\tilde {\mathcal {O}}}(\min({\frac {1}{\sqrt {n}}},{\frac {k}{n}})).}$

Here ${\displaystyle \Delta _{k}}$ denotes the k-dimensional unit simplex surface. The partition ${\displaystyle \mathbb {P} _{\sigma }}$ denotes the permutation class on ${\displaystyle \Delta _{k}}$, where ${\displaystyle p}$ and ${\displaystyle p'}$ are partitioned into the same subset if and only if ${\displaystyle p'}$ is a permutation of ${\displaystyle p}$.