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

edit

Consider estimating a discrete probability distribution   on a discrete set   based on data  , the regret of an estimator[1]   is defined as

 

where   is the set of all possible probability distribution, and

 

where   is the Kullback–Leibler divergence between   and  .

Competitive regret to the oracle with limited power

edit

Oracle with partial information

edit

The oracle is restricted to have access to partial information of the true distribution   by knowing the location of   in the parameter space up to a partition.[1] Given a partition   of the parameter space, and suppose the oracle knows the subset   where the true  . The oracle will have regret as

 

The competitive regret to the oracle will be

 

Oracle with partial information

edit

The oracle knows exactly  , 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.[1] The regret of the oracle is

 

and the competitive regret is

 

Example

edit

For the estimator   proposed in Acharya et al.(2013),[2]

 

Here   denotes the k-dimensional unit simplex surface. The partition   denotes the permutation class on  , where   and   are partitioned into the same subset if and only if   is a permutation of  .

References

edit
  1. ^ a b c 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)