# Questions tagged [measure-concentration]

The measure-concentration tag has no usage guidance.

323
questions

0
votes

0
answers

18
views

### Vector Norms of Sub-Gaussian Matrix Multiplication?

Let $X, Y$ be $n\times n$ matricies with i.i.d. sub-Gaussian entries.
I am interested in tail bounds for $\lVert XY\rVert$, where $\lVert\cdot\rVert$ is a norm on $\mathbb{R}^{n^2}$, i.e. I want tail ...

1
vote

0
answers

29
views

### Concentration of sample covariance for dependent data

Let $X_1, \ldots, X_T$ are sub-Gaussian random vectors in $\mathbb{R}^d$ coming from a common distribution with population covariance $\Sigma$. If they are independent, it is known that the sample ...

0
votes

1
answer

29
views

### VC dimension of a certain derived class of binary functions

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$...

0
votes

1
answer

28
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$...

0
votes

0
answers

52
views

### Upper-bound for bracketing number in terms of VC-dimension

Let $P$ be a probability distribution on a measurable space $\mathcal X$ (e.g;, some euclidean $\mathbb R^m$) and let $F$ be a class of funciton $f:\mathcal X \to \mathbb R$. Given, $f_1,f_2 \in F$, ...

1
vote

1
answer

160
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 ...

1
vote

1
answer

170
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 ...

2
votes

1
answer

101
views

### Existence of preferred direction for a random vector with arbitrary distribution on sphere, under a condition on its covariance matrix

Let $X$ be random vector on the unit-sphere $S_{n-1}$ in $\mathbb R^n$. We don't assume that the distribution of $X$ is uniform on $S_{n-1}$
I'm interested in proving the existence of a (...

2
votes

0
answers

71
views

### Explaning why the spectrum of a setting simple structure random matrix is always spiked ($d-1$ eigenvalues close to zero, and $1$ away from zero)

For concreteness, let $m=500$, $d=600$, $N=1000$. Let $W$ be and $d \times m$ matrix with unit-norm rows and let $u$ be a uni-norm vector of length $m$. Given a binary vector $b$ of length $m$, length ...

0
votes

0
answers

24
views

### Bound on distortion of norm of high-dim random variable upon projecting onto eigenspace spanned top $k$ eigenvectors of empirical covariance matrix

Let $X$ be a random vector in $\mathbb R^d$ with some "nice distribution" (with a covariance matrix, etc.). For example, for concreteness, one may assume that $X \sim N(0,\Sigma)$ for some $...

1
vote

0
answers

132
views

### $\newcommand\v{\operatorname{vol}_d(C}$Compact subsets of $ℝ^d$ which maximize $\inf_{|v|\le1}\dfrac{\v\cap(𝜀v+C))}{\v)}$ for fixed $\v)$ and $𝜀>0$

Let $\operatorname{vol}_d$ be the volume measure on $\mathbb R^d$ and let $B_d$ be the unit-ball. For $\varepsilon \ge 0$ and a compact subset $C$ of $\mathbb R^d$ with $\operatorname{vol}_d(C)>0$, ...

0
votes

0
answers

139
views

### Well-known inequalities with randomly selected sequences

Let $\mathcal{L}^n$ denote the Lebesgue measure on $\mathbb{C}^n$. For $r>1$, let $B_r$ denote the unit ball of $\ell_r^n$, $\mathbb{C}^n$ equipped with the usual $r$-norm.
Question: Let $1<p,q&...

0
votes

0
answers

48
views

### Nontrivial lower-bound for $\mathbb P(f(X) \le \alpha \|\nabla f(X)\|)$

Let $f:\mathbb R^d \to \mathbb R$ be a differentiable function whose gradient is $L$-Lipschitz (w.r.t euclidean norm), for some fixed $L \in [0,\infty)$. Let $X=(X_1,\ldots,X_d)$ be a concentrated ...

3
votes

1
answer

119
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 ...

1
vote

2
answers

79
views

### Concentration bound for sum of indicators of maximum value of k combinations

