slightly cleaning up section on coverage function"

1 files changed, 13 insertions, 4 deletions

diff --git a/brainstorm/results.tex b/brainstorm/results.tex
index 5ca05f2..0b37049 100644
--- a/brainstorm/results.tex
+++ b/brainstorm/results.tex
@@ -632,7 +632,7 @@ $${\cal C} \equiv \{c : {\cal A} \mapsto \mathbb{R}^+ : \forall S \subset {\cal
 A}, c(S) = w(\cup_{S_i \in S} S_i) \text{ and } w(U) = k \}$$
 
 Note that any coverage function from this family of coverage functions is
-constant almost everywhere, equal to $w(x_1)+w(x_2) = k$: 
+constant almost everywhere, equal to $w(x_1)+w(x_2) = k$:
 
 \begin{itemize}
 \item $\forall S \neq A_1,
@@ -640,11 +640,11 @@ A_2, c(S) = k$
 \item $c(\{A_1\}) = w(x_1)$, and $c(\{A_2\}) = w(x_2)$
 \end{itemize}
 
-{\bf Easy to learn under any distribution}
+\subsection{Easy to learn under any distribution}
 
 TODO
 
-{\bf Hard to optimize under cardinality constraint with $K=1$}
+\subsection{Hard to optimize under cardinality constraint with $K=1$}
 
 Given any distribution ${\cal D}$ on $2^U$ such that
 $\mathbb{P}(\{A_1\}) + \mathbb{P}(\{A_2\}) = o(n^{-c})$ for any constant $c$,
@@ -666,17 +666,26 @@ $$\mathbb{P}_{S_1, \dots S_m \sim {\cal D}}\left(\mathbb{E}(f(\hat S)) \geq
 \frac{1}{n}OPT \right) \geq 1 - \frac{n^C}{2f(n)} \rightarrow 1 \text{ when } n
 \rightarrow +\infty$$
 
-This example is not fully satisfying for two reasons:
+Note that the restriction on ${\cal D}$ is verified by many distributions. In
+the case of the uniform distribution $ = \frac{1}{2^{n-1}}$ and in the case of
+observing all sets of size $k>1$ uniformly at random: $=0$ This example is not
+fully satisfying for two reasons:
+
 \begin{itemize}
   \item the coverage function is not monotone.
   \item the sets we observe most do not satisfy the constraint.
 \end{itemize}
+
 Note that even if we observe sets which \emph{almost} satisfy the cardinality
 constraint, such as all sets of size 2 and only such sets, we would still have
 no hope to output a set with expected value within $\frac{1}{n}$ of OPT\@ under
 cardinality constraint $K=1$. This example can be modified to address the second
 issue.
 
+\subsection{Fixing second issue}
+
+We extend the previous example by slightly modifying ${\cal A}$
+
 \bibliography{optimize} \bibliographystyle{apalike}