Lower Performance Bounds In other modules, estimators/predictors are analyzed, in order to obtain upper bounds on their performance. These bounds are of the form: min f ∈ F E [ d ( f ^ n , f ) ] ≤ C n - γ where γ>0. We would like to know if these bounds are tight, in the sense that there is no other estimator that is significantly better. To answer this, we need lower bounds like inf f ^ n sup f ∈ F E [ d ( f ^ n , f ) ] ≥ c n - γ We assume we have the following ingredients: *Class of models, F⊆S. F is a class of models containing the “true" model and is a subset of some bigger class S. E.g. F could be the class of Lipschitz density functions or distributions PXY satisfying the box-counting condition. *An observation model, Pf, indexed by f∈F. Pf denotes the distribution of the data under model f. E.g. in regression and classification, this is the distribution of Z=(X1,Y1,⋯,Xn,Yn)⊆Z. We will assume that Pf is a probability measure on the measurable space (Z,B). *A performance metric d(.,.).≥0. If you have a model estimate f^n, then the performance of that model estimate relative to the true model f is d(f^n,f). E.g. Regression:d(f^n,f)=||f^n-f||2=∫(f^n(x)-f(x))2dx1/2Classification:d(f^n,f)=R(G^n)-R*=∫G^nΔG*|2η(x)-1|dPX(x) As before, we are interested in the risk of a learning rule, in particular the maximal risk given as: sup f ∈ F E f [ d ( f ^ n , f ) ] = sup f ∈ F ∫ d ( f ^ n ( Z ) , f ) d P f ( Z ) where f^n is a function of the observations Z and Ef denotes the expectation with respect to Pf. The main goal is to get results of the form R n * = Δ inf f ^ n sup f ∈ F E [ d ( f ^ n , f ) ] ≥ c s n where c>0 and sn→0 as n→∞. The inf is taken over all estimators, i.e. all measurable functions f^n:Z→S. Suppose we have shown that lim inf n → ∞ s n - 1 R n * ≥ c > 0 (A lower bound) and also that for a particular estimator f¯n lim sup n → ∞ s n - 1 sup f ∈ F E f [ d ( f ¯ n , f ) ] ≤ C ⟹ lim sup n → ∞ s n - 1 R n * ≤ C , We say that sn is the optimal rate of convergence for this problem and that f¯n attains that rate. Note: Two rates of convergence Ψn and Ψn' are equivalent, i.e. Ψn≡Ψn' iff 0 < lim inf n → ∞ Ψ n Ψ n ' ≤ lim sup n → ∞ Ψ n Ψ n ' < ∞

General Reduction Scheme Instead of directly bounding the expected performance, we are going to prove stronger probability bounds of the form inf f ^ n sup f ∈ F P f ( d ( f ^ n , f ) ≥ s n ) ≥ c > 0 These bounds can be readily converted to expected performance bounds using Markov's inequality: P f ( d ( f ^ n , f ) ≥ s n ) ≤ E f [ d ( f ^ n , f ) ] s n Therefore it follows: inf f ^ n sup f ∈ F E f [ d ( f ^ n , f ) ] ≥ inf f ^ n sup f ∈ F s n P f ( d ( f ^ n , f ) ≥ s n ) ≥ c s n

First Reduction Step Reduce the original problem to an easier one by replacing the larger class F with a smaller finite class {f0,⋯,fM}⊆F. Observe that inf f ^ n sup f ∈ F P f ( d ( f ^ n , f ) ≥ s n ) ≥ inf f ^ n sup f ∈ { f 0 , ⋯ , f M } P f ( d ( f ^ n , f ) ≥ s n ) The key idea is to choose a finite collection of models such that the resulting problem is as hard as the original, otherwise the lower bound will not be tight.

