publication . Preprint . 2017

Fourier-Based Testing for Families of Distributions

Canonne, Clément L.; Diakonikolas, Ilias; Stewart, Alistair;
Open Access English
  • Published: 18 Jun 2017
Abstract
We study the general problem of testing whether an unknown distribution belongs to a specified family of distributions. More specifically, given a distribution family $\mathcal{P}$ and sample access to an unknown discrete distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and the case that $\mathbf{P}$ is $\epsilon$-far, in total variation distance, from every distribution in $\mathcal{P}$. This is the prototypical hypothesis testing problem that has received significant attention in statistics and, more recently, in theoretical computer science. The sample complexity of this general infer...
Read more
Subjects
free text keywords: Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics, Mathematics - Probability, Mathematics - Statistics Theory
Related Organizations
View more
Funded by
NSF| AF: Small: Learning and Testing Classes of Distributions
Project
AF: Small: Learning and Testing Classes of Distributions
  • Funder: National Science Foundation (NSF)
  • Project Code: 1319788
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
, RCUK| Sublinear Algorithms for Approximating Probability Distributions
Project
Sublinear Algorithms for Approximating Probability Distributions
  • Funder: Research Council UK (RCUK)
  • Project Code: EP/L021749/1
  • Funding stream: EPSRC
, NSF| AF: Small: The Boundary of Learnability for Monotone Boolean Functions
Project
AF: Small: The Boundary of Learnability for Monotone Boolean Functions
  • Funder: National Science Foundation (NSF)
  • Project Code: 1115703
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
Download from
arXiv.org e-Print Archive
Preprint . 2017
Provider: arXiv.org e-Print Archive
20 references, page 1 of 2

[CDGR16] C. L. Canonne, I. Diakonikolas, T. Gouleakis, and R. Rubinfeld. Testing Shape Restrictions of Discrete Distributions. In 33rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2016. [OpenAIRE]

Yu Cheng, Ilias Diakonikolas, and Alistair Stewart. Playing anonymous games using simple strategies. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of SODA '17, pages 616-631, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics.

[CDVV14] S. Chan, I. Diakonikolas, P. Valiant, and G. Valiant. Optimal algorithms for testing closeness of discrete distributions. In SODA, pages 1193-1203, 2014. [OpenAIRE]

[DDKT16] C. Daskalakis, A. De, G. Kamath, and C. Tzamos. A size-free CLT for poisson multinomials and its applications. In Proceedings of STOC'16, 2016.

[DDO+13] C. Daskalakis, I. Diakonikolas, R. O'Donnell, R.A. Servedio, and L. Tan. Learning Sums of Independent Integer Random Variables. In FOCS, pages 217-226, 2013. [OpenAIRE]

C. Daskalakis, I. Diakonikolas, and R.A. Servedio. Learning Poisson Binomial Distributions. In STOC, pages 709-728, 2012.

C. Daskalakis, I. Diakonikolas, and R. A. Servedio. Learning Poisson Binomial Distributions. Algorithmica, 72(1):316-357, 2015.

[GMRZ11] P. Gopalan, R. Meka, O. Reingold, and D. Zuckerman. Pseudorandom generators for combinatorial shapes. In STOC, pages 253-262, 2011.

P. W. Goldberg and S. Turchetta. Query complexity of approximate equilibria in anonymous games. CoRR, abs/1412.6455, 2014.

W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.

J. Kruopis. Precision of approximation of the generalized binomial distribution by convolutions of poisson measures. Lithuanian Mathematical Journal, 26(1):37-49, 1986.

A. K. H. Kim and R. J. Samworth. Global rates of convergence in logconcave density estimation. Ann. Statist., 44(6):2756-2779, 12 2016. Available at http://arxiv.org/abs/1404.2298.

W. Loh. Stein's method and multinomial approximation. Ann. Appl. Probab., 2(3):536- 554, 08 1992. [OpenAIRE]

E. L. Lehmann and J. P. Romano. Testing statistical hypotheses. Springer Texts in Statistics. Springer, 2005.

J. Neyman and E. S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(694-706):289-337, 1933. [OpenAIRE]

20 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue