From d8a68c6917f5b6053117e0145f6d4d80a8bec26b Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 14 Apr 2015 15:20:19 -0400
Subject: Starting paper draft

---
 paper/sections/introduction.tex | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
 create mode 100644 paper/sections/introduction.tex

(limited to 'paper/sections/introduction.tex')

diff --git a/paper/sections/introduction.tex b/paper/sections/introduction.tex
new file mode 100644
index 0000000..bcb406f
--- /dev/null
+++ b/paper/sections/introduction.tex
@@ -0,0 +1,27 @@
+Let $\Omega$ be the universe of elements and $f$ a function defined on subsets
+of $\Omega$: $f : S \in 2^{[\Omega]} \mapsto f(S) \in \mathbb{R}$. Let $K$ be a
+collection of sets of $2^{[\Omega]}$, which we call \emph{constraints}. Let
+$S^*_K$ be any solution to $\max_{S \in K} f(S)$, which we will also denote by
+$S^*$ when there is no ambiguity. Let $L$ be the problem size, which is often
+(but not always) equal to $|\Omega|$.
+
+In general, we say we can efficiently optimize a function $f$ under constraint
+$K$ when we have a polynomial-time algorithm making adaptive value queries to
+$f$,which returns a set $S$ such that $S \in K$ and $f(S) \geq \alpha f(S^*)$
+with high probability and $\alpha$ an absolute constant.
+
+Here, we consider the scenario where we cannot make adaptive value queries, and
+in fact, where we cannot make queries at all! Instead, we suppose that we
+observe a polynomial number of set-value pairs $(S, f(S))$ where $S$ is taken
+from a known distribution $D$. We say we can efficiently \emph{passively
+optimize} $f$ under distribution $D$ or $D-$optimize $f$ under constraints $K$
+when, after observing ${\cal O}(L^c)$ set-value pairs from $D$ where $c > 0$ is
+an absolute constant, we can return a set $S$ such that $S \in K$ and $f(S)
+\geq \alpha f(S^*)$ with high probability and $\alpha$ an absolute constant.
+
+In the case of \emph{passive} observations of set-value pairs under a
+distribution $D$ for a function $f$, recent research has focused on whether we
+can efficiently and approximately \emph{learn} $f$. This was formalized in the
+PMAC model from \cite{balcan2011learning}. When thinking about passive
+optimization, it is necessary to understand the link between being able to
+ $D-PMAC$ learn $f$ and being able to $D-$optimize $f$.
-- 
cgit v1.2.3-70-g09d2


From ead8ef85b50848f078a360b040f59ea962821cb4 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 14 Apr 2015 16:46:34 -0400
Subject: Sketch of the introduction

---
 paper/sections/introduction.tex | 81 +++++++++++++++++++++++++++--------------
 paper/sections/negative.tex     | 30 +++++++++++++++
 2 files changed, 84 insertions(+), 27 deletions(-)

(limited to 'paper/sections/introduction.tex')

