Discussion about the generalized theorem

1 files changed, 49 insertions, 2 deletions

diff --git a/general.tex b/general.tex
index 23145ad..595023d 100644
--- a/general.tex
+++ b/general.tex
@@ -13,7 +13,7 @@ This optimization, commonly known as \emph{ridge regression}, includes an additi
 Let $\entropy(\beta)$ be the entropy of $\beta$ under this distribution, and $\entropy(\beta\mid y_S)$ the  entropy of $\beta$ conditioned on the experiment outcomes $Y_S$, for some $S\subseteq \mathcal{N}$. In this setting, a natural objective to select a set of experiments $S$ that maximizes her \emph{information gain}:
 $$ I(\beta;y_S) = \entropy(\beta)-\entropy(\beta\mid y_S). $$
 
-Assuming normal noise variables, the information gain is  equal (upto a constant) to the following value function \cite{chaloner1995bayesian}:
+Assuming normal noise variables, the information gain is  equal (up to a constant) to the following value function \cite{chaloner1995bayesian}:
 \begin{align}
 V(S)  = \frac{1}{2}\log\det(R + \T{X_S}X_S)\label{bayesianobjective}
 \end{align}
@@ -21,7 +21,54 @@ Our objective \eqref{,,,} clearly follows from \eqref{bayesianobjective} by sett
 
 Moreover, our results can be extended to the general Bayesian case, by replacing $I_d$ with the positive semidefinite matrix $R$:
 
-TODO: state theorem, discuss dependence on $\det R$.
+\thibaut{Discussion about the value function below}
+
+When there is an $R$ in the value function, it seems to make more sense to
+study the modified value function:
+\begin{displaymath}
+    \tilde{V}(S) = \frac{1}{2}\log\det(R + \T{X_S}X_S) - \frac{1}{2}\log\det R
+\end{displaymath}
+For two reasons:
+\begin{itemize}
+    \item $\tilde{V}(\emptyset) = 0$: the value function is normalized, I think
+    this assumption is needed somewhere in mechanism design.
+    \item $\tilde{V}(S) = \frac{1}{2}\log\det(I_d + R^{-1}\T{X_S}X_S)$, so we
+    can apply our result to get an $\alpha$ approximation ratio (see the value
+    of $\alpha$ below). If we take $V$ instead of $\tilde{V}$ then one can
+    write:
+    \begin{displaymath}
+        V(S) = \frac{1}{2}\log\det R + \tilde{V}(S)
+    \end{displaymath}
+    thus:
+    \begin{displaymath}
+        OPT(V) = \frac{1}{2}\log\det R + OPT(\tilde{V})
+    \end{displaymath}
+    we can find $S^*$ such that $OPT(\tilde{V}) \leq \alpha \tilde{V}(S)$, so:
+    \begin{displaymath}
+        OPT(V) = \frac{1}{2}\log\det R + \alpha\tilde{V}(S)
+    \end{displaymath}
+    But this does not give an $\alpha$ approximation ratio for $V$, because
+    $\log\det R$ can be negative. This is only an \emph{asymptotic}
+    approximation ratio\ldots.
+\end{itemize}
+
+\begin{theorem}
+ For the function $\tilde{V}$ defined above, there is a truthful, budget
+ feasible mechanism which achieves an approximation ratio of:
+ \begin{displaymath}
+    \frac{5e-1}{e-1}\frac{\log(1+\mu)}{\mu} + A
+ \end{displaymath}
+where $\mu$ is the smallest eigenvalue of $R$ (and $A$ is a constant that
+I will compute tomorrow, it should be roughly around 10).
+\end{theorem}
+
+Note that everything becomes nice when $R \geq I_d$. In this case, the smallest
+eigenvalue is larger than 1. Hence $\log\det R\geq 1$ and an approximation on
+$\tilde{V}$ gives an approximation ration on $V$ (see discussion above).
+Furthermore, we can bound $\log(1+\mu)/\mu$ by 1 and I think we fall back on
+the approximation ratio of section 2.
+
+Can we motivate that $R\geq 1$ ?
 
 \subsection{Beyond Linear Models}
 TODO: Independent noise model. Captures models such as logistic regression, classification, etc. Arbitrary prior. Show that change in the entropy is submodular (cite Krause, Guestrin).