  An important consideration for variable selection in interaction models is to
design an appropriate penalty that respects hierarchy of the importance of the
variables. A common theme is to include an interaction term only after the
corresponding main effects are present. In this paper, we study several
recently proposed approaches and present a unified analysis on the convergence
rate for a class of estimators, when the design satisfies the restricted
eigenvalue condition. In particular, we show that with probability tending to
one, the resulting estimates have a rate of convergence $s\sqrt{\log p_1/n}$ in
the $\ell_1$ error, where $p_1$ is the ambient dimension, $s$ is the true
dimension and $n$ is the sample size. We give a new proof that the restricted
eigenvalue condition holds with high probability, when the variables in the
main effects and the errors follow sub-Gaussian distributions. Under this
setup, the interactions no longer follow Gaussian or sub-Gaussian distributions
even if the main effects follow Gaussian, and thus existing works are not
applicable. This result is of independent interest.
