Backtracking line search

In (unconstrained) minimization, a backtracking line search, a search scheme based on the Armijo–Goldstein condition, is a line search method to determine the amount to move along a given search direction. It involves starting with a relatively large estimate of the step size for movement along the 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 decrease that is expected, based on the local gradient of the objective function.

Backtracking line search is typically used for gradient descent, but it can also 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 $\mathbf {x}$ and a search direction $\mathbf {p}$, the task of a line search is to determine a step size $\alpha >0$ that adequately reduces the objective function $f:\mathbb {R} ^{n}\to \mathbb {R}$ (assumed smooth), i.e., to find a value of $\alpha$ that reduces $f(\mathbf {x} +\alpha \,\mathbf {p} )$ relative to $f(\mathbf {x} )$. However, it is usually undesirable to devote substantial resources to finding a value of $\alpha$ to precisely minimize $f$. 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 $\alpha$ that provides a reasonable amount of improvement in the objective function, rather than to find the actual minimizing value of $\alpha$.

The backtracking line search starts with a large estimate of $\alpha$ 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 $\nabla f(\mathbf {x} )\,.$

Define the local slope of the function of $\alpha$ along the search direction $\mathbf {p}$ as $m=\nabla f(\mathbf {x} )^{\mathrm {T} }\,\mathbf {p} =\langle \nabla f(\mathbf {x} ),\mathbf {p} \rangle$ (where $\langle \cdot ,\cdot \rangle$ denotes the dot product). It is assumed that $\mathbf {p}$ is a vector for which some local decrease is possible, i.e., it is assumed that $m<0$.

Based on a selected control parameter $c\,\in \,(0,1)$, the Armijo–Goldstein condition tests whether a step-wise movement from a current position $\mathbf {x}$ to a modified position $\mathbf {x} +\alpha \,\mathbf {p}$ achieves an adequately corresponding decrease in the objective function. The condition is fulfilled, see Armijo (1966), if $f(\mathbf {x} +\alpha \,\mathbf {p} )\leq f(\mathbf {x} )+\alpha \,c\,m\,.$

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 $\displaystyle \alpha$ 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 $\tau \,\in \,(0,1)$ until the Armijo–Goldstein condition is fulfilled.

The search will terminate after a finite number of steps for any positive values of $c$ and $\tau$ that are less than 1. For example, Armijo used 1⁄2 for both $c$ and $\tau$ in Armijo (1966).

Algorithm

This condition is from Armijo (1966). Starting with a maximum candidate step size value $\alpha _{0}>0\,$, using search control parameters $\tau \,\in \,(0,1)$ and $c\,\in \,(0,1)$, the backtracking line search algorithm can be expressed as follows:

1. Set $t=-c\,m$ and iteration counter $j\,=\,0$.
2. Until the condition is satisfied that $f(\mathbf {x} )-f(\mathbf {x} +\alpha _{j}\,\mathbf {p} )\geq \alpha _{j}\,t,$ repeatedly increment $j$ and set $\alpha _{j}=\tau \,\alpha _{j-1}\,.$
3. Return $\alpha _{j}$ as the solution.

In other words, reduce $\alpha _{0}$ by a factor of $\tau \,$ 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 $\mathbf {x} _{n}$, $n=1,2,...$, to converge to a minimum, provided such a minimum exists and $\mathbf {p} _{n}$ is selected appropriately in each step. For gradient descent, $\mathbf {p} _{n}$ is selected as $-\nabla f(\mathbf {x} _{n})$.

The value of $\alpha _{j}$ for the $j$ that fulfills the Armijo–Goldstein condition depends on $\mathbf {x}$ and $\mathbf {p}$, and is thus denoted below by $\alpha (\mathbf {x} ,\mathbf {p} )$. It also depends on $f$, $\alpha _{0}$, $\tau$ and $c$ of course, although these dependencies can be left implicit if are assumed to be fixed with respect to the optimization problem.

The detailed steps are thus, see Armijo (1966), Bertsekas (2016):

