All Questions
Tagged with measure-concentration reference-request
10 questions with no upvoted or accepted answers
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
4
votes
0
answers
116
views
$\ell_p$ geodesic distance on smooth Riemannian manifold and Logarithmic Sobolev Inequalities
Bear with me, I'm not a professional geometer. Recently, I've been studying Logarithmic Sobolev Inequalities (LSI) for probability distributions on manifolds (e.g as done in works of Bobkvo et al. ...
- 6,853
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
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
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
1
vote
0
answers
351
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-...
- 380
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
1
vote
0
answers
361
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
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
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