Chapter 2: PAC Bounds

Define $Y$ as the indicator random variable $\mathbb{I}_{\{X\geq\alpha\}}$ so that $\mathbb{E}(Y)=\mathbb{P}\left(X\geq\alpha\right)$. It is clear that $\alpha Y\leq X$ which means that $\mathbb{E}(\alpha Y)\leq\mathbb{E}(X)$, which implies that $\alpha\mathbb{P}(X\geq\alpha)\leq\mathbb{E}(X)$. Using the fact that $\alpha>0$ we can re-arrange this expressions to complete the proof of the theorem. $\square$

This follows from Markov's inequality due to the increasing, positivity and injectivity of $\exp(\cdot)$ in particular we have that $$\mathbb{P}\left(X\geq a\right)=\mathbb{P}\left(\exp(tX)\geq e^{ta}\right)\leq\frac{\mathbb{E}\left(\exp(tX)\right)}{e^{ta}},$$ which completes the proof. $\square$

For $s>0$ the function $x\mapsto e^{sx}$ is convex so that $$e^{sx}\leq\frac{x-a}{b-a}e^{sb}+\frac{b-x}{b-a}e^{sa}.$$ Let $V_i=U_i-\mathbb{E}(U_i)$, then as $\mathbb{E}(V_i)=0$ it follows that $$\mathbb{E}\left(\exp(sV_i)\right)\leq\frac{b}{b-a}e^{sa}-\frac{a}{b-a}e^{sb}.$$ With $p=\frac{b}{b-a}$ and $u=(b-a)s$ consider $$\psi(u)=\log\left(pe^{sa}+(1-p)e^{sb}\right)=(p-1)u+\log\left(p+(1-p)e^u\right).$$ This is a smooth function so that by Taylor's theorem we have that for any $u\in\mathbb{R}$ there exists $\xi=\xi(u)\in\mathbb{R}$ such that $$\psi(u)=\psi(0)+\psi^\prime(0)u+\frac{1}{2}\psi^{\prime\prime}(\xi)u^2.$$ As $$\psi^\prime(u)=(p-1)+1-\frac{p}{p+(1-p)e^u}$$ we have that $\psi(0)=0$ and $\psi^\prime(0)=0$. Furthermore, as $$\psi^{\prime\prime}(u)=\frac{p(1-p)e^u}{(p+(1-p)e^u)^2},\text{ and }\psi^{(3)}(u)=\frac{p(1-p)e^u(p+(1-p)e^u)(p-(1-p)e^u)}{(p+(1-p)e^u)^2}$$ we see that $\psi^{\prime\prime}(u)$ has a stationary point at $u^*=\log\left(\frac{p}{p-1}\right)$. For $u$ slightly less than $u^*$ we have $\psi^{(3)}(u)>0$ and for $u$ slightly larger than $u^*$ we have $\psi^{(3)}(u)<0$. Therefore, $u^*$ is a maximum point and so $$\psi^{\prime\prime}(u)\leq\psi^{\prime\prime}(u^*)=\frac{1}{4}.$$ Hence, $\psi(u)\leq\frac{u^2}{8}$ which implies that $$\log\left(\mathbb{E}\left(\exp(sV_i)\right)\right)\leq\frac{u^2}{8}=\frac{s^2(b-a)^2}{8}.$$ Therefore, $$\begin{align*}\mathbb{E}\left(\exp\left(t\sum_{i=1}^n\left(U_i-\mathbb{E}(U_i)\right)\right)\right)&=\prod_{i=1}^n\mathbb{E}\left(\exp\left(t(U_i-\mathbb{E}(U_i))\right)\right)\\&\leq\prod_{i=1}^n\exp\left(\frac{t^2(b-a)^2}{8}\right)\\&\leq\exp\left(\frac{nt^2(b-a)^2}{8}\right)\end{align*}$$ which completes the proof. $\square$

Using Markov's inequality we note that for $t<0$ we have $$\begin{align*}\mathbb{P}\left(X\leq(1-\delta)\mu\right)&=\mathbb{P}\left(e^{tX}\geq e^{t(1-\delta)\mu}\right)\\&\leq\frac{\mathbb{E}\left(e^{tX}\right)}{e^{t(1-\delta)\mu}}\\&\leq\frac{\exp\left(\left(e^t-1\right)\mu\right)}{\exp\left(t(1-\delta)\mu\right)}.\end{align*}$$ Setting $t=\log(1-\delta)<0$ we get that $$\mathbb{P}\left(X\leq(1-\delta)\mu\right)\leq\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu.$$ which completes the proof of the theorem. $\square$

