# Convex loss optimization and supervised learning

I once heard the following statement from the web

Convex loss functions and nonlinear classification are two important concepts in supervised learning.

I do not know why this statement can be made? Or what are the roles that convex loss functions and nonlinear classifications play in developing supervised learning algorithms?

A convex loss function that has a minimum guarantees that there is a minimum loss that can be reached by going "downhill" from whatever point you're at. So your supervised learning algorithm, which is typically trying to minimize some loss function, will (unless something goes wrong) be able to find the "best" result, where "best" is relative to the specified loss function. Without convexity, you might have multiple local minima, and your algorithm can find one which is, local minimum though it may be, nonetheless very poor relative to the global minimum.

Edit: As mbq points out in comments, some algorithms will still be able to find global minima (under certain conditions), but many algorithms are local optimizers that use convexity assumptions because it makes finding a minimum a lot simpler.

Nonlinear classification is important because it greatly expands the possibilities for good classification rules. Linear rules imply that everything on one side of a straight line (plane in multiple dimensions) gets one classification, everything on the other gets the other (if there are two classes.) Nonlinear rules allow much more flexibility, e.g., everything inside a circle gets one classification, everything outside gets another. Of course, you can mimic a nonlinear classification rule by transforming your inputs to a linear classification rule appropriately, but what is appropriate? Much better to have an algorithm in effect figure that out for you, more or less, than have to guess, and guess, and guess again - unless of course you already have a good idea.

• It is certainly false that one cannot find minimum without convexity -- it is just way harder, yet still in range.
– user88
Commented Dec 5, 2011 at 23:11

Just to add to @jbowman's answer (+1), while many machine learning algorithms that are commonly used today (e.g. support vector machines, radial basis funcion neural networks) involve convex optimisation problems, these algorithms generally have hyper-parameters (such as kernel and regularisation parameters). These also need to be tuned and the algorithm itself is often only convex for fixed values of the hyper-parameters. The optimisation problem for tuning the hyper-parameters on the other hand is generally non-convex, so overall the problem of local minima has not been eliminated, merely shiften from the first level of inference (optimising the model parameters) to the second level of inference (model selection i.e. optimising the hyper-parameters).

It is also worth noting that seeking a global optimum of a training criterion based on the loss over a finite sample of data is a bit of a recipe for over-fitting. For example early stopping is a method often used to avoid over-fitting in multi-layer perceptron neural networks, where better generalisation is obtained by stopping even before reaching a local minimum.

This not to say that convexity is not a good thing, of course!