<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[10pt]{article}
\usepackage[left=1.5cm, right=1.5cm, top=0.8in, bottom=0.7in]{geometry}
\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage{lastpage}
\usepackage[most,breakable]{tcolorbox}
\usepackage{pdfcol,xcolor}
\usepackage{tikz}
\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
%\usepackage{url}
\usepackage{dsfont}
\usepackage{amssymb,amsmath}
\usepackage{xspace}
\usepackage[normalem]{ulem}
\usepackage{bm}
\usepackage{enumitem}
\usepackage[breaklinks=true,colorlinks,linkcolor=magenta,urlcolor=magenta,citecolor=black]{hyperref}
\usepackage{cleveref}
\usepackage{xpatch}
\xpretocmd{\algorithm}{\hsize=\linewidth}{}{}

\newtcolorbox[auto counter]{exercise}[1][]{%
	colback=yellow!10,colframe=red!75!black,coltitle=white,use color stack,enforce breakable,enhanced,fonttitle=\bfseries,before upper={\parindent15pt\noindent}, title={\color{white}Exercise~\thetcbcounter: #1}}
\pagecolor{yellow!10}

\lhead{\textbf{University of Waterloo}}
\rhead{\textbf{2025 Winter}}
\chead{\textbf{CS480/680}}
\rfoot{\thepage/\pageref*{LastPage}}
\cfoot{\textbf{Yao-Liang Yu (yaoliang.yu@uwaterloo.ca) \textcopyright 2025}}

\newcommand{\pf}{\mathfrak{p}}
\newcommand{\qf}{\mathfrak{q}}
\newcommand{\pb}{\bar{p}}
\newcommand{\qb}{\bar{q}}
\newcommand{\pfb}{\bar{\mathfrak{p}}}
\newcommand{\qfb}{\bar{\mathfrak{q}}}
\newcommand{\rK}{\reflectbox{\ensuremath{K}}}
\newcommand{\lb}{\mathtt{lb}}
\newcommand{\ub}{\mathtt{ub}}
\newcommand{\mi}{\mathtt{maxiter}}
\newcommand{\tol}{\mathtt{tol}}
\newcommand{\softmax}{\mathsf{softmax}}
\newcommand{\KL}{\mathsf{KL}}
\newcommand{\pp}{\mathsf{p}}
\newcommand{\qq}{\mathsf{q}}
\newcommand{\Dds}{\mathds{D}}

\newcommand{\bv}{\mathbf{b}}
\newcommand{\ev}{\mathbf{e}}
\newcommand{\fv}{\mathbf{f}}
\newcommand{\gv}{\mathbf{g}}
\newcommand{\pv}{\mathbf{p}}
\newcommand{\qv}{\mathbf{q}}
\newcommand{\rv}{\mathbf{r}}
\newcommand{\uv}{\mathbf{u}}
\newcommand{\wv}{\mathbf{w}}
\newcommand{\xv}{\mathbf{x}}
\newcommand{\yv}{\mathbf{y}}
\newcommand{\zv}{\mathbf{z}}
\newcommand{\gbs}{\bm{\mathsf{g}}}
\newcommand{\wbs}{\bm{\mathsf{w}}}
\newcommand{\xbs}{\bm{\mathsf{x}}}
\newcommand{\Xv}{\mathbf{X}}
\newcommand{\Yv}{\mathbf{Y}}
\newcommand{\Bsf}{\mathsf{B}}
\newcommand{\Lsf}{\mathsf{L}}
\newcommand{\Tsf}{\mathsf{T}}
\newcommand{\Usf}{\mathsf{U}}
\newcommand{\Xsf}{\mathsf{X}}
\newcommand{\Ysf}{\mathsf{Y}}
\newcommand{\Zsf}{\mathsf{Z}}
\newcommand{\Dc}{\mathcal{D}}
\newcommand{\Nc}{\mathcal{N}}
\newcommand{\EE}{\mathds{E}}
\newcommand{\RR}{\mathds{R}}
\newcommand{\alphav}{\boldsymbol{\alpha}}
\newcommand{\betav}{\boldsymbol{\beta}}
\newcommand{\epsilonv}{\boldsymbol{\epsilon}}
\newcommand{\gammav}{\boldsymbol{\gamma}}
\newcommand{\thetav}{\boldsymbol{\theta}}

\newcommand{\ans}[1]{{\color{blue}\textsf{Ans}: #1}}
\newcommand{\argmin}{\mathop{\mathrm{argmin}}}
\newcommand{\argmax}{\mathop{\mathrm{argmax}}}
\newcommand{\diag}{\mathrm{diag}}
\newcommand{\dinner}[2]{\langle\!\langle#1,#2\rangle\!\rangle}
\newcommand{\inner}[2]{\langle #1, #2 \rangle}
\newcommand{\one}{\mathbf{1}}
\newcommand{\pred}[1]{[\![#1]\!]}
\newcommand{\prox}[1]{\mathrm{P}_{#1}}
\newcommand{\rmd}{\mathrm{d}}
\newcommand{\sgm}{\mathsf{sgm}}
\newcommand{\sign}{\mathop{\mathrm{sign}}}
\newcommand{\tr}{\mathrm{tr}}
\newcommand{\zero}{\mathbf{0}}

\newcommand{\ea}{{et al.}\xspace}
\newcommand{\eg}{{e.g.}\xspace}
\newcommand{\ie}{{i.e.}\xspace}
\newcommand{\iid}{{i.i.d.}\xspace}
\newcommand{\cf}{{cf.}\xspace}
\newcommand{\wrt}{{w.r.t.}\xspace}
\newcommand{\aka}{{a.k.a.}\xspace}
\newcommand{\etc}{{etc.}\xspace}

\newcommand{\red}[1]{{\color{red}#1}}
\newcommand{\blue}[1]{{\color{blue}#1}}
\newcommand{\magenta}[1]{{\color{magenta}#1}}
\newcommand{\green}[1]{{\color{green}#1}}
%===========================================================
\begin{document}
	
	\begin{center}
		\large{\textbf{CS480/680: Introduction to Machine Learning} \\ Homework 3\\ \red{Due: 11:59 pm, March 18, 2025}, \red{submit on LEARN and Crowdmark}.} \\
		
		{\bf \green{NAME}} \\
		{\bf \green{student number}}
		
	\end{center}
	
	\begin{center}
		Submit your writeup in pdf and all source code in a zip file (with proper documentation). Write a script for each programming exercise so that the TA can easily run and verify your results. Make sure your code runs!
		
		[Text in square brackets are hints that can be ignored.]
	\end{center}

		
	\begin{exercise}[Adaboost (5 pts)]
		In this exercise we will interpret Adaboost as minimizing the exponential loss:
		\begin{align}
		\label{eq:Adaboost}
		\min_{\alphav} ~ \frac1n\sum_{i=1}^n \exp \left[ - y_i \sum_t  \alpha_t h_t(\xv_i) \right],
		\end{align}
		where $h_t$ are the so-called weak learners, and the aggregated classifier 
		\begin{align}
			\label{eq:combined-classifer}
			h_{\alphav}(\xv) := \sum_t \alpha_t h_t(\xv). 
		\end{align}
		Note that we \red{assume $y_i \in \{\pm 1\}$} in this exercise.
		
		Let us introduce the uniform distribution $\pv_1 = \tfrac1n \one$ over our training set $\{\xv_i, y_i\}_{i=1}^n$, and rewrite \eqref{eq:Adaboost} as: 
		\begin{align}
			\min_{\alphav} ~ \EE_{\pv_1} \exp\Big[-\Ysf \sum_t \alpha_t h_t(\Xsf)\Big],
		\end{align}
		where $(\Xsf, \Ysf) \sim \pv_1$, \ie, with probability $p_{i1} = \tfrac1n$, $\Xsf = \xv_i, \Ysf=y_i$.
		
		\begin{enumerate}
		\item (1 pt) Let $q &gt; 0$ be an arbitrary function (or vector). By normalization, \ie, $q \gets q / \int q$ or $q \gets q / q^\top 1$ we obtain a density function (or probability mass function). \uline{Find probability density (vector) $\pv_2$} below so that 
		\begin{align}
			\EE_{\pv_1} \exp\Big[-\Ysf \sum_{t=1}^2 \alpha_t h_t(\Xsf)\Big] = Z_1 \cdot \EE_{\pv_2} \exp\Big[-\Ysf \sum_{t=\red{2}}^2 \alpha_t h_t(\Xsf)\Big],
		\end{align}
		\uline{as well as the formula for $Z_1$ (a positive constant)}.
		
		\ans{%
			\vskip5cm
		}

		\item (1 pt) Apply the previous exercise repeatedly with probability densities (vectors) $\pv_t$ so that 
		\begin{align}
			\EE_{\pv_1} \exp\Big[-\Ysf \sum_{t=1}^T \alpha_t h_t(\Xsf)\Big] = \prod_{t=1}^{T}Z_t,
		\end{align}
		where each $Z_t$ is a positive constant. \uline{Explain what is $Z_t$ for each $t$.}
		
		\ans{%
		\vskip6cm
		}
		
		\item (1 pt) \uline{Prove the following bound} on the training error: 
		\begin{align}
			\EE_{\pv_1} \pred{ \Ysf \underbrace{h_{\alphav}(\Xsf)}_{\hat\Ysf} \leq 0} = \EE_{\pv_1} \pred{ \Ysf \sum_{t=1}^T \alpha_t h_t(\Xsf) \leq 0} \leq \prod_{t=1}^T Z_t,
		\end{align}
		where each $Z_t$ is given in the previous exercise. Recall that $h_{\alphav}(\Xsf) = \sum_{t=1}^T \alpha_t h_t(\Xsf)$ is the aggregated classifier.
		
		\ans{% 
		\vskip6cm
		}
		
		\item (1 pt) Assuming in the $t$-th iteration we have found $h_t$. We now aim to find its coefficient $\alpha_t$ by considering the following (convex) minimization problem: 
		\begin{align}
			\label{eq:Adaboost-min}
			\min_{\alpha_t} \EE_{\pv_t} \exp[ - \Ysf \alpha_t h_t(\Xsf) ],
		\end{align}
		Suppose there is indeed a minimizer, then it must satisfy (by setting derivative to 0):
		\begin{align}
			\label{eq:Adaboost-alpha}
			0 = \EE_{\pv_t} \big\{\Ysf h_t(\Xsf) \cdot \exp[ - \Ysf \alpha_t h_t(\Xsf) ]\big\}.
		\end{align}
		From the above result \uline{deduce that} 
		\begin{align}
			0 = \EE_{\pv_{t+1}} [ \Ysf h_t(\Xsf) ],
		\end{align}
		and \uline{show that} for (deterministic) weak classifiers $h_t \in \{\pm 1\}$:
		\begin{align}
			\EE_{\pv_{t+1}} \pred{h_t(\Xsf) \ne \Ysf} = \tfrac12,
		\end{align}
		namely that in the next iteration $t+1$, the previous classifier $h_t$ has error exactly $\tfrac12$.

		\ans{%
		\vskip5cm
		}

		\item (1 pt) 
		In \eqref{eq:Adaboost-alpha} above we obtained a nonlinear equation of $\alpha_t$. Although it is possible to find $\alpha_t$ through numerical root finding algorithms, we prefer to derive a closed-form solution. Assuming $h_t \in [-1, 1]$ is given, we can apply the bound (the so-called \href{https://en.wikipedia.org/wiki/Jensen%27s_inequality}{Jensen's inequality})
		\begin{align}
			\exp(-\alpha u) \leq \frac{1+u}{2}\exp(-\alpha) + \frac{1-u}{2}\exp(\alpha)
		\end{align}
		to \eqref{eq:Adaboost-min} first and then \uline{derive the optimal $\alpha_t$}.

		[This is essentially the coefficient $\log\tfrac{1}{\beta_t}$ that we saw in class, up to some trivial changes.]

		\ans{%
		\vskip6cm
		}

		\item[] {\color{gray} (Remark) We have not talked much about choosing weak classifiers $h_t$. Here is the catch: we could simply pretend we enumerate \red{all} weak classifiers (infinitely many!) in our final aggregate $h_{\alphav}$. All we need to figure out is the weight $\alpha_t$ that we assign to each weak classifier $h_t$, and a zero $\alpha$ means the corresponding weak classifier is effectively discarded. The Adaboost algorithm starts with $\alpha \equiv 0$ and only changes one $\alpha$ into nonzero in each iteration. Thus, after $T$ iterations, we have at most $T$ nonzero $\alpha$'s. On a high level, this is very similar to kernels where the dual problem only involves $n$ nonzero Lagrangian multiplier $\alpha$'s ($n$ being the size of the training set). See, we do not need to fear infinite dimensions!}
		\end{enumerate}
	\end{exercise}
	


	\begin{exercise}[Vision Transformers (10 pts)]
		Please follow the instructions of this \href{https://cs.uwaterloo.ca/~y328yu/teaching/480/assignments/a3-vit.ipynb}{\texttt{ipynb} file}. 

		\begin{enumerate}
		\item (1+3+2 = 6 pts) Complete the missing coding parts in the provided \href{https://cs.uwaterloo.ca/~y328yu/teaching/480/assignments/a3-vit.ipynb}{\texttt{ipynb} file}.

		\item (1 pt) Visualization of patches: 

		\includegraphics[width=.45\textwidth]{example-image-a}\includegraphics[width=.45\textwidth]{example-image-b}
		
		\includegraphics[width=.45\textwidth]{example-image-a}\includegraphics[width=.45\textwidth]{example-image-b}
		
		\item (1 pt) The test accuracy I obtained on MNIST is: {\color{blue} xxx\%}

		\item (2 pts) Training / Validation accuracy  vs. epoch:

		\includegraphics[width=.45\textwidth]{example-image-a}
		\includegraphics[width=.45\textwidth]{example-image-b}
		\end{enumerate}
	\end{exercise}


	
	\begin{exercise}[Generative Adversarial Networks (5 pts)]
		Let us consider the game between the generator $\qq(\xv)$ (the implicit density of $\Tsf_{\thetav}(\Zsf)$) and the discriminator $S(\xv)$:
		\begin{align}
			\label{eq:GAN-min-max}
		\inf_{\qq} ~\sup_{S} ~ \int_{\xv} S(\xv) \pp(\xv) \rmd \xv + \int_{\xv} \log\big(1-\exp(S(\xv))\big) \qq(\xv) \rmd \xv + \log 4.
		\end{align}
		We remind that $\qq$ is a probability density (so is $\pp$ which is given) while $S$ is any real-valued function. 
		\begin{enumerate}
		\item (1 pt) Fix an arbitrary generator $\qq$ and \uline{find the resulting optimal discriminator $S$}.
		
		\ans{%
		\vskip4cm
		}

		\item (1 pt) Plug the optimal discriminator $S$ above back to \eqref{eq:GAN-min-max} and \uline{find the optimal generator $\qq$}.
		
		\ans{%
		\vskip4cm
		}
		\end{enumerate}

		Now we swap the order of the two players: 
		\begin{align}
			\label{eq:GAN-max-min}
			\sup_{S} ~ \inf_{\qq} ~\int_{\xv} S(\xv) \pp(\xv) \rmd \xv + \int_{\xv} \log\big(1-\exp(S(\xv))\big) \qq(\xv) \rmd \xv + \log 4.
		\end{align}
		\begin{enumerate}[resume]
		
		\item (1 pt) Fix an arbitrary discriminator $S$ and \uline{find an optimal generator $\qq$}.
		
		\ans{%
		\vskip4cm
		}
		
		\item (1 pt) Plug the optimal generator $\qq$ above back to \eqref{eq:GAN-max-min} and \uline{find the optimal discriminator $S$}. 
		
		[Hint: average $\leq$ max.]
		
		\ans{%
		\vskip4cm
		}
		
		\item (1 pt) Let $f: \RR_+ \to \RR$ be a convex function. We see in class that the $f$-divergence admits the following variational form:
		\begin{align}
			\red{-} \Dds_{f}(\pp \| \qq) = \inf_{S: \RR^d \to [0,1]} -\EE_{\Xsf\sim \pp} [ S(\Xsf) ] + \EE_{\Xsf\sim \qq} [f^*(S(\Xsf))],
		\end{align}
		where for simplicity we have restricted the range of $S$ to $[0,1]$. Now consider the following distribution $(\Xsf, \Ysf) \sim \Dc$ where $\Ysf = \pm1$ with equal probability while 
		\begin{align}
			[\Xsf \mid \Ysf = 1] ~\sim~ \pp \mbox{ and } [\Xsf \mid \Ysf = -1] ~\sim~ \qq.
		\end{align}
		We claim that 
		\begin{align}
			\red{-\tfrac12} \Dds_{f}(\pp \| \qq) = \inf_{S: \RR^d \to [0,1]} ~ \EE_{(\Xsf, \Ysf)\sim \Dc}[\ell(\Ysf, S(\Xsf))].
		\end{align}
		\uline{Express the binary loss function $\ell$ in terms of $f$.} Thus, given an $f$-divergence, we may rewrite it as a binary classification problem! {\color{gray}Conversely, given any \emph{proper} loss function $\ell$, we may reverse the argument and induce an $f$-divergence from the binary loss $\ell$.}

		\ans{%
		\vskip4cm
		}
		\end{enumerate}
	\end{exercise}
\end{document}
              </pre></body></html>