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.

$\endgroup$
7
  • $\begingroup$ $X^\top X$ is a matrix, not scalar. In what sense do you mean "negative"? $\endgroup$
    – Sycorax
    Nov 3 '20 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$ Nov 3 '20 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
    Nov 3 '20 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
    Nov 4 '20 at 14:56
  • 1
    $\begingroup$ @Henry Then please take a look at my link or at the answer posted here by Firebug. $\endgroup$
    – whuber
    Nov 4 '20 at 15:09
20
$\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)

$\endgroup$
2
  • 1
    $\begingroup$ for all non-zero column vectors b $\endgroup$ Nov 3 '20 at 20:24
  • 1
    $\begingroup$ Yes, ok. Updated $\endgroup$ Nov 4 '20 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.

$\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
    Nov 4 '20 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
    Nov 4 '20 at 7:15
  • $\begingroup$ I modified the answer, taking care to eliminate the degenerate case instead of implying it @Cm7F7Bb $\endgroup$
    – Firebug
    Nov 4 '20 at 12:24

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.