3
$\begingroup$

Is there a version of Hoeffding's inequality for vector valued random variables?

This seems to be hard to find and I wonder why. I suppose it is difficult to show Hoeffding's lemma, since the proof for the inequality seems to translate relatively easy to a vector space.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
2
$\begingroup$

Concentration Inequalities for Bounded Random Vectors, by Xinjia Chen (2013):

We derive simple concentration inequalities for bounded random vectors, which generalize Hoeffding's inequalities for bounded scalar random variables. As applications, we apply the general results to multinomial and Dirichlet distributions to obtain multivariate concentration inequalities.

Improve this answer
$\endgroup$
3
  • 7
    $\begingroup$ What if I'm interested in bounding $\mathbb{P}\left[\left\|\sum_i^n X_i - \mu_i\right\| > \lambda\right]$ instead? $\endgroup$
    – Thomas Steinke
    Commented Mar 16, 2015 at 18:19
  • $\begingroup$ It's worth mentioning that the above is much less general than a first glance might imply. It gives you bounds $\vec{X}\geq \vec{z}$ (where $\vec{X}\geq\vec{z}$ means the partial-order induced by entry-wise comparisons), but the conditions on $\vec{z}$ are rather restrictive. Specifically, the $\lvert \vec{z}\rvert_1 = \mathbb{E}[\lvert \vec{X}\rvert_1]$, where each $z_i$ is a non-negative integer. I was unable to adapt the results in the paper for my required usage, involving Chernoff-type bounds on multinomial random variables. $\endgroup$
    – Mark Schultz-Wu
    Commented Apr 5, 2019 at 17:51
  • $\begingroup$ @Thomas this paper might help researchgate.net/publication/… $\endgroup$
    – PattuX
    Commented Mar 31, 2022 at 13:44
3
$\begingroup$

Here is one way to extend it using a simple union bound to control the deviation of every coordinate at once. You could imagine other ways to extend it, but ensuring that every coordinate is near the true value is already very strong.

For $X_1, ..., X_n \in [0,1]$ be iid from some distribution with mean $\mu$, Hoefdding says : $P ( | \bar{X} - \mu| > \epsilon) \leq 2\exp( - 2 n \epsilon^2) $.

Suppose we have iid vectors $Y_1, Y_2, \ldots, Y_n \in [0,1]^m$. For a vector $Z \in [0,1]^m$ let $Z(j)$ denote the $j$th coordinate. In particular, $(Y_k)(j)$ denotes the $jth$ coordinate of the $k$th vector in the sample.

Suppose $\mathbb{E}[Y_1(j)] = \mu_j$. We have $\mathbb{E}[Y](j) = \mathbb{E}[Y_1(j)]$ by linearity of expectation, and $\overline{Y}(j) = \overline {Y(j)}$ similarly, where the overline denotes the empirical mean.

We define the event that the $j$th coordinate of $\overline{Y}$ is far from the true mean of that coordinate: $A_j = \{ | \bar{Y}(j) - \mu_j| > \epsilon \}$. Hoeffding's tells us that $P(A_j) \leq 2\exp( - 2 n \epsilon^2) $.

We can bound the probability that any coordinate is $\epsilon$ away from the true mean of that coordinate by using the union bound. That is, $P ( \bigcup_{j = 1}^m A_j ) \leq \sum_{j = 1}^m P(A_j) \leq 2m \exp( -2n \epsilon^2)$.

This is useful as we only need to increase $n$ by adding $\log(m)/(2\epsilon^2)$ in order to eliminate the multiplier.

Improve this answer
$\endgroup$
1
$\begingroup$

As far as I know, currently, I have not found Hoeffding's inequality for vector-valued random variables. However, we can use Bernstein Inequality to describe how the concentration of the vectors sum. As indicated in 1, we have the following bound: enter image description here This bound is derived from 2 which is enter image description here

We can have a more generalized version of the Bernstein Inequality for matrices. You can refer to 3: enter image description here

1 Jonas Moritz Kohler. Sub-sampled Cubic Regularization for Non-convex optimization. 2017

2 David Gross. Recovering Low-Rank Matrices From Few Coefficients In Any Basis. 2010

3 Joel A. Tropp. An Introduction to Matrix Concentration. 2015

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .