Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (August 2020) (Learn how and when to remove this message) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (June 2015) (Learn how and when to remove this message) (Learn how and when to remove this message)

In decision theory, competitive regret is the relative regret compared to an oracle with limited or unlimited power in the process of distribution estimation.

Competitive regret to the oracle with full power

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 ${\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}$.

Competitive regret to the oracle with limited power

Oracle with partial information

The oracle is restricted to have access to partial information of the true distribution ${\displaystyle p}$ by knowing the location of ${\displaystyle p}$ in the parameter space up to a partition. Given a partition ${\displaystyle \mathbb {P} }$ of the parameter space, and suppose the oracle knows the subset ${\displaystyle P}$ where the true ${\displaystyle p\in P}$. The oracle will have regret as

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

The competitive regret to the oracle will be

${\displaystyle r_{n}^{\mathbb {P} }(q,{\mathcal {P}})=\max _{P\in \mathbb {P} }(r_{n}(q,P)-r_{n}(P)).}$

Oracle with partial information

The oracle knows exactly ${\displaystyle p}$, but can only choose the estimator among natural estimators. A natural estimator assigns equal probability to the symbols which appear the same number of time in the sample. The regret of the oracle is

${\displaystyle r_{n}^{nat}(p)=\min _{q\in {\mathcal {Q}}_{nat}}r_{n}(q,p),}$

and the competitive regret is

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

Example

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

${\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}$.

References

1. ^ Orlitsky, Alon; Suresh, Ananda Theertha. (2015), Competitive Distribution Estimation, arXiv:1503.07940, Bibcode:2015arXiv150307940O
2. Acharya, Jayadev; Jafarpour, Ashkan; Orlitsky, Alon; Suresh, Ananda Theertha (2013), "Optimal probability estimation with applications to prediction and classification", Proceedings of the 26th Annual Conference on Learning Theory (COLT)

• Game theory