What algorithms will stuck in the local minimum?

Question

Algorithms like neural network are easily getting stuck in local minimum because the shape of the loss function (so there are parameters like momentum are designed to solve this type of problem). Logistic regression will always find global minimum because log-loss is a convex function (please feel free to correct me if I miss anything here).

Then I am wondering for other algorithms like RandomForest, GradientBoostTree, or SVM, which one would face the problem of stuck in local minimum, which one would not? And why? Thanks!

Answer 1

Any greedy algorithm -- which try to maximize your objetive by choose whichever is locally best -- may get stuck in local minima.

These include, but are not limited to:

• gradient descent optimization like neural networks, which try to gradually minimize the loss function by making small changes to the weights in the direction that minimize the loss. This also includes algorithms like gradient boosting. You can mitigate such problems by using second-order derivatives (Hessian) or smart heuristics.
• one look-ahead algorithms like decision trees, which locally choose the feature $x$ and threshold $t$ whose split $x<t$ maximizes/minimizes a given metric like gini or entropy (and, as a subsequent, random forest) -- if a decision tree was able to see the final impact of all possible combinations, then it might make different choices, but that would be infeasible.
• expectation-maximization (as used by e.g. k-means) is also heavily influenced by the initialization.

I am being a little imprecise in my listing. What defines if an optimization problem may get stuck in a local minima is the function that you are trying to maximize. If you use gradient descent to solve the SVM optimization problem, then you'll always converge to the global minimum. More important than the algorithm is the surface of the optimization problem (in SVM, the objective is a nice quadratic surface).

Also notice that algorithms like Random Forests (when the number of trees is very, very high) become almost deterministic, but they still suffer from getting stuck in local minima. I am point this out because some people confuse optimizations being stuck in local minima with the algorithms being stochastic -- they reason that they can mitigate local minima by making multiple runs of the algorithm. But the algorithm being vulunerable to local minima $\neq$ the algorithm being stochastic. You'll never e.g. fix the one look-ahead problem by running a decision tree or a random forest several times. For algorithms like k-means, it is indeed a good idea to run it several times, as most implementations do behind-the-scenes.

Answer 2

For tree-based algorithms, it depends on the algorithm for building the trees that you use. If you use CART, as in sklearn, CART is by definition a greedy algorithm. For this reason, no one expects to find the global optimum when building a tree. However, local optima might do the job as well. This actually applied to gradient boosting and random forests, as they are built with trees. About SVM, there are two ways to fit an SVM: the dual and primal problem. Both ways involve sloving quadratic optimization problems, which solutions are always globally optimal.