Assouad, Fano, and Le Cam

By Bin Yu. 1997

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

Learning discrete distributions: user vs item-level privacy (2020, methodology): “The proof of Assouad’s Lemma relies on Le Cam’s [Le Cam, 1973, Yu, 1997] method, which provide lower bounds for min-max error in hypothesis testing.”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, methodology): “We can relate the accuracy of a probability estimate to the probability of error for the multiple hypothesis testing problem with hypotheses given by p z using the standard Fano’s method ( cf. [55]).”
Privacy Aware Learning (2012, methodology): “We then use lower bounds on the error probability in tests, such as Fano s and Le Cam s inequalities [Yu 1997], to obtain a lower bound on the testing error.”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “Exponential-sized model family will not work Standard lower bounds in SLT often start with the construction of a family of problem instances that has an exponential size (Yu, 1997).”
Minimax Optimal Procedures for Locally Private Estimation (2016, methodology): “Another classical approach to deriving minimax lower bounds is Assouad’s method (Assouad 1983; Yu 1997).”
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation (2013, background): “, Lemma 1 of Yu [30] or Theorem 2.”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, neutral): “Optimizing F (x) to within ✏ accuracy then implies recovering the bias of the Bernoulli random variable, which requires ⌦(1/✏2) queries based on a standard information theoretic result [2, 19].”
The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information (2018, methodology): “In this case, a number of tools are available, but to keep our presentation tighter, we focus on the generalized version of Le Cam’s method [33, 56].”
Privacy and Statistical Risk: Formalisms and Minimax Bounds (2014, methodology): “Then Le Cam’s method gives the following lower bound (recall expression (4); see also [32, 29, Theorem 2.2]), where in the lemma P denotes the joint distribution of the random variable V ∈ { 0 , 1 , the sample X 1: n iid ∼ P ν conditional on V = ν , and the estimator Lemma 1 (Le Cam’s method) .”
Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations (2013, methodology): “Our basic strategy is to reduce the optimization problem to several binary hypothesis testing problems: we choose a finite set of functions, show that optimizing well implies that one can solve each of the binary hypothesis tests, and then, as in statistical minimax theory [33], [34], apply divergen”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “An exposition of these three methods and their connections is presented in [Yu97] 1 .”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, methodology): “There are only a handful of standard techniques to prove lower bounds; and indeed the vastmajority of the lower bounds in the literature are shown via Le Cam’s two-point method (also known as the “easy direction” of Yao’s minimax principle) [46, 58].”
Optimality guarantees for distributed statistical estimation (2014, methodology): “Many papers in mathematical statistics study the classical minimax risk (1), and its behavior is precisely characterized for a range of problems [19, 33, 31, 30].”
Lower bounds for non-convex stochastic optimization (2019, background): “Proof of Lemma 11 The proof follows standard arguments used to derive informationtheoretic lower bounds for statistical estimation [31, 54].”
Optimal rates of convergence for covariance matrix estimation (2010, methodology): “ ¯P = 1 p1 Pp 1 m=1 Pθm. Lemma 7. Let T be an estimator of θbased on an observation from a distribution in the collection {Pθ,θ∈Θ={θ0,θ1,...,θp1}}, then sup θ EL(T,θ)≥ 1 2 rminkPθ0 ∧ ¯Pk. We refer to Yu (1997) for more detailed discussions on Le Cam’s method. To apply Le Cam’s method, we need to ﬁrs”