diff options
| -rw-r--r-- | paper/sections/assumptions.tex | 20 |
1 files changed, 3 insertions, 17 deletions
diff --git a/paper/sections/assumptions.tex b/paper/sections/assumptions.tex index 7cf9345..896011c 100644 --- a/paper/sections/assumptions.tex +++ b/paper/sections/assumptions.tex @@ -2,23 +2,9 @@ In this section, we discuss the main assumption of Theorem~\ref{thm:neghaban} na \subsection{The Restricted Eigenvalue Condition} -The restricted eigenvalue condition, introduced in \cite{bickel:2009}, is one of the weakest sufficient condition on the design matrix for successful sparse recovery \cite{vandegeer:2009}. Several recent papers show that large classes of correlated designs obey the restricted eigenvalue property with high probability \cite{raskutti:10} \cite{rudelson:13}. Expressing the minimum restricted eigenvalue $\gamma$ as a function of the cascade model parameters is highly non-trivial. However, the restricted eigenvalue property is however well behaved in the following sense: - -\begin{lemma} -\label{lem:expected_hessian} -Expected hessian analysis! -\end{lemma} - -This result is easily proved by adapting slightly a result from \cite{vandegeer:2009} XXX. Similarly to the analysis conducted in \cite{Daneshmand:2014}, we can show that if the eigenvalue can be showed to hold for the `expected' hessian, it can be showed to hold for the hessian itself. It is easy to see that: - -\begin{proposition} -\label{prop:expected_hessian} -If result holds for the expected hessian, then it holds for the hessian! -\end{proposition} - -It is most likely possible to remove this extra s factor. See sub-gaussian paper by ... but the calculations are more involved. - +The restricted eigenvalue condition, introduced in \cite{bickel:2009}, is one of the weakest sufficient condition on the design matrix for successful sparse recovery \cite{vandegeer:2009}. Several recent papers show that large classes of correlated designs obey the restricted eigenvalue property with high probability \cite{raskutti:10} \cite{rudelson:13}. Expressing the minimum restricted eigenvalue $\gamma$ as a function of the cascade model parameters is highly non-trivial. However, the restricted eigenvalue property is however well behaved in the following sense: under reasonable assumptions, if the population matrix of the hessian $\mathbb{E} \left[\nabla^2 {\cal L}(\theta) \right]$, corresponding to the \emph{Fisher Information Matrix} of the Cascade Model as a function of $\Theta$, verifies the restricted eigenvalue property, then the finite sample hessian also verifies the restricted eigenvalue property with overwhelming probability. It is straightforward to show this holds when $n \geq \Omega s^2 \log m$ \cite{vandegeer:2009}. By adapting Theorem 8 \cite{rudelson:13}\footnote{this result still needs to be confirmed!}, this can be reduced to: +$$n \geq C s \log m \log^3 \left( \frac{s \log m}{C'} \right)$$ \subsection{The Irrepresentability Condition} @@ -44,7 +30,7 @@ I_s & \rho J \\ \end{equation} where $I_s$ is the $s \times s$ identity matrix, $J$ is the all-ones matrix and $\rho \in \mathbb{R}^+$. It is easy to see that $\nu_{\text{irrepresentable}}(S) = \rho s$ and $\lambda_{\min}(Q) \geq 1 - \rho$, such that for any $\rho > \frac{1}{s}$ and $\rho < 1$, the restricted eigenvalue holds trivially but the (S,s)-irrepresentability does not hold. -It is intuitive that the irrepresentability condition is stronger than the {\bf(RE)} assumption. In fact, a slightly modified result from \cite{vandegeer:2009}shows that a `strong' irrepresentability condition directly {\it implies} the {\bf(RE)} condition for $\ell2$-recovery: +It is intuitive that the irrepresentability condition is stronger than the {\bf(RE)} assumption. In fact, a slightly modified result from \cite{vandegeer:2009} shows that a `strong' irrepresentability condition directly {\it implies} the {\bf(RE)} condition for $\ell2$-recovery: \begin{proposition} \label{prop:irrepresentability} |