\documentclass{article}
\usepackage[margin=1in]{geometry}

\usepackage{hyperref}       % hyperlinks
\usepackage{subcaption}
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{ifthen}
\usepackage{color}

\input{../notes/latex-defs.tex}
\usepackage{natbib}
\definecolor{mydarkblue}{rgb}{0,0.08,0.45}                                         
\hypersetup{
  colorlinks=true,
  linkcolor=mydarkblue,
  citecolor=mydarkblue,
  filecolor=mydarkblue,
  urlcolor=mydarkblue,
}
\setcitestyle{authoryear,round,citesep={;},aysep={,},yysep={;}}
\usepackage{tikz}
\usetikzlibrary{patterns,positioning,fit,calc,arrows,matrix}
\usepackage{paralist}
\usepackage{enumitem}
\usepackage{mathtools}
\usepackage{algorithm,algorithmicx,algcompatible,algpseudocode}
\usepackage{bbm}

\makeatletter
\renewcommand{\paragraph}{%
  \@startsection{paragraph}{4}%
  {\z@}{3.25ex \@plus 1ex \@minus .2ex}{-1em}%
  {\normalfont\normalsize\bfseries}%
}
\makeatother

\title{STAT240 Problem Set 5}
\author{}
\date{Due April 29th in class}

\newcommand{\psos}{\preceq_{\mathrm{sos}}}
\newcommand{\sos}{\succeq_{\mathrm{sos}}}
\newcommand{\Gup}{\mathcal{G}^{\uparrow}}
\newcommand{\Gdown}{\mathcal{G}^{\downarrow}}
\DeclareMathOperator{\sign}{sign}

\newcommand\independent{\protect\mathpalette{\protect\independenT}{\perp}}
\def\independenT#1#2{\mathrel{\rlap{$#1#2$}\mkern2mu{#1#2}}}

\begin{document}

\maketitle

\noindent {\bf Regular problems:}

\begin{enumerate}


\item Suppose that for a ridge regression problem, instead of the eigenvalues of $S$ decaying as a power law $\mu_j^* = j^{-\alpha}$, 
      they decay exponentially: $\mu_j^* = \exp(-\beta j)$. In the setting where $Y_i = \langle \beta^*, X_i \rangle + Z_i$, 
      where $\beta^*$ is drawn from a Gaussian prior with scale parameter $\rho$ and $Z_i \sim \sN(0, \sigma^2)$, compute 
      the bias and variance up to constant factors, as a function of $\sigma$, $\rho$, and $\lambda$. For the optimal regularization 
      $\lambda_n^* = \frac{\sigma^2}{\rho^2 n}$, what is the expected squared error of the ridge regression estimator?

\item Suppose we observe data $(x_1, t_1, y_1), \ldots, (x_n, t_n, y_n)$ drawn i.i.d.~from $p$ and satisfying 
      the unconfoundedness assumption, with known true propensity scores 
      $\pi_i = \pi(x_i)$ (i.e.~it is known that $p(T=1 \mid x_i) = \pi_i$). Consider the clipped inverse-propensity 
      weighted estimator for the average treatment effect:
      \begin{equation}
      \frac{1}{n} \sum_{i=1}^n \Big(\frac{\bI[t_i=1]}{\max(\pi_i, 1/M)} - \frac{\bI[t_i=0]}{\max(1-\pi_i, 1/M)}\Big)y_i,
      \end{equation}
      where the clipping parameter $M$ ensures that the clipped inverse propensity weights are all at most $M$.
      Assuming that $y \in [-1,1]$ almost surely, show that the bias of the estimator is at most
      \begin{equation}
      \bE_{x \sim p}[\max(1-\pi(x)M, 0) + \max(1 - (1-\pi(x))M, 0)],
      \end{equation}
      while the variance is at most $M^2/n$.

\item Recall that for a regression problem, the (non-robust) standard error is given by $\frac{\sigma^2}{n} S^{-1}$, while the robust standard error is given by $\frac{1}{n}S^{-1}\Omega S^{-1}$, where
\begin{align}
S &= \frac{1}{n} \sum_{i=1}^n x_ix_i^{\top}, \\
\sigma^2 &= \frac{1}{n} \sum_{i=1}^n (y_i - \langle \hat{w}, x_i \rangle)^2, \\
\Omega &= \frac{1}{n} \sum_{i=1}^n x_i (y_i - \langle \hat{w}, x_i \rangle)^2 x_i^{\top},
\end{align}
and $\hat{w}$ is the ordinary least squares estimate from $(x_1,y_1), \ldots, (x_n,y_n)$.

