Testing shape restriction properties of probability distributions in a unified way

We study the question of testing structured properties of discrete distributions. Specifically, given sample access to an arbitrary distribution D over [n] and a property P, the goal is to distinguish between ... Building on a result of [9], we develop a general algorithm for this question, which applies to a large range of "shape-constrained" properties, including monotone, log-concave, t-modal and Poisson Binomial distributions. Our generic property tester works for properties that exclusively contain distributions which can be well approximated by L-histograms for a small (usually logarithmic in the domain size) value of L. The sample complexity of this generic approach is ... Moreover, for all cases considered, our algorithm has near-optimal sample complexity. Finally, we also describe a generic method to prove lower bounds for this problem, and use it to derive strong converses to our algorithmic results. More specifically, we use the following reduction technique: we compose the property tester for a class-C of distributions with an agnostic learner for that same class to get a tester for subset CHARD ... C for which a lower bound is known.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Gouleakis, Themistoklis

Advisor dc:contributor.advisor

• Ronitt Rubinfeld.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/99864

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99864