\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{bbm}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage[linewidth=1pt]{mdframed}
\usepackage{lipsum}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring'20)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{20: MWU Application, Models for Large-scale Computation}{Apr
9, 2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Ruoshi Liu, Hongjin Wang}}

\section{Recap: Multiplicative Weights Update}

\textbf{Problem Definition}
We have n "experts" and an event which lasts from 1 to T. At each timestamp, each expert will make a prediction of the event. We define the following terms:\\

\textbullet{} $f_i^t \in [-1, +1]$: the error of expert $i$ at time $t$\\

\textbullet{} $m_i^T = \sum_{t=1}^T f_i^t$: number of errors of expert i\\

\textbullet{} $M^T = \sum_{t=1}^T f_{e_i}^t$: number of our errors, where $e_i$ is the expert we chose to follow at time t\\[0.1in]
\textbf{A Randomized Algorithm}
\begin{enumerate}
    \item Keep weights $w_i^t > 0$, where i is in index for expert, and t is for time
    \item Initialize $w_i^t = 1$
    \item At time t, make prediction: $i ~ p$, $p_i^t = \frac{w_i^t}{\sum_j w_j^t}$ and
            update: $w_i^{t+1} = w_i^t(1-\varepsilon f_i^t)$
\end{enumerate}
\begin{theorem}
$M^T \leq min_i m_i^T + \frac{\ln n}{\varepsilon} + \varepsilon T$
\end{theorem}
\begin{corollary}
If $T > \frac{\ln n}{\varepsilon^2} \implies M^T \leq min_i m_i^T + 2\varepsilon T$
\end{corollary}
Note that the theorem has been proved in last lecture.

\section{Application of MWU: feasibility of LP}
\textbf{Problem Definition}: feasibility of a standard-form LP: $\exists x \in \mathbb{R}$, s.t. $Ax \geq b$\\[0.1in]
\textbf{Relaxed Version}: distinguish between
\begin{enumerate}
    \item $\exists x \in \mathbb{R}^n$, s.t. $Ax \geq b - \varepsilon \mathbbm{1}_m$
    \item $\exists! x$ s.t. $Ax \geq b$
\end{enumerate}
To solve the relaxed version of the problem, we assume an access to the following oracle:\\ 

\begin{mdframed}
    \begin{definition}
        $\mathcal{O}$ is an oracle the given an input of $p \in \mathbb{R}^m$, if $\exists x \in \mathbb{R}^m$ s.t. $p^T Ax \geq p^T b$ and  $max_i|A_i x - b_i| \leq 1$, then output x; output 'NO' otherwise
    \end{definition}
\end{mdframed}

\begin{theorem}
We can solve the relaxed version of the LP-feasibility problem using $O(\frac{\ln n)}{\varepsilon^2}$ oracle calls
\end{theorem}

We give an algorithm solving the feasibility problem using the oracle specified above:
\begin{enumerate}
    \item Initilize $w_i^1 = 1$ , $\forall i \in \{1, ..., m\}$, where m is the number of experts
    \item at iteration t $\in$ ${1, ..., \mathbb{O}(\frac{\ln n}{\varepsilon^2})}$
    \begin{enumerate}
        \item $p_i^t = \frac{w_i^t}{\sum_j w_j^t}$; $p^t = [p_1^t, p_2^t, ..., p_m^t]$
        \item $x^t = \mathcal{O}(p^t)$
        \item if $\exists ! x$ $\implies$ return \textit{Infeasible}
        \item $w_i^{t+1} = w_i^t(1 - \varepsilon f_i^t)$, $f_i^t = A_i x - b_i$
    \end{enumerate}
    \item return the average: $\Bar{x} = \sum_{t=1}^T \frac{x^t}{T}$
\end{enumerate}

Intuition of the algorithm: in step 2.(d), if $f_i^t$ is bigger than 0, or in other words, the constraint i is well satisfied from expert i perspective, then the weight corresponding to that expert will decrease. According to step 2.(a), the probability of choosing that specific expert will also decrease. Therefore in the next iteration, the oracle will focus more on other constraints that are less satisfied.

