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.

  • 3
    $\begingroup$ For large scale problems with the two lasso components, there might be something in the computer vision literature on motion segmentation? (The "fused" part sounds like things used there which act like a median filter, and the base lasso would combine to promote "sparse activated blobs with sharp boundaries", similar to moving objects against a stationary background?) $\endgroup$
    – GeoMatt22
    Oct 11, 2016 at 1:36

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.