On Some Extensions of Bernstein's Inequality for Self-adjoint Operators

By Stanislav Minsker. 2011

171 citations recorded by the source corpus.

We present some extensions of Bernstein's concentration inequality for random matrices. This inequality has become a useful and powerful tool for many problems in statistics, signal processing and theoretical computer science. The main feature of our bounds is that, unlike the majority of previous related results, they do not depend on the dimension $d$ of the ambient space. Instead, the dimension factor is replaced by the "effective rank" associated with the underlying distribution that is bounded from above by $d$. In particular, this makes an extension to the infinite-dimensional setting possible. Our inequalities refine earlier results in this direction obtained by D. Hsu, S. M. Kakade and T. Zhang.

Subfields: Applied Mathematics

How researchers see this paper

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

In Applied Mathematics

Citations in the corpus

On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “Then, Bernstein concentration inequalities for operators ( Minsker, 2011) can be used in a way similar to the work of Bach (2013); El Alaoui and Mahoney (2014) on column sampling, to provide a bound on all desired quantities.”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, background): “In particular, this does not yield operator-norm bounds for infinite-dimensional Hilbert-Schmidt operators, as in Minsker (2017).”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, methodology): “To obtain such bounds we make use of Theorem 2 in [18] and Bernstein’s inequality (see [26] for further references).”
On the Equivalence between Quadrature Rules and Random Features (2015, methodology): “Then, Bernstein concentration inequalities for operators (Minsker, 2011) can be used in a way similar to the work of Bach (2013); El Alaoui and Mahoney (2014) on column sampling.”
Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method (2018, methodology): “Our results recover, in particular, the classic uniform bound of Talagrand (1996) for Rademacher chaoses and the more recent uniform result of Adamczak (2015) which holds under certain rather strong assumptions on the distribution of X.”
Less is More: Nyström Computational Regularization (2015, background): “From a theoretical perspective, the effect of Nyström approaches has been primarily characterized considering the discrepancy between a given empirical kernel matrix and its subsampled version [13, 14, 15, 16, 17, 18, 19].”