2D sparse fused lasso with negative binomial

Question

I am looking for a very specific model, and I am not sure it exists (yet). It is the 2D sparse fused lasso in a negative binomial regression setting. That means

• Negative binomial observations: $y_i \sim NB(\mu_i,\theta)$ , where $\log \mu = \log m + X\beta$. $m$ is given (it's an offset), and $\theta$ too.
• $\beta$ represents coefficients on a 2D grid
• Sparse lasso means I want a penalty in the form $\lambda\sum_i|\beta_i|$
• Fused lasso means I also want it on their differences to the nearest neighbors on a grid, e.g. $\lambda'\sum_i\sum_{j\in \text{ neighbors of }i} |\beta_i-\beta_j|$
• And of course I want the "best" $\lambda$ and $\lambda'$, along with the optimal $\beta$.

Focus is on very fast algorithms, as the size of $\beta$ can be in the range of milions. And the $y_i$ are even more abundant. Bonus if trend filtering is possible.

If nothing like this is available, I also accept suggestions for starting points, to build on. For example, algorithms that can be generalized easily to this case.

Answer 1

Fused lasso on a 2d grid is called generalized fused lasso, it can take into an account any neighborhood structure you can represent as a graph. I think it should not be a problem to use it for negative binomial, it is all just about adding the penalty term.

Unlike the standard lasso, fused lasso cannot be as effectively computed. I know about this paper claiming to have an efficient algorhitm, but I don't know where it stands in the state of the art, but it might be worth to look at for you http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/viewFile/8261/8862

Another option for you, if the speed is important is to ditch the fuse lasso and use just elastic net, which can be solved on GPU with SVM solvers. Not sure about the negative binomial tho. You can add the spatial dependency to your model by smoothing the data.