Questions tagged [concentration-of-measure]
Use this tag for questions about the principle that a random variable that depends in a Lipschitz way on many independent variables (but not too much on any of them) is essentially constant.
335
questions
1
vote
1
answer
24
views
Speed of convergence of empirical probability mass function
I was wondering about the following situation: Suppose we have a random variable $X$ taking values in the finite set $\{1,2,\ldots,k\}$. Let the probability mass function be denoted by $f$.
Suppose we ...
- 939
3
votes
0
answers
48
views
Is recycling samples better than drawing fresh ones?
At a high level, I am wondering if in a sequential process it is better to reutilize samples even if these samples have been used to make past decisions.
Let me formalize my doubts in a toy example ...
- 352
1
vote
0
answers
28
views
Concentration probabilities for distributions with $\exp(-c t^\alpha)$ tails
I am trying to generalize the concentration inequalities for the sub-exponential and sub-gaussian distributions to a larger family with tail $\exp(-c t^\alpha)$ for arbitrary $\alpha > 0$. In ...
- 153
0
votes
0
answers
10
views
Lipshitz deviation inequality that implies Bernstein's inequality?
In Keith Ball's convex geometry notes, the author comments on the formal similarity of the following two results:
Theorem 1. (Bernstein's Inequality for Bernoulli Random Variables.)
Let $\varepsilon_1,...
- 319
2
votes
0
answers
26
views
Tail bounds for sub-Gaussian and sub-exponential distributions
Massart and Laurent (see [1], Lemma 1 on page 1325] give tail bounds for $\chi^2$ random variables.
A corollary of their bound is the following:
$$P\left[\frac{1}{k} X \leq 1- 2\sqrt{\frac{x}{k}} \...
- 698
1
vote
0
answers
65
views
How the second inequality stands?
Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and ...
- 323
1
vote
0
answers
36
views
Markov's inequality for uniformly bounded functions
Question: If $f$ and $g$ are two positive, increasing functions such that $f(t)\leq g(t)$ for all $t>0$ and $X$ is a positive random variable, then is it true that for all $t>0$,
$$\frac{\mathbb{...
- 332
11
votes
2
answers
183
views
Can we control the distance between the empirical and theoretical mean on the whole trajectory any better than using Hoeffding and a union bound?
Suppose $X,X_1,X_2,X_3\dots$ is a $\mathbb{P}$-i.i.d. family of $[-1,1]$-valued random variables with $\mathbb{E}[X] = 0$.
Hoeffding's inequality implies that
\begin{equation*}
\forall T \in \...
- 4,648
0
votes
1
answer
43
views
How to find the size of an ϵ-net of a vector space?
Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and ...
- 323
0
votes
0
answers
22
views
Hanson-Wright Inequality Lowering the Constant to Obtain a Factor of 2 Instead of 4
I'm reading the proof of Hanson-Wright Inequality from Rudelson & Vershynin's paper "Hanson-Wright inequality and sub-gaussian concentration". (https://arxiv.org/pdf/1306.2872.pdf)
I'm ...
- 73
0
votes
0
answers
31
views
Probability of failure in a multinomial experiment
Generalised version of Probability of failing to decode a biased die
Say we are given a biased die having a total of $N$ sides that shows up $M$ of its sides with a probability of $p$ and the rest of ...
0
votes
0
answers
24
views
in-probability bound for maximum of chi square distributions
Let $X_1, \dots, X_n$ be i.i.d. Chi square random variables with $d$ degrees of freedom, i.e. $X_1, \dots, X_n \stackrel{\text{i.i.d}}{\sim} \chi^2_d$. There is a nice bound (see Example 2.7 from the ...
- 2,147
3
votes
0
answers
38
views
Does there exist a uniform Monte-Carlo Approximation of certain function classes?
Given a measurable and bounded function $f:X \to \mathbb{R}$ on a metric-measure space $(X, d, \mathcal{P})$, we can approximate $\int_\chi f$ in terms of $N$ iid samples $X_1, \ldots, X_N \sim \...
- 167
1
vote
0
answers
33
views
Understanding the question in concentration of measure
I'm reading papers about concentration of measure. Could you check if my below understanding is correct?
Let $(E, d)$ be a metric space and $\mu$ a probability measure on the Borel $\sigma$-algebra ...
- 1,153
1
vote
0
answers
20
views
A quadratic equation gives linear-like behavior that contradict the relative minimum?
Refer to the below.
Is the red term obtained by plugging in the yellow term to the blue term? If not, how is it obtained?
If yes, consider the following: If we want to minimize the blue term, i.e. a ...
- 79
1
vote
1
answer
46
views
Sampling from equal-norm tight frame (Vershynin exercise 5.6.6)
I am struggling with Exercise 5.6.6 from Vershynin's "High-Dimensional Probability":
Consider an equal-norm tight frame $(u_i)_{i=1}^{N}$ in $\mathbb{R}^n$. State and prove a result that ...
- 239
1
vote
0
answers
17
views
Find the optimal value and minimiser for a function
I encounter this problem when reading the proof of Bernstein inequality for bounded random variables.
Consider the function $h(\lambda) = \frac{\lambda^2\cdot v^2/2}{1-c\lambda}-\lambda t$ for some ...
- 217
1
vote
0
answers
33
views
Concentration of the empirical moments
I do not know of any results on the concentration of empirical moments. More specifically, my problem is :
Let $X_1,...,X_n$ iid sampled by a law $\mathbf{P}$ with moments $\mu_i=\mathbf{E}_{\mathbf{P}...
- 11
3
votes
0
answers
29
views
Gap between two consecutive order statistics under arbitrary distribution.
Consider an arbitrary distribution $\mathcal{D}$ supported on $[a,b]$ with density function $\phi(x)\in[\gamma, \Gamma]$ where $\Gamma\geq \gamma>0$. M i.i.d samples $\{d_i\}_{i=1}^M$ are drawn ...
- 93
2
votes
0
answers
94
views
A dimension-free upper bound for $\| X \|_{\infty}$ when $X \sim N(0,\Sigma)$
For a $p$-dimensional random vector $X \sim N(0,\Sigma)$, it is known that with high probability
$$
\| X \|_{\max} \le C \sqrt{\log p}
$$
where $C$ is some constant possibly depending on $\Sigma$. I ...
- 4,353
0
votes
0
answers
38
views
using biased samples to get tighter concentration bounds
Suppose $\{X_1,X_2,\cdots,X_N\}$ are sampled from a fixed distribution $P_X$. Under different assumptions, we may have $|\frac{1}{N}\sum_{i=1}^N X_i- \mathbb{E}(X)|\leq f(N,\delta)$ for a given ...
- 21
2
votes
0
answers
66
views
$\ell_1$ norm of random projection
Let $G_{m, n}$ denote the Grassmannian manifold, i.e. the set containing all possible subspaces of $R^m$ with dimension $n$. Let $E \in G_{m, n}$. We can associate with $E$ an orthogonal projection ...
8
votes
1
answer
218
views
Dudley's Inequality can be Loose (Vershynin 8.1.12)
Let $e_1,...,e_n$ denote the canonical basis vectors in $\mathbb{R}^n$. Consider the set
$$T = \left \{ \frac{e_k}{\sqrt{1 + \log k}}, k =1,...,n\right \}$$
Show that
$$\int_{0}^\infty \sqrt{\log \...
- 643
0
votes
0
answers
24
views
Lower bound for the max of absolute value of i.i.d Gaussians.
I'm trying to prove the following result :
$$
\mathbb{E} \max_{i=1,2,\ldots,n} |X_i| \ge C \sqrt{\log(n)}.
$$
where the $ X_i $'s are i.i.d $ \mathcal{N}(0,1) $. To prove it, I tried to use the ...
0
votes
1
answer
36
views
probability of error in sampling to estimate sum of a population
Given non-negative numbers $$\{m_1, m_2,\dots,m_n\}$$ we have to estimate the sum $$s = \sum_{i=1}^nm_i$$ using sampling (with replacement). If we sample k numbers uniformly at random, then I can ...
- 67
0
votes
0
answers
23
views
Hanson-Wright inequality, any relation between the original quadratic form and the decoupled quadratic form?
Hanson-Wright's inequality such as this provides a bound on the second-order chaos of the form
$$P(x^\top A x -\mathbb{E}[x^\top A x] > t) $$
For example, $x\sim N(0, I_n)$ and $A$ is some $n\times ...
- 69
2
votes
1
answer
39
views
Does Hoeffding's inequality hold for uncorrelated random variables?
I know that Hoeffding's inequality holds for sums of independent random variables. However, we also know that being uncorrelated does not necessarily imply independence. But I wish to understand ...
- 77
2
votes
0
answers
28
views
Poincare constant for Gaussian distribution
The minimum of constant $C$ to satisfy the following condition is called Poincare constant for a probability measure $\mu$.
For any smooth function $f$ on $\mathbb{R}$, the relation
$$\int_{-\infty}^\...
- 155
2
votes
0
answers
112
views
Verifying the Bernstein condition for random matrices
Theorem 6.2 of the following paper by J. Tropp states the matrix Bernstein inequality for the subexponential case. Given two i.i.d. sequences $X_1,\dots,X_n \sim N(0,\Sigma)$ and $Y_1,\dots,Y_n \sim N(...
- 4,353
0
votes
0
answers
11
views
L1 Diameter of the Highest Posterior Density Region
In the frequentist statistics, we have confidence intervals with known diameters. However, in Bayesian statistics, we haven't the faintest idea of the diameter of the credible region. I believe it is ...
- 48
1
vote
0
answers
39
views
Upper bound for operator norm of sample covariance of two sequences of independent Gaussian vectors
Assume $X_1,\dots, X_n \stackrel{\text{i.i.d.}}\sim N(\mu, \Sigma)$ and $Y_1,\dots, Y_n \stackrel{\text{i.i.d.}}\sim N(\gamma, \Gamma)$ are $d$-dimensional random vectors and the two sequences are ...
- 4,353
1
vote
0
answers
38
views
Lower bound on the probability of a sum of iid random variables larger than a threshold
Suppose you are given $n$ iid random variables $X_1,\ldots,X_n$ each taking values in $\{1,2,3,\ldots\}$. Each $X_i$ has the cumulative distribution function $P(X_i \le v) = 1 - \frac{1}{(v+1)^p}$ for ...
1
vote
1
answer
21
views
Question about the definition of concentration function $\alpha_{P, X, \rho}(\epsilon):=\sup_{A\subset X}\{1-P(A^{\epsilon})|P(A)\ge 1/2\}$.
I have a question about the definition of concentration function, which is defined as in Wainwright, High-dimensional statistics.
The concentration function $\alpha:[0,\infty)\to \mathbb{R}_{+}$ ...
- 1,788
5
votes
2
answers
153
views
Concentration result from Delta method?
Let $X_1,X_2, \cdots$ be iid random variables with finite second moment.
Let $\bar{X_n} = (1/n)\sum_{i=1}^{n} X_i$ and $\bar{X^2_n} = (1/n)\sum_{i=1}^{n} X_i^2$.
Define $S_n = \bar{X^2_n} - (\bar{X_n})...
- 1,265
1
vote
1
answer
44
views
Coupling for tail bounds
Let $X_1, X_2$ be two random variables such that $\mathbf{E}X_1=\mathbf{E}X_2=0$ and
$$\forall x\geq 0, \quad \mathbf{P}[X_1\geq x]\leq \mathbf{P}[X_2\geq x].$$
Can we construct a coupling $(Y_1,Y_2)$ ...
- 813
1
vote
1
answer
36
views
Deriving Sample Complexity from given expectation bound
In equations (1.6) and (1.7) of this paper, the authors provide an upper bound on an expectation term and the corresponding sample complexity. I am a bit confused as to how they derive their sample ...
- 4,353
1
vote
0
answers
102
views
Use Chebyshev's inequality in sum of Bernoulli random variables
I'm currently studying for my exams and doing questions related to it.
This is a problem I've be stuck on for some time now and I'd like to know how to solve it.
Setting:
We have $n\geq 10$ random ...
- 470
0
votes
1
answer
71
views
Deriving a variant of Paley-Zygmund inequality for Gaussian variables
Recently I have encountered the following inequalities:
Let $Z \sim \mathcal{N}(0,\sigma^2)$, then
\begin{equation}
\forall t \in \mathbb{R},\text{ } P(|t+Z| \geqslant \sigma) \geqslant P(|Z| \...
- 325
2
votes
0
answers
48
views
Conditional expectation of a function of i.i.d. random variables given some of them
Suppose $(\Omega, \mathcal{A}, \mathbb{P})$ is a probability space $(E, \mathcal{E})$ is a nice measurable space. Let $X_i \colon \Omega \to E$ for $1 \le i \le n$ be i.i.d. random elements, and let $...
- 812
1
vote
0
answers
9
views
Relationship between $\gamma_n(A + B)$, $\gamma_k(A)$, and $\gamma_{n-k}(B)$, where $A \subseteq V$, $B \subseteq V^\perp$, and $\gamma_n := N(0,I_n)$
Let $\gamma_n = \gamma_1^{\otimes n}$ be the standard gaussian measure on $\mathbb R^n$ and let $V$ be a $k$-dimensional subspace of $\mathbb R^n$ with orthogonal completment $V^\perp$. Let $A$ and $B$...
- 8,309
0
votes
1
answer
33
views
Lower bound for probability of being above a certain percentage of the expectation
Let $X$ be a non-negative random variable and $\lambda \in [0,1]$, can we show that
$(1-\lambda)^2$ is smaller or equal to $P(X > \lambda E(X))$, where P denotes the probability distribution of $X$ ...
- 75
2
votes
0
answers
21
views
Expectation of sum of k max chi-square variables
Consider $n$ iid standard normal random variables $g_1,\ldots,g_n$, and I am interested in the lower bound for the following expectation
$$\mathbb{E}\max_{K\subset [n],|K| = k}\sum_{i\in K}g_i^2.$$
...
- 217
3
votes
2
answers
128
views
Exponential bound on the tail of a gaussian
Let $Z$ be a centered normal variable of variance $\sigma^2$, I am trying to prove that,
$$\sup_{t>0} \left( \mathbb{P}(Z \geq t) \exp\left( \frac{t^2}{2 \sigma^2} \right) \right) = \frac{1}{2} $$
...
- 612
1
vote
1
answer
109
views
Growth rate of derivatives of $\phi_n(t):=\mathbb E_x[f(x_1)f(tx_1 + (1-t^2)^{1/2} x_2)]$, where $x=(x_1,\ldots,x_n)$ is uniform on unit-sphere
Suppose $f:[-1,1] \to \mathbb R$ is function which is $k$ times continuously-differentiable a.e on $(-1,1)$, for some fixed $k \ge 1$. Let $n$ be a large positive integer, define the function $\phi_n:[...
- 8,309
2
votes
2
answers
51
views
Compute limit of $a_n:=E[f(x_1)f(x_2)]$, for random $(x_1,\ldots,x_n)$ on unit-sphere in $R^n$ and any function $f$ with a jump discontinuity at $0$.
Let $f:[-1,1] \to \mathbb R$ be continuous a.e (and assumed to be bounded, if that helps), with a jump-discontinuity at $0$ and set
$$
c:=\frac{f(0^-)+f(0^+)}{2}.
$$
For any integer $n \ge 2$, define $...
- 8,309
5
votes
1
answer
60
views
"Bernstein version" of McDiarmid?
I have seen used in a paper the following variant of McDiarmid's inequality, referred to as a "Bernstein-type variant":
Theorem. Let $f\colon \mathbb{R}^n \to \mathbb{R}$, and $X_1,\dots, ...
- 63.6k
1
vote
0
answers
108
views
Surface order large deviation in Ising ferromagnet
Background: A familiar behaviour of independent and identically distributed (i.i.d.) random variables $X_1, X_2,\ldots X_n$ is concentration: the probability that the sum $X_1+X_2+\ldots X_n$ exceeds $...
- 367
1
vote
0
answers
84
views
Integral of product of Hermite polynomials
Let $H_n$ be the $n$th Hermite polynomial of the probabilist. For example, $H_0(x) = 1$, $H_1(x)=x$, $H_2(x) = x^2 - 1$, $H_3(x) = x^3-3x$, etc. Let $u$ and $v$ be unit-vectors in $\mathbb R^d$, and ...
- 8,309
1
vote
0
answers
33
views
How to calculate the the number of nonzero for Poisson binomial distribution
Suppose a sequence of random number $S$, each entry has probability $p_i$ to be 1, otherwise choose zero. The sequence of probability is not necessary identical. According to wiki, we can compute the ...
1
vote
0
answers
31
views
Probability of Sampling Points outside of the Empirical Span
Let $P$ be a probability distribution over $\mathbb{R}^d$. Note that we DO NOT assume that $P$ is continuous w.r.t. Lebesgue measure. For example, P can be a multinomial distribution over a finite and ...
- 95