Paper detail

An analysis of penalized interaction models

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.