What Does Make an Error Surface Convex? Is It Determined by the Covarinace Matrix or the Hessian?

Question

I am currently learning about least-squares (and other) estimations for regression, and from what I am also reading in some adaptive algorithm literatures, often times the phrase "... and since the error surface is convex..." appears and any depth as to why it is convex to begin with is no where to be found.

...So what exactly makes it convex?

I find this repeated omission mildly annoying because I want to be able to design my own adaptive algorithms, with my own cost functions, but if I cannot tell whether or not my cost function yields a convex error surface or not, I wont be able to get too far in applying something like gradient descent because there wont be a global minimum. Maybe I want to get creative - maybe I do not want to use least-squares as my error criteria for example.

Upon digging deeper, (and my questions begin here), I found that in order to be able to tell if you have a convex error surface, you must make sure that your Hessian matrix is positive semi-definite. For symmetric matricies, this test is simple - simply make sure all the eigenvalues of the Hessian matrix are non-negative. (If your matrix is not symmetric, you can make it symmetric by adding it to its own transpose and performing the same eigenvalue test, by virtue of the Gramian, but thats not important here).

What is a Hessian matrix? The Hessian matrix codifies all the possible combination of the partials of your cost function. How many partials are there? As many as the number of features in your feature vector. How to compute the partials? Take the partial derivatives 'by hand' from the original cost function.

So that is exactly what I did: I assume that we have an $m$ x $n$ data matrix, denoted by the matrix $X$, where, $m$ denotes the number of examples, and $n$ denotes the number of features per example. (which will also be the number of partials). I suppose we can say that we have $m$ time samples and $n$ spatial samples from sensors, but the physical application is not too important here.

Furthermore, we also have a vector $y$ of size $m$ x $1$. (This is your 'label' vector, or your 'answer' corresponding to every row of $X$). For simplicity, I have assumed $m=n=2$ for this particular example. So 2 'examples' and 2 'features'.

So now suppose that you want to ascertain the 'line' or polynomial of best fit here. That is, you project your input data features against your polynomial co-efficient vector $\boldsymbol{\theta}$ such that your cost function is:

$$ J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \bigg[\theta_{0}x_{0}[i] + \theta_{1}x_{1}[i] - y[i]\bigg]^{2} $$

Now, let us take the first partial derivative w.r.t $\theta_{0}$, (feature 0) Thus:

$$ \frac{\delta J(\theta)}{\delta\theta_0} = \frac{1}{m}\sum_{i=1}^{m} \bigg[\theta_{0}x_{0}[i] + \theta_{1}x_{1}[i] - y[i]\bigg] x_{0}[i] $$

$$ \frac{\delta J(\theta)}{\delta\theta_0} = \frac{1}{m}\sum_{i=1}^{m} \bigg[\theta_{0}x_{0}^{2}[i] + \theta_{1}x_{1}[i]x_{0}[i] - y[i]x_{0}[i]\bigg] $$

Now, let us compute all the second partials, so:

$$ \frac{\delta^{2} J(\theta)}{\delta\theta_0^{2}} = \frac{1}{m}\sum_{i=1}^{m} x_{0}^{2}[i] $$

$$ \frac{\delta^{2} J(\theta)}{\delta\theta_0\theta_{1}} = \frac{1}{m}\sum_{i=1}^{m} x_{0}[i]x_{1}[i] $$

$$ \frac{\delta^{2} J(\theta)}{\delta\theta_1\theta_{0}} = \frac{1}{m}\sum_{i=1}^{m} x_{1}[i]x_{0}[i] $$

$$ \frac{\delta^{2} J(\theta)}{\delta\theta_1^{2}} = \frac{1}{m}\sum_{i=1}^{m} x_{1}^{2}[i] $$

We know that the Hessian is nothing but:

$$ H(J(\theta)) = \begin{bmatrix} \frac{\delta^{2} J(\theta)}{\delta\theta_0^{2}} & \frac{\delta^{2} J(\theta)}{\delta\theta_0\theta_{1}} \\ \frac{\delta^{2} J(\theta)}{\delta\theta_1\theta_{0}} & \frac{\delta^{2} J(\theta)}{\delta\theta_1^{2}}\end{bmatrix} $$

$$ H(J(\theta)) = \begin{bmatrix} \frac{1}{m}\sum_{i=1}^{m} x_{0}^{2}[i] & \frac{1}{m}\sum_{i=1}^{m} x_{0}[i]x_{1}[i] \\ \frac{1}{m}\sum_{i=1}^{m} x_{1}[i]x_{0}[i] & \frac{1}{m}\sum_{i=1}^{m} x_{1}^{2}[i] \end{bmatrix} $$

