A CLT and tight lower bounds for estimating entropy.

Gregory Valiant, Paul Valiant

Type: Article

Publication Date: 2010-01-01

Citations: 72

Locations

Electronic colloquium on computational complexity - View

Similar Works

Action	Title	Year	Authors
+	Computing Maximum Entropy Distributions Everywhere.	2017	Damian Straszak Nisheeth K. Vishnoi
+	Optimal Randomized Approximations for Matrix based Renyi's Entropy	2022	Yuxin Dong Tieliang Gong Shujian Yu Chen Li
+	On the Complexity of Computational Problems Regarding Distributions	2011	Oded Goldreich Salil Vadhan
+	Computationally Efficient Approximations for Matrix-based Renyi's Entropy	2021	Tieliang Gong Yuxin Dong Shujian Yu
+ PDF Chat	Computationally Efficient Approximations for Matrix-Based Rényi's Entropy	2022	Tieliang Gong Yuxin Dong Shujian Yu Bo Dong
+	Efficient Computing of Stochastic Complexity.	2003	Petri Kontkanen Wray Buntine Petri Myllymäki J. Rissanen Kirsi Tirri
+	Confidence-Optimal Random Embeddings.	2021	Maciej Skórski
+	Johnson-Lindenstrauss Transforms with Best Confidence	2021	Maciej Skórski
+ PDF Chat	Chernoff-Type Concentration of Empirical Probabilities in Relative Entropy	2020	F Richard Guo Thomas S. Richardson
+	Faster Sublinear Algorithms using Conditional Sampling	2016	Themistoklis Gouleakis Christos Tzamos Manolis Zampetakis
+	Confidence-Optimal Random Embeddings	2021	Maciej Skórski
+ PDF Chat	Approximate Central Limit Theorems	2017	Ben Berckmoes Geert Molenberghs
+	Maximum Entropy Distributions: Bit Complexity and Stability.	2017	Damian Straszak Nisheeth K. Vishnoi
+	Approximate central limit theorems	2016	Ben Berckmoes Geert Molenberghs
+ PDF Chat	Bayesian computation in big spaces-nested sampling and Galilean Monte Carlo	2012	John Skilling
+	Statistical Inference over Large Domains	2016	Ananda Theertha Suresh
+ PDF Chat	A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions	2020	Héctor Zenil
+	Entropy, Optimization and Counting	2013	Mohit Singh Nisheeth K. Vishnoi
+	Entropy, Optimization and Counting	2013	Mohit Singh Nisheeth K. Vishnoi
+	Maximum Entropy Distributions: Bit Complexity and Stability	2017	Damian Straszak Nisheeth K. Vishnoi

Works That Cite This (49)

Action	Title	Year	Authors
+ PDF Chat	Estimation of Wasserstein distances in the Spiked Transport Model	2022	Jonathan Niles‐Weed Philippe Rigollet
+	Distributed Simulation and Distributed Inference	2018	Jayadev Acharya Clément L. Canonne Himanshu Tyagi
+ PDF Chat	Optimality of the Plug-in Estimator for Differential Entropy Estimation under Gaussian Convolutions	2019	Ziv Goldfeld Kristjan Greenewald Jonathan Weed Yury Polyanskiy
+ PDF Chat	On the Structure, Covering, and Learning of Poisson Multinomial Distributions	2015	Constantinos Daskalakis Gautam Kamath Christos Tzamos
+	Wasserstein Identity Testing	2017	Shichuan Deng Wenzheng Li Xuan Wu
+	Convergence of Smoothed Empirical Measures With Applications to Entropy Estimation	2020	Ziv Goldfeld Kristjan Greenewald Jonathan Niles‐Weed Yury Polyanskiy
+ PDF Chat	Chebyshev polynomials, moment matching, and optimal estimation of the unseen	2019	Yihong Wu Pengkun Yang
+ PDF Chat	Multivariate approximations in Wasserstein distance by Stein’s method and Bismut’s formula	2018	Xiao Fang Qi-Man Shao Lihu Xu
+	Stein operators, kernels and discrepancies for multivariate continuous distributions	2018	Guillaume Mijoule Gesine Reinert Yvik Swan
+	Regularity of solutions of the Stein equation and rates in the multivariate central limit theorem	2018	Thomas Gallouët Guillaume Mijoule Yvik Swan

Works Cited by This (16)

Action	Title	Year	Authors
+	An Exposition of Götze's Estimation of the Rate of Convergence in the Multivariate Central Limit Theorem	2010	Rabi Bhattacharya Susan Holmes
+ PDF Chat	On the Rate of Convergence in the Multivariate CLT	1991	Friedrich Götze
+	On the Rate of Multivariate Poisson Convergence	1999	Bero Roos
+	Estimating Entropy on&lt;tex&gt;$m$&lt;/tex&gt;Bins Given Fewer Than&lt;tex&gt;$m$&lt;/tex&gt;Samples	2004	Liam Paninski
+ PDF Chat	Multivariate normal approximation with Stein’s method of exchangeable pairs under a general linearity condition	2009	Gesine Reinert Adrian Röllin
+	Towards estimation error guarantees for distinct values	2000	Moses Charikar Surajit Chaudhuri Rajeev Motwani Vivek Narasayya
+	Upper bounds on Poisson tail probabilities	1987	Peter W. Glynn
+	The Space Complexity of Approximating the Frequency Moments	1999	Noga Alon Yossi Matias Márió Szegedy
+	MULTIVARIATE NORMAL APPROXIMATION USING EXCHANGEABLE PAIRS	2008	Sourav Chatterjee Elizabeth Meckes
+ PDF Chat	Sketching and Streaming Entropy via Approximation Theory	2008	Nicholas J. A. Harvey Jelani Nelson Krzysztof Onak