From 369835fe19615a2e78c3b45bf76cb7b11ada36cc Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 17 Jul 2012 13:35:29 -0700
Subject: Add technical lemma

---
 notes.tex | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 79 insertions(+)

(limited to 'notes.tex')

diff --git a/notes.tex b/notes.tex
index c84f989..8dc2c7b 100644
--- a/notes.tex
+++ b/notes.tex
@@ -3,6 +3,7 @@
 \usepackage{amsmath,amsthm,amsfonts}
 \usepackage{comment}
 \newtheorem{lemma}{Lemma}
+\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]}
@@ -13,6 +14,84 @@
 \newcommand{\trace}{\mathop{\mathrm{tr}}}
 \begin{document}
 
+
+\section{pomme}
+
+In this section, we will consider that we are given a \emph{universe}
+set $U$ such that all the sets we consider are subsets or $U$ and all
+functions defined on sets are defined on the power set of $U$,
+$\mathfrak{P}(U)$.
+
+A function $f$ defined on $\mathfrak{P}(U)$ will be said
+\emph{increasing} if it is increasing with regards to inclusion, that
+is:
+\begin{displaymath}
+  \forall\,S\subseteq T,\quad f(S)\leq f(T)
+\end{displaymath}
+A \emph{decreasing} function on $\mathfrak{P}(U)$ is defined similarly.
+
+\begin{prop}
+  Let $R:\mathbf{R}\rightarrow \mathbf{R}$ be a decreasing concave
+  function and $f:\mathfrak{P}(U)\rightarrow\mathbf{R}$ be a
+  decreasing submodular function, then the composed function $R\circ
+  f$ is increasing and supermodular.
+\end{prop}
+
+\begin{proof}
+  The increasingness of $R\circ f$ follows immediately from the
+  decreasingness of $R$ and $f$.
+  
+  For the supermodularity, let $S$ and $T$ be two sets such that
+  $S\subseteq T$. By decreasingness of $f$, we have:
+  \begin{displaymath}
+    \forall\,V,\quad f(T)\leq f(S)\quad\mathrm{and}\quad f(T\cup V)\leq f(S\cup V)
+  \end{displaymath}
+  
+  Thus, by concavity of $R$:
+  \begin{displaymath}\label{eq:base}
+    \forall\,V,\quad\frac{R\big(f(S)\big)-R\big(f(S\cup V)\big)}{f(S)-f(S\cup V)}
+    \leq\frac{R\big(f(T)\big)-R\big(f(T\cup V)\big)}{f(T)-f(T\cup V)}
+  \end{displaymath}
+  
+  $f$ is decreasing, so multiplying this last inequality by
+  $f(S)-f(S\cup V)$ and $f(T)-f(T\cup V)$ yields:
+  \begin{multline}
+    \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(T)-f(T\cup V)\big)\\
+    \leq \Big(R\big(f(T)\big)-R\big(f(T\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)
+  \end{multline}
+
+  $f$ is submodular, so:
+  \begin{displaymath}
+    f(T\cup V)-f(T)\leq f(S\cup V) - f(S)
+  \end{displaymath}
+  
+  $R\circ f$ is increasing, so:
+  \begin{displaymath}
+    R\big(f(S)\big)-R\big(f(S\cup V)\big)\leq 0
+  \end{displaymath}
+
+  By combining the two previous inequalities, we get:
+    \begin{multline*}
+    \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)\\
+    \leq \Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(T)-f(T\cup V)\big)
+  \end{multline*}
+
+  Injecting this last inequality into \eqref{eq:base} gives:
+  \begin{multline*}
+    \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)\\
+    \leq \Big(R\big(f(T)\big)-R\big(f(T\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)
+  \end{multline*}
+
+  Dividing left and right by $f(S)-f(S\cup V)$ yields:
+  \begin{displaymath}
+    \forall V,\quad R\big(f(S)\big)-R\big(f(S\cup V)\big)
+    \leq R\big(f(T)\big)-R\big(f(T\cup V)\big)
+  \end{displaymath}
+  which is exactly the supermodularity of $R\circ f$.
+\end{proof}
+
+
+
 \section{Understanding the recommender system}
 
 \subsection{General problem}
-- 
cgit v1.2.3-70-g09d2

