5
$\begingroup$

I know that linear regression leads to a convex optimization problem. I'd like to visually show this with a simple example. Assume that there are two parameters (x and y) and a single data point <1, 1> with 2 as the y value (no intercept term. Then the cost function becomes

$$ (x+y-2)^2 $$

However if you plot this function you will get the figure enter image description here which contains more than one minimal point. Where is the problem in this example? Thanks

$\endgroup$
5
$\begingroup$

2 parameters and a single data point is not strictly convex because the rank of the matrix of observations and predictors is deficient. Indeed, as you observe, there is a line of many "equally good" solutions, and this is because for any choice of $x$ there is a corresponding $y$ which achieves the minimum: how many points satisfy $x+y=2$?

Add more observations than predictors and the problem is (strictly) convex.

$\endgroup$
  • 3
    $\begingroup$ 2 parameters and a single data point is convex, but not strictly convex, and the global minimum is not unique. It is not "not convex". $\endgroup$ – Mark L. Stone Apr 7 '16 at 18:53
  • $\begingroup$ @MarkL.Stone Yes, thanks, it always trips me up when "X" and "not X" don't quite exactly behave the way I might expect. $\endgroup$ – Sycorax says Reinstate Monica Apr 7 '16 at 18:57
  • $\begingroup$ "more observations than predictors" exactly, thanks $\endgroup$ – Sanyo Mn Apr 7 '16 at 20:33
  • $\begingroup$ i.e., it is weakly convex $\endgroup$ – MichaelChirico Apr 8 '16 at 1:36
6
$\begingroup$

$$(x+y-2)^2=0$$ $$x+y=2$$ $$y=2-x$$

You can pick any $x$, and get a corresponding $y$, i.e. there's no unique solution. With two unknowns and one observation, there's not going to be a unique solution

$\endgroup$

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.