Questions tagged [measure-concentration]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 702
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 ...
user avatar
  • 187
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$...
user avatar
  • 5,580
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$...
user avatar
  • 5,580
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$, ...
user avatar
  • 5,580
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 ...
user avatar
  • 5,580
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 ...
user avatar
  • 5,580
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 (...
user avatar
  • 5,580
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 ...
user avatar
  • 5,580
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 $...
user avatar
  • 5,580
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$, ...
user avatar
  • 5,580
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&...
user avatar
  • 1,197
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 ...
user avatar
  • 5,580
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 ...
user avatar
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 $...
user avatar
  • 143
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 ...
user avatar
  • 5,580
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 ...
user avatar
  • 141
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 ...
user avatar
  • 5,580
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) = ...
user avatar
  • 5,580
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\|_{...
user avatar
  • 5,580
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 $\...
user avatar
  • 5,580
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 (...
user avatar
  • 5,580
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 \...
user avatar
  • 5,580
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$)....
user avatar
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 ...
user avatar
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 ...
user avatar
  • 5,580
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-...
user avatar
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,...
user avatar
  • 5,580
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$. ...
user avatar
  • 5,580
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. ...
user avatar
  • 5,580
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},\...
user avatar
  • 5,580
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 ...
user avatar
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 ...
user avatar
  • 5,580
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 ...
user avatar
  • 5,580
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,095
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 21
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$. ...
user avatar
  • 51
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 \|...
user avatar
  • 5,580
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 ...
user avatar
  • 5,580
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 ...
user avatar
  • 267
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}[...
user avatar
  • 11
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 ...
user avatar
  • 1,222
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 ...
user avatar
  • 1,347
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 ...
user avatar
  • 911
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 ...
user avatar
  • 930
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}....
user avatar

1
2 3 4 5
7