Solving a least squares rather than a quadratic program?

[stephane-caron]

Is it possible to solve a least squares rather than a quadratic program?

[stephane-caron]

Yes, there is also a solve_ls function.

See also the post Conversion from least squares to quadratic programming for details on how this is done, and inspiration if you need to convert a similar problem.

[ogencoglu]

How about ridge regression or LASSO, i.e., having an additional penalty term in the objective function regarding the magnitude of the weights?

[stephane-caron]

You're welcome. Here is a more detailed answer:

• Ridge regression: yes, $\ell^2$ norm goes to the cost matrix $P$.
• Lasso: yes, $\ell^1$ norm goes to the cost vector $q$ and inequality constraints. Essentially one introduces a new variable $z = |x|$ via inequality constraints: $x \leq z$ and $-x \leq z$, then minimize $-1^T z$ in the cost (where $1$ is a ones vector) so that all inequalities are tight. Then $z = |x|$ at the optimum and $|x|_1 \leq t$ with a constant parameter $t$ is equivalent to adding the inequality constraint $z \leq t$.
• $\ell^p$ norm: I'm not an expert on this and have not thought this question through, so my answer won't help much 😉 My hunch is "not always", but I let you research this question properly.

[stephane-caron]

@ogencoglu I wrote the following note on Lasso regularization in quadratic programming. Could you read it and let me know whether it is correct and clear, or if you have other feedback?

[ogencoglu]

Thanks a lot for the quick write-up. It seems indeed correct. I also agree that fractional or non-integer L-norms would not work in QP context.

[ogencoglu]

A side note: typically machine learning people use lambda to denote t in your equation.

[stephane-caron]

Thank you for your feedback 👍 I see in research articles (for instance Complexity Analysis of the Lasso Regularization Path) that $\lambda$ is used in the objective function rather than in the inequality constraints, and the resulting formulation is also called "lasso". That is not exactly the formulation from the original article by Tibshirani (1996) which is the one followed on the Wikipedia article on Lasso (statistics). But the $\lambda$ is also mentioned in the Wikipedia article in Making λ easier to interpret with an accuracy-simplicity tradeoff.

TL;DR: the note now mentions both $t$ and $\lambda$ 😉

[ogencoglu]

Another related question:

In order to optimize the intercept term (i.e., b in ax + b) as well in the regression, does the following makes sense:

• appending a column of 1s to the end of R and
• appending a column of zeros to the end of A

Do you see any issues with this approach or would you achieve the same in another way?

[stephane-caron]

Hi @ogencoglu, I will take a look at your question, but could you open a separate discussion for each new question?

This will make it easier for future travelers to find question and answers.

[ogencoglu]

Will do, thanks.