\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{STAT260 Problem Set 3}
\author{}
\date{Due October 24th 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}

\begin{document}

\maketitle

\noindent {\bf Regular problems:}

\begin{enumerate}

\item Prove the following invariance properties of Poincar\'e distributions:
      \begin{itemize}
      \item If $X \sim p$ is $\sigma$-Poincar\'e and $f : \bR^n \to \bR^m$ is $L$-Lipschitz, 
            then $f(X)$ is $(L\sigma)$-Poincar\'e.
      \item If $X \in \bR^n$, $Y \in \bR^m$ are independent and both $\sigma$-Poincar\'e, then the 
            ordered pair $(X, Y) \in \bR^{n + m}$ is $\sigma$-Poincar\'e.
      \end{itemize}
\item For a distribution $p$ on $\bR^d$, let $p_k(v) = \bE_{x \sim p}[\langle x, v \rangle^k]$ and observe 
      that $p_k$ is a polynomial in $v$. Give sum-of-squares proofs for the following facts:
      \begin{itemize}
      \item If $1 \leq a \leq b$ are both odd then $p_a(v)p_b(v) \psos p_{a-1}(v)p_{b+1}(v)$.
      \item If $2 \leq a \leq b$ are both even then $p_a(v)p_b(v) \psos p_{a-2}(v)p_{b+2}(v)$.
      \end{itemize}
      \emph{[Hint: Start by showing that for every even $r$, $x_r - x^{r-1}y - xy^{r-1} + y^r \sos 0$ (as a polynomial in $x$ and $y$), 
             and similarly $x^r - x^{r-2}y^2 - x^2y^{r-2} + y^r \sos 0$. This may require some clever factorization/algebra.]}

\item In class we defined sets $\Gdown$ and $\Gup$ for an arbitrary loss $L(p, \theta)$. Here we consider the following generalized 
      construction, that also incorporates a \emph{bridge function} $B(p, \theta)$:
      \begin{align}
      \Gdown(\rho_1, \epsilon) &\eqdef \{ p \mid B(r, \theta^*(p)) \leq \rho_1 \text{ whenever } r \leq \frac{p}{1-\epsilon}\}, \\
      \Gup(\rho_1, \rho_2, \epsilon) & \eqdef \{ p \mid L(p, \theta) \leq \rho_2 \text{ whenever } B(r, \theta) \leq \rho_1 \text{ for some } r \leq \frac{p}{1-\epsilon}, \theta\}.
      \end{align}
      Show that the modulus of continuity of $\Gdown(\rho_1, \epsilon) \cap \Gup(\rho_1, \rho_2, \epsilon)$ under $L$ is at most $\rho_2$.

\item Here we bound the modulus of continuity for linear classification. Given $(x, y) \sim p$ where $x \in \bR^d$ and $y \in \{\pm 1\}$, 
      Define $L(p, \theta) = \bP_{(x,y) \sim p}[y \neq \sign(\langle x, \theta)]$ and $B(p, \theta) = \bE_{(x,y) \sim p}[\max(0, 1 - y \langle x, \theta \rangle)]$, 
      and let $\theta^*(p)$ be the minimizer of $B(p, \theta)$.
      %
      Suppose that $p$ satisfies the following two properties:
      \begin{itemize}
      \item $\bE_{(x,y) \sim p}[\max(0, 1 - y \langle x, \theta^*(p) \rangle] \leq (1-\epsilon)\rho_1$
      \item Whenever $\bP_{(x,y) \sim p}[y \langle x, \theta \rangle \leq \frac{1}{2}] \leq \epsilon + 2(1-\epsilon)\rho_1$ for some $\theta$, 
            then $\bP_{(x,y) \sim p}[y \langle x, \theta \rangle \leq 0] \leq \rho_2$.
      \end{itemize}
      Show that $p \in \Gdown(\rho_1, \epsilon) \cap \Gup(\rho_2, \epsilon)$.

      \emph{[Remark: Note that the second condition is a type of tail bound, where in every direction where we are somewhat unlikely to be 
      close to the boundary, we are very unlikely to cross the boundary entirely.]}

\item Define the norm $\|x\|_{\sS_k} = \max_{\|v\|_2 \leq 1, \|v\|_0 \leq k} \langle x, v \rangle$. 
      \begin{enumerate}
      \item What is the dual norm to $\|\cdot\|_{\sS_k}$?
      \item Show that if $x$ and $y$ both have at most $k$ non-zero entries, then $\|x-y\|_{\sS_{2k}} = \|x-y\|_2$.
      \item Show that any distribution that is $(\rho, \epsilon)$-resilient in the $\ell_2$-norm is also 
            $(\rho, \epsilon)$-resilient in the $\sS_k$-norm.
      \end{enumerate}

\end{enumerate}


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

\begin{enumerate}

\item[6.] Construct a distribution that is $(\sqrt{\epsilon}, \epsilon)$-resilient in the $\sS_k$-norm 
          for all $\epsilon < 1/4$, but not $(\rho, 1/10)$-resilient in the $\ell_2$-norm for any $\rho < \Omega(k^{0.1})$.
          
          \emph{[The constants $1/4$, $1/10$, $0.1$ are all arbitrarily chosen, the point is to show a polynomial 
                 separation between $\sS_k$ and $\ell_2$ for some distribution. Note that your construction will likely 
                 need to have $d/k$ going to $\infty$ as $k \to \infty$.]}

\item[7.] Suppose that $X \sim p$ is $\sigma$-Poincar\'e and $f$ is $L$-Lipschitz. Show that $f(X)$ is sub-exponential 
          with parameter $\oo(\sigma L)$.

          \emph{[Hint: Define $u(\lambda) = \bE[e^{\lambda f(x)}]$ and compare to $\Var[e^{\lambda f(x)/2}]$.]}
\end{enumerate}
\end{document}
