Questions tagged [measure-concentration]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
2 answers
222 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 ...
dohmatob's user avatar
  • 6,716
5 votes
0 answers
218 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\...
Tyler6's user avatar
  • 91
1 vote
1 answer
184 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$, ...
dohmatob's user avatar
  • 6,716
0 votes
0 answers
133 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 ...
sorrymaker's user avatar
0 votes
0 answers
116 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 ...
Mark Schultz-Wu's user avatar
2 votes
0 answers
120 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 \...
theouscidda6's user avatar
2 votes
0 answers
201 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$. ...
Guy Fsone's user avatar
  • 1,033
3 votes
0 answers
278 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 ...
arriopolis's user avatar
2 votes
1 answer
438 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. ...
overfull hbox's user avatar
1 vote
1 answer
134 views

Minimax estimation rate of sparse vector $w_\star$, w.r.t to mixed norm $\|\hat w_n-w_\star\| := \|\hat w_n - w_\star\|_2 + \|\hat w_n-w_\star\|_q$

Let $n,d,s$ be positive integers with $s \le d$, and let $B_0(d,s)$ be the set of all (real) $d$-dimensional vectors with at most $s$ nonzero components. Given an $n \times d$ matrix $X$ with rows $...
dohmatob's user avatar
  • 6,716
2 votes
1 answer
117 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]...
Bob's user avatar
  • 123
0 votes
1 answer
104 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. ...
dohmatob's user avatar
  • 6,716
2 votes
1 answer
626 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 ...
dohmatob's user avatar
  • 6,716
2 votes
0 answers
160 views

Sudakov's lower bound type inequality for supremum of Chi-squared random variables

Let $\varepsilon$ be $n$-dimensional standard Gaussian veector, i.e., $\varepsilon \sim N_n(0, I_n)$. Let $\mathcal{P}$ be a subset of symmetric projection matrices in $\mathbb{R}^{n \times n}$ with $|...
De vinci's user avatar
  • 329
1 vote
0 answers
290 views

Lower bound on the sum of the product of random variables

Let $X_i$ be the $i$-th element of the vector $X=(X_1, ..., X_m)$ of i.i.d. random variables. I am looking for a lower bound for the expression $\mathbb{P}((\sum^n_{i=1}\prod^{m_i}_{j=1}(X_j))^2 \geq ...
Scriddie's user avatar
  • 129
2 votes
0 answers
123 views

Eigenvalues of Witten Laplacian induced by log-concave probability measure on manifold

Let $M$ be a closed $n$-dimensional Riemannian manifold and let $\mu=e^{-V}d\mathrm{vol}_M$ be a log-concave probability measure on $M$, such that the pair $(M,\mu)$ verifies the so-called Bakry-Emery ...
dohmatob's user avatar
  • 6,716
2 votes
0 answers
113 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 ...
De vinci's user avatar
  • 329
0 votes
1 answer
178 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$...
dohmatob's user avatar
  • 6,716
0 votes
1 answer
166 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$...
dohmatob's user avatar
  • 6,716
0 votes
0 answers
161 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$, ...
dohmatob's user avatar
  • 6,716
1 vote
1 answer
217 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 ...
dohmatob's user avatar
  • 6,716
1 vote
1 answer
215 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 ...
dohmatob's user avatar
  • 6,716
2 votes
1 answer
159 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 (...
dohmatob's user avatar
  • 6,716
3 votes
0 answers
91 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 ...
dohmatob's user avatar
  • 6,716
1 vote
0 answers
141 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$, ...
dohmatob's user avatar
  • 6,716
3 votes
1 answer
302 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 ...
Yihan Zhang's user avatar
1 vote
2 answers
94 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 $...
bolzano's user avatar
  • 143
1 vote
1 answer
97 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 ...
dohmatob's user avatar
  • 6,716
3 votes
1 answer
179 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 ...
Aditya's user avatar
  • 141
1 vote
1 answer
63 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 ...
dohmatob's user avatar
  • 6,716
6 votes
3 answers
415 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) = ...
dohmatob's user avatar
  • 6,716
2 votes
0 answers
51 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\|_{...
dohmatob's user avatar
  • 6,716
1 vote
1 answer
120 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 \...
dohmatob's user avatar
  • 6,716
4 votes
1 answer
201 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$)....
Jarosław Błasiok's user avatar
3 votes
1 answer
409 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 ...
ABIM's user avatar
  • 5,019
0 votes
2 answers
177 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 ...
dohmatob's user avatar
  • 6,716
1 vote
0 answers
268 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-...
Drew Brady's user avatar
1 vote
1 answer
367 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,...
dohmatob's user avatar
  • 6,716
2 votes
1 answer
85 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$. ...
dohmatob's user avatar
  • 6,716
2 votes
1 answer
112 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. ...
dohmatob's user avatar
  • 6,716
0 votes
0 answers
79 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 ...
user34500's user avatar
2 votes
1 answer
292 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 ...
dohmatob's user avatar
  • 6,716
2 votes
1 answer
162 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 ...
dohmatob's user avatar
  • 6,716
4 votes
2 answers
308 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$ ...
AspiringMat's user avatar
2 votes
1 answer
95 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 ...
Joe_Affine's user avatar
1 vote
1 answer
155 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 ...
Steve's user avatar
  • 1,117
1 vote
1 answer
293 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 ...
Probabilist's user avatar
8 votes
0 answers
163 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 ...
Sergio Zamora's user avatar
1 vote
0 answers
77 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$. ...
KNW's user avatar
  • 51
3 votes
1 answer
402 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 ...
dohmatob's user avatar
  • 6,716

1
2
3 4 5
8