Consider $$f(\delta)=-\delta-(1-\delta)\log(1-\delta)+\frac{\delta^2}{2}$$ for $\delta\in(0,1)$. Note that $$f^\prime(\delta)=\log(1-\delta)+\delta\text{ and }f^{\prime\prime}(\delta)=-\frac{1}{1-\delta}+1.$$ Which shows that $f^{\prime\prime}(\delta)<0$ for $\delta\in(0,1)$ and hence $f^{\prime}(0)=0$ implies that $f^{\prime}(\delta)\leq0$ in this range. Since, $f(0)=0$ we have that $f(\delta)\leq0$ when $\delta\in(0,1)$. Therefore, $$\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\leq\exp\left(-\frac{\delta^2}{2}\right),$$ which completes the proof of the corollary. $\square$

This can be proved by induction on $n$. When $n=1$ the result holds clearly. Now suppose that for events $E_1,\dots, E_k$ we have that $\mathbb{P}\left(\cup_{l=1}^kE_l\right)\leq\sum_{l=1}^k\mathbb{P}(E_l)$. Then for events $E_1,\dots,E_k,E_{k+1}$ it follows that $$\begin{align*}\mathbb{P}\left(\bigcup_{l=1}^{k+1}E_l\right)&=\mathbb{P}\left(\bigcup_{l=1}^kE_l\right)+\mathbb{P}\left(E_{k+1}\right)-\mathbb{P}\left(\left(\bigcup_{l=1}^kE_l\right)\cap E_{k+1}\right)\\&\leq\mathbb{P}\left(\bigcup_{l=1}^kE_l\right)+\mathbb{P}\left(E_{k+1}\right)\\&\leq\sum_{l=1}^k\mathbb{P}\left(E_l\right)+\mathbb{P}\left(E_{k+1}\right)\\&=\sum_{l=1}^{k+1}\mathbb{P}\left(E_l\right).\end{align*}$$ Therefore, by induction the result holds for all $n\in\mathbb{N}$ which completes the proof. $\square$

Let $Z_i=X_i-\mathbb{E}(X_i)$ and $Z=\frac{1}{n}\sum_{i=1}^nZ_i$. Then for $\lambda>0$ we can apply Markov's inequality to deduce that $$\begin{align*}\mathbb{P}(Z\geq\epsilon)&=\mathbb{P}\left(e^{\lambda Z}\geq e^{\lambda\epsilon}\right)\\&\leq e^{-\lambda\epsilon}\mathbb{E}\left(e^{\lambda Z}\right)\\&\leq e^{-\lambda\epsilon}\prod_{i=1}^n\mathbb{E}\left(\exp\left({\frac{\lambda Z_i}{n}}\right)\right)\\&\leq e^{-\lambda\epsilon}\prod_{i=1}^n\exp\left(\frac{\lambda^2(b-a)^2}{n^2}\right)\quad\text{ Lemma 2.1.3}\\&\leq\exp\left(-\lambda\epsilon+\frac{\lambda^2(b-a)^2}{8n}\right).\end{align*}$$ Setting $\lambda=\frac{4n\epsilon}{(b-a)^2}$ gives $$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^nX_i-\mu\geq\epsilon\right)\leq\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right).$$ Applying the same reasoning but for $\mathbb{P}\left(Z\leq-\epsilon\right)$ and $\lambda=-\frac{4n\epsilon}{(b-a)^2}$ give $$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^nX_i-\mu\leq-\epsilon\right)\leq\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right)$$ which completes the proof of the theorem. $\square$

To prove Chebyshev's inequality we use Markov's inequality, $$\begin{align*}\mathbb{P}\left(\vert X-\mu\vert\geq k\sigma\right)&=\mathbb{P}\left(\vert X-\mu\vert^2\geq k^2\sigma^2\right)\\&\leq\frac{\mathbb{E}\left((X-\mu)^2\right)}{k^2\sigma^2}\\&=\frac{\sigma^2}{k^2\sigma^2}\\&=\frac{1}{k^2}\end{align*}$$ which completes the proof of the theorem. $\square$

