\documentclass{article}
\usepackage{import}
\subimport*{../../}{macro}

\usepackage{import}
\usepackage[ruled]{algorithm2e}
\usepackage[shortlabels]{enumitem}

\setlength\parindent{0px}

\begin{document}
\setcounter{aprob}{0}
\setcounter{bprob}{0}
\title{Homework \#2}
\author{
    \normalsize{CSE 446: Machine Learning}\\
    \normalsize{Prof. Sewoong Oh}\\
    \normalsize{Due: \textbf{Friday} February 11th, 2022 11:59pm}\\
    \normalsize{108 points}
}
\date{{}}
\maketitle

\noindent Please review all homework guidance posted on the website before submitting to GradeScope. Reminders:
\begin{itemize}
    \item Make sure to read the ``What to Submit'' section following each question and include all items.
    \item Please provide succinct answers and supporting reasoning for each question. Similarly, when discussing experimental results, concisely create tables and/or figures when appropriate to organize the experimental results. All explanations, tables, and figures for any particular part of a question must be grouped together. 
    \item For every problem involving generating plots, please include the plots as part of your PDF submission.
    \item When submitting to Gradescope, please link each question from the homework in Gradescope to the location of its answer in your homework PDF. Failure to do so may result in deductions of up to \points{5}. For instructions, see \url{https://www.gradescope.com/get_started#student-submission}.
    \item If you collaborate on this homework with others, you must indicate who you worked with on your homework. Failure to do so may result in accusations of plagiarism.
    \item Please indicate your final answer to each question by placing a box around the main result(s). To do this in \LaTeX, one option is using the \texttt{boxed} command.
\end{itemize}

Not adhering to these reminders may result in point deductions. \\

% \textcolor{red}{\textbf{Changelog:}}

% \begin{itemize}
%     \item \textbf{Date:} Changed This.
% \end{itemize}

\clearpage{}


% Start of Problems:

\begin{aprob}
    The answers to these questions should be answerable without referring to external materials.
    Briefly justify your answers with a few words.
    \begin{enumerate}
      \item \points{2} Why is it necessary to apply the gradient descent algorithm on logistic regression but not linear regression?
      \item \points{2} Compared to L2 norm penalty, explain why a L1 norm penalty is more likely to result in sparsity (a larger number of 0s) in the weight vector.
      \item \points{2} In at most one sentence each, state one possible upside and one possible downside of using the following regularizer: $\left(\sum_{i}\left|w_{i}\right|^{0.5}\right)$.
      \item \points{1} True or False: If the step-size for gradient descent is too large, it may not converge.
      \item \points{2} In your own words, describe why stochastic gradient descent (SGD) works, even though only a small portion of the data is considered at each update.
      \item \points{2} In at most one sentence each, state one possible advantage of SGD over GD (gradient descent), and one possible disadvantage of SGD relative to GD.
    \end{enumerate}
    
    \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{Part d:} True or False. 
        \item \textbf{Parts a-f:} Brief (2-3 sentence) explanation.
    \end{itemize}
\end{aprob}

\section*{Convexity and Norms }

\begin{aprob}
    A \emph{norm} $\|\cdot\|$ over $\R^n$ is defined by the properties:
    (\textit{i}) non-negativity: $\|x\|\geq 0$ for all $x \in \R^n$ with equality if and only if $x=0$,
    (\textit{ii}) absolute scalability: $\|a \, x\| = |a| \, \|x\|$ for all $a \in \R$ and $x \in \R^n$, 
    (\textit{iii}) triangle inequality: $\|x+y\| \leq \|x\| + \|y\|$ for all $x,y \in \R^n$.
    \begin{enumerate}
      \item \points{3} Show that $f(x) = \left( \sum_{i=1}^n |x_i| \right)$ is a norm. (Hint: for (\textit{iii}), begin by showing that $|a+b|\leq |a| + |b|$ for all $a,b \in \R$.)
      \item \points{2} Show that $g(x) = \left(\sum_{i=1}^n |x_i|^{1/2}\right)^2$ is not a norm. (Hint: it suffices to find two points in $n=2$ dimensions such that the triangle inequality does not hold.)
    \end{enumerate} 
    Context: norms are often used in regularization to encourage specific behaviors of solutions. If we define  $\| x \|_p := \left( \sum_{i=1}^n |x_i|^{p} \right)^{1/p}$ then one can show that $\| x \|_p$ is a norm for all $p \geq 1$. The important cases of $p=2$ and $p=1$ correspond to the penalty for ridge regression and the lasso, respectively. \\
    
    \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{Parts a, b:} Proof.
    \end{itemize}
\end{aprob}

\begin{aprob}
    \points{3} A set $A \subseteq \R^n$ is \emph{convex} if $\lambda x + (1-\lambda) y \in A$ for all $x,y\in A$ and $\lambda \in [0,1]$.
    For each of the grey-shaded sets below (I-III), state whether each one is convex, or state why it is not convex using any of the points $a,b,c,d$ in your answer. 
    
    \begin{figure}[H]
        \centering
        \includegraphics[width=.6\textwidth]{../img/convex_shapes.png}
    \end{figure}

    \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{Parts I-III:} 1-2 sentence explanation of why the diagram is convex or not.
    \end{itemize}
\end{aprob}

\begin{aprob}
    \points{4} We say a function $f: \R^d \rightarrow \R$ is convex on a set $A$ if $f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)$ for all $x,y\in A$ and $\lambda \in [0,1]$. For each of the functions shown below (I-III), state whether each is convex on the specified interval, or state why not with a counterexample using any of the points $a,b,c,d$ in your answer.

    \begin{figure}[H]
        \centering
        \includegraphics[width=.75\textwidth]{../img/convex_functions.png}
    \end{figure}

    \begin{enumerate}
        \item Function in panel I on $[a,c]$
        \item Function in panel II on $[a,c]$
        \item Function in panel III on $[a,d]$
        \item Function in panel III on $[c,d]$
    \end{enumerate}

    \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{Parts a-d:} 1-2 sentence explanation of why the function is convex or not.
    \end{itemize}
\end{aprob}

\section*{Lasso on a Real Dataset}
Given $\lambda >0$ and data $\Big (x_i,y_i \Big)_{i=1}^n$, the Lasso is the problem of solving
\begin{equation*}\label{eq:lasso}
  \arg\min_{{w}\in \R^d, b \in \R} \sum_{i=1}^n { (x_i^T {w} + b - {y}_i)^2 }
    + \lambda \sum_{j=1}^d |{w}_j| 
\end{equation*}
where $\lambda$ is a regularization parameter.
For the programming part of this homework, you will implement the coordinate descent method shown in Algorithm~\ref{alg:cd} to solve the Lasso problem.

You may use common computing packages (such as \texttt{numpy} or \texttt{scipy}), but do not use an existing Lasso solver (e.g., of \texttt{scikit-learn}).

\begin{algorithm}[h]
    \caption{Coordinate Descent Algorithm for Lasso}\label{alg:cd}
    \While{not converged}{
      $b \leftarrow \frac{1}{n}\sum_{i=1}^n \left({y}_i - \sum_{j=1}^d {w}_j {x}_{i,j}\right)$\\ 
      \For{$k \in \{1,2,\cdots d\}$} {
        $a_k\leftarrow 2 \sum_{i=1}^n {x}_{i,k}^2$ \\   
        $c_k\leftarrow 2 \sum_{i=1}^n {x}_{i,k} \left({y}_i -(b + \sum_{j\neq k} {w}_j {x}_{i,j} )\right)$ \\
        ${w}_k \leftarrow 
        \left\{
        \begin{array}{ll}
          (c_k+\lambda) / a_k & c_k < -\lambda\\
          0 & c_k\in [-\lambda, \lambda]\\
          (c_k-\lambda) / a_k & c_k > \lambda\\
        \end{array}  
        \right.
        $
      }
    }
\end{algorithm}

Before you get started, the following hints may be useful:
\begin{itemize}
  \item Wherever possible, use matrix libraries for matrix operations (not \texttt{for} loops).
  \item There are opportunities to considerably speed up parts of the algorithm by precomputing quantities like $a_k$ before the for loop; you are permitted to add these improvements (and it may save you some time).
  \item As a sanity check, ensure the objective value is nonincreasing with each step. 
  \item It is up to you to decide on a suitable stopping condition.  A common criteria is to stop when no element of
      ${w}$ changes by more than some small $\delta$ during an iteration.  If you need your algorithm to run faster,
      an easy place to start is to loosen this condition.
  \item You will need to solve the Lasso on the same dataset for many values of $\lambda$.  This
      is called a regularization path.  One way to do this efficiently is to start at a large $\lambda$, and then for each consecutive solution, initialize the algorithm with the previous solution, decreasing $\lambda$ by a constant ratio (e.g., by a factor of $2$).
  \item The smallest value of $\lambda$ for which the solution $\widehat{w}$ is entirely zero is given by
       \begin{align}
           \lambda_{max} = \max_{k=1,\dots,d} 2 \left|\sum_{i=1}^n {x}_{i,k} \left({y}_i - \left(\frac{1}{n} \sum_{j=1}^n y_j \right)\right)\right|\label{eqn:lasso-lambdamax}
       \end{align}
      This is helpful for choosing the first $\lambda$ in a regularization path. 
\end{itemize}

\begin{aprob}
    We will first try out your solver with some synthetic data.
    A benefit of the Lasso is that if we believe many features are irrelevant for predicting ${y}$, the Lasso can be used to enforce a sparse solution, effectively differentiating between the relevant and irrelevant features.
    Suppose that ${x} \in \mathbb{R}^d, y \in \mathbb{R}, k < d$, and data are generated independently according to the model $y_i = w^T x_i + \epsilon_i$ where
    \begin{align}
        w_j = \begin{cases} j/k & \text{if } j \in \{1,\dots,k\} \\
        0 & \text{otherwise}
        \end{cases}\label{eqn:lasso-model}
    \end{align} 
    and $\epsilon_i \sim \mathcal{N}(0, \sigma^2)$ is noise (note that in the model above $b=0$). We can see from Equation \eqref{eqn:lasso-model} that since $k < d$ and $w_j = 0$ for $j > k$, the features $k + 1$ through $d$ are irrelevant for predicting $y$.
    
    Generate a dataset using this model with $n = 500, d = 1000, k = 100,$ and $\sigma = 1$. You should generate the dataset such that each $\epsilon_i \sim \mathcal{N}(0, 1)$ , and $y_i$ is generated as specified above. You are free to choose a distribution from which the $x$'s are drawn, but make sure standardize the $x$'s before running your experiments.

    \begin{enumerate}
        \item \points{10} With your synthetic data, solve multiple Lasso problems on a regularization path, starting at $\lambda_{max}$ where no features are selected (see Equation \eqref{eqn:lasso-lambdamax}) and decreasing $\lambda$ by a constant ratio (e.g., 2) until nearly all the features are chosen. 
        In plot 1, plot the number of non-zeros as a function of $\lambda$ on the x-axis (Tip: use \verb|plt.xscale('log')|).
        \item \points{10} For each value of $\lambda$ tried, record values for false discovery rate (FDR) (number of incorrect nonzeros in $\widehat{w}$/total number of nonzeros in $\widehat{w}$) and true positive rate (TPR)
        (number of correct nonzeros in $\widehat{w}$/k). Note: for each $j$, $\widehat{w}_j$ is an incorrect nonzero if and only if $\widehat{w}_j \neq 0$ while $w_j = 0$.
        In plot 2, plot these values with the x-axis as FDR, and the y-axis as TPR.
          
        Note that in an ideal situation we would have an (FDR,TPR) pair in the upper left corner. We can always trivially achieve $(0,0)$ and $(\tfrac{d-k}{d},1)$.
          
        \item \points{5} Comment on the effect of $\lambda$ in these two plots in 1-2 sentences.
  \end{enumerate}
  
  \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{Part a:} Plot 1.
        \item \textbf{Part b:} Plot 2.
        \item \textbf{Part c:} 1-2 sentence explanation.
        \item \textbf{Code} on Gradescope through coding submission
    \end{itemize}
  \end{aprob}
  
\begin{aprob}
    \label{crime} 
    We'll now put the Lasso to work on some real data.  Download the training data set ``crime-train.txt'' and the test data set ``crime-test.txt'' from the website. Store your data in your working directory, ensure you have the \texttt{pandas} library for Python installed, and read in the files with:
    
    \begin{verbatim}
        import pandas as pd
        df_train = pd.read_table("crime-train.txt")
        df_test = pd.read_table("crime-test.txt")
    \end{verbatim}

    This stores the data as Pandas \texttt{DataFrame} objects. \texttt{DataFrame}s are similar to Numpy \texttt{array}s but more flexible; unlike \texttt{array}s, \texttt{DataFrame}s store row and column indices along with the values of the data. Each column of a \texttt{DataFrame} can also store data of a different type (here, all data are floats). 
    Here are a few commands that will get you working with Pandas for this assignment:

    \begin{verbatim}
        df.head()                   # Print the first few lines of DataFrame df.
        df.index                    # Get the row indices for df.
        df.columns                  # Get the column indices.
        df[``foo'']                # Return the column named ``foo''.
        df.drop(``foo'', axis = 1)  # Return all columns except ``foo''.
        df.values                   # Return the values as a Numpy array.
        df[``foo''].values         # Grab column foo and convert to Numpy array.
        df.iloc[:3,:3]              # Use numerical indices (like Numpy) to get 3 rows and cols.
    \end{verbatim}

    The data consist of local crime statistics for 1,994 US
    communities. The response $y$ is the rate of violent crimes reported per capita in a community. The name of the response variable is \texttt{ViolentCrimesPerPop}, and it is held in the first column of \texttt{df\_train} and \texttt{df\_test}. There are 95 features. These
    features include many variables.
    
    Some features are the consequence of complex political processes, such as the size of the police force and other systemic and historical factors. Others are demographic
    characteristics of the community, including self-reported statistics about race, age, education, and employment drawn from Census reports.\\
    
    \emph{The goals of this problem are threefold: ($i$) to encourage you to think about how data collection processes affect the resulting model trained from that data; ($ii$) to encourage you to think deeply about models you might train and how they might be misused; and ($iii$) to see how Lasso encourages sparsity of linear models in settings where $d$ is large relative to $n$.} {\bf We emphasize that training a model on this dataset can suggest a degree of correlation between a community's demographics and the rate at which a community experiences and reports violent crime. We strongly encourage students to consider why these correlations may or may not hold more generally, whether correlations might result from a common cause, and what issues can result in misinterpreting what a model can explain.}\\

    The dataset is split into a training and test set with 1,595 and 399 entries, respectively\footnote{The features have been standardized to have mean 0 and variance 1.}. 
    We will use this training set to fit a model to predict
    the crime rate in new communities and evaluate model performance on the test set.  As there are a considerable number of input variables and fairly few training observations, overfitting is a serious issue.
    In order to avoid this, use the coordinate descent Lasso algorithm implemented in the previous problem. 

    \begin{enumerate}
        \item \points{4} Read the documentation for the originalcversion of this dataset: \url{http://archive.ics.uci.edu/ml/datasets/communities+and+crime}. Report 3 features included in this dataset for which historical \emph{policy} choices in the US would lead to variability in these features. As an example, the \emph{number of police} in a community is often the consequence of decisions made by governing bodies, elections, and amount of tax revenue available to decision makers.
        \item \points{4} Before you train a model, describe 3 features in the dataset which might, if found to have nonzero weight in model, be interpreted as \emph{reasons} for higher levels of violent crime, but which might actually be a \emph{result} rather than (or in addition to being) the cause of this violence.
    \end{enumerate}

    Now, we will run the Lasso solver. Begin with $\lambda = \lambda_{\max}$ defined in Equation \eqref{eqn:lasso-lambdamax}. Initialize all weights to $0$. Then, reduce $\lambda$ by a factor of 2 and run again, but this time initialize $\hat{{w}}$ from your $\lambda = \lambda_{\max}$ solution as your initial weights, as described above. Continue the process of reducing $\lambda$ by a factor of 2 until $\lambda < 0.01$.
    For all plots use a log-scale for the $\lambda$ dimension (Tip: use
    \verb|plt.xscale('log')|).
    \\
    
    
    \begin{enumerate}
        \item[c.] \points{4} Plot the number of nonzero weights of each solution as a function of $\lambda$.
        \item[d.] \points{4} Plot the regularization paths (in one plot) for the coefficients for input variables \texttt{agePct12t29}, \texttt{pctWSocSec}, \texttt{pctUrban}, \texttt{agePct65up}, and \texttt{householdsize}.
        \item[e.] \points{4} On one plot, plot the squared error on the training and test data as a function of $\lambda$.
        \item[f.] \points{4} Sometimes a larger value of $\lambda$ performs nearly as well as a smaller value, but a larger value will select fewer variables and perhaps be more interpretable.  Inspect the weights $\hat{w}$ for $\lambda = 30$.  Which feature had the largest (most positive) Lasso coefficient? What about the most negative? Discuss briefly.
        \item[g.] \points{4} Suppose there was a large negative weight on \texttt{agePct65up} and upon seeing this result, a politician suggests policies that encourage people over the age of 65 to move to high crime areas in an effort to reduce crime. What is the (statistical) flaw in this line of reasoning? (Hint: fire trucks
        are often seen around burning buildings, do fire trucks cause fire?)
    \end{enumerate}  

    \subsection*{What to Submit:}
    \begin{itemize}
        \item \textbf{Parts a, b:} 1-2 sentence explanation.
        \item \textbf{Part c:} Plot 1.
        \item \textbf{Part d:} Plot 2.
        \item \textbf{Part e:} Plot 3.
        \item \textbf{Parts f, g:} Answers and 1-2 sentence explanation.
        \item \textbf{Code} on Gradescope through coding submission.
    \end{itemize}
\end{aprob}

\section*{Logistic Regression}
\subsection*{Binary Logistic Regression} 
\begin{aprob}
    Here we consider the MNIST dataset, but for binary classification. Specifically, the task is to determine whether a digit is a $2$ or $7$.
    Here, let $Y=1$ for all the ``7'' digits in the dataset, and use $Y=-1$ for ``2''.
    We will use regularized logistic regression. 
    Given a binary classification dataset $\{(x_i,y_i)\}_{i=1}^n$ for $x_i \in \R^d$ and $y_i \in \{-1,1\}$ we showed in class that the regularized negative log likelihood objective function can be written as
    \begin{align*}
    J(w,b) = \frac{1}{n} \sum_{i=1}^n \log( 1 + \exp(-y_i (b + x_i^T w))) + \lambda ||w||_2^2
    \end{align*} 
    Note that the offset term $b$ is not regularized. 
    For all experiments, use $\lambda = 10^{-1}$. 
    Let $\mu_i(w,b) = \frac{1}{1+ \exp(-y_i (b + x_i^T w))}$. 
    \begin{enumerate}
        \item \points{8} Derive the gradients $\nabla_w J(w,b)$, $\nabla_{b} J(w,b)$ and give your answers in terms of $\mu_i(w,b)$ (your answers should not contain exponentials).
        \item \points{8} Implement gradient descent with an initial iterate of all zeros. Try several values of step sizes to find one that appears to make convergence on the training set as fast as possible. Run until you feel you are near to convergence.
        \begin{enumerate}[(i)]
            \item For both the training set and the test, plot $J(w,b)$ as a function of the iteration number (and show both curves on the same plot).  
            \item For both the training set and the test, classify the points according to the rule $\text{sign}(b + x_i^T w)$ and plot the misclassification error as a function of the iteration number (and show both curves on the same plot). 
        \end{enumerate}
          
        Reminder: Make sure you are only using the test set for evaluation (not for training).
          
        \item \points{7} Repeat (b) using stochastic gradient descent with a batch size of 1. Note, the expected gradient with respect to the random selection should be equal to the gradient found in part (a). Show both plots described in (b) when using batch size 1. Take careful note of how to scale the regularizer.
        \item \points{7} Repeat (b) using stochastic gradient descent with batch size of 100. That is, instead of approximating the gradient with a single example, use 100. Note, the expected gradient with respect to the random selection should be equal to the gradient found in part (a).
    \end{enumerate}
    
    \subsection*{What to Submit}
    \begin{itemize}
        \item \textbf{Part a:} Proof
        \item \textbf{Part b:} Separate plots for b(i) and b(ii).
        \item \textbf{Part c:} Separate plots for c which reproduce those from b(i) and b(ii) for this case.
        \item \textbf{Part d:} Separate plots for c which reproduce those from b(i) and b(ii) for this case.
        \item \textbf{Code} on Gradescope through coding submission.
    \end{itemize}
\end{aprob}
\section*{Administrative}
\begin{aprob}
\begin{enumerate}
    \item \points{2} About how many hours did you spend on this homework? There is no right or wrong answer :)
\end{enumerate}

\end{aprob}

\end{document}
