diff options
Diffstat (limited to 'paper/sections/assumptions.tex')
| -rw-r--r-- | paper/sections/assumptions.tex | 7 |
1 files changed, 6 insertions, 1 deletions
diff --git a/paper/sections/assumptions.tex b/paper/sections/assumptions.tex index 896011c..33d8e69 100644 --- a/paper/sections/assumptions.tex +++ b/paper/sections/assumptions.tex @@ -2,10 +2,15 @@ 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: 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: +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. Yet, 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 C s^2 \log m$ \cite{vandegeer:2009}, where $C$ is an absolute constant. 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)$$ +where $C, C'$ are constants not depending on $(s, m, n)$. + + \subsection{The Irrepresentability Condition} \cite{Daneshmand:2014} rely on an `incoherence' condition on the hessian of the likelihood function. It is in fact easy to see that their condition is equivalent to the more commonly called {\it (S,s)-irrepresentability} condition: |