Using Markov's inequality we note that for $t>0$ we have $$\begin{align*}\mathbb{P}\left(X\geq(1+\delta)\mu\right)&=\mathbb{P}\left(e^{tX}\geq e^{t(1+\delta)\mu}\right)\\&\leq\frac{\mathbb{E}\left(e^{tX}\right)}{e^{t(1+\delta)\mu}}\\&\leq\frac{\exp\left(\left(e^t-1\right)\mu\right)}{\exp\left(t(1+\delta)\mu\right)}.\end{align*}$$ Setting $t=\log(1+\delta)>0$ we get that $$\mathbb{P}\left(X\geq(1+\delta)\mu\right)\leq\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^\mu.$$ which completes the proof of the theorem. $\square$

Consider $$f(\delta)=\delta-(1+\delta)\log(1+\delta)+\frac{\delta^2}{3}$$ for $\delta\in(0,1]$. Note that $$f^\prime(\delta)=-\log(1+\delta)+\frac{2}{3}\delta\text{ and }f^{\prime\prime}(\delta)=-\frac{1}{1+\delta}+\frac{2}{3}.$$ Which shows that $f^{\prime\prime}(\delta)<0$ for $\delta\in\left[0,\frac{1}{2}\right)$ and $f^{\prime\prime}(\delta)<0$ for $\delta>\frac{1}{2}$. Since $f^\prime(0)=0$ and $f^\prime(1)<0$ we deduce that $f^\prime(\delta)\leq0$ in the interval $[0,1]$. Since, $f(0)=0$ we have that $f(\delta)\leq0$ when $\delta\in[0,1]$. Therefore, $$\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\leq\exp\left(-\frac{\delta^2}{3}\right),$$ which completes the proof of the corollary. $\square$

By the construction of Algorithm 1 it is clear that for all $i$ we have $\mathbb{E}\left(\hat{w}_i\right)=w_i$. Similarly, we have that $$\mathrm{Var}\left(\hat{w}_i\right)=2p_i(1-p_i)\frac{w_i^2}{p_i^2}\leq\frac{2w_i^2}{p_i}=\eta\gamma^2.$$ Therefore, for $u$ independent of $\hat{\mathbf{w}}$ we have that $$\mathbb{E}\left(\hat{\mathbf{w}}^\top u\right)=\sum_{i=1}^d\mathbb{E}\left(\hat{w}_iu_i\right)=\sum_{i=1}^d\mathbb{E}\left(\hat{w}_i\right)u_i=\sum_{i=1}^dw_iu_i=\mathbf{w}^\top u,$$ and $$\mathrm{Var}\left(\hat{\mathbf{w}} u^\top\right)=\mathrm{Var}\left(\sum_{i=1}^d\hat{w}_iu_i\right)=\sum_{i=1}^d\mathrm{Var}(w_i)u_i^2\leq\eta\gamma^2\sum_{i=1}^du_i^2=\eta\gamma^2\Vert u\Vert^2\leq\eta\gamma^2.$$ Therefore, by Chebyshev's inequality we have that $$\mathbb{P}\left(\left\vert \hat{\mathbf{w}}^\top u-\mathbf{w}^\top u\right\vert\geq\gamma\right)\leq\eta.$$ To determine how we can bound the number of non-zero entries we analyze the behavior of the right-hand side of Theorem 2.8.2. For each entry we can define the indicator random variable $X_i$ which is $1$ when the entry is non-zero and $0$ otherwise. Note that $\mathbb{E}(X_i)=p_i$ and for $X=\sum_{i=1}^dX_i$ we have that $$\mu=\mathbb{E}(X)=\sum_{i=1}^dp_i=\frac{2\Vert\mathbf{w}\Vert^2}{\eta\gamma^2}\leq\frac{2}{\eta\gamma^2}.$$ Therefore, we need to find for what order function $f(\cdot)$ does $$\frac{e^{f(d)-1}}{f(d)^{f(d)}}\to0,\quad\text{ as }d\to\infty,$$ so that the number of non-zero elements is bounded by $O\left(\frac{f(d)}{\eta\gamma^2}\right)$ with high probability using Theorem 2.2.2. We observe that with $f(d)=\log(d)$ we get the desired convergence, and so this completes the proof of the lemma.

