Line searches

Module containing various line searches.

Line searches are at the heart of many optimizers. After finding a suitable search direction (e.g. the steepest descent direction) we are left with a one-dimensional optimization problem, which can then be solved by a line search.

class climin.linesearch.BackTrack(wrt, f, decay=0.9, max_iter=inf, tolerance=1e-20)

Class implementing a back tracking line search.

The idea is to jump to a starting step length \(t\) and then shrink that step length by multiplying it with \(\gamma\) until we improve upon the loss.

At most max_iter attempts will be done. If the largest absolut value of a component of the step falls below tolerance, we stop as well. In both cases, a step length of 0 is returned.

To not possibly iterate forever, the field tolerance holds a small value (1E-20 per default). As soon as the absolute value of every component of the step (direction multiplied with the scalar from schedule) is less than tolerance, we stop.

Attributes

wrt	(array_like) Parameters over which the optimization is done.
f	(Callable) Objective function.
decay	(float) Factor to multiply trials for the step length with.
tolerance	(float) Minimum absolute value of a component of the step without stopping the line search.

Methods

__init__(wrt, f, decay=0.9, max_iter=inf, tolerance=1e-20)

Create BackTrack object.

Parameters:

wrt : array_like

Parameters over which the optimization is done.

f : Callable

Objective function.

decay : float

Factor to multiply trials for the step length with.

max_iter : int, optional, default infinity

Number of step lengths to try.

tolerance : float

Minimum absolute value of a component of the step without stopping the line search.

search(direction, initialization=1, args=None, kwargs=None, loss0=None)

Return a step length t given a search direction.

Perform the line search along a direction. Search will start at initialization and assume that the loss is loss0 at t == 0.

Parameters:

direction : array_like

Has to be of the same size as .wrt. Points along that direction will tried out to reduce the loss.

initialization : float

First attempt for a step size. Will be reduced by a factor of .decay afterwards.

args : list, optional, default: None

list of optional arguments for .f.

kwargs : dictionary, optional, default: None

list of optional keyword arguments for .f.

loss0 : float, optional

Loss at the current parameters. Will be calculated of not given.

class climin.linesearch.StrongWolfeBackTrack(wrt, f, fprime, decay=None, c1=0.0001, c2=0.9, tolerance=1e-20)

Class implementing a back tracking line search that finds points satisfying the Strong Wolfe conditions.

The idea is to jump to a starting step length \(t\) and then shrink that step length by multiplying it with \(\gamma\) until the strong Wolfe conditions are satisfied. That is the Armijo rule

\[\begin{split}f(\theta_t+ \alpha_t d_t) & \leq f(\theta)+ c_1 \alpha_t d_t^T f'(\theta),\end{split}\]

and the curvature condition

\[\begin{split}\big|d_k^TTf('\theta_t+\alpha_t d_t)\big| & \leq c_2 \big|d_t^T f'(\theta_t)\big|.\end{split}\]

At most max_iter attempts will be done. If the largest absolut value of a component of the step falls below tolerance, we stop as well. In both cases, a step length of 0 is returned.

To not possibly iterate forever, the field tolerance holds a small value (1E-20 per default). As soon as the absolute value of every component of the step (direction multiplied with the scalar from schedule) is less than tolerance, we stop.

Attributes

wrt	(array_like) Parameters over which the optimization is done.
f	(Callable) Objective function.
decay	(float) Factor to multiply trials for the step length with.
tolerance	(float) Minimum absolute value of a component of the step without stopping the line search.
c1	(float) Constant in the strong Wolfe conditions.
c2	(float) Constant in the strong Wolfe conditions.

Methods

__init__(wrt, f, fprime, decay=None, c1=0.0001, c2=0.9, tolerance=1e-20)

Create StrongWolfeBackTrack object.

Parameters:

wrt : array_like

Parameters over which the optimization is done.

f : Callable

Objective function.

decay : float

Factor to multiply trials for the step length with.

tolerance : float

Minimum absolute value of a component of the step without stopping the line search.

class climin.linesearch.ScipyLineSearch(wrt, f, fprime)

Wrapper around the scipy line search.

Methods

class climin.linesearch.WolfeLineSearch(wrt, f, fprime, c1=0.0001, c2=0.9, maxiter=25, min_step_length=1e-09, typ=4)

Port of Mark Schmidt’s line search.

Methods