18
$\begingroup$

A lot of tutorials online talk about gradient descent and almost all of them use a fixed step size (learning rate $\alpha$). Why is there no use of line search (such as backtracking line search or exact line search)?

$\endgroup$
  • 5
    $\begingroup$ "And almost all of them use a fixed step size" - are you sure? "learning rate" hyper parameters are supposed to adapt the step size to the conditions. A very popular Adam algorithm does adapt the step size $\endgroup$ – Aksakal Jan 4 '18 at 18:44
  • 1
    $\begingroup$ hmm, actually adaptive step size gradient methods have been around since at least 2011, and they are even cited on the Wikipedia Stochastic gradient descent page. It's not exactly hot news. Even vanilla SGD is nearly always used with a learning rate which changes with the number of iterations (schedule). Now, a very good question would be: why, even if there are so many adaptive gradient descent methods, SGD still dominates the Deep Learning world? The question is much less trivial than it might seem. $\endgroup$ – DeltaIV Jan 4 '18 at 18:47
  • 1
    $\begingroup$ Backtracking line-search fixes a direction and then looks for a way to reduce the function. So unless you have an intelligent way of picking the direction to search in, you're in for a tedious optimization. $\endgroup$ – Alex R. Jan 4 '18 at 18:54
  • 1
    $\begingroup$ I don't see that line search makes sense for SGD (as opposed to [batch] gradient descent) - so I would say that's the reason. $\endgroup$ – seanv507 Jan 4 '18 at 19:30
  • 3
    $\begingroup$ I suspect the reason why line search is not very popular is the batching in gradient descent. You get a batch, then compute the gradient. It doesn't make a lot of sense to be going back and forth the line because of the noise in the gradient. It's better to keep going with the next batch while maybe annealing the step size. $\endgroup$ – Aksakal Jan 5 '18 at 4:19
14
$\begingroup$

Vanilla gradient descent can be made more reliable using line searches; I've written algorithms that do this and it makes for a very stable algorithm (although not necessarily fast).

However, it makes almost no sense to do a line search for stochastic gradient methods. The reason I say this is that if we do a line search based on minimizing the full loss function, we've immediately lost one of the main motivations for doing stochastic methods; we now need to compute the full loss function for each update, which typically has computational cost comparable to computing the full first derivative. Given that we wanted to avoid computing the full gradient because of computational costs, it seems very unlikely that we want be okay with computing the full loss function.

Alternatively, you might think of doing something like a line search based on your randomly sampled data point. However, this isn't a good idea either; this will tell you nothing about whether you have stepped too far (which is the main benefit of line searches). For example, suppose you are performing logistic regression. Then each outcome is simply a 0 or 1, and for any single sample, we trivially get perfect separation so the optimal solution for our regression parameters based on the sample of 1 is trivially $-\infty$ or $\infty$ by the Hauck Donner effect. That's not good.

EDIT

@DeltaIV points out that this also applies to mini-batch, not just individual samples.

$\endgroup$
  • 4
    $\begingroup$ very nice (+1), but I'm not sure why in the last example you talk about a single sample. I agree that computing the line search based on a mini-batch makes no sense, but a mini-batch still contains 512 samples (usually, and when talking about ImageNet): of course there's no fixed value for the number of samples in a mini-batch, but 1 sample mini-batches feel a bit extreme. Did you use them just to make your point more clear, or am I missing something? $\endgroup$ – DeltaIV Jan 5 '18 at 9:20
  • 2
    $\begingroup$ @DeltaIV: single sample is mostly to make a point about how bad it could be on a very simple problem. If we did mini-batch with 512 samples on logistic regression with 512+ covariates, we would see the same issue. $\endgroup$ – Cliff AB Jan 5 '18 at 17:08
10
$\begingroup$

The tutorials talk about gradient descent presumably because it is one of the simplest algorithms used for optimization, so it is easy to explain. Since most of such tutorials are rather brief, they focus on simple stuff. There are at least several popular optimization algorithms beyond simple gradient descent that are used for deep learning. Actually people often use different algorithms then gradient descent since they usually converge faster. Some of them have non-constant learning rate (e.g. decreasing over time). For review of such algorithms you can check the An overview of gradient descent optimization algorithms post by Sebastian Ruder (or the arXived paper).

$\endgroup$
  • 2
    $\begingroup$ @DeltaIV: All the "other" fancy methods are built on top of SGD. The main issue is that the other methods take advantage of local knowledge to make more efficient jumps, rather than just randomly sampling points to compute the gradient on. But SGD is so simple and fast, and it's not completely terrible on its own. $\endgroup$ – Alex R. Jan 4 '18 at 19:11
  • 2
    $\begingroup$ @AlexR. the point is neither that SGD is simple and/or fast. Simplicity doesn't matter, since all decent libraries implement SGD, Adam,AdaGrad and RMSProp (and more, sometimes). Speed matters even less, because the time spent by, e.g., Adam, to compute the parameter-level updates is infinitesimal compared to the overall training time of a model like ResNet. The only point is that, for some reason we do not fully understand today, SGD generalizes better than them. So basically if you want to beat SOTA, you're often forced to use it, or at least to switch to it later on during training. $\endgroup$ – DeltaIV Jan 4 '18 at 19:47
  • 3
    $\begingroup$ @DeltaIV Very interesting. I opened the paper you linked to, and it references Wilson et al 2017 preprint for the claim that SGD generalizes better than Adam etc.; so when you say that it's "well-known", you mean well-known since around half a year, right? $\endgroup$ – amoeba says Reinstate Monica Jan 4 '18 at 23:47
  • 2
    $\begingroup$ @DeltaIV Thanks. I am not doing much of the deep learning myself, and I was not aware of that at all. Back in 2012 or so when I was watching Hinton's Coursera lectures, he was mainly advocating RMSprop and in recent 1-2 years my impression was that everybody is using Adam (which supersedes RMSprop, according to the Adam paper). When I was playing with autoencoders last year, I realized that Adam works much faster than SGD, and since then just assumed that Adam is a default choice nowadays. $\endgroup$ – amoeba says Reinstate Monica Jan 5 '18 at 10:22
  • 3
    $\begingroup$ @CliffAB Yes, the relationship between early stopping and regularization can be clearly seen for least squares, where gradient descent operates in the eigenvalue basis and small eigenvalues are the last ones to converge; whereas ridge penalty also penalizes small eigenvalues. I had now only a quick glance into Wilson et al. linked above, but at least in their least squares example SGD vs Adam different is not explained by early vs late stopping. They claim that they converge to different solutions. $\endgroup$ – amoeba says Reinstate Monica Jan 5 '18 at 19:48

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.