10
$\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$
4
  • $\begingroup$ Cross posted here http://stats.stackexchange.com/questions/69106/proof-of-convexity-of-linear-least-squares $\endgroup$
    – Avraham
    Sep 3, 2013 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, 2013 at 1:49
  • 1
    $\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, 2019 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$ Dec 18, 2019 at 17:16

5 Answers 5

19
$\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$
8
  • $\begingroup$ How were you able to differentiate ϕ twice? $\endgroup$
    – dot_zero
    May 4, 2017 at 4:02
  • $\begingroup$ Also, is the second derivative the Hessian? $\endgroup$
    – dot_zero
    May 4, 2017 at 6:18
  • 1
    $\begingroup$ The first derivative is incorrect. You're adding a row vector to a column vector. $\endgroup$ Sep 28, 2017 at 9:16
  • $\begingroup$ can anyone explain me how do we reach the first derivative? $\endgroup$ Jan 12, 2018 at 6:30
  • 2
    $\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$ Jan 12, 2018 at 11:07
10
$\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$
2
  • $\begingroup$ Can you expand on "after calculation"? $\endgroup$
    – vega
    Dec 7, 2017 at 15:01
  • $\begingroup$ @vega You can use the fact that $\Vert \mathbf{x}\Vert^2 = \mathbf{x}^T\mathbf{x}$. $\endgroup$ Jan 12, 2018 at 11:10
1
$\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$

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$
1
  • $\begingroup$ I just noted the copper.hat's comment above. This answer in fact just elaborated his comment. $\endgroup$
    – syeh_106
    Nov 26, 2019 at 6:55
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .