  The goal in extreme multi-label classification is to learn a classifier which
can assign a small subset of relevant labels to an instance from an extremely
large set of target labels. Datasets in extreme classification exhibit a long
tail of labels which have small number of positive training instances. In this
work, we pose the learning task in extreme classification with large number of
tail-labels as learning in the presence of adversarial perturbations. This view
motivates a robust optimization framework and equivalence to a corresponding
regularized objective.
  Under the proposed robustness framework, we demonstrate efficacy of Hamming
loss for tail-label detection in extreme classification. The equivalent
regularized objective, in combination with proximal gradient based
optimization, performs better than state-of-the-art methods on propensity
scored versions of precision@k and nDCG@k(upto 20% relative improvement over
PFastreXML - a leading tree-based approach and 60% relative improvement over
SLEEC - a leading label-embedding approach). Furthermore, we also highlight the
sub-optimality of a sparse solver in a widely used package for large-scale
linear classification, which is interesting in its own right. We also
investigate the spectral properties of label graphs for providing novel
insights towards understanding the conditions governing the performance of
Hamming loss based one-vs-rest scheme vis-\`a-vis label embedding methods.
