1 files changed, 219 insertions, 0 deletions
diff --git a/proof.tex b/proof.tex
new file mode 100644
index 0000000..cbfa759
--- /dev/null
+++ b/proof.tex
@@ -0,0 +1,219 @@
+\documentclass{IEEEtran}
+%\usepackage{mathptmx}
+\usepackage[utf8]{inputenc}
+\usepackage{amsmath,amsthm,amsfonts}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+\newtheorem{lemma}{Lemma}
+\newtheorem{fact}{Fact}
+\newtheorem{example}{Example}
+\newtheorem{prop}{Proposition}
+\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}
+\begin{document}
+
+\section{Budget feasible mechanism}
+
+\subsection{Data model}
+\begin{itemize}
+    \item set of $n$ users $\mathcal{N} = \{1,\ldots, n\}$
+    \item each user has a public vector of features $x_i\in\mathbf{R}^d$ and some
+        undisclosed variable $y_i\in\mathbf{R}$
+    \item \textbf{Ridge regression model:}
+        \begin{itemize}
+            \item $y_i = \beta^*x_i + \varepsilon_i$
+            \item $\varepsilon_i \sim \mathcal{N}(0,\sigma^2)$, 
+                $(\varepsilon_i)_{i\in \mathcal{N}}$ are mutually independent.
+            \item prior knowledge of $\beta$: $\beta\sim\mathcal{N}(0,\kappa I_d)$
+        \end{itemize}
+\end{itemize}
+
+\subsection{Economics}
+
+\begin{itemize}
+    \item Value function:
+        \begin{align*}
+            \forall S\subset\mathcal{N},\; V(S)
+            & = \frac{1}{2}\log\det\left(I_d
+                    + \frac{\kappa}{\sigma^2}\sum_{i\in S} x_ix_i^*\right)\\
+            & = \frac{1}{2}\log\det X(S)
+        \end{align*}
+    \item each user $i$ has a cost $c_i$
+    \item the auctioneer has a budget constraint $B$
+    \item optimisation problem:
+        \begin{displaymath}
+            OPT(V,\mathcal{N}, B) = \max_{S\subset\mathcal{N}} \left\{ V(S)\,|\,
+            \sum_{i\in S}c_i\leq B\right\}
+        \end{displaymath}
+\end{itemize}
+
+\subsection{Relaxations of the value function}
+
+We say that $R_\mathcal{N}:[0,1]^n\rightarrow\mathbf{R}$ is a relaxation of the
+value function $V$ over $\mathcal{N}$ if it coincides with $V$ at binary
+points. Formally, for any $S\subset\mathcal{N}$, let $\mathbf{1}_S$ denote the
+indicator vector of $S$. $R_\mathcal{N}$ is a relaxation of $V$ over
+$\mathcal{N}$ iff:
+\begin{displaymath}
+    \forall S\subset\mathcal{N},\; R_\mathcal{N}(\mathbf{1}_S) = V(S)
+\end{displaymath}
+
+We can extend the optimisation problem defined above to a relaxation by
+extending the cost function:
+\begin{displaymath}
+    \forall \lambda\in[0,1]^n,\; c(\lambda)
+    = \sum_{i\in\mathcal{N}}\lambda_ic_i
+\end{displaymath}
+The optimisation problem becomes:
+\begin{displaymath}
+    OPT(R_\mathcal{N}, B) =
+    \max_{\lambda\in[0,1]^n}\left\{R_\mathcal{N}(\lambda)\,|\, c(\lambda)\leq B\right\}
+\end{displaymath}
+The relaxations we will consider here rely on defining a probability
+distribution over subsets of $\mathcal{N}$.
+
+Let $\lambda\in[0,1]^n$, let us define:
+\begin{displaymath}
+    P_\mathcal{N}(S,\lambda) = \prod_{i\in S}\lambda_i
+    \prod_{i\in\mathcal{N}\setminus S}(1-\lambda_i)
+\end{displaymath}
+$P_{\mathcal{N}}(S,\lambda)$ is the probability of picking the set $S$ if we select
+a subset of $\mathcal{N}$ at random by deciding independently for each point to
+include it in the set with probability $\lambda_i$ (and to exclude it with
+probability $1-\lambda_i$).
+
+We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
+\begin{itemize}
+    \item the \emph{multi-linear extension} of $V$:
+        \begin{align*}
+            F_\mathcal{N}(\lambda) 
+            & = \mathbb{E}_{S\sim P_\mathcal{N}(S,\lambda)}\big[\log\det X(S)\big]\\
+            & = \sum_{S\subset\mathcal{N}} P_\mathcal{N}(S,\lambda) V(S)\\
+            & = \sum_{S\subset\mathcal{N}} P_{\mathcal{N}}(S,\lambda) \log\det X(S)\\
+        \end{align*}
+    \item the \emph{concave relaxation} of $V$:
+        \begin{align*}
+            L_{\mathcal{N}}(\lambda) 
+            & = \log\det \mathbb{E}_{S\sim P_\mathcal{N}(S,\lambda)}\big[X(S)\big]\\
+            & = \log\det\left(\sum_{S\subset N}
+                P_\mathcal{N}(S,\lambda)X(S)\right)\\
+            & = \log\det\left(I_d
+                + \frac{\kappa}{\sigma^2}\sum_{i\in\mathcal{N}}
+                    \lambda_ix_ix_i^*\right)
+        \end{align*}
+\end{itemize}
+
+\begin{lemma}
+    The \emph{concave relaxation} $L_\mathcal{N}$ is concave\footnote{Hence
+    this relaxation is well-named!}.
+\end{lemma}
+
+\begin{proof}
+    This follows almost immediately from the concavity of the $\log\det$
+    function over symmetric positive semi-definite matrices. More precisely, if
+    $A$ and $B$ are two symmetric positive semi-definite matrices, then:
+    \begin{multline*}
+        \forall\alpha\in [0, 1],\; \log\det\big(\alpha A + (1-\alpha) B\big)\\
+        \geq \alpha\log\det A + (1-\alpha)\log\det B
+    \end{multline*}
+\end{proof}
+
+\begin{lemma}[Rounding]
+    For any feasible $\lambda\in[0,1]^n$, there exists a feasible
+    $\bar{\lambda}\in[0,1]^n$ such that at most one of its component is
+    fractional, that is, lies in $(0,1)$ and:
+    \begin{displaymath}
+        F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})
+    \end{displaymath}
+\end{lemma}
+
+\begin{proof}
+    We give a rounding procedure which given a feasible $\lambda$ with at least
+    two fractional components, returns some $\lambda'$ with one less fractional
+    component, feasible such that:
+    \begin{displaymath}
+        F(\lambda) \leq F(\lambda')
+    \end{displaymath}
+    Applying this procedure recursively yields the lemma's result.
+
+    Let us consider such a feasible $\lambda$. Let $i$ and $j$ be two
+    fractional components of $\lambda$ and let us define the following
+    function:
+    \begin{displaymath}
+        F_\lambda(\varepsilon) = F(\lambda_\varepsilon)
+        \quad\textrm{where} \quad
+        \lambda_\varepsilon = \lambda + \varepsilon\left(e_i-\frac{c_i}{c_j}e_j\right)
+    \end{displaymath}
+
+    It is easy to see that if $\lambda$ is feasible, then:
+    \begin{multline}\label{eq:convex-interval}
+        \forall\varepsilon\in\Big[\max\Big(-\lambda_i,(\lambda_j-1)\frac{c_j}{c_i}\Big), \min\Big(1-\lambda_i, \lambda_j
+        \frac{c_j}{c_i}\Big)\Big],\;\\
+            \lambda_\varepsilon\;\;\textrm{is feasible}
+    \end{multline}
+
+    Furthermore, the function $F_\lambda$ is convex, indeed:
+    \begin{align*}
+        F_\lambda(\varepsilon)
+        & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}(S',\lambda)}\Big[
+        (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\
+        & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})\\
+        & + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\
+        & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big]\\
+    \end{align*}
+    Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is:
+    \begin{multline*}
+        \frac{c_i}{c_j}\mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}(S',\lambda)}\Big[
+            V(S'\cup\{i\})+f(S'\cup\{i\})\\
+        -V(S'\cup\{i,j\})-f(S')\Big]
+    \end{multline*}
+    which is positive by submodularity of $V$. Hence, the maximum of
+    $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is
+    attained at one of its limit, at which either the $i$-th or $j$-th component of
+    $\lambda_\varepsilon$ becomes integral.
+\end{proof}
+
+\begin{lemma}
+    There exists $C>0$ such that:
+    \begin{displaymath}
+        \forall\lambda\in[0,1]^n,\; C\,L_\mathcal{N}(\lambda)\leq
+        F_\mathcal{N}(\lambda)\leq L_{\mathcal{N}}(\lambda)
+    \end{displaymath}
+\end{lemma}
+
+\begin{lemma}
+    \begin{displaymath}
+        OPT(L_\mathcal{N}, B) \leq \frac{1}{C}OPT(V,\mathcal{N},B)
+        + \max_{i\in\mathcal{N}}V(i)
+    \end{displaymath}
+\end{lemma}
+
+\begin{algorithm}
+    \caption{Budget feasible 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\frac{B}{2}\}$
+        \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\{1,\ldots,n\}\setminus S}
+                \frac{V(S\cup\{j\})-V(S)}{c_j}$
+            \EndWhile
+            \State \textbf{return} $S$
+        \EndIf
+    \end{algorithmic}
+\end{algorithm}
+\end{document}