The Power of Linear Estimators

By Gregory Valiant, Paul Valiant. 2011

156 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, background): “This line of work is related closely to the classic problem of parameter estimation in statistics, and recent advances have pinpointed the optimal rates for functionals such as entropy, support size, and many others (see for instance [Pan04, RRSS09, VV11, JVYW15, WY16, AOST17, JVHW17, ADOS17] for so”
Differentially private anonymized histograms (2019, background): “Given a discrete distribution p over k symbols, a symmetric property is a property that depends only on the multiset of probabilities [18, 19], e.”
Minimax Estimation of the $L_1$ Distance (2017, methodology): “The main reason is that [5], [6] did not conduct approximation when p ≥ ln n n .”
Minimax Rates of Entropy Estimation on Large Alphabets via Best Polynomial Approximation (2014, background): “For (12) we need to choose a pair of priors, which, in this case, are distributions on the probability simplex M k , is to ensure the entropy values are separated.”
Instance optimal learning of discrete distributions (2016, methodology): “…and general way (a main tool from these works is a Chebyshev polynomial earthmover scheme, which was also repurposed for a rather diﬀerent end in [33]; the main improvement in the analysis is that our results no longer require any bound on the support size of the distribution, and the results no…”
Chebyshev polynomials, moment matching, and optimal estimation of the unseen (2015, background): “Finally, we mention that a general framework of designing and analyzing linear estimators is given in [40] based on linear programming (as opposed to the approximation-theoretic approach in the current paper).”
Maximum Likelihood Estimation of Functionals of Discrete Distributions (2014, methodology): “Valiant and Valiant [18] constructed another approximation based estimator that achieved better theoretical properties than the linear programming ones, which was not yet shown to be minimax rate-optimal for all ranges of S and n.”
An Automatic Inequality Prover and Instance Optimal Identity Testing (2014, background): “) For any constants 1 < 2, it requires Θ( n logn ) samples to distinguish ||p − q|||1≤ 1 from ||p − q|||1≥ 2 when p is the uniform distribution on n elements, many more than the √ n needed here [16], [17].”
Estimating the Unseen (2013, background): “The linear estimators of [2] can be viewed as a variant of this estimator with provable performance bounds.”
Minimax Rate-optimal Estimation of KL Divergence between Discrete Distributions (2016, unknown): “Hence, the optimal estimator Ĥ for entropy [1], [12]–[14] can be used here and it remains to estimate ∑S i=1 pi ln qi, i.”
Testing Shape Restrictions of Discrete Distributions (2015, background): “Besides the many technical details one has to control for the parameters to work out, one key element is the use of a tolerant testing algorithm for closeness of two distributions due to [52], whose (tight) sample complexity scales as n/ log n for a domain of size n.”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, unknown): “Starting with References [8, 10, 33], this includes the testing of symmetric properties [47, 53, 54, 56], of structured families [3, 4, 11, 17, 19, 20, 36], as well as testing under some assumption on the unknown instance [24, 27, 28, 49].”