apache/spark — pull request #53 by dbtsai (2014-03-02 07:58:49+00:00)
Title: SPARK-1157 L-BFGS Optimizer based on L-BFGS Java implementation in RISO project.

This will use the L-BFGS java implementation from RISO project (published in maven central) which is direct translation version from the original robust Fortran implementation. (Thanks to the author of L-BFGS java implementation, Robert relicensed his code to commercial friendly Apache 2 license.)

When use with regularized updater, we need compute the regVal and regGradient (the gradient of regularized part in the cost function), and in the currently updater design, it is designed for SGD with adaptive training rate in mind, so we need to do some workarounds to get those two values.

Let's review how updater works when returning newWeights given the input parameters.

w' = w - thisIterStepSize * (gradient + regGradient(w)) Note that regGradient is function of w!
If we set gradient = 0, thisIterStepSize = 1, then
regGradient(w) = w - w'

As a result, for regVal, it can be computed by

val regVal = updater.compute(
weights,
new DoubleMatrix(initialWeights.length, 1), 0, 1, regParam)._2
and for regGradient, it can be obtained by

val regGradient = weights.sub(
updater.compute(weights, new DoubleMatrix(initialWeights.length, 1), 1, 1, regParam)._1)

The PR includes the tests which compare the result with SGD with/without regularization.

We did comparison between LBFGS and SGD, and often we saw 10x less
steps in LBFGS while the cost of per step is the same (just computing
the gradient).

The following is the paper by Prof. Ng at Stanford comparing different
optimizers including LBFGS and SGD. They use them in the context of
deep learning, but worth as reference.
http://cs.stanford.edu/~jngiam/papers/LeNgiamCoatesLahiriProchnowNg2011.pdf