第 10 部分：习题提示索引
第 10 部分：习题提示索引
本页由 10_1.pdf 的 MinerU OCR 生成，用来把原书 hints 回链到当前学习笔记证明。它不是答案页；当前项目的完整证明仍以学习笔记中的 proof-* 卡片为准。
难度标签的含义：基础验证适合用来检查定义和计算，核心证明对应章节主线中的常规推导，高价值挑战适合第二遍证明精读或专题回看。
覆盖概览
| 范围 | hint 数量 | 基础验证 | 核心证明 | 高价值挑战 | 学习笔记入口 |
|---|---|---|---|---|---|
| Appetizer | 8 | 2 | 6 | 0 | Appetizer |
| 第 1 章 | 15 | 2 | 13 | 0 | 第 1 章 |
| 第 2 章 | 38 | 7 | 29 | 2 | 第 2 章 |
| 第 3 章 | 46 | 11 | 31 | 4 | 第 3 章 |
| 第 4 章 | 40 | 1 | 36 | 3 | 第 4 章 |
| 第 5 章 | 20 | 2 | 16 | 2 | 第 5 章 |
| 第 6 章 | 27 | 3 | 20 | 4 | 第 6 章 |
| 第 7 章 | 22 | 5 | 13 | 4 | 第 7 章 |
| 第 8 章 | 26 | 4 | 11 | 11 | 第 8 章 |
| 第 9 章 | 23 | 1 | 14 | 8 | 第 9 章 |
Appetizer
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 0.1 | 核心证明 | Recall that $\\| x - y \\| _ { 2 } ^ { 2 } = \\| x \\| _ { 2 } ^ { 2 } - 2 \langle x , y \rangle + \\| y \\| _ { 2 } ^ { 2 }$ . (This follows by expanding $\\| x - y \\| _ { 2 } ^ { 2 } = \langle x -$ $y , x - y \rangle . )$ Use this formula for $\\| Z - \mathbb { E } Z \\| _ { 2 } ^ { 2 }$ | 证明 |
| 0.2 | 基础验证 | Check the identity $\mathbb { E } \Vert Z - a \Vert _ { 2 } ^ { 2 } - \mathbb { E } \Vert Z - \mu \Vert _ { 2 } ^ { 2 } = \Vert a - \mu \Vert _ { 2 } ^ { 2 }$ where $\mu = \mathbb { E } Z$ | 证明 |
| 0.4 | 核心证明 | (a) Select the signs independently at random. Calculate the expected squared norm of the random vector $\pm x _ { 1 } \pm x _ { 2 } \pm \cdot \cdot \cdot \pm x _ { n }$ using Example 0.3. | 证明 |
| 0.5 | 核心证明 | Choose $T = \{ e _ { 1 } , \ldots , e _ { n } \}$ where $e _ { i }$ are the standard basis vectors. Then conv(T) is an $( n - 1 ) \cdot$ dimensional simplex; draw a picture for $n = 3$ . Let x be the center of the simplex. All that remains is to calculate the distance from x to each $\left( k - 1 \right)$ -dimensional face of the simplex. | 证明 |
| 0.6 | 核心证明 | To prove the upper bound, multiply the sum of binomial coefficients by the quantity $( k / n ) ^ { k }$ replace this quantity by $( k / n ) ^ { j }$ in the left side, and use the binomial theorem. To prove the lower bound, use the definition of the binomial coefficient to express it as a product of k fractions; check that each fraction is lower bounded by $n / k .$ | 证明 |
| 0.7 | 核心证明 | Recall the scaling property of the volume in $\mathbb { R } ^ { n }$ used in the beginning of the proof of Theorem 0.0.4: the ball of radius r has volume $r ^ { n }$ times the volume of the unit ball. | 证明 |
| 0.8 | 基础验证 | Compute the CDF of $\\| X \\| _ { 2 } ,$ deduce the probability density function by differentiation, and then compute the expectation. | 证明 |
| 0.9 | 核心证明 | First, improve the bound on the number of balls in Corollary 0.0.3 using the following fact from elementary combinatorics: the number of ways to choose an unordered subset of k elements from an N-element set, with possible repetitions, is $\binom { N + k - 1 } { k }$ . Substitute $k = k _ { 0 } =$ $n / \log ( e N / n )$ and use Exercise 0.6 to bound the binomial coefficient by $C ^ { n }$ . Then follow the proof of Theorem 0.0.4. | 证明 |
第 1 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 1.3 | 基础验证 | (a) Use induction on m. At the induction step, represent $\textstyle \sum _ { i = 1 } ^ { m } \lambda _ { i } x _ { i }$ as a convex combination of two vectors, one of which is $x _ { m }$ and the other is some convex combination of $x _ { 1 } , \ldots , x _ { m - 1 }$ | 证明 |
| 1.4 | 核心证明 | To prove the upper bound, express a point x ∈ conv(T) as a convex combination of some points in $T$ and use Jensen inequality from Exercise 1.3. | 证明 |
| 1.7 | 核心证明 | Condition on the value of $n ,$ but otherwise follow the proof of the result in Example 1.4.2. | 证明 |
| 1.8 | 核心证明 | What is the probability that a given subset of k students is independent? How many subsets consisting of k students are there? Answer these questions and use the union bound. | 证明 |
| 1.9 | 基础验证 | Following the proof of the result in Example 1.4.2, the problem reduces to checking that n $\bar { \cdot } ( 1 - p _ { n } ) ^ { n - 1 } \dot { } 0$ | 证明 |
| 1.10 | 核心证明 | (b) Expanding yields E $\begin{array} { r } { { \bf \nabla } , S _ { n } ^ { 2 } = \sum _ { i = 1 } ^ { n } \mathbb { E } X _ { i } ^ { 2 } + \sum _ { i \neq j } \mathbb { E } X _ { i } X _ { j } } \end{array}$ . Interpret each term E $X _ { i } X _ { j }$ as the probability that both students i and $j$ are friendless. Compute this probability | 证明 |
| 1.11 | 核心证明 | Use Jensen inequality. | 证明 |
| 1.12 | 核心证明 | Write $\mathbb { E } \| X \| ^ { p }$ as E $[ \| X \| \| X \| ^ { p - 1 } ]$ and bound the second factor by its supremum. | 证明 |
| 1.13 | 核心证明 | (a) To prove the first inequality, use Jensen inequality (1.19) for the random vector $X =$ $( X _ { 1 } , \ldots , X _ { n } )$ . Guess which norm you should use here. To prove the second inequality, bound the maximum of n nonnegative numbers by the sum. (c) Consider independent Bernoulli random variables Ber $\left( p _ { n } \right)$ ; find the value of $p _ { n }$ that make the argument work | 证明 |
| 1.14 | 核心证明 | Both bounds follow from Jensen inequality. For the first bound, use (1.19) for the for the random vector $X \ = \ ( X _ { 1 } , \ldots , X _ { n } )$ and the $\ell ^ { p \ }$ norm. For the second bound, consider the convex function $\phi ( x ) = x ^ { p }$ | 证明 |
| 1.15 | 核心证明 | (b) Use the integrated tail formula for $f ( X )$ and make a change of variable $t = f ( s )$ | 证明 |
| 1.16 | 核心证明 | Consider the event $E = \{ X > \varepsilon \mathbb { E } X \}$ and decompose E X into $\mathbb { E } X \mathbf { 1 } _ { E }$ and $\mathbb { E } X \mathbf { 1 } _ { E ^ { c } }$ | 证明 |
| 1.17 | 核心证明 | (a) To prove the lower bound for $q < \infty ,$ assume first that all coefficients of x satisfy $\| x _ { i } \| \leq 1$ deduce that |xi $\mathbf { \Psi } ^ { \mid q } \leq \mid x _ { i } \mid ^ { p }$ and sum these inequalities. To prove the upper bound for $q < \infty$ use the Hölder inequality with exponent $p / q$ | 证明 |
| 1.18 | 核心证明 | Use the result of Exercise 1.17 for $q = \infty$ | 证明 |
| 1.19 | 核心证明 | (a) Assume first that $x _ { i } \geq 0$ for all i. In the case where $p = 1 , p ^ { \prime } = \infty .$ set $y = ( 1 , \ldots , 1 )$ In the case where $p = \infty , p ^ { \prime } = 1$ , set $\boldsymbol { y } = ( 0 , \ldots , 0 , 1 , 0 , \ldots , 0 )$ where the value 1 is at the coordinate $i _ { 0 }$ for which $\| x _ { i _ { 0 } } \| = \\| x \\| _ { \infty }$ . In the case where $p , p ^ { \prime } \in ( 1 , \infty )$ , set $y _ { i } : = \| x _ { i } \| ^ { p / p ^ { \prime } }$ for all i. | 证明 |
第 2 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 2.1 | 基础验证 | To prove the upper bound, take square root on both sides of the inequality $Y _ { n } \ge \mathbb { E } Y _ { n }$ and apply Markov inequality. To prove the lower bound, consider the event where all $X _ { i } \geq 1 / 2$ | 证明 |
| 2.3 | 基础验证 | (b) Using the formula from part $\mathrm { ( a ) }$ , express the Gaussian tail as $\begin{array} { r } { - \frac { 1 } { \sqrt { 2 \pi } } \int _ { t } ^ { \infty } \frac { f ^ { \prime } ( x ) } { x } } \end{array}$ dx and integrate by parts with $u = 1 / x$ and $v = f ( x )$ . Repeat. | 证明 |
| 2.4 | 核心证明 | (b) Integrate by parts and then use Proposition 2.1.2. | 证明 |
| 2.5 | 核心证明 | Compare Taylor expansions of both sides term by term. | 证明 |
| 2.7 | 核心证明 | Use the exponential moment method to bound the probability $\mathbb { P } \{ \sum _ { i = 1 } ^ { N } ( - X _ { i } / \varepsilon ) \geq - N \}$ | 证明 |
| 2.8 | 核心证明 | By convexity, the graph of the function $f ( x ) = e ^ { \lambda x }$ lies below the linear segment that joins the points $( a , f ( a ) )$ and $( b , f ( b ) )$ . Write down this observation as an inequality, substitute $x = X$ and take expectation on both sides. | 证明 |
| 2.9 | 核心证明 | (a) Use translation, dilation and the comparison inequality (Exercise $2 . 8 )$ (b) You should get $K ( \lambda ) = \lambda a + \log ( b - a e ^ { \lambda } )$ . Check that $K ^ { \prime \prime } ( \lambda ) = - a b e ^ { \lambda } / ( - a e ^ { \lambda } + b ) ^ { 2 }$ and use the AM-GM inequality $\begin{array} { r } { \sqrt { x y } \leq \frac { x + y } { 2 } } \end{array}$ for $x = - a e ^ { \lambda } $ and $y = b$ . Write down the linear approximation of $K ( \lambda )$ using Taylor theorem with a remainder in Lagrange form. | 证明 |
| 2.10 | 核心证明 | Follow the proof of Theorem 2.2.1. Use Hoeffding lemma to bound the MGF of each term. | 证明 |
| 2.11 | 基础验证 | Note that $\mathbb { P } \{ S _ { N } \le t \} = \mathbb { P } \{ - S _ { N } \ge - t \}$ and proceed as in the proof of Chernoff inequality. | 证明 |
| 2.12 | 核心证明 | Express the probability in terms of binomial coefficients. To lower bound the binomial coefficient, use the result of Exercise 0.6. To handle one of the remaining terms $( 1 - \mu / N ) ^ { N - t }$ prove that the smaller quantity $( 1 - \mu / N ) ^ { N - \mu }$ is bounded below by $e ^ { - \mu }$ | 证明 |
| 2.14 | 基础验证 | Check and use the numeric inequality ln $( 1 + x ) \ge x / ( 1 + x / 2 )$ for all $x \geq 0$ | 证明 |
| 2.15 | 核心证明 | Use the MGF comparison inequality (Exercise 2.8). | 证明 |
| 2.16 | 核心证明 | Argue that we can assume that $t \geq 1 0$ without loss of generality. Choose $B = \lfloor t ^ { 2 } / 4 \rfloor$ . If $B$ does not divide $N ,$ make one of the blocks larger than B. | 证明 |
| 2.17 | 核心证明 | (a) Using triangle inequality, check that the ratio of the densities of $X _ { i } \ \sim \ \mathrm { L a p } ( 0 , 1 )$ and $\dot { Y _ { i } } \sim \mathrm { L a p } ( \mu , 1 )$ is uniformly bounded by $e ^ { - \mu }$ . Write down the densities of $X$ and $Y$ Express the probabilities $\mathbb { P } \{ X \in B \}$ and $\mathbb { P } \{ Y \in B \}$ in terms of the densities of X and $Y .$ | 证明 |
| 2.18 | 基础验证 | The number of “bad" vertices has binomial distribution. Compute its mean and use Markov inequality. | 证明 |
| 2.19 | 核心证明 | The upper bound follows from Chernoff inequality (Theorem 2.3.1) as in Proposition 2.5.1. The lower bound is trickier because the degrees are not independent. $\mathrm { ( W h y ? ) }$ You can either try the second moment method (Exercise 1.10) or make independent proxies for the degrees as follows. Divide the set of vertices into two subsets $V ^ { \prime }$ and $\dot { V } ^ { \prime \prime }$ of roughly the same size. For each vertex $i \in V ^ { \prime \prime }$ , consider the number of vertices in $V ^ { \prime }$ connected to i. These degrees into $V ^ { \prime }$ denoted $d _ { i } ^ { \prime } ,$ are independent and provide a lower bound for the true degrees $d _ { i }$ Use the reverse Chernoff inequality (Exercise 2.12). | 证明 |
| 2.20 | 核心证明 | For a given pair of subsets $S , T ,$ the number of edges $e ( S , T )$ is a binomial random variable. Use Chernoff inequality followed by a union bound over all pair of subsets $S , T .$ | 证明 |
| 2.21 | 核心证明 | Apply Hoeffding inequality for the indicators of the wrong answers. | 证明 |
| 2.22 | 核心证明 | (a) Express $\mathbb { E } \| g \| ^ { p }$ as an integral; change variables to express it as the gamma function (1.30). (b) Use Stirling approximation (1.31). | 证明 |
| 2.23 | 核心证明 | Use Jensen inequality for the exponential function. | 证明 |
| 2.26 | 核心证明 | In the forward direction, use the definition and apply Jensen inequality. | 证明 |
| 2.27 | 核心证明 | (a) Use Gaussian tail bound (Proposition 2.1.2). | 证明 |
| 2.28 | 核心证明 | Use the integrated tail formula (Lemma 1.6.1) and the result of Exercise 2.27. | 证明 |
| 2.30 | 核心证明 | Combine Paley-Zygmund inequality (Exercise 1.16) with the subgaussian Khinchine inequality (Theorem 2.7.5). | 证明 |
| 2.31 | 核心证明 | Restate the bound (2.14) in terms of the subgaussian norm. Use it for $a _ { i } = 1 / N$ and apply centering (Lemma 2.7.8). | 证明 |
| 2.32 | 基础验证 | To prove that $\\| X + Y \\| _ { \psi _ { 2 } } \geq c \\| X \\| _ { \psi _ { 2 } } ,$ compute the MGF of $X + Y .$ Prove and use the fact that the MGF of Y is bounded below by 1. | 证明 |
| 2.33 | 核心证明 | (a) Express the MGF of the sum in terms the MGF of X. | 证明 |
| 2.34 | 核心证明 | (a) Let $X _ { i }$ follow a scaled, symmetrized Bernoulli distribution, meaning that $X _ { i }$ takes values ±qi with probability $p _ { i } / 2$ each and 0 with probability $1 - p _ { i }$ . Let the parameters pi decay rapidly (at a doubly exponential rate) and choose the scaling qi to make $\\| X _ { i } \\| _ { \psi _ { 2 } } \asymp \bar { 1 } .$ | 证明 |
| 2.35 | 核心证明 | (a) Assume $b = 1$ and bound the $L ^ { p }$ norm of X by $C { \sqrt { p / \log ( 2 / a ) } } .$ (b) Consider a scaled Bernoulli random variable and use Exercise $2 . 2 4 ( \mathrm { e } )$ | 证明 |
| 2.36 | 核心证明 | (a) Represent $Z ^ { 2 } = Z ^ { 1 / 2 } Z ^ { 3 / 2 }$ and use the Cauchy-Schwarz inequality. (b) Combine the extrapolation trick with Khintchine inequality (Theorem 2.7.5) for $p = 3$ | 证明 |
| 2.37 | 高价值挑战 | Use the union bound along with the subgaussian tail bound (Proposition 2.6.6(i)). | 证明 |
| 2.38 | 高价值挑战 | (a) Use Jensen inequality for exp $\left( \lambda \cdot \mathbb { E } \operatorname* { m a x } _ { i \leq N } g _ { i } \right)$ and replace the maximum of exponentials by their sum. Optimize in λ. (b) Using Proposition 2.1.2, show that max $_ { i \le N } \| g _ { i } \| \ge \sqrt { ( 1 - \varepsilon ) 2 }$ ln N with probability → 1. | 证明 |
| 2.39 | 核心证明 | On the one hand, the probability that ma $\mathrm { x } _ { i } \| X _ { i } \| < 2 \sqrt { \log N }$ can be bounded below by Markov inequality. On the other hand, it can be expressed in terms of the tail probability of [X|. | 证明 |
| 2.40 | 核心证明 | (a) To prove the triangle inequality $\\| X + Y \\| _ { G } \leq \\| X \\| _ { G } + \\| Y \\| _ { G }$ , first assume that X and Y are mean-zero. To bound the MGF of $X + Y .$ use the Hölder inequality with conjugate exponents that you optimize in the end. (): l hlo fuat (c) is also convenient to prove for mean-zero random variables first. | 证明 |
| 2.42 | 核心证明 | (a) To check that $\\| X \\| _ { \psi } = 0$ implies $X = 0 ~ { \mathrm { a . s . } }$ , use Jensen inequality. To prove the triangle inequality, write $\begin{array} { r } { \frac { \| \ddot { X } + \dot { Y } \| } { K + L } \leq \frac { \| X \| + \| \hat { Y } \| } { K + L } = \frac { K } { K + L } \frac { \| X \| } { K } + \frac { L } { K + L } \frac { \| Y \| } { L } } \end{array}$ | 证明 |
| 2.43 | 核心证明 | Comparing Propositions 2.6.1 (corresponding to $\alpha = 2 )$ and 2.8.1 (corresponding to $\alpha = 1 )$ you should be able guess the result for general α. | 证明 |
| 2.46 | 核心证明 | Express the bound in Corollary 2.9.2 as a sum of two exponentials, and use the integrated tail formula as in the proof of Proposition $2 . 6 . 1 ( \mathrm { i } ) { \Rightarrow } ( \mathrm { i i } )$ | 证明 |
| 2.47 | 基础验证 | Check the numeric inequalty $\begin{array} { r } { e ^ { z } \leq 1 + z + \frac { z ^ { 2 } / 2 } { 1 - \| z \| / 3 } } \end{array}$ for z satisfying $\| z \| < 3 ,$ apply it for $z = \lambda X$ and take expectations on both sides. | 证明 |
第 3 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 3.1 | 基础验证 | First use Exercise 0.2 for $a = { \sqrt { n } } ,$ and then use Theorem 3.1.1. | 证明 |
| 3.2 | 基础验证 | Begin as in the solution of Exercise 3.1, and then use the identity $x - y = ( x ^ { 2 } - y ^ { 2 } ) / ( x + y )$ for $x = \\| X \\| _ { 2 }$ and $y = { \sqrt { n } }$ | 证明 |
| 3.3 | 核心证明 | To prove the bound on $\mathbb { E } \Vert X \Vert _ { 2 } ,$ consider the Taylor approximation of $\sqrt { z }$ around $z = 1$ up to a cubic term, and use it for $\begin{array} { r } { z = \frac { 1 } { n } \\| X \\| _ { 2 } ^ { 2 } } \end{array}$ | 证明 |
| 3.4 | 核心证明 | (a) Write the spectral projection as $\begin{array} { r } { P _ { k } = \sum _ { i = 1 } ^ { k } v _ { i } v _ { i } ^ { \top } } \end{array}$ , compute $\\| \boldsymbol { P _ { k } } \boldsymbol { X } \\| _ { 2 } ^ { 2 }$ and use (3.6). (b) Write the projection as $\begin{array} { r } { P = \sum _ { i = 1 } ^ { k } { u _ { i } u _ { i } ^ { \top } } } \end{array}$ for some orthonormal vectors $u _ { i }$ . Proceed as in part (a). Arguing like in the proof of Proposition 3.2.2, express E|| $P X \\| _ { 2 } ^ { 2 }$ as $\textstyle \sum _ { j = 1 } ^ { n } \lambda _ { j } a _ { j }$ for some $a _ { j }$ satisfying $a _ { j } \leq 1$ and $\begin{array} { r } { \sum _ { j = 1 } ^ { n } \lambda _ { j } a _ { j } \leq \sum _ { j = 1 } ^ { n } \lambda _ { k } } \end{array}$ . Conclude that $\begin{array} { r } { \sum _ { j = 1 } ^ { n } \lambda _ { j } a _ { j } \leq \sum _ { j = 1 } ^ { k } \lambda _ { j } } \end{array}$ | 证明 |
| 3.5 | 高价值挑战 | For $p \leq$ log $n ,$ use Jensen inequality as in Exercise 1.14 and then recall how the absolute moments of subgaussian random variables grow. | 证明 |
| 3.6 | 高价值挑战 | For $p \geq \log n ,$ use Exercise 2.38. For $p \leq \log n$ , partition the set $\{ 1 , \ldots , n \}$ into approximately $n / e ^ { p }$ disjoint subsets of cardinality approximately $e ^ { p }$ each. When computing the $\ell ^ { p \ }$ norm of $X ,$ replace the sum of $\| X _ { i } \| ^ { p }$ on each subset by the maximum; use Exercise 1.14 to push the expected value inside, and then use Exercise 2.38 to lower bound each expected maximum. | 证明 |
| 3.7 | 核心证明 | (a) While this inequality does not follow directly from the result of Exercise $2 . 7 \ \mathrm { ( w h y ? ) }$ , you can prove it by a similar argument. Assume that $a = 0 ,$ square both sides of the inequality $\\| X \\| _ { 2 } \leq \varepsilon { \sqrt { n } }$ , choose a parameter $\lambda > 0 ,$ multiply both sides $\mathrm { b y } - \lambda ^ { 2 } / \varepsilon ^ { 2 }$ , exponentiate, and apply Markov inequality. At the end, optimize the bound in $\lambda .$ (b) Rewrite the conclusion of part (a) as $\mathbb { P } \{ Z \leq \delta \} \leq \delta ^ { n }$ where $Z = C K X / { \sqrt { n } } .$ and compute $\dot { \mathbb { E } } \big [ \dot { 1 } / Z \big ]$ by the integrated tail formula. To avoid a possible singularity, remember that you can always bound a probability by 1. | 证明 |
| 3.8 | 核心证明 | (a) With $\mu : = \mathbb { E } X$ , start by expressing $\\| \mu \\| _ { 2 } ^ { 2 } = \langle \mathbb { E } X , \mu \rangle$ | 证明 |
| 3.10 | 高价值挑战 | (b) Assume $\mu = 0$ for simplicity. If Σ is invertible, $Z = \Sigma ^ { - 1 / 2 } X$ does the job. Otherwise, arrange the eigenvalues $\lambda _ { i }$ in (3.7) so that they are are nonzero for $i \leq r$ and zero for $i > r ,$ Invert $\Sigma ^ { 1 / 2 }$ where it can be inverted, and complete it by isotropy on the rest of the space. For example, pick any mean-zero, isotropic random vector ${ \cal Y } ,$ and set $\begin{array} { r } { Z = \big ( \sum _ { i < r } \lambda _ { i } ^ { - 1 / 2 } v _ { i } v _ { i } ^ { \mathsf { T } } \big ) X + } \end{array}$ $\begin{array} { r } { \big ( \sum _ { i > r } v _ { i } v _ { i } ^ { \top } \big ) Y } \end{array}$ . Verify that $\Sigma ^ { 1 / 2 } Z = X$ (Since $\mathbb { E } \langle X , v _ { i } \rangle ^ { 2 } = 0$ for $i > r ,$ we have $\langle X , v _ { i } \rangle = 0$ a.s.) | 证明 |
| 3.11 | 核心证明 | (a) For any fixed $i ,$ note that $\sigma ( i )$ is uniformly distributed over all n indices. Similarly, for any fixed pair of distinct indices $( i , j )$ , the pair $( \sigma ( i ) , \sigma ( j ) )$ is uniformly distributed over all $n ^ { 2 ^ { - } } - n$ (ordered) pairs of distinct indices | 证明 |
| 3.13 | 核心证明 | (a) Combine Theorem 3.1.1 with Proposition $2 . 7 . 6$ (b) Prove separately that $\mathbb { E } \Vert X _ { 1 } \Vert _ { 2 } \gtrsim \sqrt { n }$ and $\begin{array} { r } { \mathbb { E } \operatorname* { m a x } _ { i \leq N } \left\\| X _ { i } \right\\| _ { 2 } \gtrsim \sqrt { \log N } } \end{array}$ using Exercise 2.38. | 证明 |
| 3.14 | 核心证明 | Recall (3.6). | 证明 |
| 3.16 | 核心证明 | (a) Use Cramer-Wold device from the proof of Proposition 3.3.5. First, verify that X has finite mean µ and covariance matrix $\Sigma .$ Then, compute the means and variances of all 1D marginals of X. Using the assumption, show that these match the means and variances of the 1D marginals of $\breve { Y } \sim N ( \mu , \Sigma )$ | 证明 |
| 3.17 | 核心证明 | Randomly flip the sign of $X \sim N ( 0 , 1 )$ | 证明 |
| 3.18 | 基础验证 | Think of G and UG as vectors in $\mathbb { R } ^ { n \times n }$ . Check that the mapping $G \mapsto U G$ is a linear orthogonal transformation, then use the rotation invariance of the normal distribution. | 证明 |
| 3.19 | 核心证明 | Represent A using part (a) and use the invariance for G established in Exercise 3.18. | 证明 |
| 3.20 | 高价值挑战 | Check that the random vector $( G u , G v ) \in \mathbb R ^ { 2 m }$ obtained by concatenation is isotropic. | 证明 |
| 3.23 | 基础验证 | (a) Choose x to be the unit vector in the direction of g1. Check that, with high probability, $\langle g _ { 1 } , x \rangle > { \sqrt { n } } / 2$ while $\langle g _ { 1 } , x \rangle < { \sqrt { n } } / 2$ for all $j = 2 , \ldots , \bar { N }$ | 证明 |
| 3.24 | 基础验证 | Let $r = \\| X \\| _ { 2 }$ . Compute the CDF of r and differentiate to deduce the density. | 证明 |
| 3.25 | 基础验证 | Use Exercise 3.24 to check that $\mathbb { E } \\| Y \\| _ { 2 } ^ { 2 } = n$ . Then argue like in the proof of Proposition 3.3.8. | 证明 |
| 3.26 | 核心证明 | Argue that we can write $\\| X \\| _ { \infty } = \\| g \\| _ { \infty } / \\| g \\| _ { 2 }$ where $g \sim N ( 0 , I _ { n } )$ . To prove the upper bound, use the Cauchy-Schwarz inequality and a small ball probability bound (Exercise 3.7). For the lower bound, use concentration of the norm to control $\\| g \\| _ { 2 }$ and a direct computation using independence to control g∞. | 证明 |
| 3.27 | 核心证明 | First, consider $n = 2$ (the unit circle in the plane), and compute the density of the first coordinate of X. Make a plot and note that the density at x is proportional to the arclength that projects onto the interval $[ x , x + \epsilon ]$ . Check that this is proportional to $g ( x ) = \varepsilon / \sqrt { 1 - x ^ { 2 } } +$ $o ( \varepsilon )$ . Now try $n = 3$ and then a general n. | 证明 |
| 3.28 | 核心证明 | (b) You should be able to express the squared distance to the cube as $\scriptstyle \sum _ { i = 1 } ^ { n } ( \left\| g _ { i } \right\| - a ) _ { + } ^ { 2 }$ , where $x _ { + } = \operatorname* { m a x } ( x , 0 )$ . Show that the expected distance is small if a is large enough. On the other hand, $\\| g \\| _ { 2 }$ is unlikely to be very small due to the concentration of the norm. | 证明 |
| 3.30 | 核心证明 | For example, use the criterion in Exercise 3.29. | 证明 |
| 3.33 | 基础验证 | Note that $\langle U X , v \rangle = \langle X , U ^ { \mathsf { T } } v \rangle$ and that $U ^ { \mathsf { T } }$ is an orthogonal matrix. | 证明 |
| 3.34 | 基础验证 | Note that Av is a mean-zero random vector with independent coordinates. Use Lemma 3.4.2 to bound its subgaussian norm. | 证明 |
| 3.35 | 核心证明 | Consider a one-dimensional marginal of $\textstyle \sum _ { i } X _ { i }$ , and use Proposition 2.7.1 to bound its subgaussian norm. | 证明 |
| 3.36 | 核心证明 | (a) Argue as in Lemma 3.4.2, but use triangle inequality instead of Proposition 2.7.1. | 证明 |
| 3.38 | 核心证明 | Exercise 3.14 describes the distribution of 1D marginals of X. Exercise 2.24(c) gives their subgaussian norm. Proposition 3.2.2 allows you to maximize that expression. | 证明 |
| 3.39 | 核心证明 | (a) Apply Lemma 2.8.5 and the triangle inequality. | 证明 |
| 3.40 | 核心证明 | (a) If Y is an independent copy of X, you can use Bernstein's inequality to bound $\| \langle X , Y \rangle \|$ above, and concentration of norm to bound $\\| X \\| _ { 2 }$ and $\\| Y \\| _ { 2 }$ below, all with high probability. (b) An idea is to slightly modify an isotropic vector near the origin. For example, flip a biased coin. If it is heads (likely), pick X as the first basis vector, appropriately scaled. If it is tails (unlikely), sample X from a normal distribution on the orthogonal hyperplane $\mathbb { R } ^ { n - 1 }$ | 证明 |
| 3.41 | 核心证明 | (a) Use a conditioning trick: condition on Y and apply Theorem 3.4.5. | 证明 |
| 3.42 | 核心证明 | Use the decomposition from Exercise 3.24. | 证明 |
| 3.43 | 核心证明 | To bound the subgaussian norm of a 1D marginal $\langle X , v \rangle$ , first get basic bounds on the $L ^ { 2 }$ and $L ^ { \infty }$ norms, and then interpolate them using Exercise 2.35. For the lower bound, pick v as a standard basis vector and use Exercise 2.24(e). | 证明 |
| 3.44 | 基础验证 | (a) Argue that the density of $X _ { 1 }$ at $u \in [ - r , r ]$ is proportional to $( r - \| u \| ) ^ { n - 1 }$ (b) Use symmetry to check that the coordinates of $X$ are uncorrelated. (c) Compute $\mathbb { P } \{ X _ { 1 } > r / 2 \}$ | 证明 |
| 3.45 | 基础验证 | Note that $\\| \langle X , x \rangle \\| _ { \psi _ { 2 } } \leq K \\| x \\| _ { 2 }$ and write down what it means by definition of the subgaussian norm. | 证明 |
| 3.46 | 核心证明 | (b) Combine Exercise 3.45 with the identity $\mathbb { E } \\| X \\| _ { 2 } ^ { 2 } = n$ , which follows from isotropy. | 证明 |
| 3.47 | 核心证明 | $\mathrm { { ( a ) \Rightarrow ( b ) } }$ : for any fixed $x ,$ the function $y \mapsto x ^ { \mathsf { T } } A y$ is linear and thus convex. Now recall (1.5) and Exercise 1.4. | 证明 |
| 3.49 | 核心证明 | (b) First, check that the function $f ( z ) = z ^ { \mathsf { T } } A z$ is convex, and so it must attain its maximum in $[ - 1 , 1 ] ^ { n }$ on the vertices of the cube. Now fix any $x , y \in \{ - 1 , 1 \} ^ { n }$ , use polarization identity to bound the bilinear form $\| x ^ { \mathsf { T } } A y \|$ by two quadratic forms, and bound these two quadratic forms using the fact above. Finally, apply the classical Grothendieck inequality (Theorem 3.5.1). | 证明 |
| 3.50 | 基础验证 | (b) Check that $f ( z ) = \left\| z ^ { \mathsf { T } } A z \right\|$ is separately convex. Then proceed as in Exercise 3.49. | 证明 |
| 3.52 | 核心证明 | (a) Express the objective function as $\begin{array} { r } { \frac { 1 } { 2 } \operatorname { t r } ( \tilde { A } Z Z ^ { \top } ) } \end{array}$ , where $\tilde { \boldsymbol { A } } = \left[ \begin{array} { c c } { \boldsymbol { 0 } } & { \boldsymbol { A } } \\ { \boldsymbol { A } ^ { \top } } & { \boldsymbol { 0 } } \end{array} \right]$ is called the Hermitian dilation of the matrix $A ,$ and $Z = { \left[ \begin{array} { l } { X } \\ { Y } \end{array} \right] }$ where X and Y are the matrices with rows $X _ { i } ^ { \mathsf { T } }$ and $Y _ { j } ^ { \mathsf { T } }$ respectively. Note that $Z Z ^ { \mathsf { T } }$ is the Gram matrix of the unit vectors $X _ { 1 } , \ldots , X _ { m } , Y _ { 1 } , \ldots , Y _ { n }$ Proceed as in the proof of Proposition 3.5.6. (b) Use Grothendieck inequality. | 证明 |
| 3.53 | 核心证明 | Use the rotation invariance of the standard normal distribution to reduce the problem to $\mathbb { R } ^ { 2 }$ Once in the plane, apply rotation invariance again to show that the probability of $\langle g , u \rangle$ and $\langle g , v \rangle$ having opposite signs is $\alpha / \pi$ where $\alpha \in [ 0 , \pi ]$ is the angle between u and v. A picture might help! | 证明 |
| 3.54 | 核心证明 | Consider cutting $G$ repeatedly. To find a lower bound on the probability of a success (finding a large cut), use Paley-Zygmund inequality (Exercise 1.16). Express the the expected number of experiments until success in terms of this probability. | 证明 |
| 3.56 | 核心证明 | (a) Argue that we can assume that $v = ( 1 , 0 , \ldots , 0 )$ and $\boldsymbol { u } = ( u _ { 1 } , u _ { 2 } , 0 , \dots , 0 )$ (b) Expand E $Z _ { u } Z _ { v }$ into four terms, and use Exercise $3 . 9$ and part (a). | 证明 |
| 3.57 | 核心证明 | Sum up the identities from Exercise $3 . 5 6 ( \mathrm { b } )$ for $u = u _ { i }$ and $v = u _ { j }$ with weights $a _ { i j }$ | 证明 |
| 3.58 | 核心证明 | Use randomized rounding (3.34). | 证明 |
第 4 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 4.4 | 核心证明 | (a) Use the spectral representation of both norms (Lemma 4.1.11). (b) Use Proposition 3.2.1(b). (c) Use (b) to write $\\| \dot { \boldsymbol { B } } \boldsymbol { A } \\| _ { F } ^ { 2 } = \mathbb { E } \\| \boldsymbol { B } \boldsymbol { A } \boldsymbol { g } \\| _ { 2 } ^ { 2 }$ where $g \sim N ( 0 , I _ { n } )$ | 证明 |
| 4.5 | 核心证明 | In fact, any nonnegative, weakly decreasing numbers $s _ { k }$ whose squares sum to $a ^ { 2 }$ satisfy $s _ { k } \leq a / \sqrt { k }$ | 证明 |
| 4.6 | 核心证明 | Express $\\| A ^ { k } x \\| _ { 2 } ^ { 2 }$ in terms of the SVD of A. Show that the first term of the sum dominates. | 证明 |
| 4.7 | 核心证明 | (a) Write $\begin{array} { r } { A x = \sum _ { i = 1 } ^ { n } x _ { i } A _ { i } . ~ \mathrm { ( b ) } } \end{array}$ For a contradiction, assume that $\\| A \\| = \\| A _ { 1 } \\| _ { 2 }$ but $A _ { 1 }$ is not orthogonal to A2. Take $x = ( 1 , \varepsilon , 0 , 0 , \ldots , 0 )$ and show that the function $f ( \varepsilon ) = \\| A x \\| _ { 2 } ^ { 2 } -$ $\\| A \\| ^ { 2 } \\| x \\| _ { 2 } ^ { 2 }$ can take positive values, contradicting the definition of the operator norm. | 证明 |
| 4.8 | 核心证明 | To bound |x Ay| for unit vectors x and $^ { y , }$ use the triangle inequality: $\begin{array} { r } { \| { \boldsymbol x } ^ { \top } { \boldsymbol A } { \boldsymbol y } \| = \| \sum _ { i j } A _ { i j } x _ { i } { \boldsymbol y } _ { j } \| \leq } \end{array}$ $\textstyle \sum _ { i j } \left\| A _ { i j } x _ { i } y _ { j } \right\|$ . Now apply the Cauchy-Schwarz inequality, splitting $\left\| A _ { i j } \right\|$ between the two terms. | 证明 |
| 4.10 | 核心证明 | To prove achievability, consider a matrix whose all entries equal 1, and on the other hand Walsh matrix (Exercise 4.9). | 证明 |
| 4.11 | 核心证明 | For a unit vector $x ,$ find $\\| P x - x / 2 \\| _ { 2 } ^ { 2 }$ and $\\| Q x - x / 2 \\| _ { 2 } ^ { 2 }$ , then apply the triangle inequality. | 证明 |
| 4.12 | 核心证明 | (a) A neat trick: block-diagonalize $P - Q$ . Take an orthogonal matrix $\bar { U } = \left\lceil U \quad U _ { \perp } \right\rceil$ whose first columns form U and span Im $P .$ Similarly, take an orthogonal matrix $\bar { V } = \bar { \| V \| } V \quad V _ { \perp } ]$ whose first columns form $V$ and span Im $Q$ . Then compute $\bar { U } ^ { \top } ( P - Q ) \bar { V } ^ { \top }$ and realize that it is a block matrix whose norm is the maximal norm of the two blocks. | 证明 |
| 4.13 | 核心证明 | Use Exercise 4.12 and Lemma 4.1.16; follow the Davis-Kahan proof (Theorem 4.1.15). | 证明 |
| 4.14 | 基础验证 | For "the only" part, compute $H ^ { 2 }$ . It is a block-diagonal matrix, so its eigenvalues should be easy to compute. | 证明 |
| 4.15 | 核心证明 | Apply Davis-Kahan inequality (Exercise 4.13 and Theorem 4.1.15) for the Hermitian dilation of A (Exercise 4.14). | 证明 |
| 4.17 | 核心证明 | In one direction, assume that property (c) in Lemma 4.1.17 holds, and consider the spectral projection of $P$ onto the top n eigenvalues of $A A ^ { \mathsf { T } }$ (what are they?). For the opposite direction, use Weyl inequality (Lemma 4.1.14). | 证明 |
| 4.19 | 核心证明 | Use convexity: recall from (1.3) that $B _ { 1 } ^ { n }$ , the unit ball of $\mathbb { R } ^ { n }$ in the $\ell ^ { 1 }$ norm, is the convex hull of $\pm$ canonical basis vectors; then use the maximal principle (Exercise 1.4). Deduce the result for the $2 $ ∞ norm by duality (Exercise $4 . 1 8 ( \mathrm { c } ) \}$ 1 | 证明 |
| 4.20 | 核心证明 | (a) Write $\\| A \\| _ { \infty \to 1 }$ as the maximum of $\| x ^ { \top } A y \|$ over the unit cubes, and use convexity as in Exercise 4.19. (b) One direction is trivial by setting $Z = x y ^ { \mathsf { T } }$ . In the other direction, express a rank-one matrix $Z$ as $Z = u \boldsymbol { v } ^ { \intercal }$ , argue that $\\| u \\| _ { \infty } \\| v \\| _ { \infty } \leq 1$ , and rescale u and v to rewrite $Z$ as $Z = x y ^ { \mathsf { T } }$ with $\\| x \\| _ { \infty } = 1$ and $\\| y \\| _ { \infty } \leq 1$ | 证明 |
| 4.21 | 核心证明 | To bound $\\| A \\| _ { \infty 1 }$ , express it as in Exercise 4.20(a). Decompose $\begin{array} { r } { x ^ { \mathsf { T } } A y = \sum _ { i , j } A _ { i j } x _ { i } y _ { j } } \end{array}$ into four sums according to the value of $( x _ { i } , y _ { j } ) \in \{ - 1 , 1 \} ^ { 2 } ,$ and bound each sum by the cut norm of $A .$ To bound the cut norm of $A ,$ fix subsets I and J and write $\textstyle \sum _ { i \in I { \boldsymbol { j } } \in J } A _ { i j }$ as $\begin{array} { r } { \sum _ { i , j } A _ { i j } \big ( \frac { 1 + x _ { i } } { 2 } \big ) \big ( \frac { 1 + y _ { i } } { 2 } \big ) } \end{array}$ for some vectors x and y with ±1 entries. Expand into four sums and bound each by the $\infty 1$ norm of A. | 证明 |
| 4.22 | 核心证明 | For the $\\| A \\| _ { \infty \to 1 }$ norm, use Exercise 3.52. For the $\\| A \\| _ { \infty 2 }$ norm, express it as the maximum of the quadratic form $\\| A x \\| _ { 2 } ^ { 2 } = x ^ { \mathsf { T } } ( A ^ { \mathsf { T } } A ) x$ and use Theorem 3.5.7. | 证明 |
| 4.24 | 核心证明 | (a) Consider a disconnected metric space, such as $T = \{ - 1 , 1 \}$ with with the usual Euclidean metric. (b) Argue by contradiction: if two balls are not ε-separated, the arithmetic mean of their centers lies in both $\varepsilon / 2 .$ -balls. | 证明 |
| 4.25 | 核心证明 | If an ε/2-ball centered at x $\notin K$ covers some point in $K ,$ say $y \in K$ , the ε-ball centered at y works even better in terms of covering K. | 证明 |
| 4.26 | 核心证明 | (a) Removing a point from K makes it impossible to place a ball with that center. Make an example where K is a 3-point set. (b) can be proved similarly to Exercise 4.25. | 证明 |
| 4.27 | 核心证明 | (a) Try induction on n. | 证明 |
| 4.28 | 核心证明 | Use Exercise $3 . 7$ for i.i.d. random variables $X _ { i } \sim \mathrm { U n i f } [ - { \textstyle { \frac { 1 } { 2 } } } , { \textstyle { \frac { 1 } { 2 } } } ] ;$ it gives a bound on the volume of the intersection of a unit cube with the Euclidean ball of radius $\varepsilon \sqrt { n }$ . Take a very small ε. | 证明 |
| 4.29 | 核心证明 | (a) This is a version of the integrated tail formula (Exercise 1.15(b)) for volume instead of probability. To deduce it, modify the proof of Lemma 1.6.1 by writing $\begin{array} { r } { { \bf \tilde { \Delta } } ^ { \prime } ( \\| x \\| ) = - \int _ { \\| x \\| } ^ { \infty } f ^ { \prime } ( t ) d t } \end{array}$ | 证明 |
| 4.30 | 核心证明 | (a) Exercise $\mathrm { 1 . 1 7 ( a ) ) }$ will help with the sandwiching. | 证明 |
| 4.31 | 核心证明 | To bound $\| { \mathcal { N } } \| ,$ note that the cubes $\begin{array} { r } { y + \frac { \varepsilon } { 2 \sqrt { n } } ( - 1 , 1 ) ^ { n } } \end{array}$ where $y \in \mathcal N$ are disjoint and contained in $( 1 + \textstyle { \frac { \varepsilon } { 2 } } ) B _ { 2 } ^ { n }$ . Run the volumetric argument like in the proof of Corollary 4.2.11. | 证明 |
| 4.33 | 核心证明 | Deduce from the error correction assumption that the closed balls of radius r centered at points $E ( x )$ are disjoint. Then run a version of a volumetric argument. | 证明 |
| 4.34 | 核心证明 | (a) Construct the expansion iteratively. Approximate x by $x _ { 1 } \in \mathcal N$ , normalize the residual $x - x _ { 1 }$ and approximate it by $x _ { 2 } \in { \mathcal { N } } .$ etc. | 证明 |
| 4.36 | 核心证明 | Use Lemma 4.4.1 to approximate $\\| A \\|$ with $\\| A x \\| _ { 2 }$ for some x ∈ ${ \mathcal { N } } ;$ then use Exercise 4.35 to approximate $\\| A x \\| _ { 2 }$ with $\langle A x , y \rangle$ for some $y \in \mathcal { M }$ . For symmetric matrices, modify the proof of Lemma 4.4.1 using the identity $x ^ { \mathsf { T } } A x - x _ { 0 } ^ { \mathsf { T } } A x _ { 0 } = ( x - x _ { 0 } ) ^ { \mathsf { T } } A ( x + x _ { 0 } )$ | 证明 |
| 4.37 | 高价值挑战 | Assume without loss of generality that $\mu = 1$ . Represent $\\| A x \\| _ { 2 } ^ { 2 } - 1$ as a quadratic form $\langle R x , x \rangle$ where $R = A ^ { \mathsf { T } } A - I _ { n }$ . Use Exercise 4.36 to compute the maximum of this quadratic form on a net. | 证明 |
| 4.38 | 核心证明 | Use the ε-net expansion (Exercise 4.34). | 证明 |
| 4.39 | 核心证明 | Fix an $\varepsilon / 2 .$ -net M of RBn with good size. It is enough to show that each point $y \in \mathcal { M }$ is within distance $\varepsilon / 2$ from some point g $/ \sqrt { n } \in R B _ { 2 } ^ { n }$ . For each $y \in { \mathcal { M } } .$ fix a ball $B _ { y }$ with radius $\textstyle r = { \frac { 1 } { 4 } }$ min(ε, R) satisfying $y \in B _ { y } \subset R B _ { 2 } ^ { n }$ . Find a lower bound on the probability that $g _ { 1 } / { \sqrt { n } }$ lands in a given ball $B _ { y }$ Use independence to show that at least one of the N vectors $g _ { i } / { \sqrt { n } }$ does so with high probability. Finally, apply a union bound over M. | 证明 |
| 4.40 | 核心证明 | Use Exercise 4.39 to show that the scaled random vectors $g _ { i } / { \sqrt { n } } , i > 1$ form an good net of ball of radius 10. Use Exercise 4.38 to show that the convex hull of these points contains a ball of radius 5. Meanwhile, with high probability, the first vector $g _ { 1 } / { \sqrt { n } }$ falls in the radius 5 ball, and thus in the convex hull of the other vectors. | 证明 |
| 4.41 | 高价值挑战 | Use the integrated tail formula (Lemma 1.6.1). | 证明 |
| 4.42 | 核心证明 | Bound the operator norm of A below by the Euclidean norm of the first column and first row. Use concentration of the norm (3.2) to complete the proof. | 证明 |
| 4.43 | 核心证明 | The proof of Theorem 4.4.3 only relies on one property of A: that $\langle A x , y \rangle = \langle A , x y ^ { \mathsf { T } } \rangle$ is subgaussian for any unit vectors $x , y .$ | 证明 |
| 4.44 | 核心证明 | (a) Combine Exercise $4 . 1 9 ( \mathrm { a } )$ with (2.22). (b) Combine Exercise 4.19(b) with Exercise 3.13. | 证明 |
| 4.45 | 核心证明 | The challenge is that, if $q$ is small, the second eigenvalue of the expected adjacency matrix $D = \mathbb { E } A$ might not be well separated from the first, making it hard to use Davis-Kahan inequality. To fix this, modify the algorithm to consider both top eigenvectors of D. The spectral projections onto the top two eigenvectors of D and A will still be close, thanks to a higher-dimensional version of Davis-Kahan (Lemma 4.1.16, Exercise 4.13). | 证明 |
| 4.47 | 高价值挑战 | Using the min-max theorem (Corollary 4.1.7), reduce the problem to the smallest singular value of a $m \times k$ random matrix. (Pick E to be a coordinate subspace.) | 证明 |
| 4.48 | 核心证明 | Rewrite the quantity in question as $\\| \bar { \Sigma } _ { m } - I _ { n } \\|$ where $\bar { \Sigma } _ { m }$ is the sample covariance matrix of the standard score of X. | 证明 |
| 4.50 | 核心证明 | (b) The idea is to use SVD to approximate a matrix $A = U \Sigma V ^ { \mathsf { T } }$ ≈ $U _ { 0 } \Sigma _ { 0 } V _ { 0 } ^ { \scriptstyle \mathsf { T } }$ by replacing one factor at a time. Construct an $( \varepsilon / 3 )$ -net to approximate $U$ using (b), an $\left( \varepsilon / 3 \right)$ -net to approximate V (similarly) and $\left( \varepsilon / 3 \right)$ -net to approximate Σ. You will find Exercise 4.4 helpful. (c) Consider m × n matrices with Frobenius norm $\leq 1$ and with only r first nonzero columns. | 证明 |
| 4.51 | 核心证明 | (b) Make a quantitative conclusion for 99.5% points: not just that the signs of $\langle X _ { i } , u \rangle$ and $\theta _ { i }$ agree, but that $\langle X _ { i } , u \rangle$ is well separated from zero, e.g. $\begin{array} { r } { \| \langle X _ { i } , u \rangle - \theta _ { i } \beta \| \le \frac { \beta } { 2 } } \end{array}$ where $\beta = \\| \mu \\| _ { 2 } .$ (e) Now that you know from (d) that v ≈ u, conclude that 99.5% of the points $X _ { i }$ satisfy $\vert \langle X _ { i } , v \rangle - \langle X _ { i } , u \rangle \vert \leq 0 . 1 \beta$ (To do this, write the sum of the squares of these quantities, and express it in terms of $\Sigma _ { m }$ and $u - v . )$ Now combine with (b). | 证明 |
第 5 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 5.3 | 核心证明 | If the conclusion of the first part fails, the complement $\boldsymbol { B } : = ( A _ { s } ) ^ { c }$ satisfies $\sigma ( B ) \ge 1 / 2$ Apply the blow-up Lemma 5.1.6 for B. | 证明 |
| 5.6 | 核心证明 | For the upper bound, assume that $\\| Z - \mathbb { E } Z \\| _ { \psi _ { 2 } } \leq K$ and use the definition of the median to show that $\mathbf { \dot { \left\| \right\|} } M - \mathbb { E } Z \leq C K$ | 证明 |
| 5.7 | 核心证明 | First replace the expectation by the median using Exercise 5.6. Then apply the assumption for the function $f ( x ) : = \mathrm { d i s t } ( x , A ) = \operatorname* { i n f } \left\{ d ( x , y ) : y \in A \right\}$ whose median is zero. | 证明 |
| 5.8 | 基础验证 | The ε-neighborhood of a half-space is still a half-space, and its Gaussian measure should be easy to compute. | 证明 |
| 5.9 | 核心证明 | (a) Use Gaussian concentration for $f ( x ) = \mathrm { m a x } _ { i } x _ { i } . \ ( \mathrm { b } )$ Argue that we can express $X _ { i } =$ $\mu _ { i } + \langle g , v _ { i } \rangle$ for some non-random $\mu _ { i } , v _ { i }$ and $g \in N ( 0 , \hat { I _ { n } } )$ . Then use Gaussian concentration. | 证明 |
| 5.10 | 核心证明 | Bound $\| \mu _ { p } - \mu _ { 1 } \|$ where $\mu _ { p } : = \\| Z \\| _ { L ^ { p } }$ | 证明 |
| 5.14 | 高价值挑战 | Apply norm concentration (Theorem 3.1.1) for the random vector Az. | 证明 |
| 5.15 | 核心证明 | Consider an orthogonal basis in $\mathbb { R } ^ { N }$ | 证明 |
| 5.17 | 高价值挑战 | (a) Symmetric commuting matrices are simultaneously diagonalizable. (b) Find $2 \times 2$ matrices such that $0 \preceq X \preceq Y$ but $\boldsymbol { X } ^ { 2 } \not \propto \boldsymbol { Y } ^ { \flat }$ | 证明 |
| 5.18 | 核心证明 | (a) First consider the case where $Y = I _ { n } .$ Next, multiply the inequality $0 \preceq X \preceq Y$ by $Y ^ { - 1 / 2 }$ (justify why you can do that), and use the identity case proved before. (c) Argue that the matrix version of the formula in (b) is ln $\begin{array} { r } { X = \int _ { 0 } ^ { \infty } { \bigl [ } ( 1 + t ) ^ { - 1 } I _ { n } - ( X + } \end{array}$ $t I _ { n } ) ^ { - 1 } ]$ dt, and use part (a). | 证明 |
| 5.20 | 核心证明 | Check that matrix Bernstein inequality implies that $\begin{array} { r } { \left\\| \sum _ { i = 1 } ^ { N } X _ { i } \right\\| \lesssim \left\\| \sum _ { i = 1 } ^ { N } \mathbb { E } X _ { i } ^ { 2 } \right\\| ^ { 1 / 2 } \sqrt { \log n + u } + } \end{array}$ $K ( \log n + u )$ with probability at least $1 - 2 e ^ { - u }$ . Then use the integrated tail formula from Lemma $1 . 6 . { \dot { 1 } }$ | 证明 |
| 5.21 | 基础验证 | Proceed like in the proof of Theorem 5.4.1. Instead of Lemma 5.4.10, check that E $\exp ( \lambda \varepsilon _ { i } A _ { i } ) \preceq$ $\exp ( \lambda ^ { 2 } A _ { i } ^ { 2 } / 2 )$ just like in the proof of Hoeffding inequality (Theorem 2.2.1). | 证明 |
| 5.22 | 核心证明 | Use the integrated tail formula from Exercise 1.15(c) | 证明 |
| 5.23 | 核心证明 | Use Hermitian dilation (Exercise 4.14). | 证明 |
| 5.24 | 核心证明 | Use Hermitian dilation (Exercise 4.14). | 证明 |
| 5.25 | 核心证明 | Loops contribute only to the diagonal of the adjacency matrix. Isolate this diagonal matrix and bound its norm. | 证明 |
| 5.28 | 核心证明 | (a) Let $X \sim \operatorname { U n i f } ( { \sqrt { n } } e _ { 1 } , \ldots , { \sqrt { n } } e _ { n } )$ where ei are the standard basis vectors in $\mathbb { R } ^ { n }$ . Check that X is isotropic. Argue that, if m n log n, the sample $X _ { 1 } , \ldots , X _ { n }$ with high probability misses at least one basis vector (this is related to a coupon collector problem), making the sample covariance matrix $\Sigma _ { m }$ have at least one zero on the diagonal. | 证明 |
| 5.30 | 核心证明 | Use covariance estimation for the isotropic random vector $X \sim \operatorname { U n i f } ( { \sqrt { m } } u _ { 1 } , \dots , { \sqrt { m } } u _ { m } )$ (recall Proposition 3.3.11(iv)). | 证明 |
| 5.31 | 核心证明 | Just like in the proof of Theorem 4.6.1, derive the conclusion from a bound on $\begin{array} { r } { \frac { 1 } { m } A ^ { \top } A - I _ { n } = } \end{array}$ $\begin{array} { r } { \frac { 1 } { m } \sum _ { i = 1 } ^ { m } A _ { i } A _ { i } ^ { \top } - I _ { n } } \end{array}$ . Use the high-probability version of covariance estimation (5.28). | 证明 |
| 5.32 | 核心证明 | Consider the random vector $X \in \mathbb { R } ^ { n }$ that picks the random row of A, i.e. $X \ = \ A _ { i }$ with probability $1 / N ,$ and use the general covariance estimation result (Theorem 5.6.1) followed by Weyl inequality (Lemma 4.1.14). | 证明 |
第 6 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 6.1 | 基础验证 | Modify the proof of Theorem 6.1.1. Remove the diagonal from A and do steps 1 and 2. Then, in step 3, include the diagonal into Z. | 证明 |
| 6.2 | 基础验证 | (a) Use Theorem 6.1.1 for $F ( x ) = x ^ { p } . \ ( \mathrm { b } )$ Which $F$ is naturally suited for this? | 证明 |
| 6.4 | 核心证明 | We want to decouple $\begin{array} { r } { \mathbb { E } \\| \sum _ { i , j } A _ { i j } X _ { i } X _ { j } \\| } \end{array}$ where $X _ { i }$ are i.i.d. Ber(p) and $A _ { i j }$ is the n × n matrix with only the $( i , j )$ entry of A kept. Follow the proof of Theorem 6.1.1 using the operator norm as $F .$ Step 3 is trivial thanks to Exercise $4 . { \overset { \cdot } { 2 } } ( \mathrm { d } )$ | 证明 |
| 6.5 | 高价值挑战 | Let X have a rotation-invariant distribution, and let |X2 take two values: n with probability $1 / n$ and $\sqrt { n }$ with probability $1 - 1 / n$ | 证明 |
| 6.6 | 核心证明 | (a) Use Proposition 6.2.1. | 证明 |
| 6.7 | 核心证明 | Use the singular value decomposition for A and rotation invariance of $X \ \sim \ N ( 0 , I _ { n } )$ to simplify and control the quadratic form $X ^ { \mathsf { T } } A X$ | 证明 |
| 6.8 | 高价值挑战 | The quadratic form is now $X ^ { \mathsf { T } } A X$ where X is a d × n random matrix with columns $X _ { i } . \mathrm { A p p l y }$ Gaussian replacement (Lemma $6 . 2 . 3 )$ and redo the Gaussian MGF computation (Lemma 6.2.4). | 证明 |
| 6.9 | 基础验证 | First swap X for $g \sim N ( 0 , I _ { m } )$ like in Proposition 6.2.1. Then, compute using Gaussian properties as in Lemma $6 . 2 . 4$ | 证明 |
| 6.10 | 核心证明 | Start as in the proof of Proposition 6.2.1 and use the MGF bound from Exercise 6.9. | 证明 |
| 6.11 | 核心证明 | Find B such that $A = B ^ { \mathsf { T } } B$ and use Exercise 6.10. | 证明 |
| 6.12 | 核心证明 | First, use Exercise 6.10 to show that if a random vector Y has mean-zero, covariance matrix Σ and satisfies $\\| \langle Y , u \rangle \\| _ { \psi _ { 2 } } \leq K \\| \langle Y , u \rangle \\| _ { L ^ { 2 } }$ for all $u \in \mathbb { R } ^ { n }$ , then $\\| Y \\| _ { 2 } \le C K \sqrt { \mathrm { t r } \Sigma } +$ $C K \sqrt { \\| \Sigma \\| \log ( 1 / \alpha ) }$ with probability at least $_ { 1 - \alpha }$ . Then apply this for $\begin{array} { r } { Y = \frac { 1 } { \sqrt { N } } \sum _ { i = 1 } ^ { N } ( X _ { i } - \mu ) } \end{array}$ | 证明 |
| 6.13 | 核心证明 | Apply Hanson-Wright inequality (Theorem 6.2.2) for $A = B ^ { \mathsf { T } } B$ and $t = \varepsilon \\| B \\| _ { F } ^ { 2 }$ , and replace $\\| B ^ { \mathsf { T } } B \\| _ { F } \log \\| B ^ { \mathsf { T } } \\| \\| B \\| _ { F }$ using Exercise $4 . 4 ( \mathrm { c } )$ . This will give a deviation inequality for $\\| B X \\| _ { 2 } ^ { 2 }$ Convert it to a deviation inequality for $\\| { \dot { B } } { \dot { X } } \\| _ { 2 }$ like in the proof of Theorem 3.1.1. | 证明 |
| 6.15 | 高价值挑战 | Express the cut as a quadratic form like in (3.31) and apply Hanson-Wright inequality (Theorem 6.2.2). You can compute the Frobenius norm of A exactly, and the operator norm can only be smaller. | 证明 |
| 6.18 | 核心证明 | To prove $\mathbb { E } \\| X + v \\| \geq \mathbb { E } \\| X \\|$ , argue that $\mathbb { E } \\| X + v \\| = \mathbb { E } \\| X + \varepsilon v \\|$ where ε is an independent Rademacher, and push the expectation over ε inside the norm. | 证明 |
| 6.21 | 核心证明 | Use the result of Exercise 6.20 with $F ( x ) = \exp ( \lambda x )$ to bound the moment generating function, or with $F ( x ) = \exp ( c x ^ { 2 } )$ . | 证明 |
| 6.22 | 核心证明 | Argue that the probability equals $\begin{array} { r } { \mathbb { P } \{ \| \sum _ { i = 1 } ^ { N } \varepsilon _ { i } X _ { i } \| \ge t ( \sum _ { i = 1 } ^ { N } X _ { i } ^ { 2 } ) ^ { 1 / 2 } \} } \end{array}$ where $\varepsilon _ { i }$ are independent Rademacher random variables. Condition on $( X _ { i } )$ and use Hoeffding inmequality to bound the conditional probability. Then use the law of total expectation. | 证明 |
| 6.23 | 核心证明 | (a) Use the lp norm definition to express it as a sum, swap p for 2 by monotonicity (Exercise 1.11), apply the variance sum formula, and use monotonicity again. (b) Use symmetrization (Exercise 6.20), condition on $( X _ { i } )$ and use part $\mathrm { ( a ) }$ | 证明 |
| 6.24 | 高价值挑战 | (a) Swap exponent 2 for p by monotonicity (Exercise 1.11), use the $\ell ^ { p \ }$ norm definition to express it as a sum, apply Khintchine inequality (Theorem 2.7.5) and then the triangle inequality triangle inequality in $\left( \mathbb { R } ^ { n } , \left. \cdot \right. _ { p / 2 } \right)$ (b) Use symmetrization as in Exercise ${ \dot { 6 } } . 2 3 ( \mathrm { b } )$ | 证明 |
| 6.25 | 核心证明 | Repeat the proof of Theorem 0.0.2, using Exercises 6.23 and 6.24 instead of the variance-ofsum identity. | 证明 |
| 6.26 | 核心证明 | Apply symmetrization, then use Khintchine inequality conditionally on $( X _ { i } )$ , and finally the triangle inequality in $L ^ { p / 2 }$ | 证明 |
| 6.27 | 核心证明 | Using the equality $a ^ { 2 } - b ^ { 2 } = ( a - b ) ( a + b )$ , reduce the problem to bounding the $L ^ { p }$ norm of $\\| X \\| _ { 2 } ^ { \frac { 1 } { 2 } } - n$ . Expand $\\| X \\| _ { 2 } ^ { 2 }$ and use Marcinkiewicz-Zygmund inequality (Exercise 6.26). | 证明 |
| 6.28 | 核心证明 | Apply Theorem 6.4.1 for the Hermitial dilation of A (see Exercise 4.14). | 证明 |
| 6.29 | 核心证明 | Let A be a block-diagonal matrix with $n / k$ independent blocks, each a $k \times k$ symmetric random matrix with independent Rademacher entries on and above diagonal. Condition on a block being all ones, then pick the value of k at the end. | 证明 |
| 6.30 | 核心证明 | Fix i and use Bernstein inequality to get a tail bound for $\begin{array} { r } { \sum _ { j = 1 } ^ { n } ( \delta _ { i j } - p ) ^ { 2 } } \end{array}$ . Conclude by taking a union bound over $i = 1 , \ldots , n$ | 证明 |
| 6.33 | 核心证明 | Use symmetrization and matrix Khintchine inequality (Theorem 5.4.14) tp bound $\mathbb { E } \\| S - \mathbb { E } S \\|$ in terms of $\begin{array} { r } { \mathbb { E } \\| \sum _ { i } Z _ { i } ^ { 2 } \\| ^ { 1 / 2 } } \end{array}$ , then bound the latter quantity by (E maxi $\\| Z _ { i } \\| \cdot \mathbb { E } \\| S \\| ) ^ { 1 / 2 }$ . This should give you $\mathbb { E } \\| S - \mathbb { E } S \\| \lesssim { \sqrt { \mathbb { E } \\| S \\| \cdot L } }$ where $L = \log ( n ) \mathbb { E } \operatorname* { m a x } _ { i } \\| Z _ { i } \\|$ . Finally, replace $\mathbb { E } \\| S \\|$ with the larger quantity $\mathbf { \dot { \mathbb { E } } } \\| \mathbf { \dot { \boldsymbol { S } } } - \mathbb { E } \mathbf { \dot { \boldsymbol { S } } } \\| + \\| \mathbb { E } \boldsymbol { S } \\|$ and solve the resulting inequality. | 证明 |
| 6.34 | 核心证明 | Apply Theorem 6.33 for ${ \cal Z } _ { i } \ = \ { \textstyle \frac { 1 } { m } } X _ { i } X _ { i } ^ { \top }$ . To bound $L ,$ use the assumption and Proposition 3.2.1(b). | 证明 |
| 6.36 | 核心证明 | Use symmetrization, contraction principle (Theorem 6.6.1) conditioned on $( X _ { i } )$ , and finish by applying symmetrization again. | 证明 |
第 7 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 7.1 | 基础验证 | (b) Combine $\\| X _ { t } - X _ { s } \\| _ { L ^ { 2 } }$ and $\\| X _ { t } + X _ { s } \\| _ { L ^ { 2 } }$ | 证明 |
| 7.2 | 基础验证 | Argue like in the proof of Lemma 6.3.2. | 证明 |
| 7.3 | 核心证明 | (a) For any $t , s \in T .$ we need to find $t ^ { \prime } , s ^ { \prime } \in T$ so that $t _ { 1 } + \phi ( t _ { 2 } ) + s _ { 1 } - \phi ( s _ { 2 } ) \leq t _ { 1 } ^ { \prime } + t _ { 2 } ^ { \prime } + s _ { 1 } ^ { \prime } - s _ { 2 } ^ { \prime }$ Set $( t ^ { \prime } , s ^ { \prime } )$ as either $( t , s )$ or $( s , t )$ . Rewrite the inequality for both cases to see how to choose. (b) Condition on $\varepsilon _ { 1 } , \ldots , \varepsilon _ { n - 1 }$ and apply part (a). | 证明 |
| 7.4 | 核心证明 | Theorem 6.6.1 may help. | 证明 |
| 7.5 | 核心证明 | It might be simpler to think about increments $\\| X _ { t } - X _ { s } \\| _ { L ^ { 2 } }$ instead of the covariance matrix. | 证明 |
| 7.6 | 核心证明 | Write $X = \Sigma ^ { 1 / 2 } Z$ for $Z \sim N ( 0 , I _ { n } )$ and note that $\begin{array} { r } { X _ { i } = \sum _ { k = 1 } ^ { n } ( \Sigma ^ { 1 / 2 } ) _ { i k } Z _ { k } } \end{array}$ and E $X _ { i } f ( X ) =$ $\begin{array} { r } { \sum _ { k = 1 } ^ { n } ( \sum ^ { 1 / 2 } ) _ { i k } \mathbb { E } Z _ { k } f ( \Sigma ^ { 1 / 2 } Z ) } \end{array}$ . Apply the univariate Gaussian integration by parts (Lemma 7.2.3) for $\mathbb { E } Z _ { k } f ( \Sigma ^ { 1 / 2 } Z )$ conditionally on all random variables except $Z _ { k } \sim N ( 0 , 1 )$ , and simplify. | 证明 |
| 7.7 | 核心证明 | (b) The following identity can help simplify the expression: if $\textstyle \sum _ { i = 1 } ^ { n } p _ { i } = 1 $ then $\begin{array} { r } { \sum _ { i , j = 1 } ^ { n } \sigma _ { i j } \mathopen { } \mathclose \bgroup \left( \delta _ { i j } p _ { i } - \aftergroup \egroup \right. } \end{array}$ $\begin{array} { r } { p _ { i } p _ { j } ) = \frac { 1 } { 2 } \sum _ { i \neq j } ( \sigma _ { i i } + \sigma _ { j j } - 2 \sigma _ { i j } ) p _ { i } p _ { j } } \end{array}$ . Check it and use it for $\sigma _ { i j } = \Sigma _ { i j } ^ { X } - \Sigma _ { i j } ^ { Y }$ and $p _ { i } = p _ { i } ( Z ( u ) )$ | 证明 |
| 7.9 | 核心证明 | Use Gaussian Interpolation Lemma 7.2.5 for $\begin{array} { r } { f ( \boldsymbol x ) = \prod _ { i } \left[ 1 - \prod _ { i } h ( x _ { i j } ) \right] } \end{array}$ where $h ( x )$ is an approximation to the indicator function $\mathbf { 1 } _ { \{ x \leq \tau \} }$ , as in the proof of Slepian inequality. | 证明 |
| 7.10 | 高价值挑战 | Add and subtract the cross-term wv, factor, and expand the Frobenius norm squared like this: $\\| A - B \\| _ { F } ^ { 2 } = \\| A \\| _ { F } ^ { 2 } + \\| B \\| _ { F } ^ { 2 } - 2 \operatorname { t r } ( A ^ { \top } B )$ | 证明 |
| 7.12 | 核心证明 | Consider Taylor expansion of $\sqrt { y }$ about $y = 1$ with three leading terms, and substitute $y = \\| g \\| _ { 2 } ^ { 2 } / n$ to approximate $\mathbb { E } \Vert g \Vert _ { 2 } / { \sqrt { n } }$ | 证明 |
| 7.13 | 核心证明 | (a) Relate the smallest singular value to the min-max of a Gaussian process: $s _ { n } ( A ) \ =$ $\begin{array} { r } { \operatorname* { m i n } _ { u \in S ^ { n - 1 } } \operatorname* { m a x } _ { v \in S ^ { m - 1 } } \langle A u , \bar { v } \rangle } \end{array}$ . Apply Gordon inequality (without the requirement of equal variances) to show that $\mathbb { E } s _ { n } ( A ) \geq \mathbb { E } \\| h \\| _ { 2 } - \mathbb { E } \\| g \\| _ { 2 }$ where $h \sim N ( 0 , I _ { m } )$ and $g \sim N ( 0 , I _ { n } )$ Then use Exercise 7.12. 11 (b) Proceed like in the proof of Corollary 7.3.2, using Weyl inequality (Lemma 4.1.14). | 证明 |
| 7.15 | 基础验证 | (b) Use rotation invariance of Gaussian distribution. (e) Use property (d), replace T with $- T$ , and use property (d) again. (g) Use Sudakov-Fernique comparison inequality. | 证明 |
| 7.16 | 核心证明 | The proof of Proposition 7.5.2(f) suggests the two extreme examples: an interval and a ball | 证明 |
| 7.18 | 核心证明 | Argue that we can assume that A is diagonal. To show $\langle A , B \rangle \leq \\| A \\| _ { * } \\| B \\|$ , write the trace as a sum and use that ma $\mathrm { x } _ { i } \| B _ { i i } \| \leq \\| B \\|$ . For the reverse inequality, pick B to be diagonal with entries $\mathrm { s i g n } ( A _ { i i } )$ | 证明 |
| 7.17 | 核心证明 | Use duality (1.6) together with Exercises 3.5 and 3.6. | 证明 |
| 7.19 | 高价值挑战 | Use Exercise 7.18 to write the Gaussian width as the expected nuclear norm of a Gaussian random matrix. Then use the operator norm bound (see Remark 4.4.4) to get an upper bound, and the intermediate singular value bound (Exercise 4.47 with $k = c n )$ for the lower bound. | 证明 |
| 7.20 | 核心证明 | For the upper bound, write $x \ = \ ( x - y ) + y$ , then use triangle inequality and Proposition 7.5.11(a). | 证明 |
| 7.21 | 核心证明 | (a) By rotation invariance, assume that E is a coordinate subspace. | 证明 |
| 7.23 | 基础验证 | (a) It is easier to compute the squared version of the Gaussian width, $h ( A ( B _ { 2 } ^ { n } ) )$ , which is equivalent to the original one (Lemma 7.5.11). | 证明 |
| 7.24 | 基础验证 | It is enough to check the rotation invariance of the distribution of $B z$ | 证明 |
| 7.26 | 高价值挑战 | To obtain the bound E diam $( P T ) \gtrsim w _ { s } ( T )$ , reduce $P$ to a one-dimensional projection by dropping terms from the singular value decomposition of $P .$ To obtain the bound E diam $( P T ) \ge$ $\sqrt { \frac { m } { n } }$ diam(T), argue about a pair of points in $T$ | 证明 |
| 7.27 | 高价值挑战 | Express the operator norm of $P A$ to the diameter of the ellipsoid $P ( A B _ { 2 } ^ { k } )$ and use Theorem 7.6.1 in part (a) and Exercise 7.25 in part (b). | 证明 |
第 8 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 8.1 | 基础验证 | Use Gaussian concentration (Theorem 7.1.11) to get (8.53). Choosing, for example, $z _ { k } =$ u $+ \sqrt { k - \kappa }$ should make the union bound go through. | 证明 |
| 8.4 | 高价值挑战 | (a) should be straightforward from Exercise 2.37. (b) The first m vectors in T form a (1/√log m)-separated set. | 证明 |
| 8.5 | 高价值挑战 | Assume diam $( T ) = 1$ , replace the integral by the sum using Exercise 8.3, and split the sum into two parts: where $2 ^ { - k } \leq n ^ { - 2 } \mathrm { \ : ( s a y ) }$ and $n ^ { - 2 } < 2 ^ { - k } \leq 1$ . In the first sum, use the volumetric bound (4.17) to bound the covering numbers. The second sum has O(log n) terms. | 证明 |
| 8.6 | 高价值挑战 | Start chaining (8.9) at the coarsest scale κ where a single ball covers the entire T, i.e. where $2 ^ { - \kappa }$ ≈ diam(T), but stop early − at scale K where roughly $2 ^ { - K } \approx w ( T ) / 8 \sqrt { n }$ (say). The last term in (8.8) may not be zero as before, but rather Es ${ \mathrm { s u p } } _ { t \in T } ( X _ { t } - X _ { \pi _ { K } ( t ) } )$ . Bound this term by ${ \scriptstyle { \frac { 1 } { 2 } } w ( T ) }$ , using that $\\| t - \pi \kappa ( t ) \\| _ { 2 } \leq 2 ^ { - K }$ | 证明 |
| 8.7 | 核心证明 | Redo the chaining argument in Section 8.1. | 证明 |
| 8.8 | 核心证明 | Consider the set $V = \{ ( s , t ) \in T \times T : \ d ( s , t ) \leq \delta \}$ , define the random process $Y _ { u } = X _ { s } - X _ { t }$ indexed by $u = ( s , t ) \in V$ , and define the metric on V by $\rho ( u , u ^ { \prime } ) = \frac { 1 } { 2 K } \\| Y _ { u } - Y _ { u ^ { \prime } } \\| _ { \psi _ { 2 } }$ . Check that diam $( V , \rho ) ~ \leq ~ \dot { \delta }$ bound the covering numbers of $( V , \dot { \rho } )$ by those of $( T , d )$ , and apply Dudley inequality (8.16). | 证明 |
| 8.9 | 核心证明 | Lay a grid on the square $[ 0 , 1 ] ^ { 2 }$ with step size ε. Given $f \in { \mathcal { F } }$ , show that $\\| f - f _ { 0 } \\| _ { L ^ { \infty } } \leq \varepsilon$ for some “staircase" function $f _ { 0 }$ that follows the grid by stepping up/down by ε or staying flat (see Figure H.1). Bound the number of all staircase functions by $e ^ { \bar { C } / \varepsilon }$ . Next, use Exercise 4.25. OCR 图片已在公开版隐藏。Figure H.1 Approximating a Lipschitz function f by a mesh-following function $f _ { 0 }$ (Exercise 8.9). | 证明 |
| 8.10 | 高价值挑战 | (b) Instead of applying Dudley inequality directly, redo at the chaining argument (proof of Theorem 8.1.4) and make an early stopping at scale δ, like in the solution of Exercise 8.6. Once you proved (8.54), plug in the covering number bound from (a) and optimize δ. | 证明 |
| 8.18 | 基础验证 | The restriction of $\mathcal { F }$ onto a shattered subset $\Lambda \subset \Omega$ gives consists of all Boolean functions on Λ, so its linear algebraic dimension must be at least $\| \Lambda \|$ (check!). | 证明 |
| 8.22 | 核心证明 | (a) Argue as in the proof of Proposition 8.3.11 and use Sauer-Shelah lemma (Lemma 8.3.9). (b) Try to find an example where $\operatorname { v c } ( { \mathcal { F } } ) = \operatorname { v c } ( { \mathcal { G } } ) = 1$ while $\operatorname { v c } ( { \mathcal { F } } \cup { \mathcal { G } } ) = 3$ | 证明 |
| 8.24 | 核心证明 | Proceed similarly to the proof of Theorem 8.3.15. Combine a concentration inequality with a union bound over the entire class $\mathcal { F }$ restricted onto $\{ X _ { 1 } , \ldots , X _ { n } \}$ . Control the cardinality of $\mathcal { F }$ using Sauer-Shelah Lemma. | 证明 |
| 8.25 | 核心证明 | Apply the VC law of large numbers (Theorem 8.3.15) to the class of indicators of half-spaces. | 证明 |
| 8.26 | 高价值挑战 | (a) Let $X _ { 1 } , \ldots , X _ { m }$ denote the rows of A. Then $\Phi ( u ) = \mathrm { s i g n } ( A u ) = ( \mathrm { s i g n } \langle X _ { i } , u \rangle ) _ { i = 1 } ^ { m }$ (b) Use the uniform law of large numbers (Theorem 8.3.15) for the function class $\mathcal { F }$ consisting of the indicators of the wedges $\{ \langle x , u \rangle \neq \langle \dot { x } , v \rangle \}$ , where $u , v \in S ^ { n - 1 }$ . Use the stability property of VC dimension (Proposition 8.3.11) to bound the VC dimension of the wedges in terms of the VC dimension of half-spaces, which was computed in Example 8.3.5. | 证明 |
| 8.27 | 高价值挑战 | (a) Let $X _ { 1 } , \ldots , X _ { m }$ denote the rows of A. Use the uniform law of large numbers (Theorem $8 . 3 . 1 5 )$ for the function class $\mathcal { F }$ consisting of the indicators of the strips $\{ x : \| \langle x , u \rangle \| \geq \varepsilon \}$ where $u \in S ^ { n - 1 }$ . Note that $\| \langle X _ { i } , u \rangle \| \geq \varepsilon$ implies $\langle X _ { i } , u \rangle ^ { 2 } \geq \varepsilon$ (b) Consider a random vector X that with probability δ equals some appropriately chosen multiple of the first basis vector $e _ { 1 }$ , and with probability $1 - \delta$ takes values in the subspace orthogonal to $e _ { 1 }$ | 证明 |
| 8.28 | 高价值挑战 | Pick an arbitrarily large subset $\Omega _ { 0 } \subset \Omega$ shattered by ${ \mathcal { F } } ,$ and let $X \sim \mathrm { U n i f } ( \Omega _ { 0 } )$ | 证明 |
| 8.29 | 基础验证 | Note that $( f - h ) ^ { 2 }$ is obtained from f by flipping the bits $f ( x )$ where $h ( x ) = 1$ | 证明 |
| 8.31 | 高价值挑战 | Show that the random process $X _ { f } ~ = ~ R _ { n } ( f ) - R ( f )$ has subgaussian increments: $\parallel X _ { f } \mathrm { ~ - ~ }$ $\begin{array} { r } { X _ { g } \\| _ { \psi _ { 2 } } \lesssim \frac { 1 } { \sqrt { n } } \\| f - g \\| _ { \infty } } \end{array}$ for all $f , g \in { \mathcal { F } } .$ Use Dudley inequality to deduce that $\mathbb E \operatorname* { s u p } _ { f \in \mathcal F } \| \ddot { R _ { n } } ( \bar { f } ) -$ $R ( f ) \| \lesssim 1 / \sqrt { n }$ (see the proof of Theorem 8.2.3). Then argue like in the proof of Theorem 8.4.5. | 证明 |
| 8.32 | 高价值挑战 | Take a uniform distribution over a shattered set $\Omega _ { 0 } \subset \Omega$ of size $\mathrm { v c } ( \mathcal { F } )$ . The sample only sees the target function $T$ on half of $\Omega _ { 0 } .$ but $T$ could do anything on the rest – so it can't be learn reliably. | 证明 |
| 8.34 | 高价值挑战 | (a) Set $T _ { 0 } = \{ 0 \}$ . For each $k \in \mathbb { N } ,$ let $T _ { k }$ contain 0 and the largest $2 ^ { 2 ^ { k } } - 1$ elements of $T ,$ | 证明 |
| 8.35 | 核心证明 | Write $\| X _ { t } - X _ { t _ { 0 } } \| \leq \| X _ { t } - X _ { \pi _ { \kappa } ( t ) } \| + \| X _ { \pi _ { \kappa } ( t ) } - X _ { t _ { 0 } } \|$ and bound the two terms separately, each with probability $1 - \exp ( u ^ { 2 } )$ . The first term can be bounded by $C \gamma _ { 2 } ( T , d )$ via chaining $\pi _ { \kappa } ( t ) \to \pi _ { \kappa + 1 } ( t ) \to \pi _ { \kappa + 2 } ( t ) \to \cdot \cdot \cdot \to t \mathrm { ~ ( b y ~ \partial ~ ) ~ }$ the choice of $\kappa ,$ the failure probabilities in this finer steps are much smaller than $\exp ( - u ^ { 2 } ) )$ . The second term, corresponding to the first big leap in chaining, can be bounded by Cu diam(T) by taking a union bound over $T _ { \kappa }$ | 证明 |
| 8.36 | 核心证明 | Following the proof of Theorem 8.2.3, check that the process $\begin{array} { r } { Z _ { f } = \frac { 1 } { \sqrt { n } } \sum _ { i = 1 } ^ { n } f ( X _ { i } ) - \sqrt { n } \mathbb { E } f ( X ) } \end{array}$ has subgaussian increments: $\lVert Z _ { f } - Z _ { g } \rVert _ { \psi _ { 2 } } \lesssim d ( f , g )$ . Then apply the generic chaining bound (Theorem 8.5.2). | 证明 |
| 8.37 | 核心证明 | (a) Use Remark 8.5.3 and the majorizing measure theorem to get a bound in terms of the Gaussian width ¿ $v ( T \cup \{ 0 \} )$ , then pass to Gaussian complexity using Exercise 7.20. (b) Use Remark 8.5.4 and Exercise 7.20. | 证明 |
| 8.38 | 核心证明 | Use duality (1.6) and Talagrand comparison inequality (Remark 8.5.9). | 证明 |
| 8.39 | 高价值挑战 | (a) Follow the proof of Theorem 7.3.1 more closely instead of applying triangle inequality. Use Sudakov-Fernique inequality (Theorem $7 . 2 . 8 )$ instead of Talagrand comparison inequality. (b) Note that $\begin{array} { r } { \mathbb { E } \operatorname* { s u p } _ { x \in T , y \in S } \langle \dot { A } x , y \rangle \geq \operatorname* { s u p } _ { x \in T } \mathbb { E } \operatorname* { s u p } _ { y \in S } \langle A x , y \rangle } \end{array}$ | 证明 |
| 8.40 | 核心证明 | Use the result of Exercise 8.37(b). | 证明 |
| 8.41 | 基础验证 | Use Chevet inequality. Exercise 1.17(a) and Exercise 7.17 should help to compute the radius and Gaussian width. | 证明 |
第 9 章
| 题号 | 难度 | 原书 hint | 当前证明 |
|---|---|---|---|
| 9.2 | 基础验证 | Bound the difference between $\mathbb { E } \Vert A x \Vert _ { 2 }$ and ${ \sqrt { m } } \\| x \\| _ { 2 }$ using the concentration of norm (Theorem 3.1.1). Use Lemma $7 . 5 . 1 1 ( \mathrm { b } )$ to show that this difference can be absorbed by the main error. | 证明 |
| 9.3 | 高价值挑战 | Use the identity $a ^ { 2 } - b ^ { 2 } = ( a - b ) ( a + b )$ | 证明 |
| 9.4 | 核心证明 | Reduce to the isotropic case: write $B _ { i } = \Sigma ^ { 1 / 2 } A _ { i }$ for some isotropic $A _ { i }$ and apply Theorem 9.1.1 for $\Sigma ^ { 1 / 2 } T$ | 证明 |
| 9.5 | 高价值挑战 | To see why this result generalizes Theorem 9.1.1, express $\begin{array} { r } { \\| A x \\| _ { 2 } \mathrm { ~ a s ~ } \big ( \sum _ { i = 1 } ^ { m } \langle A _ { i } , x \rangle ^ { 2 } \big ) ^ { 1 / 2 } } \end{array}$ where $A _ { i }$ are the rows of the matrix $A ,$ and consider the class of linear functions on $\mathbb { R } ^ { n ^ { \prime } }$ . To prove the generalization, follow the proof of Theorem 9.1.1. | 证明 |
| 9.6 | 核心证明 | To make step 2 in Theorem 9.1.2), use rotation invariance to assume $x = ( 1 , 0 , 0 , \ldots , 0 )$ and $y = ( \sqrt { 1 - \varepsilon ^ { 2 } } , \varepsilon , 0 , 0 , \ldots , 0 )$ where $\varepsilon \asymp \\| x - y \\| _ { 2 }$ . Expand $\\| P x \\| _ { 2 } ^ { 2 } - \\| P y \\| _ { 2 } ^ { 2 }$ and reduce the problem to controlling one entry of $P ,$ namely $P _ { 1 2 }$ | 证明 |
| 9.7 | 核心证明 | Use the high-probability version of matrix deviation inequality, given in (9.11). | 证明 |
| 9.8 | 核心证明 | If $m \ll n$ the random matrix A in the matrix deviation inequality is an approximate projection: this follows from Section 4.6. | 证明 |
| 9.9 | 核心证明 | Use the high-probability version (9.11) of matrix deviation inequality to get a high-probability version of the quadratic deviation (Exercise 9.3); then use it in the proof of Theorem 9.2.2. | 证明 |
| 9.11 | 核心证明 | If X has nonempty interior, dimension reduction with relative error is impossible. | 证明 |
| 9.13 | 高价值挑战 | Use the high-probability version of matrix deviation inequality (see Remark 9.1.4). | 证明 |
| 9.14 | 核心证明 | (a) For the upper bound, combine the $M ^ { * }$ bound with Exercise 7.17. For the lower bound, try to show a stronger statement – that it holds even if dim $( E ) = 1$ . Check that diam $\left( B _ { p } ^ { n } \cap E \right) =$ $\\| g \\| _ { 2 } / \\| g \\| _ { p }$ where $g \sim N ( 0 , I _ { n } )$ | 证明 |
| 9.16 | 核心证明 | Consider a random rotation $U \in \operatorname { U n i f } ( S O ( n ) )$ as in Section $5 . 2 . 5 ,$ and use a union bound to show that the probability that there exists x ∈ X such that $U ^ { - 1 } x \in T$ is smaller than 1. | 证明 |
| 9.17 | 核心证明 | Modify the $M ^ { * }$ bound accordingly. | 证明 |
| 9.19 | 高价值挑战 | Check that $\lVert A ( x - { \widehat { x } } ) \rVert _ { 2 } \lesssim \lVert w \rVert _ { 2 }$ . Plug this into the matrix deviation inequality (Theorem 9.1.1) for $T - { \dot { T } }$ noting that $x , { \widehat { x } } \in T$ | 证明 |
| 9.20 | 高价值挑战 | Bound both $\\| y - A x \\| _ { 2 } ^ { 2 } + \lambda \\| x \\| _ { T }$ and $\\| y - A { \widehat { x } } \\| _ { 2 } ^ { 2 } + \lambda \\| { \widehat { x } } \\| _ { T }$ by $\\| w \\| _ { 2 } ^ { 2 } + \lambda \\| x \\| _ { T } .$ Using triangle inequality, deduce a bound on $\\| A ( { \widehat { \boldsymbol { x } } } - { \boldsymbol { x } } ) \\| _ { 2 }$ and show that $\widehat { x } - x \in C \\| x \\| _ { T } ( T - T )$ . Now use the matrix deviation inequality (Theorem 9.1.1) as in Exercise 9.19. | 证明 |
| 9.25 | 核心证明 | Note that $\\| x _ { I _ { 1 } } \\| _ { 2 } \leq 1$ . Next, for $i \geq 2$ , note that each coordinate of $x _ { I _ { i } }$ is smaller in magnitude than the average coordinate of $x I _ { i - 1 } ;$ conclude that $\\| x _ { I _ { i } } \\| _ { 2 } \leq ( 1 / \sqrt { s } ) \\| x _ { I _ { i - 1 } } \\| _ { 1 }$ . Then sum up the bounds. | 证明 |
| 9.27 | 高价值挑战 | To prove a lower bound on $w ( S _ { n , s } )$ , construct a large ε-separated subset of $S _ { n , s }$ and thus deduce a lower bound on the covering numbers of $S _ { n , s }$ Then use Sudakov inequality (Theorem 7.4.1). | 证明 |
| 9.28 | 高价值挑战 | Fix $\rho > 0$ and apply the $M ^ { * }$ bound for the truncated cross-polytope $T _ { \rho } : = B _ { 1 } ^ { n } \cap \rho B _ { 2 } ^ { n }$ . Use Exercise 9.26 to bound the Gaussian width of $T _ { \rho } .$ Note that if rad $( T _ { \rho } \cap E ) \leq \delta$ for some $\delta \le \rho$ then rad $( T \cap E ) \leq \delta$ Finally, optimize in $\rho .$ | 证明 |
| 9.32 | 核心证明 | (a) Assume the contrary and follow the proof of Lemma 9.5.2. (b) Assume the contrary and follow the proof of Theorem 9.5.1. | 证明 |
| 9.36 | 核心证明 | Follow Remark 9.1.4. | 证明 |
| 9.37 | 高价值挑战 | Argue as in Section 9.2.4. | 证明 |
| 9.40 | 核心证明 | Use the hyperplane separation theorem. | 证明 |
| 9.42 | 核心证明 | Let T be the canonical basis $\{ e _ { 1 } , \ldots , e _ { n } \}$ in $\mathbb { R } ^ { n }$ . Express the points as $g _ { i } = A e _ { i }$ , and apply Theorem 9.7.2. | 证明 |