---
title: "Homework 4: Ridge, Lasso, False-Positive Control"
date: Due at 6 pm on Thursday, 17 February 2022
author: 36-462/662, Spring 2022
output: pdf_document
header-includes:
  - \DeclareMathOperator*{\argmin}{argmin}
  - \DeclareMathOperator*{\argmax}{argmax}
  - \DeclareMathOperator{\sgn}{sgn}
---

\newcommand{\Prob}[1]{\mathbb{P}\left( #1 \right)}
\newcommand{\Expect}[1]{\mathbb{E}\left[ #1 \right]}
\newcommand{\Var}[1]{\mathrm{Var}\left[ #1 \right]}
\newcommand{\Cov}[1]{\mathrm{Cov}\left[ #1 \right]}
\newcommand{\Risk}{r}
\newcommand{\EmpRisk}{\hat{r}}
\newcommand{\Loss}{\ell}
\newcommand{\OptimalStrategy}{\sigma}
\newcommand{\ModelClass}{S}
\newcommand{\OptimalModel}{s^*}
\newcommand{\Indicator}[1]{\mathbb{1}\left\{ #1 \right\}}
\newcommand{\myexp}[1]{\exp{\left( #1 \right)}}
\newcommand{\eqdist}{\stackrel{d}{=}}
\newcommand{\OptDomain}{\Theta}
\newcommand{\OptDim}{p}
\newcommand{\optimand}{\theta}
\newcommand{\altoptimand}{\optimand^{\prime}}
\newcommand{\ObjFunc}{M}
\newcommand{\outputoptimand}{\optimand_{\mathrm{out}}}
\newcommand{\Hessian}{\mathbf{h}}
\newcommand{\Penalty}{\Omega}
\newcommand{\Lagrangian}{\mathcal{L}}



```{r, echo=FALSE, include=FALSE}
total.points <- 0
# Can't think of a good way to do this w/o a global variable assignment
this.prob <- function(x) { total.points <<- total.points+x; x }
silent <- TRUE
```

> **Agenda**: Practice with thinking through penalized and constrained model fitting, especially (but not just) regularizing linear regression.

If you view the PDF online, there are embedded links to parts of the lecture notes you may find helpful.


1. (`r this.prob(10)`) **Online reading questions** are on Canvas and are due on Monday at 6 pm.
2. **Ridge regression: penalty view** This question will guide us through finding an explicit solution to the problem of minimizing the mean squared error with a penalty on the squared length of the coefficient vector.  Specifically, we fix $\lambda > 0$, and ask for
\begin{equation}
\hat{\beta}_{\lambda} = \argmin_{b \in \mathbb{R}^p}{\frac{1}{n}\sum_{i=1}^{n}{(y_i - (x_i \cdot b))^2} + \lambda \|b\|^2}
\end{equation}
To simplify the book-keeping, we'll assume throughout that the variables $y$ and $x$ are both centered, so $n^{-1}\sum_{i}{y_i} = 0$, $n^{-1}\sum_{i}{x_i} = 0$.
    a. (`r this.prob(8)`) As a warm-up, assume that $p=1$, so $x$ is one dimensional (a scalar).  Write out the optimization problem, and show that its solution is
\begin{equation}
\hat{\beta}_{\lambda} = \frac{n^{-1}\sum_{i=1}^{n}{x_i y_i}}{\lambda + n^{-1}\sum_{i=1}^{n}{x_i^2}}
\end{equation}
How does this differ from what we'd get from ordinary least squares (OLS)?  Does it coincide with OLS in some limit for $\lambda$ and/or other variables?  _Hint_: As usual, take derivative and set equal to 0 (i.e., use the [first-order condition](https://www.stat.cmu.edu/~cshalizi/dm/22/lectures/05/lecture-05.html#(23))).
    b. (`r this.prob(8)`) The general, $p > 1$ version of the problem can be written in matrix form as
\begin{equation}
\hat{\beta}_{\lambda} = \argmin_{b \in \mathbb{R}^{p}}{\frac{1}{n}(\mathbf{y} - \mathbf{x}\mathbf{b})^T (\mathbf{y} - \mathbf{x}\mathbf{b}) + \lambda \mathbf{b}^T\mathbf{b}}
\end{equation}
What are the dimensions of $\mathbf{b}$ as a matrix?  Show that the solution is
\begin{equation}
\hat{\beta}_{\lambda} = (\mathbf{x}^T\mathbf{x} + n\lambda\mathbf{I})^{-1} \mathbf{x}^T \mathbf{y}
\end{equation}
    c. (`r this.prob(8)`) Does the formula in Q2b reduce to the formula in Q2a when $p=1$?  Should it?
3. **Ridge regression: constraint view**.  In class, we talked about how penalties and constraints are [equivalent to each other via Lagrange multipliers ("a fine is a price")](https://www.stat.cmu.edu/~cshalizi/dm/22/lectures/07/lecture-07.html#(28)).  We'll explore that in this problem, taking $p=1$ for simplicity.  Let's abbreviate the unconstrained OLS estimate as $\hat{\beta}_0$.  The constraint we'll impose is that $b^2 \leq c$.
    a. (`r this.prob(7)`) Explain why, if $\hat{\beta}_0^2 \leq c$, the constraint is not binding, and the Lagrange multiplier should be 0.  Does this mean the Lagrangian should be 0?
    b. (`r this.prob(7)`) Explain why the [Lagrangian](https://www.stat.cmu.edu/~cshalizi/dm/22/lectures/07/lecture-07.html#(25)) for the constrained problem is
\begin{equation}
\Lagrangian(b, \lambda) = \frac{1}{n}\sum_{i=1}^{n}{(y_i - x_i b)^2} + \lambda(b^2 -c)
\end{equation}
    c. (`r this.prob(7)`) Show that the two [first-order conditions](https://www.stat.cmu.edu/~cshalizi/dm/22/lectures/05/lecture-05.html#(23)) for minimizing the Lagrangian, assuming the constraint is binding, are
\begin{eqnarray}
(b^*)^2 & = & c\\
\frac{1}{n}\sum_{i=1}^{n}{(y_i - b^* x_i)x_i} & = & \lambda^* b^*
\end{eqnarray}
    d. (`r this.prob(6)`) Explain why, if the constraint is binding, $b^* = \sqrt{c} \sgn{\hat{\beta}_0}$, where $\sgn{u}$ is the "sign" function, $=1$ if $u > 0$, $=-1$ if $u<0$, and $=0$ if $u=0$.  _Hint_: why should the constrained $\hat{\beta}$ have the same sign as $\hat{\beta}_{0}$?
    e. (`r this.prob(5)`) Use the first-order conditions, and Q3c, to show that, when the constraint is binding,
\begin{equation}
\lambda^* = \frac{1}{\sqrt{c}\sgn{\hat{\beta}_0}}\frac{1}{n}\sum_{i=1}^{n}{x_i y_i} - \frac{1}{n}\sum_{i=1}^{n}{x_i^2}
\end{equation}
4. **Classifiers with false-positive control**.  Suppose we want to predict a binary variable $Y$ from a covariate $X$.  Any way of doing prediction like this is a classifier, and it's describable as a region $C$: if $x \in C$ then the classifier predicts $Y=1$, and if $x \not\in C$ then the classifier predicts $Y=0$.  (See HW2, Q6 and Q7.)  We can make two kinds of errors: false positives,
where $Y=0$ but we guess $Y=1$, and false negatives, where $Y=1$ but we guess $Y=0$.  The 0-1 loss doesn't distinguish between these errors.  Using different
losses (as in HW2 Q7) is one way to do so, but another approach is to constrain
the false positive rate to be $\leq \alpha$ for some acceptably small $\alpha$, and minimize the false negative rate.  (This can be especially useful when true positives are rare but important to find.)  Say that $p(x)$ is the PDF of $X$ conditional on $Y=1$ and $q(x)$ is the PDF of $X$ conditional on $Y=0$.
    a. (`r this.prob(6)`) Explain what the optimization problem
\begin{eqnarray}
C^* & = & \argmax_{C}{\int_{C}{p(x) dx}} \\
\nonumber & \text{subject to} & \\
\int_{C}{q(x) dx} & \leq & \alpha
\end{eqnarray}
has to do with finding classifiers with controlled false-positive rates.
    b. (`r this.prob(6)`) Explain what the optimization problem
\begin{equation}
\max_{C, \lambda}{\lambda \alpha + \int_{C}{(p(x) - \lambda q(x)) dx}}
\end{equation}
has to do with finding classifiers with controlled false-positive rates.
    c. (`r this.prob(6)`)  Explain why, if $p(x) > \lambda q(x)$, the point $x$ should be in $C^*$, but if $p(x) < \lambda q(x)$, $x$ should not be in $C^*$.  Also explain why we don't care whether $x$ is in $C^*$ when $p(x) = \lambda q(x)$.
    d. (`r this.prob(5)`) Explain why the optimal classifier $s^*(x)$ will always have the form
\begin{equation}
s^*(x) = \left\{ \begin{array}{cc} 1 & p(x)/q(x) \geq \lambda\\
                                   0 & p(x)/q(x) < \lambda
		         \end{array} \right.
\end{equation}
5. **Timing** (`r this.prob(1)`) How much time did you spend on this problem set?	
	

**Presentation rubric** (`r this.prob(10)`): The text is laid out cleanly, with
clear divisions between problems and sub-problems.  The writing itself is
well-organized, free of grammatical and other mechanical errors, and easy to
follow.  Plots are carefully labeled, with informative and legible titles, axis
labels, and (if called for) sub-titles and legends; they are placed near the
text of the corresponding problem.  All plots and tables are generated by code
included in the R Markdown file.  All quantitative and mathematical claims are
supported by appropriate derivations, included in the text, or calculations in
code.  Numerical results are reported to appropriate precision. All parts of
all problems are answered with actual coherent sentences, and raw computer code
or output are only shown when explicitly asked for.




```{r, echo=FALSE, include=TRUE}
if(!silent || (total.points != 100)) {   total.points }
```
	

