Estimation of Entropy in Constant Space with Improved Sample Complexity
Authors: Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we give a new constant memory scheme that reduces the sample complexity to (k/ 2) polylog(1/ ). We conjecture that this is optimal up to polylog(1/ ) factors. Our novel contribution is a modification which estimates a bias incurred by the estimator; this change allows us to use only O(k log2 k log2(1/ )/ 2) samples. |
| Researcher Affiliation | Academia | Boston University and Northeastern University, University of Massachusetts Amherst, UC Berkeley, Stanford University. |
| Pseudocode | Yes | Figure 1: Description of the estimator for log(1/pi). Subroutine Log Estimator(D, i). Algorithm 1 Estimating E[ log X/t] via Bucketing. |
| Open Source Code | No | Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A] |
| Open Datasets | No | The paper focuses on theoretical algorithms for estimating entropy from i.i.d. samples from an unknown distribution. It does not mention the use of any specific publicly available datasets for training, evaluation, or access information for such. |
| Dataset Splits | No | The paper does not describe dataset splits for training, validation, or testing, as it focuses on theoretical algorithm design and analysis for i.i.d. samples from an unknown distribution. |
| Hardware Specification | No | The paper focuses on algorithms using 'O(1) words of memory' but does not specify any particular hardware components (e.g., CPU, GPU models) used for computation. The author checklist states N/A for compute resources. |
| Software Dependencies | No | The paper does not specify any software dependencies (e.g., programming languages, libraries, or specific versions) used for its work. The author checklist states N/A for training details. |
| Experiment Setup | No | The paper describes theoretical algorithms and their analysis, not empirical experiments with specific setup details like hyperparameters or training configurations. The author checklist states N/A for training details. |