Let $X_1, \dots, X_n$ be i.i.d. random variables distributed as $\mathrm{Exp}(\lambda)$ for some $\lambda > 0$ and let $t > 0$. For every combination $J$ of $k$ of these variables, we define $...

1
vote

1
answer

72
views

### Limiting value of $\dfrac{1_n^\top B^{-1} A B^{-1} 1_n}{d}$, where $A=WW^\top + a I_n$, $B = WW^\top + b I_n$, and $W \sim N(0,\Sigma_d)$

Let $n$ and $d$ be positive integers with
$$
n,d \to \infty, \quad n/d \to \rho \in (0,\infty).
$$
Let $\Sigma_d$ be a psd matrix such that
$\mbox{trace}(\Sigma_d) = 1$.
$\|\Sigma_d\|_{op} = \mathcal ...

3
votes

1
answer

144
views

### Example where concentration of measure fails nontrivially

A metric probability space $(X, \mu, \rho)$, i.e., a complete separable metric space with a probability measure on its Borel sets, is said to satisfy (Gaussian) concentration of measure property if ...

1
vote

1
answer

57
views

### Lower-bound for $\mathbb E[e^{-b(v^\top X - c)^2}]$, when $X$ is log-concave in high-dimensions

Let $d$ be a large positive integer. Fix a unit-vector $v \in \mathbb R^d$, and scalars $b,c \in \mathbb R$ with $b > 0$. Let $X$ be a log-concave random vector in $\mathbb R^d$ normalized so that ...

6
votes

3
answers

378
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) = ...

2
votes

0
answers

41
views

### Spectral approximation of $(XX^\top/d)\circ(X\Sigma_dX^\top/d)$ where $X$ is an $n \times d$ random matrix with iid rows from $N(0,\Sigma_d)$

