Training a classifier over a large number of classes, known as 'extreme
classification', has become a topic of major interest with applications in
technology, science, and e-commerce. Traditional softmax regression induces a
gradient cost proportional to the number of classes $C$, which often is
prohibitively expensive. A popular scalable softmax approximation relies on
uniform negative sampling, which suffers from slow convergence due a poor
signal-to-noise ratio. In this paper, we propose a simple training method for
drastically enhancing the gradient signal by drawing negative samples from an
adversarial model that mimics the data distribution. Our contributions are
three-fold: (i) an adversarial sampling mechanism that produces negative
samples at a cost only logarithmic in $C$, thus still resulting in cheap
gradient updates; (ii) a mathematical proof that this adversarial sampling
minimizes the gradient variance while any bias due to non-uniform sampling can
be removed; (iii) experimental results on large scale data sets that show a
reduction of the training time by an order of magnitude relative to several
competitive baselines.

本文提出一种简单的训练方法，通过从模仿数据分布的对抗模型中绘制负样本来大大增强梯度信号，以实现极端分类的高效训练，并在大规模数据集上实现了训练时间相对于几个竞争基线的数量级的减少。