Mathematical optimization method
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 formula_1 and a search direction formula_2, the task of a line search is to determine a step size formula_3 that adequately reduces the objective function formula_4 (assumed formula_5 i.e. continuously differentiable), i.e., to find a value of formula_6 that reduces formula_7 relative to formula_8. However, it is usually undesirable to devote substantial resources to finding a value of formula_6 to precisely minimize formula_10. 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 formula_6 that provides a reasonable amount of improvement in the objective function, rather than to find the actual minimizing value of formula_6.
The backtracking line search starts with a large estimate of formula_6 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 formula_14
Define the local slope of the function of formula_6 along the search direction formula_2 as formula_17 (where formula_18 denotes the dot product). It is assumed that formula_2 is a vector for which some local decrease is possible, i.e., it is assumed that formula_20.
Based on a selected control parameter formula_21, the Armijo–Goldstein condition tests whether a step-wise movement from a current position
formula_1 to a modified position formula_23 achieves an adequately corresponding decrease in the objective function. The condition is fulfilled, see , if formula_24
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 formula_25 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 formula_26 until the Armijo–Goldstein condition is fulfilled.
The search will terminate after a finite number of steps for any positive values of formula_27 and formula_28 that are less than 1. For example, Armijo used ;templatestyles src="Fraction/styles.css" / ;1⁄2 for both formula_27 and formula_28 in .
Algorithm.
This condition is from . Starting with a maximum candidate step size value formula_31, using search control parameters formula_26 and formula_21, the backtracking line search algorithm can be expressed as follows:
In other words, reduce formula_40 by a factor of formula_41 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 formula_42, formula_43, to converge to a minimum, provided such a minimum exists and formula_44 is selected appropriately in each step. For gradient descent, formula_44 is selected as formula_46.
The value of formula_39 for the formula_37 that fulfills the Armijo–Goldstein condition depends on formula_1 and formula_2, and is thus denoted below by formula_51. It also depends on formula_10, formula_40, formula_28 and formula_27 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 , :
To assure good behavior, it is necessary that some conditions must be satisfied by formula_44. Roughly speaking formula_44 should not be too far away from formula_65. A precise version is as follows (see e.g. ). There are constants formula_66 so that the following two conditions are satisfied:
Lower bound for learning rates.
This addresses the question whether there is a systematic way to find a positive number formula_79 - depending on the function f, the point formula_1 and the descent direction formula_2 - so that all learning rates formula_82 satisfy Armijo's condition. When formula_83, we can choose formula_79 in the order of formula_85, where formula_86 is a local Lipschitz constant for the gradient formula_87 near the point formula_1 (see Lipschitz continuity). If the function is formula_89, then formula_86 is close to the Hessian of the function at the point formula_1. See for more detail.
Upper bound for learning rates.
In the same situation where formula_83, an interesting question is how large learning rates can be chosen in Armijo's condition (that is, when one has no limit on formula_40 as defined in the section "Function minimization using backtracking line search in practice"), since larger learning rates when formula_42 is closer to the limit point (if exists) can make convergence faster. For example, in Wolfe conditions, there is no mention of formula_40 but another condition called curvature condition is introduced. 
An upper bound for learning rates is shown to exist if one wants the constructed sequence formula_42 converges to a non-degenerate critical point, see : The learning rates must be bounded from above roughly by formula_97. Here H is the Hessian of the function at the limit point, formula_98 is its inverse, and formula_99 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, formula_100 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 formula_101, where formula_102 is a constant. Experiments with simple functions such as formula_103 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 formula_61 converges (as wished when one makes use of an iterative optimisation method), then the sequence of learning rates formula_105 should vary little when n is large enough. Therefore, in the search for formula_105, if one always starts from formula_40, one would waste a lot of time if it turns out that the sequence formula_105 stays far away from formula_40. Instead, one should search for formula_105 by starting from formula_111. The second observation is that formula_105 could be larger than formula_111, 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
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 formula_126, and a number formula_127.
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.
For convergence to critical points: For example, if the cost function is a real analytic function, then it is shown in that convergence is guaranteed. The main idea is to use Łojasiewicz inequality which is enjoyed by a real analytic function. For non-smooth functions satisfying Łojasiewicz inequality, the above convergence guarantee is extended, see . In , there is a proof that for every sequence constructed by backtracking line search, a cluster point (i.e. the limit of one subsequence, if the subsequence converges) is a critical point. For the case of a function with at most countably many critical points (such as a Morse function) and compact sublevels, as well as with Lipschitz continuous gradient where one uses standard GD with learning rate ;1/L (see the section "Stochastic gradient descent"), then convergence is guaranteed, see for example Chapter 12 in . Here the assumption about compact sublevels is to make sure that one deals with compact sets of the Euclidean space only. In the general case, where formula_10 is only assumed to be formula_5 and have at most countably many critical points, convergence is guaranteed, see . In the same reference, similarly convergence is guaranteed for other modifications of Backtracking line search (such as Unbounded backtracking gradient descent mentioned in the section "Upper bound for learning rates"), and even if the function has uncountably many critical points still one can deduce some non-trivial facts about convergence behaviour. In the stochastic setting, under the same assumption that the gradient is Lipschitz continuous and one uses a more restrictive version (requiring in addition that the sum of learning rates is infinite and the sum of squares of learning rates is finite) of diminishing learning rate scheme (see section "Stochastic gradient descent") and moreover the function is strictly convex, then the convergence is established in the well-known result , see for generalisations to less restrictive versions of a diminishing learning rate scheme. None of these results (for non-convex functions) have been proven for any other optimization algorithm so far.
For avoidance of saddle points: For example, if the gradient of the cost function is Lipschitz continuous and one chooses standard GD with learning rate ;1/L, then with a random choice of initial point formula_56 (more precisely, outside a set of Lebesgue measure zero), the sequence constructed will not converge to a non-degenerate saddle point (proven in ), and more generally it is also true that the sequence constructed will not converge to a degenerate saddle point (proven in ). Under the same assumption that the gradient is Lipschitz continuous and one uses a diminishing learning rate scheme (see the section "Stochastic gradient descent"), then avoidance of saddle points is established in .
A special case: (standard) stochastic gradient descent (SGD).
While it is trivial to mention, if the gradient of a cost function is Lipschitz continuous, with Lipschitz constant L, then with choosing learning rate to be constant and of the size formula_139,