\documentclass[11pt]{article} 
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{url}
\usepackage{fancyvrb}
\usepackage{color,hyperref}
\usepackage{enumerate}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}

\usepackage{preamble}

\begin{document}

\section*{Math 5490 -- Homework 3: Due Feb 22 by 11:59pm}
\thispagestyle{empty}

\subsection*{Instructions:}

\begin{itemize}
\item  Complete the problems below, and submit your solutions and Python code by uploading them to the Google form: \url{https://forms.gle/29WfqTaEGYi31NiJ7}
\item Submit all your Python code in a single .py file using the function templates given in each problem. I will import your functions from this file and test your code.
\item If you use LaTeX to write up your solutions, upload them as a pdf file. Students who use LaTeX to write up their solutions will receive bonus points on the homework assignment (equivalent to 1/3 of a letter grade bump).
\item If you choose to handwrite your solutions and scan them, please either use a real scanner, or use a smartphone app that allows scanning with you smartphone camera. It is not acceptable to submit photos of your solutions, as these can be hard to read.
\end{itemize}


\subsection*{Problems:}


\begin{enumerate}
\item Let $A\in \R^{m\times n}$ and $\b\in \R^n$. Recall that the least squares problem
\[\min_{\x\in \R^n} \|A\x - \b\|^2\]
has a unique solution $\x^*$ belonging to $\rng A^T$ (this is the minimal norm solution). Show that when $AA^T$ is invertible we can express $\x^*$ as 
\[\x^* = A^T(AA^T)^{-1}b.\] 
\item Complete the following parts.
\begin{enumerate}[{\normalfont (i)}]
\item Show that the linear function $F(\x)=\x\cdot \w + b$ is a convex function.
\item Show that the Euclidean norm $F(\x) = \|\x\|$ is a convex function. [Hint: Use the triangle inequality and the definition of convexity.]
\item Let $F:\R^n \to \R$ and $G:\R\to \R$ be convex functions. Assume $G$ is non-decreasing (i.e., $G(x) \leq G(y)$ whenever $x\leq y$). Show that the composition $G\circ F$, defined by
\[(G \circ F)(x) = G(F(x))\]
is a convex function. [Hint: Use the definition of a convex function directly.]
\end{enumerate}
\item For $\beta>0$ define
\[\psi_\beta(x) = \frac{1}{\beta}\log(1 + e^{\beta x}).\]
\begin{enumerate}[{\normalfont (i)}]
\item Show that 
\[\lim_{\beta \to \infty} \psi_\beta(x) =  x_+ := \max\{x,0\}.\]
\item Show that
\[\psi_\beta'(x) = \frac{1}{1 + e^{-\beta x}}.\]
\item Show that
\[\lim_{\beta \to \infty}\psi_\beta'(x) = 
\begin{cases}
1,& \text{if } x > 0,\\
\frac{1}{2},& \text{if } x = 0,\\
0,& \text{if } x < 0.
\end{cases}\]
This problem shows that the positive part $x_+$ can be well-approximated by the smooth function $\psi_\beta$. 
\end{enumerate}
\item In light of problem 3, we consider the smooth approximation of the soft-margin SVM problem given by
\[\min_{\w,b} E(\w,b),\]
where $\w\in \R^n$, $b\in \R$ and
\begin{equation}\label{eq:smooth_svm_obj}
E(\w,b) = \lambda \|\w\|^2 + \frac{1}{m}\sum_{i=1}^m \psi_\beta(1 - y_i (\x_i \cdot \w - b)).
\end{equation}
\begin{enumerate}[{\normalfont (i)}]
\item Explain why $E$ is a \emph{convex} function of $\w$ and $b$ [Hint: Use problem 2]. 
\item Show that 
\[\nabla_\w E(\w,b) = 2\lambda \w - \frac{1}{m}\sum_{i=1}^m \frac{y_i\x_i}{1+e^{-\beta(1 - y_i (\x_i \cdot \w - b))}},\]
and
\[\nabla_b E(\w,b) = \frac{1}{m}\sum_{i=1}^m \frac{y_i}{1+e^{-\beta(1 - y_i (\x_i \cdot \w - b))}}.\]
\item Write a Python program to train an SVM by minimizing $E$ via gradient descent
\begin{align*}
\w_{k+1} &= \w_k - \alpha \nabla_\w E(\w_k,b_k)\\
b_{k+1} &= b_k - \alpha \nabla_b E(\w_k,b_k).
\end{align*}
Test your program at first on some synthetic data, like the two-point example from class and the course textbook (where $\x_1=\z$ and $\x_2=-\z$). Then test your algorithm on pairs of MNIST digits. Try different pairs of MNIST digits. Which are easiest to separate? You can use \href{https://colab.research.google.com/drive/1Q5fSfNxxf7W4GmOjTIyymEeqx-jQvtPa?usp=sharing}{this notebook} as a starting place.
\end{enumerate}
\end{enumerate}

\end{document}

