(Warning: These materials may be subject to lots of typos and errors. We are grateful if you could spot errors and leave suggestions in the comments, or contact the author at yjhan@stanford.edu.) 

In previous lectures we have seen the ideas of model reduction and its application in establishing the asymptotic lower bounds. However, in many scenarios we would like to find good non-asymptotic bounds, and as we show in the examples of Lecture 3, finding such reductions may be quite difficult. In this and the next few lectures, we will introduce the testing idea which transforms the target problem (usually the estimation problem) into a proper testing problem. Despite the conceptual simplicity, the testing problem may take various forms, some of which may be difficult to analyze. This will be the central topic of the next few lectures. 

1. -divergences and Inequalities 

1.1. -divergences 

First we look at the possibly simplest testing problem: if and are two probability measures on the same probability space, and a random sample is drawn from either or . A (binary) testing problem aims to find some test which with high probability outputs when , and outputs when . To quantify the performance of a certain test , we define the total error probability as follows: 

Intuitively, when and are close to each other, we will expect that the total error probability for any test is large for they are hard to distinguish. Conversely, when and are very far from each other (e.g., with a disjoint support), then there exists some test which can well distinguish them. The next lemma gives the expression of the minimum .

Lemma 1 (Le Cam’s first lemma) Minimizing all measurable tests gives

Recall that is the total variation distance between and . 

Proof: Let , then 

with equality if and only if .  

By Lemma 1, the total variation distance between and exactly quantifies the minimum total error probability of distinguishing between two probability distributions. Similar to Lemma 1, if we impose different weights on the error probabilities, we will arrive at some divergences of the form , where is some constant, and is the weight on . Recall from convex analysis that for any convex function with compact support on , its second-order derivative always exists in the sense of a positive Radon measure, and 

for some .

Remark 1 The decomposition (1) of convex functions has several applications, e.g., in the local time analysis of continuous martingales. 

Motivated by (1), we can actually take a convex combination of the above divergences and arrive at the general class of -divergences. 

Definition 2 (-divergence) For a convex function on with , the -divergence between probability measures and on is defined as

where is the absolute continuous part of w.r.t. , and . 

In most practical scenarios, we have , and therefore . Some well-known examples of -divergences are as follows. 

Example 1

1. : total variation distance ; 

2. : Hellinger distance ; 

3. : Kullback–Leibler (KL) divergence ; 

4. : -divergence . 

The following properties also hold for any -divergences. 

Lemma 3  and is joint convex in . In particular, for any transition kernel . 

Remark 2 The last inequality is known as the data processing inequality. 

Proof: The non-negativity follows from convexity and Jensen’s inequality. The joint convexity is due to that of the perspective transform for convex . Let be the output of through kernel , then the last inequality follows from the joint convexity and 

We leave the details to the readers.  

1.2. Joint range 

Lemma 1 involves the computation of the total variation distance, which may be hard to evaluate exactly for most statistical models, especially when there is a tensor power structure. As a comparison, Hellinger, KL and -divergences tensorize better: 

Consequently, to apply Lemma 1 to proving lower bounds, we need upper bounds of the total variation distance in terms of Hellinger, KL or . We have seen examples of such inequalities from Lecture 3, but have no clue whether the claimed inequalities are tight. To obtain the best inequalities between different -divergences, we study the joint range of -divergences. 

For two convex functions on with , we call is in the joint range of if we can find two distributions over some common probability space such that . Hence, the joint range exactly characterizes the relationship between different -divergences. The central result is as follows: 

Theorem 4 Let be the joint range of , and be the joint range of when both and are discrete distributions supported on at most elements. Then

where denotes the convex hull. 

Theorem 4 provides a generic way to prove inequalities between different -divergences. Specifically, it shows that to obtain the joint range, it suffices to choose and , compute the pair , vary and then take the convex closure. The proof of Theorem 4 requires the following theorems in the convex analysis. 

Theorem 5 (Choquet–Bishop–de Leeuw) Let be a metrizable convex compact subset of a locally convex topological vector space . For any point in , there exists a probability measure supported on extremal points of such that . 

Theorem 6 (Fenchel–Eggleston–Carathéodory) Let be connected and . For any , there exists such that . 

We are ready to prove the statement of Theorem 4. 

Proof: For simplicity we always assume that , then . Viewing the likelihood ratio as a random variable , we conclude that 

Similarly, has the same representation with the additional constraint that can take at most values. Let be the set of all probability measures which are supported on and have unit mean. By linearity of the expectation and the convexity of we conclude that is convex. Moreover, since all extremal points of are supported on two elements, by Choquet–Bishop–de Leeuw theorem (note that any topological vector space is always locally convex under the weak- topology, where the unit sphere is compact and metrizable) we conclude that the distribution of can be written as a mixture of distributions supported on only two points. Then by the linearity of expectation again, we conclude that . 

For the second identity , first note that is a connected set for it is a continuous image of the divergence pair on . Hence, by Fenchel–Eggleston–Carathéodory theorem, any point in can be written as a convex combination of two points in , which gives rise to a random variable supported on at most elements.  

Based on Theorem 4, one may verify the following inequalities: 

• TV vs. Hellinger:
  Both inequalities are tight. 
• TV vs. KL: Pinsker’s inequality gives
  This bound is vacuous when , where better bounds are available:
  None of these bounds are tight. 
• Hellinger vs KL:
  This bound is tight. 
• KL vs. :
  This bound is tight. 

The above inequalities will be used quite often whenever we switch between convenient divergences.

2. Le Cam’s Two-point Method 

One popular way to prove a non-asymptotic lower bound of statistical estimation is via hypothesis testing. Let be the statistical model of interest, and the loss function is (at the moment we assume that the target is to estimate ). The idea is to use the following weaker lower bound 

Suppose that we can find two possible candidates of , say, and , such that the following two conditions hold: 

1. Large separation: the total loss is always large for any ; 
2. Indistinguishability: based on the observation, the observer cannot reliably distinguish between and ; 

then clearly the observer needs to pay a risk proportional to . The next theorem makes this intuition precise.

Theorem 7 (Two-point Method) Let be any loss function, and satisfy that

then 

Proof: The desired result follows from the following chain of inequalities: 

Note that in Theorem 7, the parameter characterizes the separation between the two points, and is the minimum error probability of testing between and (cf. Lemma 1). Typically these two quantities depend negatively on each other: when one becomes larger, the other gets smaller. A rule-of-thumb is to find such that is a constant, say , and then search for the largest possible separation . 

Although the proof of Theorem 7 did not explicitly apply testing arguments, the test can be seen as follows. Let the test be if , and otherwise, then the separability condition ensures that for as long as . Hence, 

Replacing with the above lower bound, and repeating the analysis in the proof of Theorem 7, a direct application of Lemma 1 gives the same result (with replaced by ). 

The two-point idea is simple but appears everywhere in various lower bounds, for it establishes the indistinguishability between two different tasks due to the uncertainties. Also, despite the conceptual simplicity, searching over all possible pairs of points is typically computationally expensive, and it requires effort to understand the problem structure and figure out the “correct” two points. In later lectures, this idea will be generalized in the following directions: 

• Multiple points instead of two-point; 
• One or both of the two points may be a mixture of distributions, i.e., the binary test has point-mixture or mixture-mixture structures; 
• The chioce of the two points may depend on the estimator . 

3. Examples of Two-point Methods 

The remainder of this lecture is devoted to the applications of the two-point method in various problems. 

3.1. Example I: Parameter Estimation 

We begin with the simplest example of the Gaussian location model for , and our target is to estimate . Since a natural guess is that local perturbation on makes the model indistinguishable, we choose and in the two-point method. Let be the minimax risk under the squared error loss, Theorem 7 gives 

where is the CDF of . Maximizing the above lower bound over gives . Compared with derived in Lecture 4, the two-point bound loses a constant multiplicative factor.

Next we consider the bounded mean scenario where for a known parameter in advance. Since the above is chosen to be in the end, this becomes infeasible if the upper bound is much smaller than . Consequently, we can choose and , which gives . This lower bound is also tight, for one of the estimators or attains it. 

Consider another location model where one observes and aims to estimate . Again, choosing and , the minimax risk is lower bounded by 

By the triangle inequality, 

Hence, choosing gives . The rate is also tight for the minimax risk, for the estimator attains the rate. 

Remark 3 The uniform location model is not QMD (see Lecture 4), thus it makes sense to have the correct minimax rate different from . Moreover, the inequality may not be tight for other models. 

3.2. Example II: Functional Estimation 

Recall the discrete entropy estimation problem, where we observe samples from a discrete distribution , and the target is to estimate the Shannon entropy . In Lecture 4 we proved an asymptotic minimax lower bound for the mean squared error, and here we show that the same bound holds non-asymptotically (even when grows with ). 

The idea of using two-point method here is that when we perturb each entry in the uniform distribution by some small , the value of the functional changes by an additive factor of , and the KL divergence between these two cases is . Hence, choosing will complete the proof. However, some cautions should be taken when choosing the specific points: 

