  We propose approximately exact line search (AELS), which uses only function
evaluations to select a step size within a constant fraction of the exact line
search minimizer of a unimodal objective. We bound the number of iterations and
function evaluations of AELS, showing linear convergence on smooth, strongly
convex objectives with no dependence on the initial step size for three descent
methods: steepest descent using the true gradient, approximate steepest descent
using a gradient approximation, and random direction search. We demonstrate
experimental speedup compared to Armijo line searches and other baselines on
weakly regularized logistic regression for both gradient descent and minibatch
stochastic gradient descent and on a benchmark set of derivative-free
optimization objectives using quasi-Newton search directions. We also analyze a
simple line search for the strong Wolfe conditions, finding upper bounds on
iteration and function evaluation complexity similar to AELS. Experimentally we
find AELS is much faster on deterministic and stochastic minibatch logistic
regression, whereas Wolfe line search is slightly faster on the DFO benchmark.
Our findings suggest that line searches and AELS in particular may be more
useful in the stochastic optimization regime than commonly believed.
