\documentclass{beamer}
\usepackage[utf8x]{inputenc}
\usepackage[greek,english]{babel}
\usepackage[LGR,T1]{fontenc}
\usepackage{amsmath}
\usepackage{algpseudocode,algorithm}
\DeclareMathOperator*{\argmax}{arg\,max}
\usetheme{Boadilla}
\usecolortheme{beaver}
\title[Budget Feasible Mechanisms for Experimental Design]{Budget Feasible Mechanisms for Experimental Design}
\author{xx\\ Joint work with yy and zz}
\institute[]{}
\setbeamercovered{transparent}

\AtBeginSection[]
{
\begin{frame}<beamer>
\frametitle{Outline}
\tableofcontents[currentsection]
\end{frame}
}

\begin{document}

\begin{frame}
\maketitle
\end{frame}

\begin{frame}
\tableofcontents
\end{frame}

\section{Experimental Design}
\begin{frame}{Experimental Design}
    An experimenter is about to conduct an experiment with users. 
    \begin{itemize}
        \item $n$ users
        \item $x_i\in\mathbb{R}^d$: public features of user $i$
        \item $c_i\in\mathbb{R}^+$: cost of user $i$ for taking part in the experiment
    \end{itemize}

    When paid $c_i$, user $i$ reveals $y_i$:
    \begin{displaymath}
        y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\;
        \varepsilon_i\sim\mathcal{N}(0,\sigma^2)
    \end{displaymath}
    $\beta$ is \alert{unknown} to the experimenter.

    \begin{block}{}
    \alert{Question:} budget constraint $B$, which users to pick to learn $\beta$ as
    well as possible without spending more than $B$?
    \end{block}
\end{frame}

\begin{frame}{Evaluation criterion}
    \begin{block}{}
        \alert{Question:} How to measure the helpfulness of a set of users $S$ in learning $\beta$?
    \end{block}
    
    \vspace{0.5cm}

    Bayesian approach:
    \begin{itemize}
        \item \emph{a priori} knowledge: prior distribution over $\beta$
        \item the entropy of $\beta$, $H(\beta)$ measures the uncertainty of the experimenter
        \item after observing $Y_S = \{y_i,\; i\in S\}$, uncertainty becomes $H(\beta\mid Y_S)$
    \end{itemize}

    \vspace{0.5cm}

    The value of $S$ is the \alert{entropy reduction}:
    \begin{displaymath}
        V(S) = H(\beta) - H(\beta\mid Y_S)
    \end{displaymath}
\end{frame}

\begin{frame}{Value function}
    Gaussian linear model:
    \begin{displaymath}
        y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\;
        \varepsilon_i\sim\mathcal{N}(0,\sigma^2)
    \end{displaymath}
    
    Typical prior distribution $\beta\sim\mathcal{N}(0,\tau I_d)$
   
    \vspace{0.5cm}

    \begin{block}{}
        Under the Gaussian linear model and Gaussian prior distribution:
        \begin{displaymath}
            V(S) = \log\det\Big(I_d + \lambda\sum_{i\in S}x_i x_i^T \Big)
        \end{displaymath}
    \end{block}

    \vspace{0.5cm}

    \alert{Remark:} $V$ can be computed efficiently using a Cholesky decomposition
\end{frame}

\section{Non-strategic case}
\begin{frame}{Optimization Problem}
    \begin{block}{P1}
        \begin{align*}
            &\text{maximize}\; V(S) = \log\det\Big(I_d + \lambda\sum_{i\in S}x_i x_i^T \Big)\\
            &\text{subject to}\; \sum_{i\in S}c_i\leq B\quad\text{(Knapsack constraint)}
        \end{align*}
    \end{block}

    \onslide<2->
    Good news:

    $V$ is submodular (diminishing return):
    \begin{displaymath}
        \forall S\subseteq T\, \forall i,\; V(S\cup\{i\}) - V(S)\geq
        V(T\cup\{i\}) - V(T)
    \end{displaymath}

    \onslide<3->
    Bad news:

    Maximizing a submodular function under a knapsack constraint is NP-hard (even
    in the specific case of $\log\det$)
\end{frame}

