3 ms·
Convex/ non-convex optimisation refers to the shape of the error function we're trying to optimise. In convex optimisation we can assume it's, well, convex:
by YeGoblynQueenne 6y ago
Convex/ non-convex optimisation refers to the shape of the error function
we're trying to optimise. In convex optimisation we can assume it's, well,
convex:
. . ε
\ /
\ /
\ /
\ /
'._ _.'
^
Global optimum
In non-convex optimisation we can't make any assumption about the shape of the
error function:
,--. .--. ε
/ \ / \ ,--.
/ \ / \ / \ /
.' \ / \ / \ /
\ / \ / \ /
`--' \ / `--'
^ \ / ^
| `--' |
| ^ |
| | |
| | |
`--------- Local optima ----------'
"Optimisation" means that we're trying to find an optimum of a function - a
maximum or a minimum. We're usually interested in the minimum of a function,
particularly a function that represents the error of an approximator on a set
of training data. Generally we prefer to find a _global_ minimum of the error
function because then we can expect the resulting approximator to generalise better
to data that was not available during training.
If the error function has a convex shape we're basically guaranteed to find
its global minimum. In non-convex optimisation, we're guaranteed to get stuck
to local minima.
(Ok, the above is a bit tongue in cheek, there's no _guarantee_ of getting
stuck to local minima, but it's very likely).
- dorgo 6y ago>Generally we prefer to find a _global_ minimum of the error function because then we can expect the resulting approximator to generalise better to data that was not available during training. Sorry to nitpick, but is this true? We are doing optimization here and a global minimum is just a better solution than a non-global minimum. Is there a connection to generalisation here?
- cpgxiii 6y agoIn an ML context, the global optima may often correspond to better performance and (hopefully) a more general solution. In a motion planning or controls context, a local minima can often mean a configuration or path that is infeasible due to collision or wildly inefficient.
- YeGoblynQueenne 6y agoI'ts like cpgxiii says. You're right to nitpick though, because there are no certainties. We optimise on a set of data sampled from a distribution that is probably not the real distribution, so there's some amount of sampling error. Even if we find the global optimum of our sampled data, there's no reason why it's going to be close to the global optimum of our testing data. But - there are some guarantees. Under PAC-Learning assumptions we can place an upper bound on the expected error as a function of the number of training examples and the size of the hypothesis space (the set of possible models). The maths is in a paper called Occam's Razor: https://www.sciencedirect.com/science/article/abs/pii/0020019087901141 https://www.sciencedirect.com/science/article/abs/pii/002001... Unfortunately, PAC-Learning presupposes that the sampling distribution is the same as the real distribution, i.e. what I said above we can't know for sure. In any case, I think most people would agree that a model that can reach the global minimum of training error on a large dataset has better chance to reach the global minimum of generalisation error (i.e. in the real world) than a model that gets stuck in local minima on the training data. Modulo assumptions.
- kleiba 6y agoBeautiful ASCII graphs!