Let $X \in \mathbb R^{n \times d}$ be a random matrix with iid rows from $N(0,\Sigma_d)$ where $\Sigma_d$ is a $d \times d$ psd matrix verifying w.h.p,
$\mbox{trace}(\Sigma_d/d)= 1$.
$\|\Sigma_d\|_{...

0
votes

0
answers

28
views

### Asymptotics of $\mathbb E_W 1_n^TX_1^{-1}X_2X_1^{-1}1_n$, for $X_i = \mu_i\mu_i^T + b_i WW^T + c_i I_n$, and $W=(w_1,\ldots,w_n) \sim N(0,C)$

Let $n$ and $d$ be positive integers such that
$$
n,d \to \infty,\quad d/n \to \gamma \in (0,\infty).
\tag{1}
$$
Let $W$ be a random $n \times d$ matrix with entries from $N(0,\Sigma_d)$, where $\...

0
votes

0
answers

21
views

### Find $a,b,c \in \mathbb R$ s.T $\|f(ZZ^\top)-(a I_n+bXX^\top + c 1_n1_n^\top)\|_{op} \to 0$, where $x_1,\ldots,x_n \sim N(0,C)$ and $z_i=x_i/|x_i|$

Let $f:\mathbb R \to \mathbb R$ be a "sufficiently smooth" function. Let $n$ times $d$ be comparably large positive integers. For example, assume
$$
n,d \to \infty,\quad d/n \to \gamma \in (...

1
vote

1
answer

64
views

### Given iid $w_1,\ldots,w_N \sim N(0,1/d)$ iid, find a simple matrix $A$ s.t $\|aa^T-A\|_{op} \to 0$, 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,\ldots,w_N$ be iid from $N(0,(1/d)I_d)$ and let $f:\mathbb R \...

4
votes

1
answer

112
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$)....

3
votes

1
answer

127
views

### Wasserstein-type concentration inequalities for empirical measures on polish spaces

Let $(\mathcal{X},d)$ be a Polish (metric) space and let $\{X_n\}_{n=1}^{\infty}$ be a sequence of i.i.d. $\mathcal{X}$-valued random elements defined on a common complete (standard) probability space ...

0
votes

2
answers

88
views

### What is the limiting marginal distribution of a fixed number of coordinates of a random point drawn uniformly on large-dimensional sphere?

Let $X=(X_1,\ldots,X_d)$ be uniformly-distributed on the sphere of radius $\sqrt{d}$ in $\mathbb R^d$. It is well-known that in the limit $d \to \infty$, the marginal distribution of $X_1$ converges ...

0
votes

0
answers

104
views

### Tail bounds for random Gaussian chaos?

Let $g = (g_1, \dots, g_d)$ be a sequence of independent standard Normal random variables, and suppose $\Sigma$ is a $d \times d$ (deterministic), real, symmetric, positive definite matrix. The Hanson-...

1
vote

1
answer

146
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,...

2
votes

1
answer

68
views

### Asymptotics of $w^\top G^2 w$, where $w$ is a unit-vector, $G:=X^T(XX^T+t I_n)^{-1}X$, $t > 0$, and $X$ is an $n\times d$ gaussian random matrix

Let $X$ be an random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $w$ be a unit-vector in $\mathbb R^d$. With $\lambda>0$, and define $G:=X^\top(XX^\top + \lambda I_n)^{-1}X$. ...

2
votes

1
answer

92
views

### A question on the applicability Chebyshev inequality for sequence of random quantities

Let $(X_n)_n$ and $(Y_n)_n$ be two mutually independent sequences of random tensors (i.e scalars, vectors, matrices, etc.) defined on the same probability space, and let $f$ be a measurable function.
...

0
votes

0
answers

44
views

### Bounds on trace of ratio of rank-1 perturbed Wishart matrices

Let $a,b,d,e,f \ge 0$ and $c>0$. Let $X$ be a random $n \times m$ matrix with iid entries from $N(0,1/m)$ and set
$$
\begin{split}
W &:=XX^\top,\\
D &:= W \circ I_n = \mbox{diag}(w_{1,1},\...

0
votes

0
answers

64
views

### Expected diameter of a random point set

General problem: For a point set $S\subset X$ in a metric space $(X,d)$, let $\text{diam}(S)=\max_{x,y\in S}d(x,y)$. Given a distribution $P$ on $X$ and $m$ i.i.d. points $x_1,\ldots,x_m\sim P$, what ...

1
vote

1
answer

227
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 ...

1
vote

1
answer

86
views

### Compute the limit of trace of inverse of square of rank-1 perturbation of Wishart matrix

Let $a \ge 0$, $b,c>0$ be fixed constants, and let $X$ be an $m \times d$ random matrix with entries drawn iid from $N(0,1/d)$. Consider the random psd matrix $S := a 1_m 1_m^\top + b XX^\top + c ...

4
votes

1
answer

163
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$ ...

2
votes

1
answer

67
views

### Concentration Inequality for Bounding Lipschitz Empirical Lass

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, $(X_n:\Omega\rightarrow \mathbb{R}^m)_n$ be a sequence of i.i.d. random variables and let $L:\mathbb{R}^m\rightarrow [0,\infty)$ be ...

1
vote

1
answer

78
views

### Tail bound on the RKHS norm of a zero-mean Gaussian process

Let $f \sim \mathcal{GP}(0, K)$ be a zero-mean Gaussian process defined on a compact set $\mathcal{D} \subset \mathbb{R}^d$, where $K \colon \mathcal{D} \times \mathcal{D} \rightarrow \mathbb{R} $ is ...

1
vote

1
answer

113
views

### Anti-concentration of inner product of a uniform unit norm vector with another vector

I have a question, which is necessary at one step of my research. Suppose that $X$ is a uniform random vector on the unit sphere $$S^{d-1} := \{x \in \mathbb{R}^d: \|x\|_2 = 1\}~.$$ Is there any ...

8
votes

0
answers

144
views

### Do compact universal covers have concentration of measure phenomenon?

$\DeclareMathOperator\vol{vol}\DeclareMathOperator\diam{diam}$I have a sequence of compact Riemannian manifolds $M_n$ with $\diam (M_n) \to 0$ and finite fundamental groups $\pi_1 (M_n)$ so that their ...

0
votes

0
answers

41
views

### Concentration of function of Markov frequencies

Let $S=\{1,2,...,n\}$ be a finite set of states and $\{X_t,1\le t\le T\}\subset S$ be a Markov chain with stationary distribution $\pi=(\pi_1,...,\pi_n)$. For $1\le i\le n$, denote by $F_i$ the number ...

1
vote

0
answers

72
views

### Cosine function evaluations are linearly independent? [closed]

Let $\{x_1,\ldots,x_n\}$ be distinct points in $\mathbb{R}^d$, and consider the functions $f_j(x) = cos(w_j^T x + b_j)$ for $w_j \in\mathbb{R}^d$, $b_j\in\mathbb{R}$, $j=1\ldots,m$, and let $m\ge n$. ...

0
votes

0
answers

40
views

### Comparison inequality between Sobolev-seminorm w.r.t spherical uniform distribution and gaussian distribution

Let $d$ be a large positive integer. Let $f:\mathbb R^d \to \mathbb R$ be a continuously differentiable function. Let $X$ be uniformly distributed on the unit-sphere $S_{d-1} := \{x \in \mathbb R^d \|...

3
votes

1
answer

338
views

### Use statistical physics ideas ("replica trick") to compute asymptotic value of $\inf_{\|w\| \le r} (1/n)\|Xw-y\|^2$ for random $X$ and $y$

I'm trying to get my head around the "replica trick" and it's mathematically rigorous formulations (due to Talagrand, Parchenko, etc.). I was wondering to myself that a solution or insight ...

2
votes

1
answer

91
views

### Reweighting probability measures by convex potentials, and contraction in transport distance

Let $W: \mathbf{R}^d \to \mathbf{R}$ be a convex function such that $\int \exp(-W) = 1$, and define probability measures $\mu_y$ by
$$\mu_y (dx) = \exp( - W (x - y)) \,dx,$$
i.e. each $\mu_y$ is a ...

1
vote

0
answers

45
views

### Concentration inequality for matrix martingale with dynamic upper bounds

Consider a sequence of stochastic PSD matrices $X_1, X_2, \dots, X_n \in \mathbb{R}^{d\times d}$. Let $\mathcal{F}_k = \sigma(X_1, X_2, \dots, X_{k-1})$ be the natural filtration and $Y_k = \mathbb{E}[...

6
votes

0
answers

258
views

### Question about size-biased couplings and concentration of the number of collisions

Edit/Update: I was indeed missing something quite obvious. I assumed the notion of collision used was the one I am used to (number of pairwise collisions, so if a bin received $k$ balls then this ...

5
votes

1
answer

175
views

### Anti-concentration of Gaussian when conditioning on event

Let $v$ be a given vector with $\|v\|_{\Sigma^{-1}} \leq 1$, where $\Sigma$ is a positive semi-definite matrix and $\|v\|_{\Sigma^{-1}} = \sqrt{v^\top\Sigma v}$. Meanwhile, let $u$ be a random vector ...

3
votes

0
answers

71
views

### Ornstein-Ulhenbeck like semigroup for the orthogonal group with a hypercontractive inequality

I am looking for an Ornstein-Uhlenbeck like semigroup $P_t$ and associated generator $\mathcal{L}$ on $G = \operatorname{SO}(n)$ or $\operatorname{O}(n)$ that has a hypercontractive inequality with a ...

2
votes

1
answer

79
views

### Lipschitz condition with respect to operator norm of a Gaussian matrix with iid entries. Improved Gaussian Poincare Inequality?

The Gaussian Poincare inequality says that if $q:R^n\to R$ is Lipschitz (for simplicity you may additionally assume smooth with compact support), then $Var[f(X)] \le L^2$
for $X\sim N(0,I_q)$.
Now ...

2
votes

1
answer

97
views

### Concentration on discrete probability estimator

Let $t>1$ and $X_1,..., X_t$ a set of real random variables from a discrete distribution, whose pmf is $p(x)$, supported on the points $1,...,k$.
Let $N_t(x) = \sum_{i = 1}^t \mathbb{1}_{X_i =\, x}....