\begin{proof}
  First, If the algorithm returns 'inf' $\implies$ the relaxed problem is infeasible.\\
  Here we draw connection to MWU: expert i is the same as constraint $A_i x \geq b_i$\\
  We define $f_i^t$ as the error at constraint i:
  \begin{equation}
      f_i^t = A_i x^t - b_i;
      f^t = A x^t - b
  \end{equation}
  which satisfies $f_i^t \in [-1, +1]$ by $\mathcal{O}$\\
  By definition,
  \begin{align*}
      M^T &= \sum_{t=1}^T <p^t, f^t> \\
      &= \sum_{t=1}^T \sum_{i=1}^m p_i^t \cdot f_i^t\\
      &= \sum_t <p^t, Ax^t - b>\\
      &= \sum_t <p^t, Ax^t> - \sum_t<p^t, b>\\
      &= \sum_t [(p^t)^T Ax^t - (P^t)^T\cdot b] \geq 0
  \end{align*}
  
  From corallary 2 , we know that,
  \begin{equation}
      M^t \leq m_i^T + 2\varepsilon T, \forall i \in [m]
  \end{equation}
  Which implies,
\begin{align*}
    m_i^T \geq -2\varepsilon T &\implies \sum_{t=1}^T f_i^t \geq -2\varepsilon T\\
    &\implies \sum_{t=1}^T [A_i x^t - b_i] \geq -2\varepsilon T\\
    &\implies A_i\cdot \sum_{t=1}^T x^t \geq T\cdot b_i - 2\varepsilon t\\
    &\implies A_i \cdot \frac{\sum_{t=1}^T x^t}{T} \geq b_i - 2\varepsilon
\end{align*}
\end{proof}


Student question: How can we guarantee $\max_i |A_ix-b_i|\leq 1$?

Suppose we can solve $\mathcal{O}$:$$\max_i |A_ix-b_i|\leq k, Ax\geq b$$
$$\Rightarrow\max_i |\frac{A_i}{k}x-\frac{b_i}{k}|\leq 1$$

This can be solve approximately:
$$\frac{A}{k}x\geq \frac{b}{k}-\epsilon \mathbbm{1}m$$
$$\Rightarrow Ax\geq b-\epsilon k\mathbbm{1}m$$

Define $\epsilon^\prime = \epsilon k$

by above can be solved in $T=O(\frac{\lg n}{\epsilon^2}) = O(k^2 \frac{\lg n}{(\epsilon^\prime)^2})$
\section{Large Scale Model}
From now on we design algorithm taking into account the architecture.

\subsection{Usual Model(RAM Model)}
See Figure \ref{fig1}
\begin{figure}[h]
    \centering
    \includegraphics[scale = 0.8]{fig19.png}
    \caption{Usual Model(RAM Model)}
    \label{fig1}
\end{figure}

\subsection{Modern Model}
See Figure \ref{fig2}
\begin{figure}[h]
    \centering
    \includegraphics[scale = 0.8]{fig19-2.png}
    \caption{Modern Model}
    \label{fig2}
\end{figure}

\subsection{I/O Model}
See Figure \ref{fig3}
\begin{figure}[h]
    \centering
    \includegraphics[scale = 0.8]{fig19-3.png}
    \caption{I/O model}
    \label{fig3}
\end{figure}

\begin{itemize}
    \item CPU with O(1) registers(or cell of memory/word)
    \item cache of size $M$
    \item unlimited memory
    \item cache/memory are composed of cache lines, each of $B$ words
    \item when accessing a new location $x$, if it not in cache, we need to bring entire cache line
    \item cache line: Starts at $B\cdot i, i\in N$, ends at $B\cdot(i+1)-1$
    \item when cache is full, throw one cache line out(replace), either "manually" or Least Recently Used(LRU) policy
\end{itemize}

Since accessing cache is cheap, while accessing memory is expensive, we can define \textbf{cost} as number of times bring a cache line from memory into cache.
\subsection{ Problem: searching memory }
Searching $x$ in an unsorted array of size N.

\begin{itemize}
    \item RAM model: O(N)
    \item I/O model: Assume array stored linearly. O(N/B+1)
\end{itemize}

\begin{figure}[h]
    \centering
    \includegraphics[scale = 0.8]{fig4.png}
    \caption{Search $x$ in an unsorted array}
    \label{fig4}
\end{figure}
\begin{proof}

The proof is illustrated in Figure \ref{fig4}.

  When $N\leq B$, it depends on whether the array is divided by the cache line boundary.  $cost = 2$ if divided, $cost = 1$ if not.
  
  When $N> B$, the array straddles $\leq N/B +2$ cache lines $\Rightarrow O(N/B+1)$ "runtime" 
  
\end{proof}





\end{document}
