Efficiency of Line Search in Proximal Gradient Methods

Line search methods are very effective in practice for speeding up first-order methods for minimizing smooth functions. The step size found by a line-search procedure during each iteration can be regarded as the reciprocal of a local Lipschitz constant. We show that the convergence speed of first-order methods equipped with a simple line-search procedure depends on the harmonic mean of the local Lipschitz constants.