From ead8ef85b50848f078a360b040f59ea962821cb4 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Tue, 14 Apr 2015 16:46:34 -0400 Subject: Sketch of the introduction --- paper/sections/introduction.tex | 81 +++++++++++++++++++++++++++-------------- 1 file changed, 54 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. -- cgit v1.2.3-70-g09d2