Speeding-up One-vs-All Training for Extreme Classification via Smart
  Initialization
  In this paper we show that a simple, data dependent way of setting the
initial vector can be used to substantially speed up the training of linear
one-versus-all (OVA) classifiers in extreme multi-label classification (XMC).
We discuss the problem of choosing the initial weights from the perspective of
three goals. We want to start in a region of weight space a) with low loss
value, b) that is favourable for second-order optimization, and c) where the
conjugate-gradient (CG) calculations can be performed quickly. For margin
losses, such an initialization is achieved by selecting the initial vector such
that it separates the mean of all positive (relevant for a label) instances
from the mean of all negatives -- two quantities that can be calculated quickly
for the highly imbalanced binary problems occurring in XMC. We demonstrate a
speedup of $\approx 3\times$ for training with squared hinge loss on a variety
of XMC datasets. This comes in part from the reduced number of iterations that
need to be performed due to starting closer to the solution, and in part from
an implicit negative mining effect that allows to ignore easy negatives in the
CG step. Because of the convex nature of the optimization problem, the speedup
is achieved without any degradation in classification accuracy.
