8
$\begingroup$

I'm just learning about optimization, and the difference between an analytical solution, and a numerical one. Suppose there is a cost function f(x), and we want to find the value of x which minimizes this. In an analytical solution, we would differentiate with respect to x, i.e. find df(x)/dx. Whereas in a numerical solution, we would try values of x, and see in which direction we need to change x in order to move towards the solution (gradient descent).

It seems to me that the analytical solution is always preferred because it gives you an exact answer. You do not get stuck in local minima and you can be sure that your solution is correct. So why do we not always use analytical solutions?

I understand that numerical solutions make things easier because you don't have to work out by hand the analytical solution, but it seems to me that solving something by hand to get a precise answer is highly preferred to doing it computationally for an approximate answer. Can somebody clear this up for me? Thanks!

$\endgroup$
2
  • 2
    $\begingroup$ Very often there is no analytical solution. Also sometimes the analytical solution is not very practical. Consider $\hat \beta = (X^T X)^{-1} X^T y$ for ordinary least squares regression. This is an exact analytical solution but you would never want to actually use this formula for any real-sized problem (note that there are less naive ways to analytically obtain $\hat \beta$ but this is just an example). In general there are cases where an approximation can produce a result that is practically no different but can be obtained way faster. $\endgroup$ – jld Sep 14 '15 at 13:58
  • 2
    $\begingroup$ Your cost function may not be analytic, which may restrict the non-numerical methods available to you. Even if it is analytic, the solutions to a particular question may be difficult to find analytically. Worse, if you prefer analysis then you may distort your cost function to fit the mathematical tools available to you. As a result you may find a solution which is only optimal based on unrealistic assumptions: if all you have is a hammer, everything looks like a nail. $\endgroup$ – Henry Sep 14 '15 at 16:42
9
$\begingroup$

Your question is interesting, because it is a starting point into optimization in general.

It is maybe better to start with a concrete example on the existence of analytical solution. If you look at your standard polynomial of 2nd degree, $f(x)=ax^2+bx+c$. You have a formula for the zeroes of the function, which is an analytical solution. If you have a polynomial of order 5 or higher, no such formula exists.

This is of course not an optimization problem as in minimizing or maximizing a function, but when you find where the derivative is zero, you are essentially looking for a zero of a function, namely the derivative.

So it seems that you cannot always solve a problem with pen and paper. This is also dependent on the scale of the problem. Sometimes you need to estimate billions of parameters, and it is just not feasible for a human to work out an analytical solution or even find out if it exists.

In the case of ordinary least squares, or fitting a linear model, an analytical solution exist. But it is very easy to change the model slightly, such that no such solution exists, (at least not one we know of). An example of this is the lasso.

So the use of numerical methods is completely justified, both by the fact that an analytical solution may not exist, or it is not feasible to work out such a solution.

$\endgroup$
6
$\begingroup$

I will add another perspective here, which considers the second order Hessian based methods. Often times, to speed up the convergence, gradient based solvers resort to line-search techniques such as Armijo, L-BFGS etc. These are usually preferred over the naive gradient descent (if we are not training deep networks nowadays). L-BFGS family approaches opt to come up with a positive definite approximation to the inverse Hessian (see BFGS recursion). Of course, whenever possible, we like to provide an analytically computed Hessian, whose inverse has to be positive definite. However, for a large body of problems this quantity is indefinite and thus off the shelf optimizers cannot handle the situation. There are methods such as the Moré and Sorensen trust region step, but a widely accepted solution is far from being existent.

This is the reason, for instance, mature optimizers such as Ceres Solver do not allow analytical Hessians, but prefer numerically approximated ones.

$\endgroup$
5
$\begingroup$

There are many reasons which usually dance around one main consideration: convenience.

Often, it's much easier, as you mentioned, to plug the numerical solution than analytical. Say, you have a function $f(x_1,x_2,\dots,x_n)$. If it's a complicated expression, then getting $\bigtriangledown{f}$ and coding it may be cumbersome and error-prone. I mean the typos, not the numerical errors. It's more of an issue in multivariate case, imagine coding all the Hessians! I think that probability of introducing a bug in analytical Hessians is quite high.

Hence, the benefit of using analytical expression could be very marginal, especially in multivariate analysis. So, you go through all this trouble to basically get the same result as numerical approximation in many cases.

In fact, I code analytical expressions for derivatives only when it's absolutely necessary. This is usually the case only when numerical derivatives are far worse in terms of accuracy.

Speed is usually not the factor. It's rare that numerical derivative is slower than analytic one.

I focused only on the numerical derivatives, because they always exist analytically as long as $f(.)$ exists. In other problems such as solving equations, integration, optimization - the problem with analytical solutions is that they don't always exist or are very difficult to find, i.e. feasibility.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.