\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{url, hyperref}

\renewcommand{\Pr}[1]{\mathbb{P}\left[#1\right]}
\newcommand{\Ex}[1]{\mathbb{E}\left[#1\right]}
\newcommand{\Var}[1]{\text{Var}\left[#1\right]}

\renewcommand{\bf}[1]{\mathbf{#1}}
\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\mat}[1]{\ensuremath{\begin{pmatrix} #1 \end{pmatrix}}}
% Functions using mathrm
\renewcommand{\dim}{\mathrm{dim}}
\newcommand{\OPT}{\textup{\textsf{OPT}}}
\newcommand{\opt}{\textup{\textsf{opt}}}
\newcommand{\range}{\mathcal{range}}
\newcommand{\sign}{\textup{\textsf{sign}}}
\DeclareMathOperator{\sgn}{\textup{\textsf{sign}}}
\DeclareMathOperator{\diag}{\textsf{Diag}}
\newcommand{\ber}{\textup{\textsf{Ber}}}
\newcommand{\err}{\mathrm{err}}
\newcommand{\gen}{(\frac{\nu}{12})}
\newcommand{\error}{\mathrm{err}}
\newcommand{\hinge}{\mathrm{hinge}}
\newcommand{\erf}{\mathrm{erf}}
\newcommand{\Appendix}[1]{the full version for}
\newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}}


\newtheorem{problem}{Problem}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{assumption}{Assumption}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{condition}{Condition}
\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}
\renewcommand{\a}{\mathbf{a}}
\renewcommand{\b}{\mathbf{b}}
\renewcommand{\c}{\mathbf{c}}
\newcommand{\e}{\mathbf{e}}
\newcommand{\g}{\mathbf{g}}
\newcommand{\s}{\mathbf{s}}
\renewcommand{\u}{\mathbf{u}}
\renewcommand{\v}{\mathbf{v}}
\newcommand{\w}{\mathbf{w}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\z}{\mathbf{z}}
\newcommand{\A}{\mathbf{A}}
\newcommand{\B}{\mathbf{B}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\D}{\mathbf{D}}
\newcommand{\E}{\mathbf{E}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\G}{\mathbf{G}}
\renewcommand{\H}{\mathbf{H}}
\newcommand{\I}{\mathbf{I}}
\newcommand{\K}{\mathcal{K}}
\renewcommand{\L}{\mathbf{L}}
\newcommand{\M}{\mathbf{M}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\Q}{\mathbf{Q}}
\newcommand{\R}{\mathbb{R}}
\renewcommand{\S}{\mathbf{S}}
\newcommand{\T}{\mathbf{T}}
\newcommand{\U}{\mathbf{U}}
\newcommand{\V}{\mathbf{V}}
\newcommand{\W}{\mathbf{W}}
\newcommand{\X}{\mathbf{X}}
\newcommand{\Y}{\mathbf{Y}}
\newcommand{\Z}{\mathbf{Z}}
\newcommand{\rank}{\mathsf{rank}}
\newcommand{\orthc}{\mathbf{orth}_c}
\newcommand{\orthr}{\mathbf{orth}_r}
\newcommand{\bLambda}{\mathbf{\Lambda}}
\newcommand{\0}{\mathbf{0}}
\newcommand{\1}{\mathbf{1}}
\newcommand{\red}[1]{{\color{red}#1}}
\newcommand{\blue}[1]{{\color{blue}#1}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\bits}{\{ 0, 1 \}}

\newcommand{\bbF}{\mathbb{F}}
\newcommand{\bO}{\mathbf{O}}

\newcommand{\sXOR}{\mathsf{XOR}}
\newcommand{\sAND}{\mathsf{AND}}
\newcommand{\BHH}{\mathsf{BHH}}
\newcommand{\RS}{\mathsf{RS}}
\newcommand{\YES}{\mathsf{YES}}
\newcommand{\NO}{\mathsf{NO}}
\newcommand{\srank}{\mathsf{srank}}

\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator{\erfc}{erfc}
\DeclareMathOperator*{\bbE}{\mathbb{E}}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\poly}{\mathsf{poly}}
\DeclareMathOperator{\polylog}{\mathsf{polylog}}

\newcommand{\case}[2][lllllllllllllllllllllllllllllllllllll]{\left\{\begin{array}{#1}#2 \\ \end{array}\right.}

\usepackage{mathtools}
\usepackage{amsmath}
\newcommand{\paren}[1]{\left( #1 \right)}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\brc}[1]{\left\{ #1 \right\}}
\newcommand{\iprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\llnorm}[1]{\left\| #1 \right\|_2}
\newcommand{\brk}[1]{\left[ #1 \right]}
\newcommand{\mnorm}[2]{\left\| #2 \right\|_{#1}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\fnorm}[1]{\left\| #1 \right\|_F}
\newcommand{\id}{\mathbb{I}}
\newtheorem{question}{Question}

\title{\large CS480/680, Spring 2026\\\huge Assignment 1}

\author{Designer: Wenyu Bo; Instructor: Hongyang Zhang}
\date{Released: May 13; Due: June 8, noon}
\setlength\parindent{0pt}

%\input{preamble}

\begin{document}

\maketitle

\subsection*{Instructions}

\begin{itemize}
    \item We do not accept hand-written submissions.
    \item This assignment is due by noon on June 8, 2026.
    \item For questions labelled as ``\textbf{coding}'', please follow the instructions provided and implement the required features.
    Unless otherwise specified, all implementations should be in \emph{Python} using a \emph{Jupyter Notebook}.
    Before submission, please make sure that your code can run without any errors.
    Also, be sure to save the output of each cell, as any missing output may not be graded.
    \item Please submit the following TWO files to LEARN:
    \begin{itemize}
        \item A write-up in PDF format: the written answers to ALL questions, including the reported results and plots of coding questions, in a single PDF file.
        \item An IPYNB file: your implementations for ALL coding questions. Please save the output of each cell, or your coding questions may NOT be graded.
    \end{itemize}
\end{itemize}

\newpage
\begin{question}[SVM - 10 points]
~
\begin{enumerate}
    \item ($4$ points)
    Assume that the data set is linearly separable. 
    \begin{enumerate} 
        \item ($3$ points) Prove that removing any non support vector ($\alpha = 0$) from data set does not change SVM solution using dual conditions.
        \item ($1$ point) Let $f_{-i}$ be the SVM trained on $D_{-i} = D \setminus \{(x_i,y_i)\}$, and $L$ be the error rate, i.e. $L = \frac{|\{i: f_{-i}(x_i) \neq y_i\}|}{n}$, prove that $L \leq \frac{|\text{support vector of } f|}{n}$ where $f$ is the SVM trained on $D$.
    \end{enumerate}

    \item ($6$ points) Assume data points are $1$ dimensional, and two classes. Consider the polynomial kernel $k(x,x') = (1+xx')^2$.
    \begin{enumerate}
        \item ($1$ point) Find the map $\phi: \R \to \R^d$ such that $k(x,x') = \phi(x)^T \phi(x')$.
        \item ($1$ point)Let $D = \{(-1,+1),(0,-1),(1,+1)\}$, Using the map $\phi$ found in the previous part, write down the primal SVM problem for this data set. You need to give the explicit numerical values.
        \item ($1$ point)Write the expression of the dual SVM problem for this data set. You need to give the explicit numerical values.
        \item ($2$ points) Solve the dual SVM problem.
        \item ($1$ point) Write down the classifier $f(x) = \text{sign}(w^T \phi(x) + b)$, and report the dicision boundary.
    \end{enumerate}
\end{enumerate}
\end{question}

\medskip


\begin{question}[Regression on MNIST - 15 points]

    In this problem, we will implement regularized classifiers for the MNIST data set. The task is to classify handwritten images of numbers between $0$ to $9$.

    Each example has features $x_i \in \R^d$ (with $d=28*28=784$) and label $z_j \in \{0,\dots,9\}$. We wish to learn a predictor $\hat{f}$ that takes as input a vector in $\R^d$ and outputs an index in $\{0,\dots,9\}$. We define our training and testing classification error on a predictor $f$ as
    \begin{align*}
        \widehat{\epsilon}_{\textrm{train}}(f) &=
        \frac{1}{N _{\textrm{train}}} \sum_{(x,z)\in \textrm{Training Set}}     \1\{ f(x) \neq z \},
        \\
          \widehat{\epsilon}_{\textrm{test}}(f) &=
          \frac{1}{N _{\textrm{test}}} \sum_{(x,z)\in \textrm{Test Set}}     \1\{ f(x) \neq z \}. 
    \end{align*}
    
    We will use one-hot encoding of the labels: for each observation $(x,z)$, the original label $z \in \{0, \ldots, 9\}$ is mapped to the standard basis vector $e_{z+1}$ where $e_i$ is a vector of size $k$ containing all zeros except for a $1$ in the $i^{\textrm{th}}$ position (positions in these vectors are indexed starting at one, hence the $z+1$ offset for the digit labels). We adopt the notation where we have $n$ data points in our training objective with features $x_i \in \R^d$ and label one-hot encoded as $y_i \in \{0,1\}^k$. Here, $k=10$ since there are 10 digits.
    
    \begin{enumerate}
        \item ($2$ points)
        
        In this problem we will choose a linear classifier to minimize the regularized least squares objective:
        \begin{align*}
            \widehat{W} = \text{argmin}_{W \in \R^{d \times k}} \| X W - Y \|^{2}_{F} + \lambda \|W\|_{F}^{2}.
        \end{align*}
        Note that $\|W\|_{F}$ corresponds to the Frobenius norm of $W$, i.e. $\|W\|_{F}^{2} = \sum_{i=1}^d \sum_{j=1}^k W_{i,j}^2$. Show that
        \begin{align*}
            \widehat{W} = (X^T X + \lambda I)^{-1} X^T Y.
        \end{align*} 

        \bigskip
        
        \item ($5$ points, coding)
        \begin{itemize}
            \item Implement a function \verb|train| that takes as input $X \in\R^{n \times d}$, $Y \in \{0,1\}^{n \times k}$, $\lambda > 0$ and returns $\widehat{W} \in \R^{d \times k}$.
            \item Implement a function \verb|one_hot| that takes as input $Y \in \{0, ..., k-1\}^{n}$, and returns $Y \in \{0,1\}^{n \times k}$.
            \item Implement a function  \verb|predict| that takes as input $W \in \R^{d \times k}$, $X' \in\R^{m \times d}$ and returns an $m$-length vector with the $i$th entry equal to $\arg\max_{j=0,\dots,9} x'_i W e_{j+1}^T$.
            \item Using the functions you coded above, train a model to estimate $\widehat{W}$ on the MNIST training data with $\lambda = 10^{-4}$, and make label predictions on the test data.
        \end{itemize}
        
         \item ($1$ point, coding) 
         What are the training and testing errors of the classifier trained as above?

        \item ($7$ points)
        Consider softmax classifier, the loss function is defined as \begin{align*}
            l = -\frac{1}{n} \sum_{i=1}^n \log \frac{\exp \left(x_i W_{y_i}\right)}{\sum_{l = 1}^k \exp \left(x_i W_l\right)} + \frac{\lambda}{2}\|W\|_F^2.
        \end{align*}
        where $W_{y_i}$ is the $y_i+1$-th column of $W$ (label $0$ means the first column), $W_l$ is the $l$-th column of $W$. 
        \begin{itemize}
            \item ($2$ points) Derive the gradient of the loss function with respect to $W$.
            \item ($3$ points, coding)
            Implement a function \verb|grad_descent| that takes as imput $X \in \R^{n \times d}$, $Y \in \{0,1\}^{n \times k}$, $\lambda > 0$, learning rate $\eta > 0 $, and number of iteration $T$, and returns $\widehat{W} \in \R^{d \times k}$ after performing $T$ steps of gradient descent. 
        
            Using the function you coded above, train a softmax classifier on the MNIST training data with $\lambda = 10^{-4}$, learning rate $\eta = 0.1$, and $T = 500$, and make label predictions on the test data (The prediction function is the same as in part (2)). 
        
            \item ($2$ points, coding)
            Report the training and testing errors of the resulting classifier, and plot the training loss as a function of the iteration number.
        \end{itemize}
    \end{enumerate}


\end{question}



\end{document}