\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, total={6in, 8in}]{geometry}
\usepackage{amsmath, amsfonts}
\usepackage{hyperref, graphicx}

\title{CSCI 145 Problem 13: How Shallow Is a Residual Network?}
\author{} % TODO: Put your name here
\date{\today}

\begin{document}
\maketitle

\subsection*{Submission Instructions}
Please upload your work to Gradescope by \textbf{11:59pm on DATE}. % TODO: date
\begin{itemize}
\item Turn in a single PDF of \textit{handwritten} solutions. Typed (including \LaTeX) solutions will not be accepted.
\item Problems are grouped into three-week \textbf{cycles}. Once per cycle, you will meet with the grader and present the solution to \emph{one} problem from that cycle, selected at random when you arrive; bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 13: How Shallow Is a Residual Network? \hfill \textnormal{2 points}}

Along one input, the Jacobian of an $L$-block residual network is
$$
\mathbf{J}=(\mathbf{I}+\mathbf{J}_L)(\mathbf{I}+\mathbf{J}_{L-1})\cdots(\mathbf{I}+\mathbf{J}_1),
\qquad \|\mathbf{J}_\ell\|_2\leq \varepsilon<1.
$$
Let $\mathbf{J}_{<m}$ denote the sum of all terms in the product expansion that use fewer than $m$ of the matrices $\mathbf{J}_1,\ldots,\mathbf{J}_L$, in their original order.

A compression memo says that for $L=50$ and $\varepsilon=0.1$, ``paths of depth at most ten contain at least $99\%$ of the input-output Jacobian.'' The lecture estimates give the conservative certificate
$$
\frac{\|\mathbf{J}-\mathbf{J}_{<m}\|_2}{\|\mathbf{J}\|_2}
\leq
\frac{\displaystyle\sum_{k=m}^{L}\binom{L}{k}\varepsilon^k}
{(1-\varepsilon)^L}.
$$
Use this certificate to determine the smallest cutoff that guarantees relative error at most $0.01$, then issue a verdict on the memo using only the stated norm assumption. Distinguish failure to certify a claim from evidence that the claim is false, support your verdict with an admissible choice of the matrices $\mathbf{J}_\ell$, and explain why ``$99\%$ of the Jacobian'' is potentially misleading when path terms can align or cancel.

The final cutoff should follow from a reproducible calculation, not from a normal or Poisson approximation. You may include a short table of exact binomial sums.

\paragraph{Results you may use.}
You may use scalar multiples of $\mathbf{I}$ as admissible residual Jacobians, and you may evaluate the exact binomial sums with a calculator or short program.

%\input{solutions/solution13}
\end{document}
