\documentclass{acm_proc_article-sp}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsfonts}
\usepackage{algorithm}
\usepackage{algpseudocode}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{theorem}{Theorem}
\newcommand*{\defeq}{\stackrel{\text{def}}{=}}
\newcommand{\var}{\mathop{\mathrm{Var}}}
\newcommand{\condexp}[2]{\mathop{\mathbb{E}}\left[#1|#2\right]}
\newcommand{\expt}[1]{\mathop{\mathbb{E}}\left[#1\right]}
\newcommand{\norm}[1]{\lVert#1\rVert}
\newcommand{\tr}[1]{#1^*}
\newcommand{\ip}[2]{\langle #1, #2 \rangle}
\newcommand{\mse}{\mathop{\mathrm{MSE}}}
\DeclareMathOperator{\trace}{tr}
\DeclareMathOperator*{\argmax}{arg\,max}
\title{Budgeted mechanism for optimal experiment design}
\begin{document}

\maketitle

\section{Intro}

\begin{itemize}
    \item already existing field of experiment design: survey-like setup, what
    are the best points to include in your experiment? Measure of the
    usefulness of the data: variance-reduction or entropy-reduction.
    \item nowadays, there is also a big focus on purchasing data: paid surveys,
    mechanical turk, etc. that add economic aspects to the problem of
    experiment design
    \item recent advances (Singer, Chen) in the field of budgeted mechanisms
    \item we study ridge regression, very widely used in statistical learning,
    and treat it as a problem of budgeted experiment design
    \item we make the following contributions: ...
    \item extension to a more general setup which includes a wider class of
    machine learning problems
\end{itemize}

\section{Problem formulation}

\subsection{Notations}

Throughout the paper, we will make use of the following notations: if $x$ is
a (column) vector in $\mathbf{R}^d$, $x^*$ denotes its transposed (line)
vector. Thus, the standard inner product between two vectors $x$ and $y$ is
simply $x^* y$. $\norm{x}_2 = x^*x$ will denote the $L_2$ norm of $x$.

We will also often use the following order over symmetric matrices: if $A$ and
$B$ are two $d\times d$ and $B$ are two $d\times d$ real symmetric matrices, we
write that $A\leq B$ iff:
\begin{displaymath}
    \forall x\in\mathbf{R}^d,\quad
    x^*Ax \leq x^*Bx
\end{displaymath}
That is, iff $B-A$ is symmetric semi-definite positive.

This order let us define the notion of a \emph{decreasing} or \emph{convex}
matrix function similarly to their real counterparts. In particular, let us
recall that the matrix inversion is decreasing and convex over symmetric
definite positive matrices.

\subsection{Data model}

There is a set of $n$ users, $\mathcal{N} = \{1,\ldots, n\}$. Each user
$i\in\mathcal{N}$ has a public vector of features $x_i\in\mathbf{R}^d$ and an
undisclosed piece of information $y_i\in\mathbf{R}$. We assume that the data
has already been normalized so that $\norm{x_i}_2\leq 1$ for all
$i\in\mathcal{N}$.

The experimenter is going to select a set of users and ask them to reveal their
private piece of information. We are interested in a \emph{survey setup}: the
experimenter has not seen the data yet, but he wants to know which users he
should be selecting. His goal is to learn the model underlying the data. Here,
we assume a linear model:
\begin{displaymath}
    \forall i\in\mathcal{N},\quad y_i = \beta^* x_i + \varepsilon_i
\end{displaymath}
where $\beta\in\mathbf{R}^d$ and $\varepsilon_i\in\mathbf{R}$ follows a normal
distribution of mean $0$ and variance $\sigma^2$. Furthermore, we assume the
error $\varepsilon$ to be independent of the user:
$(\varepsilon_i)_{i\in\mathcal{N}}$ are mutually independent.

After observing the data, the experimenter could simply do linear regression to
learn the model parameter $\beta$. However, in a more general setup, the
experimenter has a prior knowledge about $\beta$, a distribution over
$\mathbf{R}^d$. After observing the data, the experimenter performs
\emph{maximum a posteriori estimation}: computing the point which maximizes the
posterior distribution of $\beta$ given the observations.

Here, we will assume, as it is often done, that the prior distribution is
a multivariate normal distribution of mean zero and covariance matrix $\kappa
I_d$. Maximum a posteriori estimation leads to the following maximization
problem:
\begin{displaymath}
    \beta_{\text{max}} = \argmax_{\beta\in\mathbf{R}^d} \sum_i (y_i - \beta^*x_i)^2
    + \frac{1}{\mu}\sum_i \norm{\beta}_2^2
\end{displaymath}
which is the well-known \emph{ridge regression}. $\mu
= \frac{\kappa}{\sigma^2}$ is the regularization parameter. Ridge regression
can thus be seen as linear regression with a regularization term which
prevents $\beta$ from having a large $L_2$-norm.

\subsection{Value of data}

Because the user private variables $y_i$ have not been observed yet when the
experimenter has to decide which users to include in his experiment, we treat
$\beta$ as a random variable whose distribution is updated after observing the
data.

Let us recall that if $\beta$ is random variable over $\mathbf{R}^d$ whose
probability distribution has a density function $f$ with respect to the
Lebesgue measure, its entropy is given by:
\begin{displaymath}
    \mathbb{H}(\beta) \defeq - \int_{b\in\mathbf{R}^d} \log f(b) f(b)\text{d}b
\end{displaymath}

A usual way to measure the decrease of uncertainty induced by the observation
of data is to use the entropy. This leads to the following definition of the
value of data called the \emph{value of information}:
\begin{displaymath}
    \forall S\subset\mathcal{N},\quad V(S) = \mathbb{H}(\beta)
    - \mathbb{H}(\beta\,|\,
    Y_S)
\end{displaymath}
where $Y_S = \{y_i,\,i\in S\}$ is the set of observed data.

\begin{theorem}
    Under the ridge regression model explained in section TODO, the value of data
    is equal to:
    \begin{align*}
        \forall S\subset\mathcal{N},\; V(S)
        & = \frac{1}{2}\log\det\left(I_d
            + \mu\sum_{i\in S} x_ix_i^*\right)\\
        & \defeq \frac{1}{2}\log\det A(S)
    \end{align*}
\end{theorem}

\begin{proof}

Let us denote by $X_S$ the matrix whose rows are the vectors $(x_i^*)_{i\in
S}$. Observe that $A_S$ can simply be written as:
\begin{displaymath}
    A_S  = I_d + \mu X_S^* X_S
\end{displaymath}

Let us recall that the entropy of a multivariate normal variable $B$ over
$\mathbf{R}^d$ of covariance $\Sigma I_d$ is given by:
\begin{equation}\label{eq:multivariate-entropy}
    \mathbb{H}(B) = \frac{1}{2}\log\big((2\pi e)^d \det \Sigma I_d\big)
\end{equation}

Using the chain rule for conditional entropy, we get that:
\begin{displaymath}
    V(S) = \mathbb{H}(Y_S) - \mathbb{H}(Y_S\,|\,\beta)
\end{displaymath}

Conditioned on $\beta$, $(Y_S)$ follows a multivariate normal
distribution of mean $X\beta$ and of covariance matrix $\sigma^2 I_n$. Hence:
\begin{equation}\label{eq:h1}
    \mathbb{H}(Y_S\,|\,\beta) 
    = \frac{1}{2}\log\left((2\pi e)^n \det(\sigma^2I_n)\right)
\end{equation}

$(Y_S)$ also follows a multivariate normal distribution of mean zero. Let us
compute its covariance matrix, $\Sigma_Y$:
\begin{align*}
    \Sigma_Y & = \expt{YY^*} = \expt{(X_S\beta + E)(X_S\beta + E)^*}\\
             & = \kappa X_S X_S^* + \sigma^2I_n
\end{align*}
Thus, we get that:
\begin{equation}\label{eq:h2}
    \mathbb{H}(Y_S) 
    = \frac{1}{2}\log\left((2\pi e)^n \det(\kappa X_S X_S^* + \sigma^2 I_n)\right)
\end{equation}

Combining \eqref{eq:h1} and \eqref{eq:h2} we get:
\begin{displaymath}
    V(S) = \frac{1}{2}\log\det\left(I_n+\frac{\kappa}{\sigma^2}X_S
    X_S^*\right)
\end{displaymath}

Finally, we can use Sylvester's determinant theorem to get the result.
\end{proof}

It is also interesting to the marginal contribution of a user to a set: the
increase of value induced by adding a user to an already existing set of users.
We have the following lemma.

\begin{lemma}[Marginal contribution]
    \begin{displaymath}
        \Delta_i V(S)\defeq V(S\cup\{i\}) - V(S) 
        = \frac{1}{2}\log\left(1 + \mu x_i^*A(S)^{-1}x_i\right)
    \end{displaymath}
\end{lemma}

\begin{proof}
    We have:
    \begin{align*}
        V(S\cup\{i\}) & = \frac{1}{2}\log\det A(S\cup\{i\})\\
        & = \frac{1}{2}\log\det\left(A(S) + \mu x_i x_i^*\right)\\
        & = V(S) + \frac{1}{2}\log\det\left(I_d + \mu A(S)^{-1}x_i
    x_i^*\right)\\
        & = V(S) + \frac{1}{2}\log\left(1 + \mu x_i^* A(S)^{-1}x_i\right)
    \end{align*}
    where the last equality comes from Sylvester's determinant formula.
\end{proof}

Because $A(S)$ is symmetric definite positive, the marginal contribution is
positive, which proves that the value function is set increasing. Furthermore,
it is easy to see that if $S\subset S'$, then $A(S)\leq A(S')$. Using the fact
that matrix inversion is decreasing, we see that the marginal contribution of
a fixed user is a set decreasing function. This is the \emph{submodularity} of
the value function.

\subsection{Auction}

Explain the optimization problem, why it has to be formulated as an auction
problem. Explain the goals:
\begin{itemize}
    \item truthful
    \item individually rational
    \item budget feasible
    \item has a good approximation ratio
\end{itemize}

\section{Main result}

Explain:
\begin{itemize}
    \item the mechanism uses the greedy heuristic
    \item we know that the maximum of greedy and meatiest guy is a good
    approximation, but not incentive compatible
    \item instead compare the value of the meatiest guy to $L(x^*)$ (introduce
    $L(x^*)$ which can be easily computed and is not too far from the greedy
    value
\end{itemize}

\begin{algorithm}\label{mechanism}
    \caption{Mechanism for ridge regression}
    \begin{algorithmic}[1]
    \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
    \State $x^* \gets \argmax_{x\in[0,1]^n} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
                                    \,|\, c(x)\leq B\}$
        \Statex
        \If{$L(x^*) < CV(i^*)$}
            \State \textbf{return} $\{i^*\}$
        \Else
            \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$
            \State $S \gets \emptyset$
            \While{$c_i\leq \frac{B}{2}\frac{V(S\cup\{i\})-V(S)}{V(S\cup\{i\})}$}
                \State $S \gets S\cup\{i\}$
                \State $i \gets \argmax_{j\in\mathcal{N}\setminus S}
                \frac{V(S\cup\{j\})-V(S)}{c_j}$
            \EndWhile
            \State \textbf{return} $S$
        \EndIf
    \end{algorithmic}
\end{algorithm}

\begin{theorem}
    The mechanism is truthful, individually rational, budget feasible.
    Furthermore, choosing:
    \begin{multline*}
        C = C^* =  \frac{5e-1 + C_\mu(2e+1)}{2C_\mu(e-1)}\\
        + \frac{\sqrt{C_\mu^2(1+2e)^2
        + 2C_\mu(14e^2+5e+1) + (1-5e)^2}}{2C_\mu(e-1)}
    \end{multline*}
    we get an approximation ratio of:
    \begin{multline*}
        1 + C^* = \frac{5e-1 + C_\mu(4e-1)}{2C_\mu(e-1)}\\
        + \frac{\sqrt{C_\mu^2(1+2e)^2
        + 2C_\mu(14e^2+5e+1) + (1-5e)^2}}{2C_\mu(e-1)}
    \end{multline*}
\end{theorem}

\section{General setup}

\section{Conclusion}

\end{document}