First note that $$\left\Vert\mathbf{w}^\prime-\mathbf{w}\right\Vert^2=\sum_{i=1}^d\left\vert w^\prime_i-w_i\right\vert^2\leq\sum_{i=1}^d\frac{\gamma^2}{16d}=\frac{\gamma^2}{16},$$ which implies that $\left\Vert\mathbf{w}^\prime-\mathbf{w}\right\Vert\leq\frac{\gamma}{4}$. Similarly, $$\left\Vert\hat{\tilde{\mathbf{w}}}-\tilde{\mathbf{w}}^*\right\Vert^2=\sum_{i=1}^d\left\vert\hat{\tilde{w}}_i-\tilde{w}_i^*\right\vert^2\leq\sum_{i=1}^d\left(\frac{1}{2}\frac{\gamma}{2\sqrt{d}}\right)^2=\frac{\gamma^2}{16},$$ which implies that $\left\Vert\hat{\tilde{\mathbf{w}}}-\tilde{\mathbf{w}}^*\right\Vert\leq\frac{\gamma}{4}$. Now suppose Algorithm 2 $\left(\frac{\gamma}{2},\mathbf{w}^\prime\right)$ returns the capped vector $\mathbf{v}$. When $\vert w_i\vert\leq\frac{\gamma}{4\sqrt{d}}$ we have that $w_i^\prime=0$ so that $v_i=0$. We also have that, $\tilde{w_i}$ is either $0$ or $$\vert\tilde{w}_i\vert=\left\vert\frac{w_i}{\left(\frac{2w_i^2}{\eta\gamma^2}\right)}\right\vert=\left\vert\frac{\eta\gamma^2}{2w_i}\right\vert\geq\vert2\eta\gamma\sqrt{d}\vert$$ so that in any case we also have that $\tilde{w}^*_i=0$. If instead $\vert\tilde{w}_i\vert\geq 2\eta\gamma\sqrt{d}$ then $\tilde{w}^*_i=0$ and through similar computations we have that $\vert w_i\vert\leq\frac{\gamma}{4\sqrt{d}}$ and so $v_i=0$. It is clear that when either of these two conditions do not hold we have $\tilde{w}^*_i=v_i$ as $w_i=w^\prime_i$. Therefore, $\tilde{\mathbf{w}}^*=\mathbf{v}$ and so from Lemma 2.8.4 we conclude that with probability at least $1-\eta$ we have $\left\vert\left(\tilde{\mathbf{w}}^*\right)^\top u-(\mathbf{w}^\prime)^\top u\right\vert\leq\frac{\gamma}{2}$ for a fixed vector $u$ with $\Vert u\Vert\leq1$. Using these observation we deduce for a fixed vector $u$ with $\Vert u\Vert\leq1$ that $$\begin{align*}\left\vert\hat{\tilde{\mathbf{w}}}^\top u-\mathbf{w}^\top u\right\vert&\leq\left\vert\hat{\tilde{\mathbf{w}}}^\top u-\left(\tilde{\mathbf{w}}^*\right)^\top u\right\vert+\left\vert\left(\hat{\mathbf{w}}^*\right)^\top u-\left(\mathbf{w}^\prime\right)^\top u\right\vert+\left\vert\left(\mathbf{w}^\prime\right)^\top u-\mathbf{w}^\top u\right\vert\\&\leq\left\Vert\hat{\tilde{\mathbf{w}}}^\prime-\tilde{\mathbf{w}}^*\right\Vert+\frac{\gamma}{2}+\left\Vert\mathbf{w}^\prime-\mathbf{w}\right\Vert\\&\leq\frac{\gamma}{4}+\frac{\gamma}{2}+\frac{\gamma}{4}=\gamma,\end{align*}$$ with probability at least $1-\eta$, which completes the proof of the lemma.$\square$

Observe that $$\hat{\mathbf{w}}^\top u=\frac{1}{k}\sum_{i=1}^k\langle v_i,\mathbf{w}\rangle\langle v_i,u\rangle.$$ Where, $$\mathbb{E}\left(\langle v_i,\mathbf{w}\rangle\langle v_i,u\rangle\right)=\mathbb{E}\left(\mathbf{w}^\top v_iv_i^\top u\right)=\mathbf{w}^\top\mathbb{E}\left(v_iv_i^\top\right)=\mathbf{w}^\top u$$ and $$\mathrm{Var}\left(\hat{\mathbf{w}}^\top u\right)\leq O\left(\frac{1}{k}\right).$$ Therefore, by standard concentration inequalities $$\begin{align*}\mathbb{P}\left(\left\vert\hat{\mathbf{w}}^\top u-\mathbf{w}^\top u\right\vert\geq\frac{\gamma}{2}\right)\leq\exp\left(\frac{-\gamma^2k}{16}\right)\leq\eta.\end{align*}$$ As with discretization the vector can only change by at most $\frac{\gamma}{2}$, the proof of the lemma is complete. $\square$

