3 ms·

Is there any particular reason why we have conversations on learning rates and not simply use a line-search that finds a point that satisfies the strong Wolfe c

by kxyvr 7y ago

Is there any particular reason why we have conversations on learning rates and not simply use a line-search that finds a point that satisfies the strong Wolfe conditions? https://en.wikipedia.org/wiki/Wolfe_conditions https://en.wikipedia.org/wiki/Wolfe_conditions Unless I'm missing something, optimization theory and practice tells us concretely how to guarantee convergence.

mochomocha 7y ago
Line search is expensive. It costs you 1 pass over the data just for function evaluation. Also, there's only theoretical guarantees in convex cases (and even in these cases, details get murky if you look at L-BFGS and its treatment in Nocedal optimization book for example). Most modern neural networks are optimized over non-convex loss functions and through SGD optimizers which prove to be extremely effective because they make quick progress for super cheap (mandatory plug to this classic NIPS paper: https://papers.nips.cc/paper/3323-the-tradeoffs-of-large-scale-learning.pdf https://papers.nips.cc/paper/3323-the-tradeoffs-of-large-sca...).
- kxyvr 7y ago
  I suppose I don't follow. Strong Wolfe conditions do not require convexity in order to guarantee convergence. If I recall correctly, the requirement for convergence is that the gradient be Lipschitz continuous, not convexity, which should be Theorem 3.2 in Nocedal and Wright's book that you referenced. As far as expense, yes, there is a cost for a line-search. However, machine learning algorithms typically use automatic differentiation (back-propogation) in order to calculus the derivative. This is far more expensive than a function evaluation. As such, in optimization, we generally try to use cheaper computations such as a function evaluation to better capitalize on expensive calculations like the gradient. Essentially, it seems like using a learning rate rather than doing a line search means we're wasting a huge amount of information and doing something that's not guaranteed to converge even if the underlying functions were convex, which they're not.
  - dual_basis 7y ago
    I may be misunderstanding something, but, from the Wikipedia article, checking that the Wolfe conditions hold requires calculation of the gradient at the proposed new point as well. If you're going to do that, you may as well move in the direction of the new gradient, no?
    - kxyvr 7y ago
      No, I don't think so. The derivative required by the Wolfe-conditions is a directional derivative. Even if we're using AD to calculate the derivative, this can be calculated using a forward-mode method, which is cheaper than a reverse mode calculation for the gradient. Of course, even if we wanted to spent the time to calculate the full gradient, if the step is satisfies the Wolfe condition, we can simply save this value and use it on the next iteration. Certainly, if we decide to use a stochastic method, we may not want this new gradient with the current randomization, but then we can always fall back to calculating the directional derivative, which is cheaper. Finally, even if we really, really don't want to do any additional derivatives, we could simply use a trust-region method, which doesn't require a derivative calculation to guarantee convergence. Yes, the model used in a trust-region method has derivatives, but all of these derivatives should be cached when computing the direction in the first place. But, really, if it's bad step because the Wolfe conditions say it's a bad step, then moving to that point is counter-productive, both in theory and practice. We might as well know that before we go there.
      - dual_basis 7y ago
        Your suggestion is very interesting. Here is some recent related work which seems to have explored the idea in more depth: https://arxiv.org/pdf/1703.10034.pdf https://arxiv.org/pdf/1703.10034.pdf
  - thorel 7y ago
    There are a few inaccuracies here: using automatic differentiation basically makes computing the gradient of the objective function as efficient as computing the function itself. But the main goal of algorithms being used in machine learning nowadays (stochastic gradient descent and variants thereof) is to avoid having to compute the objective function or its gradient altogether: instead, the gradient is computed at a single data point (example) which provides an approximation of the true gradient. The important thing is that what is considered expensive is not to compute the objective function or its gradient, but to compute it over the entire dataset. Line-search would require evaluating the function (and its gradient) over the entire dataset several times, which completely defeats the purpose of stochastic gradient descent. One could imagine doing a line search using the approximate function or its gradient (coming from the evaluation at a single data point) as the basis for a line-search, but intuitively it does not make much sense to fine-tune the step size to a single example, and this would in any case destroy the guarantees provided by the Strong Wolfe conditions. Finally, there are convergence guarantees for stochastic gradient descent with fixed learning rate when the objective functions are convex.

