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

\title{CSCI 145 Problem 13: A Residual Network Is an Ensemble of $2^L$ Paths}
\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 --- so bring your work and be ready to explain any of them.
\end{itemize}

\newpage \section*{Problem 13: A Residual Network Is an Ensemble of $2^L$ Paths}

A residual network $50$ blocks deep is usually described as one very deep network, but it is better described as a collection of roughly $10^{15}$ shallower ones, of which only a vanishing fraction matter.
Lecture kept one identity path through each block; here we count \emph{all} of the paths, and the counting explains why residual networks are so forgiving to train.

Throughout, the stack has $L$ blocks of one width $d$, so every matrix is $d\times d$: $\mathbf{I}$ is the identity and $\mathbf{J}_F^{(l)}$ is the Jacobian of block $l$'s learned part $F^{(l)}$, as in lecture.
By the chain rule, the stack's end-to-end Jacobian is $\prod_{l=1}^{L}\big(\mathbf{I}+\mathbf{J}_F^{(l)}\big)$.

\subsection*{Part A: Two Blocks, by Hand}

Take $L=2$ and expand $\big(\mathbf{I}+\mathbf{J}_F^{(1)}\big)\big(\mathbf{I}+\mathbf{J}_F^{(2)}\big)$ by hand into four terms.
Identify each term with a ``path'' through the two blocks: which term skips both blocks entirely, which takes both blocks' learned transformations, and which two take one block's shortcut and the other's learned path?

\subsection*{Part B: $L$ Blocks, $2^L$ Paths}

Generalize Part A.
Show by induction on $L$ (Part A is the case $L=2$) that
\begin{align*}
    \prod_{l=1}^L \big(\mathbf{I}+\mathbf{J}_F^{(l)}\big) = \sum_{T \subseteq \{1,\ldots,L\}} \; \prod_{l \in T} \mathbf{J}_F^{(l)},
\end{align*}
where each inner product is taken in increasing order of $l$, and the empty product is $\mathbf{I}$.
Each of the $2^L$ subsets $T$ names one path: through the learned part of every block in $T$, and along the identity shortcut through every block outside it.
Which subset is the all-shortcuts path, the one term that survives no matter what the blocks learn?

\subsection*{Part C: The Gradient Concentrates on Short Paths}

Suppose every block's learned Jacobian is small, $\|\mathbf{J}_F^{(l)}\|_2 \le \epsilon$ for some $\epsilon<1$, a fair description early in training. (Recall that $\|\cdot\|_2$ is the largest singular value, the SVD quantity this course has tracked since the power method.)
Using the triangle inequality and submultiplicativity of the spectral norm ($\|\mathbf{A}\mathbf{B}\|_2 \le \|\mathbf{A}\|_2\|\mathbf{B}\|_2$), show that the paths through exactly $k$ blocks contribute at most
\begin{align*}
    \left\| \sum_{|T|=k} \; \prod_{l\in T} \mathbf{J}_F^{(l)} \right\|_2 \leq \binom{L}{k} \epsilon^k .
\end{align*}
Summing over $k$ and applying the binomial theorem recovers lecture's bound $(1+\epsilon)^L$ for the whole stack, so no mass has gone missing.
Now fix $L=50$ and $\epsilon=0.1$, where that total is $1.1^{50}\approx 117$, and evaluate $\binom{L}{k}\epsilon^k$ at $k=1$, $k=5$, and $k=25$.
Conclude in one sentence where essentially all of the end-to-end Jacobian's mass lives: on paths through many of the $50$ blocks, or on paths through a handful of them?

\vspace{0.5em}
\noindent
\textbf{Where this goes next.}
A sum over exponentially many paths with the mass on the short ones is why a residual network of depth $L$ trains like a network of much smaller \emph{effective} depth, and why it behaves like an ensemble of shallower networks, one per short path, all sharing the same weights.
Every transformer in the Architectures unit is a residual stack, which is why those models can be tens or even hundreds of blocks deep.

%\input{solutions/solution13}

\end{document}
