slightly better formulation of results on coverage function

1 files changed, 34 insertions, 12 deletions

diff --git a/brainstorm/results.tex b/brainstorm/results.tex
index 0453d95..5ca05f2 100644
--- a/brainstorm/results.tex
+++ b/brainstorm/results.tex
@@ -632,17 +632,39 @@ $${\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$. $\forall S \neq A_1,
-A_2, c(S) = k$ except for two singleton sets of ${\cal A}$: $c(\{A_1\}) =
-w(x_1)$, and $c(\{A_2\}) = w(x_2)$.
+constant almost everywhere, equal to $w(x_1)+w(x_2) = k$: 
 
-It can be shown that this class of functions is $PAC$-learnable, and
-$PMAC$-learnable. However, given any distribution ${\cal D}$ on $2^U$ such that
+\begin{itemize}
+\item $\forall S \neq A_1,
+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}
+
+TODO
+
+{\bf 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$,
-then for $m = \Omega(n^c)$ for a constant $c \in \mathbb{R}^+$ and for $\hat S$
-returned by any one-shot optimization algorithm ${\cal B}$:
+i.e. $\exists f : n \mapsto \mathbb{R}^+ \text{ s.t. } \lim_{n\rightarrow
++\infty} f(n) = +\infty \text{ and } \mathbb{P}(\{A_1\}) + \mathbb{P}(\{A_2\}) =
+{\cal O}(n^{-f(n)})$, and for any constant $C \in \mathbb{R}$ and $m \equiv
+n^C$, then for $n$ sufficiently large, the set $\hat S$ returned by any one-shot
+optimization algorithm after observing random sets $S_1, S_2, \dots S_m$ from
+${\cal D}$ is such that:
+
 $$\mathbb{P}_{S_1, \dots S_m \sim {\cal D}}\left(\mathbb{P}_{\hat S}
-\left(f(\hat S) \geq \frac{OPT}{n}\right) \geq 1- \epsilon\right) \leq \delta$$
+\left(f(\hat S) > 0\right) \geq \frac{1}{n}\right) \leq \frac{n^C}{2f(n)}
+\rightarrow 0 \text{ when } n \rightarrow +\infty$$
+
+The previous proposition can be reformulated in the slightly weaker formulation
+which is more intuitive:
+
+$$\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:
 \begin{itemize}
@@ -650,10 +672,10 @@ This example is not fully satisfying for two reasons:
   \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, we would still have no hope to optimize
-the function within better than a $\frac{1}{n}$ approximation factor.
-
-This example can be modified to address the second issue.
+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.
 
 \bibliography{optimize} \bibliographystyle{apalike}