done sun night

1 files changed, 84 insertions, 7 deletions

diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex
index ca60e04..98de9c2 100644
--- a/slides/BudgetFeasibleExperimentalDesign.tex
+++ b/slides/BudgetFeasibleExperimentalDesign.tex
@@ -126,7 +126,7 @@
 
     \begin{center}
         \begin{overprint}
-        \onslide<1>\begin{center}$N$ users (``experiment subjects''), $[N]\equiv \{1,\ldots,N\}$ \end{center}
+        \onslide<1>\begin{center}$N$ ``experiment subjects'', $[N]\equiv \{1,\ldots,N\}$ \end{center}
             \onslide<2>
             \begin{center}
                 $x_i\in \reals^d$: public features (\eg, age, gender, height, \etc)
@@ -528,7 +528,7 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).}
 \end{frame}
 
 
-\begin{frame}{Main Results}
+\begin{frame}{Our Main Results}
    \begin{theorem}<2->
         There exists deterministic,  budget feasible, individually rational and truthful mechanism for
         EDP which runs in polynomial time. Its
@@ -737,13 +737,62 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause
 \end{frame}
 \end{comment}
 
-\section{Extensions \& Generalization}
+\section{Generalization}
 
 \begin{frame}{Outline}
     \tableofcontents[currentsection]
 \end{frame}
 
-\begin{frame}{Generalization}
+\begin{frame}{Towards More General ML Tasks}
+   \begin{center}
+        \includegraphics<1>[scale=0.4]{st2.pdf}
+        \includegraphics<2>[scale=0.4]{st3.pdf}
+        \includegraphics<3>[scale=0.4]{st4.pdf}
+        \includegraphics<4-5>[scale=0.4]{st25.pdf}
+        \includegraphics<6->[scale=0.4]{st26.pdf}
+    \end{center}
+
+    \begin{overprint}
+        \onslide<1>
+		\begin{center}$N$ experiment subjects\end{center}
+       	\onslide<2>
+            \begin{center}
+                $x_i\in \Omega$: public features
+            \end{center}
+        \onslide<3>
+            \begin{center}
+                $y_i\in \reals$: private data 
+            \end{center}
+        \onslide<4-5>
+             \begin{center}
+                \textbf{Hypothesis.}  There exists $h:\Omega\to \reals$ s.t.
+ %   \begin{displaymath}
+        $y_i =  h(x_i) + \varepsilon_i,$ %\quad
+	where $\varepsilon_i$ are independent.
+	\visible<5>{Examples: Logistic Regression, LDA, SVMs, \etc}
+  % \end{displaymath}
+		\end{center}
+%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ 
+            %\end{center}
+	    \onslide<6>
+	    \begin{center}
+		Experimenter {\tt E} wishes to learn $h$, and has a prior distribution over $$\mathcal{H}=\{\text{mappings from }\Omega\text{ to }\reals\}.$$ 
+	    \end{center}
+    \onslide<7->\begin{center}
+\vspace*{-0.5cm}
+%    \begin{block}
+%{Value function: Information gain}
+        \begin{displaymath}
+            V(S) = H(h) - H(h\mid y_i,i\in S),\quad S\subseteq[N]
+        \end{displaymath}
+ %   \end{block}
+	\visible<8>{$V$ is submodular! [Krause and Guestrin 2009]}
+    \end{center}
+	\end{overprint}
+
+\end{frame}
+
+\begin{comment}
     \begin{itemize}
         \item Generative model: $y_i = f(x_i) + \varepsilon_i,\;i\in\mathcal{A}$
         \pause
@@ -769,18 +818,46 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause
     $V$ is \alert{submodular} $\Rightarrow$ randomized budget feasible mechanism
 \end{frame}
 
+\end{comment}
 
 \begin{frame}{Conclusion}
     \begin{itemize}
-        \item Experimental design + Auction theory = powerful framework
+        \item Experimental design + Budget Feasible Mechanisms
         \vspace{1cm}
         \pause
-        \item deterministic mechanism for the general case? other learning tasks?
+        \item Deterministic mechanism for other ML Tasks? General submodular functions?
             \vspace{1cm}
             \pause
-        \item  approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$}
+        \item  Approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$}
     \end{itemize}
 \end{frame}
+\begin{frame}{}
+\vspace{\stretch{1}}
+\begin{center}
+Thank you!
+\end{center}
+\vspace{\stretch{1}}
+\end{frame}
+
+\begin{frame}{Non-Homotropic Prior}
+Recall that:
+\begin{align*}
+V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\
+& = \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T)
+\end{align*}
+What if $R\neq I$?
+\begin{theorem}
+ There exists a truthful, poly-time, and budget feasible mechanism for the objective
+ function $V$ above. Furthermore, 
+ the algorithm computes a set $S^*$ such that:
+ \begin{displaymath}
+    OPT \leq 
+    \frac{5e-1}{e-1}\frac{2}{\mu\log(1+1/\mu)}V(S^*) + 5.1 
+\end{displaymath}
+where $\mu$ is the largest eigenvalue of $R$.
+\end{theorem}
+\end{frame}
+
 \end{document}