• The two points cannot be , and . In this way, we have ; 
• The two points cannot be , and . In this way, we have if and otherwise. Hence, this choice fails for some parameters . 

The final choice of the two-point is as follows: 

Simple algebra gives , and 

Now choosing completes the proof of . This example shows that the choice of the two points may sometimes be a little bit delicate. 

3.3. Example III: Non-local Choice of Two Points 

We return to the entropy estimation problem, but this time we choose different points to arrive at an entirely different lower bound. Note that all above choices of the two points are based on local perturbations, and the resulting bounds are essentially for the variance. This example will show that a more sophisticated construction can also take care of the bias part. 

For observations , let be the sorted histogram of , i.e., is the sorted version of with . The next lemma shows that there exists a minimax estimator which depends only on . 

Lemma 8 For any estimator of the entropy , there exists an estimator such that

Proof: The proof relies on the symmetry of in permutations of . Let be any permutation on , clearly , and the distribution of under is the same as that under . Hence, let , the estimator 

depends only on , and the desired inequality follows from Jensen’s inequality.  

Lemma 8 shows that the model can be reduced to , which by data processing inequality results in a smaller total variation distance between two points. Now the new construction of the two points is motivated by the following lemma. 

Lemma 9 Let and be two probability vectors, with . Then

The proof of Lemma 9 is referred to the bibliographic notes. Lemma 9 shows that if the lower moments of and are equal, the total variation distance between their tensor powers will be small. This fact motivates us to consider distributions and which are repetitions of the vectors 

respectively, where is some fixed integer, and

1. and are valid distributions: ; 
2. and have matched moments: ; 
3. and have different entropies: . 

The existence of such vectors is ensured by the following lemma. 

Lemma 10 For any positive integer , there exist vectors and satisfying the above properties. 

Proof: Fix any -dimensional vector with distinct positive entries. Consider 

which for small enough clearly has positive zeros. Let be the zeros of , then comparing the coefficients of on both sides of the polynomial and invoking Newton’s identity, vectors and have matched moments up to . The first property is ensured via simple normalizations, and it suffices to choose a suitable to ensure the third property.  

Using the above two points, we have and for any . Moreover, for , we have 

Hence, by Lemma 9, 

which is strictly smaller than one if . Note that the choice of the integer is arbitrary, we conclude that the minimax risk is at least a positive constant whenever for any . This lower bound says nothing about when gets larger, but compared with the previous bound , the new bound shows that actually needs to be much larger than for the consistent estimation. 

In later lectures, it will be shown that the minimax risk of this problem is 

Hence, the current bound is slightly weaker than the first term, and the old bound is exactly the second term. 

3.4. Example IV: Robust Statistics 

In this section we look at the Gaussian mean estimation again, but now with outliers. Specifically, we consider the following Huber’s -contamination model: 

where denotes the outlier distribution and may be arbitrary. The robust estimation problem is that, given i.i.d. observations from , propose a robust estimator which minimizes the worst-case risk of estimating , where the worst case is taken over both and the outlier distribution . Under the squared loss, let be the minimax risk with samples and outlier probability . 

The central claim of this section is that 

This lower bound is tight for the Tukey median and some other estimators; we refer to the bibliographic notes. Since the lower bound even holds when , we may restrict our attention to showing that . 

To apply the two-point method, we need to choose both and , where the latter is more important in this robust setting. Since and can be arbitrary probability distributions, we actually have a large degree of freedom and can actually achieve perfect ambiguity here. This phenomenon is summarized in the following lemma. 

Lemma 11 Let be any probability distributions with . Then there exist probability distributions such that

Proof: Consider the signed measure . Clearly , and by assumption , where denotes the total variation measure of . Hence, by Jordan decomposition of signed measures, we have , where measures are mutually singular and . Finally, adding any common measure with to both completes the proof.  

By Lemma 11, it suffices to find such that 

and the incurred loss is . Hence, the lower bound is completed by choosing . 

3.5. Example V: Two-armed Bandits 

In this section we study the simplest online learning problem, namely, the two-armed bandit. At each time , the learner can pull one of the two arms, and the reward of pulling arm follows a standard normal distribution , where the mean parameters are unknown to the learner. A policy is a sequence where denotes the arm to pull at time , where can depend on all past policies and past rewards . The regret of a policy is defined as the difference of the cumulative reward of the best arm and that of the policy, i.e., 

The target of the online learning is to devise a policy with a small expected regret, where the expectation is taken over the randomness of the rewards (and therefore the random realizations of the policy). A fundamental tradeoff in online learning is the exploration-exploitation tradeoff, where the learner needs to pull the suboptimal arm sufficiently many times to identify the best arm with better precision, and also needs to exploit the current knowledge to focus on the arm which seems to be the best. 

In this section we aim to prove minimax lower bounds of the regrets in the two-armed bandits. First consider the case where can take any values in . The two-point method suggests that we may find two worlds such that 

1. there is no fixed policy whose regrets are small in both worlds; 
2. these two worlds are hard to distinguish. 

To do so, we may take in the first world, and in the second world, where is some parameter to be chosen. Note that in both worlds, pulling a wrong arm incurs an instanteous regret of . Let and be the distribution of the rewards up to time in respective worlds, then the minimax regret is lower bounded by 

Using Lemma 1 and 

we conclude that by choosing . 

We also consider the case where there is a known suboptimality gap between arms, i.e., . Using the above arguments and the inequality 

we will arrive at 

which converges to a constant as . However, this lower bound is not tight – we will show that as gets large. To show this stronger lower bound, we need a more delicate construction of the two points. 

Set in world I, and in world II. Let be defined as before, then 

where is the total number of pulls of arm , and denotes the expectation under world I. Hence, applying the previous arguments, we have 

Clearly, this is a better bound for small , while it is less useful when is large. However, a large implies that the learner pulls the suboptimal arm (i.e., arm 2) too many times in world I, and in mathematical words we have 

Note that these two bounds exactly characterize the tradeoff between exploitation and exploration. Combining these bounds, we have 

where the second inequality follows from the minimization of the inner sum with respect to . 

In summary, we have two different lower bounds: when there is no assumption on the optimality gap, then ; when the optimality gap is at least , then . Both bounds are tight and there exist policies attaining these bounds; we refer to bibliographic notes for details. 

3.6. Example VI: Multi-armed Bandits 

Interestingly, the two-point method can also give the correct minimax lower bound of the regret for general multi-armed bandits (in later lectures, we will provide a proof using multiple points). However, the following application of the two-point method differs from all previous ones. In previous examples, we fix two points and prove that all estimators (or policies) cannot achieve small risk (or regret) under both points. In this example, the construction of the two points depends on the policy. 

We first define the multi-armed bandit problem. In fact, the only difference from the two-armed case is that now there are arms in total, and the -th arm has reward distribution . The regret of a given policy is defined as 

To apply the two-point method, let the first point be . Clearly, the first arm is the optimal arm, and pulling any wrong arm incurs an instanteous regret . For any given policy , the choice of the second point will depend on the policy: for , let be the expected number of pulls of arm for policy under the first point. Since , there must exist some such that . In other words, under the first point, the policy does not pull arm much in expectation. Note that depends on the policy . 

Now the second point is as follows: , where the only difference from the first point is that . We claim that the two points are hard to distinguish: let be the distribution of all observed rewards under these two points, respectively, then 

Hence, by choosing we have , and consequently the worst-case regret for the policy is at least . By the arbitrariness of , this is a minimax lower bound. This bound is tight for multi-armed bandits. 

The idea of constructing points based on given approaches is widely used in problems where several rounds of adaptivity are available. One future lecture will be devoted exclusively to this topic. 

4. Bibliographic Notes 

The lower bound technique based on hypothesis testing was pioneered by Ibragimov and Khas’minskii (1977) (see also Le Cam (1973) for the binary case). The general -divergence was proposed by Csiszár (1967), and the joint range of -divergences (Theorem 4) was established in Harremoës and Vajda (2011). For the results in convex analysis, the Choquet–Bishop–de Leeuw theorem can be found in Phelps (2001), and the Fenchel–Eggleston–Carathéodory theorem can be found in Eggleston (1958). The inequalities between -divergences and the two-point method can be mostly found in the excellent textbook Tsabykov (2009). 

For the examples, the first lower bound of entropy estimation is taken from Wu and Yang (2016). For the second lower bound, Lemma 9 was proved in Valiant (2008) under the Poissonized model, and Lemma 10 is taken from Archaya et al. (2016). For robust statistics, Huber’s -contamination model dates back to Huber (1964), and the general lower bound technique in Lemma 11 is taken from Chen, Gao and Ren (2016). For the robust estimators achieving the lower bound, see Chen, Gao and Ren (2018) and Ilias et al. (2018). 

The lower bounds of bandit problems are taken from Voger (1960) and Lai and Robbins (1985). We also refer to Bubeck, Perchet and Rigollet (2013) and Lattimore and Szepesvári (2018) for non-asymptotic bounds. For more on bandit problems such as the upper bounds, we refer to the book Bubeck and Cesa-Bianchi (2012). 