\begin{frame}{Approximation}
    \begin{definition}[Approximation ratio]
        Let $OPT$ denote the optimal solution to P1, $S$ is an $\alpha$-approximation
        if:
        \begin{displaymath}
            V(OPT)\leq \alpha V(S)
        \end{displaymath}
    \end{definition}

    \vspace{0.5cm}

    \begin{theorem}[Sviridenko]
        \begin{enumerate}
            \item There is an algorithm which returns a set $S$ which is a $\frac{e}{e-1}$-approximation
            \item No algorithm can do better unless P=NP
        \end{enumerate}
    \end{theorem}

    \vspace{0.5cm}

    The algorithm is a combination of an enumeration method and a greedy heuristic.
\end{frame}

\begin{frame}{Greedy algorithm}
    \begin{block}{Greedy($V$, $B$)}  
        \begin{algorithmic}
            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
            \State $S \gets \emptyset$
            \While{$c_i\leq B - \sum_{j\in S} c_j$}
                \State $S \gets S\cup\{i\}$
                \State $i \gets \argmax_{1\leq j\leq n}
                \frac{V(S\cup\{j\})-V(S)}{c_j}$
            \EndWhile
            \State \textbf{return} $S$
        \end{algorithmic}
    \end{block}

    \vspace{0.5cm}

    \begin{lemma}
        Greedy has an \alert{unbounded} approximation ratio.
    \end{lemma}
\end{frame}

\begin{frame}
    \begin{block}{MaxGreedy}
        \begin{algorithmic}
            \State $i^* \gets \argmax_{1\leq j\leq n} V(j)$
            \State $S \gets$ Greedy($V$, $B$)
            \If{$V(i^*)\geq V(S)$}
                \State \textbf{return} $\{i^*\}$
            \Else
                \State \textbf{return} $S$
            \EndIf
        \end{algorithmic}
    \end{block}

    \vspace{0.5cm}

    \begin{lemma}
        MaxGreedy is a $\frac{5e}{e-1}$ approximation
    \end{lemma}
\end{frame}

\section{Strategic case}

\begin{frame}{Reverse auction}

    \alert{Problem:} In real life, user are strategic agents. They lie about their costs.
    This is a \alert{reverse auction}: the experimenter wants to buy data
    from users.

    \vspace{0.5cm}

    \alert{Goal:} Design an auction mechanism:
    \begin{itemize}
        \item a selection rule $s: (c_1,\ldots,c_n) \mapsto (s_1,\ldots,s_n)$,
            $s_i\in\{0,1\}$
        \item a payment rule $p: (c_1,\ldots,c_n) \mapsto (p_1,\ldots,p_n)$,
            $p_i\in\mathbb{R}^+$
    \end{itemize}

    \vspace{0.5cm}

    As usual in auction mechanism design, we want payments to be:
    \begin{itemize}
        \item individually rational: $p_i\geq c_i$
        \item truthful: reporting one's true cost is a dominant strategy
        \item normalized: $s_i=0$ implies $p_i=0$
    \end{itemize}
\end{frame}

\begin{frame}{Optimization problem for budget feasible auctions}
    \begin{block}{P2}
        \begin{align*}
            &\text{maximize}\; V\big(s(c_1,\ldots,c_n)\big) = \log\det\Big(I_d + \lambda\sum_{i\in S}x_i x_i^T \Big)\\
            &\text{subject to}\; \sum_{i\in S}\alert{p_i}\leq B\quad\text{(budget feasible)}
        \end{align*}
        where the payments are further constrained to be individually rational, truthful
        and normalized
    \end{block}

    \vspace{1cm}

    This is again NP-hard $\Rightarrow$ we seek good approximation ratios
\end{frame}

\begin{frame}{Myerson's theorem}
    \begin{theorem}[Myerson]
        Let $(s, p)$ be a mechanism. If:
        \begin{itemize}
            \item $s$ is \alert{monotonic}: if $c_i\leq c_i'$ then $s_i \geq s_i'$
            \item users are paid \alert{threshold payments}: $p_i = \inf\{c_i':i\notin s(c_i',c_{-i})\}$
        \end{itemize}
        Then, the mechanism is individually rational and truthful.
    \end{theorem}

    \vspace{1cm}

    \alert{Consequence:} It suffices to find a monotonic selection rule such that
    the threshold payments are within the budget constraint.
