Sharp Matrix Empirical Bernstein Inequalities
We present two sharp, closed-form empirical Bernstein inequalities for symmetric random matrices with bounded eigenvalues. By sharp, we mean that both inequalities adapt to the unknown variance in a tight manner: the deviation captured by the first-order $1/\sqrt{n}$ term asymptotically matches the matrix Bernstein inequality exactly, including constants, the latter requiring knowledge of the variance. Our first inequality holds for the sample mean of independent matrices, and our second inequality holds for a mean estimator under martingale dependence at stopping times.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Concentration for matrix martingales in continuous time and microscopic activity of social networks
This paper gives new concentration inequalities for the spectral norm of a wide class of matrix martingales in continuous time. These results extend previously established Freedman and Bernstein inequalities for series o…
Empirical Bernstein Inequalities for U-Statistics
We present original empirical Bernstein inequalities for U-statistics with bounded symmetric kernels q. They are expressed with respect to empirical estimates of either the variance of q or the conditional variance that …
Concentration Inequalities for Exchangeable Tensors and Matrix-valued Data
We study concentration inequalities for structured weighted sums of random data, including (i) tensor inner products and (ii) sequential matrix sums. We are interested in tail bounds and concentration inequalities for th…
Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables
We present a new concentration of measure inequality for sums of independent bounded random variables, which we name a split-kl inequality. The inequality is particularly well-suited for ternary random variables, which n…
Open-Ended Question AnsweringImproved Analysis of UCRL2 with Empirical Bernstein Inequality
We consider the problem of exploration-exploitation in communicating Markov Decision Processes. We provide an analysis of UCRL2 with Empirical Bernstein inequalities (UCRL2B). For any MDP with $S$ states, $A$ actions, $\…