1. Il’dar Abdullovich Ibragimov and Rafail Zalmanovich Khas’minskii. On the estimation of an infinite-dimensional parameter in Gaussian white noise. Doklady Akademii Nauk. Vol. 236. No. 5. Russian Academy of Sciences, 1977. 
2. Lucien Le Cam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics 1.1 (1973): 38-53. 
3. Imre Csiszár. Information-type measures of difference of probability distributions and indirect observation. studia scientiarum Mathematicarum Hungarica 2 (1967): 229-318. 
4. Peter Harremoës and Igor Vajda. On pairs of -divergences and their joint range. IEEE Transactions on Information Theory 57.6 (2011): 3230-3235. 
5. Robert R. Phelps. Lectures on Choquet’s theorem. Springer Science & Business Media, 2001. 
6. H. G. Eggleston. Convexity. Cambridge University Press, 1958. 
7. Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009. 
8. Yihong Wu and Pengkun Yang, Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory 62.6 (2016): 3702-3720. 
9. Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing 40.6 (2011): 1927-1968. 
10. Jayadev Acharya et al. Estimating Rényi entropy of discrete distributions. IEEE Transactions on Information Theory 63.1 (2016): 38-56. 
11. Peter J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics (1964): 73-101. 
12. Mengjie Chen, Chao Gao, and Zhao Ren. A general decision theory for Huber’s -contamination model. Electronic Journal of Statistics 10.2 (2016): 3752-3774. 
13. Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance and scatter matrix estimation under Huber’s contamination model. The Annals of Statistics 46.5 (2018): 1932-1960. 
14. Ilias Diakonikolas et al. Robustly learning a gaussian: Getting optimal error, efficiently. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018. 
15. Walter Vogel. A sequential design for the two armed bandit. The Annals of Mathematical Statistics 31.2 (1960): 430-443. 
16. Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6.1 (1985): 4-22. 
17. Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet. Bounded regret in stochastic multi-armed bandits. Conference on Learning Theory, 2013. 
18. Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint (2018). 
19. Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning 5.1 (2012): 1-122. 

(Warning: These materials may be subject to lots of typos and errors. We are grateful if you could spot errors and leave suggestions in the comments, or contact the author at yjhan@stanford.edu.) 

In this lecture, we establish the asymptotic lower bounds for general statistical decision problems. Specifically, we show that models satisfying the benign local asymptotic normality (LAN) condition are asymptotically equivalent to a Gaussian location model, under which the Hájek–Le Cam local asymptotic minimax (LAM) lower bound holds. We also apply this theorem to both parametric and nonparametric problems. 

1. History of Asymptotic Statistics 

To begin with, we first recall the notions of the score function and Fisher information, which can be found in most textbooks. 

Definition 1 (Fisher Information) A family of distributions on is quadratic mean differentiable (QMD) at if there exists a score function such that

In this case, the matrix exists and is called the Fisher information at . 

R. A. Fisher popularized the above Fisher information and the usage of the maximum likelihood estimator (MLE) starting from 1920s. He believes that, the Fisher information of a statistical model characterizes the fundamental limits of estimating based on i.i.d. observations from , and MLE asymptotically attains this limit. More specifically, he makes the following conjectures: 

1. For any asymptotically normal estimators such that for any , there must be
   
2. The MLE satisfies that for any . 

Although the second conjecture is easier to establish assuming certain regularity conditions, the first conjecture, which seems to be correct by the well-known Cramér-Rao bound, actually caused some trouble when people tried to prove it. The following example shows that (1) may be quite problematic. 

Example 1 Here is a counterexample to (1) proposed by Hodges in 1951. Let , and consider a Gaussian location model where are i.i.d. distributed as . A natural estimator of is the empirical mean , and the Fisher information is . The Hodges’ estimator is constructed as follows:

It is easy to show that for any , with for non-zero and for . Consequently, (1) does not hold for the Hodges’ estimator. The same result holds if the threshold in (2) is changed by any sequence with and . 

Hodges’ example suggests that (1) should at least be weakened in appropriate ways. Observing the structure of Hodges’ estimator (2) carefully, there can be three possible attempts: 

1. The estimator is superefficient (i.e., where (1) fails) only at one point . It may be expected that the set of such that (1) fails is quite small. 
2. Although the Hodges’ estimator satisfies the asymptotic normal condition, i.e., weakly converges to a normal distribution under , for any non-zero perturbation , the sequence does not weakly converge to the same distribution under . Hence, we may expect that (1) actually holds for more regular estimator sequences. 
3. Let be the risk function of the estimator under the absolute value loss. It can be computed that , while for . In other words, the worst-case risk over an interval of size around is still of the order , which is considerably larger than the single point . Therefore, it may make sense to consider the local minimax risk. 

It turns out that all these attempts can be successful, and the following theorem summarizes the key results of asymptotic statistics developed by J. Hájek and L. Le Cam in 1970s. 

Theorem 2 (Asymptotic Theorems) Let be a QMD statistical model which admits a non-singular Fisher information at . Let be differentiable at , and be an estimator sequence of in the model .

1. (Almost everywhere convolution theorem) If converges in distribution to some probability measure for every , and is non-singular for every , then there exists some probability measure such that
for Lebesgue almost every , where denotes the convolution. 

2. (Convolution theorem) If converges in distribution to some probability measure for , and is regular in the sense that weakly converges to the same limit under for every , then there exists some probability measure such that

3. (Local asymptotic minimax theorem) Let be a bowl-shaped loss function, i.e., is non-negative, symmetric and quasi-convex. In mathematical words, and the sublevel sets are convex for all . Then
with . 

We will be primarily interested in the local asymptotic minimax (LAM) theorem, for it directly gives general lower bounds for statistical estimation. This theorem will be proved in the next two sections using asymptotic equivalence between models, and some applications will be given in the subsequent section. 

2. Gaussian Location Model 

In this section we study the possibly simplest statistical model, i.e., the Gaussian location model, and will show in the next section that all regular models will converge to it asymptotically. In the Gaussian location model, we have and observes with a known non-singular covaraince . Consider a bowl-shaped loss function (defined in Theorem 2), a natural estimator of is , whose worst-case risk is with . The main theorem in this section is that the natural estimator is minimax. 

Theorem 3 For any bowl-shaped loss , we have

for . 

The proof of Theorem 3 relies on the following important lemma for Gaussian random variables. 

Lemma 4 (Anderson’s Lemma) Let and be bowl-shaped. Then

Proof: For , let . Since is bowl-shaped, the set is convex. Moreover, since 

it suffices to show that for any . We shall need the following inequality in convex geometry. 

Theorem 5 (Prépoka-Leindler Inequality, or Functional Brunn-Minkowski Inequality) Let and be non-negative real-valued measurable functions on , with

Then 

Let be the density function of , which is log-concave. Consider functions 

and , the log-concavity of and by convexity of ensures the condition of Theorem 5. Hence, Theorem 5 gives 

Finally, by symmetry of and , we have , which completes the proof.  

Now we are ready to prove Theorem 3. 

Proof: Consider a Gaussian prior on . By algebra, the posterior distribution of given is Gaussian distributed as . By Proposition 3 in Lecture 3 and the above Anderson’s lemma, the Bayes estimator is then . Since the minimax risk is lower bounded by any Bayes risk (as the maximum is no less than the average), we have 

Since this inequality holds for any , choosing with completes the proof of Theorem 3.  

3. Local Asymptotic Minimax Theorem 

In this section, we show that regular statistical models converge to a Gaussian location model asymptotically. To prove so, we shall need verifiable criterions to establish the convergence of Le Cam’s distance, as well as the specific regularity conditions. 

3.1. Likelihood Ratio Criteria for Asymptotic Equivalence 

In Lecture 3 we introduced the notion of Le Cam’s model distance, and showed that it can be upper bounded via the randomization criterion. However, designing a suitable transition kernel between models is too ad-hoc and sometimes challenging, and it will be helpful if simple criteria suffice. 

The main result of this subsection is the following likelihood ratio criteria: 

Theorem 6 Let and be finite statistical models. Further assume that is homogeneous in the sense that any pair in is mutually absolutely continuous. Define

as the likelihood ratios, and similarly for . Then if the distribution of under weakly converges to that of under . 

In other words, Theorem 6 states that a sufficient condition for asymptotic equivalence of models is the weak convergence of likelihood ratios. Although we shall not use that, this is also a necessary condition. The finiteness assumption is mainly for technical purposes, and the general case requires proper limiting arguments. 

To prove Theorem 6, we need the following notion of standard models. 

Definition 7 (Standard Model) Let , and be its Borel -algebra. A standard distribution on is a probability measure such that for any . The model

is called the standard model of . 

The following lemma shows that any finite statistical model can be transformed into an equivalent standard form. 

Lemma 8 Let be a finite model, and be a standard model with standard distribution being the distribution of under mean measure . Then . 

Proof: Since , the measure is a standard distribution. Moreover, let be the distribution of under , then 

for any measurable function , which gives , agreeing with the standard model. Finally, since , by the factorization criterion (e.g., Theorem 7 in Lecture 3) we conclude that the statistic is sufficient, and therefore .  

