Competitive regret
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)
|
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]- ^ a b c Orlitsky, Alon; Suresh, Ananda Theertha. (2015), Competitive Distribution Estimation, arXiv:1503.07940, Bibcode:2015arXiv150307940O
- ^ 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)