\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{11}{June 3, 2009}{Ronitt Rubinfeld}{Anat Ganor, Roy Kasher, O. Paneth}

%%%% body goes in here %%%%

\section{Introduction}
In this lecture we show an algorithm for learning Parity with noise. If $f$ is linear we can find it easily by solving a linear system of equations. For an arbitrary $f$, our goal is to find all linear functions that are close to $f$.

Under the general PAC model this problem is conjectured to be hard, refered to as \emph{hardness of parity with noise}, \emph{hardness of decoding linear codes}, \emph{maximum likelihood decoding of linear codes} or \emph{finding largest fourier coefficient}. For certain relaxtions of the problem we know subexponential algorithms exist, however, the general case is believed to be NP-hard.

We can consider two noise models: Adverserial, where a linear function is changed adverserially in up to $\frac{1}{2}-\epsilon$ fraction of its inputs, or noisy, where the corruption occurs randomly.

Since the problem is infeasible in the PAC model, we will allow queries to $f$ instead of random sampling. This makes it feasible even with adverserial noise. This problem was first studied by Goldreich and Levin in the context of cryptographic pseudorandom generators, and has found applications in error correcting coes (list decoding of Hadamard codes) and learning theory (by Kushilevitz and Mansour).

\paragraph*{The goal}
We want to output all $S\subseteq[n]$ s.t. $\hat{f}(S)\geq\theta$ (i.e. $\Pr_{x}\left[\chi_{S}(x)=f(x)\right]\geq\frac{1+\theta}{2}$) and not output any $S$ for which $\hat{f(S)}\leq\frac{\theta}{2}$, in runtime $\poly(n,\frac{1}{\theta})$
\paragraph*{Notation}
\begin{itemize}
    \item $e_{i}=(1,...,1,-1,1,...,1)$ where $-1$ is in the $i^{th}$ location.
    \item Bitwise product: $xy=(x_{1}y_{1},x_{2}y_{2},...,x_{n}y_{n})$
\end{itemize}


%\begin{enumerate}

\section{Learning Parity with Noise}

\subsection{Warmup 1}
$f$ is linear, i.e. $\exists S$ s.t. $f(x)=\chi_{S}(x)$
\paragraph*{The algorithm \\} 
$\forall i\in[n]$ put $i$ in $S$ if $1=f(\overrightarrow{1})\neq f(e_{i})$

\subsection{Warmup 2}
Arbitrary $f$, using poly queries and unbounded time
\paragraph*{The algorithm\\} 
Iterate all $S$ and test if $f$ and $\chi_{S}$ agree "enough" (by sampling)
\\
\\Note the samples must be "recycled" for all $S$'s. The analysis is simple using the Chernoff and union bounds as we've seen in the last lecture.

\subsection{Warmup 3}
Exists $S$ s.t. $f$ agrees with $\chi_{S}$ "almost everywhere", on $\geq1-\frac{1}{4n}$ fraction of inputs (Note every two linear functions disagree on half of the inputs, so $f$ is determined uniquely by $\chi_{S}$)

\paragraph*{The algorithm}
\begin{itemize}
    \item Choose $r\leftarrow_{R}\{\pm1\}^{n}$
    \item $\forall i\in[n]$ put $i$ in $S$ if $f(r)\neq f(r\cdot e_{i})$
\end{itemize}
\paragraph*{Why does it work?}
\begin{eqnarray*}
\Pr\left[\mbox{$i$ is decided incorrectly}\right] & \leq & \Pr\left[f(r)\neq\chi_{S}(r)\mbox{ or }f(r\cdot e_{i})\neq\chi_{S}(r\cdot e_{i})\right]\\
 & \leq & \Pr\left[f(r)\neq\chi_{S}(r)\right]+\Pr\left[\, f(r\cdot e_{i})\neq\chi_{S}(r\cdot e_{i})\right] \, \mbox{(union bound)} \\
 & \leq & \frac{1}{4n}+\frac{1}{4n}=\frac{1}{2n} \, \mbox{($r$ and $r\cdot e_{i}$ are uniformly distributed)} \\
\end{eqnarray*}
$\Rightarrow \Pr\left[\mbox{any $i$ is decided incorrectly}\right] \leq n\cdot\frac{1}{2n}=\frac{1}{2}$ (union bound)
\\

\subsection{Warmup 4}
Exists $S$ s.t. $f$ agrees with $\chi_{S}$ on $\geq\frac{3}{4}+\epsilon$ fraction of the inputs, for a constant $\epsilon$. Note the previous algorithm doesn't work. We will use standard amplification techniques.