Lemma 8 helps to convert the sample space of all finite models to the simplex , and comparison between models is reduced to the comparison between their standard distributions. Consequently, we have the following quantitative bound on the model distance between finite models. 

Lemma 9 Let and be two finite models with standard distributions respectively. Then

where denotes the Dudley’s metric between probability measures , and the supremum is taken over all measurable functions with and for any . 

Remark 1 Recall that Dudley’s metric metrizes the weak convergence of probability measures on a metric space with its Borel -algebra. The fact that it is smaller than the total variation distance will be crucial to establish Theorem 6. 

Proof: Similar to the proof of the randomization criterion (Theorem 5 in Lecture 3), the following upper bound on the model distance holds: 

where denotes the Bayes risk of model under loss and prior , and the loss is non-negative and upper bounded by one in the supremum. By algebra, the Bayes risk admits the following simple form under the standard model with standard distribution : 

where the set is defined as 

Since the diameter of in is one, we conclude that is upper bounded by and -Lipschitz under . The rest of the proof follows from the definition of Dudley’s metric.  

Finally we are ready to present the proof of Theorem 6. Note that there is a bijective map between and , which is continuous under the model due to the homogeneity assumption. Then by continuous mapping theorem (see remark below), the weak convergence of likelihood ratios implies the weak convergence of their standard distributions. Since Dudley’s metric metrizes the weak convergence of probability measures, the result of Lemma 9 completes the proof. 

Remark 2 The continuous mapping theorem for weak convergence states that, if Borel-measurable random variables converges weakly to on a metric space, and is a function continuous on a set such that , then also converges weakly to . Note that the function is only required to be continuous on the support of the limiting random variable . 

3.2. Locally Asymptotically Normal (LAN) Models 

Motivated by Theorem 6, in order to prove that certain models asymptotically become normal, we may show that the likelihood functions weakly converge to those in the normal model. Note that for the Gaussian location model , the log-likelihood ratio is given by 

where for . The equation (3) motivates the following definition of local asymptotic normal (LAN) models, in which the likelihood function looks like (3). 

Definition 10 (Local Asymptotic Normality) A sequence of models with is called locally asymptotically normal (LAN) with central sequence and Fisher information matrix if

with under , and converges to zero in probability under for any fixed . 

Based on the form of the likelihood ratio in (4), the following theorem is then immediate. 

Theorem 11 If a sequence of models satisfies the LAN condition with Fisher information matrix , then for . 

Proof: Note that for any finite sub-model, Slutsky’s theorem applied to (4) gives the desired convergence in distribution, and clearly the Gaussian location model is homogeneous. Now applying Theorem 6 gives the desired convergence. We leave the discussion of the general case in the bibliographic notes.  

Now the only remaining task is to check the likelihood ratios for some common models and show that the LAN condition is satisfied. For example, for QMD models , we have 

where intuitively by CLT and LLN will arrive at the desired form (4). The next proposition makes this intuition precise. 

Proposition 12 Let be QMD in an open set with Fisher information matrix . Then the sequence of model , with satisfies the LAN condition with Fisher information . 

Proof: Write and . Then by Taylor expansion, 

where , and . By the QMD condition, we have 

Moreover, by the property of the score function, and 

Consequently, we conclude that 

For the second term, the QMD condition gives , and therefore LLN gives . For the last term, the Markov’s inequality gives , and therefore , as desired.  

In other words, Proposition 12 implies that all regular statistical models locally look like normal, where the local radius is . 

3.3. Proof of LAM Theorem 

Now we are ready to glue all necessary ingredients together. First, for product QMD statistical models, Proposition 12 implies that LAN condition is satisfied for the local model around any chosen parameter . Second, by Theorem 11, these local models will converge to a Gaussian location model with covariance . By definition of the model distance, the minimax risk of these local models will be asymptotically no smaller than that of the limiting Gaussian location model, which by Theorem 3 is with for bowl-shaped loss . Consequently, we have the following local asymptotic minimax theorem. 

Theorem 13 (LAM, restated) Let be a QMD statistical model which admits a non-singular Fisher information at . Let be differentiable at , and be an estimator sequence of in the model . Consider any compact action space , and any bowl-shaped loss function . Then

with . 

Note that here the compactness of the action space is required for the limiting arguments, while all our previous analysis consider finite models. Our arguments via model distance are also different from those used by H\'{a}jek and Le Cam, where they introduced the notion of contiguity to arrive at the same result with weaker conditions. Further details of these alternative approaches are referred to the bibliographic notes. 

4. Applications and Limitations 

In this section, we will apply the LAM theorem to prove asymptotic lower bounds for both parametric and nonparametric problems. We will also discuss the limitations of LAM to motivate the necessity of future lectures. 

4.1. Parametric Entropy Estimation 

Consider the discrete i.i.d. sampling model , where denotes the probability simplex on elements. The target is to estimate the Shannon entropy 

under the mean squared loss. We can apply LAM to prove a local minimax lower bound for this problem. 

First we compute the Fisher information of the multinomial model , where we set to be the free parameters. It is easy to show that 

By the matrix inversion formula , we have 

Now choosing and in LAM, after some algebra we arrive at 

Note that on the RHS is due to our arbitrary choice of the centering . 

4.2. Nonparametric Entropy Estimation 

Consider a continuous i.i.d. sampling model from some density, i.e., . Assume that the density is supported on , and the target is to estimate the differential entropy 

As before, we would like to prove a local minimax lower bound for the mean squared error around any target density . However, since the model is nonparametric and the parameter has an infinite dimension, there is no Fisher information matrix for this model. To overcome this difficulty, we may consider a one-dimensional parametric submodel instead.

Let be any measurable function with and , then is still a valid density on for small . Consequently, keeping small, the i.i.d. sampling model becomes a submodel parametrized only by . For this 1-D parametric submodel, the Fisher information at can be computed as 

Setting in LAM, we have 

and consequently 

Since our choice of the test function is arbitrary, we may actually choose the worst-case such that the above lower bound is maximized. We claim that the maximum value is 

Clearly, this value is attained for the test function For the maximality, the Cauchy–Schwartz inequality and the assumption gives 

Therefore, the parametric lower bound for nonparametric entropy estimation is 

4.3. Limitations of Classical Asymptotics 

The theorems from classical asymptotics can typically help to prove an error bound with an explicit constant, and it is also known that these bounds are optimal and achieved by MLE. However, there are still some problems in these approaches: 

1. Non-asymptotic vs. asymptotic: Asymptotic bounds are useful only in scenarios where the problem size remains fixed and the sample size grows to infinity, and there is no general guarantee of when we have entered the asymptotic regime (it may even require that ). In practice, essentially all recent problems are high-dimensional ones where the number of parameters is comparable to or even larger than the sample size (e.g., an over-parametrized neural network), and some key properties of the problem may be entirely obscured in the asymptotic regime. 
2. Parametric vs. nonparametric: The results in classical asymptotics may not be helpful for a large quantity of nonparametric problems, where the main problem is the infinite-dimensional nature of nonparametric problems. Although sometimes the parametric reduction is helpful (e.g., the entropy example), the parametric rate is in general not attainable in nonparametric problems and some other tools are necessary. For example, if we would like to estimate the density at some point , the worst-case test function will actually give a vacuous lower bound (which is infinity). 
3. Global vs. local: As the name of LAM suggests, the minimax lower bound here holds locally. However, the global structure of some problems may also be important, and the global minimax lower bound may be much larger than the supremum of local bounds over all possible points. For example, in Shannon entropy estimation, the bias is actually dominating the problem and cannot be reflected in local methods. 

To overcome these difficulties, we need to develop tools to establish non-asymptotic results for possibly high-dimensional or nonparametric problems, which is the focus of the rest of the lecture series. 

5. Bibliographic Notes 

The asymptotic theorems in Theorem 2 are first presented in Hájek (1970) and Hájek (1972), and we refer to Le Cam (1986), Le Cam and Yang (1990) and van der Vaart (2000) as excellent textbooks. Here the approach of using model distance to establish LAM is taken from Section 4, 6 of Liese and Miescke (2007); also see Le Cam (1972). 

There is another line of approach to establish the asymptotic theorems. A key concept is the contiguity proposed by Le Cam (1960), which enables an asymptotic change of measure. Based on contiguity and LAN condition, the distribution of any (regular) estimator under the local alternative can be evaluated. Then the convolution theorem can be shown, which helps to establish LAM; details can be found in van der Vaart (2000). LAM theorem can also be established directly by computing the asymptotic Bayes risk under proper priors; see Section 6 of Le Cam and Yang (1990). 

For parametric or nonparametric entropy estimation, we refer to recent papers (Jiao et al. (2015) and Wu and Yang (2016) for the discrete case, Berrett, Samworth and Yuan (2019) and Han et al. (2017) for the continuous case) and the references therein. 

