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 j=0. 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 j by 1. Theoretical guarantee (for gradient descent) Compared with Wolfe's conditions, which is more