Skip to main content

All Questions

Filter by
Sorted by
Tagged with
2 votes
1 answer
302 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}....
Apprentice'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
1 vote
1 answer
475 views

Convergence of quadratic form $y^T Q y$ where $y$ is a random iid sequence of length $n$ and $Q$ is an $n \times n$ random matrix independent of $y$

For each positive integer, let $Q_n=(q_{i,j})_{i,j \in [n]}$ be a random $n \times n$ psd matrix. In the limit $n \to \infty$, suppose the eigenvalues of this sequence of matrices are uniformly ...
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
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. ...
user2316602's user avatar
1 vote
1 answer
144 views

Bounds for the extreme singular-values of random matrix with thresholded entries

Let $n,d,k$ be large positive integers such that $\max(n/d,k/d) =: \lambda < 1$. Let $X$ be a random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $W$ be a $k \times d$ random ...
dohmatob's user avatar
  • 6,853
1 vote
0 answers
155 views

Relation between the class $\mathcal{M}(m,\sigma)$ and subgaussianity

In this paper, Adamczak defines, for $m>0$ and $\sigma\geq 0$, the class of probability distributions $\mathcal{M}(m,\sigma)$ over $\mathbb{R}$ as those $\mu$ satisfying the tail conditions $$\nu^+(...
Clement C.'s user avatar
  • 1,372
2 votes
0 answers
83 views

Concentration inequalities for sets

Assume that we have a random set $B$ which is constructed by selecting elements from $U = \{ X_1, \dots, X_n \}$ where $X_i$ are independent samples from Gaussians with means $\mu_i$ and variances $\...
bolzano's user avatar
  • 143
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
1 vote
0 answers
96 views

Concentration for $\sum_{i=1}^n y_i \psi(x_i^\top u)$, for $y_1,\ldots,y_n \sim \{\pm 1\}$ and $x_1,\ldots,x_n$ uniform iid on hypersphere

Let $y_1,\ldots,y_n$ be drawn iid uniformly from $\{\pm 1\}$ and let $x_1,\ldots,x_n$ be drawn iid uniformly from the unit-sphere $(d-1)$-dimensional sphere $\mathbb S_{d-1}$, and independently from ...
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
1 vote
0 answers
68 views

(Anti-)concentration of gap between largest and second largest component of multivariate random gaussian vector

Let $n$ be a large positive integer and let $Y=(Y_1,\ldots,Y_n)$ be a zero-centered random $n$-dmensional real vector with covariance matrix $\Sigma$, an $n$-by-$n$ positive definite matrix with ...
dohmatob's user avatar
  • 6,853
0 votes
1 answer
966 views

Bound the norm of sum of random vector that generated from standard basis

I have a question like this: Consider $N$ samples $X_1, X_2, ..., X_N$ that uniformly random generated from standard basis $\{e_i, i=1,2,...,d\}$, i.e. $(1,0,0,\cdots,0),(0,1,0,\cdots,0),(0,0,1,0,\...
Betty's user avatar
  • 25
3 votes
1 answer
176 views

Gaussian concentration/isoperimetric inequality with correlated Gaussian measure

Famous Gaussian concentration inequality states that: If $\mathrm{F}$ is 1 -Lip, and $\mathbb{E} F(X)=0,$ and $X=(X_1,...,X_n) \sim N\left(0, I_{n}\right),$ then we have for some absolute constant $C&...
Daniel Li's user avatar
  • 519
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
1 vote
1 answer
261 views

Concentration inequality for a function whose parameter depends on input samples

Concentration inequalities can be used to establish results such as sample mean cannot be too far from the actual population mean, and so on. For example, let $X_1 \ldots X_n$ be i.i.d instances of a ...
Arnab's user avatar
  • 615
3 votes
1 answer
114 views

Lower-bound for $\underset{p \le \gamma_d(A) \le q}{\inf} \gamma(A^\epsilon)$, where $\gamma_d$ is the standard gaussian distribution on $\mathbb R^d$

Let $\gamma_d = \gamma_1 \otimes \ldots \otimes \gamma_1$ be the standard Gaussian distribution on $\mathbb R^d$, where $d$ is a large positive integer. Given $\epsilon \ge 0$ and a measurable $A \...
dohmatob's user avatar
  • 6,853
9 votes
1 answer
350 views

Concentration inequalities for very rare events on a multiplicative scale

Let $E_1, \dots, E_N$ be independent events, each of probability $p$, where $p$ is very close to $0$. Let $A_N = \frac{1}{N} ( 1_{E_1} + \dots + 1_{E_N} )$ be the proportion of the events $E_i$ that ...
Adam's user avatar
  • 323
1 vote
0 answers
57 views

Good lower-bound for $\inf_{x \in \Delta_n} \|Gx\|$ where $G$ is an $N \times n$ random matrix with iid entries from $\mathcal N(0,1/\sqrt{N})$

Let $G$ be an $N \times n$ random matrix with independent entries distributed according to a centered Gaussian with variance $1/\sqrt{N}$ and let $n/N = \lambda \in (0, 1)$. Let $\Delta_n$ be the $(n-...
dohmatob's user avatar
  • 6,853
3 votes
2 answers
636 views

Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2$

Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that $$ X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2. $$ Question 1: Does the following hold? $$...
Siam's user avatar
  • 33
1 vote
1 answer
141 views

Central limit theorem for chi-squared random field on $\mathbb R^p$

Let $X:x \mapsto X(x)$ be a centered stationary Gaussian process on the $\Omega:=\mathbb R^p$, such that $X(x) \overset{d}{=}X(x')$ for all $x,x' \in \Omega$. Set $\sigma^2 := \mbox{Var}(X(0)) = \...
dohmatob's user avatar
  • 6,853
1 vote
1 answer
343 views

Concentration inequality for the supremum of $L_2$ norm of a vector-valued Gaussian process with iid components

Let $\Omega$ be a compact subset of $\mathbb R^p$ and let $f_1,\ldots,f_k$ be zero mean identically distrubuted Gaussian processes on $\Omega$ such that $f_1(x),\ldots,f_k(x)$ are independent $x \in \...
dohmatob's user avatar
  • 6,853
1 vote
1 answer
59 views

Characterization of random variables whose tensor powers have subexponential "small-ball" probabilities

Is there a succinct characterization of all random variables $\zeta$ on $\mathbb R$ with the following properties 1. Symmetry: $\zeta \overset{d}{=} - \zeta$. 2. Small-ball probability: there exists ...
dohmatob's user avatar
  • 6,853
2 votes
1 answer
212 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) ...
dohmatob's user avatar
  • 6,853
0 votes
1 answer
280 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 (...
dohmatob's user avatar
  • 6,853
3 votes
0 answers
103 views

Concentration inequalities for gradient flows induced by random fields

Let $G=(G(x))_{x \in \mathbb R^m}$ be a conservative random field with values in $\mathbb R^m$, for large positive integer $m$. That is, there exists a scalar random field $g=(g(x))_{x \in \mathbb R^m}...
dohmatob's user avatar
  • 6,853
3 votes
1 answer
1k views

Extension of Bernstein’s Inequality when the random variable is bounded with large probability

Bernstein’s Inequality can be stated as follows : Let $x_1, x_2, \dots, x_n$ be independent bounded random variables such that $\mathbb{E}[x_i] = 0$ and $|x_i| \leq \zeta$ with probability $1$ and let ...
Kom kom's user avatar
  • 33
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
5 votes
1 answer
273 views

Chernoff-style concentration inequality for k-tuples

I'm looking for a seemingly natural generalization of a Chernoff bound. In many scenarios, we have a distribution $D$ with support $\mathsf{Supp}(D)$, and some event $E \subset \mathsf{Supp}(D)$ ...
Geoffroy Couteau's user avatar
0 votes
1 answer
806 views

Concentration of $\ell_2$ norm of a vector sampled from a distribution

Let $X=(X_1,\ldots,X_n)$, where $X_i \sim P_{p_i}(0,\frac{1}{\lambda})$ are iid, $P_{p_i}$ is sub gaussian distribution for $i^\text{th}$ element, and 0 and $1/\lambda$ are mean and variance. I'm ...
newbie's user avatar
  • 61
3 votes
1 answer
182 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/...
dohmatob's user avatar
  • 6,853
24 votes
1 answer
1k views

A Rademacher ‘root 7’ anti-concentration inequality

Let $r_1,r_2,r_3,\dotsc$ be an IID sequence of Rademacher random variables, so that $\mathbb P(r_n=\pm1)=1/2$, and $a_1,a_2,\dotsc$ be a real sequence with $\sum_na_n^2=1$. For $S=\sum_na_nr_n$, does ...
George Lowther's user avatar
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
1 vote
1 answer
201 views

Upper bound for $\mathbb P(|f(A+XX^T)-f(A)| > \epsilon)$, where $A$ is a fixed pd matrix and $X$ has random iid entries

Let $A$ be a fixed $n$ by $n$ real symmetric positive definite matrix with eigenvalues $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n > 0$, and let $f(A):=\sum_{i=1}^n\log\lambda_i$, and let $X$ ...
dohmatob's user avatar
  • 6,853
3 votes
2 answers
402 views

Something between the Chernoff and Hoeffding bounds

Suppose I have $n$ independent 0-1 random variables $X_1, \cdots, X_n$ and I want to show a concentration of $X = \sum_i X_i$. I can use either the Chernoff bound or the Hoeffding bound. Suppose $E[...
user2316602's user avatar
-1 votes
1 answer
138 views

On the concentration of Lipschitz functions near its expectation, where the vector has identical but not independent, components

Consider the random vector $X:=(X_1\dots X_1) \in \mathbb{R}^n, X_1 \sim \mathcal{N}(0,1).$ Notice the identical components, they're identically distributed but not independent. Now, I was wondering ...
Learning math's user avatar
5 votes
1 answer
1k views

Explicit constant for Carbery–Wright inequality

The Carbery–Wright inequality is a seminal result about the anti-concentration of polynomials of Gaussian random variables. See e.g. Meka, Nguyen, and Vu - Anti-concentration for polynomials of ...
user134977's user avatar
0 votes
1 answer
378 views

Concentration of norm of linearly transformed normal random vector as dimension go to infinity

Earlier asked on MSE, but didn't get an answer, so posting here: Let $X=(X_1 \dots X_n) \in \mathbb{R}^n, X_i\sim N(0,1), iid.$ Let $B: \mathbb{R}^n \to \mathbb{R}^n $ be the diagonal linear map: $...
Learning math's user avatar
0 votes
1 answer
58 views

Good upper-bound for $\mathbb E_A[e^{-t\|A\|_2}]$, for $t\ge0$ and random m by n matrix with iid entries with law $N(0,1)$

Let $A$ be a random $m$-by-$n$ matrix with iid $N(0,1)$ entries, $m$ and $n$ large with $n/m \longrightarrow \alpha \in (0, 1)$ . Let $\|A\|_2$ be the largest singular value of $A$ (i.e the spectral ...
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
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
5 votes
1 answer
165 views

Is there an i.i.d sequence in the unit cube $[-1,1]^d$ with $\mathbb E \left[ \Big \| \sum_{i=1}^N X_N \Big \|_\infty\right] = \sqrt {dN}$?

There are loads of concentration results for sums of scalar-valued independent sums $X_1,X_2,\ldots, X_N$ with $\mathbb E[X_n]=0$. For example Hoeffding's Inequality says if all $|X_1|\le 1$ then $\...
Daron's user avatar
  • 1,955
0 votes
1 answer
140 views

Tail bounds for the absolute difference of a coupled pair of sub-Gaussian random variables

Let $P$ and $Q$ are sub-Gaussian distributions on $\mathbb R$, and $(X,X')$ be a coupling of $P$ and $Q$, i.e $(X,X') \sim \pi$ for some distribution on $\mathbb R^2$ with marginals $P$ and $Q$. ...
dohmatob's user avatar
  • 6,853
1 vote
1 answer
89 views

Use $\mathbb{P}(\vert \hat{s}_n-s\vert > x)\leq a(n,x)$ and $\mathbb{P}(\vert \hat{s}_n-s_n\vert > x)\leq b(n,x)$ to bound $\vert s_n - s\vert$

Let $s, s_n\in\mathbb{R}$ and $\hat{s}_n$ be a random variable. I have two concentration inequalities: $$\mathbb{P}(\vert \hat{s}_n-s\vert > x)\leq a(n,x)$$ for all $n\geq1$ and $x>0$; and $$\...
C. Trudon's user avatar
2 votes
0 answers
58 views

An upper bound on $\mathbb{E}\bigg[\bigg(\sum_{i=1}^{k}(X^{\top}A_{i}X)^{2}\bigg)^{q}\bigg]$

Let $X\in\mathbb{R}^{d}$ have independent, mean zero subgaussian entries, and $A_{1},\ldots,A_{k}$ be fixed $d\times d$ matrices that have zeros on the diagonal. I would like to upper bound the ...
nemo's user avatar
  • 129
3 votes
1 answer
1k views

Chernoff-type bound for sum of Bernoulli random variables, with outcome-dependent success probabilities

Let $X = (X_1, X_2, \ldots, X_n)$ be a sequence of (not necessarily independent) Bernoulli random variables where for each $i$, the success probability $\Pr[X_i = 1]$ itself is a random variable ...
Mathman's user avatar
  • 153
0 votes
1 answer
273 views

Sum of sequences of random variables, with variable success probabilities

Consider two sequences of (not necessarily independent) Bernoulli random variables $X_1, X_2, \ldots, X_n$ and $Y_1, Y_2, \ldots, Y_n$. Suppose that for any $i$, we have $\Pr[X_i = 1] = \Pr[Y_i = 1] = ...
Mathman's user avatar
  • 153
7 votes
3 answers
496 views

Chernoff-type bounds for a stopped sum of independent random variables

Let $Y_1, \ldots, Y_n$ and $X_1, \ldots, X_n$ be i.i.d. $p$-Bernoulli random variables and let $T \in \{0, \ldots, n\}$ be a stopping time for the process. From Wald's equation, we know $$ E\left[\...
Mathman's user avatar
  • 153
3 votes
1 answer
2k views

Gaussian concentration inequality

Recently I found a concentration inequality for infinite dimensional Gaussian r.v.s in this paper. Specifically, Lemma 4 on page 307 states (without a proof) that There exists a universal constant $...
d.k.o.'s user avatar
  • 185

1 2
3
4 5
7