1. Jaroslav Hájek, A characterization of limiting distributions of regular estimates. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 14.4 (1970): 323-330. 
2. Jaroslav Hájek, Local asymptotic minimax and admissibility in estimation. Proceedings of the sixth Berkeley symposium on mathematical statistics and probability. Vol. 1. 1972. 
3. Lucien M. Le Cam, Asymptotic methods in statistical theory. Springer, New York, 1986. 
4. Lucien M. Le Cam and Grace Yang, Asymptotics in statistics. Springer, New York, 1990. 
5. Aad W. Van der Vaart, Asymptotic statistics. Vol. 3. Cambridge university press, 2000. 
6. Friedrich Liese and Klaus-J. Miescke. Statistical decision theory. Springer, New York, NY, 2007. 
7. Lucien M. Le Cam, Limits of experiments. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Theory of Statistics. The Regents of the University of California, 1972. 
8. Lucien M. Le Cam, Locally asymptotically normal families of distributions. University of California Publications in Statistics 3, 37-98 (1960). 
9. Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman, Minimax estimation of functionals of discrete distributions. IEEE Transactions on Information Theory 61.5 (2015): 2835-2885. 
10. Yihong Wu and Pengkun Yang, Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory 62.6 (2016): 3702-3720. 
11. Thomas B. Berrett, Richard J. Samworth, and Ming Yuan, Efficient multivariate entropy estimation via -nearest neighbour distances. The Annals of Statistics 47.1 (2019): 288-318. 
12. Yanjun Han, Jiantao Jiao, Tsachy Weissman, and Yihong Wu, Optimal rates of entropy estimation over Lipschitz balls. arXiv preprint arXiv:1711.02141 (2017).

(Warning: These materials may be subject to lots of typos and errors. We are grateful if you could spot errors and leave suggestions in the comments, or contact the author at yjhan@stanford.edu.) 

This lecture starts to talk about specific tools and ideas to prove information-theoretic lower bounds. We will temporarily restrict ourselves to statistical inference problems (which most lower bounds apply to), where the presence of randomness is a key feature in these problems. Since the observer cannot control the realizations of randomness, the information contained in the observations, albeit not necessarily in a discrete structure (e.g., those in Lecture 2), can still be limited. In this lecture and subsequent ones, we will introduce the reduction and hypothesis testingideas to prove lower bounds of statistical inference, and these ideas will also be applied to other problems. 

1. Basics of Statistical Decision Theory 

To introduce statistical inference problems, we first review some basics of statistical decision theory. Mathematically, let be a collection of probability triplets indexed by , and the observation is a random variable following distribution for an unknown parameter in the known parameter set . The specific structure of is typically called models or experiments, for the parameter can represent different model parameters or theories to explain the observation . A decision rule, or a (randomized) estimator is a transition kernel from to some action space . Let be a loss function, where represents the loss of using action when the true parameter is . A central quantity to measure the quality of a decision rule is the risk in the following definition. 

Definition 1 (Risk) Under the above notations, the risk of the decision rule under loss function and the true parameter is defined as

Intuitively, the risk characterizes the expected loss (over the randomness in both the observation and the decision rule) of the decision rule when the true parameter is . When is a point mass for some deterministic function , we will also call as an estimator and the risk in (1) becomes 

Example 1 In linear regression model with random design, let the observations be i.i.d. with and . Here the parameter set is a finite-dimensional Euclidean space, and therefore we call this model parametric. The quantity of interest is , and the loss function may be chosen to be the prediction error of the linear estimator . 

Example 2 In density estimation model, let be i.i.d. drawn from some -Lipschitz density supported on . Here the parameter set of the unknown is the infinite-dimensional space of all possible -Lipschitz functions on , and we call this model non-parametric. The target may be to estimate the density at a point, the entire density, or some functional of the density. In respective settings, the loss functions can be

Example 3 By allowing general action spaces and loss functions, the decision-theoretic framework can also incorporate some non-statistical examples. For instance, in stochastic optimization may parameterize a class of convex Lipschitz functions , and denotes the noisy observations of the gradients at the queried points. Then the action space may just be the entire domain , and the loss function is the optimality gap defined as

In practice, one would like to find optimal decision rules for a given task. However, the risk is a function of and it is hard to compare two risk functions directly. Hence, people typically map the risk functions into scalars and arrive at the following minimax and Bayesian paradigm. 

Definition 2 (Minimax and Bayes Decision Rule) The minimax decision rule is the decision rule which minimizes the quantity . The Bayes decision rule under distribution (called the prior distribution) is the decision rule which minimizes the quantity . 

It is typically hard to find the minimax decision rule in practice, while the Bayes decision rule admits a closed-form expression (although hard to compute in general). 

Proposition 3 The Bayes decision rule under prior is given by the estimator

where denotes the posterior distribution of under (assuming the existence of regular posterior). 

Proof: Left as an exercise for the reader.  

2. Deficiency and Model Distance 

The central target of statistical inference is to propose some decision rule for a given statistical model with small risks. Similarly, the counterpart in the lower bound is to prove that certain risks are unavoidable for any decision rules. Here to compare risks, we may either compare the entire risk function, or its minimax or Bayes version. In this lecture we will focus on the risk function, and many later lectures will be devoted to appropriate minimax risks. 

We start with the task of comparing two statistical models with the same parameter set . Intuitively, one may think that the model with a smaller noise level would be better than the other, e.g., the model should be better than . However, this criterion is bad due to two reasons: 

1. There is no proper notion of noise for general (especially non-additive) statistical models; 
2. Even if a natural notion of noise exists for certain models, it is not necessarily true that the model with smaller noise is always better. For example, let
   the model has a smaller magnitude of the additive noise. However, despite with a larger magnitude of the noise, the model is actually noise-free since one can decode the perfect knowledge of from the observation. 

To overcome the above difficulties, we introduce the idea of model reduction. Specifically, we aim to establish the fact that for any decision rule in one model, there is another decision rule in the other model which is uniformly no worse than the former rule. The idea of reduction appears in many fields, e.g., in P/NP theory it is sufficient to work out one NP-complete instance (e.g., circuit satisfiability) from scratch and establish all others by polynomial reduction. This reduction idea is made precise via the following definition. 

Definition 4 (Model Deficiency) For two statistical models and , we call is -deficient relative to if for any finite subset , any finite action space , any loss function , and any decision rule based on model , there exists some decision rule based on model such that

Note that the definition of model deficiency does not involve the specific choice of the action space and loss function, and the finiteness of and in the definition is mainly for technical purposes. Intuitively speaking, is -deficient relative to if the entire risk function of some decision rule in is no worse than that of any given decision rule in , within an additive gap . 

Although Definition 4 gives strong performance guarantees for the -deficient model , it is difficult to verify the condition (4), i.e., to transform an arbitrary decision rule to some proper . A crucial observation here is that it may be easier to transform between models and , and in particular, when is a randomization of . For example, if there exists some stochastic kernel such that for all (where denotes the marginal distribution of the output of kernel with input distributed as ), then we may simply set to arrive at (4) with . The following theorem shows that model deficiency is in fact equivalent to approximate randomization. 

Theorem 5 Model is -deficient with respect to if and only if there exists some stochastic kernel such that

where is the total variation distance between probability measures and . 

Proof: The sufficiency part is easy. Given such a kernel and a decision rule based on model , we simply set , i.e., transmit the output through kernel and apply . Then for any , 

for the loss function is non-negative and upper bounded by one. 

The necessity part is slightly more complicated, and for simplicity we assume that all are finite (the general case requires proper limiting arguments). In this case, any decision rules or , loss functions and priors can be represented by a finite-dimensional vector. Given and , the condition (4) ensures that 

Note that the LHS of (5) is bilinear in and , both of which range over some convex sets (e.g., the domain for is exactly ), the minimax theorem allows to swap and of (5) to obtain that 

By evaluating the inner supremum, (6) implies the existence of some such that 

Finally, choosing and in (7), the corresponding is the desired kernel .  

Based on the notion of deficiency, we are ready to define the distance between statistical models, also known as the Le Cam’s distance. 

Definition 6 (Le Cam’s Distance) For two statistical models and with the same parameter set , Le Cam’s distance is defined as the infimum of such that is -deficient relative to , and is -deficient relative to . 

It is a simple exercise to show that Le Cam’s distance is a pesudo-metric in the sense that it is symmetric and satisfies the triangle inequality. The main importance of Le Cam’s distance is that it helps to establish equivalence between some statistical models, and people are typically interested in the case where or . The main idea is to use randomization (i.e., Theorem 5) to obtain an upper bound on Le Cam’s distance, and then apply Definition 4 to deduce useful results (e.g., to carry over an asymptotically optimal procedure in one model to other models). 

In the remainder of this lecture, I will give some examples of models whose distance is zero or asymptotically zero. In the next lecture it will be shown that regular models will always be close to some Gaussian location model asymptotically, and thereby the classical asymptotic theory of statistics can be established. 

3. Equivalence between Models 

3.1. Sufficiency 

We first examine the case where . By Theorem 5, models and are mutual randomizations. In the special case where is a deterministic function of (thus is the push-forward measure of through ), we have the following result. 

Theorem 7 Under the above setting, if and only if forms a Markov chain. 

Note that the Markov condition is the usual definition of sufficient statistics, and also gives the well-known Rao–Blackwell factorization criterion for sufficiency. Hence, sufficiency is in fact a special case of model equivalence, and deficiency can be thought of as approximate sufficiency. 

