5
$\begingroup$

It's well known that linear least squares problems are convex optimization problems. Although this fact is stated in many texts explaining linear least squares I could not find any proof of it. That is, a proof showing that the optimization objective in linear least squares is convex. Any idea how can it be proved? Or any pointers that I can look at?

Thanks

$\endgroup$
  • $\begingroup$ Cross posted here http://stats.stackexchange.com/questions/69106/proof-of-convexity-of-linear-least-squares $\endgroup$ – Avraham Sep 3 '13 at 20:57
  • 2
    $\begingroup$ All norms are convex, and the function $\phi(t)= 1_{(-\infty,0)} (t) t^2$ is convex and non-decreasing, hence $x \mapsto \|x\|^2$ is also convex (see Rockafellar's "Convex Analysis" Theorem 5.1) . Finally, a convex function composed with a linear map is convex. $\endgroup$ – copper.hat Sep 9 '13 at 1:49
  • $\begingroup$ Another quick proof is to note that the gradient of $f(x) = (1/2)\| Ax-b\|^2$ is $A^T(Ax-b)$ and the Hessian is $A^TA$, which is positive semidefinite. It follows that $f$ is convex. $\endgroup$ – littleO Dec 18 '19 at 1:43
  • 1
    $\begingroup$ I think these answers are a little complicated. Note that $x \mapsto x^2$ is convex for any $x \in \mathbb{R}$. The sum of convex functions is convex, and affine precomposition is convex. The latter two statements are one-line proofs, so you're done since $\|Ax - b\|_2^2 = \sum_i (a_i^Tx - b)^2$. $\endgroup$ – Guillermo Angeris Dec 18 '19 at 17:16
9
$\begingroup$

Another way to prove that a function is convex is by showing that the second order derivative (if it exists) is positive semi-definite.

$$ \phi: \beta \mapsto \Vert y - X \beta \Vert^2 = \Vert y \Vert^2 - 2 y^T X \beta + \Vert X \beta \Vert^2$$ $\phi$ is twice differentiable and the second derivative (i.e. the Hessian) is

$$ \dfrac {\partial \phi} {\partial \beta} = - 2y^TX + 2(X\beta)^TX =- 2y^TX + 2\beta^TX^TX $$

$$ \dfrac {\partial^2 \phi} {\partial \beta \partial \beta^T} = 2X^TX$$

which is a positive semi-definite matrix. Therefore, $\phi$ is a convex function.

$\endgroup$
  • $\begingroup$ How were you able to differentiate ϕ twice? $\endgroup$ – David May 4 '17 at 4:02
  • $\begingroup$ Also, is the second derivative the Hessian? $\endgroup$ – David May 4 '17 at 6:18
  • 1
    $\begingroup$ The first derivative is incorrect. You're adding a row vector to a column vector. $\endgroup$ – Rodrigo de Azevedo Sep 28 '17 at 9:16
  • $\begingroup$ can anyone explain me how do we reach the first derivative? $\endgroup$ – Bagus Trihatmaja Jan 12 '18 at 6:30
  • 1
    $\begingroup$ @BagusTrihatmaja I corrected the first derivative in my edit. It depends upon the fact that the derivative of $\Vert \mathbf{x}\Vert^2$ with respect to $\mathbf{x}$ is $2\mathbf{x}^T$. Then you can make use of the chain rule. $\endgroup$ – Christian Sykes Jan 12 '18 at 11:07
5
$\begingroup$

You want a proof that the function $$ \phi: \beta \mapsto \Vert y - X \beta \Vert^2 = \Vert y \Vert^2 - 2 y^T X \beta + \beta^T X^T X \beta $$ is convex, right? (here $\beta$ and $y$ are vectors and $X$ is a matrix). In other words, you need to prove that $$ \phi(t \beta_1 + (1-t) \beta_2) - \left[ t \phi( \beta_1) + (1-t) \phi(\beta_2) \right] \leq 0 $$ for all $\beta_1, \beta_2$ and $t \in [0,1]$. After calculation, the left-hand term becomes $$ t^2 \beta_1^T X^T X \beta_1 + (1-t)^2 \beta_2^T X^T X \beta_2 + 2 t(1-t) \beta_1^T X^T X \beta_2 - t \beta_1^T X^T X \beta_1 - (1-t) \beta_2^T X^T X \beta_2 $$ $$ = - t(1-t) \left[ (\beta_1 - \beta_2)^T X^T X (\beta_1 - \beta_2) \right] = - t(1-t) \Vert X (\beta_1 - \beta_2) \Vert^2$$ which is clearly $\leq 0$.

$\endgroup$
  • $\begingroup$ Can you expand on "after calculation"? $\endgroup$ – vega Dec 7 '17 at 15:01
  • $\begingroup$ @vega You can use the fact that $\Vert \mathbf{x}\Vert^2 = \mathbf{x}^T\mathbf{x}$. $\endgroup$ – Christian Sykes Jan 12 '18 at 11:10
0
$\begingroup$

Here's an alternative way to see the convexity of $f(\beta)\triangleq \Vert y-X\beta\Vert^2$. For $t\in [0,1]$, let $\bar t=1-t$. Then

$f(t\alpha + \bar t \beta)=\Vert t(y-X\alpha)+\bar t (y-X\beta)\Vert^2 \le \left(t\Vert y-X\alpha\Vert +\bar t\Vert y-X\beta\Vert\right)^2\le t\Vert y-X\alpha\Vert^2+\bar t \Vert y-X\beta\Vert^2=tf(\alpha)+\bar tf(\beta)$

where the first inequality is due to triangle inequality of vector norm, and the 2nd inequality follows because the square function ($x^2$) is also convex.

$\endgroup$
  • $\begingroup$ I just noted the copper.hat's comment above. This answer in fact just elaborated his comment. $\endgroup$ – syeh_106 Nov 26 '19 at 6:55
0
$\begingroup$

I decided to make my comment an answer since I think that a few of these are a little complicated due to the careful bookkeeping for derivatives. We say a function $f$ is convex if for any $0 \le \gamma \le 1$ and $x, y \in \mathbb{R}^n$ we have that $$ f(\gamma x + (1-\gamma)y) \le \gamma f(x) + (1-\gamma)f(y). $$

We can now prove it in three (simple!) steps, which I will prove here for the sake of convenience, but these are extraordinarily standard one-line-proofs.

  1. First, it's clear that the function $f(x) = x^2$ is convex (prove this in your favorite way).

  2. Now, for any two convex functions $f, g: \mathbb{R}^n \to \mathbb{R}$, their sum is convex since, simply applying the definitions, $$ f(\gamma x + (1-\gamma)y) + g(\gamma x + (1-\gamma)y) \le \gamma (f(x) + g(x)) + (1-\gamma) (f(y) + g(y)). $$

  3. Affine precomposition preserves convexity, since if $f$ is convex, then $$ f(A(\gamma x + (1-\gamma)y) + b) =f(\gamma Ax + (1-\gamma)Ay + (\gamma + (1-\gamma)) b) \le \gamma f(Ax + b) + (1-\gamma)f(Ay+b), $$

so, since the function $$ f(x) = \|Ax - b\|_2^2 = \sum_i (a_i^Tx - b_i)^2, $$ is the sum of a bunch of convex functions precomposed with affine functions, then $f$ is convex.

$\endgroup$
0
$\begingroup$

I just want to elucidate a bit on proofs provided by @roger and @acharuva.

Two popular ways to prove that a function $f$ is convex are to prove that:

\begin{equation} f(tx_1+(1-t)x_2)-tf(x_1)-(1-t)f(x_2) \leq 0 \end{equation}

for $t \in [0,1]$ and to prove that the second derivative is non-negative for the entire support (domain of $f$). The first is the definition of convexity and the second is a well-known theorem (Proof here http://www.princeton.edu/~aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec7_gh.pdf) . For multivariate functions this means proving that the Hessian is PSD (A matrix A is PSD if A is symmetric and $u^TAu\geq0$ irrespective of $u$).

In case of OLS or the linear regression cost function we have: \begin{equation} J(\theta) = \frac 1 2 {(X \theta -Y)}^2 = \frac12( \theta^TX^TX\theta -2Y^TX\theta + Y^TY) \end{equation}

\begin{equation} \frac {\partial J(\theta)} {\partial \theta} = X^T(X\theta-Y) \end{equation} [because $\nabla_Atr(ABA^TC)=C^TAB^T+CAB$; here A=$\theta^T$, B=$X^TX$, C=$I$]

\begin{equation} \frac {\partial^2 J(\theta)} {\partial \theta^2} = X^TX \end{equation}

$X^TX$ is a PSD matrix ($u^TX^TXu=\Vert Xu\Vert^2$) and hence the cost function is convex with respect to $\theta$. That's the first proof.

The 2nd proof goes like this. It requires us to prove that \begin{equation} J(t\theta_1+(1-t)\theta_2)-tJ(\theta_1)-(1-t)J(\theta_2)\leq0 \end{equation} $\forall \theta_1, \theta_2$ and $\forall t \in [0,1]$.

We will call this $E_1$. Note that here \begin{equation} J(\theta) = \frac12( \theta^TX^TX\theta -2Y^TX\theta + Y^TY) \end{equation}

The full expansion of $E_1$ will be slightly verbose but we can make our life easy by considering that for any linear function $f(x)=ax+b$, \begin{equation} f(tx_1+(1-t)x_2)=tf(x_1)+(1-t)f(x_2) \end{equation} You can convince yourself of this by expanding both sides.

This means the term $\frac12( -2Y^TX\theta + Y^TY)$ of $J(\theta)$ will be $0$ in $E_1$. Let us now look at $E_1$ with only the first term of $J(\theta)$ and drop the $\frac12$ for convenience.

\begin{equation} LHS = {(t\theta_1+(1-t)\theta_2)}^TX^TX(t\theta_1+(1-t)\theta_2)-t\theta_1^TX^TX\theta_1-(1-t)\theta_2^TX^TX\theta_2 \end{equation} \begin{equation} LHS = t^2\theta_1^TX^TX\theta_1+(1-t)^2\theta_2^TX^TX\theta_2+2t(1-t)\theta_1^TX^TX\theta_2 -t\theta_1^TX^TX\theta_1-(1-t)\theta_2^TX^TX\theta_2 \end{equation}

[Note that $\theta_1^TX^TX\theta_2 $=$(X\theta_1)^T(X\theta_2)$=$(X\theta_2)^T(X\theta_1)$=$\theta_2^TX^TX\theta_1$]

\begin{equation} LHS = (t^2-t)\theta_1^TX^TX\theta_1+((1-t)^2-(1-t))\theta_2^TX^TX\theta_2+2t(1-t)\theta_1^TX^TX\theta_2 \end{equation}

\begin{equation} LHS = -t(1-t)[\theta_1^TX^TX\theta_1+\theta_2^TX^TX\theta_2-2\theta_1^TX^TX\theta_2] \end{equation}

[Note that $(1-t)^2-(1-t) = t^2-t=-t(1-t)$]

\begin{equation} LHS = -t(1-t)[(\theta_1-\theta_2)^TX^TX(\theta_1-\theta_2)] \end{equation}

\begin{equation} LHS = -t(1-t) \Vert X(\theta_1-\theta_2) \Vert^2 \end{equation}

which is always $\leq0$.

This completes our second proof.

If you are having trouble following the second proof, try to first prove that a scalar quadratic function $f(x)=ax^2+bx+c$ is convex for $a>0$. I promise that exercise will be helpful (since our function for $J(\theta)$ is also quadratic in $\theta$).

$\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.