  We consider the problem of efficiently computing the maximum likelihood
estimator in Generalized Linear Models (GLMs) when the number of observations
is much larger than the number of coefficients ($n \gg p \gg 1$). In this
regime, optimization algorithms can immensely benefit from approximate second
order information. We propose an alternative way of constructing the curvature
information by formulating it as an estimation problem and applying a
Stein-type lemma, which allows further improvements through sub-sampling and
eigenvalue thresholding. Our algorithm enjoys fast convergence rates,
resembling that of second order methods, with modest per-iteration cost. We
provide its convergence analysis for the general case where the rows of the
design matrix are samples from a sub-gaussian distribution. We show that the
convergence has two phases, a quadratic phase followed by a linear phase.
Finally, we empirically demonstrate that our algorithm achieves the highest
performance compared to various algorithms on several datasets.
