Naive Line Search for Gradient Descent I'm trying to understand the Line Search approach to Gradient Descent (http://en.wikipedia.org/wiki/Line_search). It seems that a naive implementation would
while (termination criteria not met)
    1) Compute gradient at a current location
    2) Move in that direction until the objective function begins to increase
    3) Set current location to the location before the "increase" in step 2
    4) GOTO 1

Is this understanding correct?
 A: More or less ;-) If you knew the minimum (what you are looking for), you could move "until the objective function begins to increase". But you don't know the minimum, so you must try a "good enough" step length $\alpha_k$. There are several ways, for example you can look for a step length such that:


*

*the function decreases, i.e. $h(\alpha_k)=f(x_k+\alpha_k p_k)< f(x_k)$, and the reduction is proportional to both the step length and the directional derivative (sufficient decrease condition);

*the slope of $h$ at $a_k$, $h'(\alpha_k)$, is greater than the initial slope (curvature condition); the initial slope is negative, so:


*

*if $h'(\alpha_k)$ is greater because it's positive, then you can expect that $f$ increases if you choose a step greater than $\alpha_k$;

*if it is greater because still negative but lesser in absolute value, then $\alpha_k$ is a good step toward the minimum.


A: Not really your question, but fyinfo,
Stochastic gradient descent, SGD,
is a form of gradient descent with no line search, no function values at all,
gradients only.
My non-expert explanation is that you may have either or both of


*

*func(): cheap or expensive, noisy or not

*gradient(): ditto


so there are very different methods if you have func() only -- Derivative-free optimization, DFO --
or huge, noisy ML problems with fast gradients -- SGD;
see
SGDClassifier
and SGDRegressor
in scikit-learn .
Even when you have both func() and gradient(), 
it's not at all clear how to tradeoff
for low total cost ~  Nfunc * Funccost + Ngrad * Gradcost.)
Fwiw, I've found gradient descent with simplest-possible line search,
take the best of [.1 .5 1 2] * stepsize * gradient(),
not bad.