Now, based on how I have constructed the data matrix $X$, (my 'features' go by columns, and my examples go by rows), the Hessian appears to be:

$$ H(J(\theta)) = X^{T}X = \Sigma $$

...which is nothing but the sample covariance matrix!

So I am not quite sure how to interpret - or I should say, I am not quite sure how generalizing I should be here. But I think I can say that:

• Always true:

  • The Hessian matrix always controls whether or not your error/cost surface is convex.
  • If you Hessian matrix is pos-semi-def, you are convex, (and can happily use algorithms like gradient descent to converge to the optimal solution).

• True for LSE only:

  • The Hessian matrix for the LSE cost criterion is nothing but the original covariance matrix. (!).
  • To me this means that, if I use LSE criterion, the data itself determines whether or not I have a convex surface? ... Which would then mean that the eigenvectors of my covariance matrix somehow have the capability to 'shape' the cost surface? Is this always true? Or did it just work out for the LSE criteria? It just doesnt sit right with me that the convexity of an error surface should be dependent on the data.

So putting it back in the context of the original question, how does one determine whether or not an error surfance (based on some cost function you select) is convex or not? Is this determination based on the data, or the Hessian?

Thanks

TLDR: How, exactly, and practically do I go about determining whether my cost-function and/or data-set yield a convex or non-convex error surface?

Answer 1

You can think of linear-least squares in single dimension. The cost function is something like $a^{2}$. The first derivative (Jacobian) is then $2a$, hence linear in $a$. The second derivative (Hessian) is $2$ - a constant.

Since the second derivative is positive, you are dealing with convex cost function. This is eqivalent to positive definite Hessian matrix in multivariate calculus.

You deal with just two variables ($\theta_{1}$, $\theta_{2}$) thus the Hessian is particularly simple.

In practice, however, there are often many variables involved, so it is impractical to build and inspect Hessian.

More efficient method is to work directly on the Jacobian matrix $J$ in the least-squares problem:

$$Jx=b$$

$J$ can be rank-deficient, singular or near-singular. In such cases, the quadratic surface of the cost function is almost flat and/or wildly stretched in some direction. You can also find that your matrix is theoretically solvable, but the solution is numerically unstable. A method of preconditioning can be used to cope with such cases.

Some algorithms simple run a Cholesky decomposition of $J$. If the algorithm fails, it means that $J$ is singular (or ill-conditioned).

Numerically more stable, but more expensive is a QR decomposition, which also exists only if $J$ is regular.

Finally, the state-of-the art method is a Singular Value Decomposition (SVD), which is most expensive, can be done on every matrix, reveals numerical rank of $J$ and allows you to treat rank-deficient cases separately.

I wrote an article about linear and non-linear least squares solutions that covers these topics in detail:

Linear and Nonlinear Least-Squares with Math.NET

There are also references to great books that deal with advanced topics related to least-squares (covariance in parameters/data points, preconditioning, scaling, orthogonal distance regression - total least-squares, determining precision and accuracy of the least-squares estimator etc.).

I have made a sample project for the article, which is open source:

LeastSquaresDemo - binary

LeastSquaresDemo - source (C#)

Answer 2

"So putting it back in the context of the original question, how does one determine whether or not an error surfance (based on some cost function you select) is convex or not? Is this determination based on the data, or the Hessian?"

It's always the Hessian. For a least squares cost function, the Hessian is always positive-semidefinite (PSD). Why?

To understand this, it's important to understand what PSD means. If a matrix, $A \in \mathbb{R}^{N \times N}$, is PSD, then for any vector, $v \in \mathbb{R}^{N \times 1}$, it satisfies the property $v^\top A v \geq 0 \ \forall \ v $

Now, as you have correctly derived, $H(J(\theta)) = X^\top X = \Sigma$. It is easy to prove that any covariance matrix, by virtue of its definition, is PSD. Let us take any vector, $v$ with the same size as the number of columns in $X$, and see if the inequality is satisfied,

\begin{align} v^\top \Sigma v &= v^\top (X^\top X) v \\ &= (Xv)^\top (Xv). \ \ Let \ Xv = z, \\ &= z^\top z \geq 0 \ \forall \ z \end{align} Since $z^\top z$ is a quadratic function, it is guaranteed to be greater than, or equal to zero, thus satisfying the PSD criteria.