\documentclass[11pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsmath, amssymb, amsthm}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{booktabs}
\usepackage{bm}
\usepackage{parskip}
\usepackage{array}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning}

\hypersetup{colorlinks=true, linkcolor=blue, urlcolor=blue}

%% code style
\definecolor{codebg}{rgb}{0.97,0.97,0.97}
\definecolor{codegreen}{rgb}{0.0,0.45,0.0}
\definecolor{codeblue}{rgb}{0.0,0.0,0.75}
\definecolor{codegray}{rgb}{0.45,0.45,0.45}
\definecolor{codepurple}{rgb}{0.5,0.0,0.7}
\lstdefinestyle{python}{
  language=Python,
  backgroundcolor=\color{codebg},
  basicstyle=\ttfamily\footnotesize,
  keywordstyle=\color{codeblue}\bfseries,
  commentstyle=\color{codegreen},
  stringstyle=\color{codepurple},
  numberstyle=\tiny\color{codegray},
  numbers=left, numbersep=6pt,
  frame=single, rulecolor=\color{gray!40},
  breaklines=true, showstringspaces=false,
  tabsize=4, keepspaces=true,
  morekeywords={self,True,False,None}
}
\lstset{style=python}

%% math shortcuts
\newcommand{\R}{\mathbb{R}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bt}{\boldsymbol{\theta}}
\newcommand{\bp}{\hat{\mathbf{p}}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\pts}[1]{\textbf{[#1 pts]}}

% =====================================================================
\begin{document}

% ----- title block ---------------------------------------------------
\begin{center}
  {\LARGE\bfseries CS480/680 \quad Spring 2026}\\[6pt]
  {\Large\bfseries Assignment 2}\\[4pt]
  Designer: Abdenour Belarbi \quad Instructor: Hongyang Zhang\\[2pt]
  Released: June 8 \quad\quad Due: \textbf{July 13, noon}
\end{center}
\vspace{2pt}\hrule\vspace{8pt}

% ----- instructions --------------------------------------------------
\subsection*{Instructions}
\begin{itemize}[leftmargin=1.5em, itemsep=2pt]
  \item We do \textbf{not} accept hand-written submissions.
  \item For \textbf{coding} questions, implement in Python using a Jupyter
        Notebook. Ensure all cells run without error and that outputs are
        saved before submission.
  \item Submit \textbf{two files} to LEARN:
        a PDF write-up (written answers to \emph{all} questions,
          including reported accuracy results for coding questions), and
        an IPYNB file (all coding questions with saved outputs).
  \item Name your files
        \texttt{Lastname\_Firstname\_assignment2.pdf} and
        \texttt{Lastname\_Firstname\_assignment2.ipynb}.
        Incorrect naming may result in a grade of 0.
\end{itemize}
\hrule\vspace{6pt}

% =====================================================================
\section*{Question 1 \quad Theory \hfill (10 points)}

% ----- Q1.1 ----------------------------------------------------------
\subsection*{1.1 \; Gradient Descent Convergence \pts{3}}

Consider $f(x) = \tfrac{1}{2}(10x_1^2 + x_2^2)$, $x \in \R^2$.

\begin{enumerate}[label=(\alph*), itemsep=4pt]
  \item Compute the Hessian $\nabla^2 f(x)$.
        Is $f$ convex? Is it strongly convex?
        Identify the smoothness constant $L$ and the strong convexity
        constant $m$.

  \item What is the maximum step size $t$ that guarantees
        convergence of gradient descent?
        Give the bound from the convex theorem ($t \le 1/L$)
        and from the strongly convex theorem ($t \le 2/(m+L)$).

  \item Assume $x^{(0)} = (1,1)^\top$ and target accuracy
        $\varepsilon = 0.01$. Using step size $t = 1/L$, find the
        minimum number of iterations $k$ to guarantee
        $f(x^{(k)}) - f^* \le \varepsilon$ under:
        \begin{itemize}
          \item the \textbf{convex} bound:
                $\;f(x^{(k)})-f^* \le
                \dfrac{\norm{x^{(0)}-x^*}_2^2}{2tk}$
          \item the \textbf{strongly convex} bound:
                $\;f(x^{(k)})-f^* \le
                \gamma^k\dfrac{L}{2}\norm{x^{(0)}-x^*}_2^2$,
                where $\gamma = 1 - m/L$.
        \end{itemize}
\end{enumerate}

% ----- Q1.2 ----------------------------------------------------------
\subsection*{1.2 \; CNN: Output Size and Parameter Counting \pts{3}}

The following CNN is applied to FashionMNIST ($28\!\times\!28\!\times\!1$):

\begin{center}
\begin{tabular}{clllc}
\toprule
Layer & Type & Filters/Units & Kernel & Stride / Padding \\
\midrule
1 & Convolutional   & 16 & $5\times5$ & stride 1, no padding \\
2 & BatchNorm       & -- & --         & --                   \\
3 & Max Pooling     & -- & $2\times2$ & stride 2             \\
4 & Convolutional   & 32 & $3\times3$ & stride 1, no padding \\
5 & BatchNorm       & -- & --         & --                   \\
6 & Max Pooling     & -- & $2\times2$ & stride 2             \\
7 & Dropout ($p=0.2$) & -- & --       & --                   \\
8 & Fully Connected & 10 & --         & --                   \\
\bottomrule
\end{tabular}
\end{center}

Output size formula (height $\times$ width for one channel):
$\;\bigl(1+\frac{m-a}{s}\bigr)\times\bigl(1+\frac{n-b}{s}\bigr)$
for input $m\!\times\!n$, kernel $a\!\times\!b$, stride $s$
(no padding).

\begin{enumerate}[label=(\alph*), itemsep=4pt]
  \item Compute the output size (H$\times$W$\times$C) after
        \emph{each} layer. Show your work.

  \item Count the learnable parameters (weights + biases)
        in each layer. For a conv layer:
        $a \cdot b \cdot c_{\mathrm{in}} \cdot c_{\mathrm{out}}
        + c_{\mathrm{out}}$. For a BatchNorm layer with $c$ channels:
        $2c$ (one $\gamma$ and one $\beta$ per channel).
        Pooling layers have \emph{zero} parameters.
        Give the total.

  \item Compare the CNN's total parameters to a fully connected
        network with input 784, one hidden layer of 256 units, and
        output 10 (all with biases). What does this tell you about
        convolutional layers?
\end{enumerate}

% ----- Q1.3 ----------------------------------------------------------
\subsection*{1.3 \; Transformer: Architecture and Scaling \pts{4}}

Consider one Transformer encoder layer with $d=256$, $h=8$ heads,
and feedforward dimension $d_{\mathrm{ff}}=1024$.
Assume \textbf{no biases} in the attention projections and
\textbf{biases included} in the feedforward and LayerNorm.

\begin{enumerate}[label=(\alph*), itemsep=4pt]

  \item Count the total learnable parameters in this encoder layer.
        Include: multi-head self-attention
        ($W_Q,W_K,W_V,W_O\in\R^{d\times d}$),
        feedforward sublayer
        ($W_1\!\in\!\R^{d\times d_{\mathrm{ff}}}$,
         $W_2\!\in\!\R^{d_{\mathrm{ff}}\times d}$, with biases),
        and the two LayerNorms ($\gamma,\beta\in\R^d$ each).

  \item Let $\mathbf{q},\mathbf{k}\in\R^{d_k}$ have i.i.d.\ entries
        from $\mathcal{N}(0,1)$.
        Show that $\mathrm{Var}(\mathbf{q}^\top\mathbf{k}) = d_k$.

  \item As $d_k$ grows, the dot products $\mathbf{q}^\top\mathbf{k}$
        become large. Explain what this does to the softmax output
        and why it is a problem for training.

  \item Show that scaling by $1/\sqrt{d_k}$ restores the variance
        of the scores to 1.

\end{enumerate}

% =====================================================================
\section*{Question 2 \quad Backpropagation \hfill (8 points)}

% ----- Q2.1 ----------------------------------------------------------
\subsection*{2.1 \; Softmax Gradient Warm-Up \pts{1}}

A softmax output layer produces $\bp = \mathrm{softmax}(\bt)$
and the loss is the cross-entropy $J = -\log\hat{p}_y$.

\textit{Recall from Lecture 4 that this can be written as
$J = -\theta_y + \log\sum_j e^{\theta_j}$.}

Given logits $\bt = [0,\;0.5,\;0.25,\;0.75]$ and true class $y=2$:

\begin{enumerate}[label=(\alph*), itemsep=4pt]
  \item Compute $\bp$ and $J$ (round to 4 decimal places).
  \item Show that
        $\dfrac{\partial J}{\partial \theta_i} = \hat{p}_i - \mathbf{1}[i=y]$,
        and evaluate this for the values above.
\end{enumerate}

% ----- Q2.2 ----------------------------------------------------------
\subsection*{2.2 \; Full Backpropagation \pts{7}}

Consider the 2-layer MLP below with all weights and bias terms labeled.
The hidden layer uses ReLU; the output uses softmax with
cross-entropy loss $J=-\log\hat{p}_y$.
Input: $x_1=1$, $x_2=0.5$. True class: $y=0$.

\begin{center}
\begin{tikzpicture}[scale=0.75,
    nrn/.style={circle, draw, thick, minimum size=0.90cm, font=\small},
    bias/.style={circle, draw, minimum size=0.50cm, font=\tiny, fill=gray!10},
    wl/.style={font=\tiny, fill=white, inner sep=1pt},
    arr/.style={->, >=stealth, thin}
  ]

  %% INPUT LAYER  x = 0
  \node[nrn] (x1) at (0,  2.0) {$x_1$};
  \node[nrn] (x2) at (0, -2.0) {$x_2$};
  \node[font=\scriptsize, left=4pt of x1] {$1$};
  \node[font=\scriptsize, left=4pt of x2] {$0.5$};

  %% HIDDEN LAYER  x = 5.5  (three neurons, evenly spaced)
  \node[nrn] (h1) at (5.5,  2.5) {$h_1$};
  \node[nrn] (h2) at (5.5,  0.0) {$h_2$};
  \node[nrn] (h3) at (5.5, -2.5) {$h_3$};

  %% Bias node for hidden (above-left of hidden layer)
  \node[bias] (b1) at (3.2, 5.0) {$1$};
  \draw[arr] (b1) -- node[wl, above right]{$0.1$} (h1);
  \draw[arr] (b1) -- node[wl, above]{$0.2$}       (h2);
  \draw[arr] (b1) -- node[wl, above left]{$0.1$}  (h3);

  %% OUTPUT LAYER  x = 11  (two neurons)
  \node[nrn] (o1) at (11,  2.0) {$\hat{p}_1$};
  \node[nrn] (o2) at (11, -2.0) {$\hat{p}_2$};
  \node[font=\scriptsize, right=5pt of o1] {$\leftarrow y=0$};

  %% Bias node for output (above-left of output layer)
  \node[bias] (b2) at (8.5, 4.0) {$1$};
  \draw[arr] (b2) -- node[wl, above right]{$0$} (o1);
  \draw[arr] (b2) -- node[wl, below right]{$0$} (o2);

  %% INPUT -> HIDDEN
  \draw[arr] (x1) -- node[wl, above left]{$0.2$}  (h1);
  \draw[arr] (x2) -- node[wl, below]{$0.4$}        (h1);
  \draw[arr] (x1) -- node[wl, above]{$-0.3$}       (h2);
  \draw[arr] (x2) -- node[wl, below]{$0.1$}        (h2);
  \draw[arr] (x1) -- node[wl, above]{$0.5$}        (h3);
  \draw[arr] (x2) -- node[wl, below left]{$-0.2$}  (h3);

  %% HIDDEN -> OUTPUT
  \draw[arr] (h1) -- node[wl, above left]{$0.2$}   (o1);
  \draw[arr] (h2) -- node[wl, above]{$0$}           (o1);
  \draw[arr] (h3) -- node[wl, below right]{$-0.2$} (o1);
  \draw[arr] (h1) -- node[wl, above right]{$-0.3$} (o2);
  \draw[arr] (h2) -- node[wl, below]{$0$}           (o2);
  \draw[arr] (h3) -- node[wl, below left]{$0.3$}   (o2);

  %% LAYER LABELS (bottom)
  \node[font=\scriptsize, gray] at (0,   -3.8) {Input};
  \node[font=\scriptsize, gray] at (5.5, -3.8) {Hidden (ReLU)};
  \node[font=\scriptsize, gray] at (11,  -3.8) {Output (softmax)};

\end{tikzpicture}
\end{center}

\vspace{4pt}
The same network written as explicit matrix operations (true class $y=0$):
\[
  \mathbf{z} = \underbrace{\begin{pmatrix}0.2 & 0.4\\ -0.3 & 0.1\\ 0.5 & -0.2\end{pmatrix}}_{W}
               \underbrace{\begin{pmatrix}1\\ 0.5\end{pmatrix}}_{\mathbf{x}}
             + \underbrace{\begin{pmatrix}0.1\\ 0.2\\ 0.1\end{pmatrix}}_{\mathbf{b}_1},
  \quad
  \mathbf{h} = \mathrm{ReLU}(\mathbf{z}),
\]
\[
  \boldsymbol{\theta} =
  \underbrace{\begin{pmatrix}0.2 & 0 & -0.2\\ -0.3 & 0 & 0.3\end{pmatrix}}_{U}
  \mathbf{h}
  + \underbrace{\begin{pmatrix}0\\ 0\end{pmatrix}}_{\mathbf{b}_2},
  \quad
  \hat{\mathbf{p}} = \mathrm{softmax}(\boldsymbol{\theta}),
  \quad
  J = -\log\hat{p}_0.
\]

\textit{Hint: $\partial J/\partial X$ must have the same shape as $X$. Use this as a dimension check after each step.}

\begin{enumerate}[label=(\alph*), itemsep=2pt]

  \item Compute the forward pass: $\mathbf{z}$, $\mathbf{h}$,
        $\boldsymbol{\theta}$, $\hat{\mathbf{p}}$, and $J$ (exact form).
        Which hidden neuron is dead and why?

  \item Using Q2.1, state and compute
        $\partial J/\partial\boldsymbol{\theta}$.

  \item Derive and compute $\partial J/\partial U$ and
        $\partial J/\partial \mathbf{b}_2$. State dimensions.

  \item Derive and compute $\partial J/\partial \mathbf{h}$
        and $\partial J/\partial \mathbf{z}$.
        Why is one entry of $\partial J/\partial \mathbf{z}$ zero?

  \item Derive and compute $\partial J/\partial W$ and
        $\partial J/\partial \mathbf{b}_1$. State dimensions.

  \item Perform one GD step with $t=0.1$.
        Write the updated $W^+$ and $U^+$.

\end{enumerate}

% =====================================================================
\section*{Question 3 \quad Coding \hfill (7 points)}

All models are trained on \textbf{FashionMNIST}. Use the data loader below for
all sub-questions.

% ----- Q3.0 ----------------------------------------------------------
\subsection*{3.0 \; Data Loading \textbf{(0 pts --- do not modify)}}

\begin{lstlisting}
import torch
import torchvision
import torchvision.transforms as transforms
from torch.utils.data import DataLoader

def get_FashionMNIST():
    torch.manual_seed(480)
    train_set = torchvision.datasets.FashionMNIST('./data', train=True,
                    transform=transforms.ToTensor(), download=True)
    test_set  = torchvision.datasets.FashionMNIST('./data', train=False,
                    transform=transforms.ToTensor())
    train_loader = DataLoader(train_set, batch_size=128, shuffle=True)
    test_loader  = DataLoader(test_set,  batch_size=128, shuffle=False)
    return train_loader, test_loader

train_loader, test_loader = get_FashionMNIST()
\end{lstlisting}

% ----- Q3.1 ----------------------------------------------------------
\subsection*{3.1 \; MLP \pts{2} \textbf{(coding)}}

Implement and train an MLP on FashionMNIST.

\textbf{Architecture:}
input $784$ $\to$
Linear(256) $\to$ BatchNorm $\to$ ReLU $\to$ Dropout($p=0.2$) $\to$
Linear(128) $\to$ BatchNorm $\to$ ReLU $\to$ Dropout($p=0.2$) $\to$
Linear(10).

\textbf{Training:} \texttt{CrossEntropyLoss},
SGD (lr$=0.05$, momentum$=0.9$), 10 epochs.

Complete the skeleton and report the final training and test accuracy.

\begin{lstlisting}
import torch.nn as nn
import torch.optim as optim

##### COMPLETE THE FOLLOWING CODE #####
class MLP(nn.Module):
    def __init__(self, input_dim=784, hidden1=256, hidden2=128,
                 output_dim=10, dropout_p=0.2):
        super(MLP, self).__init__()
        # TODO: define layers
        pass

    def forward(self, x):
        # TODO: flatten input then apply layers
        pass

def compute_accuracy(model, loader, device):
    model.eval()
    correct, total = 0, 0
    with torch.no_grad():
        for images, labels in loader:
            images, labels = images.to(device), labels.to(device)
            preds = model(images).argmax(dim=1)
            correct += (preds == labels).sum().item()
            total   += labels.size(0)
    return correct / total

def train(model, train_loader, test_loader,
          epochs=10, lr=0.05, device='cpu'):
    model.to(device)
    criterion = nn.CrossEntropyLoss()
    optimizer = optim.SGD(model.parameters(), lr=lr, momentum=0.9)
    for epoch in range(epochs):
        model.train()
        for images, labels in train_loader:
            images, labels = images.to(device), labels.to(device)
            optimizer.zero_grad()
            # TODO: forward pass, loss, backward, step
            pass
        tr = compute_accuracy(model, train_loader, device)
        te = compute_accuracy(model, test_loader,  device)
        print(f"Epoch {epoch+1:2d}  Train: {tr:.4f}  Test: {te:.4f}")

device = 'cuda' if torch.cuda.is_available() else 'cpu'
mlp = MLP()
train(mlp, train_loader, test_loader, device=device)
\end{lstlisting}

% ----- Q3.2 ----------------------------------------------------------
\subsection*{3.2 \; CNN \pts{4} \textbf{(coding)}}

Implement and train the CNN from \textbf{Question 1.3} on FashionMNIST.

\textbf{Architecture:} Conv(16, $5\!\times\!5$) $\to$ BatchNorm $\to$ ReLU $\to$
MaxPool($2\!\times\!2$) $\to$ Conv(32, $3\!\times\!3$) $\to$ BatchNorm $\to$ ReLU $\to$
MaxPool($2\!\times\!2$) $\to$ Flatten $\to$ Dropout($p=0.2$) $\to$ Linear(10).

\textbf{Training:} same settings as Q3.1 (reuse \texttt{train}).

Complete the skeleton and report the final training and test accuracy.

\begin{lstlisting}
##### COMPLETE THE FOLLOWING CODE #####
class CNN(nn.Module):
    def __init__(self, num_classes=10):
        super(CNN, self).__init__()
        # TODO: define layers using nn.Conv2d, nn.BatchNorm2d,
        #       nn.MaxPool2d, nn.ReLU, nn.Flatten, nn.Dropout, nn.Linear
        pass

    def forward(self, x):
        # TODO: apply layers in order
        pass

cnn = CNN()
train(cnn, train_loader, test_loader, device=device)
\end{lstlisting}

% ----- Q3.3 ----------------------------------------------------------
\subsection*{3.3 \; Comparison \pts{1} \textbf{(coding)}}

Fill in the table below with the final test accuracy of each model.

\begin{center}
\begin{tabular}{lcc}
\toprule
Model       & Training Accuracy & Test Accuracy \\
\midrule
MLP         & \quad\quad        & \quad\quad    \\
CNN         &                   &               \\
\bottomrule
\end{tabular}
\end{center}

In 2--3 sentences: which model (MLP or CNN) performs better, and give
one architectural reason that explains the difference.

% =====================================================================
\vspace{10pt}\hrule\vspace{6pt}
{\small
\textbf{Grade breakdown:}\quad
Q1.1: 3\,pts\quad
\quad
Q1.2: 3\,pts\quad
Q1.3: 4\,pts\quad
Q2.1: 1\,pt\quad
Q2.2: 7\,pts\quad
Q3.1: 2\,pts\quad
Q3.2: 4\,pts\quad
Q3.3: 1\,pt\quad
\textbf{Total: 25\,pts}
}

\end{document}