For fixed vectors $u,v$ we have that $$u^\top\hat{A}v=\frac{1}{k}\sum_{l=1}^ku^\top Z_lv=\frac{1}{k}\sum_{l=1}^k\langle A,M_l\rangle\left\langle uv^\top,M_l\right\rangle.$$ Furthermore, we have that $$\begin{align*}\mathbb{E}\left(\langle A,M_l\rangle\left\langle uv^\top,M_l\right\rangle\right)&=\mathbb{E}\left(\mathrm{tr}\left(A^\top M_l\right)\mathrm{tr}\left(M_l^\top\left(uv^\top\right)\right)\right)\\&=\mathbb{E}\left(\left(\sum_{i,j}a_{ij}m_{ij}\right)\left(\sum_{i,j}m_{ij}u_{ij}\right)\right)\\&=\sum_{i,j}a_{ij}u_{ij}\\&=\left\langle A,uv^\top\right\rangle,\end{align*}$$ where we achieve the last equality as we note that $\mathbb{E}(m_{ij}m_{kl})$ is $1$ when $ij=kl$ and $0$ otherwise. By standard concentration inequalities we deduce that $$\mathbb{P}\left(\left\vert\frac{1}{k}\sum_{l=1}^k\langle A,M_l\rangle\left\langle uv^\top,M_l\right\rangle-\left\langle A,uv^\top\right\rangle\right\vert\geq\epsilon\Vert A\Vert_F\left\Vert uv^\top\right\Vert_F\right)\leq\exp\left(-k\epsilon^2\right).$$ Therefore, for the choice of $k$ from Algorithm 3 we know that $$\mathbb{P}\left(\left\vert u^\top\hat{A}v-u^\top Av\right\vert\geq\epsilon\Vert A\Vert_F\left\Vert u\right\Vert\left\Vert v\right\Vert\right)\leq\eta.$$ Let $(U,x)\in G$ and $u_i$ be the $i^\text{th}$ row of $U$. We can apply the above result with a union bound over the $mn$ rows $u_i$ in $G$ to get that $$\mathbb{P}\left(\left\vert u_i^\top\hat{A}v-u_i^\top Av\right\vert\leq\epsilon\Vert A\Vert_F\left\Vert u_i\right\Vert\left\Vert v\right\Vert\right)\geq1-\delta$$ for all $i$ simultaneously. Furthermore, $$\left\Vert U\left(\hat{A}-A\right)x\right\Vert^2=\sum_{i=1}^n\left(u_i^\top\left(\hat{A}-A\right)x\right)^2,\text{ and }\Vert U\Vert_F^2=\sum_{i=1}^n\Vert u_i\Vert^2$$ we see that with probability at least $1-\delta$ we have $$\begin{align*}\left\Vert U(\hat{A}-A)x\right\Vert^2&=\sum_{i=1}^n\left(u_i^\top\left(\hat{A}-A\right)x\right)^2\\&\leq\sum_{i=1}^n\epsilon^2\Vert A\Vert_F^2\Vert u_i\Vert^2\Vert x\Vert\\&=\epsilon^2\Vert A\Vert_F^2\Vert U\Vert^2\Vert x\Vert\end{align*}$$ which completes the proof of the lemma. $\square$

