Extreme Classification via Adversarial Softmax Approximation
This work solves the computational bottleneck in training classifiers with many classes, which is crucial for applications in technology, science, and e-commerce, representing a strong incremental improvement.
The paper tackles the problem of extreme classification by addressing the slow convergence of uniform negative sampling in softmax approximations, proposing an adversarial sampling method that reduces training time by an order of magnitude on large-scale datasets.
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.