In (unconstrained) mathematical optimization, a backtracking line search is a line search method to determine the amount to move along a given search direction. Its use requires that the objective function is differentiable and that its gradient is known.
The method involves starting with a relatively large estimate of the step size for movement along the line search direction, and iteratively shrinking the step size (i.e., "backtracking") until a decrease of the objective function is observed that adequately corresponds to the amount of decrease that is expected, based on the step size and the local gradient of the objective function. A common stopping criterion is the Armijo–Goldstein condition.
Backtracking line search is typically used for gradient descent (GD), but it can also be used in other contexts. For example, it can be used with Newton's method if the Hessian matrix is positive definite.
Motivation Given a starting position and a search direction , the task of a line search is to determine a step size that adequately reduces the objective function (assumed i.e. continuously differentiable), i.e., to find a value of that reduces relative to . However, it is usually undesirable to devote substantial resources to finding a value of to precisely minimize . This is because the computing resources needed to find a more precise minimum along one particular direction could instead be employed to identify a better search direction. Once an improved starting point has been identified by the line search, another subsequent line search will ordinarily be performed in a new direction. The goal, then, is just to identify a value of that provides a reasonable amount of improvement in the objective function, rather than to find the actual minimizing value of .
The backtracking line search starts with a large estimate of and iteratively shrinks it. The shrinking continues until a value is found that is small enough to provide a decrease in the objective function that adequately matches the decrease that is expected to be achieved, based on the local function gradient
Define the local slope of the function of along the search direction as (where denotes the dot product). It is assumed that is a vector for which some local decrease is possible, i.e., it is assumed that .
Based on a selected control parameter , the Armijo–Goldstein condition tests whether a step-wise movement from a current position to a modified position achieves an adequately corresponding decrease in the objective function. The condition is fulfilled, see , if
This condition, when used appropriately as part of a line search, can ensure that the step size is not excessively large. However, this condition is not sufficient on its own to ensure that the step size is nearly optimal, since any value of that is sufficiently small will satisfy the condition.
Thus, the backtracking line search strategy starts with a relatively large step size, and repeatedly shrinks it by a factor until the Armijo–Goldstein condition is fulfilled.
The search will terminate after a finite number of steps for any positive values of and that are less than 1. For example, Armijo used for both and in .
Algorithm This condition is from . Starting with a maximum candidate step size value , using search control parameters and , the backtracking line search algorithm can be expressed as follows: Set and iteration counter . Until the condition is satisfied that repeatedly increment and set Return as the solution.
In other words, reduce by a factor of in each iteration until the Armijo–Goldstein condition is fulfilled.
Function minimization using backtracking line search in practice
In practice, the above algorithm is typically iterated to produce a sequence , , to converge to a minimum, provided such a minimum exists and is selected appropriately in each step. For gradient descent, is selected as .
The value of for the that fulfills the Armijo–Goldstein condition depends on and , and is thus denoted below by . It also depends on , , and of course, although these dependencies can be left implicit if they are assumed to be fixed with respect to the optimization problem.
The detailed steps are thus, see , : Choose an initial starting point and set the iteration counter . Until some stopping condition is satisfied, choose a descent direction , update the position to , and increment . Return as the minimizing position and as the function minimum.
To assure good behavior, it is necessary that some conditions must be satisfied by . Roughly speaking should not be too far away from . A precise version is as follows (see e.g. ). There are constants so that the following two conditions are satisfied: For all n, . Here, is the Euclidean norm of . (This assures that if , then also . More generally, if , then also .) A more strict version requires also the reverse inequality: for a positive constant . For all n, . (This condition ensures that the directions of and are similar.)
Lower bound for learning rates
This addresses the question whether there is a systematic way to find a positive number - depending on the function f, the point and the descent direction - so that all learning rates satisfy Armijo's condition. When , we can choose in the order of , where is a local Lipschitz constant for the gradient near the point (see Lipschitz continuity). If the function is , then is close to the Hessian of the function at the point . See for more detail.
Upper bound for learning rates
In the same situation where , an interesting question is how large learning rates can be chosen in Armijo's condition (that is, when one has no limit on as defined in the section "Function minimization using backtracking line search in practice"), since larger learning rates when is closer to the limit point (if exists) can make convergence faster. For example, in Wolfe conditions, there is no mention of but another condition called curvature condition is introduced.
An upper bound for learning rates is shown to exist if one wants the constructed sequence converges to a non-degenerate critical point, see : The learning rates must be bounded from above roughly by . Here H is the Hessian of the function at the limit point, is its inverse, and is the norm of a linear operator. Thus, this result applies for example when one uses Backtracking line search for Morse functions. Note that in dimension 1, is a number and hence this upper bound is of the same size as the lower bound in the section "Lower bound for learning rates".
On the other hand, if the limit point is degenerate, then learning rates can be unbounded. For example, a modification of backtracking line search known as unbounded backtracking gradient descent (see ) allows the learning rate to be half the size , where is a constant. Experiments with simple functions such as show that unbounded backtracking gradient descent converges much faster than the basic version described in the section "Function minimization using backtracking line search in practice".
Time efficiency
An argument against the use of Backtracking line search, in particular in Large scale optimisation, is that satisfying Armijo's condition is expensive. There is a way (so-called Two-way Backtracking) to go around, with good theoretical guarantees and has been tested with good results on deep neural networks, see . (There, one can find also good/stable implementations of Armijo's condition and its combination with some popular algorithms such as Momentum and NAG, on datasets such as Cifar10 and Cifar100.) One observes that if the sequence converges (as wished when one makes use of an iterative optimisation method), then the sequence of learning rates should vary little when n is large enough. Therefore, in the search for , if one always starts from , one would waste a lot of time if it turns out that the sequence stays far away from . Instead, one should search for by starting from . The second observation is that could be larger than , and hence one should allow to increase learning rate (and not just decrease as in the section Algorithm). Here is the detailed algorithm for Two-way Backtracking: At step n
Set . Set and iteration counter . (Increase learning rate if Armijo's condition is satisfied.) If , then while this condition and the condition that are satisfied, repeatedly set and increase j. (Otherwise, reduce the learning rate if Armijo's condition is not satisfied.) If in contrast , then until the condition is satisfied that repeatedly increment and set Return for the learning rate .
(In one can find a description of an algorithm with 1), 3) and 4) above, which was not tested in deep neural networks before the cited paper.)
One can save time further by a hybrid mixture between two-way backtracking and the basic standard gradient descent algorithm. This procedure also has good theoretical guarantee and good test performance. Roughly speaking, we run two-way backtracking a few times, then use the learning rate we get from then unchanged, except if the function value increases. Here is precisely how it is done. One choose in advance a number , and a number .
Set iteration counter . At the steps , use Two-way Backtracking. At each step k in the set : Set . If , then choose and . (So, in this case, use the learning rate unchanged.) Otherwise, if , use Two-way Backtracking. Increase k by 1 and repeat. Increase by 1.
Theoretical guarantee (for gradient descent)
Compared with Wolfe's conditions, which is more complicated, Armijo's condition has a better theoretical guarantee. Indeed, so far backtracking line search and its modifications are the most theoretically guaranteed methods among all numerical optimization algorithms concerning convergence to critical points and avoidance of saddle points, see below.
Critical points are points where the gradient of the objective function is 0. Local minima are critical points, but there are critical points which are not local minima. An example is saddle points. Saddle points are critical points, at which there are at least one direction where the function is (local) maximum. Therefore, these points are far from being local minima. For example, if a function has at least one saddle point, then it cannot be convex. The relevance of saddle points to optimisation algorithms is that in large scale (i.e. high-dimensional) optimisation, one likely sees more saddle points than minima, see . Hence, a good optimisation algorithm should be able to avoid saddle points. In the setting of deep learning, saddle points are also prevalent, see . Thus, to apply in deep learning, one needs results for non-convex functions.