3.2. Equivalence between Multinomial and Poissonized Models 

Consider a discrete probability vector with . A widely-used model in practice is the multinomial model , which models the i.i.d. sampling process and draws i.i.d. observations . However, a potential difficulty in handling multinomial models is that the empirical frequencies of symbols are dependent, which makes the analysis annoying. To overcome this difficulty, a common procedure is to consider a Poissonized model , where we draw a Poisson random variable first and observes i.i.d. . Due to the nice properties of Poisson random variables, the empirical frequencies now follow independent scaled Poisson distribution. 

The next theorem shows that the multinomial and Poissonized models are asymptotically equivalent, which means that it actually does no harm to consider the more convenient Poissonized model for analysis, at least asymptotically. In later lectures I will also show a non-asymptotic result between these two models. 

Theorem 8 For fixed , . 

Proof: We only show that is -deficient relative to , with , where the other direction is analogous. By Theorem 5, it suffices to show that is an approximate randomization of . The randomization procedure is as follows: based on the observations under the multinomial model, let be the vector of empirical frequencies. Next draw an independent random variable . If , let be the output of the kernel. Otherwise, we generate i.i.d. samples , and let be the output. We remark that it is important that the above randomization procedure does not depend on the unknown . 

Let be the distribution of the Poissonized and randomized model under true parameter , respectively. Now it is easily shown that 

where , denotes the -fold produce of , takes the expectation w.r.t. , and takes the expectation w.r.t. random samples . To upper bound the total variation distance in (8), we shall need the following lemma. 

Lemma 9 Let and be the KL divergence and -divergence, respectively. Then

The proof of Lemma 9 will be given in later lectures when we talk about joint ranges of divergences. Then by Lemma 9 and Jensen’s inequality, 

Since by simple algebra, 

then by (8) we obtain that 

which goes to zero uniformly in as , as desired.  

Remark 1 In fact, the following non-asymptotic characterization

could be established. This result is contained in an upcoming paper.

3.3. Equivalence between Nonparametric Regression and Gaussian White Noise Models 

A well-known problem in nonparametric statistics is the nonparametric regression: 

where the underlying regression function is unknown, and is some noise level. Typically, the statistical goal is to recover the function at some point or globally, and some smoothness conditions are necessary to perform this task. A typical assumption is that belongs to some H\”{o}lder ball, where 

with denotes the smoothness parameter. 

There is also a continuous version of (9) called the Gaussian white noise model, where a process satisfying the following stochastic differential equation is observed: 

where is the standard Brownion motion. Compared with the regression model in (9), the white noise model in (10) gets rid of the quantization issue of and is therefore easier to analyze. Note that in both models is effectively the sample size. 

Let be the regression and white noise models with known parameters and the paramter set , respectively. The main result in this section is that, when , these models are asymptotically equivalent. 

Theorem 10 If , we have . 

Proof: Consider another Gaussian white noise model where the only difference is to replace in (10) by defined as 

Note that under the same parameter , we have 

which goes to zero uniformly in as . Therefore, by Theorem 5 and Lemma 9, we have . On the other hand, in the model the likelihood ratio between the signal distribution and the pure noise distribution is 

As a result, under model , there is a Markov chain . Since under the same parameter , under is identically distributed as under , by Theorem 7 we have exact sufficiency and conclude that . Then the rest follows from the triangle inequality.  

3.4. Equivalence between Density Estimation and Gaussian White Noise Models 

Another widely-used model in nonparametric statistics is the density estimation model, where samples are i.i.d. drawn from some unknown density . Typically some smoothness condition is also necessary for the density, and we assume that again belongs to the H\”{o}lder ball. 

Compared with the previous results, a slightly more involved result is that the density estimation model, albeit with a seemingly different form, is also asymptotically equivalent to a proper Gaussian white noise model. However, here the Gaussian white noise model should take the following different form: 

In other words, in nonparametric statistics the problems of density estimation, regression and estimation in Gaussian white noise are all asymptotically equivalent, under certtain smoothness conditions. 

Let be the density estimation model and the Gaussian white noise model in (11), respectively. The main result is summarized in the following theorem. 

Theorem 11 If and the density is bounded below from zero everywhere, then . 

Proof: Instead of the original density estimation model, we actually consider a Poissonized sampling model instead, where the observation under is a Poisson process on with intensity . Similar to the proof of Theorem 8, we have and it remains to show that . 

Fix an equal-spaced grid in with , where is a small constant depending only on . Next we come up with two new models and , where the only difference is that the parameter is replaced by defined as 

As long as , the same arguments in the proof of Theorem 10 can be applied to arrive at (for the white noise model, the assumption that is bounded away from zero ensures the smoothness of ). Hence, it further suffices to focus on the new models and show that . An interesting observation is that under the model , the vector with 

is sufficient. Moreover, under the model , the vector with 

is also sufficient. Further, all entries of and are mutually independent. Hence, the ultimate goal is to find mutual randomizations between and for . 

To do so, a first attempt would be to find a bijective mapping independently for each . However, this approach would lose useful information from the neighbors as we know that thanks to the smoothness of . For example, we have with , and with . Motivated by this fact, we represent and in the following bijective way (assume that is even): 

Note that is again an independent Poisson vector, we may repeat the above transformation for this new vector. Similar things also hold for . Hence, at each iteration we may leave half of the components unchanged, and apply the above transformations to the other half. We repeat the iteration for times (assuming is a power of ), so that finally we arrive at a vector of length consisting of sums. Let (resp. ) be the final vector of sums, and (resp. ) be the vector of remaining entries which are left unchanged at some iteration. 

Remark 2 Experienced readers may have noticed that these are the wavelet coefficients under the Haar wavelet basis, where superscripts and stand for father and mother wavelets, respectively. 

Next we are ready to describe the randomization procedure. For notational simplicity we will write as a representative example of an entry in , and write as a representative example of an entry in . 

For entries in , note that by the delta method, for , the random variable is approximately distributed as (in fact, the squared root is the variance-stabilizing transformation for Poisson random variables). The exact transformation is then given by 

where is an independent auxiliary variable. The mapping (12) is one-to-one and can thus be inverted as well. 

For entries in , we aim to use quantile transformations to convert to . For , let be the CDF of , and be the CDF of . Then the one-to-one quantile transformation is given by 

where again is an independent auxiliary variable. The output given by (13) will be expected to be close in distribution to , and the overall transformation is also invertible. 

The approximation properties of these transformations are summarized in the following theorem. 

Theorem 12 Sticking to the specific examples of and , let be the respective distributions of the RHS in (12) and (13), and be the respective distributions of and , we have

where is some universal constant, and denotes the Hellinger distance. 

The proof of Theorem 12 is purely probabilitistic and involved, and is omitted here. Applying Theorem 12 to the vector of length , each component is the sum of elements bounded away from zero. Consequently, let be the overall transition kernel of the randomization, the inequality gives 

As for the vector , the components lie in possible different levels. At level , the spacing of the grid becomes , and there are elements. Also, we have at -th level, with . Consequently, 

Since , we may choose to be sufficiently small (i.e., ) to make . The proof is completed.  

4. Bibliographic Notes 

The statistical decision theory framework dates back to Wald (1950), and is currently the elementary course for graduate students in statistics. There are many excellent textbooks on this topic, e.g., Lehmann and Casella (2006) and Lehmann and Romano (2006). The concept of model deficiency is due to Le Cam (1964), where the randomization criterion (Theorem 5) was proved. The present form is taken from Torgersen (1991). We also refer to the excellent monographs by Le Cam (1986) and Le Cam and Yang (1990). 

The asymptotic equivalence between nonparametric models has been studied by a series of papers since 1990s. The equivalence between nonparametric regression and Gaussian white noise models (Theorem 10) was established in Brown and Low (1996), where both the fixed and random designs were studied. It was also shown in a follow-up work (Brown and Zhang 1998) that these models are non-equivalent if . The equivalence of the density estimation model and others (Theorem 11) was established in Brown et al. (2004), and we also refer to a recent work (Ray and Schmidt-Hieber 2016) which relaxed the crucial assumption that the density is bounded below from zero. Poisson approximation or Poissonization is a well-known technique widely used in probability theory, statistics and theoretical computer science, and the current treatment is essentially taken from Brown et al. (2004). 

