Speeding-up one-versus-all training for extreme classification via mean-separating initialization

Erik Schultheis, Rohit Babbar

Research output: Contribution to journalArticlepeer-review

8 Citations (SciVal)


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 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 training speedup of up to 5 × on Amazon-670K dataset with 670,000 labels. 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. The implementation can be found at https://github.com/xmc-aalto/dismecpp.

Original languageEnglish
Pages (from-to)3953-3976
Number of pages24
JournalMachine Learning
Issue number11
Publication statusPublished - 18 Oct 2022

Bibliographical note

Funding Open Access funding provided by Aalto University. Academy of Finland (347707)

Data availability http://manikvarma.org/downloads/XC/XMLRepository.html


  • 2nd order optimization
  • Class imbalance
  • Large-scale multi-label classification
  • Linear classification
  • Weight initialization

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Speeding-up one-versus-all training for extreme classification via mean-separating initialization'. Together they form a unique fingerprint.

Cite this