The proof of this lemma proceeds by induction. For $i\geq0$ let $\hat{x}_i^j$ be the output at layer $j$ if weights $A^1,\dots,A^i$ are replaced with $\tilde{A}^1,\dots,\tilde{A}^i$. We want to show for any $i$ if $j\geq i$ then $$\mathbb{P}\left(\left\Vert\hat{x}_i^j-x^j\right\Vert\leq\frac{i}{d}\epsilon\left\Vert x^j\right\Vert\right)\geq1-\frac{i\delta}{2d}.$$ For $i=0$ the result is clear as the weight matrices are unchanged. Suppose the result holds true for $i-1$. Let $\hat{A}^i$ be the result of applying Algorithm 3 to $A^i$ with $\epsilon_i=\frac{\epsilon\mu_i\mu_{i\to}}{4cd}$ and $\eta=\frac{\delta}{6d^2n^2m}$. Consider the set $$G=\left\{\left(J_{x^i}^{i,j},x^i\right):x^i\in\mathcal{X},j\geq i\right\}$$ and let $\Delta^i=\hat{A}^i-A^i$. Note that $$\left\Vert\hat{x}_i^j-x^j\right\Vert\leq\left\Vert\hat{x}_i^j-\hat{x}_{i-1}^j\right\Vert+\left\Vert\hat{x}_{i-1}^j-x^j\right\Vert.$$ The second term is bounded by $\frac{(i-1)\epsilon\left\Vert x^j\right\Vert}{d}$ by inductive assumption. Therefore, it suffices to show that the first term is bounded by $\frac{\epsilon}{d}$ to complete the inductive step. First observe that, $$\left\Vert\hat{x}_i^j-\hat{x}_{i-1}^j\right\Vert\leq\left\Vert J_{x^i}^{i,j}\left(\Delta^i\phi\left(\hat{x}^{i-1}\right)\right)\right\Vert+\left\Vert M^{i,j}\left(\hat{A}^i\phi\left(\hat{x}^{i-1}\right)\right)-M^{i,j}\left(A^i\phi\left(\hat{x}^{i-1}\right)\right)-J_{x^i}^{i,j}\left(\Delta^i\phi\left(\hat{x}^{i-1}\right)\right)\right\Vert.$$ The first term can be bounded as follows $$\begin{align*}\left\Vert J_{x^i}^{i,j}\left(\Delta^i\phi\left(\hat{x}^{i-1}\right)\right)\right\Vert&\leq\frac{\epsilon\mu_i\mu_{i\to}}{6cd}\left\Vert J_{x^i}^{i,j}\right\Vert\left\Vert A^i\right\Vert_F\left\Vert\phi\left(\hat{x}^{i-1}\right)\right\Vert\quad\text{Lemma 2.21.1}\\&\leq\frac{\epsilon\mu_i\mu_{i\to}}{6cd}\left\Vert J_{x^i}^{i,j}\right\Vert\left\Vert A^i\right\Vert_F\left\Vert\hat{x}^{i-1}\right\Vert\quad\text{Lipschitz of $\phi$}\\&\leq\frac{\epsilon\mu_i\mu_{i\to}}{3cd}\left\Vert J_{x^i}^{i,j}\right\Vert\left\Vert A^i\right\Vert_F\left\Vert x^{i-1}\right\Vert\quad\text{ Inductive Assumption}\\&\leq\frac{\epsilon\mu_{i\to}}{3d}\left\Vert J_{x^i}^{i,j}\right\Vert\left\Vert A^i\phi\left(x^{i-1}\right)\right\Vert\\&\leq\frac{\epsilon\mu_{i\to}}{3d}\left\Vert J_{x^i}^{i,j}\right\Vert\left\Vert x^i\right\Vert\\&\leq\frac{\epsilon}{3d}\left\Vert x^j\right\Vert.\end{align*}$$ The second term can be split as $$\left\Vert\left(M^{i,j}-J_{x^i}^{i,j}\right)\left(\hat{A}^i\phi\left(\hat{x}^{i-1}\right)\right)\right\Vert+\left\Vert\left(M^{i,j}-J_{x^i}^{i,j}\right)\left(A^i\phi\left(\hat{x}^{i-1}\right)\right)\right\Vert,$$ which can be bounded by inter-layer smoothness. By inductive assumption $$\left\Vert A^i\phi\left(\hat{x}^{i-1}\right)-x^i\right\Vert\leq\frac{(a-1)\epsilon\left\Vert x^i\right\Vert}{d}\leq\epsilon\left\Vert x^i\right\Vert.$$ Then by inter-layer smoothness $$\left\Vert\left(M^{i,j}-J_{x^i}^{i,j}\right)\left(A^i\phi\left(\hat{x}^{i-1}\right)\right)\right\Vert\leq\frac{\left\Vert x^b\right\Vert\epsilon}{\rho_{\delta}}\leq\frac{\epsilon}{3d}\left\Vert x^j\right\Vert.$$ On the other hand, $$\left\Vert\hat{A}^i\phi\left(\hat{x}^{i-1}\right)-x^i\right\Vert\leq\left\Vert A^i\phi\left(\hat{x}^{i-1}\right)-x^i\right\Vert+\left\Vert\Delta^i\phi\left(\hat{x}^{i-1}\right)\right\Vert\leq\frac{(i-1)\epsilon}{d}+\frac{\epsilon}{3d}\leq\epsilon$$ so that $$\left\Vert\left(M^{i,j}-J_{x^i}^{i,j}\right)\left(A^i\phi\left(\hat{x}^{i-1}\right)\right)\right\Vert\leq\frac{\epsilon}{3d}\left\Vert x^j\right\Vert.$$ This completes the inductive step. To complete the proof we bound the total number of parameters. With the values of $\epsilon_i$ and $\eta$ used in the induction we see that the total number of parameters is $$\begin{align*}\sum_{i=1}^d\frac{\log\left(\frac{1}{\frac{\delta}{6d^2n^2m}}\right)}{\left(\frac{\epsilon\mu_i\mu_{i\to}}{4cd}\right)^2}&=\sum_{i=1}^d\frac{16c^2d^2\log\left(\frac{6d^2n^2m}{\delta}\right)}{\epsilon^2\mu_i\mu_{i\to}}\\&\leq\frac{16c^2d^2\log\left(\frac{d^2n^2m^2}{\delta^2}\right)}{\epsilon^2}\sum_{i=1}^d\frac{1}{\mu_i^2\mu_{i\to}^2}\\&\leq\frac{32c^2d^2\log\left(\frac{mdn}{\delta}\right)}{\epsilon^2}\sum_{i=1}^d\frac{1}{\mu_i^2\mu_{i\to}^2},\end{align*}$$ which completes the proof of the lemma. $\square$

