diff options
| -rw-r--r-- | results.tex | 52 |
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} |