How to check whether my loss function is convex or not?

Question

Loss functions are useful in calculating loss and then we can update the weights of a neural network. The loss function is thus useful in training neural networks.

Consider the following excerpt from this answer

In principle, differentiability is sufficient to run gradient descent. That said, unless $L$ is convex, gradient descent offers no guarantees of convergence to a global minimiser. In practice, neural network loss functions are rarely convex anyway.

It implies that the convexity property of loss functions is useful in ensuring the convergence, if we are using the gradient descent algorithm. There is another narrowed version of this question dealing with cross-entropy loss. But, this question is, in fact, a general question and is not restricted to a particular loss function.

How to know whether a loss function is convex or not? Is there any algorithm to check it?

Answer 1

It is the same as other functions. You can use Theorem 2 in this lecture (from Princeton University):

(ii) condition is about the first-order condition for convexity and (iii) is the second-order. You can also find more detail in chapter 3 of this book ("Convex Optimization" by Stephen Boyd and Lieven Vandenberghe).

Answer 2

For the case of at least twice differentiable functions, the answer is given by @OmG - you need to look at the eigenvalues of Hessian.

For the 1-dimensional case the picture is rather intuitive:

If the function grows faster then linear with deviation from the minimum, then the function is convex.

For multidimensional case for any projection on a plane, cutting the loss hypersurface you need to have the same picture as for 1-dimensional case. This is satisfied, provided, that the Hessian matrix is positive definite.

If the function is not twice differentiable, the situation becomes more complicated, and I am not aware of any general algorithm.

However, for the case of piecewise-linear function, you can imagine something like $|x|$, or a more general function like: $$ f(x) = \begin{cases} \alpha x & \alpha > 0, x > 0 \\ \beta x & \beta < 0, x < 0 \end{cases} $$

If any section of the loss hypersurface in the vicinity of such a singularity has this form - the function will be convex as well.