Backtracking line search

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (September 2020) (Learn how and when to remove this template message)

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

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

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

Based on a selected control parameter ${\displaystyle c\,\in \,(0,1)}$, the Armijo–Goldstein condition tests whether a step-wise movement from a current position ${\displaystyle \mathbf {x} }$ to a modified position ${\displaystyle \mathbf {x} +\alpha \,\mathbf {p} }$ achieves an adequately corresponding decrease in the objective function. The condition is fulfilled, see Armijo (1966), if ${\displaystyle 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 \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 ${\displaystyle \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 ${\displaystyle c}$ and ${\displaystyle \tau }$ that are less than 1. For example, Armijo used 1⁄2 for both ${\displaystyle c}$ and ${\displaystyle \tau }$ in Armijo (1966).

Algorithm[]

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

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

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

The value of ${\displaystyle \alpha _{j}}$ for the ${\displaystyle j}$ that fulfills the Armijo–Goldstein condition depends on ${\displaystyle \mathbf {x} }$ and ${\displaystyle \mathbf {p} }$, and is thus denoted below by ${\displaystyle \alpha (\mathbf {x} ,\mathbf {p} )}$. It also depends on ${\displaystyle f}$, ${\displaystyle \alpha _{0}}$, ${\displaystyle \tau }$ and ${\displaystyle c}$ 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 Armijo (1966), Bertsekas (2016):

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

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

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

Lower bound for learning rates[]

This addresses the question whether there is a systematic way to find a positive number ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ - depending on the function f, the point ${\displaystyle \mathbf {x} }$ and the descent direction ${\displaystyle \mathbf {p} }$ - so that all learning rates ${\displaystyle \alpha \leq \beta (\mathbf {x} ,\mathbf {p} )}$ satisfy Armijo's condition. When ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$, we can choose ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ in the order of ${\displaystyle 1/L(\mathbf {x} )\,}$, where ${\displaystyle L(\mathbf {x} )\,}$ is a local Lipschitz constant for the gradient ${\displaystyle \nabla f\,}$ near the point ${\displaystyle \mathbf {x} }$ (see Lipschitz continuity). If the function is ${\displaystyle C^{2}}$, then ${\displaystyle L(\mathbf {x} )\,}$ is close to the Hessian of the function at the point ${\displaystyle \mathbf {x} }$. See Armijo (1966) for more detail.

Upper bound for learning rates[]

In the same situation where ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$, an interesting question is how large learning rates can be chosen in Armijo's condition (that is, when one has no limit on ${\displaystyle \alpha _{0}}$ in the section "Function minimization using backtracking line search in practice"), since larger learning rates when ${\displaystyle \mathbf {x} _{n}}$ is closer to the limit point (if exists) can make convergence faster. For example, in Wolfe conditions, there is no mention of ${\displaystyle \alpha _{0}}$ but another condition called curvature condition is introduced.

An upper bound for learning rates is shown to exist if one wants the constructed sequence ${\displaystyle \mathbf {x} _{n}}$ converges to a non-degenerate critical point, see Truong & Nguyen (2020): The learning rates must be bounded from above roughly by ${\displaystyle ||H||\times ||H^{-1}||^{2}}$. Here H is the Hessian of the function at the limit point, ${\displaystyle H^{-1}}$ is its inverse, and ${\displaystyle ||.||}$ 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, ${\displaystyle H}$ 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, named Unbounded backtracking gradient descent (see Truong & Nguyen (2020)) allows learning rate to be in the size of ${\displaystyle ||\nabla f(\mathbf {x} _{n})||^{-\gamma }}$, where ${\displaystyle 1>\gamma >0}$ is a constant. Experiments with simple functions such as ${\displaystyle f(x,y)=x^{4}+y^{4}}$ show that Unbounded backtracking gradient descent converges much faster than the basic version 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 Truong & Nguyen (2020). (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 ${\displaystyle \mathbf {x} _{n}}$ converges (as wished when one makes use of an iterative optimisation method), then the sequence of learning rates ${\displaystyle \alpha _{n}}$ should vary little when n is large enough. Therefore, in the search for ${\displaystyle \alpha _{n}}$, if one always starts from ${\displaystyle \alpha _{0}}$, one would waste a lot of time if it turns out that the sequence ${\displaystyle \alpha _{n}}$ stays far away from ${\displaystyle \alpha _{0}}$. Instead, one should search for ${\displaystyle \alpha _{n}}$ by starting from ${\displaystyle \alpha _{n-1}}$. The second observation is that ${\displaystyle \alpha _{n}}$ could be larger than ${\displaystyle \alpha _{n-1}}$, 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

1. Set ${\displaystyle \gamma _{0}=\alpha _{n-1}}$. Set ${\displaystyle t=-c\,m}$ and iteration counter ${\displaystyle j\,=\,0}$.
2. (Increase learning rate if Armijo's condition is satisfied.) If ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$, then while this condition and the condition that ${\displaystyle \gamma _{j}\leq \alpha _{0}}$ are satisfied, repeatedly set ${\displaystyle \gamma _{j}=\alpha _{j-1}/\tau }$ and increase j.
3. (Otherwise, reduce the learning rate if Armijo's condition is not satisfied.) If in contrast ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{0}\,\mathbf {p} )<\gamma _{j}\,t,}$, then until the condition is satisfied that ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$ repeatedly increment ${\displaystyle j}$ and set ${\displaystyle \alpha _{j}=\tau \,\alpha _{j-1}\,.}$
4. Return ${\displaystyle \gamma _{j}}$ for the learning rate ${\displaystyle \alpha _{n}}$.

(In Nocedal & Wright (2000) one can find a description of an algorithm with 1), 3) and 4) above, which was not tested in DNN 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 N, and a number ${\displaystyle m\leq N}$.

1. Set iteration counter j=0.
2. At the steps ${\displaystyle jN+1,\ldots ,jN+m}$, use Two-way Backtracking.
3. At each step k in the set ${\displaystyle jN+m+1,\ldots ,jN+N-1}$: Set ${\displaystyle \alpha =\alpha _{k-2}}$. If ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})\geq 0}$, then choose ${\displaystyle \alpha _{k-1}=\alpha _{k-2}}$ and ${\displaystyle x_{k}=x_{k-1}+\alpha _{k-1}p_{k-1}}$. (So, in this case, use the learning rate ${\displaystyle \alpha _{k-2}}$ unchanged.) Otherwise, if ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})<0}$, use Two-way Backtracking. Increase k by 1 and repeat.
4. Increase j 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 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. 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 Attouch, Bolte & Svaiter (2011). 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 (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 about Stochastic gradient descent), then convergence is guaranteed, see for example Chapter 12 in Lange (2013). 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 f is only assumed to be ${\displaystyle C^{1}}$ and have at most countably many critical points, convergence is guaranteed, see Truong & Nguyen (2020). 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 Robbins & Monro (1951), see Bertsekas & Tsitsiklis (2006) for generalisations to less restrictive versions of Diminishing learning rate scheme. None of these results (for non-convex functions) have been proven for any other optimization algorithm so far.^{[citation needed]}

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 ${\displaystyle \mathbf {x} _{0}}$ (more precisely, outside a set of Lebesgue measure zero), the sequence constructed will not converge to a non-degenerate 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)). Under the same assumption that the gradient is Lipschitz continuous and one uses Diminishing learning rate scheme (see section Stochastic gradient descent), then avoidance of saddle points is established in Panageas, Piliouras & Wang (2019).

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 ${\displaystyle 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, which can be called Standard GD (to distinguish with SGD). In the Stochastic setting (such as in the mini-batch setting in Deep learning), Standard GD is called 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. 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 ${\displaystyle 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 ${\displaystyle 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.

Practicalities for using in the stochastic setting and implementing in DNN[]

The algorithm described above is for the deterministic setting, which as reported above has good theoretical guarantees. When one uses Armijo's algorithm in real life settings where random features play important roles, there are practicalities one needs to take care about. This section describes some main points to be noted in the more theoretical setting of stochastic optimization and the more realistic setting of mini-batch in DNN.

1) Stochastic optimization:

The typical statement of this setting is as follows: Assume that we have a function ${\displaystyle f(x,\xi )}$ depending on a random variable ${\displaystyle \xi }$. Now we want to find minimum of the expectation function ${\displaystyle F(x):=E(f(x,\xi ))}$, here ${\displaystyle E(.)}$ computes the expectation with respect to the random variable ${\displaystyle \xi }$.

In general, it is very difficult to compute the expectation, in particular when working for example with DNN (see the next part). Therefore, we can only do as follows:

At step n: choose randomly ${\displaystyle k_{n}}$ variables ${\displaystyle \xi _{n,1},\xi _{n,2},\ldots ,\xi _{n,k_{n}}}$ (with respect to the given distribution), and replace the (unknown) function ${\displaystyle F(x)}$ by an approximation ${\displaystyle F_{n}(x):={\frac {1}{k_{n}}}\sum _{i=1}^{k_{n}}f(x,\xi _{i})}$.

We need to modify Armijo's backtracking line search as follows: Then the descent direction is chosen as ${\displaystyle p_{n}=-\nabla F_{n}(x)}$ and the Armijo's learning rate ${\displaystyle \alpha (x_{n},p_{n})}$ is chosen relative to the function ${\displaystyle F_{n}(x)}$.

It is noted that in general ${\displaystyle k_{n}}$ is allowed to change. There are works which let ${\displaystyle k_{n}}$ increase. The following example explains the motivation for such a scheme (also, see theoretical justification later). However, it will be explained in the section about implementing in DNN that there are difficulties/not very good performance with implementing this scheme.

Example 1: Consider the simple function ${\displaystyle F(x)=x^{2}}$, which is convex with a unique critical point ${\displaystyle x=0}$. Recall the normal distribution ${\displaystyle N(1,\sigma ^{2})}$. Then ${\displaystyle F(x)=E(\xi x^{2})}$, where ${\displaystyle \xi }$ is a random variable with distribution ${\displaystyle N(1,\sigma ^{2})}$. Then, one can check with Python, that if we choose ${\displaystyle \sigma ^{2}=100}$ and ${\displaystyle k_{n}=1}$ for all step n, and run Armijo's Backtracking line search with maximum learning rate ${\displaystyle \alpha _{0}=1}$, in this setting as described above, then we have divergence (not convergence as one would hope for this too simple convex function)! [What happens here is that, while small, there is a non-zero probability of the random value of ${\displaystyle \xi }$ is ${\displaystyle <0}$, in which case what Armijo's backtracking line search will do is to push away from the point 0 a lot!]

Another way is, originating from the classical work Robbins & Monro (1951), in SGD to keep ${\displaystyle k_{n}}$ constant (even can choose to be always 1), but let the learning rates ${\displaystyle \delta _{n}}$ going to 0. [Even if the random value of ${\displaystyle \xi }$ is ${\displaystyle <0}$, since the learning rate ${\displaystyle \delta _{n}}$ is smaller and smaller, this scheme will push away from 0 less than Backtracking.] While this scheme works well also for this example, again in the setting of DNN the experimental results are not very good.

It is worthy to note also that if one uses SGD and keeps k_n constant, but also learning rates constant, then one can observe divergence even for some values of the learning rates for which there is convergence guarantee for F(x). So what mentions in Example 1 is not the fault of Backtracking itself, but also for SGD, the most studied optimization algorithm.

Example 1'. The same function F(x) and distribution ${\displaystyle N(1,\sigma ^{2})}$. Choose ${\displaystyle \sigma ^{2}=100}$ and ${\displaystyle k_{n}=1}$ for all step n. Note that the function F(x) is ${\displaystyle C_{L}^{1,1}}$ with ${\displaystyle L=2}$. Hence, by classical theory, for learning rate ${\displaystyle <1/(2L)=0.25}$, SGD with constant learning rate will converge for F(x). However, one check with Python that for the associated stochastic optimization problem, even with the choice of a smaller learning rate 0.1, one observes divergence to infinity! On the other hand, with the learning rate 0.05 then one observes convergence to the minimum 0. Therefore, it seems that even for this simple function, the choice of (constant) learning rate must take into account the distribution, and not just that from the deterministic function F(x), for to obtain convergence for the stochastic optimization problem. [Note: if here one runs Armijo's Backtracking line search with maximum learning rate ${\displaystyle \alpha _{0}=0.2>0.1}$, then one observes convergence! Hence, still Armijo's Backtracking line search helps with choosing a good learning rate to use, compared to SGD with constant learning rates.]

A typical theoretical result (in the literature, one may find weaker results than what stated here, either because requiring stronger assumptions or proving weaker conclusions) in this setting is as follows:

Prototype theorem: Let ${\displaystyle F(x)}$ be convex (or strongly convex) and in ${\displaystyle C_{L}^{1,1}}$. Then both of the following schemes guarantee convergence: Scheme 1: Backtracking with increasing "mini-batch" sizes ${\displaystyle k_{n}}$. Scheme 2: SGD with learning rates decreasing to 0.

Why these schemes yield not very good experimental results in DNN can be because:

- The implementation does not take into account the differences between stochastic optimization and DNN (see more in the next section);

and/or

- The assumptions of these theoretical results are not satisfied (too strong to be satisfied) by the cost functions in DNN.

It is worthy to notice that current successful implementations of Backtracking in DNN use constant mini-batch sizes ${\displaystyle k_{n}=constant}$. However, the difference with Example 1 is that one does not choose k_n=1 since that is too small. Indeed, one has the following.

Example 2. Let the function F(x) and the distribution ${\displaystyle N(1,\sigma ^{2})}$ be as in Example 1, where ${\displaystyle \sigma ^{2}=100}$. If one chooses ${\displaystyle k_{n}=500}$ for all n, then one can check with Python that Armijo's backtracking line search with maximum learning rate ${\displaystyle \alpha _{0}=1}$ in this stochastic setting converges!

This can be explained that in this example, choosing ${\displaystyle k_{n}=1}$ for all n is not good enough to approximate the function F(x), but choosing ${\displaystyle k_{n}=500}$ for all n is a good approximation. The same story happens with DNN: one needs to choose a big enough mini-batch size depending on the specific question and setting (see next section). People who are familiar with undergraduate calculus can find an analogy in using Riemann sums to approximate an integral.

2) DNN:

