  We show that running gradient descent with variable learning rate guarantees
loss $f(x) \leq 1.1 \cdot f(x^*) + \epsilon$ for the logistic regression
objective, where the error $\epsilon$ decays exponentially with the number of
iterations and polynomially with the magnitude of the entries of an arbitrary
fixed solution $x^*$. This is in contrast to the common intuition that the
absence of strong convexity precludes linear convergence of first-order
methods, and highlights the importance of variable learning rates for gradient
descent. We also apply our ideas to sparse logistic regression, where they lead
to an exponential improvement of the sparsity-error tradeoff.
