Backtracking Line Search

Choose the step size for one gradient descent step with backtracking line search.

A fixed learning rate is a guess. Line search instead tries a large step and shrinks it until the step gives a large enough decrease in the function. The test it uses is the Armijo condition. For the direction -g, where g is the gradient at x, a step size t is accepted when

f(x - t * g) <= f(x) - alpha * t * dot(g, g)

Start with t = t0. While the condition fails, multiply t by beta. Return the first t that passes. Stop after max_iter shrinks and return the current t if no step passes.

Function signature

def backtracking_step(f, grad_fn, x, t0=1.0, alpha=0.3, beta=0.5, max_iter=50):

Example

Input

f = lambda x: float(np.sum(x ** 2))
grad_fn = lambda x: 2 * x
backtracking_step(f, grad_fn, np.array([1.0]))

Output

0.5

Reasoning

At x = 1 the gradient is 2 and f(x) = 1. With t = 1 the new point is -1, and f(-1) = 1 is not below 1 - 0.3 * 1 * 4 = -0.2, so the step is too long. With t = 0.5 the new point is 0, and f(0) = 0 is below 1 - 0.3 * 0.5 * 4 = 0.4, so 0.5 is accepted.

Constraints and notes

• x is a 1D array. f returns a float.
• Compute the gradient and f(x) once, not once per trial step.
• 0 < alpha < 0.5 and 0 < beta < 1.