Skip to main content

All Questions

Filter by
Sorted by
Tagged with
18 votes
1 answer
1k views

How fast can extreme eigenvalues of the average of random matrices converge to their expectation?

Suppose that $X_1,X_2,\ldots,X_m$ are independent $d\times d$ random matrices and let $\overline{X} := \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices is ...
sbahmani's user avatar
  • 181
10 votes
2 answers
847 views

Minimum separation among $m$ random points on an $n$-dimensional unit sphere

Consider $m$ points $v_1, \ldots, v_m \in R^{n}$, which are uniformly distributed on the $n$-dimensional unit sphere $S^{n-1} = \{v:\|v\|_2 = 1\}$. Let the minimum separation be $$ \rho = \min_{i,j\in{...
Minkov's user avatar
  • 1,127
10 votes
4 answers
645 views

Expected value of Bernoulli quadratic forms

Let $\mathbf{Y}\in\mathbb{R}^{n\times n}$ be a symmetric matrix. Let $\mathbf{x}\in\mathbb{R}^n$ be random vectors with entries i.i.d. $\pm 1$ with equal probability. I'm interested in a lower bound ...
Anahita's user avatar
  • 363
10 votes
2 answers
455 views

Largest deviations for uniform order statistics

Let $n >0$. Let $X_1,\ldots,X_n$ be i.i.d. uniform random variable on $[0,1].$ Denote by $X^{(1)}\leq X^{(2)} \leq \cdots \leq X^{(n)}$ their order statistics, and write $\Delta^{(i)} = \vert X^{(...
Gericault's user avatar
  • 245
8 votes
2 answers
1k views

Does Multiplicative Version of Azuma's Inequality Hold?

It is known that there are multiplicative version concentration inequalities for sums of independent random variables. For example, the following multiplicative version Chernoff bound. Chernoff bound:...
Liwei Wang's user avatar
7 votes
1 answer
466 views

Martingale version of Bernstein-type inequality for (slightly) heavy-tailed distributions?

It is known that for sub-exponentially distributed martingale difference sequence, the following Bernstein-type inequality holds: $$ ℙ\left(\left| \sum_{i=1}^N a_i X_i \right| \ge t \right) \le 2\...
Nikolayevich's user avatar
7 votes
2 answers
606 views

Uniform Concentration Bounds on Weighted Sum of i.i.d. Bernoulli Random Variables

Let $\delta_1,...,\delta_n$ be $n$ independent identically distributed Bernoulli random variables with $\mathbb{P}(\delta_1=1)=p$. We consider a set $\Omega = \{\mathbf{a}:=(a_1,...,a_n)~|~a_i\in [0,c/...
tourzhao's user avatar
6 votes
1 answer
203 views

Good upper-bound for $\mathbb E[|X-np|^r]$ where $X \sim \text{Binomial}(n,p)$ and $r \ge 1$

Disclaimer. Question moved from SE. Setup Let $X \sim \text{Binomial}(p, n)$, and $r \ge 1$. Question What is a good upper-bound for $\mathbb E[|X-np|^r]$ ? Solution for small $r$ If $r=2$, then ...
dohmatob's user avatar
  • 6,853
6 votes
0 answers
554 views

a variation on Hanson-Wright inequality

The classic Hanson-Wright inequality states that for a Gaussian random vector $\mathbf{x}\in\mathbb{R}^n$ distributed as $\mathcal{N}(\mathbf{0},\mathbf{I})$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$ ...
mohi's user avatar
  • 859
5 votes
1 answer
372 views

What are some of results in low dimensional statistics that do not hold in high dimensions?

This question is partially inspired by the following MO post: What are some of the surprising results of finite sample statistical estimation? and current heated research front of high dimensional ...
Henry.L's user avatar
  • 8,071
5 votes
2 answers
565 views

Concentration of U-statistics for exchangable distributions (and the unbounded case)

Consider the following so-called $U$-statistic of order 2: $$U = \frac1{\binom{m}{2}} \sum_{i < j} h(w_i,w_j)$$ where $w_1,\dots,w_m$ are IID from some distribution and $h$ is symmetric. If $|h(w_1,...
passerby51's user avatar
  • 1,731
5 votes
0 answers
711 views

Concentration inequality for max component of a multivariate Gaussian in the general case

I am looking to bound the variance of the maximum component of a vector distributed multivariate Gaussian in the general case where the Gaussian distribution has arbitrary mean and full covariance ...
ted's user avatar
  • 283
4 votes
1 answer
1k views

Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences

A classic formulation of the Bernstein inequality (from Wikipedia) is as follow: Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$...
Jean Claude's user avatar
4 votes
2 answers
175 views

Almost independence of $x^\top a$ and $x^\top b$ for $x$ uniform on the sphere in $\mathbb R^d$ and $a,b \in \mathbb R^d$ with $a^\top b = 0$

Let $d$ be a large positive integer. Let $x$ be uniformly distributed on the unit-sphere in $\mathbb R^d$ and let $a$ and $b$ be perpendicular vectors in $\mathbb R^d$, i.e such that $a^\top b=0$. Let ...
dohmatob's user avatar
  • 6,853
4 votes
1 answer
239 views

Uniform inequality of the form $\text{Proba}(\sup_{v \in [-M,M]^k}|p^Tv-\hat{p}_n^Tv| \le \epsilon_n) \ge 1 - \delta$

Let $M > 0$, $k$ be a positive integer, and $\mathcal V:=[-M,M]^k$. Finally, let $p \in \Delta_k$, (where $\Delta_k$ is the $(k-1)$-dimensional probability simplex) and let $\hat{p}_n$ be an ...
dohmatob's user avatar
  • 6,853
4 votes
1 answer
206 views

Inner product of sorted Gaussian vector

Suppose $X_1,\ldots,X_n$ are i.i.d. standard normal. I'm wondering how to analyze the following quantity: $$\left|\frac{X_{(1)}X_{(n)}+X_{(2)}X_{(n-1)}+\cdots+X_{(n)}X_{(1)}}{n}\right|$$ where $X_{(1)}...
neverevernever's user avatar
4 votes
1 answer
347 views

Concentration of functional of Gaussian random variable

Suppose I have two Gaussian distributions $p(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_p|^{1/2}}\exp(-\frac{1}{2}x^\top \Sigma_p^{-1} x)$ and $q(x) = \frac{1}{(2\pi)^{d/2}|\Sigma_q|^{1/2}}\exp(-\frac{1}{2}x^\...
Wuchen's user avatar
  • 515
4 votes
0 answers
638 views

Comparison of concentrations of different $L^p$-norms of (sub) Gaussian distributions

It's well-known that the Euclidean $2$-norm of subgaussian random vectors concentrates in high dimensions, e.g. when $X \sim \mathcal{N}(0,I_n),$ (or in general $X$ is subgaussian with independent co-...
Learning math's user avatar
4 votes
0 answers
141 views

Is there an example that both Berry-Essen bound and DKW bound are attained?

The Berry-Essen bound stated that $$\sup _{{x\in {\mathbb R}}}\left|\widehat{F_{n}(x)}-\Phi (x)\right|\leq C_{0}\cdot \psi _{0}$$ where $\psi _{0}(n)={\Big (}{\textstyle \sum \limits _{{i=1}}^{n}\...
Henry.L's user avatar
  • 8,071
4 votes
0 answers
76 views

How well does an estimator perform on another dataset?

Suppose $X \sim N(0, \Sigma)$ is a $d$-dimensional Gaussian random vector. And we have $2n$ $i.i.d$ sample $X_1, \ldots, X_{n}, \ldots, X_{2n}$. Let $\hat{\Sigma}_1 = \frac{1}{n}\sum_{i=1}^nX_i X_i^\...
Wuchen's user avatar
  • 515
4 votes
0 answers
1k views

Concentration of sum of independent random variables

Let $X_1, ..., X_n$ be i.i.d. sub-Gaussian random variables with mean $0$ and variance $1$. That is, we have $\Pr[|X_i| > t] \leq \exp(1-t^2/K^2)$ for all $t>0$ and a parameter $K$. Then we can ...
MCH's user avatar
  • 1,324
3 votes
2 answers
732 views

Concentration inequality for sum of iid random variables that involve KL distance

Conider $X \in \mathbb{R}^d$ and $Y \in \{0,1\}$, and a joint distribution $p_{XY}(x,y)$, and a set of $N$ i.i.d. samples $\{(X_i,Y_i)\}_{i=1}^{N}$. Define $p_{X0} = p_{XY}(x,0)$ and $p_{X1} = p_{XY}(...
Jeff's user avatar
  • 482
3 votes
1 answer
88 views

If $X \sim N(0,I_m)$, what is a necessary and sufficient condition on $u_m > 0$ such that $\lim\sup_{m\to \infty} P(\|X\|^2 \ge u_m|X_1|) = 1$

Let $m$ be a large positive integer and $X=(X_1,\ldots,X_m) \sim N(0,I_m)$. I wish to show that the squared norm of $X$ is much much bigger than the absolute value of any of the $X_j$'s. For example, ...
dohmatob's user avatar
  • 6,853
3 votes
2 answers
319 views

Concentration inequality of joint event over time of a submartingale

Consider a discrete time submartingale $X_n$ with bounded difference $|X_n-X_{n-1}|\leq c$. With Azuma inequality we have the concentration of a single time event as $$ P(X_t-X_0 \leq -t) \leq exp\...
Sung-En Chiu's user avatar
3 votes
1 answer
294 views

Concentration inequalities specialized for log-likelihood / log-density functions

Let $P$ be a probability measure and $f$ be some probability density function (not necessarily related to $P$). Consider the function $$ L(X_1,\ldots,X_n) =\frac1n\sum_{i=1}^n\log f(X_i), \quad X_i\...
JohnA's user avatar
  • 710
3 votes
1 answer
196 views

Uniform Convergence for Vectors

$\textbf{Problem statement:}$ Let $\mathcal H:\mathcal X \rightarrow \{0,1\}$ be a class of Boolean functions for $\mathcal X \subset \mathbb R^n$, and let the VC Dimension of $\mathcal H$ be $VC_{...
AvidLearner's user avatar
3 votes
0 answers
92 views

Tighter Freedman's inequality for a special martingale difference sequence

Let $X_{1}, \ldots, X_{T} \in \{0, 1\}$ be a sequence of Boolean random variables with $$ \mathbb{E}[X_{t} | X_{1}, \dots, X_{t - 1}] = p_{t}. $$ Consider the sequence $Y_{t} := X_{t} - p_{t}$ (which ...
Fellow4's user avatar
  • 41
3 votes
0 answers
93 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,853
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 ...
dohmatob's user avatar
  • 6,853
3 votes
0 answers
307 views

Upper-bound for eigenvalues of $E [UU^T]$, where $U$ is uniformly distributed on the unit $n$-sphere

Let $X$ be a $\sigma$-subGaussian random vector on $\mathbb R^n$ (for large $n \ge 3$), meaning that the random variable $X^Tv$ is $\sigma$-subGaussian for every unit vector $v \in \mathbb R^n$. ...
dohmatob's user avatar
  • 6,853
3 votes
1 answer
826 views

concentration inequality for a weighted sum of independent but not identical binary variables

Let $\alpha\in[0,1]$ be a fixed constant, and let $w,x\in[0,1]^n$ be two vectors such that $\sum_i w_i x_i=\alpha$. Define $Y = \sum_i w_i X_i$, where $X_i \sim \operatorname{Bernoulli}(x_i)$, so it ...
guigux's user avatar
  • 617
2 votes
1 answer
668 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 ...
dohmatob's user avatar
  • 6,853
2 votes
2 answers
690 views

Concentration and anti-concentration of gap between largest and second largest value in Gaussian iid sample

Let $n \ge 3$ be an integer and let $X=(X_1,\ldots,X_n)$ be random vector with iid coordinates from $N(0,1)$. For $1 \le k \le n$, let $X_{(k)}$ be the value of the $k$th largest coordinate of $X$. ...
dohmatob's user avatar
  • 6,853
2 votes
1 answer
848 views

Concentration inequality for quadratic form of Gaussian variables with non-idempotent matrix

Given $y \sim N(0,\sigma^2 I)$, and $M$ that is a symmetric matrix (not necessarily idempotent) what is the distribution of ${y^T M y}$? is there a high probability bound on $|{y^T M y}|$? Most ...
Enigman's user avatar
  • 123
2 votes
1 answer
464 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^{\...
aest's user avatar
  • 163
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 ...
dohmatob's user avatar
  • 6,853
2 votes
1 answer
90 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,853
2 votes
1 answer
187 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,853
2 votes
2 answers
1k views

Lower bound on number of samples for an epsilon delta approximation matching the Chernoff bound

So we have two biased coins, one comes out head w.p. $1/2+\epsilon$ and the other w.p. $1/2-\epsilon$. How many times should we flip these two coins to be able to tell them apart w.p. at least $\delta$...
shahrzad haddadan's user avatar
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-...
Drew Brady's user avatar
2 votes
1 answer
939 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,853
2 votes
1 answer
116 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,853
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 ...
dohmatob's user avatar
  • 6,853
2 votes
0 answers
84 views

Concentration result for self-normalized empirical process

In Theorem 1.1 of this paper by Bercu, Gassiat and Rio, a concentration result is derived for the 'self-normalized' empirical process. Specifically, suppose that $(X,X_n)_{n \ge 1}$ is a sequence of i....
WeakLearner's user avatar
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,853
2 votes
0 answers
172 views

Asymptotic lower and upper bounds for the eigenvalues of hadamard product $W \circ W$, where $W$ is a large Wishart matrix

Let $n$ and $d$ be large positive integers with $n,d \to \infty$ such that $n/d \to \gamma \in (0,\infty)$. Let $X$ be a random $n \times d$ random matrix with iid copies of log-concave isotropic ...
dohmatob's user avatar
  • 6,853
2 votes
1 answer
415 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 ...
dohmatob's user avatar
  • 6,853
2 votes
0 answers
68 views

Approximate any point of the interval $[-1/2,1/2]$ by the sum of $n$ iid uniform random variables from $[-1,1]$

Let $x \in [-1/2,1/2]$ and $X_1,\ldots,X_n$ be drawn iid from the uniform distribution on $[-1,1]$. Question. Given $\varepsilon \ge 0$ an integer $k \in [1,n]$, what is a good lower-bound on the ...
dohmatob's user avatar
  • 6,853
2 votes
0 answers
366 views

Convergence rate of Pearson correlation matrix

I am interested in (rather sharp if not the finest) tail/concentration bounds for the Pearson correlation matrix: let $X_1,\ldots,X_N \sim \mathcal{N}(0,1)$ be correlated random variables; let $\rho(...
mic's user avatar
  • 121
2 votes
0 answers
386 views

What is the concentration of measure for Gaussian random variables which are independent, but are transformed?

This might be a too easy question for Mathoverflow, but Googling led to similar questions and answers here (though not the one I was looking for). The question is split into two: I have a matrix $X \...
kloop's user avatar
  • 131