All Questions
23 questions
1
vote
0
answers
42
views
Sub-Gaussian analysis via bounded decomposition?
Let $\psi_\alpha(x) := \exp(x^\alpha)-1$.
The Sub-Gaussian Norm $\lVert X \rVert_{\psi_2}$ of a random variable $X$ is defined as
$$
\lVert X\rVert_{\psi_2} = \inf\{c>0\mid \mathbb{E}[\varphi_2(|X|/...
- 2,183
3
votes
0
answers
130
views
A Talagrand inequality for the supremum of partial sums over function classes under dependence. (Reference request)
As a consequence to the Talagrand concentration inequality, it is well known that for a measurable space $(S,\mathcal{S})$ and an i.i.d. sample $X_1,...,X_n$ of $S$-valued random variables, if $\...
- 141
5
votes
1
answer
400
views
Lower tail of random rank one sums?
Let $\{x_i\}_{i\geq 1}$ be iid random elements of the sequence space $\ell^2(\mathbb{N})$;
assume that $\|x_i\|_2 \leq 1$ almost surely. Let $\Sigma = \mathbb{E}[x_1 \otimes x_1]$.
Define
$$
\Sigma_n =...
- 410
10
votes
2
answers
1k
views
Simple proof of sharp constant in DKW inequality
The DKW inequality says that if $F_n$ is the empirical CDF corresponding to real-valued random variables $X_1, \dots, X_n$ distributed identically and independently from a distribution with CDF $F$, ...
- 410
1
vote
0
answers
348
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-...
- 410
0
votes
0
answers
86
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 ...
- 19
3
votes
1
answer
553
views
How did the story of Kim-Vu type inequalities continue?
I am interested in the concentration of polynomials of random variables. I have been reading Boucheron, Lugosi, and Massart's "Concentration inequalities" and they give some references. ...
- 233
2
votes
1
answer
210
views
Prove / disprove: If $1 \le n < N$ and $A$ is an $N \times n$ matrix with iid from $\mathcal N(0,1)$, then $s_\min(A) \ge c\sqrt{N}$ w.p $1-2e^{-N}$
Let $1 \le n < N$ be integers and $A$ be a random $N\times n$ matrix with iid entries from $\mathcal N(0,1)$. This paper (Rudelson and Vershynin) claims in the paragraph just before formula (3.4) ...
- 6,853
0
votes
1
answer
279
views
Lower-bound on smallest singular-value of rectangular random matrix
Let $X$ be a random $N \times n$ matrix with iid entries from $\mathcal N(0, 1)$ and with $n/N =: \lambda(N,n) \le \lambda_0$, for some $\lambda_0 \in (0, 1)$. That is, $X$ is genuinely rectangular (...
- 6,853
3
votes
1
answer
181
views
How tight is the bound $P(\|X\|^2 \ge t |\langle a,X\rangle|) \ge 1 - t\sqrt{\frac{2}{m-1}}$, where $X \sim N(0, I_m)$ and $\|a\| = 1$?
Let $X$ be a random vector in $\mathbb R^m$ with iid $N(0,1)$ coordinates and let $a$ be a fixed unit vector in $\mathbb R^m$. In another post (SE link here https://math.stackexchange.com/a/3792730/...
- 6,853
0
votes
1
answer
115
views
Compute lower bound on $\min_{E} \mathcal N(0,\sigma^2 I_n)(E)$ subject to $vol(E \cap H_n(r)) / vol(H_n(r)) \ge p$ where $H_n(r)$ is $n$-hemisphere
Let $n \ge 2$ be an integer, which may be assumed to be very large. For $r > 0$, consider the hemi-sphere $H_n(r) := S_n(r) \cap (\mathbb R^+ \times \mathbb R^{n-1})$, where
$$
S_n(r):= \{x \in \...
- 6,853
12
votes
2
answers
2k
views
Can we do better than Azuma-Hoeffding when the variance is small?
The Azuma-Hoeffding Inequality says that if $X_1,X_2, \ldots$ is a martingale and the differences are bounded by constants, $\|X_i - X_{i-1}\| \le 1$ say, then we should not expect the difference $\|...
- 1,955
1
vote
0
answers
175
views
Matrix Bernstein for spherical random variables
Theorem 4.1 in Tropp's Matrix Concentration Inequalities provides an exponential concentration inequality for the spectral norm of a matrix $Z = \sum_i \gamma_i B_i $, where $\gamma_i$ are an i.i.d. ...
- 111
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 ...
- 8,071
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}\...
- 8,071
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 ...
- 363
9
votes
2
answers
1k
views
Adaptive version of the Azuma–Hoeffding inequality
The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition:
$$|X_k - X_{k-1}| \leq c_k$$
Then:
$$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...
- 794
1
vote
0
answers
360
views
concentration inequalities for quadratic forms of correlated random vectors
Let $\mathbf{n}$ is a Gaussian random vector with mean $\mathbf{0}$ and co-variance matrix $\mathbf{H}$. Let $\mathbf{r} = Sign(\mathbf{n})$, where $Sign(n_i) = 1$ if $n_i>0$ and $Sign(n_i) = -1$ ...
- 39
4
votes
1
answer
474
views
Concentration inequalities in $\ell_{\infty}$ for sums of iid random ("nice") functions?
I'm looking for "tail-bound-like" inequalities that look like this (I state a specific setting but more general settings are interesting):
Let $D$ be a distribution on a set of "nice" functions $g$:...
- 4,529
1
vote
0
answers
98
views
Small ball probabilities for functions of correlated normals
Let $f : \mathbb{R}^k \rightarrow \mathbb{R}$ and let $X$ be distributed k-dimensional normal with mean $0$ (with "arbitrary" covariance matrix). I am looking for references with bounds of the form: ...
- 111
5
votes
1
answer
282
views
What is the spectral norm of a random projection times a diagonal?
Take $n\ll N$. Let $P$ be an $n\times N$ matrix of iid $\mathcal{N}(0,1)$ random variables, and let $D$ be an $N\times N$ diagonal matrix.
What can be said about the distribution of the largest ...
- 7,633
9
votes
0
answers
1k
views
Balls and bins -- concentration bounds pertaining to the minimal load bin
Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...
- 201
7
votes
2
answers
2k
views
Tails of sums of Weibull random variables
Suppose that $X_1, X_2, \ldots, X_n$ are i.i.d random variables distributed according to Weibull distribution with shape $0 < \epsilon < 1$ (it means that $\mathbf{Pr}[X_i \geq t] = e^{-\Theta(t^...
- 1,791