I am currently reading a paper stating the following regression problem $$\text{min} \sum_{i=1}^N ||\beta\cdot x_i-y_i||\\ \text{subject to} \sum_{j=2}^M ||\beta_{j}-\beta_{j-1}|| \leq S $$ for vectors $x_1,\dots,x_N, \beta \in \mathbb{R}^n, y_i \in \mathbb{R}$. This is a slightly changed version of the fused lasso loss for a regression problem. The authors state, this poblem can be solved via maximum likelihood estimation. I would have used quadratic program solvers instead but they are slower of course. Are there closed form solutions (from MLE) for this kind of problem?

  • $\begingroup$ Do you have a reference to the paper? $\endgroup$ – Sextus Empiricus Aug 28 '18 at 15:59
  • $\begingroup$ people.cs.vt.edu/gangwang/ccs18.pdf The mentioned paragraph on the computation is directly below equation (7) $\endgroup$ – AlexConfused Aug 28 '18 at 16:15
  • $\begingroup$ This is actually related to the penalty used by P-splines, see projecteuclid.org/download/pdf_1/euclid.ss/1038425655 (Eilers and Marx, Flexible Smoothing with B-splines and Penalties). $\endgroup$ – jbowman Aug 28 '18 at 16:30
  • $\begingroup$ The regression problem you present defines an estimator based on a loss function that is being minimized. Meanwhile, maximum likelihood (ML) defines an estimator based on maximizing the likelihood. I do not think the two can ever coincide since ML would never yield a penalized solution such as this one. ML is not even an method for calculating parameter estimates, unlike quadratic solvers, gradient descent, Newton-Raphson etc. (I have a problem finding the right term for all of these; optimization methods, maybe?). ML tells you what you are looking for but not how to calculate it mechanically. $\endgroup$ – Richard Hardy Sep 16 '18 at 8:38
  • $\begingroup$ Therefore, I am not sure whether the current formulation of the question quite makes sense. $\endgroup$ – Richard Hardy Sep 16 '18 at 8:40

How about transforming to the vectors as following:

$$z_j = \sum_{i=j}^{N} x_i $$

where the index refers to the index of the regressors.


$$\beta^\star \cdot z = \beta \cdot x$$


$$\beta_j = \sum_{i=1}^{j} \beta_i^\star \quad \text{ or (when $i \geq 2$)} \quad \beta^\star_i = \beta_i-\beta_{i-1}$$

Now you just have to solve the problem for $z$ (instead of $x$) with the easier constraint $ \sum_{i=2}^M ||\beta^\star_{i}|| \leq S$.

This turns into ridge regression (where $\Gamma_{11} = 0$ in the Tikhonov regularization matrix) when we assume $\Vert \cdot \Vert$ is the quadratic norm, in which case there is a closed solution. Otherwise for Lasso there is a good algorithm to solve it.

Schematic example for $\beta^\star \cdot z = \beta \cdot x$ using three variables:

$\begin{array}{ccccccc} \beta_1^\star z_1 &=& \beta_1^\star x_1 & + & \beta_1^\star x_2 &+& \beta_1^\star x_3 \\ \beta_2^\star z_2 &=& & & \beta_2^\star x_2 &+& \beta_2^\star x_3 \\ \beta_3^\star z_3 &=& & & && \beta_3^\star x_3 \\ & & \vert\vert & & \vert\vert & & \vert\vert \\ & & \beta_1 x_1 & & \beta_2 x_2 & & \beta_3 x_3 \\ \end{array} $

To avoid confusion about indices

The article speaks of the cost function

$$L(f(\mathbf{x}),y) = \sum_{i=1}^N \Vert \boldsymbol\beta \mathbf{x_i} -y_i \Vert$$

with $x_i$ a sample $i$ represented by a row vector $(x_1, x_2, \cdots, x_M)^T$ of different features. This can be simplified to a matrix notation using $X = ((x_1, x_2, \cdots, x_M)^T)_i$ where each column of X is a vector of the same feature for different samples $i$.

$$L(f(\mathbf{x}),\mathbf{y}) = \Vert \mathbf{X} \boldsymbol\beta^T -\mathbf{y} \Vert$$

when I speak about the index of the regressors I mean the column index of the matrix $X$ (this adding the columns of $X$ is equivalent to adding the entries in the row vectors $\mathbf{x_i}$)

see also https://en.wikipedia.org/wiki/Design_matrix

  • $\begingroup$ I don't think this is correct. Firstly, I am not sure if your transformation works and even if it works you will solve a regression problem with ridge loss in the end, i.e. your parameters $\beta$ will not have a form such that neighbor parameters are as close as $S$ to each other. $\endgroup$ – AlexConfused Aug 28 '18 at 13:58
  • $\begingroup$ I changed the the transformation (which was indeed in error). The $\beta^\star$ will indeed not be necessarily close to each other. Instead the $\beta^\star$ will be as small as possible such that the neighbors in $\beta_j=\sum_{i=1}^j \beta_i^\star$ will be as close as possible. $\endgroup$ – Sextus Empiricus Aug 28 '18 at 14:01
  • $\begingroup$ In your transformation $z_j = \sum_{i=j}^N x_i$ , is $x_i$ the $i$-th vector from the training set (as introduced in question) or the $i$-th entry of some vector $x$? $\endgroup$ – AlexConfused Aug 28 '18 at 14:44
  • $\begingroup$ It refers to the i-th vector $\endgroup$ – Sextus Empiricus Aug 28 '18 at 14:56
  • $\begingroup$ I think it should refer to the i-th entry. Only then is the transformation correct. $\endgroup$ – AlexConfused Aug 28 '18 at 16:25

After some research I have found out that there is no closed form solution for this problem (and therefore no MLE in particular). A (fast) solution for this problem has been proposed via solution paths, the algorithm can be found here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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