1. Abraham Wald, Statistical decision functions. Wiley, 1950. 
2. Erich L. Lehmann and George Casella, Theory of point estimation. Springer Science & Business Media, 2006. 
3. Erich L. Lehmann and Joseph P. Romano, Testing statistical hypotheses. Springer Science & Business Media, 2006. 
4. Lucien M. Le Cam, Sufficiency and approximate sufficiency. The Annals of Mathematical Statistics (1964): 1419-1455. 
5. Erik Torgersen, Comparison of statistical experiments. Cambridge University Press, 1991. 
6. Lucien M. Le Cam, Asymptotic methods in statistical theory. Springer, New York, 1986. 
7. Lucien M. Le Cam and Grace Yang, Asymptotics in statistics. Springer, New York, 1990. 
8. Lawrence D. Brown and Mark G. Low, Asymptotic equivalence of nonparametric regression and white noise. The Annals of Statistics 24.6 (1996): 2384-2398. 
9. Lawrence D. Brown and Cun-Hui Zhang, Asymptotic nonequivalence of nonparametric experiments when the smoothness index is . The Annals of Statistics 26.1 (1998): 279-287. 
10. Lawrence D. Brown, Andrew V. Carter, Mark G. Low, and Cun-Hui Zhang, Equivalence theory for density estimation, Poisson processes and Gaussian white noise with drift. The Annals of Statistics 32.5 (2004): 2074-2097. 
11. Kolyan Ray, and Johannes Schmidt-Hieber, The Le Cam distance between density estimation, Poisson processes and Gaussian white noise. arXiv preprint arXiv:1608.01824 (2016). 

(Warning: These materials may be subject to lots of typos and errors. We are grateful if you could spot errors and leave suggestions in the comments, or contact the author at yjhan@stanford.edu.) 

This lecture continues the introduction of information-theoretic lower bounds without formally developing tools. The emphasis of this lecture is that, the dependence of the fundamental limits on the problem structure may be very subtle, where the results may change significantly even with tiny changes in the problem setting. Hence, one should be very careful when applying some known lower bounds to similar problems, and it is vital to fully understand the specific problem structure. We will use a specific example of communication complexity in the theoretical computer science literatue to illustrate this phenomenon. 

1. Equality Evaluation: Deterministic Communication Complexity 

Alice and Bob hold vectors respectively, and they would like to check whether or not. However, they live very far from each other, and some limited resources of communication are available. What is the minimum number of communication bits to perform this task reliably, in the sense that they always find the correct answer for any pairs ? In other words, what is the deterministic communication complexity of the distributed computing problem for the equality function ? 

To answer this question, we need to formally define all possible communication protocols. Here we define a general class of blackboard communication protocols. 

Definition 1 (Blackboard Communication Protocol) A blackboard communication protocol over domain with range is a binary tree where each internal node is labeled by a function or by a function , and each leaf is labeled by an element .

The value of the protocol on input is the label of the leaf reached by starting from the root and walking on the tree using the following rule: at each internal node labeled by , walk left if and right if ; at each internal node labeled by , walk left if and right if . The cost of the protocol is the height of the tree. 

Intuitively speaking, there is a blackboard in front of both Alice and Bob in a blackboard communication protocol on which they can write binary bits, and this process continues sequentially where later bits can depend on the entire history. The formal definition above simply uses a binary tree to keep track of the history, and uses functions to illustrate who will be writing on the blackboard at stage . The communication cost of a given protocol is simply the maximum length of the message written on the blackboard, where the maximum is taken over all possible input pairs . 

Now the question we are asking is: among all blackboard communication protocols which always give the correct evaluation of the equality function, what is the minimum communication cost? This is also known as the deterministic communication complexity, where “deterministic” here means zero-error. 

To prove a lower bound on the deterministic complexity, we need to make the following key observation: 

Lemma 2 (Copy-paste Property) If a blackboard communication protocol arrives at the same leaf node on both inputs and , then on input the protocol also arrives at . 

Proof: For each internal nodes labeled by on the path from the root to , the condition ensures that . Similarly, if the internal node is labeled by . Then the result is immediate.  

The above copy-paste property shows the following limitation of any blackboard communication protocols: the set of all input pairs arriving at any leaf node forms a rectangle, i.e., takes the form of . Hence, if the value of the function to be computed is not a constant on large rectangles, each leaf node will need to take care of small rectangles and more leaves are required. This is the key insight of the following theorem. 

Theorem 3 (Log-rank Inequality) Let be a binary matrix defined as for all . Then the deterministic communication complexity of computing is at least , where the linear rank is understood over . 

Proof: For any leaf node which outputs , define . Then clearly . By the sub-additivity of rank, we have 

However, by Lemma 2, we have for any leaf, so inequality (1) implies that the number of leaf nodes is at least , and we are done.

Applying Theorem 3 to the equality function, the matrix is a identity matrix, and therefore the deterministic communication complexity is at least . This is essentially tight: Alice can communicate the entire vector to Bob using bits and Bob then sends the 1-bit evaluation of the equality function back to Alice. Hence, the deterministic communication complexity of equality evaluation is . 

2. Equality Evaluation: Randomized Private-coin Communication Complexity 

Next we consider a slight variant of the previous problem: what is the communication complexity if Alice and Bob can tolerate some maximum probability of error on all inputs? This quantity is called the randomized communication complexity. Here to introduce randomness, we assume that both Alice and Bob have access to some (private, not shared) random number generators. We also assume that is a small constant (say, ) and suppress the dependence of the communication complexity on . 

A striking result is that, if we allow some small probability of error (even of the order ), the randomized communication complexity drops from to . Here is a communication protocol: by Bertrand’s postulate there exists some prime number . Alice chooses such a and , evaluates the polynomial 

and sends to Bob using bits, where . Bob then evaluates in (2) and outputs . Clearly, if then Bob always outputs correctly. If , the map is a non-zero polynomial with degree at most , so it has at most zeros in . Consequently, Bob makes mistakes with probability at most for any .

The previous upper bound shows that Theorem 3 no longer holds for the randomized communication complexity. In fact, a careful inspection of the proof shows that the zero-error property is crucial for Theorem 3 to hold. However, we may still perform a deterministic simulation of any randomized protocol and reduce to the previous case. 

Theorem 4 Let and be the deterministic and randomized private-coin communication complexity of computing , respectively. Then

Proof: Given a randomized protocol, Alice can transmit the probabilities of arriving at all leaf nodes based on her input . Given these probabilities, Bob can privately evaluate the probabilities of arriving at each leaf based on the inputs (which is made possible by the product law of independent events thanks to the private-coin assumption). Then Bob sums up probabilities for leaf nodes which output and , respectively, and takes the majority vote. Since the error probability of the randomized protocol is at most , the final output given by the majority vote is always correct. The proof of (3) is completed by noting that these probabilities sent by Alice can be made within precision without hurting the majority vote.  

Applying Theorem 4 to the equality function , we immediately obtain that . Hence, the randomized private-coin communication complexity of equality evaluation is . 

3. Equality Evaluation: Randomized Public-coin Communication Complexity 

We ask again the same question in the previous section, but now Alice and Bob have shared randomness. Careful readers may have noticed a subtle point used in the proof of Theorem 4, i.e., the identity for events given by independent private randomness. Hence, the lower bound does not directly apply to the public-coin scenario, and the public-coin protocols may perform much better. This is indeed the case – the randomized public-coin communication complexity is actually . 

There is nothing to prove for the lower bound. For the upper bound, here is a simple procotol: both Alice and Bob draw (the same collection of) independent vectors . Then Alice sends an -bit vector to Bob, and Bob claims that if and only if for all . Clearly, this protocol errs with probability at most on all inputs. Hence, the randomized public-coin communication complexity of equality evaluation is . 

4. Equality Evalution: Randomized One-round Private-coin Communication Complexity 

Now we consider a final variant of the distributed equality evaluation problem, where we assume a randomized private-coin protocol but restrict the protocol to be only one-round. Recall that the previous blackboard communication protocol allows for multiple rounds of interaction, i.e., Alice may provide feedbacks to the messages transmitted by Bob, and vice versa. In the one-round scenario, Alice and Bob can only send -bit messages once to a central referee, and the target is to minimize the communication cost while controlling the maximum error probability below . Then what is the communication complexity in this scenario? 

Surprisingly, the communication complexity is , which is different from all previous ones. We first prove this lower bound. Notice that the one-round protocol has a more concise representation than a binary tree, i.e., any randomized strategy of Alice or Bob may be written as stochastic mappings from to . In particular, the copy-paste property in Lemma 2 becomes insufficient for our purposes. Let be the transition matrices of the stochastic mappings of Alice and Bob, respectively, and be the matrix with being the probability that the referee outputs given messages . Now denotes the probability of outputting on inputs , the correctness property ensures that 

where denotes the identity matrix, and denotes the norm of vectors. Hence, (4) implies that is an approximate non-negative matrix factorization of the identity matrix, and is the approximate non-negative rank of the identity matrix. The following result in linear algebra provides a lower bound on . 

Theorem 5 Let . If there exist stochastic matrices and a non-negative matrix such that , then

The proof of Theorem 5 is quite involved, and we refer interested readers to the reference cited in bibliographic notes. Now is an immediate consequence of (4) and Theorem 5. 

To show the upper bound , the idea is to simulate a randomized protocol by deterministic ones. Recall that in the previous section, there is a randomized public-coin protocol which requires bits of communication. Let be independent deterministic realizations of the randomized protocol with maximum error probability , then by Hoeffding’s inequality, for any fixed input we have 

Hence, by (5) and the union bound over possible inputs, for fixed we may simply choose such that the average probability of error of deterministic protocols on each inputs is at most . 