diff --git a/paper/sections/introduction.tex b/paper/sections/introduction.tex
index bcb406f..6eda59d 100644
--- a/paper/sections/introduction.tex
+++ b/paper/sections/introduction.tex
@@ -1,27 +1,54 @@
-Let $\Omega$ be the universe of elements and $f$ a function defined on subsets
-of $\Omega$: $f : S \in 2^{[\Omega]} \mapsto f(S) \in \mathbb{R}$. Let $K$ be a
-collection of sets of $2^{[\Omega]}$, which we call \emph{constraints}. Let
-$S^*_K$ be any solution to $\max_{S \in K} f(S)$, which we will also denote by
-$S^*$ when there is no ambiguity. Let $L$ be the problem size, which is often
-(but not always) equal to $|\Omega|$.
-
-In general, we say we can efficiently optimize a function $f$ under constraint
-$K$ when we have a polynomial-time algorithm making adaptive value queries to
-$f$,which returns a set $S$ such that $S \in K$ and $f(S) \geq \alpha f(S^*)$
-with high probability and $\alpha$ an absolute constant.
-
-Here, we consider the scenario where we cannot make adaptive value queries, and
-in fact, where we cannot make queries at all! Instead, we suppose that we
-observe a polynomial number of set-value pairs $(S, f(S))$ where $S$ is taken
-from a known distribution $D$. We say we can efficiently \emph{passively
-optimize} $f$ under distribution $D$ or $D-$optimize $f$ under constraints $K$
-when, after observing ${\cal O}(L^c)$ set-value pairs from $D$ where $c > 0$ is
-an absolute constant, we can return a set $S$ such that $S \in K$ and $f(S)
-\geq \alpha f(S^*)$ with high probability and $\alpha$ an absolute constant.
-
-In the case of \emph{passive} observations of set-value pairs under a
-distribution $D$ for a function $f$, recent research has focused on whether we
-can efficiently and approximately \emph{learn} $f$. This was formalized in the
-PMAC model from \cite{balcan2011learning}. When thinking about passive
-optimization, it is necessary to understand the link between being able to
- $D-PMAC$ learn $f$ and being able to $D-$optimize $f$.
+The natural “diminishing return” property of submodular functions makes them
+suitable to model many real-life scenarios. However, even when they are
+suitable as a model, it is not realistic to assume that they are entirely
+known. For example, most submodular functions depend on unknown parameters that
+have to be learned from observations.
+
+A recent line of work has focused on learning submodular functions. The
+PMAC-learnable framework formalizes what it means to learn a submodular
+function in an “overall” sense. For specific examples of submodular functions,
+results are known on how well the parameters of the function can be learned
+from observations.
+
+When the experimenter wishes to optimize the unknown submodular function, the
+well-known approximation algorithms cannot be readily applied because they rely
+on a value query oracle, which is much stronger than what the present scenario
+suggests (at best, random independent samples). The results on learning
+submodular functions also seem to be insufficient in that they are myopic to
+the ultimate use which will be made of the submodular function (optimizing).
+The experimenter experimenter only cares about learning the function to the
+extent that what he knows is sufficient to optimize it. As such, the main
+question underlying the present work is the following:
+
+\begin{center}
+    \emph{What is a good model of learning for submodular functions when the
+    ultimate goal is to be able to optimize them?}
+\end{center}
+
+We make the following contributions:
+\begin{itemize}
+    \item We show how the PMAC learning framework does not provide a satisfying
+    framework for optimizing under uncertainty. In particular, we show that
+    there are functions which are PMAC-learnable but not optimizable and
+    vice-versa.
+    \item For specific class of submodular functions, we show how to optimize
+    them under uncertainty.
+\end{itemize}
+
+\subsection{Related Work}
+
+\paragraph{Maximizing submodular functions} Vast literature on maximizing
+submodular functions under many kind of constraints. All the algorithms rely on
+some kind of oracle (e.g. value query or demand query) which is stronger than
+what we have: access to polynomially many observations coming from
+a distribution. In particular, an algorithm cannot make arbitrary (and
+certainly not adaptive) queries to the oracle.
+
+\paragraph{PMAC-learning} Interesting line of work, but oblivious to the
+ultimate goal.
+
+\paragraph{Bandits} Interesting in that it ties together learning and
+optimizing. However, it assumes that arbitrary queries can be made to an oracle
+allowing the experimenter to explore more efficiently (even though the standard
+regret benchmark means that he will incur some cost for exploring vs
+exploiting.
diff --git a/paper/sections/negative.tex b/paper/sections/negative.tex
index 2eaeb47..555aa1d 100644
--- a/paper/sections/negative.tex
+++ b/paper/sections/negative.tex
@@ -1,3 +1,33 @@
+\subsection{Model}
+
+Let $\Omega$ be the universe of elements and $f$ a function defined on subsets
+of $\Omega$: $f : S \in 2^{[\Omega]} \mapsto f(S) \in \mathbb{R}$. Let $K$ be a
+collection of sets of $2^{[\Omega]}$, which we call \emph{constraints}. Let
+$S^*_K$ be any solution to $\max_{S \in K} f(S)$, which we will also denote by
+$S^*$ when there is no ambiguity. Let $L$ be the problem size, which is often
+(but not always) equal to $|\Omega|$.
+
+In general, we say we can efficiently optimize a function $f$ under constraint
+$K$ when we have a polynomial-time algorithm making adaptive value queries to
+$f$,which returns a set $S$ such that $S \in K$ and $f(S) \geq \alpha f(S^*)$
+with high probability and $\alpha$ an absolute constant.
+
+Here, we consider the scenario where we cannot make adaptive value queries, and
+in fact, where we cannot make queries at all! Instead, we suppose that we
+observe a polynomial number of set-value pairs $(S, f(S))$ where $S$ is taken
+from a known distribution $D$. We say we can efficiently \emph{passively
+optimize} $f$ under distribution $D$ or $D-$optimize $f$ under constraints $K$
+when, after observing ${\cal O}(L^c)$ set-value pairs from $D$ where $c > 0$ is
+an absolute constant, we can return a set $S$ such that $S \in K$ and $f(S)
+\geq \alpha f(S^*)$ with high probability and $\alpha$ an absolute constant.
+
+In the case of \emph{passive} observations of set-value pairs under a
+distribution $D$ for a function $f$, recent research has focused on whether we
+can efficiently and approximately \emph{learn} $f$. This was formalized in the
+PMAC model from \cite{balcan2011learning}. When thinking about passive
+optimization, it is necessary to understand the link between being able to
+ $D-PMAC$ learn $f$ and being able to $D-$optimize $f$.
+
 \subsection{Learnable $\nRightarrow$ Optimizable}
 
 Consider the following function:
-- 
cgit v1.2.3-70-g09d2

