Questions tagged [measure-concentration]
The measure-concentration tag has no usage guidance.
397 questions
3
votes
1
answer
374
views
Concentration of very dependent Markov chains
Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary).
The flip ...
- 161
2
votes
0
answers
70
views
A lemma in the application of Lions's concentration compactness pricnciple in Hardy-Littlewood-Sobolev inequality
I'm encountering some problems when reading Lions' paper "the concentration-compactness principle in the calculus of variations. The limit case, Part 2".
The Hardy-Littlewood-Sobolev (HLS) ...
- 121
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 6,853
1
vote
1
answer
415
views
Approximate the singular values of a certain random dot-product kernel matrix (in the sense of El Karoui, Cheng-Singer, etc.)
Let $g:\mathbb R \to \mathbb R $ be a continuous function which is
"sufficiently smooth" (e.g $\mathcal C^3$) around $0$, and
"sufficiently integrable" (e.g integrable w.r.t $N(0,...
- 6,853
2
votes
1
answer
468
views
Converse of the Herbst argument?
Background
For a real-valued random variable $X$, define its entropy by $H(X) = E[\phi(X)] - \phi(E[X])$, where $\phi(u) = u \log u$.
It can be shown that, if the entropy satisfies the bound
$$
H(e^{\...
- 163
1
vote
1
answer
108
views
Asymptotic scaling of mean and variance for the norm of random vector (non gaussian components)
The norm of a vector whoose components $X_i$ are normally distributed follows the Non-central chi distribution and it can be shown that, increasing the number of components $k$ (i.e. the dimension of ...
- 305
1
vote
1
answer
161
views
Given iid $w_1,\dotsc,w_N \sim N(0,1/d)$ iid, find a simple matrix $A$ s.t $\|aa^T-A\|_\text{op}\to0$, where $a_i := E_{G \sim N(0,1)}[f(\|w_i\| G)]$
Let $d$ and $N$ be two large comparable integers, for example assume
$$
N,d \to \infty, \quad d/N \to \gamma \in (0,\infty).
$$
Let $w_1,\dotsc,w_N$ be iid from $N(0,(1/d)I_d)$ and let $f:\mathbb R \...
- 6,853
1
vote
1
answer
216
views
Rademacher complexity of function class $(x,y) \mapsto 1[|yf(x)-\alpha| \ge \beta]$ in terms of $\alpha$, $\beta$, and Rademacher complexity of $F$
Let $X$ be a measurable space and let $P$ be a probability distribution on $X \times \{\pm 1\}$. Let $F$ be a function class on $X$, i.e., a collection of (measurable) functions from $X$ to $\mathbb R$...
- 6,853
0
votes
1
answer
124
views
Is the product of sub-Gaussian polynomials in $\mathbb{R}[x]/(x^n-1)$ sub-Gaussian?
Let $\psi_\alpha(x) := \exp(x^\alpha)-1$.
It is well-known that for $\alpha\geq 1$ that
$$\lVert X\rVert_{\psi_\alpha} = \inf\{k>0\mid \mathbb{E}[\psi_\alpha(|X|/k)] \leq 1\}$$
defines an Orlicz ...
- 2,183
0
votes
1
answer
110
views
Positivity of linear combination of gaussian variables
Consider a collection of independent standard Gaussian variables $w_i$ for $i = 1, 2, \ldots, N$. Define its linear combination $f:=\sum_{i=1}^Na_iw_i+b_i$, where $a_i=pb_i$ ($p$ is a fixed parameter),...
- 49
4
votes
2
answers
308
views
Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$
Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
- 6,853
1
vote
1
answer
191
views
concentration of random field to its expectation function
Question
Given a random field $X(t)$ where the parameter space $T\subset\mathbb{R}_N$. Is there result regarding the concentration of the random field? For example
$\mathbb{P}\{\|X(t)-\mathbb{E}\{X(t)\...
- 405
0
votes
1
answer
182
views
Deducing norm concentration from MGF bounds
Suppose that $X$ is a centered, $\mathbf{R}^d$-valued random variable such that for all $t \in \mathbf{R}^d$, there holds the bound $$\log \mathbf{E} \left[ \exp \langle t, X \rangle \right] \leqslant ...
- 801
1
vote
1
answer
207
views
Anti-concentration inequality for the eigenvalue of Gaussian matrix
Let $f(x) = f(x_1, . . . , x_n)$ be a polynomial of degree $d$ and $\text{Var}[f] = 1$. One result by Carbery and Wright shows that for any $t\in\mathbb{R}$ and $ε > 0$,
$$
\text{Pr}_{x\sim N^n}[|f(...
- 91
1
vote
0
answers
129
views
Concentration of a combinatorial sum
Let $X=(x_1,\ldots,x_p)$ be an $p \times n$ random matrix with iid entries from $\{\pm 1\}$, distributed so that $\mathbb P(x_{ij} = 1) \equiv 1/2$, where $x_i=(x_{i1},\ldots,x_{in})$. Let $y$ be a ...
- 6,853
2
votes
1
answer
336
views
The lower bound of bivariate normal distribution
Suppose $(Z_1, Z_2)$ is the zero-mean bivariate normal distribution with covariance $\left( \begin{matrix} 1 & \rho; \\ \rho & 1\end{matrix} \right)$ with positive $\rho > 0$. What I want ...
- 331
2
votes
1
answer
150
views
Normalized concentration inequality for empirical CDF (iid sum)
Consider the empirical and population CDF,
$$
F_n(t) = \frac{1}{n} \sum_{i=1}^n 1\{X_i \leq t\} \quad \mbox{and} \quad
F(t) = \mathbb{E} [F_n(t)],
$$
where above $X_1, \dots, X_n$ are iid, real-...
- 380
2
votes
1
answer
417
views
High-probability lower bound for norm of least squares solution when both design matrix $X$ and response vector $y$ are random (and independent)
Let $n,d \to \infty$ with $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ matrix independent rows uniformly distributed on the the unit-sphere in $\mathbb R^d$ and let $y$ be a ...
- 6,853
1
vote
0
answers
121
views
Composing an Orlicz norm related to Bernstein's inequality?
This is related to my previous question, but is hopefully more precise.
I would like to reason about tail-bounds for polynomial products of concentrated random variables in $R:=\mathbb{R}[x]/(x^n-1)$.
...
- 2,183
1
vote
1
answer
310
views
$L_1$ norm concentration of an empirical distribution
Suppose we have one random variable $X$, whose sample space is $\mathbb{X}=\{x_1,x_2,\dots,x_m\}$, and the size of the sample space is $m$. We have $N$ i.i.d. samples from this distribution, and $x_i$ ...
- 23
0
votes
0
answers
195
views
Anti-concentration for Bernoulli summation
Suppose $\{ Y_i\}_{i = 1}^n$ is i.i.d. Bernoulli distribution with mean $p$. Denote the sample of $\{ Y_i\}_{i = 1}^n$ as $\overline{Y} = \frac{1}{n} \sum_{i = 1}^n Y_i$. I want to know where there ...
- 331
2
votes
0
answers
131
views
Large deviation principle for product of iid bounded symmetric random variables
Let $n$ and $k$ be positive integers. Let $X$ be the empirical mean of $n$ iid Rademacher random variables. Note that the distribution of $X$ is symmetric about 0, and also $|X| \le 1$ w.p 1. Let $X_1,...
- 6,853
5
votes
1
answer
1k
views
Explicit constant for Carbery–Wright inequality
The Carbery–Wright inequality is a seminal result about the anti-concentration of polynomials of Gaussian random variables.
See e.g. Meka, Nguyen, and Vu - Anti-concentration for polynomials of ...
- 111
3
votes
1
answer
746
views
Vector version of concentration of Lipschitz functions on sphere (Levy's Lemma)
Levy's Lemma asserts Lipschitz functions of vectors chosen uniformly from the unit hypersphere concentrate:
Lemma.
Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-Lipschitz on the unit hypersphere. ...
- 131
3
votes
1
answer
379
views
Concentration inequality for norm of solution to nonlinear least-squares problem
Define the piecewise-linear function $\psi(t):=\max(t,0)$ for all $t \in \mathbb R$.
Let $d,n,k \to \infty$ at the same rate (i.e $n \asymp k \asymp d$).
Let $y_1,\ldots,y_n \in \{-1,1\}$ uniformly ...
- 6,853
2
votes
2
answers
228
views
Minimal conditions on random vector $X \in R^n$ to ensure that $\lim_{t\to 0^+}\sup_{\|w\|_p = 1}\sup_{u \in \mathbb R}\mathbb P(|X'w-u| \le t)=0$
Let $X$ be a random variable on $\mathbb R^n$ and let $S_p^n := \{w \in \mathbb R^n \mid \|w\|_p = 1\}$ be the unit-sphere w.r.t to the $\ell_p$-norm in $\mathbb R^n$. We will be particularly ...
- 6,853
1
vote
1
answer
234
views
Hypothesis to guarantee Lindeberg's condition
Imagine to have a set of random variables $\{ X_i \}_{i=1}^{n}$ independent (Non identically distributed). In these scenario, if the Lindeberg's condition hold we can extend the result of the CLT, i.e....
- 305
3
votes
0
answers
70
views
Concentration for Hamming balls
It is well known that Lipschitz functions on the Boolean $n$-cube endowed with the Hamming metric satisfy concentration properties. Specifically, most of their values lie in a range of width $O(\sqrt ...
- 2,772
2
votes
1
answer
295
views
A result about sub-exponential random variables
I am reading the proof of Theorem 1(a) in the paper that proposed the CLIME method for estimating precision matrix. I am puzzled by an inequality on Page 605 three lines above formula (29). I isolate ...
- 56
5
votes
0
answers
266
views
Concentration inequalities for random measures
For random variables $X_1,\dots,X_n$ with common mean $\mathbb{E}[X_i]=\mu$ and common bounds $a\leq X_i\leq b$, we have the very useful Hoeffding's inequality:
$$\mathbb{P}\left(\left|\mu -\frac1n\...
- 101
2
votes
0
answers
202
views
Prove or disprove that $u=0$ a.e. on $\Bbb R^d$
Let $\Omega\subset\Bbb R^d$ be an open set. Let $k:\Bbb R^d\to [0,\infty)$ be measurable such that $0\in \operatorname{supp}k$. This implies that $\Omega\subset \Omega_k=\Omega+\operatorname{supp}k$. ...
- 1,101
0
votes
0
answers
142
views
Anti-concentration of the $\ell_2$ norm of log-concave measures
This question is regarding a special case of this question, for which it is plausible the details are known.
The Carbery-Wright inequality is an "anti-concentration inequality" that states ...
- 2,183
0
votes
0
answers
293
views
Can we prove the following anti-concentration inequality of polynomials of square Gaussian variables?
Following this question Anti-concentration of Gaussian quadratic form. We have the following inequality:
Let $X_1,\dots,X_n$ denote i.i.d. standard Gaussian random variables. For every $\epsilon>0$...
- 288
6
votes
3
answers
447
views
Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace
Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = ...
- 6,853
6
votes
1
answer
306
views
Weak concentration bounds for averages of independent random variables in Orlicz spaces
Let $\phi$ be an $N$-function, (i.e. $\phi : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}$ is convex and satisfies $\lim_{t \to 0} \frac{\phi(t)}{t} = 0, \lim_{t\to \infty} \frac{\phi(t)}{t} = \infty$)....
- 1,190
1
vote
1
answer
229
views
Gaussian width of intersection of cube and ball in high-dimensional euclidean space
Let $d$ be a large positive integer and fix $r \ge 0$. Set $S := B_2^n \cap [-r,r]^d$, where $B_2^d$ is the euclidean unit-ball in $\mathbb R^d$. Finally, let $\omega(S)$ be the Gaussian width of $S$, ...
- 6,853
1
vote
1
answer
231
views
For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?
Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...
- 6,853
5
votes
3
answers
5k
views
Distribution of the individual coordinates of a uniform random vector on a high-dimensional sphere
Let $X=(X_1,\ldots,X_n)$ be a random vector uniformly distributed on the $n$-dimensional sphere of radius $R > 0$. Intuitively, i think that for large $p$ every coordinate $X_i$ is normally ...
- 6,853
1
vote
1
answer
223
views
Bound error in approximating $E_x [H(f(x))]$ with random $(1/n) \sum_{i=1}^n \Phi(f(x_i)/h)$ where $H$ is Heaviside function and $\Phi$ is normal CDF
Let $f:\mathbb R^d \to \mathbb R$ be a "sufficiently smooth" function. For simplicity, we may consider $f$ to be an affine function, i.e $f(x) \equiv b-x^\top w$, for some $(w,b) \in \mathbb ...
- 6,853
3
votes
0
answers
335
views
Tail bound on trace norm / nuclear norm / Schatten-1 norm of Rademacher matrix
Let $0 < r \leq d$ integers. Let $X$, $Y$ be $d \times r$ matrices of independent Rademacher variables, that is, $X,Y \in \mathbb{R}^{d \times r}$ with entries $\pm1$ with probability $1/2$. I am ...
- 223
0
votes
0
answers
152
views
Concentration compactness lemma and the best Sobolev constant
It is well known that the best Sobolev constant can be achieved on $\mathbf{R}^n$. More precisely, we have the following theorem (A):
Let $\frac{1}{q}=\frac{1}{2}-\frac{1}{n}$, $$S=\inf\limits_{{u\in ...
- 705
2
votes
1
answer
304
views
An approximation problem w.r.t marginal distribution of coordinates of uniform random vector on high-dimensional unit-sphere
Let $X=(X_1,\ldots,X_d)$ be uniformly distributed on the sphere of radius $\sqrt{d}$ in $\mathbb R^d$. Fix a "sufficiently integrable" function $h:\mathbb R \to \mathbb R$, and define ...
- 6,853
7
votes
3
answers
496
views
Chernoff-type bounds for a stopped sum of independent random variables
Let $Y_1, \ldots, Y_n$ and $X_1, \ldots, X_n$ be i.i.d. $p$-Bernoulli random variables and let $T \in \{0, \ldots, n\}$ be a stopping time for the process. From Wald's equation, we know
$$
E\left[\...
- 153
0
votes
1
answer
108
views
On the invertibility of $Z^\top Z$, where $Z$ is a Random matrix with concentrated weakly correlated entries
Let $d$, $n$, and $m$ be large positive integers. Let $X=(x_1,\ldots,x_n) \in \mathbb R^{n \times d}$ be a random matrix iid rows from some distribition $P$ on $\mathbb R^d$ which admits a density. ...
- 6,853
4
votes
2
answers
343
views
Concentration of $k$-th pairwise distance of random points in a unit square
For $1\leq i \leq n$, let $X_i\sim \text{Uniform}(0,1)$, $Y_i \sim \text{Uniform}(0,1)$ be $n$ points chosen uniformly in the unit square. Denote the $k$-th smallest pairwise distances across the $n$ ...
- 662
2
votes
1
answer
947
views
Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries
Let $n$ and $m$ be large positive integers. Let $x=(x_1,\ldots,x_n)$ be a vector of independent random variables from $N(0,1)$. It is clear that the covariance matrix of $x$ is $I_n$, the identity ...
- 6,853
2
votes
1
answer
143
views
DKW inequality for $L^1$-norm
Suppose that $X,X_1,X_2,X_3\dots$ is a sequence of $\mathbb{P}$-i.i.d. random variables supported in the interval $[0,1]$. Let $F$ be the cumulative distribution of $X$, i.e. $F(x):=\mathbb{P}[X \le x]...
- 123
24
votes
1
answer
1k
views
A Rademacher ‘root 7’ anti-concentration inequality
Let $r_1,r_2,r_3,\dotsc$ be an IID sequence of Rademacher random variables, so that $\mathbb P(r_n=\pm1)=1/2$, and $a_1,a_2,\dotsc$ be a real sequence with $\sum_na_n^2=1$. For $S=\sum_na_nr_n$, does ...
- 17.1k
2
votes
1
answer
669
views
Lower-bound for smallest eigenvalue of random $k \times $k matrix $C(W)$ defined by $C(W)_{i,j} := 2(w_i^\top w_j)^2 + \|w_i\|^2\|w_j\|^2$
Let $k$ and $d$ be positive integers such that $d/k:=\lambda > 1$. Let $W$ be $k \times d$ random matrix with rows $w_1,\ldots,w_k \in \mathbb R^d$ drawn iid from $N(0,(1/d)I_d)$, and define the $k ...
- 6,853
2
votes
0
answers
167
views
Convex ordering of measures that are obtained by different push-forwards of a same measure
Suppose that we have a probability measure $\rho$ which is supported on $\mathbb{R}^d$ and absolutely continuous w.r.t. the Lebesgue measure. Take two vector fields $F, G : \mathbb{R}^d \rightarrow \...
- 21