Second Reduction Step Next, we reduce the problem to a hypotheses test. Ideally, we would like to have something like inf f ^ n sup f ∈ F P f ( d ( f ^ n , f ) ≥ s n ) ≥ inf f ^ n sup j ∈ { 0 , ⋯ , M } P f j ( h ^ n ( Z ) ≠ j ) The inf is over all measurable test functions h ^ n : Z → { 0 , ⋯ , M } and Pfj(h^n(Z)≠j) denotes the probability that after observing the data, the test infers the wrong hypothesis. This might not always be true or easy to show, but in certain scenarios it can be done. Suppose d(.,.) is a semi-distance, i.e. it satisfies (i)d(f,g)=d(g,f)≥0 (Symmetric) (ii) d ( f , f ) = 0 (iii)d(f,g)≤d(h,f)+d(h,g) (Triangle inequality) E.g. with f,g:Rd→R,d(f,g)=Δ||f-g||2. Lemma 1 Suppose d(.,.) is a semi-distance. Also suppose that we have constructed f0,⋯,fM s.t. d(fj,fk)≥2sn, ∀j≠k. Take any estimator f^n and define the test: Ψ*∘f^n:Z→{0,⋯,M} as Ψ * ( f ^ n ) = arg min j d ( f ^ n , f j ) Then Ψ*(f^n)≠j, implies d(f^n,fj)≥sn. Suppose Ψ*(f^n)≠j⟺∃k≠j:d(f^n,fk)≤d(f^n,fj). Now 2 s n ≤ d ( f j , f k ) ≤ d ( f ^ n , f j ) + d ( f ^ n , f k ) ≤ 2 d ( f ^ n , f j ) ⟹ d ( f ^ n , f j ) ≥ s n The previous lemma implies that P f j ( d ( f ^ n , f j ) ≥ s n ) ≥ P f j ( Ψ * ( f ^ n ) ≠ j ) Therefore, inf f ^ n sup f ∈ F P f j ( d ( f ^ n , f j ) ≥ s n ) ≥ inf f ^ n max f ∈ { f 0 , ⋯ , f M } P f j ( d ( f ^ n , f j ) ≥ s n ) ≥ inf f ^ n max j ∈ { 0 , ⋯ , M } P f j ( Ψ * ( f ^ n ) ≠ j ) ≥ inf h ^ n max j ∈ { 0 , ⋯ , M } P j ( h ^ n ≠ j ) = Δ P e , M The third step follows since we are replacing the class of tests defined by Ψ*(f^n) by a larger class of ALL possible tests h^n, and hence the inf taken over the larger class is smaller. Now our goal throughout is going to be to find lower bounds for Pe,M. So we need to construct f0,⋯,fM s.t. d(fj,fk)≥2sn, j≠k and Pe,M≥c>0. Observe that this requires careful construction since the first condition necessitates that fj and fk are far from each other, while the second condition requires that fj and fk are close enough so that it is harder to distinguish them based on a given sample of data, and hence the prob of error Pe,M is bounded away from 0. We now try to lower bound the prob of error Pe,M. We first consider the case M=1, corresponding to binary hypothesis testing. M = 1: Let P0 and P1 denote the two probability measures, i.e. distributions of the data under models 0 and 1. Clearly if P0 and P1 are very “close", then it is hard to distinguish the two hypotheses, and so Pe,1 is large. A natural measure between probability measures is the total variation , defined as: V ( P 0 , P 1 ) = sup A | P 0 ( A ) - P 1 ( A ) | = sup A | ∫ A p 0 ( Z ) - p 1 ( Z ) d ν ( Z ) | where p0 and p1 are the densities of P0 and P1 with respect to a common dominating measure ν and A is any subset of the domain. We will lower bound the prob of error Pe,1 using the total variation distance. But first, we establish the following lemma. Scheffe's lemma V ( P 0 , P 1 ) = 1 2 ∫ | p 0 ( Z ) - p 1 ( Z ) | d ν ( Z ) = 1 2 ∫ | p 0 - p 1 | = 1 - ∫ min ( p 0 , p 1 ) Recall the definition of the total variation distance: V ( P 0 , P 1 ) = sup A | ∫ A p 0 - p 1 | Observe that the set A maximizing the right hand side is given by either {Z∈Z:p0(Z)≥p1(Z)} or {Z∈Z:p1(Z)≥p0(Z)}. Let us pick A0={Z∈Z:p0(Z)≥p1(Z)}. Then V ( P 0 , P 1 ) = ∫ A 0 p 0 - p 1 = - ∫ A 0 c p 0 - p 1 = 1 2 ∫ | p 0 - p 1 | For the second part, notice that p 0 ( Z ) - min ( p 0 ( Z ) , p 1 ( Z ) ) = 0 if p 0 ( Z ) ≤ p 1 ( Z ) p 0 ( Z ) - p 1 ( Z ) if p 0 ( Z ) ≥ p 1 ( Z ) Now consider 1 - ∫ min ( p 0 , p 1 ) = ∫ p 0 ( Z ) - min ( p 0 ( Z ) , p 1 ( Z ) ) = ∫ A 0 p 0 ( Z ) - p 1 ( Z ) d ν ( Z ) = V ( P 0 , P 1 ) We are now ready to tackle the lower bound on Pe,1. In this case, we consider all tests h^n(Z):Z→{0,1}. Equivalently, we can define h^n(Z)=1A(Z), where A is any subset of the domain. P e , 1 = inf h ^ n max j ∈ { 0 , ⋯ , M } P j ( h ^ n ≠ j ) ≥ inf h ^ n 1 2 P 0 ( h ^ n ≠ 0 ) + P 1 ( h ^ n ≠ 1 ) = 1 2 inf A P 0 ( 1 A ( Z ) ≠ 0 ) + P 1 ( 1 A ( Z ) ≠ 1 ) = 1 2 inf A P 0 ( A ) + P 1 ( A c ) = 1 2 inf A 1 - ( P 1 ( A ) - P 0 ( A ) ) = 1 2 ( 1 - V ( P 0 , P 1 ) ) So if P0 is close to P1, then V(P0,P1) is small and the probability of error Pe,1 is large. This is interesting, but unfortunately, it is hard to work with total variation, especially for multivariate distributions. Bounds involving the Kullback-Leibler divergence are much more convenient. K ( P 1 | | P 0 ) = ∫ log p 1 ( Z ) p 0 ( Z ) p 1 ( Z ) d ν ( Z ) = ∫ log p 1 p 0 p 1 The following Lemma relates total variation, affinity and KL divergence. Lemma 2 1-V(P0,P1)≥12A2(P0,P1)≥12exp(-K(P1||P0)) For the first inequality, A 2 ( P 0 , P 1 ) = ∫ p 0 p 1 2 = ∫ min ( p 0 , p 1 ) max ( p 0 , p 1 ) 2 = ∫ min ( p 0 , p 1 ) max ( p 0 , p 1 ) 2 ≤ ∫ min ( p 0 , p 1 ) ∫ max ( p 0 , p 1 ) by Cauchy-Schwarz inequality = ∫ min ( p 0 , p 1 ) 2 - ∫ min ( p 0 , p 1 ) ∵ ∫ min ( p 0 , p 1 ) + ∫ max ( p 0 , p 1 ) = ∫ p 0 + ∫ p 1 = 2 ≤ 2 ∫ min ( p 0 , p 1 ) = 2 ( 1 - V ( P 0 , P 1 ) ) For the second inequality, A 2 ( P 0 , P 1 ) = ∫ p 0 p 1 2 = exp log ∫ p 0 p 1 2 = exp 2 log ∫ p 0 p 1 = exp 2 log ∫ p 0 p 1 p 1 ≥ exp 2 ∫ log p 0 p 1 p 1 by Jensen's inequality = exp - ∫ log p 1 p 0 p 1 = exp ( - K ( P 1 | | P 0 ) ) Putting everything together, we now have the following Theorem: Theorem 1 Let F be a class of models, and suppose we have observations Z distributed according to Pf, f∈F. Let d(f^n,f) be the performance measure of the estimator f^n(Z) relative to the true model f. Assume also d(.,.) is a semi-distance. Let f0,f1∈F be s.t. d(f0,f1)≥2sn. Then inf f ^ n sup f ∈ F P f ( d ( f ^ n , f ) ≥ s n ) ≥ inf f ^ n