
\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\newcommand{\D}{\mathbf{D}}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}
\usepackage{amsmath}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{automata,positioning}
\usetikzlibrary{decorations.pathmorphing,shapes}
\usepackage{amssymb}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{hyperref}

\newenvironment{oneshot}[1]{\@begintheorem{#1}{\unskip}}{\@endtheorem}
\newtheorem{example}{Example}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}
\lecture{16}{April 8, 2019}{Ronitt Rubinfeld}{Thuy-Duong Vuong}



\section{Outline}
The following topics were covered in class:
\begin{itemize}
    \item Hypothesis testing
    \item Cover Method
\end{itemize}
\section{Hypothesis testing}
We say a distribution $p$ is \textbf{known} to algorithm $\mathcal{A}$ if $\mathcal{A}$ has access to $p$'s probability density function (pdf). We say $p$ is \textbf{unknown} to algorithm $\mathcal{A}$ if $\mathcal{A}$ doesn't have access to $p$'s pdf. Unless otherwise stated, $\mathcal{A}$ can take samples from distribution $p$ (in order to "learn" $p$). 

For distributions $p,q$ and parameter $\epsilon,$ we say $p$ is $\epsilon$-close to $q$ iff $ \abs{p-q}_1 \leq \epsilon$
Input: 
\begin{itemize}
    
    \item Unknown distribution $p.$ %We can take samples from $p,$ but we are not given $p$'s description.
    \item Collection $\mathcal{H}$ of known distributions. $\mathcal{H}$ is guaranteed to contain a distribution that is $\epsilon$-close to $p$. %, where each distribution in $\mathcal{H}$ is described completely (via, say, its density function).
\end{itemize} 
Output: a distribution $q \in \mathcal{H}$ that is $\epsilon$-close to $p$ %s.t. to $\abs{p-q}_1 \leq \epsilon.$

\begin{example} \label{ex:coin}
$\mathcal{H} $ is the set of biased coins i.e. $\mathcal{H} = \{Ber(q) | q \in [0,1]\}$\footnote{see \url{https://en.wikipedia.org/wiki/Bernoulli_distribution}} and $p = Ber(x).$
\end{example}
%where for $Pr_{X \sim Ber(p)} [X=1] = p$

\section{Subtool: Comparing two hypothesis} \label{sec:2hypo}
We break the problem down into smaller pieces. First, let us consider an "easy" case of the problem: when $\abs{\mathcal{H}} = 2.$ We can build a solution for the general case from there. %Ideally, we want a tool that
\begin{theorem}
There exists algorithm $\mathcal{A}$ that when given input: 
\begin{itemize}
    \item Known distributions $h_1, h_2.$%, where each distribution in $\mathcal{H}$ is described completely (via, say, its density function).
    \item Unknown distribution $p.$ %We can take samples from $p,$ but we are not given $p$'s description.
    \item parameter $\epsilon' > 0,$ confidence level $\delta' \in (0,1).$
\end{itemize}
takes $O(\log(1/\epsilon')/{\epsilon'}^2)$ samples from $p,$ and output $h \in \{h_1, h_2\}$ such that: if one of $h_1, h_2$ are $\epsilon'$-close to $p,$ then with probability $\geq 1-\delta'$ output $h$ is $11 \epsilon'$-close to $p.$ Note that, we do not hold any assumption on the output when neither $h_1, h_2$ are $\epsilon$-close to $p.$  
\end{theorem}
Actually, we will prove something stronger:
\begin{theorem}
There exists algorithm "Choose" when given input: 
\begin{itemize}
 \item Unknown distribution $p.$
    \item Known distributions $h_1, h_2,$ assuming that at least one of them are $\epsilon$-close to $p$%, where each distribution in $\mathcal{H}$ is described completely (via, say, its density function).
    %We can take samples from $p,$ but we are not given $p$'s description.
    \item parameter $\epsilon' > 0,$ confidence level $\delta' \in (0,1).$
\end{itemize}
takes $O(\log(1/\delta')/{\epsilon'}^2)$ samples from $p,$ 

and outputs tuple out=(outcome, $h$) where outcome $\in \{ \text{win}, \text{tie}\}$ and  $h \in \{h_1, h_2\}$ that with probability $\geq 1-\delta'$ satisfies:
\begin{enumerate}[label = (\arabic*)]
    \item If $h_i$ is more than $12\epsilon'$-far from $p,$ then $\text{out}\neq(\text{outcome}, h_i)$
    \item If $h_i$ is more than $10\epsilon'$-far from $p,$ then $\text{out}\neq(\text{win}, h_i)$ (but it is probable that $\text{out} = (\text{tie}, h_i)$).
   % \item $h_i$ is $11\epsilon'$-close to $p.$
\end{enumerate}
\end{theorem}

\begin{proof}
Let $A = \{x | h_1(x) > h_2(x)\}.$ Let $a_i = h_i(A)= \sum_{x \in A} h_i(a)$ for $i \in \{1,2\}.$

Claim (1): $\abs{h_1-h_2}_1 =2 (a_1 -a_2).$ 

For a proof by picture, see \url{https://people.csail.mit.edu/ronitt/COURSE/S19/Handouts/lec16b.pdf}. Here, we formalize the proof in words. for $x \in A$, $\abs{h_1(x) - h_2(x)} = h_1(x) - h_2(x)$ so $$\sum_{x \in A} \abs{h_1(x) - h_2(x)} = \sum_{x\in A} (h_1(x) -h_2(x)) = h_1(A) - h_2(A) = a_1 - a_2.$$ Similarly, $\sum_{x \not\in A} \abs{h_1(x) - h_2(x)} = \sum_{x\in A} (h_2(x) -h_1(x)) = h_2(A^c) - h_1(A^c) = (1-h_2(A)) - (1-h_1(A)) = h_1(A) - h_2(A),$ where $A^c$ is the complement of $A$ in the union of the domains of $h_1$ and $h_2.$ 

Thus $$\abs{h_1-h_2}_1 = \sum_{x \in A} \abs{h_1(x) - h_2(x)}+ \sum_{x \not\in A} \abs{h_1(x) - h_2(x)} = 2 (a_1 -a_2)$$

Algorithm "Choose":

\begin{enumerate}
    \item \label{step:1} If $a_1 -a_2 \leq 5 \epsilon',$ return $(\text{tie}, h)$
    \item \label{step:2} Draw $m = \log(1/\delta')/{\epsilon'}^2$ samples $s_1, \cdots, s_m$ from $p$
    \item Let $\alpha \leftarrow \frac{1}{m} \abs{\{i | s_i \in A \} }.$
    \item If $\alpha > a_1 - \frac{3}{2} \epsilon'$ returns $(\text{win}, h_1)$
    
    else if $\alpha < a_2 + \frac{3}{2} \epsilon'$ returns $(\text{win}, h_2)$
    
    else return $(\text{tie}, h_1)$
\end{enumerate}
%WLOG, assume $h_1$ is $\epsilon'$-close to $p.$
There exists $h^* \in \{h_1, h_2\}$ that is  $\epsilon'$-far from $p.$
If algorithm ends at Step \ref{step:1}, then $h_2, h_1$ are $10\epsilon'$-close to one another thus also $10\epsilon'$-close to $h^*;$ hence, they are $11\epsilon'$-close to $p.$ So algorithm can output "tie" along with either $h_1$ or $h_2.$ On the other hand, if either $h_1$ or $h_2$ is $> 12 \epsilon'$-far from $p.$ WLOG, may assume $h^* = h_1$ and $h_2$ is $12\epsilon'$-far from $p,$ then by triangle inequality, $h_2$ is  $11\epsilon'$-far from $h_1,$ so $a_1 -a_2 =\abs{h_1-h_2}_1/2 > 5 \epsilon',$ and algorithm will reach Step \ref{step:2}.

Assume algorithm reaches Step \ref{step:2}. Note that $E(\alpha) = p(A),$ and by Chernoff's bound, with probability $\geq 1-\delta,$ $\abs{\alpha - E(\alpha)} <\epsilon'/2.$ Assume this inequality holds. If $h_1$ is $\epsilon'$-close to $p$ then by triangle inequality, $\abs{p(A) - h_1 (A)} \leq \sum_{x \in A} \abs{ p(x) - h_1(x)} \leq \abs{p-h_1}_1 \leq \epsilon';$ thus, $$\alpha > E (\alpha ) - \epsilon'/2 = p(A) - \epsilon'/2 \geq (a_1-\epsilon') -\epsilon'/2 = a_1 - \frac{3}{2}\epsilon'  .$$ Similarly, if $h_2$ is $\epsilon'$-close to $p$ then $\abs{p(A) - a_2} \leq \epsilon'$ so $\alpha < a_2 + \frac{3}{2}\epsilon'.$ Note that since we reach step \ref{step:2}, $a_1 - a_2> 5 \epsilon'$ so $a_1 - \frac{3}{2}\epsilon' > a_2 + \frac{3}{2}\epsilon',$ thus the algorithm wouldn't output "tie" (assuming the inequality $\abs{\alpha - E(\alpha)} <\epsilon'/2$ holds!)

%Note that if algorithm stops at step $1,$ then both $h_1,h_2$ are $11\epsilon'$-close to $p.$ If algorithms stops after step $2,$ then the outputted $h_i$ is $\epsilon'$-close (thus obviously $11\epsilon'$-close) to $p.$  
\end{proof}

\section{Cover method}
Using the subtool in Section \ref{sec:2hypo}, we can get an algorithm for the case when $\mathcal{H}$ is finite. But as we see in Example \ref{ex:coin}, $\mathcal{H}$ might be infinite. How do we deal with that? We revisit the idea of $\epsilon$-net discussed in previous lectures. More concretely, given a set of distributions $\mathcal{D},$ we want to take a smaller set of distributions $\mathcal{C}$ that approximate $\mathcal{D}$ within some $\epsilon$ distance. Formally,
\begin{definition}
Let $\mathcal{D}$ be a set of distributions. Set of distributions $\mathcal{C}$ is a $\epsilon$-cover of $\mathcal{D}$ if $\forall q \in \mathcal{D},$ there exists $p \in \mathcal{C}$ such that $\abs{p-q}_1 \leq \epsilon.$
\end{definition}
This way, we can save time by running algorithms on $\mathcal{C}$ instead of $\mathcal{D}.$ 
\begin{theorem}
There exists an algorithm, that given $p \in \mathcal{D},$ takes $O(\frac{1}{\epsilon^2} \log\abs{\mathcal{C}})$ samples of $p$ and output $h \in \mathcal{C}^{\mathcal{D}}$ such that $\abs{ h - p} \leq 11 \epsilon.$

\end{theorem}
\begin{proof}
Since $p \in \mathcal{D},$ there exists $q \in \mathcal{C}$ such that $\abs{p-q}_1 \leq \epsilon.$ We run Choose on every pair $q_1, q_2 $ in $\mathcal{C}$ with parameter $\epsilon' = \epsilon$ and $\delta' = \frac{1}{10\binom{\abs{\mathcal{C} }}{2}}.$ Then by union bound, with probability $\geq 1 -\binom{\abs{\mathcal{C} }}{2} \delta' =9/10, $ all output of calls to Choose satisfy their guarantee. Assuming this happens. We can show that there is a $q '$ that wins or ties all matches $(q', q_2)$ where $q_2 \in \mathcal{C} \setminus \{q'\}.$ For example, let $q'=q$ then by Definition of Algorithm Choose, any match $(q,q_2)$ either ends in a "tie" at Step \ref{step:1}, or reaches Step \ref{step:2} and ends in a "win" for $q.$ 

But what if there is multiple $q'$ that wins or ties all matches? We can just pick an arbitrary such $q'$ and output it, since any such $q'$ satisfies $\abs{q'-p}_1 \leq 11 \epsilon.$ Indeed, if $q'=q$ then we are done, as $q$ is $\epsilon$-close to $p.$ Assume $q'\neq q,$ and consider the match between $q'$ and $q$: if $q'$ wins, then $q'$ is $\leq 10\epsilon'$-close to $p,$ else if $q'$ tie, then $q'$ is $10\epsilon$-close to $q,$ thus $11\epsilon$-close to $p.$ 
\end{proof}

%\begin{oneshot}{Example \ref{ex:coin}}
\textbf{Example \ref{ex:coin}} revisited.
We abuse notation and write $q$ in place of $Ber(q)$ for brevity's sake. We write $\mathcal{H} = \{ q | q \in [0,1]\}.$ Then $\mathcal{C} = \{0, \frac{1}{k}, \frac{2}{k}, \cdots, \frac{k-1}{k}, 1\}$ where $k = 2/\epsilon$ is a $\epsilon$-cover of $\mathcal{H}.$ Indeed, let $r \in \{0, \cdots, k\}$ be such that $ \frac{r}{k} \leq x < \frac{r+1}{k}$ then $\abs{Ber(x) - Ber(\frac{r}{k})}_1 = 2 \abs{\frac{r}{k} -x} \leq 2/k = \epsilon.$ Note that $\abs{\mathcal{C}} = \theta(1/\epsilon).$ So by Theorem 3, setting $\epsilon' = \epsilon/11,$ can learn $Ber(q)$ $\epsilon$-close to $p=Ber(x)$ by taking $O(\frac{1}{\epsilon^2}\log (\frac{1}{\epsilon}))$ samples from $p.$

\begin{example}[2-Bucket distributions]
A 2-bucket distribution $B_{\alpha, \beta}$ is defined by $$Pr_{X \sim B_{\alpha, \beta}} [X= i] = \begin{cases}\frac{\alpha}{n/2} \text{ if $i\in [n/2]$ }\\\frac{\beta}{n/2} \text{ if $i\in [n] \setminus [n/2]$ } \\ 0 \text{ else}  \end{cases}$$

Let $\mathcal{D}$ be the set of all 2-bucket distributions $B_{\alpha, \beta}$ where $\alpha, \beta \in [0,1]$.
Similar to in Example \ref{ex:coin}, we can create an $\epsilon$-cover using $\epsilon$-net for each of $\alpha,\beta$ i.e. $\mathcal{C} = \{ B_{i/k, j/k}  | i, j \in \{0, \cdots, k\}\}$ where $k = 1/\epsilon.$ The size of this cover is $\theta(\frac{1}{\epsilon^2})$ thus can learn unknown $B_{\alpha, \beta}$ in $O(\frac{1}{\epsilon^2} \log (\frac{1}{\epsilon})).$
%is a distribution over $[n]$ and satisfy $B_{\alpha, \beta}$ 
\end{example}
\begin{example}[Monotone distributions]
Let $\mathcal{D}$ be the set of monotone (decreasing) distributions over $[n] = \{1,2,\cdots, n\}.$ By lecture 15, the set of Birge distributions\footnote{see Lecture 15} 
$ \mathcal{C} = \{ (w_1, \cdots, w_{\theta(\frac{\log n}{\epsilon})} ) | w_i = \frac{j_i}{k}, j_i \in \{0,\cdots, k\}\}$ where $k = 1/\epsilon$ forms an $\epsilon$-cover. The size of this cover is $\abs{\mathcal{C}} = \theta(\frac{1}{\epsilon^{\log n/ \epsilon} }),$ so we can learn $p \in \mathcal{D}$ in $O(\frac{\log n}{\epsilon^3} \log(\frac{1}{\epsilon})).$
\end{example}
%\end{oneshot}

\end{document}
