10
$\begingroup$

Definition of ridge regression $$min_\beta||y-X\beta||_2^2+\lambda||\beta||_2^2, \lambda\ge0$$

you can prove a function is strictly convex if the 2nd derivative is strictly greater than 0 thus

enter image description here

But unfortunately I don't know if this is sufficient proof as it's possible for $X^TX$ to be negative and $\lambda$ can be 0. Unless I'm missing something.

Improve this question
$\endgroup$
7
  • $\begingroup$ $X^\top X$ is a matrix, not scalar. In what sense do you mean "negative"? $\endgroup$
    – Sycorax ♦
    Commented Nov 3, 2020 at 4:44
  • $\begingroup$ @Sycorax I assumed that no entries in the resulting matrix can be negative in order for the function to be strictly convex. Or is that not the case? Is convexity different if it's a matrix? $\endgroup$
    – user8714896
    Commented Nov 3, 2020 at 4:47
  • $\begingroup$ Since the second partial derivative of $f$ is a matrix, you'll need to adapt your definition to the case of a matrix. You can show that $\frac{\partial ^2 f}{\partial \beta^2}$ is positive semi-definite. What remarks about convexity can you make about p.s.d. matrices? $\endgroup$
    – Sycorax ♦
    Commented Nov 3, 2020 at 5:00
  • 2
    $\begingroup$ @Henry and when $\lambda$ otherwise is positive, it is still OLS regression.. In short, this objective function is a squared Euclidean distance to a point, whence it is (obviously) strictly convex. $\endgroup$
    – whuber ♦
    Commented Nov 4, 2020 at 14:56
  • 1
    $\begingroup$ @Henry Then please take a look at my link or at the answer posted here by Firebug. $\endgroup$
    – whuber ♦
    Commented Nov 4, 2020 at 15:09

2 Answers 2

Reset to default
21
$\begingroup$

"you can prove a function is strictly convex if the 2nd derivative is strictly greater than 0"

That's in one dimension. A multivariate twice-differentiable function is convex iff the 2nd derivative matrix is positive semi-definite, because that corresponds to the directional derivative in any direction being non-negative. It's strictly convex iff the second derivative matrix is positive definite.

As you showed, the ridge loss function has second derivative $2\lambda I +2X^TX$, which is positive definite for any $\lambda>0$ because

  • $\lambda I$ is positive definite for any $\lambda>0$
  • $X^TX$ is positive semi-definite for any $X$
  • the sum of a positive definite and positive semi-definite matrix is positive definite

If you aren't sure about any of these and want to check in more detail it's useful to know that $A$ is positive definite iff $b^TAb>0$ for all (non-zero) column vectors $b$. Because of this relationship, many matrix proofs of positive definiteness just come from writing the scalar proofs of positiveness in matrix notation (including non-trivial results like the Cramér-Rao lower bound for variances)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ for all non-zero column vectors b $\endgroup$
    – David Epstein
    Commented Nov 3, 2020 at 20:24
  • 1
    $\begingroup$ Yes, ok. Updated $\endgroup$
    – Thomas Lumley
    Commented Nov 4, 2020 at 5:25
2
$\begingroup$

Less of a proof, and more of a convincing argument (that can lead you towards the proof): we all agree ordinary least squares with full rank covariance matrix $X^TX$ is strictly convex (see Convexity of linear regression), ridge regression is a form of OLS with augmented (virtual) data, thus it's also strictly convex.

The augmentation $X\text{aug} = \left[ \begin{matrix}X^T & \sqrt\lambda\mathbb I \end{matrix}\right]^T$ actually ensures that, in ridge, $X\text{aug}^TX\text{aug}$ is full rank, since it consists of concatenating a multiple of the identity matrix $\sqrt\lambda\mathbb I$.

So, if you can show that the equivalent OLS is strictly convex, so is ridge regression.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ OLS is not necessarily strictly convex. OLS is strictly convex if and only if the columns of the design matrix are linearly independent. $\endgroup$
    – Cm7F7Bb
    Commented Nov 4, 2020 at 3:25
  • $\begingroup$ The argument could be modified to take care of @Cm7F7Bb's point, by noting that the particular form of the augmentation guarantees linearly independent columns (as long as the ridge parameter is greater than zero). $\endgroup$
    – user20160
    Commented Nov 4, 2020 at 7:15
  • $\begingroup$ I modified the answer, taking care to eliminate the degenerate case instead of implying it @Cm7F7Bb $\endgroup$
    – Firebug
    Commented Nov 4, 2020 at 12:24

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.