Lasso-ing the order of a lag? Suppose I have longitudinal data  of the form $\mathbf Y = (Y_1, \ldots, Y_J) \sim \mathcal N(\mu, \Sigma)$ (I have multiple observations, this is just the form of a single one). I'm interested in restrictions on $\Sigma$. An unrestricted $\Sigma$ is equivalent to taking
$$
Y_j = \alpha_j + \sum_{\ell = 1} ^ {j - 1} \phi_{\ell j} Y_{j-\ell} + \varepsilon_j
$$
with $\varepsilon_j \sim N(0, \sigma_j)$. 
This is typically not done since it requires estimating $O(J^2)$ covariance parameters. A model is "lag-$k$" if we take
$$
Y_j = \alpha_j + \sum_{\ell = 1} ^ k \phi_{\ell j} Y_{j - \ell} + \varepsilon_j,
$$
i.e. we only use the preceding $k$ terms to predict $Y_j$ from the history.
What I'd really like to do is use some kind of shrinkage idea to zero out some of the $\phi_{\ell j}$, like the LASSO. But the thing is, I also would like the method I use to prefer models which are lag-$k$ for some $k$; I'd like to penalize higher order lags more than lower order lags. I think this is something we would particularly like to do given that the predictors are highly correlated. 
An additional issue is that if (say) $\phi_{35}$ is shrunk to $0$ I would also like it if $\phi_{36}$ is shrunk to $0$, i.e. the same lag is used in all of the conditional distributions. 
I could speculate on this, but I don't want to reinvent the wheel. Is there any LASSO techniques designed to get at this sort of problem? Am I better off just doing something else entirely, like stepwise inclusion of lag orders? Since my model space is small, I could even use an $L_0$ penalty on this problem I guess?
 A: The ordered LASSO seems to be what you're looking for: It computes the regularized regression coefficients $\beta_{1...j}$ as in the standard LASSO, but subject to the additional constraint that $|\beta_1| \geq |\beta_2|...\geq|\beta_j|$. 
This accomplishes the second goal of zeroing out coefficients for higher-order lags, but is more restrictive than the sole restriction of preferring a lower lag model. And as others point out, this is a heavy restriction that can be very difficult to justify.
Having dispensed with the caveats, the paper presents the method's results on both real and simulated time series data, and details algorithms to find the coefficients. The conclusion mentions an R package, but the paper is rather recent and a search on CRAN for "ordered LASSO" comes up empty, so I suspect the package is still in development.
The paper also offers a generalized approach in which two regularization parameters "encourage near-monotonicity." (See p. 6.) In other words, one should be able to tune the parameters to allow for a relaxed ordering. Sadly, neither examples nor comparisons of the relaxed method are provided. But, the authors write that implementing this change is a simple matter of replacing one algorithm with another, so one hopes it will be part of the coming R package. 
A: You can do cross validation repeatedly from k = 0 to whatever the maximum is, and plot the performance against k. Since the model is being tested on data it hasn't seen before, there is no guarantee the complex models will perform better, and indeed you should see a degradation in performance if the model becomes too complex due to overfitting. Personally I think this is safer and easier to justify than having an arbitrary penalty factor, but your mileage may vary. 
I also don't really follow how ordered Lasso answers the question. It seems too restrictive, it is completely forcing the ordering of the coefficients. Whereas the original question may end up for some data having a solution where $\phi_{lj}$ is not strictly decreasing with l.
A: The nested LASSO penalty (pdf) could be employed but there are no R packages for it.
A: I know you wrote it as a premise, but I would not use the ordered LASSO without being absolutely sure that this is thing that is needed, because the assumptions of the ordered LASSO are not directly appropriate for time-series prediction. As a counter-example, consider the case where you have a delay-time of, say, ten time-steps between measurement and target. Obviously, the ordered LASSO constraints cannot handle such a effects without attributing nonsense to the first nine parameters.
In contrast, I would rather stick to the normal LASSO and include all previous observation -- particularly because you wrote your model space is small, and coordinate-descent optimization routines for the LASSO (as described here) are working efficiently also for large datasets. Then compute the path for the regularization strength parameter $\lambda$ and look which parameters get included as you go from large $\lambda$ to $\lambda=0$. Especially those included earlier are the important ones.
Finally, you have to choose an appropriate criterion and optimize the parameter $\lambda$ using cross-validation, standard one-dimensional minimization or whatever. The criterion can for example be something as "prediction error + number of included variables" (--AIC criterion-like).
