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...
Subjects
free text keywords: Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics, Mathematics - Probability, Mathematics - Statistics Theory
Funded by
NSF| AF: Small: Learning and Testing Classes of Distributions
Project
  • 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
  • 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
  • Funder: National Science Foundation (NSF)
  • Project Code: 1115703
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
Download from
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
Any information missing or wrong?Report an Issue