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


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

\begin{document}
\input{preamble.tex}
\newcommand{\poisson}{{\rm Pois}}
\newcommand{\pbd}{{\rm PBD}}
\newtheorem{example}[theorem]{Example}


%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{17}{April 10, 2019}{Ronitt Rubinfeld}{Yinzhan Xu}

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


\section{Outline}
Today we covered the following topics:
\begin{itemize}
\item Learning and testing Poisson Binomial Distributions.
\item Introduction to local computation algorithms.
\item An outline for a local computation algorithm of maximal independent set. 
\end{itemize}

\section{Poisson Binomial Distributions (PBDs)}

The Poisson binomial distribution is the distribution of a sum of independent Bernoulli variables that are not necessarily identically distributed. More specifically, given a sequence $p_1, p_2, \ldots, p_n$ of real numbers in $[0, 1]$, we define
$$\pbd(p_1, p_2, \ldots, p_n) : X=\sum_{i=1}^n X_i,$$
where $X_i$s are independent random Bernoulli variables, such that $\mathbb{E}[X_i] = p_i$. Note that since $p_i$ can be different for each $i$, these $X_i$s are not necessarily identically distributed. 

\begin{example}
When $p_i = \frac{1}{2}$ for every $1 \le i \le n$, $\pbd(p)$ is a binomial distribution.  
\end{example}