by kxyvr 7y ago

mochomocha 7y ago

Line search is expensive. It costs you 1 pass over the data just for function evaluation. Also, there's only theoretical guarantees in convex cases (and even in these cases, details get murky if you look at L-BFGS and its treatment in Nocedal optimization book for example). Most modern neural networks are optimized over non-convex loss functions and through SGD optimizers which prove to be extremely effective because they make quick progress for super cheap (mandatory plug to this classic NIPS paper: https://papers.nips.cc/paper/3323-the-tradeoffs-of-large-scale-learning.pdf https://papers.nips.cc/paper/3323-the-tradeoffs-of-large-sca...).

kxyvr 7y ago
I suppose I don't follow. Strong Wolfe conditions do not require convexity in order to guarantee convergence. If I recall correctly, the requirement for convergence is that the gradient be Lipschitz continuous, not convexity, which should be Theorem 3.2 in Nocedal and Wright's book that you referenced. As far as expense, yes, there is a cost for a line-search. However, machine learning algorithms typically use automatic differentiation (back-propogation) in order to calculus the derivative. This is far more expensive than a function evaluation. As such, in optimization, we generally try to use cheaper computations such as a function evaluation to better capitalize on expensive calculations like the gradient. Essentially, it seems like using a learning rate rather than doing a line search means we're wasting a huge amount of information and doing something that's not guaranteed to converge even if the underlying functions were convex, which they're not.
- dual_basis 7y ago
  I may be misunderstanding something, but, from the Wikipedia article, checking that the Wolfe conditions hold requires calculation of the gradient at the proposed new point as well. If you're going to do that, you may as well move in the direction of the new gradient, no?
  - kxyvr 7y ago
    No, I don't think so. The derivative required by the Wolfe-conditions is a directional derivative. Even if we're using AD to calculate the derivative, this can be calculated using a forward-mode method, which is cheaper than a reverse mode calculation for the gradient. Of course, even if we wanted to spent the time to calculate the full gradient, if the step is satisfies the Wolfe condition, we can simply save this value and use it on the next iteration. Certainly, if we decide to use a stochastic method, we may not want this new gradient with the current randomization, but then we can always fall back to calculating the directional derivative, which is cheaper. Finally, even if we really, really don't want to do any additional derivatives, we could simply use a trust-region method, which doesn't require a derivative calculation to guarantee convergence. Yes, the model used in a trust-region method has derivatives, but all of these derivatives should be cached when computing the direction in the first place. But, really, if it's bad step because the Wolfe conditions say it's a bad step, then moving to that point is counter-productive, both in theory and practice. We might as well know that before we go there.
    - dual_basis 7y ago
      Your suggestion is very interesting. Here is some recent related work which seems to have explored the idea in more depth: https://arxiv.org/pdf/1703.10034.pdf https://arxiv.org/pdf/1703.10034.pdf
- thorel 7y ago
  There are a few inaccuracies here: using automatic differentiation basically makes computing the gradient of the objective function as efficient as computing the function itself. But the main goal of algorithms being used in machine learning nowadays (stochastic gradient descent and variants thereof) is to avoid having to compute the objective function or its gradient altogether: instead, the gradient is computed at a single data point (example) which provides an approximation of the true gradient. The important thing is that what is considered expensive is not to compute the objective function or its gradient, but to compute it over the entire dataset. Line-search would require evaluating the function (and its gradient) over the entire dataset several times, which completely defeats the purpose of stochastic gradient descent. One could imagine doing a line search using the approximate function or its gradient (coming from the evaluation at a single data point) as the basis for a line-search, but intuitively it does not make much sense to fine-tune the step size to a single example, and this would in any case destroy the guarantees provided by the Strong Wolfe conditions. Finally, there are convergence guarantees for stochastic gradient descent with fixed learning rate when the objective functions are convex.