On Learning and Covering Structured Distributions
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/92966 |
| _version_ | 1826189667543810048 |
|---|---|
| author | Kamath, Gautam (Gautam Chetan) |
| author2 | Constantinos Daskalakis. |
| author_facet | Constantinos Daskalakis. Kamath, Gautam (Gautam Chetan) |
| author_sort | Kamath, Gautam (Gautam Chetan) |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. |
| first_indexed | 2024-09-23T08:19:14Z |
| format | Thesis |
| id | mit-1721.1/92966 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:19:14Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/929662019-04-09T17:55:50Z On Learning and Covering Structured Distributions Kamath, Gautam (Gautam Chetan) Constantinos Daskalakis. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 91-95). We explore a number of problems related to learning and covering structured distributions: Hypothesis Selection: We provide an improved and generalized algorithm for selecting a good candidate distribution from among competing hypotheses. Namely, given a collection of ... hypotheses containing at least one candidate that is ...-close to an unknown distribution, our algorithm outputs a candidate which is ...-close to the distribution. The algorithm requires ... samples from the unknown distribution and ... time, which improves previous such results (such as the Scheffé estimator) from a quadratic dependence of the running time on ... to quasilinear. Given the wide use of such results for the purpose of hypothesis selection, our improved algorithm implies immediate improvements to any such use. Proper Learning Gaussian Mixture Models: We describe an algorithm for properly learning mixtures of two single-dimensional Gaussians without any separability assumptions. Given ... samples from an unknown mixture, our algorithm outputs a mixture that is ...-close in total variation distance, in time ... Our sample complexity is optimal up to logarithmic factors, and significantly improves upon both Kalai et al., whose algorithm has a prohibitive dependence on 1/..., and Feldman et al., whose algorithm requires bounds on the mixture parameters and depends pseudo-polynomially in these parameters. Covering Poisson Multinomial Distributions: We provide a sparse ..-cover for the set of Poisson Multinomial Distributions. Specifically, we describe a set of ... distributions such that any Poisson Multinomial Distribution of size ?? and dimension ... is ...-close to a distribution in the set. This is a significant sparsification over the previous best-known ...-cover due to Daskalakis and Papadimitriou [24], which is of size ..., where ... is polynomial in ... and exponential in ... This cover also implies an algorithm for learning Poisson Multinomial Distributions with a sample complexity which is polynomial in ... and log ... by Gautam Kamath. S.M. 2015-01-20T15:30:36Z 2015-01-20T15:30:36Z 2014 2014 Thesis http://hdl.handle.net/1721.1/92966 900006537 eng 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. http://dspace.mit.edu/handle/1721.1/7582 95 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kamath, Gautam (Gautam Chetan) On Learning and Covering Structured Distributions |
| title | On Learning and Covering Structured Distributions |
| title_full | On Learning and Covering Structured Distributions |
| title_fullStr | On Learning and Covering Structured Distributions |
| title_full_unstemmed | On Learning and Covering Structured Distributions |
| title_short | On Learning and Covering Structured Distributions |
| title_sort | on learning and covering structured distributions |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/92966 |
| work_keys_str_mv | AT kamathgautamgautamchetan onlearningandcoveringstructureddistributions |