Questions tagged [hoeffdings-inequality]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
123 views

How to prove error of ensemble model by using the Hoeffding's inequality?

Under Binary classification situation, error between function $f$ and basic learner(classifier) $h_i(x)$ is $$P(h_i(x)≠f(x))=\mathcal{E}.$$ It is assumed that $T$ basic classifiers are combined by a ...
3 votes
1 answer
147 views

Proof of corollary of Hoeffding's inequality

I need to proof a corollary of Hoeffding's inequality, and since I'm not used to doing proofs I really don't know where to begin. Hoeffding's inequality: Let $X_1,...,X_n$ be independent real-valued ...
1 vote
1 answer
34 views

Dose McDiarmid's inequality holds in hilbert space,specially or in $L^2$ space?

Consider McDiarmid's inequality in Hilbert space, or can we extend McDiarmid's inequality to functional data analysis with the complete observed data?
  • 11
5 votes
1 answer
343 views

Taylor expansion in Hoeffding's Lemma proof

Hoeffding's Lemma proof uses Taylor expansion with this statement: From Taylor's theorem, for some $ 0\leq \theta \leq 1$ $ L(h) = L(0) + h L'(0) + \frac{1}{2} h^2 L''(h\theta) \leq \frac{1}{8}h^2 $ ...
  • 151
3 votes
1 answer
139 views

Why does "Hoeffding's bound greatly overestimates the probability of large deviations for distributions of small variance"?

I've read in a paper using Hoeffding's inequality to derive a bound on the probability of the difference of means of two samples being larger than a threshold that "Hoeffding's bound greatly ...
  • 155
2 votes
1 answer
136 views

Is my way of deriving a statistical test from Hoeffding's inequality correct?

I'm trying to deduce from samples of observations from two finite sets of random variables $X_{1}, ..., X_{n}$ and $Y_{1}, ..., Y_{m}$ that the expected values of the average of those random variables ...
  • 155
1 vote
0 answers
20 views

$L^2$ convergence of inverse

Let $h$ be some bounded non-negative function. Assume that some random quantity $\mu^N (h)$ be some random quantity with almost sure limit $\mu(h) > 0$. For instance we could have $\mu^N(h) = N^{-1}...
  • 141
0 votes
0 answers
74 views

Sample size for using Hoeffding inquality

I am stuck on this problem: I need to find the sample size for an experiment with Hoeffding's inequality. I want to know how many people I should sample so that the estimate differs from the true ...
2 votes
1 answer
47 views

Hoeffding's inequality implementation wrong?

I've learned Hoeffding'e inequality from Wikipedia, and to check if I understand correctly the formula, I refer to this lecture for exact example that I can solve. But why do I think I get a different ...
  • 83
4 votes
1 answer
234 views

Hoeffding type concentration result for the inverse of a sum of iid random variables

Consider a collection of $n$ i.i.d. Bernoulli random variables $\{ X_i \}_{i=1}^{n}$ with $\mathbb{E}[X_i] = \mu$. Then, if $\hat{\mu}$ is the mean of the $n$ random variables, i.e. if, $$\hat{\mu} = \...
  • 155
1 vote
1 answer
64 views

Normal approximation and Hoeffding bound

Hoeffding bound for any $\epsilon>0$ is: $$P_F(|\bar{X}_n-\mu(F)|\geq \epsilon)\leq 2 \exp\{-\frac{n\epsilon^2}{2}\}=h(\sqrt{n}\epsilon)$$ wherever $|X|<1$. Now I want to have a comparison ...
  • 581
1 vote
0 answers
75 views

Hoeffding's inequality for high dimensional data, particularly when p>>n

In one dimension, if $X_i\in\left[a_i,b_i\right]$, $i\in\left\{1,\ldots{},n\right\}$, are i.i.d. then \begin{align*} P\left(|\bar{X}-E\left[\bar{X}\right]|\geq{}t\right)\leq{}2\exp\left(-\frac{2n^2t^2}...
2 votes
1 answer
240 views

Probability that a Linear Combination of Dirichlet Random Variables is a Distribution

I've been putting a lot of thought on this problem, but it seems I ran out of ideas. Any help would be appreciated! Suppose we generate two probability vectors $\boldsymbol{\theta}_1, \boldsymbol{\...
  • 80
0 votes
0 answers
51 views

Proof (requested) of sample sizes in multivariate distribution

My team has been asked to build a predictive model. We have a very limited dataset, but using a number of rationalizations about bounds on the data and the current behavior (54 data points) I have ...
0 votes
1 answer
106 views

Linear combination of Random Variables less than Zero and Hoeffding's inequality

Let $X_1$ and $X_2$ be Uniform Random Variables and set $$X = aX_1 + bX_2, $$ with $a \geq 0$ and $b \leq 0$. I'd like to bound $P(X \leq 0)$ using Hoeffding's inequality. How do I do that? P.S.: I ...
  • 80
0 votes
0 answers
53 views

Hoeffding inequality

I came across these questions online : As known, Learning relies that the Hoeffding inequality holds. In what way? Can you give an example where it doesn’t hold? I know what is the meaning of ...
  • 27
3 votes
0 answers
40 views

Prove or disprove a concentration result of the norm of high dimensional random vector

Suppose that $X = (X_1,X_2,\cdots ,X_n)$ is a vector, where $X_i, i=1,2,\cdots ,n$ are independent and sub-gaussian random variables satisfying $\mathbb{E}[X_i^2] = 1$. Prove or disprove the following ...
  • 193
0 votes
0 answers
309 views

Symmetrization in Proof of Hoeffding's Lemma

This alternative proof of a slightly weaker version of Hoeffding's Lemma features in Stanford's CS229 course notes. What's notable about this proof is its use of symmetrization. However, I find this ...
  • 161
2 votes
1 answer
437 views

Expectation of (sum subtract the expectation of sum)

Let's say we have random variables $\mathbf{X}$, and we have $P(\mathbf{X}\in [a, b])=1$, we have $\mathbf{S}_n = \mathbf{X}_1 + \mathbf{X}_2, +\dots + \mathbf{X}_n$. If $\mathbf{X}_1, \mathbf{X}_2, ...
user avatar
2 votes
1 answer
82 views

Bounding the structural-risk-minimization (using Hoeffding's inequality twice)

tl;dr: The main question is if I use an inequality that is true with a certain probability (confidence) twice, do I get the same confidence? Original: I've got the following exercise: Where $e_p(h)...
0 votes
0 answers
111 views

Using Hoeffding's inequality on sum of uniform variables

I have the following problem: $X_1,...,X_n$ are i.i.d. $\sim U(-3,5)$ continuous uniform variables in the support between -3 and 5. $S := X_1 + ... + X_n$. I need to use Hoeffding's inequality to ...
2 votes
1 answer
499 views

Sample size for estimating success probability of a Bernoulli process

Suppose an AI player in a game can either win or lose. I wish to estimate the win ratio of this player. My question is, how many samples (games) needed in order to get an error smaller than 1%? A ...
  • 316