hex.optimization

Class L_BFGS

java.lang.Object

water.Iced

hex.optimization.L_BFGS

All Implemented Interfaces:

java.io.Externalizable, java.io.Serializable, java.lang.Cloneable, water.Freezable

public final class L_BFGS
extends water.Iced

Created by tomasnykodym on 9/15/14. Generic L-BFGS optimizer implementation. NOTE: The solver object keeps its state and so the same object can not be reused to solve different problems. (but can be used for warm-starting/continuation of the same problem) Usage: To apply L-BFGS to your optimization problem, provide a GradientSolver with following 2 methods: 1) double [] getGradient(double []): evaluate ginfo at given coefficients, typically an MRTask 2) double [] getObjVals(double[] beta, double[] direction): evaluate objective value at line-search search points (e.g. objVals[k] = obj(beta + step(k)*direction), step(k) = .75^k) typically a single MRTask

See Also:

L-BFGS will then perform following loop: while(not converged): coefs := doLineSearch(coefs, dir) // distributed, 1 pass over data ginfo := getGradient(coefs) // distributed, 1 pass over data history += (coefs, ginfo) // local dir := newDir(history, ginfo) // local 1 L-BFGS iteration thus takes 2 passes over the (distributed) dataset., Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	L_BFGS.History Keeps L-BFGS history ie curvature information recorded over the last m steps.
static interface	L_BFGS.ProgressMonitor Monitor progress and enable early termination.
static class	L_BFGS.Result

Constructor Summary

Constructors

Constructor and Description
L_BFGS()

Method Summary

Modifier and Type	Method and Description
int	k()
int	maxIter()
L_BFGS	setGradEps(double d)
L_BFGS	setHistorySz(int sz)
L_BFGS	setMaxIter(int m)
L_BFGS	setObjEps(double d)
L_BFGS.Result	solve(OptimizationUtils.GradientSolver gslvr, double[] coefs) Solve the optimization problem defined by the user-supplied ginfo function using L-BFGS algorithm.
L_BFGS.Result	solve(OptimizationUtils.GradientSolver gslvr, double[] beta, OptimizationUtils.GradientInfo ginfo, L_BFGS.ProgressMonitor pm) Solve the optimization problem defined by the user-supplied ginfo function using L-BFGS algorithm.
static double[]	startCoefs(int n, long seed)

Methods inherited from class water.Iced

asBytes, clone, copyOver, frozenType, read, readExternal, readJSON, reloadFromBytes, toJsonBytes, toJsonString, write, writeExternal, writeJSON

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

L_BFGS

public L_BFGS()

Method Detail

setMaxIter

public L_BFGS setMaxIter(int m)

setGradEps

public L_BFGS setGradEps(double d)

setObjEps

public L_BFGS setObjEps(double d)

setHistorySz

public L_BFGS setHistorySz(int sz)

k

public int k()

maxIter

public int maxIter()

solve

public final L_BFGS.Result solve(OptimizationUtils.GradientSolver gslvr,
                                 double[] beta,
                                 OptimizationUtils.GradientInfo ginfo,
                                 L_BFGS.ProgressMonitor pm)

Solve the optimization problem defined by the user-supplied ginfo function using L-BFGS algorithm. Will result into multiple (10s to 100s or even 1000s) calls of the user-provided ginfo function. Outside of that it does only limited single threaded computation (order of number of coefficients). The ginfo is likely to be the most expensive part and key for good perfomance.

Parameters:

gslvr - - user ginfo function

beta - - starting solution

Returns:

Optimal solution (coefficients) + ginfo info returned by the user ginfo function evaluated at the found optmimum.

solve

public final L_BFGS.Result solve(OptimizationUtils.GradientSolver gslvr,
                                 double[] coefs)

Solve the optimization problem defined by the user-supplied ginfo function using L-BFGS algorithm. Will result into multiple (10s to 100s or even 1000s) calls of the user-provided ginfo function. Outside of that it does only limited single threaded computation (order of number of coefficients). The ginfo is likely to be the most expensive part and key for good perfomance.

Parameters:

gslvr - - user ginfo function

Returns:

Optimal solution (coefficients) + ginfo info returned by the user ginfo function evaluated at the found optmimum.

startCoefs

public static double[] startCoefs(int n,
                                  long seed)