Empirical Bernstein Confidence Bound

less than 1 minute read


A small note for a useful conclusion for giving concentration bound.

Theorem on Empirical Bernstein Confidence Bound

The assumption of bounded entries in matrix allows us to use exponential concentration inequalities and construct tight finite-sample confidence bounds. Based on the following empirical Bernstein inequality in Maurer and Pontil, some useful results might be obtained.

Theorem Let Z, Z1, …, Zn be i.i.d. random variables with values in [0, 1] and let δ > 0. Then with probability at least 1 − δ in the i.i.d. vector Z = (Z1, · · · , Zn) that

where Vn(Z) is the sample variance.

This theorem looks much useful and I am quite curious about its proof. For analysis on Stein lower bound, we might first obtain the confidence bound for entries in a matrix whose trace of inverse is closely related to our Stein lower bound.