← Back to papers
2011 COLT COLT 2011

Competitive Closeness Testing

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.

🚀 Conference Pioneer — COLT 2011
🧭 Keyword Pioneer — error probability
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Machine Learning, Mathematics & Optimization, Natural Language Processing
🌉 Interdisciplinary Bridge — Machine Learning and Mathematics & Optimization
📈 Trend Setter — Statistics
🐣 Hot Topic Early Bird — information theory

Authors

Jayadev Acharya , Hirakendu Das , Ashkan Jafarpour , Alon Orlitsky , Shengjun Pan

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Optimization Mathematics & Optimization > Statistics Machine Learning > Optimization & Theory > Statistics Machine Learning > Learning Types > Evaluation

Keywords

information theory hypothesis testing distribution testing error probability pattern maximum likelihood optimal testing
Download PDF

Related papers

Bandits, Query Learning, and the Haystack Dimension 2011
Minimax Policies for Combinatorial Prediction Games 2011
Sample Complexity Bounds for Differentially Private Learning 2011
Multiclass Learnability and the ERM principle 2011
Distribution-Independent Evolvability of Linear Threshold Functions 2011