1. Choose an initial starting point $\mathbf {x} _{0}$ and set the iteration counter $n=0$.
2. Until some stopping condition is satisfied, choose a descent direction $\mathbf {p} _{n}$, increment $n$, and update the position to $\mathbf {x} _{n+1}=\mathbf {x} _{n}+\alpha (\mathbf {x} _{n},\mathbf {p} _{n})\,\mathbf {p} _{n}$.
3. Return $\mathbf {x} _{n}$ as the minimizing position and $f(\mathbf {x} _{n})$ as the function minimum.

To assure good behavior, it is necessary that some conditions must be satisfied by $\mathbf {p} _{n}$. Roughly speaking $\mathbf {p} _{n}$ should not be too far away from $\nabla f(\mathbf {x} _{n})$. A precise version is as follows (see e.g. Bertsekas (2016)). There are constants $C_{1},C_{2}>0$ so that the following two conditions are satisfied:

1. For all n, $\|\mathbf {p} _{n}\|\geq C_{1}\,\|\nabla f(\mathbf {x} _{n})\|$. Here, $\|y\|$ is the Euclidean norm of $y$. (This assures that if $\mathbf {p} _{n}=0$, then also $\nabla f(\mathbf {x} _{n})=0$. More generally, if $\lim _{n\rightarrow \infty }\mathbf {p} _{n}=0$, then also $\lim _{n\rightarrow \infty }\nabla f(\mathbf {x} _{n})=0$.) A more strict version requires also the reverse inequality: $\|\mathbf {p} _{n}\|\leq C_{3}\,\|\nabla f(\mathbf {x} _{n})\|$ for a positive constant $C_{3}>0$.
2. For all n, $\|\mathbf {p} _{n}\|\,\|\nabla f(\mathbf {x} _{n})\|\leq -C_{2}\,\langle \mathbf {p} _{n},\nabla f(\mathbf {x} _{n})\rangle$. (This condition ensures that the directions of $\mathbf {p} _{n}$ and $\nabla f(\mathbf {x} _{n})$ are similar.)

Lower bound for gradient descent

A lower bound for learning rates satisfying Armijo's condition, where $\mathbf {p} =-\nabla f(\mathbf {x} )$, is in the order of $1/L(\mathbf {x} )\,$, where $L(\mathbf {x} )\,$ is a local Lipschitz constant for the gradient $\nabla f\,$ near the point $\mathbf {x}$ (see Lipschitz continuity). See Armijo (1966) for more detail.

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 point (mathematics) and avoidance of Saddle point, see below.

Critical point (mathematics) 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 point 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 function. 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 Bray & Dean (2007). Hence, a good optimisation algorithm should be able to avoid saddle points. In the setting of Deep learning, saddle points are also prevalent, see Dauphin et al. (2014). 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 Absil, Mahony & Andrews (2005) that convergence is guaranteed. In Bertsekas (2016), 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 and compact sublevels (see Level set), as well as with Lipschitz continuous gradient where one uses Standard GD with learning rate <1/L (see the section about Stochastic gradient descent), then convergence is guaranteed, see for example Chapter 12 in Lange (2013).

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 $\mathbf {x} _{0}$ (more precisely, outside a set of Lebesgue measure zero), the sequence constructed will not converge to a non-degenerate (see Critical point) saddle point (proven in Lee et al. (2016)), and more generally it is also true that the sequence constructed will not converge to a degenerate saddle point (proven in Panageas & Piliouras (2017)).

None of these results have been proven for any other optimization algorithm so far.

A special case: (Standard) Stochastic gradient descent

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 1/L, one has a special case of Backtracking line search (for gradient descent). This has been used at least in Armijo (1966). This scheme however requires that one needs to have a good estimate for L, otherwise if learning rate is too big (relative to 1/L) then the scheme has no convergence guarantee. One can see what will go wrong if the cost function is a smoothing (near the point 0) of the function f(t)=|t|. Such a good estimate is, however, difficult and laborious in large dimensions. Also, if the gradient of the function is not globally Lipschitz continuous, then this scheme has no convergence guarantee. For example, this is similar to an exercise in Bertsekas (2016), for the cost function $f(t)=|t|^{1.5}\,$ and for whatever constant learning rate one chooses, with a random initial point the sequence constructed by this special scheme does not converge to the global minimum 0.