In the first case suppose that $\gamma^2>2\max_{x\in\mathcal{X}}\left\Vert h_{\mathbf{w}}(x)\right\Vert_2^2$, then $$\left\vert h_{\mathbf{w}}(x)[y]-\max_{j\neq y}h_{\mathbf{w}}(x)[j]\right\vert^2\leq 2\max_{x\in\mathcal{X}}\left\Vert h_{\mathbf{w}}(x)\right\Vert_2^2\leq\gamma^2.$$ Therefore, the margin can be at most $\gamma$ which implies that $\hat{L}_{\gamma}(h_{\mathbf{w}})=1$ and so the statement holds in this case. If instead $\gamma^2\leq2\max_{x\in\mathcal{X}}\left\Vert h_{\mathbf{w}}(x)\right\Vert_2^2$, then setting $\epsilon=\frac{\gamma^2}{2\max_{x\in\mathcal{X}}\left\Vert h_{\mathbf{w}}(x)\right\Vert_2^2}$ in Lemma 2.21.2 we conclude that $$\left\Vert h_{\mathbf{w}}(x)-h_{\tilde{\mathbf{w}}}(x)\right\Vert\leq\frac{\gamma}{\sqrt{2}}$$ for any $x\in\mathcal{X}$. If for $(x,y)\in\mathcal{Z}$ we have that $$h_{\mathbf{w}}(x)[y]\leq\gamma+\max_{j\neq y}f_{\mathbf{w}}[j]$$ then for $h_{\tilde{\mathbf{w}}}$ the contribution of this data point to the empirical classification loss can only be less than or equal to its contribution to the empirical classification margin loss of $h_{\mathbf{w}}$. On the other hand, suppose that $$h_{\mathbf{w}}[y]>\gamma+\max_{j\neq y}h_{\mathbf{w}}[j],$$ so that the data point doesn't contribute to $\hat{L}_{\gamma}(h_{\mathbf{w}})$. For the data point's contribution to $\hat{L}_0(h_{\tilde{\mathbf{w}}})$ to be larger we need $$h_{\tilde{w}}\leq\max_{j\neq y}h_{\tilde{w}}(x)[y]$$ which would either require a change of more than $\gamma$ between two components of $h_{\mathbf{w}}(x)$ under compression to $h_{\tilde{\mathbf{w}}}(x)$. If this change occurs then the distance between $h_{\mathbf{w}}(x)$ and $h_{\tilde{\mathbf{w}}}(x)$ is minimized when only two components change by more than $\frac{\gamma}{2}$. Suppose that components the $i^\text{th}$ and $j^\text{th}$ components move sufficiently then, $$\begin{align*}\left\Vert h_{\mathbf{w}}(x)-h_{\tilde{w}}(x)\right\Vert^2&>\vert h_{\mathbf{w}}(x)[i]-h_{\tilde{\mathbf{w}}}(x)[i]\vert^2+\vert h_{\mathbf{w}}(x)[j]-h_{\tilde{\mathbf{w}}}(x)[j]\vert^2\\&>\frac{\gamma^2}{4}+\frac{\gamma^2}{4}\\&=\frac{\gamma^2}{2}\end{align*}$$ which contradicts the conclusion of Lemma 2.21.2. We now bound the number of total parameters. With our value for $\epsilon$ Lemma 2.21.2 tells us that the number of total parameters is at most $$\frac{32c^2d^2\log\left(\frac{mdn}{\delta}\right)}{\frac{\gamma^2}{2\max_{x\in\mathcal{X}}}}\sum_{i=1}^d\frac{1}{\mu_i^2\mu_{i\to}^2},$$ from which the required result follows and completes the proof of the lemma.

