more proof stuff

1 files changed, 82 insertions, 36 deletions

diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex
index 98de9c2..cc8a1a6 100644
--- a/slides/BudgetFeasibleExperimentalDesign.tex
+++ b/slides/BudgetFeasibleExperimentalDesign.tex
@@ -3,7 +3,7 @@
 \usepackage[greek,english]{babel}
 \usepackage[LGR,T1]{fontenc}
 \usepackage{amsmath,bbm,verbatim}
-\usepackage{algpseudocode,algorithm}
+\usepackage{algpseudocode,algorithm,bbding}
 \usepackage{graphicx}
 \DeclareMathOperator*{\argmax}{arg\,max}
 \DeclareMathOperator*{\argmin}{arg\,min}
@@ -12,7 +12,7 @@
 
 \title[EconCS Seminar]{Budget Feasible Mechanisms for Experimental Design}
 \author[Horel, Ioannidis, Muthu]{Thibaut Horel$^*$, \alert{Stratis Ioannidis}$^\dagger$, and S. Muthukrishnan$^\ddagger$}
-\institute[]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University}
+\institute[Technicolor]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University}
 \setbeamercovered{transparent}
 \setbeamertemplate{navigation symbols}{}
 %\AtBeginSection[]
@@ -84,17 +84,17 @@
         \item Linear Regression 
 	    \pause
 	    \begin{itemize}
-                \item We present a \alert{deterministic, poly-time}, truthful, budget feasible, 12.98-appriximate mechanism. 
-		\pause
-		\vspace*{0.5cm}
-		\item Previous results:
-			\begin{itemize}
-			\item  \alert{Randomized}, poly-time, universally truthful,  7.91-approximate mechanism. [Singer 2010, Chen 2011]
-			\item Deterministic, \alert{exponential time}, truthful mechanism. [Chen 2011] 
-			\end{itemize}
+                \item We present a \alert{deterministic, poly-time}, truthful, budget feasible, 12.98-approximate mechanism. 
+	%	\pause
+	%	\vspace*{0.5cm}
+	%	\item Previous results:
+	%		\begin{itemize}
+	%		\item  \alert{Randomized}, poly-time, universally truthful,  7.91-approximate mechanism. [Singer 2010, Chen 2011]
+	%		\item Deterministic, \alert{exponential time}, truthful mechanism. [Chen 2011] 
+	%		\end{itemize}
 	    \end{itemize}
             \pause
-	\vspace*{1cm}
+	    \vspace*{1cm}
         \item Generalization to other machine learning tasks. 
    \end{itemize}
 \end{frame}
@@ -133,7 +133,7 @@
             \end{center}
             \onslide<3>
             \begin{center}
-                $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, etc.)
+                $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, movie rating, etc.)
             \end{center}
             \onslide<4>
              %\begin{}
@@ -157,7 +157,7 @@
             \end{center}
 	    \onslide<8-9>
 	    \begin{center}
-		\E\ pays subjects\visible<9>{; $y_i$ is revealed only if $i$ is paid.}
+		\E\ pays subjects\visible<9>{; $y_i$ is revealed only if $i$ is paid at least $c_i$.}
 	    \end{center} 
 	    \onslide<10>
 	    \begin{center}{\tt E}  estimates ${\beta}$  through \emph{ridge regression}.
@@ -173,7 +173,7 @@ Goal: Determine (a) who to pay and (b) how much,\\ so that $\hat{\beta}$ is as a
 %\end{enumerate}
 	    \end{center}
 	    \onslide<12->
-	    \begin{center}Users are \alert{strategic}: the may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments)
+	    \begin{center}Users are \alert{strategic}: they may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments)
 	    \end{center}
 	    
         \end{overprint}
@@ -227,9 +227,9 @@ Let $S\subset [N]$ be the set of experiments performed, and
         \item computationally efficient: polynomial time
             \pause
             \vspace{0.2cm}
-        \item constant approximation: $V(OPT) \leq \alpha V(S)$  with:
+        \item approximation: $OPT \leq \alpha V(S)$  with:
             \begin{displaymath}
-                OPT = \arg\max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\}
+                OPT = \max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\}
             \end{displaymath}
     \end{itemize}
 \end{frame}
@@ -422,11 +422,11 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).}
         \item \alert{Deterministic, poly-time}, truthful mechanisms for specific submodular functions $V$ :
             \vspace{0.3cm}
             \begin{itemize}
-                \item Knapsack: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011]
+                \item \textsc{Knapsack}: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011]
                     \vspace{0.3cm}
                 \item Matching: 7.37 [Singer, 2010]
                     \vspace{0.3cm}
-                \item Coverage: 31 [Singer, 2012]
+                \item \textsc{Coverage}: 31 [Singer, 2012]
                     \vspace{0.3cm}
             \end{itemize}
     \end{itemize}
@@ -530,7 +530,7 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).}
 
 \begin{frame}{Our Main Results}
    \begin{theorem}<2->
-        There exists deterministic,  budget feasible, individually rational and truthful mechanism for
+        There exists a deterministic,  budget feasible, individually rational and truthful mechanism for
         EDP which runs in polynomial time. Its
         approximation ratio is:
         \begin{displaymath}
@@ -577,7 +577,7 @@ Stop when budget $B$ is reached.
     \begin{block}{Allocation $S$:}
         \begin{itemize}
         \item Let $i^* = \arg\max_i V(\{i\})$
