2
$\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?

$\endgroup$
  • $\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 Aug 24 '16 at 17:40
  • $\begingroup$ @horaceT, i agree, however, in my case, even numerical gradient is a little bit hard to calculate. $\endgroup$ – Haitao Du Aug 24 '16 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 Aug 24 '16 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 Aug 24 '16 at 18:05
4
$\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.

$\endgroup$
  • $\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 Aug 24 '16 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 Aug 24 '16 at 14:51
2
$\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.

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

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