For $x\in\mathcal{X}$ recall that $x^i$ is the vector before activation at layer $i$. Now we also consider $\hat{x}^i$ as the vector before activation for the network with weights $\hat{A}$. For the lemma $x\in\mathcal{X}$ is fixed so let $\xi_i=\left\vert\hat{x}^i-x^i\right\vert$. Now proceed by induction on the statement $$\xi_i\leq\left(1+\frac{1}{d}\right)^i\Vert x\Vert\left(\prod_{j=1}^i\left\Vert A^j\right\Vert_2\right)\sum_{j=1}^i\frac{\left\Vert A^j-\hat{A}^j\right\Vert_2}{\left\Vert A^j\right\Vert_2}.$$ The base case clearly holds as $\xi_0=0$. Therefore, for $i\geq1$ we proceed as follows, $$\begin{align*}\xi_{i+1}&=\left\vert\hat{A}^{i+1}\phi\left(\hat{x}^i\right)-A^{i+1}\phi\left(x^i\right)\right\vert_2\\&=\left\vert\hat{A}^i\left(\phi\left(\hat{x}^i\right)-\phi\left(x^i\right)\right)+\left(\hat{A}^i-A^i\right)\phi\left(x^i\right)\right\vert_2\\&\leq\left(\left\Vert A^{i+1}\right\Vert_2+\left\Vert\hat{A}^{i+1}+A^{i+1}\right\Vert_2\right)\left\vert\phi\left(\hat{x}^i\right)-\phi\left(x^i\right)\right\vert_2+\left\Vert\hat{A}^{i+1}-A^{i+1}\right\Vert_2\left\vert\phi\left(x^i\right)\right\vert_2\\&\leq\left(\left\Vert A^{i+1}\right\Vert_2+\left\Vert\hat{A}^{i+1}+A^{i+1}\right\Vert_2\right)\left\vert\hat{x}^i-x^i\right\vert_2+\left\Vert\hat{A}^{i+1}-A^{i+1}\right\Vert_2\left\vert x^i\right\vert_2\\&=\left(\left\Vert A^{i+1}\right\Vert_2+\left\Vert\hat{A}^{i+1}+A^{i+1}\right\Vert_2\right)\xi_i+\left\Vert\hat{A}^{i+1}-A^{i+1}\right\Vert_2\left\vert x^i\right\vert_2,\end{align*}$$ note how the second arises as a specific property of the ReLU activation function. By the assumption of the lemma and the inductive assumption it therefore follows that $$\begin{align*}\xi_{i+1}&\leq\xi_i\left(1+\frac{1}{d}\right)\left\Vert A^{i+1}\right\Vert_2+\left\Vert\hat{A}^{i+1}-A^{i+1}\right\Vert_2\Vert x\Vert_2\prod_{j=1}^i\left\Vert A^j\right\Vert_2\\&\leq\left(1+\frac{1}{d}\right)^{i+1}\left(\prod_{j=1}^{i+1}\left\Vert A^j\right\Vert_2\right)\Vert x\Vert_2\sum_{j=1}^i\frac{\left\Vert\hat{A}^j-A^j\right\Vert_2}{\left\Vert A^j\right\Vert_2}+\frac{\left\Vert\hat{A}^{i+1}-A^{i+1}\right\Vert_2}{\left\Vert A^{i+1}\right\Vert_2}\Vert x\Vert_2\prod_{j=1}^{i+1}\left\Vert A^j\right\Vert_2\\&\leq\left(1+\frac{1}{d}\right)^{i+1}\left(\prod_{j=1}^{i+1}\left\Vert A^j\right\Vert_2\right)\Vert x\Vert_2\sum_{j=1}^{i+1}\frac{\left\Vert\hat{A}^j-A^j\right\Vert_2}{\left\Vert A^j\right\Vert_2},\end{align*}$$ then using the fact that $\left(1+\frac{1}{d}\right)^d\leq e$ completes the proof of the lemma.