21
$\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$
8
  • 6
    $\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
  • 2
    $\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
  • 4
    $\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
17
$\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$
9
  • 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
  • $\begingroup$ @DeltaIV and Cliff - Hmm, exact line search could be very expensive (actual minimization in the direction of the gradient), but backtracking line search can be done by testing the Loss function value in the direction of the gradient by simply doing a few forward passes (which iterative mini-batch and SGD requires anyways). Could not one argue that iterating these two steps feed forward + backpropagation would actually be more expensive than testing feed-forward for multiple step sizes? $\endgroup$
    – Josh
    Jun 1 '20 at 17:23
  • $\begingroup$ @Josh: I may be confused on your question, but the key point is that even evaluating the target objective once scales with the sample size, while a single batch does not. So just doing a single check of the loss function is often orders of magnitude more expensive than the actual SGD step meaning you immediately lose the advantage of SGD: fast updates. $\endgroup$
    – Cliff AB
    Jun 1 '20 at 19:16
  • $\begingroup$ Thanks @CliffAB but doesn't SGD also technically evaluate the loss (on the batch) on each step as the first step in backpropagation to compute the gradient? i.e. I'm not suggesting backtracking line search on the full Loss, but on the Loss on the batch (I know that wouldn't be backtracking line search on the full Loss per se) $\endgroup$
    – Josh
    Jun 1 '20 at 20:20
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$
20
  • 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
    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
    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
    Jan 5 '18 at 19:48
2
$\begingroup$

This question was asked in early 2018, but if you still wait for an answer then: Yes, now there are some implementation of line search in DNN with good performances. See:

https://arxiv.org/abs/1808.05160 (published in 2 journals)

and more recently, by a different group:

https://arxiv.org/abs/1905.09997 (published in ICML).

It is important to note that instead of many claims: 1st, the theoretical results in the stochastic settings are not strong enough (for convex functions only, most DNN are highly nonconvex) and 2nd, implementation in DNN requires some modifications to suit with mini-batch practice (stochastic optimisation, while close, is not the same as mini-batch practice).

P.S. The performances were done on CIFAR10 and CIFAR100. Now more resources and personnel needed to check with a larger range of datasets/DNN.

You can also look at the Wikipedia page:

https://en.wikipedia.org/wiki/Backtracking_line_search

$\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.