-        \item Compute $S_G$ greedily over $[N]\setminus i^*$
+        \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$
 	\item Return $S$:
 		\begin{itemize}
 		\item Selected at random between $i^*$ and $S_G$
@@ -600,10 +600,10 @@ Stop when budget $B$ is reached.
     \begin{block}{Allocation $S$}
         \begin{itemize}
         \item Find $i^* = \arg\max_i V(\{i\})$
-        \item Compute $S_G$ greedily
+        \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$
         \item Return:
             \begin{itemize}
-                \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{V(OPT_{-i^*})}$ 
+                \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{OPT_{-i^*}}$ 
                 \item $S_G$ otherwise
             \end{itemize}
         \end{itemize}
@@ -616,9 +616,10 @@ Stop when budget $B$ is reached.
 \item budget-feasible
 \item 8.34-approximate [Chen \etal\ 2011].
 \end{itemize}
-    \vspace{0.5cm}
-    \pause
-    \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute
+}   
+\uncover<3->
+{ \vspace{0.5cm}
+    \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute\ldots
 }
 \end{frame}
 
@@ -643,7 +644,7 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause
             \begin{itemize}
 		   \item computable in polynomial time
                     \pause
-                \item close to $V(OPT_{-i^*})$
+                \item close to $OPT_{-i^*}$
 		    \pause
 		\item monotone in costs $c$
             \end{itemize}
@@ -651,13 +652,55 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause
 	\pause
         \begin{column}{0.45\textwidth}
    	\begin{itemize}
-                \item Knapsack (Chen \etal, 2011)
-                \item Coverage (Singer, 2012)
+                \item \textsc{Knapsack} (Chen \etal, 2011)
+                \item \textsc{Coverage} (Singer, 2012)
             \end{itemize}
 	\end{column}
        \end{columns}
 \end{frame}
 
+\begin{frame}{Finding a Relaxation}
+\alt<1>{\begin{block}{Submodular Maximization}
+\vspace*{-0.4cm}		
+\begin{align*}
+			\text{Maximize}\qquad &V(S) \\
+			\text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B
+\end{align*}
+\end{block}
+}
+{
+\begin{block}{Multilinear Relaxation}
+\vspace*{-0.4cm}		
+\begin{align*}
+			\text{Maximize}\qquad &F(\lambda)=\mathbb{E}_{\lambda}[V(S)] = \textstyle\sum_{S\subset [N]}V(S)\prod_{i\in S}\lambda_i\prod_{i\notin S}(1-\lambda_i)\\
+			\text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\lambda_i c_i\leq B,\\& \lambda_i\in[0,1], i\in [N]
+\end{align*}
+\end{block}
+}
+\medskip
+\visible<2->{Replace $V$ with expectation when $i\in[N]$ is included with probability $\lambda_i$. }\visible<3->{Let $\lambda^*$ be optimal solution. Then:}
+\bigskip
+\visible<3->{
+\begin{itemize} 
+\item<3->$F(\lambda^*)$ is monotone in $c$.
+\item<4->$F(\lambda^*)$ is close to $OPT$ under a certain condition on $F$ ($\epsilon$-convexity). Can be shown through \alert{pipage rounding}  [Ageev and Sviridenko 2004].\\
+\end{itemize}}
+\bigskip
+\visible<5->{Good relaxation candidate, if it can be computed in poly-time.}
+\visible<6->{
+\begin{center}
+\begin{tabular}{lc}
+ \textsc{Knapsack} &\Checkmark
+\end{tabular}\qquad
+\begin{tabular}{lc}
+ \textsc{Coverage} &\XSolidBrush\\
+ EDP &\XSolidBrush
+\end{tabular}
+\end{center}
+}
+\end{frame}
+
+
 \begin{frame}{Main Technical Contribution: Relaxation for EDP}
 \alt<1>{\begin{block}{\textsc{EDP} }
 \vspace*{-0.4cm}		
@@ -678,20 +721,23 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause
 }
 \pause
 \pause
+$L(\lambda^*)$ is:
     \begin{itemize}
-        \item Poly-time: $L$ is convex and self-concordant
+	\item Monotone in $c$
+\pause
+        \item Poly-time: $L$ is convex and self-concordant (Boyd\&Vanderberghe)
             \pause
-            \vspace{0.5cm}
-        \item Close to $V(OPT)$:\pause
-            \vspace{0.5cm}
+          %  \vspace{0.5cm}
+        \item Close to $OPT$:\pause
+           % \vspace{0.5cm}
             \begin{block}{Technical Lemma}
                 \begin{displaymath}
-                    L^* \leq 2 V(OPT) + V(\{i^*\})
+                    L(\lambda^*) \leq 2 OPT + V(\{i^*\})
                 \end{displaymath}
             \end{block}
     \end{itemize}
    \pause
-    Proved using \emph{pipage rounding} [Ageev and Sviridenko 2004]
+    Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004]
 \end{frame}
 
 \begin{comment}
@@ -711,8 +757,8 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause
         \pause
         \begin{column}{0.45\textwidth}
             \begin{itemize}
-                \item Knapsack (Chen et al., 2011)
-                \item Coverage (Singer, 2012)
+                \item \textsc{Knapsack} (Chen et al., 2011)
+                \item \textsc{Coverage} (Singer, 2012)
             \end{itemize}
         \end{column}
     \end{columns}