Show that the robust standard error can be arbitrarily larger than the standard error. In other words, show that for any 
real number $t$ there is a collection of points $(x_i, y_i)$ such that $\frac{1}{n}S^{-1}\Omega S^{-1} \succeq t \cdot \frac{\sigma^2}{n}S^{-1}$.

\item Show that the following quantity also yields a doubly robust estimate, in the sense that it is correct if either $q = p$ or $\bar{Y} = \bE[Y \mid X]$:

\begin{align}
\mu_t &= \frac{\bE_{X, T, Y \sim p}\Big[\bI[T=t] (Y(T) - \bar{Y}_T(X)) / q(t \mid X)\Big]}{\bE_{X, T, Y \sim p}[\frac{\bI[T=t]}{q(t \mid X)}]} + \bE_{X \sim p}[\bar{Y}_t(X)], \text{ for } t = 0, 1, \\
DRE' &= \mu_1 - \mu_0.
\end{align}
    Qualitatively, how does this estimate compare to the doubly robust estimator from lecture?

\end{enumerate}

\noindent {\bf Challenge problems (turn in as a separate document typset in LaTeX):}

\begin{enumerate}

\item[5.] Call a set of points $S = \{x_1, \ldots, x_s\}$ $(\epsilon, \kappa)$-\emph{dimension-preserving} if $\frac{1}{|T|} \sum_{i \in T} x_ix_i^{\top} \succeq \kappa^{-1} \frac{1}{|S|} \sum_{i \in S} x_ix_i^{\top}$ for all $T \subseteq S$ with $|T| \geq \epsilon |S|$.

Consider a linear-regression setting where we observe $(x_1, y_1), \ldots, (x_n,y_n)$. Suppose that there is a set $S^*$ of 
$\alpha n$ of the $x_i$ that are $(\alpha/4, \kappa)$-dimension-preserving, and that for these points we have 
$y_i = \langle w^*, x_i \rangle + z_i$, where $z_i \sim \sN(0, \sigma^2 I)$. Show that with high probability it is possible to output 
a set of $m = \oo(1/\alpha)$ candidates $\hat{w}_1, \ldots, \hat{w}_m$ such that, for at least one of the elements $\hat{w}_l$, 
the excess prediction loss on $S^*$ satisfies
\begin{equation}
\frac{1}{|S^*|} \sum_{i \in S^*} (\langle \hat{w}_l, x_i \rangle - y_i)^2 - (\langle w^*, x_i \rangle - y_i)^2 = \oo\Big(\kappa \sigma^2\frac{\log(1/\alpha)}{\alpha}\Big).
\end{equation}
\emph{[Note: This should be true as stated, but you will get full points for any bound that is polynomial in $\kappa$, $\sigma$, and $\alpha$, as long as it is independent of the dimension $d$ for $n$ sufficiently large.]}

\item[6.] Consider a causal inference setting where instead of two treatment conditions $T = 0, 1$, the treatment is represented by a non-negative real number $T \in \bR_{\geq 0}$ (this might be the case for instance if we 
      are estimating the effect of vitamin D consumption on catching the flu, and for each patient we observe their daily vitamin D consumption in milligrams).

      We will still define $Y(t)$ to be the outcome that ``would have'' occurred if the treatment were $T = t$, and unconfoundedness means that $(Y(t))_{t \geq 0} \independent T \mid X$.

      We will define the marginal average treatment effect to be
      \begin{equation}
      MATE = \bE_{X, T \sim p}\left[\left. \frac{d}{dt} \bE[Y(t) \mid X] \right|_{t = T}\right].
      \end{equation}
      In other words, this is the infinitesimal amount by which $Y$ would increase on average, if we increased everyone's treatment 
      level by a small amount.

      (i) Show that under unconfoundedness, and assuming the propensity to treat $p(t \mid X)$ is differentiable in $t$,
          the MATE is equal to
      \begin{equation}
      MATE = -\bE_{p}\Big[\big(\left. \frac{d}{dt} \log p(t \mid X)\right|_{t = T}\big) \cdot Y \Big]
      \end{equation}

      (ii) Assuming we have an estimate $q$ for $p$ and an estimate $\bar{Y}(t, x)$ for $Y$, design a doubly robust 
           estimator based on the above equation. Show that it yields the correct answer as long as either $q(t \mid x) = p(t \mid x)$, 
           or $\bar{Y}(t, x) = \bE[Y(t) \mid X=x]$.
\end{enumerate}
\end{document}
