\documentclass{article}

\usepackage{amsfonts,amsmath,amsthm,amssymb,stmaryrd}

\usepackage{xurl}
\usepackage[colorlinks]{hyperref}
% \usepackage{savetrees}
\usepackage{enumitem}

\DeclareMathOperator*{\argmax}{argmax}
\newcommand{\rrr}{\mathbb{R}}
\newcommand{\comment}[1]{}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqa}{\begin{eqnarray}}
\newcommand{\eeqa}{\end{eqnarray}}
\newcommand{\bit}{\begin{itemize}\setlength{\itemsep}{0cm}\setlength{\topsep}{0cm}}
\newcommand{\eit}{\end{itemize}}
\newcommand{\benum}{\begin{enumerate}\setlength{\itemsep}{0cm}\setlength{\parsep
}{0cm}}
\newcommand{\eenum}{\end{enumerate}}
\newcommand{\mmp}[1]{\textcolor{blue}{MMP: #1}}

\begin{document}
\setlength{\parindent}{0em}
\setlength{\parskip}{1.3em}

\begin{large}
\centerline{CS 480/680 Homework 3}  % assignment number here

\centerline{Released Jan 28, 2026}       % out date here
\centerline{Due Feb 4, 2026 - Before 11:59PM EST}       % due date here
\end{large}

\centerline{\large \copyright Marina Meil\u{a}}
\centerline{\large mmp@stat.washington.edu}

\vspace{2em}

{\bf Problem 1 -- Bias and Variance Again}

The questions in this problem refer to \textbf{Problem 2 from Homework 1}.

\begin{enumerate}[label=\textbf{\alph*.}]
    \item Consider all the quantities you are asked to calculate or plot in Homework 1, Problem 2 (e.g., $\hat{l}_b, L_b, \hat{l}, V, \ldots$). List 2 of these which are \textit{statistical approximations}. 
    
    \textit{Note:} For example, computing a mean from samples is a \textit{statistical approximation}, whereas computing an integral by discretization is a \textit{numerical approximation}. We assume that all floating point computations and function calls are exact.
    
    Explain (1 line or less) in each case what is (are) the approximation(s) made.

    \item For one of your answers above, explain how you could increase the approximation accuracy.

    \item {\bf [680 only]}Assume that in Homework 1, Problem 2, $\tilde{n}\rightarrow\infty$. Will the error bars on $L\rightarrow 0$? Explain (1 line).

    \item Assume that in Homework 1, Problem 2, $n\rightarrow\infty$. Will the error bars on $\hat{l}\rightarrow 0$? Explain (1 line).
\end{enumerate}

\vspace{0.5cm}

{\bf [Problem 2 -- Logistic Regression Basic Properties -- NOT GRADED]}

\textit{Notations follow the \texttt{lgood2-linear.pdf} course notes.}

We consider the following definitions for the Sigmoid function $\sigma(u)$, the Logit function $\psi(\theta)$, and the Logistic Regression model:

\begin{align*}
    \text{Sigmoid: } & \quad \sigma(u)=\frac{1}{1+e^{-u}} \\
    \text{Logit: } & \quad \psi(\theta)=\ln( 1+e^\theta) \\
    \text{Model: } & \quad \ln \frac{P[Y=1|X=x]}{P[Y=0|X=x]}=f(x)\equiv \beta^T \mathbf{x}
\end{align*}
Here $Y\in\{0,1\}$.

\begin{enumerate}[label=\textbf{\alph*.}]
    \item \textbf{Symmetry:} Prove that $\sigma(-u)=1-\sigma(u)$. Using this, show that $\sigma'(-u)=\sigma'(u)$. 
    
    \item \textbf{Calculus Properties:}
    \begin{enumerate}[label=\textbf{(\roman*)}]
        \item Show that $\argmax_{u \in \rrr} \sigma'(u) = 0$.
        \item Show that $\max_u \sigma'(u) = 1/4$.
        \item Prove that if $u \rightarrow \pm\infty$, the derivative $\sigma'(u) \rightarrow 0$.
    \end{enumerate}
    \textit{Interpretation:} Based on result (iii), explain why correctly classified data points away from the boundary have little influence on the log-likelihood. (i.e., Why do the parameters $\beta$ change little when points far away from the decision boundary move?)

    \item \textbf{Alternative Form:} Verify that $\sigma(u) = \frac{e^{u/2}}{e^{u/2}+e^{-u/2}} = \frac{e^{u}}{1+e^u}$.

    \item \textbf{Normalization:} Let the probability mass function be $P_\theta(y)=e^{\theta y-\psi_0(\theta)}$, where $\psi_0(\theta)=\ln Z(\theta)$ and $Z(\theta)$ is the normalization constant. Show that $\psi_0 = \psi$ (the logit function defined above).

    \item {\bf [680 only]} \textbf{Expectation:} Calculate $\mathbb{E}_\beta[Y]$ and identify it with one of the three functions defined at the start of the problem. $\mathbb{E}_\beta[Y]$ is the expectation of $Y$ under the model $P[Y|X=x]$ defined by the logistic regression. Note that when $Y\in\{0,1\}$, the expectation is equal to the probability that $Y=1$. 
\end{enumerate}

{\bf Problem 3 -- Implementing Logistic Regression}

In this question, you will implement logistic regression from scratch. Download the following files into your working directory. Note that these files should in the same directory.

\begin{itemize}[leftmargin=*]
    \item \texttt{hw3q3.py}: The script where you will implement the main optimization algorithm.
    \item \texttt{hw3q3vis.py}: The script where you will implement the visualization functions.
    \item \texttt{hw3\_X\_logistic.dat}: Data matrix $X \in \mathbb{R}^{n\times 2}$, where $n$ is the number of samples.
    \item \texttt{hw3\_y\_logistic.dat}: Label vector $\mathbf{y} \in \{-1, 1\}^{n}$.
    \item \texttt{hw3q3.sh}: A shell script to automate the execution. You should be able to execute this script with no errors after finishing the problem. \textbf{Do not modify this file.}
\end{itemize}

\begin{enumerate}[label=\textbf{\alph*.}, leftmargin=*]
    \item The logistic regression model you will train is
    \beq
    f(x_1,x_2) \;=\; \begin{bmatrix} \beta_1 & \beta_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + \beta_0
    \eeq
    You will fit a parameter vector $\boldsymbol{\beta} = \begin{bmatrix} \beta_0 \\ \beta_1 \\ \beta_2 \end{bmatrix} \in \mathbb{R}^3$. What is the vector $\mathbf{x} \in \mathbb{R}^3$ so that $f(x_1,x_2)=\boldsymbol{\beta}^T\mathbf{x}$?

    \item Write down the mathematical expression for the Log-likelihood $\ell(\boldsymbol{\beta})$ and its gradient $\nabla_{\boldsymbol{\beta}} \ell$.

    \item Implement and run the logistic regression model on the dataset given in files \texttt{hw3q3.py}.    
    Use \textbf{Gradient Ascent} for optimization. Terminate the training when the relative change in the log-likelihood is less than $10^{-3}$, i.e., 
    $$ \frac{|\ell_{\text{new}} - \ell_{\text{old}}|}{|\ell_{\text{old}}|} \leq 10^{-3} $$
    Report the learning rate $\eta$ you selected. In how many iterations did the training terminate?

    \item Report the final fitted values of $\boldsymbol{\beta}$.
\end{enumerate}

Create a visualization of the training process in \texttt{hw3q3vis.py} by implementing the functions listed below. \textbf{Note:} Ensure your previous script is named exactly \texttt{hw3q3.py} so it can be imported correctly.

\begin{enumerate}[label=\textbf{\alph*.}, leftmargin=*]
    \setcounter{enumi}{4}

    \item Complete the function \texttt{plot\_ll}, and use it to create a plot of the log-likelihood $\ell$ and one of the magnitude of the change in log-likelihood $|\Delta \ell|$ with respect to the number of iterations. Include these plots here.

    \item Complete the function \texttt{plot\_betas}, and use it to create a plot of the parameter values $\beta_0, \beta_1, \beta_2$ with respect to the number of iterations (on the same graph). Include this plot here.

    \item Complete the function \texttt{plot\_gradients}, and use it to create a plot of the gradient components $\frac{\partial \ell}{\partial \beta_0}, \frac{\partial \ell}{\partial \beta_1}, \frac{\partial \ell}{\partial \beta_2}$ with respect to the number of iterations. Include this plot here.

    \item Complete the function \texttt{plot\_decision\_boundary}, and use it to create a scatter plot of the data samples (color-coded by class $-1$ and $1$) and overlay the final linear decision boundary. Include this plot here.
\end{enumerate}

\vspace{0.5cm}

\textbf{Instructions for Code Submission:} \\
Ensure you can run \texttt{./hw3q3.sh} without errors. This script should be able to create a zip file named \texttt{hw3q3-submission.zip} containing only \texttt{hw3q3.py} and \texttt{hw3q3vis.py}. \textbf{Submit \texttt{hw3q3-submission.zip} to LEARN.}
\end{document}
