1
$\begingroup$

In reading about machine learning (ML), and working through some basic examples, it appears to me most learning algorithms use generic optimizers. I am using the word "optimizer" to describe the technique the learner uses to minimize the loss function. Gradient decent, and it's variants, seems to be the most common. But the general idea in ML seems to be to continually iterate a learning algorithm, each time adjusting various things to try to improve the loss.

Gradient decent, and similar techniques, are generic in that they work on a wide variety of learning models. This makes intuitive sense, all you need is the predicted value and the known target value.

But, often the trade-off with generic techniques is that while they work everywhere, they are slow. In other words, in theory you could construct a learner-specific optimizer that exploits characteristics of the learning algorithm to avoid some of the work that something like SGD might have to do. So if you know you're going to use learning algorithm XYZ, then maybe you can speed up computation considerably by using a loss-minimizing technique designed explicitly for learner XYZ.

As a rough analogy, since my background is in programming, consider sorting algorithms. Quicksort is often cited as the best general sorting algorithm. But if you know in advance that your data is constrained in certain ways, other algorithms will be faster, given a specific use-case (even good old bubblesort can be fast if conditions are right!).

So, that's the question: have learner-specific optimizers been developed? (And a related question, is "optimizer" the right word to use here?)

(FWIW, I posted this same question to Kaggle Q&A, but didn't get any responses there.)

$\endgroup$
2
$\begingroup$

I would argue and say that different machine learning algorithms use different optimization algorithms. Linear regression has a direct solution $(X'X)^{-1}X'Y$. For logistic regression sklearn python library uses a Liblinear C++ library. The library uses "a trust region Newton method". SGD (Stochastic Gradient Descent) with Backpropagation is mainly used in neural networks and I did not hear about both of them before implementing my first neural network. LightGBM and XGBoost use their own invented heuristics to build decision trees.

Generally speaking most of ML algorithms are fast. If the training time is in seconds there is no need to optimize the time of algorithm execution. If the training time is actually in years (most recent papers on neural networks by Google where they use hundreds of GPUs and CPUs) then you definitely start thinking about speed optimization.

SGD is supposed to be inferior to other algorithms because it uses only first derivatives. The problem with the neural networks is that the gradient changes too fast and the calculation of the second derivative appears too costly (There are papers that benchmark it). SGD was specifically optimized for neural networks with momentum calculations and reducing learning rate after the networks stopped training. Constant attempts are made to improve it, for example ADAM. But ADAM is still considered to perform worse on validation sets (There was a big benchmark paper about it).

There are some papers that try to use neural networks to choose the direction of the descent instead of using SGD. Papers show some marginal improvements in speed but the algorithms are still not used as the main method of optimization.

Lots of other algorithms are tried for neural networks. For example, genetic algorithms. There are papers that use the idea of "stochastic" in SGD for genetic algorithms. According to their benchmarks they achieve 1/10th of the speed of SGD. They argue that the best neural networks are influenced a lot by the ability of SGD to find a minimum (like ResNet with residual links). But if you choose genetic algorithms then maybe it is possible to use more complicated neural networks where SGD actually fails.

In term of how to call the algorithms.

I prefere the name "optimization algorithm" or "algorithm used for training". But for some of the ML methods "optimization algorithm" sounds wrong. LightGBM and XGBoost have pretty complicated algorithms of building trees where they balance between optimization of a score (logloss or sum of squares) and using other algorithms to fight overfitting. Decision trees could be trained to zero error but then they are one of the worst predictors for the validation set. LightGBM and XGBoost do not reduce their errors to zero and thus allow to win most of machine learning competitions with structured data on Kaggle.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, appreciate the detailed response! Any chance you could point me to additional resources (papers, books, etc) on this topic? $\endgroup$ – Matt Nov 1 '18 at 14:28
  • $\begingroup$ I will find an evening and collect all the links. It is almost all papers. Even ADAM vs SGD is a highly cited paper. $\endgroup$ – keiv.fly Nov 1 '18 at 14:39

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.