Efficient universal estimators for symmetric property estimation
Abstract/Contents
- Abstract
- Given i.i.d samples from an unknown distribution, estimating its symmetric properties is a classical problem in information theory, statistics, operations research and computer science. Symmetric properties are those that are invariant to label permutations and include popular functionals such as entropy and support size. Over the past decade, the study of time and sample complexities for estimating properties of distributions has received great attention leading to computationally efficient and sample optimal estimators for various symmetric properties. Most of these estimators were property specific and the design of a single estimator that is sample optimal for any symmetric property remained a central open problem in the area. In a seminal result, Acharya et al. showed that computing an approximate profile maximum likelihood (PML) distribution, a distribution that maximizes the likelihood of the observed multiset of frequencies, allows statistically optimal estimation of various symmetric properties. However, since its introduction by Orlitsky et al. in 2004, efficient computation of approximate PML distributions remained a well-known open problem. In our work, we resolved this question by designing the first efficient algorithm for computing an approximate PML distribution. More broadly our investigation has led to a deeper understanding of various computational and statistical aspects of PML and universal estimators. Additional results include the design of better algorithms for deterministic permanent approximation, new rounding algorithms, faster optimization methods and novel techniques for statistical analysis.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Shiragur, Kirankumar |
|---|---|
| Degree supervisor | Charikar, Moses |
| Degree supervisor | Sidford, Aaron |
| Thesis advisor | Charikar, Moses |
| Thesis advisor | Sidford, Aaron |
| Thesis advisor | Valiant, Gregory |
| Degree committee member | Valiant, Gregory |
| Associated with | Stanford University, Department of Management Science and Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Kirankumar Shiragur. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/gr443rv6306 |
Access conditions
- Copyright
- © 2022 by Kirankumar Shiragur
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...