While stochastic optimization is meant to be a theoretical model for what happens in training DNN, in practice there are important differences in many aspects: assumptions, resources, ways to proceed and goals.

Assumptions: in stochastic optimization, among many others, there is usually the requirement that the cost function is (strongly-)convex. This is hardly satisfied or verified in practice.

Summary[]

In summary, Backtracking line search (and modifications) is a method which is easy to implement, is applicable for very general functions, has very good theoretical guarantee (for both convergence to critical points and avoidance of saddle points) and works well in practice. Several other methods which have good theoretical guarantee, such as Diminishing learning rates or Standard GD with learning rate <1/L - both require the gradient of the objective function to be Lipschitz continuous, turn out to be a special case of Backtracking line search or satisfy Armijo's condition. Even though a priori one needs the cost function to be continuously differentiable to apply this method, in practice one can apply this method successfully also for functions which are continuously differentiable on a dense open subset such as ${\displaystyle f(t)=|t|}$ or ${\displaystyle f(t)=ReLu(t)=\max\{t,0\}}$. The latter functions appear in Deep Neural Networks.

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.
• 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.
• Attouch, H.; Bolte, J.; Svaiter, B. F. (2011). "Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods". Mathematical Programming. 137 (1–2): 91–129. doi:10.1007/s10107-011-0484-9.
• Bertsekas, Dimitri P. (2016), Nonlinear Programming, Athena Scientific, ISBN 978-1886529052
• Bertsekas, D. P.; Tsitsiklis, J. N. (2006). "Gradient convergence in gradient methods with errors". SIAM J. Optim. 10 (3): 627–642. doi:10.1137/S1052623497331063.
• Bray, A. J.; Dean, D. S. (2007). "Statistics of critical points of gaussian fields on large-dimensional spaces". Physical Review Letters. 98 (15): 150–201. arXiv:cond-mat/0611023. Bibcode:2007PhRvL..98o0201B. doi:10.1103/PhysRevLett.98.150201. PMID 17501322.
• 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. arXiv:1406.2572.
• 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". . 49: 1246–1257.
• 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.
• Panageas, I.; Piliouras, G.; Wang, X. (2019). "First-order methods almost always avoid saddle points: The case of vanishing step-sizes" (PDF). NeurIPS. arXiv:1906.07772.
• Robbins, H.; Monro, S. (1951). "A stochastic approximation method". Annals of Mathematical Statistics. 22 (3): 400–407. doi:10.1214/aoms/1177729586.
• Truong, T. T.; Nguyen, H.-T. (6 September 2020). "Backtracking Gradient Descent Method and Some Applications in Large Scale Optimisation. Part 2: Algorithms and Experiments". Applied Mathematics & Optimization: 30. doi:10.1007/s00245-020-09718-8.CS1 maint: date and year (link)