  We present and analyze a momentum-based gradient method for training linear
classifiers with an exponentially-tailed loss (e.g., the exponential or
logistic loss), which maximizes the classification margin on separable data at
a rate of $\widetilde{\mathcal{O}}(1/t^2)$. This contrasts with a rate of
$\mathcal{O}(1/\log(t))$ for standard gradient descent, and $\mathcal{O}(1/t)$
for normalized gradient descent. This momentum-based method is derived via the
convex dual of the maximum-margin problem, and specifically by applying
Nesterov acceleration to this dual, which manages to result in a simple and
intuitive method in the primal. This dual view can also be used to derive a
stochastic variant, which performs adaptive non-uniform sampling via the dual
variables.