If one does not care about the condition that learning rate must be bounded by 1/L, then this special scheme has been used much older, at least since 1847 by Cauchy Gradient descent, which can be called Standard GD (to distinguish with SGD). In the Stochastic setting (such as in the mini-batch setting in Deep learning Deep learning), Standard GD is called Stochastic gradient descent Stochastic gradient descent, or SGD.

Even if the cost function has globally continuous gradient, good estimate of the Lipschitz constant for the cost functions in Deep Learning may not be feasible or desirable, given the very high dimensions of Deep neural networks Deep learning. Hence, there is a technique of fine-tuning of learning rates in applying Standard GD or SGD. One way is to choose many learning rates from a grid search, with the hope that some of the learning rates can give good results. (However, if the loss function does not have global Lipschitz continuous gradient, then the example with $f(t)=|t|^{1.5}\,$ above shows that grid search cannot help.) Another way is the so-called adaptive Standard GD or SGD, some representatives are Adam, Adadelta, RMSProp and so on, see Stochastic gradient descent. In adaptive Standard GD or SGD, learning rates are allowed to vary at each iterate step n, but in a different manner from Backtracking line search for gradient descent. Apparently, it would be more expensive to use Backtracking line search for gradient descent, since one needs to do a loop search until Armijo's condition is satisfied, while for adaptive Standard GD or SGD no loop search is needed. Most of these adaptive Standard GD or SGD do not have the descent property $f(x_{n+1})\leq f(x_{n})$, for all n, as Backtracking line search for gradient descent. Only a few has this property, and which have good theoretical properties, but they turn out to be special cases of Backtracking line search or more generally Armijo's condition Armijo (1966). The first one is when one chooses learning rate to be a constant <1/L, as mentioned above, if one can have a good estimate of L. The second is so called Diminshing learning rate, used in the well known paper by Robbins & Monro (1951), if again the function has globally Lipschitz continuous gradient (but the Lipschitz constant may be unknown) and the learning rates converge to 0.

See also

• Gradient descent
• Stochastic gradient descent
• Wolfe conditions

References

• Absil, P. A.; Mahony, R.; Andrews, B. (2005). "Convergence of the iterates of Descent methods for analytic cost functions". SIAM J. Optim. 16 (2): 531–547. doi:10.1137/040605266. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
• Armijo, Larry (1966). "Minimization of functions having Lipschitz continuous first partial derivatives". Pacific J. Math. 16 (1): 1–3. doi:10.2140/pjm.1966.16.1.
• Bertsekas, Dimitri P. (2016), Nonlinear Programming, Athena Scientific, ISBN 978-1886529052
• Bray, A. J.; Dean, D. S. (2007). "Statistics of critical points of gaussian fields on large-dimensional spaces". Physical Review Letters. 98: 150201. doi:10.1103/PhysRevLett.98.150201. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
• Dauphin, Y. N.; Pascanu, R.; Gulcehre, C.; Cho, K.; Ganguli, S.; Bengio, Y. (2014). "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization". NeurIPS. 14: 2933–2941.
• Lange, K. (2013). Optimization. New York: Springer-Verlag Publications. ISBN 978-1-4614-5838-8.
• Dennis, J. E.; Schnabel, R. B. (1996). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Philadelphia: SIAM Publications. ISBN 978-0-898713-64-0.
• Lee, J. D.; Simchowitz, M.; Jordan, M. I.; Recht, B. (2016). "Gradient descent only converges to minimizers". Proceedings of Machine Learning Research. 49: 1246–1257. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
• Nocedal, Jorge; Wright, Stephen J. (2000), Numerical Optimization, Springer-Verlag, ISBN 0-387-98793-2
• Panageas, I.; Piliouras, G. (2017). "Gradient descent only converges to minimizers: non-isolated critical points and invariant regions" (PDF). Innovations in theoretical computer science conference: 2:1-2:12. doi:10.4230/LIPIcs.ITCS.2017.2. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
• Robbins, H.; Monro, S. (1951). "A stochastic approximation method". Annals of Mathematical Statistics. 22 (3): 400–407.