Exercises

May 21'24

Let [math]X_1,\ldots,X_n[/math] be independent random variables such that [math]\E(X_i) = 0[/math] and [math]X_i \sim \subE(\lambda)[/math]. For any vector [math]a=(a_1, \ldots, a_n)^\top \in \R^n[/math], define the weighted sum

[[math]] S(a) = \sum_{i=1}^n a_iX_i\,, [[/math]]

Show that for any [math]t \gt 0[/math] we have

[[math]] \p(|S(a)| \gt t) \leq 2\exp \left[- C\big(\frac{t^2}{\lambda^2|a|_2^2}\wedge \frac{t}{\lambda|a|_\infty}\big)\right]. [[/math]]

for some positive constant [math]C[/math].

BBy Bot

May 21'24

A random variable [math]X[/math] has [math]\chi^2_n[/math] (chi-squared with [math]n[/math] degrees of freedom) if it has the same distribution as [math]Z_1^2+ \ldots +Z_n^2[/math], where [math]Z_1, \ldots, Z_n[/math] are \iid [math]\cN(0,1)[/math].

Let [math]Z \sim \cN(0,1)[/math]. Show that the moment generating function of [math]Y=Z^2-1[/math] satisfies
[[math]] \phi(s):=E\big[e^{sY}\big]=\left\{ \begin{array}{ll} \displaystyle\frac{e^{-s}}{\sqrt{1-2s}}& \text{if } s \lt 1/2\\ \infty & \text{otherwise} \end{array}\right. [[/math]]
Show that for all [math]0 \lt s \lt 1/2[/math],
[[math]] \phi(s)\le \exp\Big(\frac{s^2}{1-2s}\Big)\,. [[/math]]
Conclude that
[[math]] \p(Y \gt 2t+2\sqrt{t})\le e^{-t} [[/math]]
Hint: you can use the convexity inequality [math]\sqrt{1+u}\le 1+u/2.[/math]
Show that if [math]X \sim \chi^2_n[/math], then, with probability at least [math]1-\delta[/math], it holds
[[math]] X \le n+ 2 \sqrt{n\log(1/\delta)}+ 2\log(1/\delta) \,. [[/math]]

BBy Bot

May 21'24

Let [math]X_1, X_2 \ldots[/math] be an infinite sequence of sub-Gaussian random variables with variance proxy [math]\sigma_i^2=C(\log i)^{-1}[/math]. Show that for [math]C[/math] large enough, we get

[[math]] \E\big[\max_{i\ge 2} X_i \big] \lt \infty\,. [[/math]]

BBy Bot

May 21'24

Let [math]A=\{A_{i,j}\}_{\substack{1\le i\le n \\ 1\le j \le m}}[/math] be a random matrix such that its entries are \iid sub-Gaussian random variables with variance proxy [math]\sigma^2[/math].

Show that the matrix [math]A[/math] is sub-Gaussian. What is its variance proxy?
Let [math]\|A\|[/math] denote the operator norm of [math]A[/math] defined by
[[math]] \max_{x \in \R^m}\frac{|Ax|_2}{|x|_2}\,. [[/math]]
Show that there exits a constant [math]C \gt 0[/math] such that
[[math]] \E\|A\|\le C(\sqrt{m}+\sqrt{n})\,. [[/math]]

BBy Bot

May 21'24

Recall that for any [math]q \ge 1[/math], the [math]\ell_q[/math] norm of a vector [math]x \in \R^n[/math] is defined by

[[math]] |x|_q=\Big(\sum_{i=1}^n |x_i|^q\Big)^{\frac1q}\,. [[/math]]

Let [math]X=(X_1, \ldots, X_n)[/math] be a vector with independent entries such that [math]X_i[/math] is sub-Gaussian with variance proxy [math]\sigma^2[/math] and [math]\E(X_i)=0[/math].

Show that for any [math]q\ge2[/math], and any [math]x \in \R^d[/math],
[[math]] |x|_2\le |x|_qn^{\frac12-\frac1q}\,, [[/math]]
and prove that the above inequality cannot be improved
Show that for for any [math]q \gt 1[/math],
[[math]] \E|X|_q\le 4\sigma n^{\frac{1}{q}}\sqrt{q} [[/math]]
Recover from this bound that
[[math]] \E\max_{1\le i\le n} |X_i|\le 4e\sigma\sqrt{\log n}\,. [[/math]]

BBy Bot

May 21'24

Let [math]K[/math] be a compact subset of the unit sphere of [math]\R^p[/math] that admits an [math]\eps[/math]-net [math]\cN_\eps[/math] with respect to the Euclidean distance of [math]\R^p[/math] that satisfies [math]|\cN_\eps|\le (C/\eps)^d[/math] for all [math]\eps \in (0,1)[/math]. Here [math]C \ge 1[/math] and [math]d\le p[/math] are positive constants. Let [math]X \sim \sg_p(\sigma^2)[/math] be a centered random vector.

Show that there exists positive constants [math]c_1[/math] and [math]c_2[/math] to be made explicit such that for any [math]\delta \in (0,1)[/math], it holds

[[math]] \max_{\theta \in K} \theta^\top X \le c_1\sigma\sqrt{d \log (2p/d)} +c_2\sigma\sqrt{ \log(1/\delta)} [[/math]]

with probability at least [math]1-\delta[/math]. Comment on the result in light of Theorem.

BBy Bot

May 21'24

For any [math]K \subset \R^d[/math], distance [math]d[/math] on [math]\R^d[/math] and [math]\eps \gt 0[/math], the [math]\eps[/math]-covering number [math]C(\eps)[/math] of [math]K[/math] is the cardinality of the smallest [math]\eps[/math]-net of [math]K[/math]. The [math]\eps[/math]-packing number [math]P(\eps)[/math] of [math]K[/math] is the cardinality of the largest set [math]\cP \subset K[/math] such that [math]d(z, z') \gt \eps[/math] for all [math]z,z' \in \cP[/math], [math]z \neq z'[/math]. Show that

[[math]] C(2\eps)\le P(2\eps)\le C(\eps)\,. [[/math]]

BBy Bot

May 21'24

Let [math]X_1, \ldots, X_n[/math] be [math]n[/math] independent and random variables such that [math]\E[X_i]=\mu[/math] and [math]\var(X_i)\le \sigma^2[/math]. Fix [math]\delta \in (0,1)[/math] and assume without loss of generality that [math]n[/math] can be factored into [math]n=K\cdot G[/math] where [math]G=8\log(1/\delta)[/math] is a positive integers. For [math]g=1,\ldots, G[/math], let [math]\bar X_g[/math] denote the average over the [math]g[/math]th group of [math]k[/math] variables. Formally

[[math]] \bar X_g=\frac{1}{k}\sum_{i=(g-1)k+1}^{gk}X_i\,. [[/math]]

Show that for any [math]g= 1, \ldots, G[/math],
[[math]] \p\big[\bar X_g - \mu \gt \frac{2\sigma}{\sqrt{k}}\big] \le \frac{1}{4}\,. [[/math]]
Let [math]\hat \mu[/math] be defined as the median of [math]\{\bar X_1, \ldots, \bar X_G\}[/math]. Show that
[[math]] \p\big[\hat \mu -\mu \gt \frac{2\sigma}{\sqrt{k}}\big] \le \p\big[\cB \ge \frac{G}{2}\big]\,, [[/math]]
where [math]\cB\sim \Bin(G, 1/4)[/math].
Conclude that
[[math]] \p\big[\hat \mu -\mu \gt 4\sigma\sqrt{\frac{2\log (1/\delta)}{n}}\big] \le \delta [[/math]]
Compare this result with Corollary and Lemma. Can you conclude that [math]\hat \mu -\mu \sim \sg(\bar\sigma^2/n)[/math] for some [math]\bar\sigma^2[/math]? Conclude.

BBy Bot

May 21'24

The goal of this problem is to prove the following theorem:

Theorem (Johnson-Lindenstrauss Lemma)

Given [math] n [/math] points denoted by [math] X = \{x_1, \dots, x_n\} [/math] in [math] \R^d [/math], let [math] Q \in \R^{k \times d} [/math] be a random projection operator and set [math] P := \sqrt{\frac{d}{k}} Q [/math]. There is a constant [math] C \gt 0 [/math] such that if

[[math]] \begin{equation*} k \geq \frac{C}{\varepsilon^2} \log n, \end{equation*} [[/math]]

[math] P [/math] is an [math] \varepsilon [/math]-isometry for [math] X [/math], \ie

[[math]] \begin{equation*} (1 - \varepsilon) \| x_i - x_j \|_2^2 \leq \| P x_i - P x_j \|_2^2 \leq (1 + \varepsilon) \|x_i - x_j\|_2^2, \quad \text{for all } i, j \end{equation*} [[/math]]

with propability at least [math] 1 - 2 \exp(-c \varepsilon^2 k) [/math].

Convince yourself that if [math] d \gt n [/math], there is a projection [math] P \in \R^{n \times d} [/math] to an [math] n [/math] dimensional subspace such that [math] \| P x_i - P x_j \|_2 = \| x_i - x_j \|_2 [/math], \ie pairwise distances are exactly preserved.

Let [math] k \leq d [/math] be two integers, [math] Y = (y_1, \dots, y_d) \sim \cN(0, I_{d \times d} ) [/math] independent and identically distributed Gaussians and [math] Q \in \R^{d \times k} [/math] the projection onto the first [math] k [/math] coordinates, \ie [math] Qy = (y_1, \dots, y_k) [/math]. Define [math] Z = \frac{1}{\|Y\|}QY = \frac{1}{\|Y\|} (y_1, \dots, y_k) [/math] and [math] L = \|Z\|^2 [/math].

Show that [math] \E[L] = \frac{k}{d} [/math].
Show that for all [math] t \gt 0 [/math] such that [math] 1 - 2t(k \beta - d) \gt 0 [/math] and [math] 1 - 2t \beta k \gt 0 [/math],
[[math]] \begin{equation*} \label{eq:a} \p \left( \sum_{i = 1}^{k} y_i^2 \leq \beta \frac{k}{d} \sum_{i = 1}^{d} y_i^2 \right) \leq (1 - 2t(k \beta - d))^{-k/2} (1 - 2t \beta k)^{-(d-k)/2} \end{equation*} [[/math]]
(Hint: Show that [math] \E[\e^{\lambda X^2}] = \frac{1}{\sqrt{1 - 2 \lambda}} [/math] for [math] \lambda \lt \frac{1}{2} [/math] if [math] X \sim \cN(0,1) [/math].)
Conclude that for [math] \beta \lt 1 [/math],
[[math]] \begin{equation*} \label{eq:b} \p\left(L \leq \beta \frac{k}{d}\right) \leq \exp \left( \frac{k}{2} (1 - \beta + \log \beta) \right). \end{equation*} [[/math]]
Similarly, show that for [math] \beta \gt 1 [/math],
[[math]] \begin{equation*} \label{eq:c} \p\left(L \geq \beta \frac{k}{d}\right) \leq \exp \left( \frac{k}{2} (1 - \beta + \log \beta) \right). \end{equation*} [[/math]]
Show that for a random projection operator [math] Q \in \R^{k \times d} [/math] and a fixed vector [math] x \in \R^d [/math],
- [math] \E[\|Qx\|^2] = \frac{k}{d} \|x\|^2 [/math].
- For [math] \varepsilon \in (0, 1) [/math], there is a constant [math] c \gt 0 [/math] such that with probability at least [math] 1 - 2 \exp(-c k \varepsilon^2) [/math],
  [[math]] \begin{equation*} \label{eq:d} (1 - \varepsilon) \frac{k}{d} \| x \|^2 \leq \| Q x \|_2^2 \leq (1 + \varepsilon) \frac{k}{d} \|x\|_2^2. \end{equation*} [[/math]]
  (Hint: Think about how to apply the previous results in this case and use the inequalities [math] \log (1-\varepsilon) \leq -\varepsilon - \varepsilon^2/2 [/math] and [math] \log (1+\varepsilon) \leq \varepsilon - \varepsilon^2/2 + \varepsilon^3/3 [/math].)
- Prove Theorem.