4
$\begingroup$

The tricky thing of manually implement optimization algorithm is that, even there are some errors, such as wrong gradient, the algorithm still can work in some way, i.e., decrease the objective, and even find the optimal parameters.

I am manually implementing gradient boosting algorithm (gradient descent), can I checking the correct implementation for gradient boosting algorithm by looking at if the loss is monotonically decreasing?

For example, I am plotting objective function for $200$ iterations in left subplot, and plotting the diff(L_trace)>0 in the right subplot.

enter image description here

There are 2 cases in right sub-plot where the objective is not monotonically decreasing, so, can we know something wrong with the algorithm?

Improve this question
$\endgroup$
4
  • $\begingroup$ The best method of validating any gradient descent algorithm is validating the gradient. The usual approach is to get a numeric gradient and check against your calculated version. $\endgroup$
    – horaceT
    Commented Aug 24, 2016 at 17:40
  • $\begingroup$ @horaceT, i agree, however, in my case, even numerical gradient is a little bit hard to calculate. $\endgroup$
    – Haitao Du
    Commented Aug 24, 2016 at 17:45
  • $\begingroup$ A while back I was coding a flavor of deep neural net and I found the 'numDeriv' package quite useful. You feed the 'grad' function with your loss and it spits out the derivative calculated at a point. $\endgroup$
    – horaceT
    Commented Aug 24, 2016 at 17:57
  • $\begingroup$ BTW, not an expert myself, but theano and friends (python world) spare you the headache of coming up with theoretical gradient. They do symbolic differentiation so you just specify the objective function and voila comes the gradient! $\endgroup$
    – horaceT
    Commented Aug 24, 2016 at 18:05

3 Answers 3

Reset to default
7
$\begingroup$

There is something "wrong" with the algorithm, gradient descent (its very name is an example of false advertising). That doesn't mean there is a mistake in your implementation.

Gradient descent, i.e., steepest descent without use of line search or trust regions, need not converge, and can actually diverge, even on a strictly convex function, even in one dimension.

For example, apply gradient descent to the function $f(x) = x^4$. Its gradient is $4x^3$. Apply gradient descent with a learning rate of $1.0$; this is the classic steepest descent, implemented without the protection afforded by line search or trust regions.

Start at $x=1$. The gradient is $4$, so the next point is $-3$. Its gradient is $-108$, so the next point is $105$. its gradient is $4630500$, so the next point is $-4630395$. Hmm, this seems to be diverging. On a nice strictly convex function. Gradient descent has actually achieved monotonic increase in the objective function.

So yes, there is no guarantee gradient descent will descend on every iteration. And even with a smaller learning rate, it may not necessarily be small enough to ensure descent.

Improve this answer
$\endgroup$
2
  • $\begingroup$ if we use back tracking line search, not fixed learning rate, GD will still have no guarantee descend on every iteration? $\endgroup$
    – Haitao Du
    Commented Aug 24, 2016 at 14:46
  • 1
    $\begingroup$ Backtracking line search should ensure descent, presuming that the objective function and gradient evaluations are error-free (i.e., sufficiently accurate and not subject to random or other error). Such an algorithm would not generally be considered to be gradient descent, rather it would be steepest descent with line search. $\endgroup$
    – Mark L. Stone
    Commented Aug 24, 2016 at 14:51
3
$\begingroup$

When I was learning SGD, this[1] left me with a strong impression and I quote Leon Bottou as possible/alternative answer/solution to your question,

"During the last twenty years, I have often been approached for advice in setting the learning rates $\gamma_t$ of some rebellious stochastic gradient descent program. My advice is to forget about the learning rates and check that the gradients are computed correctly. This reply is biased because people who compute the gradients correctly quickly find that setting small enough learning rates is easy. Those who ask usually have incorrect gradients. Carefully checking each line of the gradient computation code is the wrong way to check the gradients. Use finite differences...." (page 8, [1])

[1] Bottou, L. (2012). Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade (pp. 421-436). Springer Berlin Heidelberg.

Improve this answer
$\endgroup$
2
$\begingroup$

Checking your gradient against Finite differences method aka numerical differentiation is a good way to find errors. See this: https://en.wikipedia.org/wiki/Numerical_differentiation

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.