Seven Algorithms for the Same Task (Testing Uniformity)

The Data Science Discipline of the School of ITEE is hosting the following seminar:

Seven Algorithms for the Same Task (Testing Uniformity)

Speaker: Dr Clément Canonne (University of Sydney)
Host: Dr Yadan Luo

More info: https://uq-ds-seminar.github.io/testing-uniformity/

Abstract: Suppose you get a set of (independent) data points in some discrete but huge domain {1,2,…,k}, and want to determine if this data is uniformly distributed. This is a basic and fundamental problem in Statistics, and has applications in computer science, not all made up: from testing the mixing time of a random walk, to detecting malicious changes in a data stream, to selecting a good algorithm depending on the input distribution.

The goal, of course, is to perform this task efficiently, both time- (time complexity) and data-wise (sample complexity). In this talk, I will survey and discuss seven algorithms for uniformity testing, and explain some of their (dis)advantages.

Speaker Bio: Clément Canonne is a Lecturer in the School of Computer Science of the University of Sydney, and an ARC DECRA fellow; he obtained his Ph.D. in 2017 from Columbia University, before joining Stanford as a Motwani Postdoctoral Fellow, then IBM Research as a Goldstine Postdoctoral Fellow. His main areas of research are distribution testing (and, broadly speaking, property testing) and learning theory; focusing, in particular, on understanding the computational aspects of learning and statistical inference subject to various resource or information constraints.