Now the private-coin protocol is as follows: put the above deterministic protocols in a matrix. Alice draws , runs all protocols in -th row and sends all outputs to the referee (together with ). Similarly, Bob draws and runs all protocols in -th column. The central referee simply looks at the protocol at the -th entry, whose probability of error is exactly the average probability of error of these deterministic protocols, which is at most . Meanwhile, the communication complexity of this protocol is , as desired. 

5. Bibliographic Notes 

Communication complexity is a central topic in theoretical computer science. The blackboard communication protocol is proposed by Yao in 1979, where some central tools (including Theorems 3 and 4) are available in the excellent book by Kushilevitz and Nisan (1996). The proof of Theorem 5 is given by Newman and Szegedy (1996), and the simulation idea is due to Newman (1991). 

1. Andrew Chi-Chih Yao, Some complexity questions related to distributive computing (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209–213. ACM, 1979. 
2. Eyal Kushilevitz and Noam Nisan, Communication complexity. Cambridge University Press. 1996. 
3. Ilan Newman and Mario Szegedy, Public vs private coin flips in one round communication games, In Proceedings of the 28th annual ACM symposium on Theory of computing, pages 561–570. ACM, 1996. 
4. Ilan Newman, Private vs. common random bits in communication complexity. Information processing letters 39.2 (1991): 67–71. 

(Warning: These materials may be subject to lots of typos and errors. We are grateful if you could spot errors and leave suggestions in the comments, or contact the author at yjhan@stanford.edu.) 

1. Overview 

Most scientific research are devoted to developing new tools or findings for challenging problems arising in practice, which help to provide explicit solutions to real problems. These works are typically called constructive, and characterize tasks which are possible to accomplish. However, there is also another line of work which focuses on the other side, i.e., provides fundamental limits on certain tasks. In other words, these works are mostly non-constructive and illustrate targets which are impossible to achieve. Such results are also useful for a number of reasons; we may certify the fundemental limits and optimality of some procedures so that it becomes unnecessary to look for better ones, we may understand the limitations of the current framework, and we may compute the amount of resources necessary to complete certain tasks. 

Among different types of fundamental limits (or converse in information theory, lower bounds broadly used in a number of fields), throughout these lectures we will be interested in so-called information-theoretic ones. When it comes to the information-theoretic lower bounds, typically one makes observations (either passively or actively) subject to some prescribed rules and argues that certain tasks cannot be accomplished using any tool solely based on these observations. To show these impossibility results, one argues through the line that the amount of information contained in these observations is insufficient to perform these tasks. Therefore, the limited-information structure is of utmost importance in the previous arguments, and the structure occurs in a number of fields including statistics, machine learning, optimization, reinforcement learning, to name a few; e.g., a given size of samples to perform inference, a given amount of training data to learn a statistical model, a given number of gradient evaluations to optimize a convex function, a given round of adaptivity to search for a good policy, etc. 

These lectures are devoted to providing an overview of (classical and modern) tools to establish information-theoretic lower bounds. We will neither be restricted to certain problems (e.g., statistical inference, optimization, bandit problems), nor restrict ourselves to tools in information theory. Instead, we will try to present an extensive set of tools/ideas which are suitable for different problem structures, followed by numerous interdisplinary examples. We will see that certain tools/ideas can be applied to many seemingly unrelated problems. 

2. Usefulness of Lower Bounds 

We ask the following question: why do we care about lower bounds? We remark that the usefulness of lower bounds is not restricted to providing fundamental limits and telling people which are impossible. In fact, the power of understanding lower bounds lies more on the upper bound in the sense that it helps us to understand the problem structure better, including figuring out the most difficult part of the problem and the most essential part of information which should be made full use of. In other words, the lower bounds are interwined with the upper bounds, and should be in no means treated as an independent component. We elaborate on this point via the following examples from puzzle games. 

2.1. Example I: Card Guessing Game 

There is a magic show as follows: there is a -card deck thoroughly shuffled by the audience. Alice draws cards from the top of the deck and reveals of them to Bob one after one, and then Bob can always correctly guess the remaining card in Alice’s hand. How can Alice and Bob achieve that? 

Instead of proposing an explicit strategy of Alice and Bob, let us look at the information-theoretic limit of this game first. Suppose the deck consists of cards, what are the possible values of such that such a strategy still exists? To prove such a bound, we need to understand what are the possible strategies. From Alice’s side, her strategy is simply a mapping from unordered -tuples to an ordered -tuple, with an additional restriction that for any unordered -tuples . From Bob’s side, his strategy is another mapping from ordered -tuples to a specific card in . Finally, the correcntess of Bob’s guessing corresponds to 

An equivalent way to state (1) is that, Bob can recover all cards after observing the first ordered 4 cards; write for this strategy. Now we come to our information-theoretic observation: do ordered -tuples contain enough information to recover any unordered -tuples? Here we will quantify the information as cardinality: mathematically speaking, the mapping must be surjective, so . In other words, 

Hence, this magic show will fail for any deck with more than cards. The next question is that, is achievable? Now we are seeking an upper bound, but the previous lower bound still helps – the equality in (2) holds implies that must be a bijection! Keeping the bijective nature of in mind, it then becomes not too hard to propose the following strategy which works. Label all cards by , and suppose the chosen cards be . Alice computes the sum , keeps and reveals all others to Bob. Let , then for Bob to decode , he only needs to solve the following equation: 

where we define . It is easy to show that (3) always admits solutions in , and any solution can be encoded using different permutations of the revealed cards . 

2.2. Example II: Coin Flipping Game 

Now Alice and Bob play another game cooperatively: consider coins on the table each of which may be head or tail, and the initial state is unknown to both Alice and Bob. The audience tells a number in to Alice, and she comes to the table, looks at all coins and flips one of them. Bob then comes to the table and tells the number told by the audience correctly. The question is: for which values of can they come up with such a strategy? 

To answer this question, again we need to understand the structure of all strategies. Let be the initial state of the coins, which may be arbitrary. We may also identify as vertices of an -dimensional hypercube. Let be the number given by the audience. Alice’s strategy is then a mapping , choosing a coin to flip (where denotes the -th canonical vector) based on her knowledge. Then Bob’s strategy is a mapping , and the correctness condition implies that 

It is clear from (4) that the map for any must be injective. By cardinality arguments, this map is further bijective. Now the problem structure becomes more transparent: for each , let be the states where Bob will claim . We call these vertices in the hypercube have -th color. Then (4) states that, for each vertex , its different neighbors must have different colors. The converse is also true: if there exists such a coloring scheme, then we may find such that (4) holds. 

Now when does such a coloring scheme exist? A simple idea is that, the number of vertices with any color should be the same by double counting arguments. Hence, we must have , which implies that must be a power of . Based on the coloring intuition given by the lower bound, the strategy also becomes simple: consider any finite Abelian group with elements, we identify colors as elements of and let have color 

It is straightforward to verify that (4) holds if and only if has characteristic , i.e., for any . By algebra, such an Abelian group exists if and only if is a power of , e.g., when (necessity can be shown via taking quotients repeatedly). Hence, such a strategy exists if and only if is a power of . 

2.3. Example III: Hat Guessing Game 

Now we look at a hat-guessing game with a more complicated information structure. There are people who are sitting together, each of whom wears a hat of color red or blue, independently with probability . They cannot talk to each other, and they can see the color of all hats except for their own. Now each of them simultaneously chooses to guess the color of his own hat, or chooses to pass. They win if at least one person guesses the color, and all guesses are correct. What is their optimal winning probability of this game? 

The answer to this question is , which is shocking at the first appearance because it greatly outperforms achieved by the naive guessing scheme where only the first person guesses. To understand this improvement, we first think about the fundamental limit of this problem. Let be the sequence of hat colors, and is called success if they win under state , and failure if fail. Clearly, at each success state , there must be some person who makes the correct guess. However, since he cannot see , he will make the same guess even if is flipped, and this guess becomes wrong in the new state. This argument seems to suggest that the winning probability is not improvable, for each success state corresponds to a failure state and therefore at most consistutes half of the states. However, this intuition is wrong since multiple success states may correspond to the same failure state. 

Mathematically speaking, let be the success states and be the failure states. By the previous argument, there exists a map which only flips one coordinate. Since there are at most coordinates which can be flipped, we have for each . Consequently, , and the winning probability is 

The above lower bound argument shows that, in order to achieve the optimal winning probability, we must have for any . Consequently, in any failure state, it must be the case where everyone makes wrong guesses. This crucial observation motivates the following strategy: identify people as elements of . Each person computes the sums of the people indices with red and blue hats, respectively. If , he claims blue; if , he claims red; otherwise he passes. Then it becomes obvious that a failure occurs if and only if the indices of people with red hats sum into , whose probability is . 

3. Bibliographic Notes 

There are tons of information-theoretic analysis used to solve puzzles. We recommend two books if the readers would like to learn more about funny puzzles: 

1. Peter Winkler, Mathematical puzzles: a connoisseur’s collection. AK Peters/CRC Press, 2003. 
2. Jiri Matousek, Thirty-three miniatures: Mathematical and Algorithmic applications of Linear Algebra. Providence, RI: American Mathematical Society, 2010.