\end{frame}

\begin{frame}{Main result}
    \begin{theorem}
        There is a budget feasible, individually rational and truthful mechanism for
        the experimental design problem which runs in polynomial time. Its
        approximation ratio is:
        \begin{displaymath}
        \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)}
        \simeq 12.98 
        \end{displaymath}
    \end{theorem}
\end{frame}


\begin{frame}{Greedy revisited}
    \begin{block}{Greedy\only<2>{\alert{'}}($V$, $B$)}  
        \begin{algorithmic}
            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
            \State $S \gets \emptyset$
            \While{$c_i\leq \only<1>{B - \sum_{j\in S} c_j} \only<2->{\alert{\frac{B}{2}\frac{V(S\cup\{i\})-V(S)}{V(S\cup\{i\})}}}$}
                \State $S \gets S\cup\{i\}$
                \State $i \gets \argmax_{1\leq j\leq n}
                \frac{V(S\cup\{j\})-V(S)}{c_j}$
            \EndWhile
            \State \textbf{return} $S$
        \end{algorithmic}
    \end{block}

    \vspace{1cm}

    \alert{Problem:} The threshold payments are not budget feasible.
\end{frame}

\begin{frame}{MaxGreedy revisited}
    \begin{block}{MaxGreedy}
        \begin{algorithmic}
            \State $i^* \gets \argmax_{1\leq j\leq n} V(j)$
            \State $S \gets$ Greedy\alert{'}($V$, $B$)
            \If{$V(i^*)\geq \only<1>{V(S)}\only<2,3>{\alert{OPT_{-i^*}}}\only<4>{\alert{OPT'_{i^*}}}$}
                \State \textbf{return} $\{i^*\}$
            \Else
                \State \textbf{return} $S$
            \EndIf
        \end{algorithmic}
    \end{block}

    \vspace{0.5cm}

    \only<1>{\alert{Problem:} MaxGreedy is not monotonic}

    \only<2,3>{\alert{Solution 1:} use $OPT_{-i^*} = \max_{S, i^*\notin S}\{V(S) \mid \sum_{j\in S} c_j\}$. Gives a 8.34 approximation}

    \only<3>{\alert{Problem:} $OPT_{-i^*}$ cannot be computed in polynomial time}

    \only<4->{\alert{Solution 2:} use a concave relaxation:
    \begin{displaymath}
        OPT'_{i^*} = \max_{\lambda\in[0, 1]^n, \lambda_{i^*} = 0} L(\lambda)
        = \max_{\lambda\in[0, 1]^n, \lambda_{i^*} = 0}\log\det\big(I_d + \sum_{i=1}^n \lambda_i x_ix_i^T\big)
    \end{displaymath}
    }
\end{frame}

\begin{frame}{Proof}
\begin{itemize}
    \item Monotonicity: OK
    \pause
    \item Budget feasibility: OK
    \pause
    \item Approximation ratio: what do we lose by using a concave relaxation? Powerful
        method, \alert{pipage rounding} [Ageev, Sviridenko]
    \begin{itemize}
        \item let's introduce $F(\lambda) = \mathbb{E}\Big[\log\det(I_d+\sum_{i=1}^n \mu_ix_ix_i^T)\Big]$, $\mu_i\sim\mathcal{B}(\lambda_i)$
        \item $L(\lambda) \leq 2 F(\lambda)$ (technical lemma)
        \item $F$ is well-behaved: $\lambda$ can be round to a binary vector $\bar{\lambda}$ s.t $F(\lambda)\leq F(\bar{\lambda})$ 
        \item $OPT'_{-i^*}\leq 2 OPT_{-i^*} + V(i^*)$ 
        \item we can conclude by using the approximation ratio for $OPT_{-i^*}$
    \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Conclusion}
    \begin{itemize}
        \item Experimental design + Auction theory = powerful framework when working with user data
        \vspace{1cm}
        \item Can we extend this to learning tasks beyond linear regression?
            \vspace{1cm}
        \item $\simeq \alert{13}$ approximation ratio. Lower bound: \alert{$2$}
    \end{itemize}
\end{frame}
\end{document}