UCL logo
skip to navigation. skip to content.

Gatsby Computational Neuroscience Unit




UCL Home
  • UCL Home
  • UCL Gatsby Computational Neuroscience Unit
UCL Gatsby Unit
  • introduction
  • people
  • research
  • publications
  • courses
  • phd programme
  • events
  • directions
  • greater gatsby
  • vacancies
  • Internal
  • ucl

 

 

  • Home
  • Staff & Students
  • Vacancies

 

Tugkan Batu
(http://www.maths.lse.ac.uk/Personal/batu/)

 

(LSE London School of Economics)

 

Wednesday 18th January 2012

16:00

 

B10 Seminar Room, Basement,

Alexandra House, 17 Queen Square, London, WC1N 3AR

 

 

Testing Properties of Discrete Distributions

 

 

In this talk, we will survey some algorithmic results for several fundamental statistical inference tasks.  The algorithms are given access only to i.i.d. samples from the discrete input distributions and make inferences based on these samples.  The main focus of this research is the sample complexity of each task as a function of the domain size for the underlying discrete probability distributions. The inference tasks studied include (i) similarity to a fixed distribution (i.e., goodness-of-fit); (ii) similarity between two distributions (i.e., homogeneity); (iii) independence of joint distributions; and (iv) entropy estimation.  For each of these tasks, an algorithm with sublinear sample complexity is presented (e.g., a goodness-of-fit test on a discrete domain of size $n$ is shown to require $O(\sqrt{n}polylog(n))$ samples). Given certain extra information on the distributions (such as the distribution is monotone or unimodal with respect to a fixed total order on the domain), the sample complexity of these tasks become polylogarithmic in the domain size.

 

 

 

 

  • Disclaimer
  • Freedom of Information
  • Accessibility
  • Privacy
  • Advanced Search
  • Contact Us
Gatsby Computational Neuroscience Unit - Alexandra House - 17 Queen Square - London - WC1N 3AR - Telephone: +44 (0)20 7679 1176

© UCL 1999–20112011