Competitive Closeness Testing

Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:47-68, 2011.

Abstract

We test whether two sequences are generated by the same distribution or by two different ones. Unlike previous work, we make no assumptions on the distributions’ support size. Additionally, we compare our performance to that of the best possible test. We describe an efficiently-computable algorithm based on pattern maximum likelihood that is near optimal whenever the best possible error probability is $\le\exp(-14n^{2/3})$ using length-$n$ sequences.

Cite this Paper

BibTeX
@InProceedings{pmlr-v19-acharya11a, title = {Competitive Closeness Testing}, author = {Acharya, Jayadev and Das, Hirakendu and Jafarpour, Ashkan and Orlitsky, Alon and Pan, Shengjun}, booktitle = {Proceedings of the 24th Annual Conference on Learning Theory}, pages = {47--68}, year = {2011}, editor = {Kakade, Sham M. and von Luxburg, Ulrike}, volume = {19}, series = {Proceedings of Machine Learning Research}, address = {Budapest, Hungary}, month = {09--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v19/acharya11a/acharya11a.pdf}, url = {https://proceedings.mlr.press/v19/acharya11a.html}, abstract = {We test whether two sequences are generated by the same distribution or by two different ones. Unlike previous work, we make no assumptions on the distributions’ support size. Additionally, we compare our performance to that of the best possible test. We describe an efficiently-computable algorithm based on pattern maximum likelihood that is near optimal whenever the best possible error probability is $\le\exp(-14n^{2/3})$ using length-$n$ sequences.} }
Endnote
%0 Conference Paper %T Competitive Closeness Testing %A Jayadev Acharya %A Hirakendu Das %A Ashkan Jafarpour %A Alon Orlitsky %A Shengjun Pan %B Proceedings of the 24th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2011 %E Sham M. Kakade %E Ulrike von Luxburg %F pmlr-v19-acharya11a %I PMLR %P 47--68 %U https://proceedings.mlr.press/v19/acharya11a.html %V 19 %X We test whether two sequences are generated by the same distribution or by two different ones. Unlike previous work, we make no assumptions on the distributions’ support size. Additionally, we compare our performance to that of the best possible test. We describe an efficiently-computable algorithm based on pattern maximum likelihood that is near optimal whenever the best possible error probability is $\le\exp(-14n^{2/3})$ using length-$n$ sequences.
RIS
TY - CPAPER TI - Competitive Closeness Testing AU - Jayadev Acharya AU - Hirakendu Das AU - Ashkan Jafarpour AU - Alon Orlitsky AU - Shengjun Pan BT - Proceedings of the 24th Annual Conference on Learning Theory DA - 2011/12/21 ED - Sham M. Kakade ED - Ulrike von Luxburg ID - pmlr-v19-acharya11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 19 SP - 47 EP - 68 L1 - http://proceedings.mlr.press/v19/acharya11a/acharya11a.pdf UR - https://proceedings.mlr.press/v19/acharya11a.html AB - We test whether two sequences are generated by the same distribution or by two different ones. Unlike previous work, we make no assumptions on the distributions’ support size. Additionally, we compare our performance to that of the best possible test. We describe an efficiently-computable algorithm based on pattern maximum likelihood that is near optimal whenever the best possible error probability is $\le\exp(-14n^{2/3})$ using length-$n$ sequences. ER -
APA
Acharya, J., Das, H., Jafarpour, A., Orlitsky, A. & Pan, S.. (2011). Competitive Closeness Testing. Proceedings of the 24th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 19:47-68 Available from https://proceedings.mlr.press/v19/acharya11a.html.

Related Material