\begin{example}
Suppose $p_1 = \frac{1}{2}, p_2 = 1$, and $p_i = 0$ for all $i \ge 3$. Then 
$$\Pr[\pbd(p)=k] = \left\{
  \begin{array}{ll}
    \frac{1}{2} & : k = 1 \ {\rm or}\ k = 2\\
    0 & : {\rm otherwise}
  \end{array}
\right.
$$
\end{example}
In the remainder of this section, we will compare PBDs with some other families of distributions, and show two ways to learn PBDs. 

\subsection{PBDs vs Poisson}
We first review the definition of Poisson distributions:
$$\poisson(\lambda): \Pr[X=k] = e^{-\lambda} \cdot \frac{\lambda^k}{k!}.$$
Many useful and interesting facts about Poisson distributions are mentioned during the class, but they are not necessarily related to this lecture.
\begin{fact}
$\mathbb{E}[\poisson(\lambda)] = {\rm Var}[\poisson(\lambda)] = \lambda$.
\end{fact}
\begin{fact}\label{fact:pois_sum}
If $X_i \sim \poisson(\lambda_i)$ for $i=1, \ldots, n$ are independent, then $$Y=\left(\sum_{i=1}^n X_i\right) \sim \poisson\left(\sum_{i=1}^n \lambda_i\right)$$. 
\end{fact}
Surprisingly, the converse of Fact \ref{fact:pois_sum} is also true:
\begin{theorem}[Raikov's theorem, \cite{raikov1937decomposition}]
If the sum of two independent random variables is Poisson-distributed, then so are each of those two independent random variables.
\end{theorem}
\begin{fact}
If $n$ is large and $p$ is small enough, then $\poisson(np)$ is close to $B(n, p)$. 
\end{fact}

The following theorem shows that the PBDs are actually pretty close to some Poisson distributions. 
\begin{theorem}[Le Cam's theorem, \cite{le1960approximation}]\label{thm:lecam}
For any sequence $p_1, p_2, \ldots, p_n$, where each $p_i$ is a real number in $[0, 1]$, 
$$\left|\pbd(p)-\poisson\left(\sum_{i=1}^n p_i\right) \right|_1 \le 4 \sum_{i=1}^n p_i^2.$$
\end{theorem}
We omit the proof of Theorem~\ref{thm:lecam}. Theorem~\ref{thm:lecam} indicates that Poisson approximation of PBDs is pretty good, but not arbitrarily good: the $\ell_1$ distance is determined by $p$, and we cannot find a Poisson distribution that is $\epsilon$-close to $\pbd(p)$, for an arbitrary $\epsilon$. 
\subsection{PBDs vs Translated Poisson Distribution}

Using translated Poisson distribution, we can obtain a better approximation to PBDs. We first define the translated Poisson distribution ${\rm TP}(\mu, \delta^2)$: $Y=\lfloor \mu - \delta^2\rfloor + Z$, where $Z \sim \poisson(\delta^2 + \{\mu - \delta^2\})$. Here, the notation $\{x\}$ means the fractional part of $x$, which formally is $x - \lfloor x\rfloor$. 

The following theorem states that we can approximate PBDs with translated Poisson distribution. 
\begin{theorem}[\cite{rollin2007translated}]\label{thm:tpd}
Given a sequence $p_1, p_2, \ldots, p_n$, define $\mu = \sum_{i} p_i$, and $\delta^2 = \sum_{i}p_i(1-p_i)$. Then 
$$\mathlarger{\left| \pbd(p) - {\rm TP}(\mu, \delta^2)\right|_1 \le 2 \cdot \frac{\sqrt{\sum_{i=1}^n p_i^3(1-p_i)} + 2}{\sum_{i=1}^n p_i(1-p_i)}}.$$
\end{theorem}
When each $p_i$ is within $[c, 1-c]$ for some constant $c$,  the right hand side of Theorem~\ref{thm:tpd} gives $O(n^{-1/2})$; whereas Theorem~\ref{thm:lecam} only gives an $O(n)$ bound. 

\subsection{Learning and Testing PBDs}

In this section, we will describe two methods to learn the PBDs. The first method uses the fact that PBDs are unimodal, and then reduces the problem to  learning monotone distributions. The second method uses the structural theorem, which classifies all PBDs to two categories. The structural theorem also implies a way to test PBDs. 

In both of these methods, we will use the cover method discussed in the last lecture. For a quick reminder, if we have an $\epsilon$-cover $\mathcal{C}$ of a set of distributions $\mathcal{D}$, then we can learn $p \in \mathcal{D}$ using $O(\frac{1}{\epsilon^2} \log |\mathcal{C}|)$ samples of $p$. 

\subsubsection{The Unimodal Method}

\begin{theorem}\label{thm:unimodal}
Every Poisson binomial distribution is unimodal over $[n]$. More specifically, there exists $k \in [n]$, such that the distribution is monotonically increasing in $[1, k]$, and monotonically decreasing in $[k, n]$.
\end{theorem}
With Theorem~\ref{thm:unimodal}, we can construct a cover with reasonable size. The number of possible modal $k$ is $O(n)$. For each fixed $k$, the distribution is a combination of two monotone distributions. Since we can construct an $\epsilon$-cover for monotone distributions of size $O(\frac{1}{\epsilon^{\log n/\epsilon}})$, we can construct an $\epsilon$-cover $\mathcal{C}$ for Poisson binomial distributions of size $O\left(n \cdot \left(\frac{1}{\epsilon^{\log n/\epsilon}}\right)^2\right)$. Thus, there exists an algorithm that takes 
$$O\left(\frac{1}{\epsilon^2} \log|\mathcal{C}|\right) = O\left(\frac{1}{\epsilon^3} \log n \cdot \log \frac{1}{\epsilon}\right)$$
samples.

\subsubsection{Structure Theorem}
Even though the unimodal method already gives a sublinear time algorithm, the dependency on $\log n$ is not ideal. Also, it does not provide a way to test whether a distribution is PBD. The following theorem resolves these two issues. 
\begin{theorem}[Structure Theorem]
Every Poisson binomial distribution is $\epsilon$-close in $\ell_1$ distance to a distribution $Y$ in one of the following two families:
\begin{itemize}
\item ($\frac{1}{\epsilon}$-sparse) The support of $Y$ is on an interval of length $O(1/\epsilon^3)$. 
\item ($\frac{1}{\epsilon}$-heavy Binomial) $Y$ is a binomial distribution on $\Omega({\rm poly}(1/\epsilon))$ i.i.d. variables. 
\end{itemize}
\end{theorem}

\paragraph{Learning using Structure Theorem}
Still we construct a small $\epsilon$-cover. In the $\frac{1}{\epsilon}$-sparse case, there are $n$ possible places for the support. Inside the support, we can enumerate all possible probabilities up to granularity $\epsilon^4$. Thus, the size of the cover would be $O(n \cdot (1/\epsilon^4)^{1/\epsilon^3})$. For the $\frac{1}{\epsilon}$-heavy Binomial case, there are up to $n$ possible choices for the number of i.i.d. variables, and we can enumerate possible probabilities of each variables up to granularity $O(\poly(\epsilon))$. Thus, the size of the cover for this case is at most $O(n \cdot \poly(1/\epsilon))$. The logarithm of the size of the cover would be $O(\log n \cdot \poly(1/\epsilon))$, so number of samples required for learning is $O(\log n \cdot \poly(1/\epsilon))$. 

\paragraph{High Level Idea for Removing the $\log n$ dependency} For the $\frac{1}{\epsilon}$-sparse case, we can learn the offset of the interval by a few samples since almost all probability mass is in the interval. After we know the interval, the size of the $\epsilon$-cover will not have a factor of $n$. The $\log n$ dependency for the   $\frac{1}{\epsilon}$-heavy Binomial case can also be removed, but we did not cover this in lecture. 

\paragraph{Testing using Structure Theorem}

For the $\frac{1}{\epsilon}$-sparse case, the effective support size is small, so we can test the distribution in time polynomial in the support size. For the $\frac{1}{\epsilon}$-heavy Binomial, we know that almost the entire probability mass of this distribution is centered on the middle $O(\sqrt{n})$ elements, by concentration bound like Chernoff. Therefore, we can test the distribution in $O(n^{1/4})$ time. 


\section{Local Computation Algorithm}

In this section, we switch to a completely different topic. In previous lectures, we care about problems that have a large input size, but the output size is usually small. In reality, many problems also have large output size. In many cases, we  don't need to compute the whole output. This section will introduce some example problems that fall into this category, describe the model for local computation algorithms, and outline a locally computable maximal independent set algorithm. 

\subsection{Examples}

\paragraph{Locally Decodable Codes}
Given a string of bits $w$, we use some code to encode it to get ${\rm ENC}(w)$. The decoding problem is to compute $w$ from ${\rm ENC}(w)$. In many applications, we don't need the whole string $w$. Instead, we only want to compute a single bit $w_i$. Can we achieve this by only looking at a small number of encoded bits? The answer is yes by using locally decodable codes.

\paragraph{Local Property Reconstruction}
Suppose the data has some property $\mathcal{P}$, but it was corrupted. Can we change a small portion of the data so that it satisfies the property again? For instance, suppose the data was monotone, but $\epsilon n$ positions of the data have been modified. We need to change at most $O(\epsilon n)$ places in the data to change it back to monotone. Local Property Reconstruction imposes another constraint to the problem: to output the new value of a certain data point, we can only look at a small number of old data values. 

\paragraph{Estimating Graph
Parameters} Many problems fall into this category, like page
rank, communities,
dominating set, and maximal independent set. Take dominating set for example. For each node, we need to output whether it is in the dominating set, by only querying a few other nodes. 

\subsection{Local Computation Algorithm: a Model}

A local computation algorithm (LCA) outputs a bit $y_i$ of the output if an index $i$ is queries, and it probes  several bits $x_j$ of the input. The queries $i_1, i_2, \ldots$ can happen in either sequential or parallel. 

\begin{figure}[h]
\centering
\includegraphics[width=8cm]{a}
\caption{A graphical illustration of the model. }
\end{figure}

Usually, there can be multiple LCAs that process queries at the same time. 
One difficulty in this model is that there can be more than one valid output. For instance, if we query whether some vertex is in a maximal independent set, we can always answer ``yes'' to each individual queries, since every vertex is in some maximal independent set. Therefore, we need some way for all LCAs to have a consistent view. 

One common method to overcome this issue is to share some (short) random strings among all instances of LCAs at the beginning. Afterwards, each instance needs to compute independently. 

\subsection{Maximal Independent Set}

In this section, we discuss local computation algorithms for maximal independent set of an undirected graph $G=(V, E)$. The graph is sparse: each vertex has degree at most $d$. The maximal independent set $I$ is a subset of $V$, such that any two vertices in $I$ are not connected, and all vertices in $V \setminus I$ are connected to at least one vertex  in $I$. 

Unlike \textit{maximum} independent set, which is ${\rm NP}$-complete, it is easy to compute a \textit{maximal} independent set. For instance, we can try to add vertices to $I$ one by one. If a vertex $v_i$ is not connected to any vertex in $I$, then we add it to $I$; otherwise, we do not add it to $I$. This algorithm actually produces a lexicographically-first maximal independent set. However, we do not expect to have very fast local computation algorithm to compute the lexicographically-first maximal independent set because of the following theorem.
\begin{theorem}
Lexicographically-first-MIS is P-complete. That is, if there exists a parallel algorithm of ${\rm polylog}(n)$-depth that computes it, then every problem in $P$ has a parallel algorithm of ${\rm polylog}(n)$-depth. 
\end{theorem}

A common way to design a local computation algorithm is to simulate a distributed algorithm. If there is a $k$ round distributed algorithm for maximal independent set, then the output of a particular vertex $v$ depends only on inputs and computations of the $k$-radius ball around $v$. Since there are at most $O(d^k)$ vertices in the $k$-radius ball, we can simulate this algorithm in $O(d^k)$ probes. Unfortunately, the best algorithm runs in $O(\log n)$ rounds, which yields an $O(d^{c \log n}) = 2^{O(\log d \log n)}$ LCA.

\begin{figure}[h]
\centering
\includegraphics[width=4cm]{ball.eps}
\caption{The $k$-radius ball is small compared to the whole graph. }
\end{figure}

The main idea for the sublinear time LCA is to use distributed algorithm to ``shatter'' the graph. Basically, we want to run a distributed algorithm for a small number of rounds, so that we only need to consider connected components of ${\rm polylog} n$ size. 

Many distributed MIS
algorithms have the following outline:

\begin{algorithm}[!h]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
All nodes start out ``live''    

    \For{each round}{
    
    Live nodes toss coins\\
    
    Live nodes use coins and interaction with neighbors to
decide whether to join MIS\\

If node or its neighbor joined MIS, node ``dies''

    }
    
    \caption{Distributed MIS}
    \label{alg:dist_mis}
\end{algorithm}
Usually, Algorithm~\ref{alg:dist_mis} will repeat until all nodes die, which would require $O(\log n)$ rounds. Here, we will repeat until a constant fraction of nodes die. It turns out we only need $O(d)$ rounds in this case. In fact, after we run $O(d)$ rounds of a variant of Algorithm~\ref{alg:dist_mis}, we can prove that with high probability, the remaining ``live'' connected components are logarithmically small. The proof is delayed to the next lecture and will use a  Beck-like analysis for algorithmic Lovasz Local
Lemma. 

Now again we can use a sequential execution to simulate the above distributed algorithm. Let ${\rm ALIVE}(v)$ be the sequential simulation of $v$'s local view of distributed algorithm in $d^{O(d)}$ probes. Using ${\rm ALIVE}(v)$, we can define the following LCA algorithm. 

\begin{algorithm}[H]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
    
    \If{$v$'s output is determined by ${\rm ALIVE}(v)$}{output it}
    \Else{Find $v$'s small ``live'' connected component via BFS, by calling
${\rm ALIVE}(*)$\\
Output ``yes'' if $v$ is in the lexicographically first MIS in this live
component}
    
    \caption{LCA($v$)}
    \label{alg:lca}
\end{algorithm}

The number of times Algorithm~\ref{alg:lca} calls ${\rm LCA}$ is at most $d$ times the size of the connected component of $v$. Therefore, Algorithm~\ref{alg:lca} runs in $O(d^{O(d)} {\rm polylog} n)$ time. 

Next lecture, we will prove the size of the ``live'' connected components are $O({\rm polylog} n))$. 
\bibliographystyle{plain}
\bibliography{ref}
\end{document}