\paragraph*{The algorithm}
\begin{itemize}
    \item Choose $r_{1},r_{2},...,r_{t}\leftarrow_{R}\{\pm1\}^{n}$ where $t=\Theta(\frac{\log(n)}{\epsilon^{2}})$
    \item $\forall i\in[n]$ put $i$ in $S$ if for the majority of $r_{j}$'s $f(r_{j})\neq f(r_{j}\cdot e_{i})$
\end{itemize}
\paragraph*{Why does it work?\\}
$\Pr\left[\mbox{wrong answer for $i$ on $r_{j}$} \right] \leq \frac{1}{2}-2\epsilon$ \\
$\Rightarrow \Pr\left[\mbox{most $r_{j}$'s wrong for $i$}\right] \leq \frac{1}{2n}$ (by Chernoff and the choice of $t$)\\
$\Rightarrow \Pr\left[\mbox{any $i$ is decided incorrectly}\right] \leq \frac{1}{2}$ (union bound)
\\

\subsection{Warmup 5}
Exists $S$ s.t. $f$ agrees with $\chi_{S}$ on $\geq\frac{1}{2}+\epsilon$ fraction of the inputs, for a constant $\epsilon$.
Note we cannot win with the union bound as before, and we must decide on $i$ using only one query. To do this, we can just assume we are given the correct values of $\sigma_{j}=\chi_{S}(r_{j})$. The problem now becomes that of testing $\sigma_{j}\neq f(r_{j}\cdot e_{i})$ using the previous techniques. Since we can eventually verify (by sampling) that our output function is indeed close to $f$, we can simply enumerate all possible values of the $\sigma_{j}$'s.

\paragraph*{The algorithm}
\begin{itemize}
    \item Choose $r_{1},r_{2},...,r_{t}\leftarrow_{R}\{\pm1\}^{n}$ where $t=\Theta(\frac{\log(n)}{\epsilon^{2}})$
    \item \emph{Generating candidates}\\
    For all possible settings of $\sigma_{1}\sigma_{2},...\sigma_{t}$ (guesses of $\chi_{S}(r_{j})$'s)\\
 	$\forall i\in[n]$ put $i$ in $S_{\sigma_{1}\sigma_{2}...\sigma_{t}}$ if for the majority of $r_{j}$'s $\sigma_{j}\neq f(r_{j}\cdot e_{i})$
    \item \emph{Verify the candidates before outputting}\\
    Test $\chi_{S_{\sigma_{1}\sigma_{2}...\sigma_{t}}}$ agrees with $f$ on $\geq \frac{1}{2}+\frac{3}{4}\epsilon$ fraction of inputs by sampling
\end{itemize}
\paragraph*{Why does it work?\\}
For each $S$ that should be output there are $\sigma_{1},\sigma_{2},...,\sigma_{t}$ s.t. $\forall j \, \sigma_{j}=\chi_{S}(r_{j})$.\\
The test puts $i$ in $S$ if $\sigma_{j}\cdot f(r_{j}\cdot e_{i}) = -1$. The test succeeds when $f(r_{j}\cdot e_{i})\cdot \sigma_{j} = \chi_{S}(e_{i})$. Note that if $f(r_{j}\cdot e_{i})=\chi_{S}(r_{j}\cdot e_{i})$ then $f(r_{j}\cdot e_{i})\cdot 
\chi_{S}(r_{j}) = \chi_{S}(r_{j}\cdot e_{i})\cdot \chi_{S}(r_{j}) = \chi_{S}(e_{i})$ and the test succeeds.
\begin{eqnarray*}
\Pr\left[\mbox{right answer for $r_{j}$ on $i$}\right] & = & \Pr\left[f(r_{j}\cdot e_{i})\cdot \sigma_{j}=\chi_{S}(e_{i})\right]\\
 & \geq & \Pr\left[f(r_{j}\cdot e_{i})=\chi_{S}(r_{j}\cdot e_{i})\right]\\
 & \geq & \frac{1}{2}+\epsilon
\end{eqnarray*}
$\Rightarrow \Pr\left[\mbox{most $r_{j}$'s wrong for $i$}\right] \leq \frac{1}{2n}$ (by Chernoff and the choice of $t$)\\
$\Rightarrow \Pr\left[\mbox{any $i$ is decided incorrectly}\right] \leq \frac{1}{2}$ (union bound)\\
\\This analysis shows that if the $\sigma_{j}$'s are consistent with $\chi_{S}$ and $\chi_{S}$ is close to $f$, then it will be output w.p. at least half, which can easily be amplified. Since we enumerate all the possible $\sigma_{j}$'s, it remains to show that no far functions will be output. This is guaranteed from the verification stage that ensures functions that are $(\frac{1}{2}+\frac{\epsilon}{2})$-far are output with low probability.

\subsection{Finally -- The Real Problem}
Exists $S$ s.t. $f$ agrees with $\chi_{S}$ on $\geq\frac{1}{2}+\epsilon$ fraction of the inputs, for \emph{any} $\epsilon$. The last algorithm we've seen requires $\epsilon$ to be constant for Chernoff to work for small $t$'s. Larger $t$'s are not advised as we enumerate $2^t$ possible $\sigma$'s. Since we are dealing with linear functions, we can guess a much smaller set and compute the function values in all possible linear combinations.

\paragraph*{The algorithm}
\begin{itemize}
    \item Choose $u_{1},u_{2},...,u_{k}\leftarrow_{R}\{\pm1\}^{n}$ where $k=\log(t+1)$, $t=\Theta(\frac{n}{\epsilon^{2}}$ (number of $r_{j}$'s)
    \item \emph{Generating lots of examples ($\Theta(\frac{n}{\epsilon^{2}})$)}\\
    For all possible settings of $\sigma_{1},\sigma_{2},...,\sigma_{k}$ (guesses of $\chi_{S}(u_{j})$'s)\\
    For every $w\subseteq\{1,...,k\},\, w\neq\emptyset$\\
    Set $r_{w}\leftarrow\oplus_{j\in w}u_{j}$ and $p_{w}\leftarrow\prod_{j\in w}\sigma_{j}$
    \item \emph{Generating candidates}\\
    For all possible settings of $\sigma_{1},\sigma_{2},...,\sigma_{k}$ (guesses of $\chi_{S}(u_{j})$'s)\\
 	$\forall i\in[n]$ put $i$ in $S_{\sigma_{1}\sigma_{2}...\sigma_{k}}$ if for the majority of $r_{j}$'s $p_{w}\neq f(r_{w}\cdot e_{i})$
    \item \emph{Verify the candidates before outputting}\\
    Test $\chi_{S_{\sigma_{1}\sigma_{2}...\sigma_{k}}}$ agrees with $f$ on $\geq \frac{1}{2}+\frac{3}{4}\epsilon$ fraction of inputs by sampling
\end{itemize}

\paragraph*{Why does it work?\\}
As before, for a "given" $S$ the test succeeds for $r_{w}$ when $f(r_{w}\cdot e_{i})\cdot p_{w} = \chi_{S}(e_{i})$, and this happens w.p. $\geq \frac{1}{2}+\epsilon$. Let $X_{w}$ be an indicator for this event. Unfortunately, unlike in the last warmup, we can no longer claim independence of the indicators and apply the Chernoff bound. However, as in the constructions in lecture 3, the $r_{w}$'s are \emph{pairwise independent}.\\
We have: $\mbox{E}[X_{w}]\geq \frac{1}{2}+\epsilon$, $\mbox{VAR}[X_{w}]=\mbox{E}[X_{w}^2]-\mbox{E}[X_{w}]\leq \frac{1}{4}-\epsilon^2$. By Chebychev,
\begin{eqnarray*}
\\Pr\left[\mbox{most $r_{j}$'s wrong for $i$}\right] & = & \Pr[\sum{X_{w}}<\frac{t}{2}]\\
 & \leq & \Pr[\left|\frac{1}{n}\sum{X_w}-\mbox{E}[X_{w}]\right|>\epsilon]\\
 & \leq & \frac{\mbox{VAR}[X_{w}]}{\epsilon^2 t}\leq \frac{1}{2n}
\end{eqnarray*}
$\Rightarrow \Pr\left[\mbox{any $i$ is decided incorrectly}\right] \leq \frac{1}{2}$ (union bound)\\

\begin{theorem}
There is an algorithm which outputs all $S$ s.t. $|\hat{f}(S)|\geq\theta$ and doesn't output any $S$ s.t. $|\hat{f}(S)|\leq\frac{\theta}{2}$ w.p. $\geq 1-\delta$ with query and time complexity $\poly(n, \frac{1}{\theta}, \log(\frac{1}{\delta}))$
\end{theorem}

\begin{corollary}
The number of sets $S$ s.t. $|\hat{f}(S)|\geq\theta$ is at most $O(\frac{n}{\theta^2})$
\end{corollary}

\begin{theorem}
Given $\mathcal{S}\subseteq 2^{[n]}$ (a collection of subsets) s.t. $\sum_{S\in \mathcal{S}}\hat{f}(S)^2\geq 1-\epsilon$ and $\poly(n,|\mathcal{S}|,\frac{1}{\tau},\log(\frac{1}{\delta})$ uniformly chosen examples of $f$, there is an algorithm which outputs $g(x):\{\pm1\}^{n}\rightarrow \mathbb{R}$ s.t. $g(x)=\sum_{S\in \mathcal{S}}C_{S}\chi_{S}(x)$ and $\Pr\left[\mbox{sign}(g(x))\neq f(x)\right]\leq\epsilon+\tau$ w.p. $\geq 1-\delta$
\end{theorem}
\begin{proof-idea}
Use previous theorem and the ideas from the low degree algorithm of last lecture.
\end{proof-idea}

\section{Learning Functions with Small $L_1$ Norm}

\begin{define}
The $L_{1}$ norm of $f$ is $L_{1}(f)=\sum_{S}|\hat{f}(S)|$
\end{define}
Examples:
\begin{itemize}
\item $L_{1}(\chi_{S})=1$
\item $L_{1}((x_{1}\wedge x_{2})\oplus(x_{3}\wedge x_{4})\oplus...)=2^{\frac {n}{2}}$
\end{itemize}

\begin{claim}
Given $\epsilon$, $\mathcal{S}_{\epsilon}=\left\{S\subseteq [n]: |\hat{f}(S)|\geq \frac{\epsilon}{L_{1}(f)}\right\}$ then:
\begin{enumerate}
	\item $|\mathcal{S}_{\epsilon}|\leq \frac{L_{1}(f)^2}{\epsilon}$
	\item $\sum_{S\in \mathcal{S}_{\epsilon}}\hat{f}(S)^{2}\geq1-\epsilon$
\end{enumerate}
\end{claim}
\begin{proof}
\begin{enumerate}
	\item $L_{1}(f)\geq \sum_{S\in \mathcal{S}_{\epsilon}}|\hat{f}(S)|\geq \frac{\epsilon}{L_{1}(f)}|\mathcal{S}_{\epsilon}|$
	\item $\sum_{S\notin \mathcal{S}_{\epsilon}}\hat{f}(S)^2\leq \max_{S\notin \mathcal{S}_{\epsilon}}|\hat{f}(S)|\cdot \sum_{S\notin \mathcal{S}_{\epsilon}}|\hat{f}(S)|\leq \frac{\epsilon}{L_{1}(f)}L_{1}(f)=\epsilon$. By Boolean Parseval, $\sum_{S}\hat{f}(S)^2=1$ and so $\sum_{S\in \mathcal{S}_{\epsilon}}\hat{f}(S)^{2}\geq1-\epsilon$
\end{enumerate}
\end{proof}

\begin{theorem}
We can learn any Boolean function to $\epsilon$-accuracy with membership queries \\
in time $\poly(n,L_{1}(f),\frac{1}{\epsilon})$
\end{theorem}
\begin{proof}
Use theorems 1 and 3 with $\theta={\epsilon}{L_{1}(f)}$. If $L_{1}(f)$ is unknown, try values $2,4,8,\dots$ for $L_{1}(f)$ until you find a good hypothesis (Can always test it by random sampling).
\end{proof}

\subsection{Learning Decision Trees}

\begin{theorem}
If $f$ has decision tree with $\leq t$ leaves then $L_{1}(f)\leq t$
\end{theorem}

\begin{proof}
Fix leaf $l$. Define $g_l=I[{\mbox{$x$ reaches $l$}}]$, let $x_{i_1},\dots,x_{i_k}$ be the path to $l$, and $m$ the number of left turns taken. Recall $g_l(x)=\left(\frac{1\pm x_{i_1}}{2}\right)\cdot \left(\frac{1\pm x_{i_2}}{2}\right)\cdot\dots\cdot\left(\frac{1\pm x_{i_k}}{2}\right) = \frac{1}{2^k}\sum_{S\in [k]}(-1)^m\chi_{S}(x)$ and so $L_1(g_l) = \sum_{S\in[k]}|\hat(g)_l(S)|=2^k\cdot \frac{1}{2^k}=1$\\
Since $f(x)=\sum_{l}g_l(x)(\mbox{output of leaf $l$})$ we have $\hat{f}(x)=\sum_{l}\hat{g}_l(x)(\mbox{output of leaf $l$})$\\
\\
$\Rightarrow L_1(f) = \sum_{S}|\hat{f}(S)| = \sum_{S}\sum_{l}|\hat{g}_l(x)\cdot(\pm 1)| = \sum_{l}\sum_{S}|\hat{g}_l(x)| = \sum_{l}L_1(g_l)=\sum_{l}1=t$
\end{proof}

\end{document}
