cleaning section 3.3

1 files changed, 18 insertions, 34 deletions

diff --git a/results.tex b/results.tex
index 66e8f10..e293905 100644
--- a/results.tex
+++ b/results.tex
@@ -87,7 +87,7 @@ Hence the probability that our random matrix $A$ is invertible is:
 It is easy to see that $P_n$ is a decreasing sequence. Its limit is
 $\phi(\frac{1}{2})$ where $\phi$ is the Euler function. We have
 $\phi(\frac{1}{2})\approx
-0.2887880950866024212788997219292307800889119048406857$ and $P_n$ converges
+0.289$ and $P_n$ converges
 exponentially fast to this constant (one way to see this is to use the
 Pentagonal number theorem).
 
@@ -221,39 +221,20 @@ A result by~\cite{balcan2011learning} states that:
   by outputting a function $\tilde f: S\mapsto \sqrt{\frac{1}{(n+1)z}w^T
   \chi(S)}$.  \end{proposition}
 
-By adapting Section~\ref{subsec:invert_the_system}, we get the following
-result:
-
-TODO:actually this is is not entirely accurate! Though we might not care about
-not learning the zeros of the function, not being able to estimate correctly
-a fraction of the non-zero sets is a big problem
-
-\begin{proposition} Any non-negative monotone submodular function can be
-passively optimized under cardinality constraint $k \in \mathbb{N}$ from $D_p$
-for \emph{any} $p \in ]0, 1[$ with polynomially many samples up to a factor
-  $1/\sqrt{n+1}$. TODO:what about $\epsilon$ \end{proposition}
-
-\begin{proof} We optimize $\tilde f$ from
-Proposition~\ref{prop:balcan_learned}, which can easily be done by solving for
-the system $Ax = b^2$ where ${(b^2)}_i = (b_i)^2$. TODO: complete proof
-\end{proof}
-
-
+{\bf TODO}: Does this imply a good guarantee if we solve the system
+$Ax=f^{-1}(b)$? Probably not, though we might not care about not learning the
+zeros of the function perfectly, not being able to estimate correctly a
+fraction of the non-zero sets is a big problem
 
 \subsection{Average weight method}
 
-Same thing can probably be said for the average weight method.
-
 \subsection{Passive Optimization can be easier than Learning}
 
-We consider the Matroid construction from~\cite{balcan2011learning}: it is easy
- to see that from this example we can construct a set of matroid rank functions 
- which can never be learned (under any distribution, even with active queries!)
- but which are very easy to optimize exactly! We recall the Matroid construction
- (Theorem 1):
+Consider the matroid construction from~\cite{balcan2011learning}, which we
+recall here:
 
 \begin{theorem}
-  For any $k$ with $k = 2^{o(n^{1/3}}$, there exists a family of sets ${\cal A}
+  For any $k$ with $k = 2^{o(n^{1/3})}$, there exists a family of sets ${\cal A}
   \subseteq2^{[n]}$ and a family of matroids $\cal{M} = \{M_{\cal{B}} :
   \cal{B} \subseteq\cal{A} \}$ such that:
   \begin{itemize}
@@ -267,13 +248,16 @@ We consider the Matroid construction from~\cite{balcan2011learning}: it is easy
   \end{itemize}
 \end{theorem}
 
-By considering the above family of matroids, such that
-$|\cal{A}\backslash\cal{B}| \geq frac{1}{n}\cal{A}$, we will observe at least
-one element from $\cal{A}\backslash\cal{B}$ with constant probability after
-polynomially many observations as long as the distribution is uniform (but for
-a more general class of distribution $\cal{D}$ this would be true as well),
-which means we can maximise exactly. Yet we cannot learn the family of matroid
-rank functions under any distribution.
+Consider the following subset of the above family of matroids: ${\cal M}^1 =
+\{M_{\cal B} : {\cal B} \subseteq{\cal A} \wedge |{\cal A}\backslash{\cal B}| \geq
+\frac{1}{n}{\cal A}\}$. Suppose we observe sets from a uniform distribution
+over all sets of ${\cal A}$, then after polynomially observations, we will
+observe at least one element from $\cal{A}\backslash\cal{B}$ with constant
+probability. Note that as long as we observe \emph{one} set from ${\cal A}
+\backslash {\cal B}$, we can optimize the unknown function directly. However,
+it follows from the analysis of~\cite{balcan2011learning} that we cannot learn
+this family of matroid rank functions under any distribution, even with active
+value queries!
 
 \bibliography{optimize} \bibliographystyle{apalike}